1 //===- DependenceAnalysis.cpp - Dependence analysis on SSA views ----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements view-based alias and dependence analyses.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "mlir/Dialect/Linalg/Analysis/DependenceAnalysis.h"
14 #include "mlir/Dialect/Linalg/IR/LinalgOps.h"
15 #include "mlir/Dialect/StandardOps/IR/Ops.h"
16 
17 #include "llvm/Support/CommandLine.h"
18 #include "llvm/Support/Debug.h"
19 
20 #define DEBUG_TYPE "linalg-dependence-analysis"
21 
22 using namespace mlir;
23 using namespace mlir::linalg;
24 
25 using llvm::dbgs;
26 
27 Value Aliases::find(Value v) {
28   if (v.isa<BlockArgument>())
29     return v;
30 
31   auto it = aliases.find(v);
32   if (it != aliases.end()) {
33     assert(it->getSecond().getType().isa<MemRefType>() && "Memref expected");
34     return it->getSecond();
35   }
36 
37   while (true) {
38     if (v.isa<BlockArgument>())
39       return v;
40     Operation *defOp = v.getDefiningOp();
41     if (auto alloc = dyn_cast_or_null<AllocOp>(defOp)) {
42       if (isStrided(alloc.getType()))
43         return alloc.getResult();
44     }
45     if (auto viewLikeOp = dyn_cast_or_null<ViewLikeOpInterface>(defOp)) {
46       auto it =
47           aliases.insert(std::make_pair(v, find(viewLikeOp.getViewSource())));
48       return it.first->second;
49     }
50 
51     llvm::errs() << "View alias analysis reduces to: " << v << "\n";
52     llvm_unreachable("unsupported view alias case");
53   }
54 }
55 
56 StringRef LinalgDependenceGraph::getDependenceTypeStr(DependenceType depType) {
57   switch (depType) {
58   case LinalgDependenceGraph::DependenceType::RAW:
59     return "RAW";
60   case LinalgDependenceGraph::DependenceType::RAR:
61     return "RAR";
62   case LinalgDependenceGraph::DependenceType::WAR:
63     return "WAR";
64   case LinalgDependenceGraph::DependenceType::WAW:
65     return "WAW";
66   default:
67     break;
68   }
69   llvm_unreachable("Unexpected DependenceType");
70 }
71 
72 LinalgDependenceGraph
73 LinalgDependenceGraph::buildDependenceGraph(Aliases &aliases, FuncOp f) {
74   SmallVector<Operation *, 8> linalgOps;
75   f.walk([&](LinalgOp op) { linalgOps.push_back(op); });
76   return LinalgDependenceGraph(aliases, linalgOps);
77 }
78 
79 LinalgDependenceGraph::LinalgDependenceGraph(Aliases &aliases,
80                                              ArrayRef<Operation *> ops)
81     : aliases(aliases), linalgOps(ops.begin(), ops.end()) {
82   for (auto en : llvm::enumerate(linalgOps)) {
83     assert(isa<LinalgOp>(en.value()) && "Expected value for LinalgOp");
84     linalgOpPositions.insert(std::make_pair(en.value(), en.index()));
85   }
86   for (unsigned i = 0, e = ops.size(); i < e; ++i) {
87     for (unsigned j = i + 1; j < e; ++j) {
88       addDependencesBetween(cast<LinalgOp>(ops[i]), cast<LinalgOp>(ops[j]));
89     }
90   }
91 }
92 
93 void LinalgDependenceGraph::addDependenceElem(DependenceType dt,
94                                               LinalgOpView indexingOpView,
95                                               LinalgOpView dependentOpView) {
96   LLVM_DEBUG(dbgs() << "\nAdd dep type " << getDependenceTypeStr(dt) << ":\t"
97                     << *indexingOpView.op << " -> " << *dependentOpView.op);
98   dependencesFromGraphs[dt][indexingOpView.op].push_back(
99       LinalgDependenceGraphElem{dependentOpView, indexingOpView.view});
100   dependencesIntoGraphs[dt][dependentOpView.op].push_back(
101       LinalgDependenceGraphElem{indexingOpView, dependentOpView.view});
102 }
103 
104 LinalgDependenceGraph::dependence_range
105 LinalgDependenceGraph::getDependencesFrom(
106     LinalgOp src, LinalgDependenceGraph::DependenceType dt) const {
107   return getDependencesFrom(src.getOperation(), dt);
108 }
109 
110 LinalgDependenceGraph::dependence_range
111 LinalgDependenceGraph::getDependencesFrom(
112     Operation *src, LinalgDependenceGraph::DependenceType dt) const {
113   auto iter = dependencesFromGraphs[dt].find(src);
114   if (iter == dependencesFromGraphs[dt].end())
115     return llvm::make_range(nullptr, nullptr);
116   return llvm::make_range(iter->second.begin(), iter->second.end());
117 }
118 
119 LinalgDependenceGraph::dependence_range
120 LinalgDependenceGraph::getDependencesInto(
121     LinalgOp dst, LinalgDependenceGraph::DependenceType dt) const {
122   return getDependencesInto(dst.getOperation(), dt);
123 }
124 
125 LinalgDependenceGraph::dependence_range
126 LinalgDependenceGraph::getDependencesInto(
127     Operation *dst, LinalgDependenceGraph::DependenceType dt) const {
128   auto iter = dependencesIntoGraphs[dt].find(dst);
129   if (iter == dependencesIntoGraphs[dt].end())
130     return llvm::make_range(nullptr, nullptr);
131   return llvm::make_range(iter->second.begin(), iter->second.end());
132 }
133 
134 void LinalgDependenceGraph::addDependencesBetween(LinalgOp src, LinalgOp dst) {
135   assert(src.hasBufferSemantics() &&
136          "expected linalg op with buffer semantics");
137   assert(dst.hasBufferSemantics() &&
138          "expected linalg op with buffer semantics");
139   for (auto srcView : src.getOutputBuffers()) { // W
140     // RAW graph
141     for (auto dstView : dst.getInputs()) {   // R
142       if (aliases.alias(srcView, dstView)) { // if alias, fill RAW
143         addDependenceElem(DependenceType::RAW,
144                           LinalgOpView{src.getOperation(), srcView},
145                           LinalgOpView{dst.getOperation(), dstView});
146       }
147     }
148     // WAW graph
149     for (auto dstView : dst.getOutputBuffers()) { // W
150       if (aliases.alias(srcView, dstView)) { // if alias, fill WAW
151         addDependenceElem(DependenceType::WAW,
152                           LinalgOpView{src.getOperation(), srcView},
153                           LinalgOpView{dst.getOperation(), dstView});
154       }
155     }
156   }
157   for (auto srcView : src.getInputs()) { // R
158     // RAR graph
159     for (auto dstView : dst.getInputs()) {   // R
160       if (aliases.alias(srcView, dstView)) { // if alias, fill RAR
161         addDependenceElem(DependenceType::RAR,
162                           LinalgOpView{src.getOperation(), srcView},
163                           LinalgOpView{dst.getOperation(), dstView});
164       }
165     }
166     // WAR graph
167     for (auto dstView : dst.getOutputBuffers()) { // W
168       if (aliases.alias(srcView, dstView)) { // if alias, fill WAR
169         addDependenceElem(DependenceType::WAR,
170                           LinalgOpView{src.getOperation(), srcView},
171                           LinalgOpView{dst.getOperation(), dstView});
172       }
173     }
174   }
175 }
176 
177 SmallVector<Operation *, 8>
178 LinalgDependenceGraph::findCoveringDependences(LinalgOp srcLinalgOp,
179                                                LinalgOp dstLinalgOp) const {
180   return findOperationsWithCoveringDependences(
181       srcLinalgOp, dstLinalgOp, nullptr,
182       {DependenceType::WAW, DependenceType::WAR, DependenceType::RAW});
183 }
184 
185 SmallVector<Operation *, 8> LinalgDependenceGraph::findCoveringWrites(
186     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view) const {
187   return findOperationsWithCoveringDependences(
188       srcLinalgOp, dstLinalgOp, view,
189       {DependenceType::WAW, DependenceType::WAR});
190 }
191 
192 SmallVector<Operation *, 8> LinalgDependenceGraph::findCoveringReads(
193     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view) const {
194   return findOperationsWithCoveringDependences(
195       srcLinalgOp, dstLinalgOp, view,
196       {DependenceType::RAR, DependenceType::RAW});
197 }
198 
199 SmallVector<Operation *, 8>
200 LinalgDependenceGraph::findOperationsWithCoveringDependences(
201     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view,
202     ArrayRef<DependenceType> types) const {
203   auto *src = srcLinalgOp.getOperation();
204   auto *dst = dstLinalgOp.getOperation();
205   auto srcPos = linalgOpPositions.lookup(src);
206   auto dstPos = linalgOpPositions.lookup(dst);
207   assert(srcPos < dstPos && "expected dst after src in IR traversal order");
208 
209   SmallVector<Operation *, 8> res;
210   // Consider an intermediate interleaved `interim` op, look for any dependence
211   // to an aliasing view on a src -> op -> dst path.
212   // TODO(ntv) we are not considering paths yet, just interleaved positions.
213   for (auto dt : types) {
214     for (auto dependence : getDependencesFrom(src, dt)) {
215       auto interimPos = linalgOpPositions.lookup(dependence.dependentOpView.op);
216       // Skip if not interleaved.
217       if (interimPos >= dstPos || interimPos <= srcPos)
218         continue;
219       if (view && !aliases.alias(view, dependence.indexingView))
220         continue;
221       auto *op = dependence.dependentOpView.op;
222       LLVM_DEBUG(dbgs() << "\n***Found covering dependence of type "
223                         << getDependenceTypeStr(dt) << ": " << *src << " -> "
224                         << *op << " on " << dependence.indexingView);
225       res.push_back(op);
226     }
227   }
228   return res;
229 }
230