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