1//===- LoopAnalysis.cpp - Misc loop 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 loop analysis routines.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
14
15#include "mlir/Analysis/SliceAnalysis.h"
16#include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h"
17#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
18#include "mlir/Dialect/Affine/Analysis/NestedMatcher.h"
19#include "mlir/Dialect/Affine/Analysis/Utils.h"
20#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
21#include "llvm/Support/MathExtras.h"
22
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/DebugLog.h"
25#include <numeric>
26#include <optional>
27
28#define DEBUG_TYPE "affine-loop-analysis"
29
30using namespace mlir;
31using namespace mlir::affine;
32
33namespace {
34/// A directed graph to model relationships between MLIR Operations.
35class DirectedOpGraph {
36public:
37 /// Add a node to the graph.
38 void addNode(Operation *op) {
39 assert(!hasNode(op) && "node already added");
40 nodes.emplace_back(Args&: op);
41 edges[op] = {};
42 }
43
44 /// Add an edge from `src` to `dest`.
45 void addEdge(Operation *src, Operation *dest) {
46 // This is a multi-graph.
47 assert(hasNode(src) && "src node does not exist in graph");
48 assert(hasNode(dest) && "dest node does not exist in graph");
49 edges[src].push_back(Elt: getNode(op: dest));
50 }
51
52 /// Returns true if there is a (directed) cycle in the graph.
53 bool hasCycle() { return dfs(/*cycleCheck=*/true); }
54
55 void printEdges() {
56 for (auto &en : edges) {
57 llvm::dbgs() << *en.first << " (" << en.first << ")"
58 << " has " << en.second.size() << " edges:\n";
59 for (auto *node : en.second) {
60 llvm::dbgs() << '\t' << *node->op << '\n';
61 }
62 }
63 }
64
65private:
66 /// A node of a directed graph between MLIR Operations to model various
67 /// relationships. This is meant to be used internally.
68 struct DGNode {
69 DGNode(Operation *op) : op(op) {};
70 Operation *op;
71
72 // Start and finish visit numbers are standard in DFS to implement things
73 // like finding strongly connected components. These numbers are modified
74 // during analyses on the graph and so seemingly const API methods will be
75 // non-const.
76
77 /// Start visit number.
78 int vn = -1;
79
80 /// Finish visit number.
81 int fn = -1;
82 };
83
84 /// Get internal node corresponding to `op`.
85 DGNode *getNode(Operation *op) {
86 auto *value =
87 llvm::find_if(Range&: nodes, P: [&](const DGNode &node) { return node.op == op; });
88 assert(value != nodes.end() && "node doesn't exist in graph");
89 return &*value;
90 }
91
92 /// Returns true if `key` is in the graph.
93 bool hasNode(Operation *key) const {
94 return llvm::find_if(Range: nodes, P: [&](const DGNode &node) {
95 return node.op == key;
96 }) != nodes.end();
97 }
98
99 /// Perform a depth-first traversal of the graph setting visited and finished
100 /// numbers. If `cycleCheck` is set, detects cycles and returns true as soon
101 /// as the first cycle is detected, and false if there are no cycles. If
102 /// `cycleCheck` is not set, completes the DFS and the `return` value doesn't
103 /// have a meaning.
104 bool dfs(bool cycleCheck = false) {
105 for (DGNode &node : nodes) {
106 node.vn = 0;
107 node.fn = -1;
108 }
109
110 unsigned time = 0;
111 for (DGNode &node : nodes) {
112 if (node.vn == 0) {
113 bool ret = dfsNode(node, cycleCheck, time);
114 // Check if a cycle was already found.
115 if (cycleCheck && ret)
116 return true;
117 } else if (cycleCheck && node.fn == -1) {
118 // We have encountered a node whose visit has started but it's not
119 // finished. So we have a cycle.
120 return true;
121 }
122 }
123 return false;
124 }
125
126 /// Perform depth-first traversal starting at `node`. Return true
127 /// as soon as a cycle is found if `cycleCheck` was set. Update `time`.
128 bool dfsNode(DGNode &node, bool cycleCheck, unsigned &time) const {
129 auto nodeEdges = edges.find(Val: node.op);
130 assert(nodeEdges != edges.end() && "missing node in graph");
131 node.vn = ++time;
132
133 for (auto &neighbour : nodeEdges->second) {
134 if (neighbour->vn == 0) {
135 bool ret = dfsNode(node&: *neighbour, cycleCheck, time);
136 if (cycleCheck && ret)
137 return true;
138 } else if (cycleCheck && neighbour->fn == -1) {
139 // We have encountered a node whose visit has started but it's not
140 // finished. So we have a cycle.
141 return true;
142 }
143 }
144
145 // Update finish time.
146 node.fn = ++time;
147
148 return false;
149 }
150
151 // The list of nodes. The storage is owned by this class.
152 SmallVector<DGNode> nodes;
153
154 // Edges as an adjacency list.
155 DenseMap<Operation *, SmallVector<DGNode *>> edges;
156};
157} // namespace
158
159/// Returns the trip count of the loop as an affine expression if the latter is
160/// expressible as an affine expression, and nullptr otherwise. The trip count
161/// expression is simplified before returning. This method only utilizes map
162/// composition to construct lower and upper bounds before computing the trip
163/// count expressions.
164void mlir::affine::getTripCountMapAndOperands(
165 AffineForOp forOp, AffineMap *tripCountMap,
166 SmallVectorImpl<Value> *tripCountOperands) {
167 MLIRContext *context = forOp.getContext();
168 int64_t step = forOp.getStepAsInt();
169 int64_t loopSpan;
170 if (forOp.hasConstantBounds()) {
171 int64_t lb = forOp.getConstantLowerBound();
172 int64_t ub = forOp.getConstantUpperBound();
173 loopSpan = ub - lb;
174 if (loopSpan < 0)
175 loopSpan = 0;
176 *tripCountMap = AffineMap::getConstantMap(
177 val: llvm::divideCeilSigned(Numerator: loopSpan, Denominator: step), context);
178 tripCountOperands->clear();
179 return;
180 }
181 auto lbMap = forOp.getLowerBoundMap();
182 auto ubMap = forOp.getUpperBoundMap();
183 if (lbMap.getNumResults() != 1) {
184 *tripCountMap = AffineMap();
185 return;
186 }
187
188 // Difference of each upper bound expression from the single lower bound
189 // expression (divided by the step) provides the expressions for the trip
190 // count map.
191 AffineValueMap ubValueMap(ubMap, forOp.getUpperBoundOperands());
192 AffineValueMap lbValueMap(lbMap, forOp.getLowerBoundOperands());
193
194 AffineValueMap tripCountValueMap;
195 AffineValueMap::cartesianProductDifference(a: ubValueMap, b: lbValueMap,
196 res: &tripCountValueMap);
197 for (unsigned i = 0, e = tripCountValueMap.getNumResults(); i < e; ++i)
198 tripCountValueMap.setResult(i,
199 e: tripCountValueMap.getResult(i).ceilDiv(v: step));
200
201 *tripCountMap = tripCountValueMap.getAffineMap();
202 tripCountOperands->assign(in_start: tripCountValueMap.getOperands().begin(),
203 in_end: tripCountValueMap.getOperands().end());
204}
205
206/// Returns the trip count of the loop if it's a constant, std::nullopt
207/// otherwise. This method uses affine expression analysis (in turn using
208/// getTripCount) and is able to determine constant trip count in non-trivial
209/// cases.
210std::optional<uint64_t> mlir::affine::getConstantTripCount(AffineForOp forOp) {
211 if (std::optional<APInt> tripCount = forOp.getStaticTripCount())
212 return tripCount->getZExtValue();
213 return std::nullopt;
214}
215
216/// Returns the greatest known integral divisor of the trip count. Affine
217/// expression analysis is used (indirectly through getTripCount), and
218/// this method is thus able to determine non-trivial divisors.
219uint64_t mlir::affine::getLargestDivisorOfTripCount(AffineForOp forOp) {
220 SmallVector<Value, 4> operands;
221 AffineMap map;
222 getTripCountMapAndOperands(forOp, tripCountMap: &map, tripCountOperands: &operands);
223
224 if (!map)
225 return 1;
226
227 // The largest divisor of the trip count is the GCD of the individual largest
228 // divisors.
229 assert(map.getNumResults() >= 1 && "expected one or more results");
230 std::optional<uint64_t> gcd;
231 for (auto resultExpr : map.getResults()) {
232 uint64_t thisGcd;
233 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: resultExpr)) {
234 uint64_t tripCount = constExpr.getValue();
235 // 0 iteration loops (greatest divisor is 2^64 - 1).
236 if (tripCount == 0)
237 thisGcd = std::numeric_limits<uint64_t>::max();
238 else
239 // The greatest divisor is the trip count.
240 thisGcd = tripCount;
241 } else {
242 // Trip count is not a known constant; return its largest known divisor.
243 thisGcd = resultExpr.getLargestKnownDivisor();
244 }
245 if (gcd.has_value())
246 gcd = std::gcd(m: *gcd, n: thisGcd);
247 else
248 gcd = thisGcd;
249 }
250 assert(gcd.has_value() && "value expected per above logic");
251 return *gcd;
252}
253
254/// Given an affine.for `iv` and an access `index` of type index, returns `true`
255/// if `index` is independent of `iv` and false otherwise.
256///
257/// Prerequisites: `iv` and `index` of the proper type;
258static bool isAccessIndexInvariant(Value iv, Value index) {
259 assert(isAffineForInductionVar(iv) && "iv must be an affine.for iv");
260 assert(isa<IndexType>(index.getType()) && "index must be of 'index' type");
261 auto map = AffineMap::getMultiDimIdentityMap(/*numDims=*/1, context: iv.getContext());
262 SmallVector<Value> operands = {index};
263 AffineValueMap avm(map, operands);
264 avm.composeSimplifyAndCanonicalize();
265 return !avm.isFunctionOf(idx: 0, value: iv);
266}
267
268// Pre-requisite: Loop bounds should be in canonical form.
269template <typename LoadOrStoreOp>
270bool mlir::affine::isInvariantAccess(LoadOrStoreOp memOp, AffineForOp forOp) {
271 AffineValueMap avm(memOp.getAffineMap(), memOp.getMapOperands());
272 avm.composeSimplifyAndCanonicalize();
273 return !llvm::is_contained(Range: avm.getOperands(), Element: forOp.getInductionVar());
274}
275
276// Explicitly instantiate the template so that the compiler knows we need them.
277template bool mlir::affine::isInvariantAccess(AffineReadOpInterface,
278 AffineForOp);
279template bool mlir::affine::isInvariantAccess(AffineWriteOpInterface,
280 AffineForOp);
281template bool mlir::affine::isInvariantAccess(AffineLoadOp, AffineForOp);
282template bool mlir::affine::isInvariantAccess(AffineStoreOp, AffineForOp);
283
284DenseSet<Value> mlir::affine::getInvariantAccesses(Value iv,
285 ArrayRef<Value> indices) {
286 DenseSet<Value> res;
287 for (Value index : indices) {
288 if (isAccessIndexInvariant(iv, index))
289 res.insert(V: index);
290 }
291 return res;
292}
293
294// TODO: check access stride.
295template <typename LoadOrStoreOp>
296bool mlir::affine::isContiguousAccess(Value iv, LoadOrStoreOp memoryOp,
297 int *memRefDim) {
298 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
299 AffineWriteOpInterface>::value,
300 "Must be called on either an affine read or write op");
301 assert(memRefDim && "memRefDim == nullptr");
302 auto memRefType = memoryOp.getMemRefType();
303
304 if (!memRefType.getLayout().isIdentity())
305 return memoryOp.emitError("NYI: non-trivial layout map"), false;
306
307 int uniqueVaryingIndexAlongIv = -1;
308 auto accessMap = memoryOp.getAffineMap();
309 SmallVector<Value, 4> mapOperands(memoryOp.getMapOperands());
310 unsigned numDims = accessMap.getNumDims();
311 for (unsigned i = 0, e = memRefType.getRank(); i < e; ++i) {
312 // Gather map operands used in result expr 'i' in 'exprOperands'.
313 SmallVector<Value, 4> exprOperands;
314 auto resultExpr = accessMap.getResult(i);
315 resultExpr.walk([&](AffineExpr expr) {
316 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr))
317 exprOperands.push_back(Elt: mapOperands[dimExpr.getPosition()]);
318 else if (auto symExpr = dyn_cast<AffineSymbolExpr>(Val&: expr))
319 exprOperands.push_back(Elt: mapOperands[numDims + symExpr.getPosition()]);
320 });
321 // Check access invariance of each operand in 'exprOperands'.
322 for (Value exprOperand : exprOperands) {
323 if (!isAccessIndexInvariant(iv, index: exprOperand)) {
324 if (uniqueVaryingIndexAlongIv != -1) {
325 // 2+ varying indices -> do not vectorize along iv.
326 return false;
327 }
328 uniqueVaryingIndexAlongIv = i;
329 }
330 }
331 }
332
333 if (uniqueVaryingIndexAlongIv == -1)
334 *memRefDim = -1;
335 else
336 *memRefDim = memRefType.getRank() - (uniqueVaryingIndexAlongIv + 1);
337 return true;
338}
339
340template bool mlir::affine::isContiguousAccess(Value iv,
341 AffineReadOpInterface loadOp,
342 int *memRefDim);
343template bool mlir::affine::isContiguousAccess(Value iv,
344 AffineWriteOpInterface loadOp,
345 int *memRefDim);
346
347template <typename LoadOrStoreOp>
348static bool isVectorElement(LoadOrStoreOp memoryOp) {
349 auto memRefType = memoryOp.getMemRefType();
350 return isa<VectorType>(memRefType.getElementType());
351}
352
353using VectorizableOpFun = std::function<bool(AffineForOp, Operation &)>;
354
355static bool
356isVectorizableLoopBodyWithOpCond(AffineForOp loop,
357 const VectorizableOpFun &isVectorizableOp,
358 NestedPattern &vectorTransferMatcher) {
359 auto *forOp = loop.getOperation();
360
361 // No vectorization across conditionals for now.
362 auto conditionals = matcher::If();
363 SmallVector<NestedMatch, 8> conditionalsMatched;
364 conditionals.match(op: forOp, matches: &conditionalsMatched);
365 if (!conditionalsMatched.empty()) {
366 return false;
367 }
368
369 // No vectorization for ops with operand or result types that are not
370 // vectorizable.
371 auto types = matcher::Op(filter: [](Operation &op) -> bool {
372 if (llvm::any_of(Range: op.getOperandTypes(), P: [](Type type) {
373 if (MemRefType t = dyn_cast<MemRefType>(Val&: type))
374 return !VectorType::isValidElementType(t: t.getElementType());
375 return !VectorType::isValidElementType(t: type);
376 }))
377 return true;
378 return !llvm::all_of(Range: op.getResultTypes(), P: VectorType::isValidElementType);
379 });
380 SmallVector<NestedMatch, 8> opsMatched;
381 types.match(op: forOp, matches: &opsMatched);
382 if (!opsMatched.empty()) {
383 return false;
384 }
385
386 // No vectorization across unknown regions.
387 auto regions = matcher::Op(filter: [](Operation &op) -> bool {
388 return op.getNumRegions() != 0 && !isa<AffineIfOp, AffineForOp>(Val: op);
389 });
390 SmallVector<NestedMatch, 8> regionsMatched;
391 regions.match(op: forOp, matches: &regionsMatched);
392 if (!regionsMatched.empty()) {
393 return false;
394 }
395
396 SmallVector<NestedMatch, 8> vectorTransfersMatched;
397 vectorTransferMatcher.match(op: forOp, matches: &vectorTransfersMatched);
398 if (!vectorTransfersMatched.empty()) {
399 return false;
400 }
401
402 auto loadAndStores = matcher::Op(filter: matcher::isLoadOrStore);
403 SmallVector<NestedMatch, 8> loadAndStoresMatched;
404 loadAndStores.match(op: forOp, matches: &loadAndStoresMatched);
405 for (auto ls : loadAndStoresMatched) {
406 auto *op = ls.getMatchedOperation();
407 auto load = dyn_cast<AffineLoadOp>(Val: op);
408 auto store = dyn_cast<AffineStoreOp>(Val: op);
409 // Only scalar types are considered vectorizable, all load/store must be
410 // vectorizable for a loop to qualify as vectorizable.
411 // TODO: ponder whether we want to be more general here.
412 bool vector = load ? isVectorElement(memoryOp: load) : isVectorElement(memoryOp: store);
413 if (vector) {
414 return false;
415 }
416 if (isVectorizableOp && !isVectorizableOp(loop, *op)) {
417 return false;
418 }
419 }
420 return true;
421}
422
423bool mlir::affine::isVectorizableLoopBody(
424 AffineForOp loop, int *memRefDim, NestedPattern &vectorTransferMatcher) {
425 *memRefDim = -1;
426 VectorizableOpFun fun([memRefDim](AffineForOp loop, Operation &op) {
427 auto load = dyn_cast<AffineLoadOp>(Val&: op);
428 auto store = dyn_cast<AffineStoreOp>(Val&: op);
429 int thisOpMemRefDim = -1;
430 bool isContiguous =
431 load ? isContiguousAccess(iv: loop.getInductionVar(),
432 memoryOp: cast<AffineReadOpInterface>(Val&: *load),
433 memRefDim: &thisOpMemRefDim)
434 : isContiguousAccess(iv: loop.getInductionVar(),
435 memoryOp: cast<AffineWriteOpInterface>(Val&: *store),
436 memRefDim: &thisOpMemRefDim);
437 if (thisOpMemRefDim != -1) {
438 // If memory accesses vary across different dimensions then the loop is
439 // not vectorizable.
440 if (*memRefDim != -1 && *memRefDim != thisOpMemRefDim)
441 return false;
442 *memRefDim = thisOpMemRefDim;
443 }
444 return isContiguous;
445 });
446 return isVectorizableLoopBodyWithOpCond(loop, isVectorizableOp: fun, vectorTransferMatcher);
447}
448
449bool mlir::affine::isVectorizableLoopBody(
450 AffineForOp loop, NestedPattern &vectorTransferMatcher) {
451 return isVectorizableLoopBodyWithOpCond(loop, isVectorizableOp: nullptr, vectorTransferMatcher);
452}
453
454/// Checks whether SSA dominance would be violated if a for op's body
455/// operations are shifted by the specified shifts. This method checks if a
456/// 'def' and all its uses have the same shift factor.
457// TODO: extend this to check for memory-based dependence violation when we have
458// the support.
459bool mlir::affine::isOpwiseShiftValid(AffineForOp forOp,
460 ArrayRef<uint64_t> shifts) {
461 auto *forBody = forOp.getBody();
462 assert(shifts.size() == forBody->getOperations().size());
463
464 // Work backwards over the body of the block so that the shift of a use's
465 // ancestor operation in the block gets recorded before it's looked up.
466 DenseMap<Operation *, uint64_t> forBodyShift;
467 for (const auto &it :
468 llvm::enumerate(First: llvm::reverse(C&: forBody->getOperations()))) {
469 auto &op = it.value();
470
471 // Get the index of the current operation, note that we are iterating in
472 // reverse so we need to fix it up.
473 size_t index = shifts.size() - it.index() - 1;
474
475 // Remember the shift of this operation.
476 uint64_t shift = shifts[index];
477 forBodyShift.try_emplace(Key: &op, Args&: shift);
478
479 // Validate the results of this operation if it were to be shifted.
480 for (unsigned i = 0, e = op.getNumResults(); i < e; ++i) {
481 Value result = op.getResult(idx: i);
482 for (auto *user : result.getUsers()) {
483 // If an ancestor operation doesn't lie in the block of forOp,
484 // there is no shift to check.
485 if (auto *ancOp = forBody->findAncestorOpInBlock(op&: *user)) {
486 assert(forBodyShift.count(ancOp) > 0 && "ancestor expected in map");
487 if (shift != forBodyShift[ancOp])
488 return false;
489 }
490 }
491 }
492 }
493 return true;
494}
495
496bool mlir::affine::isTilingValid(ArrayRef<AffineForOp> loops) {
497 assert(!loops.empty() && "no original loops provided");
498
499 // We first find out all dependences we intend to check.
500 SmallVector<Operation *, 8> loadAndStoreOps;
501 loops[0]->walk(callback: [&](Operation *op) {
502 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: op))
503 loadAndStoreOps.push_back(Elt: op);
504 });
505
506 unsigned numOps = loadAndStoreOps.size();
507 unsigned numLoops = loops.size();
508 for (unsigned d = 1; d <= numLoops + 1; ++d) {
509 for (unsigned i = 0; i < numOps; ++i) {
510 Operation *srcOp = loadAndStoreOps[i];
511 MemRefAccess srcAccess(srcOp);
512 for (unsigned j = 0; j < numOps; ++j) {
513 Operation *dstOp = loadAndStoreOps[j];
514 MemRefAccess dstAccess(dstOp);
515
516 SmallVector<DependenceComponent, 2> depComps;
517 DependenceResult result = checkMemrefAccessDependence(
518 srcAccess, dstAccess, loopDepth: d, /*dependenceConstraints=*/nullptr,
519 dependenceComponents: &depComps);
520
521 // Skip if there is no dependence in this case.
522 if (!hasDependence(result))
523 continue;
524
525 // Check whether there is any negative direction vector in the
526 // dependence components found above, which means that dependence is
527 // violated by the default hyper-rect tiling method.
528 LDBG() << "Checking whether tiling legality violated "
529 << "for dependence at depth: " << Twine(d) << " between:"
530 << OpWithFlags(srcAccess.opInst, OpPrintingFlags().skipRegions())
531 << "\nand:\n"
532 << OpWithFlags(dstAccess.opInst,
533 OpPrintingFlags().skipRegions());
534 for (const DependenceComponent &depComp : depComps) {
535 if (depComp.lb.has_value() && depComp.ub.has_value() &&
536 *depComp.lb < *depComp.ub && *depComp.ub < 0) {
537 LDBG() << "Dependence component lb = " << Twine(*depComp.lb)
538 << " ub = " << Twine(*depComp.ub)
539 << " is negative at depth: " << Twine(d)
540 << " and thus violates the legality rule.";
541 return false;
542 }
543 }
544 }
545 }
546 }
547
548 return true;
549}
550
551bool mlir::affine::hasCyclicDependence(AffineForOp root) {
552 // Collect all the memory accesses in the source nest grouped by their
553 // immediate parent block.
554 DirectedOpGraph graph;
555 SmallVector<MemRefAccess> accesses;
556 root->walk(callback: [&](Operation *op) {
557 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: op)) {
558 accesses.emplace_back(Args&: op);
559 graph.addNode(op);
560 }
561 });
562
563 // Construct the dependence graph for all the collected acccesses.
564 unsigned rootDepth = getNestingDepth(op: root);
565 for (const auto &accA : accesses) {
566 for (const auto &accB : accesses) {
567 if (accA.memref != accB.memref)
568 continue;
569 // Perform the dependence on all surrounding loops + the body.
570 unsigned numCommonLoops =
571 getNumCommonSurroundingLoops(a&: *accA.opInst, b&: *accB.opInst);
572 for (unsigned d = rootDepth + 1; d <= numCommonLoops + 1; ++d) {
573 if (!noDependence(result: checkMemrefAccessDependence(srcAccess: accA, dstAccess: accB, loopDepth: d)))
574 graph.addEdge(src: accA.opInst, dest: accB.opInst);
575 }
576 }
577 }
578 return graph.hasCycle();
579}
580