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