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<BaseMemRefType>() &&
34            "Memref expected");
35     return it->getSecond();
36   }
37 
38   while (true) {
39     if (v.isa<BlockArgument>())
40       return v;
41 
42     Operation *defOp = v.getDefiningOp();
43     if (!defOp)
44       return v;
45 
46     if (auto memEffect = dyn_cast<MemoryEffectOpInterface>(defOp)) {
47       // Collect all memory effects on `v`.
48       SmallVector<MemoryEffects::EffectInstance, 1> effects;
49       memEffect.getEffectsOnValue(v, effects);
50 
51       // If we have the 'Allocate' memory effect on `v`, then `v` should be the
52       // original buffer.
53       if (llvm::any_of(
54               effects, [](const MemoryEffects::EffectInstance &instance) {
55                 return isa<MemoryEffects::Allocate>(instance.getEffect());
56               }))
57         return v;
58     }
59 
60     if (auto viewLikeOp = dyn_cast<ViewLikeOpInterface>(defOp)) {
61       auto it =
62           aliases.insert(std::make_pair(v, find(viewLikeOp.getViewSource())));
63       return it.first->second;
64     }
65 
66     llvm::errs() << "View alias analysis reduces to: " << v << "\n";
67     llvm_unreachable("unsupported view alias case");
68   }
69 }
70 
71 StringRef LinalgDependenceGraph::getDependenceTypeStr(DependenceType depType) {
72   switch (depType) {
73   case LinalgDependenceGraph::DependenceType::RAW:
74     return "RAW";
75   case LinalgDependenceGraph::DependenceType::RAR:
76     return "RAR";
77   case LinalgDependenceGraph::DependenceType::WAR:
78     return "WAR";
79   case LinalgDependenceGraph::DependenceType::WAW:
80     return "WAW";
81   default:
82     break;
83   }
84   llvm_unreachable("Unexpected DependenceType");
85 }
86 
87 LinalgDependenceGraph
88 LinalgDependenceGraph::buildDependenceGraph(Aliases &aliases, FuncOp f) {
89   SmallVector<Operation *, 8> linalgOps;
90   f.walk([&](LinalgOp op) { linalgOps.push_back(op); });
91   return LinalgDependenceGraph(aliases, linalgOps);
92 }
93 
94 LinalgDependenceGraph::LinalgDependenceGraph(Aliases &aliases,
95                                              ArrayRef<Operation *> ops)
96     : aliases(aliases), linalgOps(ops.begin(), ops.end()) {
97   for (auto en : llvm::enumerate(linalgOps)) {
98     assert(isa<LinalgOp>(en.value()) && "Expected value for LinalgOp");
99     linalgOpPositions.insert(std::make_pair(en.value(), en.index()));
100   }
101   for (unsigned i = 0, e = ops.size(); i < e; ++i) {
102     for (unsigned j = i + 1; j < e; ++j) {
103       addDependencesBetween(cast<LinalgOp>(ops[i]), cast<LinalgOp>(ops[j]));
104     }
105   }
106 }
107 
108 void LinalgDependenceGraph::addDependenceElem(DependenceType dt,
109                                               LinalgOpView indexingOpView,
110                                               LinalgOpView dependentOpView) {
111   LLVM_DEBUG(dbgs() << "\nAdd dep type " << getDependenceTypeStr(dt) << ":\t"
112                     << *indexingOpView.op << " -> " << *dependentOpView.op);
113   dependencesFromGraphs[dt][indexingOpView.op].push_back(
114       LinalgDependenceGraphElem{dependentOpView, indexingOpView.view});
115   dependencesIntoGraphs[dt][dependentOpView.op].push_back(
116       LinalgDependenceGraphElem{indexingOpView, dependentOpView.view});
117 }
118 
119 LinalgDependenceGraph::dependence_range
120 LinalgDependenceGraph::getDependencesFrom(
121     LinalgOp src, LinalgDependenceGraph::DependenceType dt) const {
122   return getDependencesFrom(src.getOperation(), dt);
123 }
124 
125 LinalgDependenceGraph::dependence_range
126 LinalgDependenceGraph::getDependencesFrom(
127     Operation *src, LinalgDependenceGraph::DependenceType dt) const {
128   auto iter = dependencesFromGraphs[dt].find(src);
129   if (iter == dependencesFromGraphs[dt].end())
130     return llvm::make_range(nullptr, nullptr);
131   return llvm::make_range(iter->second.begin(), iter->second.end());
132 }
133 
134 LinalgDependenceGraph::dependence_range
135 LinalgDependenceGraph::getDependencesInto(
136     LinalgOp dst, LinalgDependenceGraph::DependenceType dt) const {
137   return getDependencesInto(dst.getOperation(), dt);
138 }
139 
140 LinalgDependenceGraph::dependence_range
141 LinalgDependenceGraph::getDependencesInto(
142     Operation *dst, LinalgDependenceGraph::DependenceType dt) const {
143   auto iter = dependencesIntoGraphs[dt].find(dst);
144   if (iter == dependencesIntoGraphs[dt].end())
145     return llvm::make_range(nullptr, nullptr);
146   return llvm::make_range(iter->second.begin(), iter->second.end());
147 }
148 
149 void LinalgDependenceGraph::addDependencesBetween(LinalgOp src, LinalgOp dst) {
150   assert(src.hasBufferSemantics() &&
151          "expected linalg op with buffer semantics");
152   assert(dst.hasBufferSemantics() &&
153          "expected linalg op with buffer semantics");
154   for (auto srcView : src.getOutputBuffers()) { // W
155     // RAW graph
156     for (auto dstView : dst.getInputs()) {   // R
157       if (aliases.alias(srcView, dstView)) { // if alias, fill RAW
158         addDependenceElem(DependenceType::RAW,
159                           LinalgOpView{src.getOperation(), srcView},
160                           LinalgOpView{dst.getOperation(), dstView});
161       }
162     }
163     // WAW graph
164     for (auto dstView : dst.getOutputBuffers()) { // W
165       if (aliases.alias(srcView, dstView)) { // if alias, fill WAW
166         addDependenceElem(DependenceType::WAW,
167                           LinalgOpView{src.getOperation(), srcView},
168                           LinalgOpView{dst.getOperation(), dstView});
169       }
170     }
171   }
172   for (auto srcView : src.getInputs()) { // R
173     // RAR graph
174     for (auto dstView : dst.getInputs()) {   // R
175       if (aliases.alias(srcView, dstView)) { // if alias, fill RAR
176         addDependenceElem(DependenceType::RAR,
177                           LinalgOpView{src.getOperation(), srcView},
178                           LinalgOpView{dst.getOperation(), dstView});
179       }
180     }
181     // WAR graph
182     for (auto dstView : dst.getOutputBuffers()) { // W
183       if (aliases.alias(srcView, dstView)) { // if alias, fill WAR
184         addDependenceElem(DependenceType::WAR,
185                           LinalgOpView{src.getOperation(), srcView},
186                           LinalgOpView{dst.getOperation(), dstView});
187       }
188     }
189   }
190 }
191 
192 SmallVector<Operation *, 8>
193 LinalgDependenceGraph::findCoveringDependences(LinalgOp srcLinalgOp,
194                                                LinalgOp dstLinalgOp) const {
195   return findOperationsWithCoveringDependences(
196       srcLinalgOp, dstLinalgOp, nullptr,
197       {DependenceType::WAW, DependenceType::WAR, DependenceType::RAW});
198 }
199 
200 SmallVector<Operation *, 8> LinalgDependenceGraph::findCoveringWrites(
201     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view) const {
202   return findOperationsWithCoveringDependences(
203       srcLinalgOp, dstLinalgOp, view,
204       {DependenceType::WAW, DependenceType::WAR});
205 }
206 
207 SmallVector<Operation *, 8> LinalgDependenceGraph::findCoveringReads(
208     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view) const {
209   return findOperationsWithCoveringDependences(
210       srcLinalgOp, dstLinalgOp, view,
211       {DependenceType::RAR, DependenceType::RAW});
212 }
213 
214 SmallVector<Operation *, 8>
215 LinalgDependenceGraph::findOperationsWithCoveringDependences(
216     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view,
217     ArrayRef<DependenceType> types) const {
218   auto *src = srcLinalgOp.getOperation();
219   auto *dst = dstLinalgOp.getOperation();
220   auto srcPos = linalgOpPositions.lookup(src);
221   auto dstPos = linalgOpPositions.lookup(dst);
222   assert(srcPos < dstPos && "expected dst after src in IR traversal order");
223 
224   SmallVector<Operation *, 8> res;
225   // Consider an intermediate interleaved `interim` op, look for any dependence
226   // to an aliasing view on a src -> op -> dst path.
227   // TODO: we are not considering paths yet, just interleaved positions.
228   for (auto dt : types) {
229     for (auto dependence : getDependencesFrom(src, dt)) {
230       auto interimPos = linalgOpPositions.lookup(dependence.dependentOpView.op);
231       // Skip if not interleaved.
232       if (interimPos >= dstPos || interimPos <= srcPos)
233         continue;
234       if (view && !aliases.alias(view, dependence.indexingView))
235         continue;
236       auto *op = dependence.dependentOpView.op;
237       LLVM_DEBUG(dbgs() << "\n***Found covering dependence of type "
238                         << getDependenceTypeStr(dt) << ": " << *src << " -> "
239                         << *op << " on " << dependence.indexingView);
240       res.push_back(op);
241     }
242   }
243   return res;
244 }
245