1 //===- LoopAnalysis.h - loop analysis methods -------------------*- C++ -*-===// 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 header file defines prototypes for methods to analyze loops. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef MLIR_DIALECT_AFFINE_ANALYSIS_LOOPANALYSIS_H 14 #define MLIR_DIALECT_AFFINE_ANALYSIS_LOOPANALYSIS_H 15 16 #include "mlir/Support/LLVM.h" 17 #include "llvm/ADT/ArrayRef.h" 18 #include "llvm/ADT/Optional.h" 19 20 namespace mlir { 21 22 class AffineExpr; 23 class AffineForOp; 24 class AffineMap; 25 class BlockArgument; 26 class MemRefType; 27 class NestedPattern; 28 class Operation; 29 class Value; 30 31 /// Returns the trip count of the loop as an affine map with its corresponding 32 /// operands if the latter is expressible as an affine expression, and nullptr 33 /// otherwise. This method always succeeds as long as the lower bound is not a 34 /// multi-result map. The trip count expression is simplified before returning. 35 /// This method only utilizes map composition to construct lower and upper 36 /// bounds before computing the trip count expressions 37 void getTripCountMapAndOperands(AffineForOp forOp, AffineMap *map, 38 SmallVectorImpl<Value> *operands); 39 40 /// Returns the trip count of the loop if it's a constant, None otherwise. This 41 /// uses affine expression analysis and is able to determine constant trip count 42 /// in non-trivial cases. 43 Optional<uint64_t> getConstantTripCount(AffineForOp forOp); 44 45 /// Returns the greatest known integral divisor of the trip count. Affine 46 /// expression analysis is used (indirectly through getTripCount), and 47 /// this method is thus able to determine non-trivial divisors. 48 uint64_t getLargestDivisorOfTripCount(AffineForOp forOp); 49 50 /// Given an induction variable `iv` of type AffineForOp and `indices` of type 51 /// IndexType, returns the set of `indices` that are independent of `iv`. 52 /// 53 /// Prerequisites (inherited from `isAccessInvariant` above): 54 /// 1. `iv` and `indices` of the proper type; 55 /// 2. at most one affine.apply is reachable from each index in `indices`; 56 /// 57 /// Emits a note if it encounters a chain of affine.apply and conservatively 58 /// those cases. 59 DenseSet<Value, DenseMapInfo<Value>> 60 getInvariantAccesses(Value iv, ArrayRef<Value> indices); 61 62 using VectorizableLoopFun = std::function<bool(AffineForOp)>; 63 64 /// Checks whether the loop is structurally vectorizable; i.e.: 65 /// 1. no conditionals are nested under the loop; 66 /// 2. all nested load/stores are to scalar MemRefs. 67 /// TODO: relax the no-conditionals restriction 68 bool isVectorizableLoopBody(AffineForOp loop, 69 NestedPattern &vectorTransferMatcher); 70 71 /// Checks whether the loop is structurally vectorizable and that all the LoadOp 72 /// and StoreOp matched have access indexing functions that are are either: 73 /// 1. invariant along the loop induction variable created by 'loop'; 74 /// 2. varying along at most one memory dimension. If such a unique dimension 75 /// is found, it is written into `memRefDim`. 76 bool isVectorizableLoopBody(AffineForOp loop, int *memRefDim, 77 NestedPattern &vectorTransferMatcher); 78 79 /// Checks where SSA dominance would be violated if a for op's body 80 /// operations are shifted by the specified shifts. This method checks if a 81 /// 'def' and all its uses have the same shift factor. 82 // TODO: extend this to check for memory-based dependence violation when we have 83 // the support. 84 bool isOpwiseShiftValid(AffineForOp forOp, ArrayRef<uint64_t> shifts); 85 86 } // namespace mlir 87 88 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_LOOPANALYSIS_H 89