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 #include "mlir/IR/BuiltinOps.h"
17 
18 #include "llvm/Support/CommandLine.h"
19 #include "llvm/Support/Debug.h"
20 
21 #define DEBUG_TYPE "linalg-dependence-analysis"
22 
23 using namespace mlir;
24 using namespace mlir::linalg;
25 
26 using llvm::dbgs;
27 
28 Value Aliases::find(Value v) {
29   if (v.isa<BlockArgument>())
30     return v;
31 
32   auto it = aliases.find(v);
33   if (it != aliases.end()) {
34     assert(it->getSecond().getType().isa<BaseMemRefType>() &&
35            "Memref expected");
36     return it->getSecond();
37   }
38 
39   while (true) {
40     if (v.isa<BlockArgument>())
41       return v;
42 
43     Operation *defOp = v.getDefiningOp();
44     if (!defOp)
45       return v;
46 
47     // Treat RegionBranchOpInterfaces like an allocate and don't try to follow
48     // the aliasing further.
49     if (isa<RegionBranchOpInterface>(defOp))
50       return v;
51     if (isa<TensorToMemrefOp>(defOp))
52       return v;
53 
54     if (auto memEffect = dyn_cast<MemoryEffectOpInterface>(defOp)) {
55       // Collect all memory effects on `v`.
56       SmallVector<MemoryEffects::EffectInstance, 1> effects;
57       memEffect.getEffectsOnValue(v, effects);
58 
59       // If we have the 'Allocate' memory effect on `v`, then `v` should be the
60       // original buffer.
61       if (llvm::any_of(
62               effects, [](const MemoryEffects::EffectInstance &instance) {
63                 return isa<MemoryEffects::Allocate>(instance.getEffect());
64               }))
65         return v;
66     }
67 
68     if (auto viewLikeOp = dyn_cast<ViewLikeOpInterface>(defOp)) {
69       auto it =
70           aliases.insert(std::make_pair(v, find(viewLikeOp.getViewSource())));
71       return it.first->second;
72     }
73 
74     llvm::errs() << "View alias analysis reduces to: " << v << "\n";
75     llvm_unreachable("unsupported view alias case");
76   }
77 }
78 
79 StringRef LinalgDependenceGraph::getDependenceTypeStr(DependenceType depType) {
80   switch (depType) {
81   case LinalgDependenceGraph::DependenceType::RAW:
82     return "RAW";
83   case LinalgDependenceGraph::DependenceType::RAR:
84     return "RAR";
85   case LinalgDependenceGraph::DependenceType::WAR:
86     return "WAR";
87   case LinalgDependenceGraph::DependenceType::WAW:
88     return "WAW";
89   default:
90     break;
91   }
92   llvm_unreachable("Unexpected DependenceType");
93 }
94 
95 LinalgDependenceGraph
96 LinalgDependenceGraph::buildDependenceGraph(Aliases &aliases, FuncOp f) {
97   SmallVector<LinalgOp, 8> linalgOps;
98   f.walk([&](LinalgOp op) { linalgOps.push_back(op); });
99   return LinalgDependenceGraph(aliases, linalgOps);
100 }
101 
102 LinalgDependenceGraph::LinalgDependenceGraph(Aliases &aliases,
103                                              ArrayRef<LinalgOp> ops)
104     : aliases(aliases), linalgOps(ops.begin(), ops.end()) {
105   for (auto en : llvm::enumerate(linalgOps)) {
106     linalgOpPositions.insert(
107         std::make_pair(en.value().getOperation(), en.index()));
108   }
109   for (unsigned i = 0, e = ops.size(); i < e; ++i) {
110     for (unsigned j = i + 1; j < e; ++j) {
111       addDependencesBetween(ops[i], ops[j]);
112     }
113   }
114 }
115 
116 void LinalgDependenceGraph::addDependenceElem(DependenceType dt,
117                                               OpOperand *indexingOpView,
118                                               OpOperand *dependentOpView) {
119   LLVM_DEBUG(dbgs() << "\nAdd dep type " << getDependenceTypeStr(dt) << ":\t ("
120                     << indexingOpView->get() << " @"
121                     << indexingOpView->getOperandNumber() << ") -> \n\t\t("
122                     << dependentOpView->get() << " @"
123                     << dependentOpView->getOperandNumber() << ")");
124   dependencesFromGraphs[dt][indexingOpView->getOwner()].push_back(
125       LinalgDependenceGraphElem{dependentOpView, indexingOpView, dt});
126   dependencesIntoGraphs[dt][dependentOpView->getOwner()].push_back(
127       LinalgDependenceGraphElem{indexingOpView, dependentOpView, dt});
128 }
129 
130 LinalgDependenceGraph::dependence_range
131 LinalgDependenceGraph::getDependencesFrom(
132     LinalgOp src, LinalgDependenceGraph::DependenceType dt) const {
133   return getDependencesFrom(src.getOperation(), dt);
134 }
135 
136 LinalgDependenceGraph::dependence_range
137 LinalgDependenceGraph::getDependencesFrom(
138     Operation *src, LinalgDependenceGraph::DependenceType dt) const {
139   auto iter = dependencesFromGraphs[dt].find(src);
140   if (iter == dependencesFromGraphs[dt].end())
141     return llvm::make_range(nullptr, nullptr);
142   return llvm::make_range(iter->second.begin(), iter->second.end());
143 }
144 
145 LinalgDependenceGraph::dependence_range
146 LinalgDependenceGraph::getDependencesInto(
147     LinalgOp dst, LinalgDependenceGraph::DependenceType dt) const {
148   return getDependencesInto(dst.getOperation(), dt);
149 }
150 
151 LinalgDependenceGraph::dependence_range
152 LinalgDependenceGraph::getDependencesInto(
153     Operation *dst, LinalgDependenceGraph::DependenceType dt) const {
154   auto iter = dependencesIntoGraphs[dt].find(dst);
155   if (iter == dependencesIntoGraphs[dt].end())
156     return llvm::make_range(nullptr, nullptr);
157   return llvm::make_range(iter->second.begin(), iter->second.end());
158 }
159 
160 void LinalgDependenceGraph::addDependencesBetween(LinalgOp src, LinalgOp dst) {
161   for (OpOperand *srcOpOperand : src.getOutputBuffersOpOperands()) { // W
162     // RAW graph
163     for (OpOperand *dstOpOperand : dst.getInputBuffersOpOperands()) // R
164       if (aliases.alias(srcOpOperand->get(), dstOpOperand->get()))  // RAW alias
165         addDependenceElem(DependenceType::RAW, srcOpOperand, dstOpOperand);
166     // WAW graph
167     for (OpOperand *dstOpOperand : dst.getOutputBuffersOpOperands()) // W
168       if (aliases.alias(srcOpOperand->get(), dstOpOperand->get())) // WAW alias
169         addDependenceElem(DependenceType::WAW, srcOpOperand, dstOpOperand);
170   }
171   for (OpOperand *srcOpOperand : src.getInputBuffersOpOperands()) { // R
172     // RAR graph
173     for (OpOperand *dstOpOperand : dst.getInputBuffersOpOperands()) // R
174       if (aliases.alias(srcOpOperand->get(), dstOpOperand->get()))  // RAR alias
175         addDependenceElem(DependenceType::RAR, srcOpOperand, dstOpOperand);
176     // WAR graph
177     for (OpOperand *dstOpOperand : dst.getOutputBuffersOpOperands()) // W
178       if (aliases.alias(srcOpOperand->get(), dstOpOperand->get())) // WAR alias
179         addDependenceElem(DependenceType::WAR, srcOpOperand, dstOpOperand);
180   }
181 }
182 
183 SmallVector<Operation *, 8>
184 LinalgDependenceGraph::findCoveringDependences(LinalgOp srcLinalgOp,
185                                                LinalgOp dstLinalgOp) const {
186   return findOperationsWithCoveringDependences(
187       srcLinalgOp, dstLinalgOp, nullptr,
188       {DependenceType::WAW, DependenceType::WAR, DependenceType::RAW});
189 }
190 
191 SmallVector<Operation *, 8> LinalgDependenceGraph::findCoveringWrites(
192     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view) const {
193   return findOperationsWithCoveringDependences(
194       srcLinalgOp, dstLinalgOp, view,
195       {DependenceType::WAW, DependenceType::WAR});
196 }
197 
198 SmallVector<Operation *, 8> LinalgDependenceGraph::findCoveringReads(
199     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view) const {
200   return findOperationsWithCoveringDependences(
201       srcLinalgOp, dstLinalgOp, view,
202       {DependenceType::RAR, DependenceType::RAW});
203 }
204 
205 SmallVector<Operation *, 8>
206 LinalgDependenceGraph::findOperationsWithCoveringDependences(
207     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, Value view,
208     ArrayRef<DependenceType> types) const {
209   auto *src = srcLinalgOp.getOperation();
210   auto *dst = dstLinalgOp.getOperation();
211   auto srcPos = linalgOpPositions.lookup(src);
212   auto dstPos = linalgOpPositions.lookup(dst);
213   assert(srcPos < dstPos && "expected dst after src in IR traversal order");
214 
215   SmallVector<Operation *, 8> res;
216   // Consider an intermediate interleaved `interim` op, look for any dependence
217   // to an aliasing view on a src -> op -> dst path.
218   // TODO: we are not considering paths yet, just interleaved positions.
219   for (auto dt : types) {
220     for (auto dependence : getDependencesFrom(src, dt)) {
221       auto interimPos =
222           linalgOpPositions.lookup(dependence.dependentOpView->getOwner());
223       // Skip if not interleaved.
224       if (interimPos >= dstPos || interimPos <= srcPos)
225         continue;
226       Value consumerView = dependence.indexingOpView->get();
227       if (view && !aliases.alias(view, consumerView))
228         continue;
229       auto *op = dependence.dependentOpView->getOwner();
230       LLVM_DEBUG(dbgs() << "\n***Found covering dependence of type "
231                         << getDependenceTypeStr(dt) << ": " << *src << " -> "
232                         << *op << " on " << consumerView);
233       res.push_back(op);
234     }
235   }
236   return res;
237 }
238 
239 bool LinalgDependenceGraph::hasDependenceFrom(
240     LinalgOp srcLinalgOp, LinalgOp dstLinalgOp,
241     ArrayRef<LinalgDependenceGraph::DependenceType> depTypes) const {
242   for (auto dep : depTypes)
243     for (auto dependence : getDependencesInto(dstLinalgOp, dep))
244       if (dependence.dependentOpView->getOwner() == srcLinalgOp)
245         return true;
246   return false;
247 }
248 
249 bool LinalgDependenceGraph::hasDependentOperationsFrom(
250     LinalgOp linalgOp,
251     ArrayRef<LinalgDependenceGraph::DependenceType> depTypes) const {
252   for (auto dep : depTypes) {
253     if (!getDependencesFrom(linalgOp, dep).empty())
254       return true;
255   }
256   return false;
257 }
258 
259 bool LinalgDependenceGraph::hasDependentOperationsInto(
260     LinalgOp linalgOp,
261     ArrayRef<LinalgDependenceGraph::DependenceType> depTypes) const {
262   for (auto dep : depTypes) {
263     if (!getDependencesInto(linalgOp, dep).empty())
264       return true;
265   }
266   return false;
267 }
268 
269 bool LinalgDependenceGraph::hasDependentOperations(
270     LinalgOp linalgOp, ArrayRef<DependenceType> depTypes) const {
271   return hasDependentOperationsInto(linalgOp, depTypes) ||
272          hasDependentOperationsFrom(linalgOp, depTypes);
273 }
274 
275 SmallVector<LinalgDependenceGraph::LinalgDependenceGraphElem, 2>
276 LinalgDependenceGraph::getDependentOperationsInto(
277     LinalgOp linalgOp, ArrayRef<DependenceType> depTypes) const {
278   SmallVector<LinalgDependenceGraph::LinalgDependenceGraphElem, 2>
279       dependentOperations;
280   for (auto dependenceType : depTypes) {
281     auto dependencies = getDependencesInto(linalgOp, dependenceType);
282     dependentOperations.append(dependencies.begin(), dependencies.end());
283   }
284   return dependentOperations;
285 }
286 
287 SmallVector<LinalgDependenceGraph::LinalgDependenceGraphElem, 2>
288 LinalgDependenceGraph::getDependentOperationsFrom(
289     LinalgOp linalgOp, ArrayRef<DependenceType> depTypes) const {
290   SmallVector<LinalgDependenceGraph::LinalgDependenceGraphElem, 2>
291       dependentOperations;
292   for (auto dependenceType : depTypes) {
293     auto dependencies = getDependencesFrom(linalgOp, dependenceType);
294     dependentOperations.append(dependencies.begin(), dependencies.end());
295   }
296   return dependentOperations;
297 }
298 
299 /// Returns all dependent operations (into and from) given `operation`.
300 SmallVector<LinalgDependenceGraph::LinalgDependenceGraphElem, 2>
301 LinalgDependenceGraph::getDependentOperations(
302     LinalgOp linalgOp, ArrayRef<DependenceType> depTypes) const {
303   SmallVector<LinalgDependenceGraphElem, 2> dependentOperations =
304       getDependentOperationsInto(linalgOp, depTypes);
305   SmallVector<LinalgDependenceGraphElem, 2> t =
306       getDependentOperationsFrom(linalgOp, depTypes);
307   dependentOperations.append(t.begin(), t.end());
308   return dependentOperations;
309 }
310