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