|
150
|
1 //===- AffineAnalysis.cpp - Affine structures analysis routines -----------===//
|
|
|
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 miscellaneous analysis routines for affine structures
|
|
|
10 // (expressions, maps, sets), and other utilities relying on such analysis.
|
|
|
11 //
|
|
|
12 //===----------------------------------------------------------------------===//
|
|
|
13
|
|
|
14 #include "mlir/Analysis/AffineAnalysis.h"
|
|
|
15 #include "mlir/Analysis/Utils.h"
|
|
173
|
16 #include "mlir/Dialect/Affine/IR/AffineOps.h"
|
|
|
17 #include "mlir/Dialect/Affine/IR/AffineValueMap.h"
|
|
|
18 #include "mlir/Dialect/StandardOps/IR/Ops.h"
|
|
150
|
19 #include "mlir/IR/AffineExprVisitor.h"
|
|
|
20 #include "mlir/IR/Function.h"
|
|
|
21 #include "mlir/IR/IntegerSet.h"
|
|
|
22 #include "mlir/Support/MathExtras.h"
|
|
|
23 #include "llvm/ADT/DenseMap.h"
|
|
|
24 #include "llvm/Support/Debug.h"
|
|
|
25 #include "llvm/Support/raw_ostream.h"
|
|
|
26
|
|
|
27 #define DEBUG_TYPE "affine-analysis"
|
|
|
28
|
|
|
29 using namespace mlir;
|
|
|
30
|
|
|
31 using llvm::dbgs;
|
|
|
32
|
|
|
33 /// Returns the sequence of AffineApplyOp Operations operation in
|
|
|
34 /// 'affineApplyOps', which are reachable via a search starting from 'operands',
|
|
|
35 /// and ending at operands which are not defined by AffineApplyOps.
|
|
|
36 // TODO(andydavis) Add a method to AffineApplyOp which forward substitutes
|
|
|
37 // the AffineApplyOp into any user AffineApplyOps.
|
|
|
38 void mlir::getReachableAffineApplyOps(
|
|
|
39 ArrayRef<Value> operands, SmallVectorImpl<Operation *> &affineApplyOps) {
|
|
|
40 struct State {
|
|
|
41 // The ssa value for this node in the DFS traversal.
|
|
|
42 Value value;
|
|
|
43 // The operand index of 'value' to explore next during DFS traversal.
|
|
|
44 unsigned operandIndex;
|
|
|
45 };
|
|
|
46 SmallVector<State, 4> worklist;
|
|
|
47 for (auto operand : operands) {
|
|
|
48 worklist.push_back({operand, 0});
|
|
|
49 }
|
|
|
50
|
|
|
51 while (!worklist.empty()) {
|
|
|
52 State &state = worklist.back();
|
|
|
53 auto *opInst = state.value.getDefiningOp();
|
|
|
54 // Note: getDefiningOp will return nullptr if the operand is not an
|
|
|
55 // Operation (i.e. block argument), which is a terminator for the search.
|
|
|
56 if (!isa_and_nonnull<AffineApplyOp>(opInst)) {
|
|
|
57 worklist.pop_back();
|
|
|
58 continue;
|
|
|
59 }
|
|
|
60
|
|
|
61 if (state.operandIndex == 0) {
|
|
|
62 // Pre-Visit: Add 'opInst' to reachable sequence.
|
|
|
63 affineApplyOps.push_back(opInst);
|
|
|
64 }
|
|
|
65 if (state.operandIndex < opInst->getNumOperands()) {
|
|
|
66 // Visit: Add next 'affineApplyOp' operand to worklist.
|
|
|
67 // Get next operand to visit at 'operandIndex'.
|
|
|
68 auto nextOperand = opInst->getOperand(state.operandIndex);
|
|
|
69 // Increment 'operandIndex' in 'state'.
|
|
|
70 ++state.operandIndex;
|
|
|
71 // Add 'nextOperand' to worklist.
|
|
|
72 worklist.push_back({nextOperand, 0});
|
|
|
73 } else {
|
|
|
74 // Post-visit: done visiting operands AffineApplyOp, pop off stack.
|
|
|
75 worklist.pop_back();
|
|
|
76 }
|
|
|
77 }
|
|
|
78 }
|
|
|
79
|
|
|
80 // Builds a system of constraints with dimensional identifiers corresponding to
|
|
|
81 // the loop IVs of the forOps appearing in that order. Any symbols founds in
|
|
|
82 // the bound operands are added as symbols in the system. Returns failure for
|
|
|
83 // the yet unimplemented cases.
|
|
|
84 // TODO(andydavis,bondhugula) Handle non-unit steps through local variables or
|
|
|
85 // stride information in FlatAffineConstraints. (For eg., by using iv - lb %
|
|
|
86 // step = 0 and/or by introducing a method in FlatAffineConstraints
|
|
|
87 // setExprStride(ArrayRef<int64_t> expr, int64_t stride)
|
|
|
88 LogicalResult mlir::getIndexSet(MutableArrayRef<AffineForOp> forOps,
|
|
|
89 FlatAffineConstraints *domain) {
|
|
|
90 SmallVector<Value, 4> indices;
|
|
|
91 extractForInductionVars(forOps, &indices);
|
|
|
92 // Reset while associated Values in 'indices' to the domain.
|
|
|
93 domain->reset(forOps.size(), /*numSymbols=*/0, /*numLocals=*/0, indices);
|
|
|
94 for (auto forOp : forOps) {
|
|
|
95 // Add constraints from forOp's bounds.
|
|
|
96 if (failed(domain->addAffineForOpDomain(forOp)))
|
|
|
97 return failure();
|
|
|
98 }
|
|
|
99 return success();
|
|
|
100 }
|
|
|
101
|
|
|
102 // Computes the iteration domain for 'opInst' and populates 'indexSet', which
|
|
|
103 // encapsulates the constraints involving loops surrounding 'opInst' and
|
|
|
104 // potentially involving any Function symbols. The dimensional identifiers in
|
|
|
105 // 'indexSet' correspond to the loops surrounding 'op' from outermost to
|
|
|
106 // innermost.
|
|
|
107 // TODO(andydavis) Add support to handle IfInsts surrounding 'op'.
|
|
|
108 static LogicalResult getInstIndexSet(Operation *op,
|
|
|
109 FlatAffineConstraints *indexSet) {
|
|
|
110 // TODO(andydavis) Extend this to gather enclosing IfInsts and consider
|
|
|
111 // factoring it out into a utility function.
|
|
|
112 SmallVector<AffineForOp, 4> loops;
|
|
|
113 getLoopIVs(*op, &loops);
|
|
|
114 return getIndexSet(loops, indexSet);
|
|
|
115 }
|
|
|
116
|
|
|
117 namespace {
|
|
|
118 // ValuePositionMap manages the mapping from Values which represent dimension
|
|
|
119 // and symbol identifiers from 'src' and 'dst' access functions to positions
|
|
|
120 // in new space where some Values are kept separate (using addSrc/DstValue)
|
|
|
121 // and some Values are merged (addSymbolValue).
|
|
|
122 // Position lookups return the absolute position in the new space which
|
|
|
123 // has the following format:
|
|
|
124 //
|
|
|
125 // [src-dim-identifiers] [dst-dim-identifiers] [symbol-identifiers]
|
|
|
126 //
|
|
|
127 // Note: access function non-IV dimension identifiers (that have 'dimension'
|
|
|
128 // positions in the access function position space) are assigned as symbols
|
|
|
129 // in the output position space. Convenience access functions which lookup
|
|
|
130 // an Value in multiple maps are provided (i.e. getSrcDimOrSymPos) to handle
|
|
|
131 // the common case of resolving positions for all access function operands.
|
|
|
132 //
|
|
|
133 // TODO(andydavis) Generalize this: could take a template parameter for
|
|
|
134 // the number of maps (3 in the current case), and lookups could take indices
|
|
|
135 // of maps to check. So getSrcDimOrSymPos would be "getPos(value, {0, 2})".
|
|
|
136 class ValuePositionMap {
|
|
|
137 public:
|
|
|
138 void addSrcValue(Value value) {
|
|
|
139 if (addValueAt(value, &srcDimPosMap, numSrcDims))
|
|
|
140 ++numSrcDims;
|
|
|
141 }
|
|
|
142 void addDstValue(Value value) {
|
|
|
143 if (addValueAt(value, &dstDimPosMap, numDstDims))
|
|
|
144 ++numDstDims;
|
|
|
145 }
|
|
|
146 void addSymbolValue(Value value) {
|
|
|
147 if (addValueAt(value, &symbolPosMap, numSymbols))
|
|
|
148 ++numSymbols;
|
|
|
149 }
|
|
|
150 unsigned getSrcDimOrSymPos(Value value) const {
|
|
|
151 return getDimOrSymPos(value, srcDimPosMap, 0);
|
|
|
152 }
|
|
|
153 unsigned getDstDimOrSymPos(Value value) const {
|
|
|
154 return getDimOrSymPos(value, dstDimPosMap, numSrcDims);
|
|
|
155 }
|
|
|
156 unsigned getSymPos(Value value) const {
|
|
|
157 auto it = symbolPosMap.find(value);
|
|
|
158 assert(it != symbolPosMap.end());
|
|
|
159 return numSrcDims + numDstDims + it->second;
|
|
|
160 }
|
|
|
161
|
|
|
162 unsigned getNumSrcDims() const { return numSrcDims; }
|
|
|
163 unsigned getNumDstDims() const { return numDstDims; }
|
|
|
164 unsigned getNumDims() const { return numSrcDims + numDstDims; }
|
|
|
165 unsigned getNumSymbols() const { return numSymbols; }
|
|
|
166
|
|
|
167 private:
|
|
|
168 bool addValueAt(Value value, DenseMap<Value, unsigned> *posMap,
|
|
|
169 unsigned position) {
|
|
|
170 auto it = posMap->find(value);
|
|
|
171 if (it == posMap->end()) {
|
|
|
172 (*posMap)[value] = position;
|
|
|
173 return true;
|
|
|
174 }
|
|
|
175 return false;
|
|
|
176 }
|
|
|
177 unsigned getDimOrSymPos(Value value,
|
|
|
178 const DenseMap<Value, unsigned> &dimPosMap,
|
|
|
179 unsigned dimPosOffset) const {
|
|
|
180 auto it = dimPosMap.find(value);
|
|
|
181 if (it != dimPosMap.end()) {
|
|
|
182 return dimPosOffset + it->second;
|
|
|
183 }
|
|
|
184 it = symbolPosMap.find(value);
|
|
|
185 assert(it != symbolPosMap.end());
|
|
|
186 return numSrcDims + numDstDims + it->second;
|
|
|
187 }
|
|
|
188
|
|
|
189 unsigned numSrcDims = 0;
|
|
|
190 unsigned numDstDims = 0;
|
|
|
191 unsigned numSymbols = 0;
|
|
|
192 DenseMap<Value, unsigned> srcDimPosMap;
|
|
|
193 DenseMap<Value, unsigned> dstDimPosMap;
|
|
|
194 DenseMap<Value, unsigned> symbolPosMap;
|
|
|
195 };
|
|
|
196 } // namespace
|
|
|
197
|
|
|
198 // Builds a map from Value to identifier position in a new merged identifier
|
|
|
199 // list, which is the result of merging dim/symbol lists from src/dst
|
|
|
200 // iteration domains, the format of which is as follows:
|
|
|
201 //
|
|
|
202 // [src-dim-identifiers, dst-dim-identifiers, symbol-identifiers, const_term]
|
|
|
203 //
|
|
|
204 // This method populates 'valuePosMap' with mappings from operand Values in
|
|
|
205 // 'srcAccessMap'/'dstAccessMap' (as well as those in 'srcDomain'/'dstDomain')
|
|
|
206 // to the position of these values in the merged list.
|
|
|
207 static void buildDimAndSymbolPositionMaps(
|
|
|
208 const FlatAffineConstraints &srcDomain,
|
|
|
209 const FlatAffineConstraints &dstDomain, const AffineValueMap &srcAccessMap,
|
|
|
210 const AffineValueMap &dstAccessMap, ValuePositionMap *valuePosMap,
|
|
|
211 FlatAffineConstraints *dependenceConstraints) {
|
|
|
212 auto updateValuePosMap = [&](ArrayRef<Value> values, bool isSrc) {
|
|
|
213 for (unsigned i = 0, e = values.size(); i < e; ++i) {
|
|
|
214 auto value = values[i];
|
|
|
215 if (!isForInductionVar(values[i])) {
|
|
|
216 assert(isValidSymbol(values[i]) &&
|
|
|
217 "access operand has to be either a loop IV or a symbol");
|
|
|
218 valuePosMap->addSymbolValue(value);
|
|
|
219 } else if (isSrc) {
|
|
|
220 valuePosMap->addSrcValue(value);
|
|
|
221 } else {
|
|
|
222 valuePosMap->addDstValue(value);
|
|
|
223 }
|
|
|
224 }
|
|
|
225 };
|
|
|
226
|
|
|
227 SmallVector<Value, 4> srcValues, destValues;
|
|
|
228 srcDomain.getIdValues(0, srcDomain.getNumDimAndSymbolIds(), &srcValues);
|
|
|
229 dstDomain.getIdValues(0, dstDomain.getNumDimAndSymbolIds(), &destValues);
|
|
|
230 // Update value position map with identifiers from src iteration domain.
|
|
|
231 updateValuePosMap(srcValues, /*isSrc=*/true);
|
|
|
232 // Update value position map with identifiers from dst iteration domain.
|
|
|
233 updateValuePosMap(destValues, /*isSrc=*/false);
|
|
|
234 // Update value position map with identifiers from src access function.
|
|
|
235 updateValuePosMap(srcAccessMap.getOperands(), /*isSrc=*/true);
|
|
|
236 // Update value position map with identifiers from dst access function.
|
|
|
237 updateValuePosMap(dstAccessMap.getOperands(), /*isSrc=*/false);
|
|
|
238 }
|
|
|
239
|
|
|
240 // Sets up dependence constraints columns appropriately, in the format:
|
|
|
241 // [src-dim-ids, dst-dim-ids, symbol-ids, local-ids, const_term]
|
|
|
242 static void initDependenceConstraints(
|
|
|
243 const FlatAffineConstraints &srcDomain,
|
|
|
244 const FlatAffineConstraints &dstDomain, const AffineValueMap &srcAccessMap,
|
|
|
245 const AffineValueMap &dstAccessMap, const ValuePositionMap &valuePosMap,
|
|
|
246 FlatAffineConstraints *dependenceConstraints) {
|
|
|
247 // Calculate number of equalities/inequalities and columns required to
|
|
|
248 // initialize FlatAffineConstraints for 'dependenceDomain'.
|
|
|
249 unsigned numIneq =
|
|
|
250 srcDomain.getNumInequalities() + dstDomain.getNumInequalities();
|
|
|
251 AffineMap srcMap = srcAccessMap.getAffineMap();
|
|
|
252 assert(srcMap.getNumResults() == dstAccessMap.getAffineMap().getNumResults());
|
|
|
253 unsigned numEq = srcMap.getNumResults();
|
|
|
254 unsigned numDims = srcDomain.getNumDimIds() + dstDomain.getNumDimIds();
|
|
|
255 unsigned numSymbols = valuePosMap.getNumSymbols();
|
|
|
256 unsigned numLocals = srcDomain.getNumLocalIds() + dstDomain.getNumLocalIds();
|
|
|
257 unsigned numIds = numDims + numSymbols + numLocals;
|
|
|
258 unsigned numCols = numIds + 1;
|
|
|
259
|
|
|
260 // Set flat affine constraints sizes and reserving space for constraints.
|
|
|
261 dependenceConstraints->reset(numIneq, numEq, numCols, numDims, numSymbols,
|
|
|
262 numLocals);
|
|
|
263
|
|
|
264 // Set values corresponding to dependence constraint identifiers.
|
|
|
265 SmallVector<Value, 4> srcLoopIVs, dstLoopIVs;
|
|
|
266 srcDomain.getIdValues(0, srcDomain.getNumDimIds(), &srcLoopIVs);
|
|
|
267 dstDomain.getIdValues(0, dstDomain.getNumDimIds(), &dstLoopIVs);
|
|
|
268
|
|
|
269 dependenceConstraints->setIdValues(0, srcLoopIVs.size(), srcLoopIVs);
|
|
|
270 dependenceConstraints->setIdValues(
|
|
|
271 srcLoopIVs.size(), srcLoopIVs.size() + dstLoopIVs.size(), dstLoopIVs);
|
|
|
272
|
|
|
273 // Set values for the symbolic identifier dimensions.
|
|
|
274 auto setSymbolIds = [&](ArrayRef<Value> values) {
|
|
|
275 for (auto value : values) {
|
|
|
276 if (!isForInductionVar(value)) {
|
|
|
277 assert(isValidSymbol(value) && "expected symbol");
|
|
|
278 dependenceConstraints->setIdValue(valuePosMap.getSymPos(value), value);
|
|
|
279 }
|
|
|
280 }
|
|
|
281 };
|
|
|
282
|
|
|
283 setSymbolIds(srcAccessMap.getOperands());
|
|
|
284 setSymbolIds(dstAccessMap.getOperands());
|
|
|
285
|
|
|
286 SmallVector<Value, 8> srcSymbolValues, dstSymbolValues;
|
|
|
287 srcDomain.getIdValues(srcDomain.getNumDimIds(),
|
|
|
288 srcDomain.getNumDimAndSymbolIds(), &srcSymbolValues);
|
|
|
289 dstDomain.getIdValues(dstDomain.getNumDimIds(),
|
|
|
290 dstDomain.getNumDimAndSymbolIds(), &dstSymbolValues);
|
|
|
291 setSymbolIds(srcSymbolValues);
|
|
|
292 setSymbolIds(dstSymbolValues);
|
|
|
293
|
|
|
294 for (unsigned i = 0, e = dependenceConstraints->getNumDimAndSymbolIds();
|
|
|
295 i < e; i++)
|
|
|
296 assert(dependenceConstraints->getIds()[i].hasValue());
|
|
|
297 }
|
|
|
298
|
|
|
299 // Adds iteration domain constraints from 'srcDomain' and 'dstDomain' into
|
|
|
300 // 'dependenceDomain'.
|
|
|
301 // Uses 'valuePosMap' to determine the position in 'dependenceDomain' to which a
|
|
|
302 // srcDomain/dstDomain Value maps.
|
|
|
303 static void addDomainConstraints(const FlatAffineConstraints &srcDomain,
|
|
|
304 const FlatAffineConstraints &dstDomain,
|
|
|
305 const ValuePositionMap &valuePosMap,
|
|
|
306 FlatAffineConstraints *dependenceDomain) {
|
|
|
307 unsigned depNumDimsAndSymbolIds = dependenceDomain->getNumDimAndSymbolIds();
|
|
|
308
|
|
|
309 SmallVector<int64_t, 4> cst(dependenceDomain->getNumCols());
|
|
|
310
|
|
|
311 auto addDomain = [&](bool isSrc, bool isEq, unsigned localOffset) {
|
|
|
312 const FlatAffineConstraints &domain = isSrc ? srcDomain : dstDomain;
|
|
|
313 unsigned numCsts =
|
|
|
314 isEq ? domain.getNumEqualities() : domain.getNumInequalities();
|
|
|
315 unsigned numDimAndSymbolIds = domain.getNumDimAndSymbolIds();
|
|
|
316 auto at = [&](unsigned i, unsigned j) -> int64_t {
|
|
|
317 return isEq ? domain.atEq(i, j) : domain.atIneq(i, j);
|
|
|
318 };
|
|
|
319 auto map = [&](unsigned i) -> int64_t {
|
|
|
320 return isSrc ? valuePosMap.getSrcDimOrSymPos(domain.getIdValue(i))
|
|
|
321 : valuePosMap.getDstDimOrSymPos(domain.getIdValue(i));
|
|
|
322 };
|
|
|
323
|
|
|
324 for (unsigned i = 0; i < numCsts; ++i) {
|
|
|
325 // Zero fill.
|
|
|
326 std::fill(cst.begin(), cst.end(), 0);
|
|
|
327 // Set coefficients for identifiers corresponding to domain.
|
|
|
328 for (unsigned j = 0; j < numDimAndSymbolIds; ++j)
|
|
|
329 cst[map(j)] = at(i, j);
|
|
|
330 // Local terms.
|
|
|
331 for (unsigned j = 0, e = domain.getNumLocalIds(); j < e; j++)
|
|
|
332 cst[depNumDimsAndSymbolIds + localOffset + j] =
|
|
|
333 at(i, numDimAndSymbolIds + j);
|
|
|
334 // Set constant term.
|
|
|
335 cst[cst.size() - 1] = at(i, domain.getNumCols() - 1);
|
|
|
336 // Add constraint.
|
|
|
337 if (isEq)
|
|
|
338 dependenceDomain->addEquality(cst);
|
|
|
339 else
|
|
|
340 dependenceDomain->addInequality(cst);
|
|
|
341 }
|
|
|
342 };
|
|
|
343
|
|
|
344 // Add equalities from src domain.
|
|
|
345 addDomain(/*isSrc=*/true, /*isEq=*/true, /*localOffset=*/0);
|
|
|
346 // Add inequalities from src domain.
|
|
|
347 addDomain(/*isSrc=*/true, /*isEq=*/false, /*localOffset=*/0);
|
|
|
348 // Add equalities from dst domain.
|
|
|
349 addDomain(/*isSrc=*/false, /*isEq=*/true,
|
|
|
350 /*localOffset=*/srcDomain.getNumLocalIds());
|
|
|
351 // Add inequalities from dst domain.
|
|
|
352 addDomain(/*isSrc=*/false, /*isEq=*/false,
|
|
|
353 /*localOffset=*/srcDomain.getNumLocalIds());
|
|
|
354 }
|
|
|
355
|
|
|
356 // Adds equality constraints that equate src and dst access functions
|
|
|
357 // represented by 'srcAccessMap' and 'dstAccessMap' for each result.
|
|
|
358 // Requires that 'srcAccessMap' and 'dstAccessMap' have the same results count.
|
|
|
359 // For example, given the following two accesses functions to a 2D memref:
|
|
|
360 //
|
|
|
361 // Source access function:
|
|
|
362 // (a0 * d0 + a1 * s0 + a2, b0 * d0 + b1 * s0 + b2)
|
|
|
363 //
|
|
|
364 // Destination access function:
|
|
|
365 // (c0 * d0 + c1 * s0 + c2, f0 * d0 + f1 * s0 + f2)
|
|
|
366 //
|
|
|
367 // This method constructs the following equality constraints in
|
|
|
368 // 'dependenceDomain', by equating the access functions for each result
|
|
|
369 // (i.e. each memref dim). Notice that 'd0' for the destination access function
|
|
|
370 // is mapped into 'd0' in the equality constraint:
|
|
|
371 //
|
|
|
372 // d0 d1 s0 c
|
|
|
373 // -- -- -- --
|
|
|
374 // a0 -c0 (a1 - c1) (a1 - c2) = 0
|
|
|
375 // b0 -f0 (b1 - f1) (b1 - f2) = 0
|
|
|
376 //
|
|
|
377 // Returns failure if any AffineExpr cannot be flattened (due to it being
|
|
|
378 // semi-affine). Returns success otherwise.
|
|
|
379 static LogicalResult
|
|
|
380 addMemRefAccessConstraints(const AffineValueMap &srcAccessMap,
|
|
|
381 const AffineValueMap &dstAccessMap,
|
|
|
382 const ValuePositionMap &valuePosMap,
|
|
|
383 FlatAffineConstraints *dependenceDomain) {
|
|
|
384 AffineMap srcMap = srcAccessMap.getAffineMap();
|
|
|
385 AffineMap dstMap = dstAccessMap.getAffineMap();
|
|
|
386 assert(srcMap.getNumResults() == dstMap.getNumResults());
|
|
|
387 unsigned numResults = srcMap.getNumResults();
|
|
|
388
|
|
|
389 unsigned srcNumIds = srcMap.getNumDims() + srcMap.getNumSymbols();
|
|
|
390 ArrayRef<Value> srcOperands = srcAccessMap.getOperands();
|
|
|
391
|
|
|
392 unsigned dstNumIds = dstMap.getNumDims() + dstMap.getNumSymbols();
|
|
|
393 ArrayRef<Value> dstOperands = dstAccessMap.getOperands();
|
|
|
394
|
|
|
395 std::vector<SmallVector<int64_t, 8>> srcFlatExprs;
|
|
|
396 std::vector<SmallVector<int64_t, 8>> destFlatExprs;
|
|
|
397 FlatAffineConstraints srcLocalVarCst, destLocalVarCst;
|
|
|
398 // Get flattened expressions for the source destination maps.
|
|
|
399 if (failed(getFlattenedAffineExprs(srcMap, &srcFlatExprs, &srcLocalVarCst)) ||
|
|
|
400 failed(getFlattenedAffineExprs(dstMap, &destFlatExprs, &destLocalVarCst)))
|
|
|
401 return failure();
|
|
|
402
|
|
|
403 unsigned domNumLocalIds = dependenceDomain->getNumLocalIds();
|
|
|
404 unsigned srcNumLocalIds = srcLocalVarCst.getNumLocalIds();
|
|
|
405 unsigned dstNumLocalIds = destLocalVarCst.getNumLocalIds();
|
|
|
406 unsigned numLocalIdsToAdd = srcNumLocalIds + dstNumLocalIds;
|
|
|
407 for (unsigned i = 0; i < numLocalIdsToAdd; i++) {
|
|
|
408 dependenceDomain->addLocalId(dependenceDomain->getNumLocalIds());
|
|
|
409 }
|
|
|
410
|
|
|
411 unsigned numDims = dependenceDomain->getNumDimIds();
|
|
|
412 unsigned numSymbols = dependenceDomain->getNumSymbolIds();
|
|
|
413 unsigned numSrcLocalIds = srcLocalVarCst.getNumLocalIds();
|
|
|
414 unsigned newLocalIdOffset = numDims + numSymbols + domNumLocalIds;
|
|
|
415
|
|
|
416 // Equality to add.
|
|
|
417 SmallVector<int64_t, 8> eq(dependenceDomain->getNumCols());
|
|
|
418 for (unsigned i = 0; i < numResults; ++i) {
|
|
|
419 // Zero fill.
|
|
|
420 std::fill(eq.begin(), eq.end(), 0);
|
|
|
421
|
|
|
422 // Flattened AffineExpr for src result 'i'.
|
|
|
423 const auto &srcFlatExpr = srcFlatExprs[i];
|
|
|
424 // Set identifier coefficients from src access function.
|
|
|
425 for (unsigned j = 0, e = srcOperands.size(); j < e; ++j)
|
|
|
426 eq[valuePosMap.getSrcDimOrSymPos(srcOperands[j])] = srcFlatExpr[j];
|
|
|
427 // Local terms.
|
|
|
428 for (unsigned j = 0, e = srcNumLocalIds; j < e; j++)
|
|
|
429 eq[newLocalIdOffset + j] = srcFlatExpr[srcNumIds + j];
|
|
|
430 // Set constant term.
|
|
|
431 eq[eq.size() - 1] = srcFlatExpr[srcFlatExpr.size() - 1];
|
|
|
432
|
|
|
433 // Flattened AffineExpr for dest result 'i'.
|
|
|
434 const auto &destFlatExpr = destFlatExprs[i];
|
|
|
435 // Set identifier coefficients from dst access function.
|
|
|
436 for (unsigned j = 0, e = dstOperands.size(); j < e; ++j)
|
|
|
437 eq[valuePosMap.getDstDimOrSymPos(dstOperands[j])] -= destFlatExpr[j];
|
|
|
438 // Local terms.
|
|
|
439 for (unsigned j = 0, e = dstNumLocalIds; j < e; j++)
|
|
|
440 eq[newLocalIdOffset + numSrcLocalIds + j] = -destFlatExpr[dstNumIds + j];
|
|
|
441 // Set constant term.
|
|
|
442 eq[eq.size() - 1] -= destFlatExpr[destFlatExpr.size() - 1];
|
|
|
443
|
|
|
444 // Add equality constraint.
|
|
|
445 dependenceDomain->addEquality(eq);
|
|
|
446 }
|
|
|
447
|
|
|
448 // Add equality constraints for any operands that are defined by constant ops.
|
|
|
449 auto addEqForConstOperands = [&](ArrayRef<Value> operands) {
|
|
|
450 for (unsigned i = 0, e = operands.size(); i < e; ++i) {
|
|
|
451 if (isForInductionVar(operands[i]))
|
|
|
452 continue;
|
|
|
453 auto symbol = operands[i];
|
|
|
454 assert(isValidSymbol(symbol));
|
|
|
455 // Check if the symbol is a constant.
|
|
173
|
456 if (auto cOp = symbol.getDefiningOp<ConstantIndexOp>())
|
|
150
|
457 dependenceDomain->setIdToConstant(valuePosMap.getSymPos(symbol),
|
|
|
458 cOp.getValue());
|
|
|
459 }
|
|
|
460 };
|
|
|
461
|
|
|
462 // Add equality constraints for any src symbols defined by constant ops.
|
|
|
463 addEqForConstOperands(srcOperands);
|
|
|
464 // Add equality constraints for any dst symbols defined by constant ops.
|
|
|
465 addEqForConstOperands(dstOperands);
|
|
|
466
|
|
|
467 // By construction (see flattener), local var constraints will not have any
|
|
|
468 // equalities.
|
|
|
469 assert(srcLocalVarCst.getNumEqualities() == 0 &&
|
|
|
470 destLocalVarCst.getNumEqualities() == 0);
|
|
|
471 // Add inequalities from srcLocalVarCst and destLocalVarCst into the
|
|
|
472 // dependence domain.
|
|
|
473 SmallVector<int64_t, 8> ineq(dependenceDomain->getNumCols());
|
|
|
474 for (unsigned r = 0, e = srcLocalVarCst.getNumInequalities(); r < e; r++) {
|
|
|
475 std::fill(ineq.begin(), ineq.end(), 0);
|
|
|
476
|
|
|
477 // Set identifier coefficients from src local var constraints.
|
|
|
478 for (unsigned j = 0, e = srcOperands.size(); j < e; ++j)
|
|
|
479 ineq[valuePosMap.getSrcDimOrSymPos(srcOperands[j])] =
|
|
|
480 srcLocalVarCst.atIneq(r, j);
|
|
|
481 // Local terms.
|
|
|
482 for (unsigned j = 0, e = srcNumLocalIds; j < e; j++)
|
|
|
483 ineq[newLocalIdOffset + j] = srcLocalVarCst.atIneq(r, srcNumIds + j);
|
|
|
484 // Set constant term.
|
|
|
485 ineq[ineq.size() - 1] =
|
|
|
486 srcLocalVarCst.atIneq(r, srcLocalVarCst.getNumCols() - 1);
|
|
|
487 dependenceDomain->addInequality(ineq);
|
|
|
488 }
|
|
|
489
|
|
|
490 for (unsigned r = 0, e = destLocalVarCst.getNumInequalities(); r < e; r++) {
|
|
|
491 std::fill(ineq.begin(), ineq.end(), 0);
|
|
|
492 // Set identifier coefficients from dest local var constraints.
|
|
|
493 for (unsigned j = 0, e = dstOperands.size(); j < e; ++j)
|
|
|
494 ineq[valuePosMap.getDstDimOrSymPos(dstOperands[j])] =
|
|
|
495 destLocalVarCst.atIneq(r, j);
|
|
|
496 // Local terms.
|
|
|
497 for (unsigned j = 0, e = dstNumLocalIds; j < e; j++)
|
|
|
498 ineq[newLocalIdOffset + numSrcLocalIds + j] =
|
|
|
499 destLocalVarCst.atIneq(r, dstNumIds + j);
|
|
|
500 // Set constant term.
|
|
|
501 ineq[ineq.size() - 1] =
|
|
|
502 destLocalVarCst.atIneq(r, destLocalVarCst.getNumCols() - 1);
|
|
|
503
|
|
|
504 dependenceDomain->addInequality(ineq);
|
|
|
505 }
|
|
|
506 return success();
|
|
|
507 }
|
|
|
508
|
|
|
509 // Returns the number of outer loop common to 'src/dstDomain'.
|
|
|
510 // Loops common to 'src/dst' domains are added to 'commonLoops' if non-null.
|
|
|
511 static unsigned
|
|
|
512 getNumCommonLoops(const FlatAffineConstraints &srcDomain,
|
|
|
513 const FlatAffineConstraints &dstDomain,
|
|
|
514 SmallVectorImpl<AffineForOp> *commonLoops = nullptr) {
|
|
|
515 // Find the number of common loops shared by src and dst accesses.
|
|
|
516 unsigned minNumLoops =
|
|
|
517 std::min(srcDomain.getNumDimIds(), dstDomain.getNumDimIds());
|
|
|
518 unsigned numCommonLoops = 0;
|
|
|
519 for (unsigned i = 0; i < minNumLoops; ++i) {
|
|
|
520 if (!isForInductionVar(srcDomain.getIdValue(i)) ||
|
|
|
521 !isForInductionVar(dstDomain.getIdValue(i)) ||
|
|
|
522 srcDomain.getIdValue(i) != dstDomain.getIdValue(i))
|
|
|
523 break;
|
|
|
524 if (commonLoops != nullptr)
|
|
|
525 commonLoops->push_back(getForInductionVarOwner(srcDomain.getIdValue(i)));
|
|
|
526 ++numCommonLoops;
|
|
|
527 }
|
|
|
528 if (commonLoops != nullptr)
|
|
|
529 assert(commonLoops->size() == numCommonLoops);
|
|
|
530 return numCommonLoops;
|
|
|
531 }
|
|
|
532
|
|
|
533 // Returns Block common to 'srcAccess.opInst' and 'dstAccess.opInst'.
|
|
|
534 static Block *getCommonBlock(const MemRefAccess &srcAccess,
|
|
|
535 const MemRefAccess &dstAccess,
|
|
|
536 const FlatAffineConstraints &srcDomain,
|
|
|
537 unsigned numCommonLoops) {
|
|
|
538 if (numCommonLoops == 0) {
|
|
|
539 auto *block = srcAccess.opInst->getBlock();
|
|
|
540 while (!llvm::isa<FuncOp>(block->getParentOp())) {
|
|
|
541 block = block->getParentOp()->getBlock();
|
|
|
542 }
|
|
|
543 return block;
|
|
|
544 }
|
|
|
545 auto commonForValue = srcDomain.getIdValue(numCommonLoops - 1);
|
|
|
546 auto forOp = getForInductionVarOwner(commonForValue);
|
|
|
547 assert(forOp && "commonForValue was not an induction variable");
|
|
|
548 return forOp.getBody();
|
|
|
549 }
|
|
|
550
|
|
|
551 // Returns true if the ancestor operation of 'srcAccess' appears before the
|
|
|
552 // ancestor operation of 'dstAccess' in the common ancestral block. Returns
|
|
|
553 // false otherwise.
|
|
|
554 // Note that because 'srcAccess' or 'dstAccess' may be nested in conditionals,
|
|
|
555 // the function is named 'srcAppearsBeforeDstInCommonBlock'. Note that
|
|
|
556 // 'numCommonLoops' is the number of contiguous surrounding outer loops.
|
|
|
557 static bool srcAppearsBeforeDstInAncestralBlock(
|
|
|
558 const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
|
|
|
559 const FlatAffineConstraints &srcDomain, unsigned numCommonLoops) {
|
|
|
560 // Get Block common to 'srcAccess.opInst' and 'dstAccess.opInst'.
|
|
|
561 auto *commonBlock =
|
|
|
562 getCommonBlock(srcAccess, dstAccess, srcDomain, numCommonLoops);
|
|
|
563 // Check the dominance relationship between the respective ancestors of the
|
|
|
564 // src and dst in the Block of the innermost among the common loops.
|
|
|
565 auto *srcInst = commonBlock->findAncestorOpInBlock(*srcAccess.opInst);
|
|
|
566 assert(srcInst != nullptr);
|
|
|
567 auto *dstInst = commonBlock->findAncestorOpInBlock(*dstAccess.opInst);
|
|
|
568 assert(dstInst != nullptr);
|
|
|
569
|
|
|
570 // Determine whether dstInst comes after srcInst.
|
|
|
571 return srcInst->isBeforeInBlock(dstInst);
|
|
|
572 }
|
|
|
573
|
|
|
574 // Adds ordering constraints to 'dependenceDomain' based on number of loops
|
|
|
575 // common to 'src/dstDomain' and requested 'loopDepth'.
|
|
|
576 // Note that 'loopDepth' cannot exceed the number of common loops plus one.
|
|
|
577 // EX: Given a loop nest of depth 2 with IVs 'i' and 'j':
|
|
|
578 // *) If 'loopDepth == 1' then one constraint is added: i' >= i + 1
|
|
|
579 // *) If 'loopDepth == 2' then two constraints are added: i == i' and j' > j + 1
|
|
|
580 // *) If 'loopDepth == 3' then two constraints are added: i == i' and j == j'
|
|
|
581 static void addOrderingConstraints(const FlatAffineConstraints &srcDomain,
|
|
|
582 const FlatAffineConstraints &dstDomain,
|
|
|
583 unsigned loopDepth,
|
|
|
584 FlatAffineConstraints *dependenceDomain) {
|
|
|
585 unsigned numCols = dependenceDomain->getNumCols();
|
|
|
586 SmallVector<int64_t, 4> eq(numCols);
|
|
|
587 unsigned numSrcDims = srcDomain.getNumDimIds();
|
|
|
588 unsigned numCommonLoops = getNumCommonLoops(srcDomain, dstDomain);
|
|
|
589 unsigned numCommonLoopConstraints = std::min(numCommonLoops, loopDepth);
|
|
|
590 for (unsigned i = 0; i < numCommonLoopConstraints; ++i) {
|
|
|
591 std::fill(eq.begin(), eq.end(), 0);
|
|
|
592 eq[i] = -1;
|
|
|
593 eq[i + numSrcDims] = 1;
|
|
|
594 if (i == loopDepth - 1) {
|
|
|
595 eq[numCols - 1] = -1;
|
|
|
596 dependenceDomain->addInequality(eq);
|
|
|
597 } else {
|
|
|
598 dependenceDomain->addEquality(eq);
|
|
|
599 }
|
|
|
600 }
|
|
|
601 }
|
|
|
602
|
|
|
603 // Computes distance and direction vectors in 'dependences', by adding
|
|
|
604 // variables to 'dependenceDomain' which represent the difference of the IVs,
|
|
|
605 // eliminating all other variables, and reading off distance vectors from
|
|
|
606 // equality constraints (if possible), and direction vectors from inequalities.
|
|
|
607 static void computeDirectionVector(
|
|
|
608 const FlatAffineConstraints &srcDomain,
|
|
|
609 const FlatAffineConstraints &dstDomain, unsigned loopDepth,
|
|
|
610 FlatAffineConstraints *dependenceDomain,
|
|
|
611 SmallVector<DependenceComponent, 2> *dependenceComponents) {
|
|
|
612 // Find the number of common loops shared by src and dst accesses.
|
|
|
613 SmallVector<AffineForOp, 4> commonLoops;
|
|
|
614 unsigned numCommonLoops =
|
|
|
615 getNumCommonLoops(srcDomain, dstDomain, &commonLoops);
|
|
|
616 if (numCommonLoops == 0)
|
|
|
617 return;
|
|
|
618 // Compute direction vectors for requested loop depth.
|
|
|
619 unsigned numIdsToEliminate = dependenceDomain->getNumIds();
|
|
|
620 // Add new variables to 'dependenceDomain' to represent the direction
|
|
|
621 // constraints for each shared loop.
|
|
|
622 for (unsigned j = 0; j < numCommonLoops; ++j) {
|
|
|
623 dependenceDomain->addDimId(j);
|
|
|
624 }
|
|
|
625
|
|
|
626 // Add equality constraints for each common loop, setting newly introduced
|
|
|
627 // variable at column 'j' to the 'dst' IV minus the 'src IV.
|
|
|
628 SmallVector<int64_t, 4> eq;
|
|
|
629 eq.resize(dependenceDomain->getNumCols());
|
|
|
630 unsigned numSrcDims = srcDomain.getNumDimIds();
|
|
|
631 // Constraint variables format:
|
|
|
632 // [num-common-loops][num-src-dim-ids][num-dst-dim-ids][num-symbols][constant]
|
|
|
633 for (unsigned j = 0; j < numCommonLoops; ++j) {
|
|
|
634 std::fill(eq.begin(), eq.end(), 0);
|
|
|
635 eq[j] = 1;
|
|
|
636 eq[j + numCommonLoops] = 1;
|
|
|
637 eq[j + numCommonLoops + numSrcDims] = -1;
|
|
|
638 dependenceDomain->addEquality(eq);
|
|
|
639 }
|
|
|
640
|
|
|
641 // Eliminate all variables other than the direction variables just added.
|
|
|
642 dependenceDomain->projectOut(numCommonLoops, numIdsToEliminate);
|
|
|
643
|
|
|
644 // Scan each common loop variable column and set direction vectors based
|
|
|
645 // on eliminated constraint system.
|
|
|
646 dependenceComponents->resize(numCommonLoops);
|
|
|
647 for (unsigned j = 0; j < numCommonLoops; ++j) {
|
|
|
648 (*dependenceComponents)[j].op = commonLoops[j].getOperation();
|
|
|
649 auto lbConst = dependenceDomain->getConstantLowerBound(j);
|
|
|
650 (*dependenceComponents)[j].lb =
|
|
|
651 lbConst.getValueOr(std::numeric_limits<int64_t>::min());
|
|
|
652 auto ubConst = dependenceDomain->getConstantUpperBound(j);
|
|
|
653 (*dependenceComponents)[j].ub =
|
|
|
654 ubConst.getValueOr(std::numeric_limits<int64_t>::max());
|
|
|
655 }
|
|
|
656 }
|
|
|
657
|
|
|
658 // Populates 'accessMap' with composition of AffineApplyOps reachable from
|
|
|
659 // indices of MemRefAccess.
|
|
|
660 void MemRefAccess::getAccessMap(AffineValueMap *accessMap) const {
|
|
|
661 // Get affine map from AffineLoad/Store.
|
|
|
662 AffineMap map;
|
|
173
|
663 if (auto loadOp = dyn_cast<AffineReadOpInterface>(opInst)) {
|
|
150
|
664 map = loadOp.getAffineMap();
|
|
173
|
665 } else {
|
|
|
666 auto storeOp = cast<AffineWriteOpInterface>(opInst);
|
|
150
|
667 map = storeOp.getAffineMap();
|
|
173
|
668 }
|
|
150
|
669 SmallVector<Value, 8> operands(indices.begin(), indices.end());
|
|
|
670 fullyComposeAffineMapAndOperands(&map, &operands);
|
|
|
671 map = simplifyAffineMap(map);
|
|
|
672 canonicalizeMapAndOperands(&map, &operands);
|
|
|
673 accessMap->reset(map, operands);
|
|
|
674 }
|
|
|
675
|
|
|
676 // Builds a flat affine constraint system to check if there exists a dependence
|
|
|
677 // between memref accesses 'srcAccess' and 'dstAccess'.
|
|
|
678 // Returns 'NoDependence' if the accesses can be definitively shown not to
|
|
|
679 // access the same element.
|
|
|
680 // Returns 'HasDependence' if the accesses do access the same element.
|
|
|
681 // Returns 'Failure' if an error or unsupported case was encountered.
|
|
|
682 // If a dependence exists, returns in 'dependenceComponents' a direction
|
|
|
683 // vector for the dependence, with a component for each loop IV in loops
|
|
|
684 // common to both accesses (see Dependence in AffineAnalysis.h for details).
|
|
|
685 //
|
|
|
686 // The memref access dependence check is comprised of the following steps:
|
|
|
687 // *) Compute access functions for each access. Access functions are computed
|
|
|
688 // using AffineValueMaps initialized with the indices from an access, then
|
|
|
689 // composed with AffineApplyOps reachable from operands of that access,
|
|
|
690 // until operands of the AffineValueMap are loop IVs or symbols.
|
|
|
691 // *) Build iteration domain constraints for each access. Iteration domain
|
|
|
692 // constraints are pairs of inequality constraints representing the
|
|
|
693 // upper/lower loop bounds for each AffineForOp in the loop nest associated
|
|
|
694 // with each access.
|
|
|
695 // *) Build dimension and symbol position maps for each access, which map
|
|
|
696 // Values from access functions and iteration domains to their position
|
|
|
697 // in the merged constraint system built by this method.
|
|
|
698 //
|
|
|
699 // This method builds a constraint system with the following column format:
|
|
|
700 //
|
|
|
701 // [src-dim-identifiers, dst-dim-identifiers, symbols, constant]
|
|
|
702 //
|
|
|
703 // For example, given the following MLIR code with "source" and "destination"
|
|
|
704 // accesses to the same memref label, and symbols %M, %N, %K:
|
|
|
705 //
|
|
|
706 // affine.for %i0 = 0 to 100 {
|
|
|
707 // affine.for %i1 = 0 to 50 {
|
|
|
708 // %a0 = affine.apply
|
|
|
709 // (d0, d1) -> (d0 * 2 - d1 * 4 + s1, d1 * 3 - s0) (%i0, %i1)[%M, %N]
|
|
|
710 // // Source memref access.
|
|
|
711 // store %v0, %m[%a0#0, %a0#1] : memref<4x4xf32>
|
|
|
712 // }
|
|
|
713 // }
|
|
|
714 //
|
|
|
715 // affine.for %i2 = 0 to 100 {
|
|
|
716 // affine.for %i3 = 0 to 50 {
|
|
|
717 // %a1 = affine.apply
|
|
|
718 // (d0, d1) -> (d0 * 7 + d1 * 9 - s1, d1 * 11 + s0) (%i2, %i3)[%K, %M]
|
|
|
719 // // Destination memref access.
|
|
|
720 // %v1 = load %m[%a1#0, %a1#1] : memref<4x4xf32>
|
|
|
721 // }
|
|
|
722 // }
|
|
|
723 //
|
|
|
724 // The access functions would be the following:
|
|
|
725 //
|
|
|
726 // src: (%i0 * 2 - %i1 * 4 + %N, %i1 * 3 - %M)
|
|
|
727 // dst: (%i2 * 7 + %i3 * 9 - %M, %i3 * 11 - %K)
|
|
|
728 //
|
|
|
729 // The iteration domains for the src/dst accesses would be the following:
|
|
|
730 //
|
|
|
731 // src: 0 <= %i0 <= 100, 0 <= %i1 <= 50
|
|
|
732 // dst: 0 <= %i2 <= 100, 0 <= %i3 <= 50
|
|
|
733 //
|
|
|
734 // The symbols by both accesses would be assigned to a canonical position order
|
|
|
735 // which will be used in the dependence constraint system:
|
|
|
736 //
|
|
|
737 // symbol name: %M %N %K
|
|
|
738 // symbol pos: 0 1 2
|
|
|
739 //
|
|
|
740 // Equality constraints are built by equating each result of src/destination
|
|
|
741 // access functions. For this example, the following two equality constraints
|
|
|
742 // will be added to the dependence constraint system:
|
|
|
743 //
|
|
|
744 // [src_dim0, src_dim1, dst_dim0, dst_dim1, sym0, sym1, sym2, const]
|
|
|
745 // 2 -4 -7 -9 1 1 0 0 = 0
|
|
|
746 // 0 3 0 -11 -1 0 1 0 = 0
|
|
|
747 //
|
|
|
748 // Inequality constraints from the iteration domain will be meged into
|
|
|
749 // the dependence constraint system
|
|
|
750 //
|
|
|
751 // [src_dim0, src_dim1, dst_dim0, dst_dim1, sym0, sym1, sym2, const]
|
|
|
752 // 1 0 0 0 0 0 0 0 >= 0
|
|
|
753 // -1 0 0 0 0 0 0 100 >= 0
|
|
|
754 // 0 1 0 0 0 0 0 0 >= 0
|
|
|
755 // 0 -1 0 0 0 0 0 50 >= 0
|
|
|
756 // 0 0 1 0 0 0 0 0 >= 0
|
|
|
757 // 0 0 -1 0 0 0 0 100 >= 0
|
|
|
758 // 0 0 0 1 0 0 0 0 >= 0
|
|
|
759 // 0 0 0 -1 0 0 0 50 >= 0
|
|
|
760 //
|
|
|
761 //
|
|
|
762 // TODO(andydavis) Support AffineExprs mod/floordiv/ceildiv.
|
|
|
763 DependenceResult mlir::checkMemrefAccessDependence(
|
|
|
764 const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
|
|
|
765 unsigned loopDepth, FlatAffineConstraints *dependenceConstraints,
|
|
|
766 SmallVector<DependenceComponent, 2> *dependenceComponents, bool allowRAR) {
|
|
|
767 LLVM_DEBUG(llvm::dbgs() << "Checking for dependence at depth: "
|
|
|
768 << Twine(loopDepth) << " between:\n";);
|
|
|
769 LLVM_DEBUG(srcAccess.opInst->dump(););
|
|
|
770 LLVM_DEBUG(dstAccess.opInst->dump(););
|
|
|
771
|
|
|
772 // Return 'NoDependence' if these accesses do not access the same memref.
|
|
|
773 if (srcAccess.memref != dstAccess.memref)
|
|
|
774 return DependenceResult::NoDependence;
|
|
|
775
|
|
173
|
776 // Return 'NoDependence' if one of these accesses is not an
|
|
|
777 // AffineWriteOpInterface.
|
|
|
778 if (!allowRAR && !isa<AffineWriteOpInterface>(srcAccess.opInst) &&
|
|
|
779 !isa<AffineWriteOpInterface>(dstAccess.opInst))
|
|
150
|
780 return DependenceResult::NoDependence;
|
|
|
781
|
|
|
782 // Get composed access function for 'srcAccess'.
|
|
|
783 AffineValueMap srcAccessMap;
|
|
|
784 srcAccess.getAccessMap(&srcAccessMap);
|
|
|
785
|
|
|
786 // Get composed access function for 'dstAccess'.
|
|
|
787 AffineValueMap dstAccessMap;
|
|
|
788 dstAccess.getAccessMap(&dstAccessMap);
|
|
|
789
|
|
|
790 // Get iteration domain for the 'srcAccess' operation.
|
|
|
791 FlatAffineConstraints srcDomain;
|
|
|
792 if (failed(getInstIndexSet(srcAccess.opInst, &srcDomain)))
|
|
|
793 return DependenceResult::Failure;
|
|
|
794
|
|
|
795 // Get iteration domain for 'dstAccess' operation.
|
|
|
796 FlatAffineConstraints dstDomain;
|
|
|
797 if (failed(getInstIndexSet(dstAccess.opInst, &dstDomain)))
|
|
|
798 return DependenceResult::Failure;
|
|
|
799
|
|
|
800 // Return 'NoDependence' if loopDepth > numCommonLoops and if the ancestor
|
|
|
801 // operation of 'srcAccess' does not properly dominate the ancestor
|
|
|
802 // operation of 'dstAccess' in the same common operation block.
|
|
|
803 // Note: this check is skipped if 'allowRAR' is true, because because RAR
|
|
|
804 // deps can exist irrespective of lexicographic ordering b/w src and dst.
|
|
|
805 unsigned numCommonLoops = getNumCommonLoops(srcDomain, dstDomain);
|
|
|
806 assert(loopDepth <= numCommonLoops + 1);
|
|
|
807 if (!allowRAR && loopDepth > numCommonLoops &&
|
|
|
808 !srcAppearsBeforeDstInAncestralBlock(srcAccess, dstAccess, srcDomain,
|
|
|
809 numCommonLoops)) {
|
|
|
810 return DependenceResult::NoDependence;
|
|
|
811 }
|
|
|
812 // Build dim and symbol position maps for each access from access operand
|
|
|
813 // Value to position in merged constraint system.
|
|
|
814 ValuePositionMap valuePosMap;
|
|
|
815 buildDimAndSymbolPositionMaps(srcDomain, dstDomain, srcAccessMap,
|
|
|
816 dstAccessMap, &valuePosMap,
|
|
|
817 dependenceConstraints);
|
|
|
818
|
|
|
819 initDependenceConstraints(srcDomain, dstDomain, srcAccessMap, dstAccessMap,
|
|
|
820 valuePosMap, dependenceConstraints);
|
|
|
821
|
|
|
822 assert(valuePosMap.getNumDims() ==
|
|
|
823 srcDomain.getNumDimIds() + dstDomain.getNumDimIds());
|
|
|
824
|
|
|
825 // Create memref access constraint by equating src/dst access functions.
|
|
|
826 // Note that this check is conservative, and will fail in the future when
|
|
|
827 // local variables for mod/div exprs are supported.
|
|
|
828 if (failed(addMemRefAccessConstraints(srcAccessMap, dstAccessMap, valuePosMap,
|
|
|
829 dependenceConstraints)))
|
|
|
830 return DependenceResult::Failure;
|
|
|
831
|
|
|
832 // Add 'src' happens before 'dst' ordering constraints.
|
|
|
833 addOrderingConstraints(srcDomain, dstDomain, loopDepth,
|
|
|
834 dependenceConstraints);
|
|
|
835 // Add src and dst domain constraints.
|
|
|
836 addDomainConstraints(srcDomain, dstDomain, valuePosMap,
|
|
|
837 dependenceConstraints);
|
|
|
838
|
|
|
839 // Return 'NoDependence' if the solution space is empty: no dependence.
|
|
|
840 if (dependenceConstraints->isEmpty()) {
|
|
|
841 return DependenceResult::NoDependence;
|
|
|
842 }
|
|
|
843
|
|
|
844 // Compute dependence direction vector and return true.
|
|
|
845 if (dependenceComponents != nullptr) {
|
|
|
846 computeDirectionVector(srcDomain, dstDomain, loopDepth,
|
|
|
847 dependenceConstraints, dependenceComponents);
|
|
|
848 }
|
|
|
849
|
|
|
850 LLVM_DEBUG(llvm::dbgs() << "Dependence polyhedron:\n");
|
|
|
851 LLVM_DEBUG(dependenceConstraints->dump());
|
|
|
852 return DependenceResult::HasDependence;
|
|
|
853 }
|
|
|
854
|
|
|
855 /// Gathers dependence components for dependences between all ops in loop nest
|
|
|
856 /// rooted at 'forOp' at loop depths in range [1, maxLoopDepth].
|
|
|
857 void mlir::getDependenceComponents(
|
|
|
858 AffineForOp forOp, unsigned maxLoopDepth,
|
|
|
859 std::vector<SmallVector<DependenceComponent, 2>> *depCompsVec) {
|
|
|
860 // Collect all load and store ops in loop nest rooted at 'forOp'.
|
|
|
861 SmallVector<Operation *, 8> loadAndStoreOpInsts;
|
|
|
862 forOp.getOperation()->walk([&](Operation *opInst) {
|
|
173
|
863 if (isa<AffineReadOpInterface>(opInst) ||
|
|
|
864 isa<AffineWriteOpInterface>(opInst))
|
|
150
|
865 loadAndStoreOpInsts.push_back(opInst);
|
|
|
866 });
|
|
|
867
|
|
|
868 unsigned numOps = loadAndStoreOpInsts.size();
|
|
|
869 for (unsigned d = 1; d <= maxLoopDepth; ++d) {
|
|
|
870 for (unsigned i = 0; i < numOps; ++i) {
|
|
|
871 auto *srcOpInst = loadAndStoreOpInsts[i];
|
|
|
872 MemRefAccess srcAccess(srcOpInst);
|
|
|
873 for (unsigned j = 0; j < numOps; ++j) {
|
|
|
874 auto *dstOpInst = loadAndStoreOpInsts[j];
|
|
|
875 MemRefAccess dstAccess(dstOpInst);
|
|
|
876
|
|
|
877 FlatAffineConstraints dependenceConstraints;
|
|
|
878 SmallVector<DependenceComponent, 2> depComps;
|
|
|
879 // TODO(andydavis,bondhugula) Explore whether it would be profitable
|
|
|
880 // to pre-compute and store deps instead of repeatedly checking.
|
|
|
881 DependenceResult result = checkMemrefAccessDependence(
|
|
|
882 srcAccess, dstAccess, d, &dependenceConstraints, &depComps);
|
|
|
883 if (hasDependence(result))
|
|
|
884 depCompsVec->push_back(depComps);
|
|
|
885 }
|
|
|
886 }
|
|
|
887 }
|
|
|
888 }
|
