MLIR  20.0.0git
LoopAnalysis.h
Go to the documentation of this file.
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 <optional>
19 
20 namespace mlir {
21 class AffineExpr;
22 class AffineMap;
23 class BlockArgument;
24 class MemRefType;
25 class Operation;
26 class Value;
27 
28 namespace affine {
29 class AffineForOp;
30 class NestedPattern;
31 
32 /// Returns the trip count of the loop as an affine map with its corresponding
33 /// operands if the latter is expressible as an affine expression, and nullptr
34 /// otherwise. This method always succeeds as long as the lower bound is not a
35 /// multi-result map. The trip count expression is simplified before returning.
36 /// This method only utilizes map composition to construct lower and upper
37 /// bounds before computing the trip count expressions
38 void getTripCountMapAndOperands(AffineForOp forOp, AffineMap *map,
39  SmallVectorImpl<Value> *operands);
40 
41 /// Returns the trip count of the loop if it's a constant, std::nullopt
42 /// otherwise. This uses affine expression analysis and is able to determine
43 /// constant trip count in non-trivial cases.
44 std::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 /// Checks if an affine read or write operation depends on `forOp`'s IV, i.e.,
52 /// if the memory access is invariant on `forOp`.
53 template <typename LoadOrStoreOp>
54 bool isInvariantAccess(LoadOrStoreOp memOp, AffineForOp forOp);
55 
56 /// Given an induction variable `iv` of type AffineForOp and `indices` of type
57 /// IndexType, returns the set of `indices` that are independent of `iv`.
58 ///
59 /// Prerequisites (inherited from `isAccessInvariant` above):
60 /// 1. `iv` and `indices` of the proper type;
61 /// 2. at most one affine.apply is reachable from each index in `indices`;
62 ///
63 /// Emits a note if it encounters a chain of affine.apply and conservatively
64 /// those cases.
65 DenseSet<Value, DenseMapInfo<Value>>
66 getInvariantAccesses(Value iv, ArrayRef<Value> indices);
67 
68 /// Given:
69 /// 1. an induction variable `iv` of type AffineForOp;
70 /// 2. a `memoryOp` of type const LoadOp& or const StoreOp&;
71 /// determines whether `memoryOp` has a contiguous access along `iv`. Contiguous
72 /// is defined as either invariant or varying only along a unique MemRef dim.
73 /// Upon success, the unique MemRef dim is written in `memRefDim` (or -1 to
74 /// convey the memRef access is invariant along `iv`).
75 ///
76 /// Prerequisites:
77 /// 1. `memRefDim` ~= nullptr;
78 /// 2. `iv` of the proper type;
79 /// 3. the MemRef accessed by `memoryOp` has no layout map or at most an
80 /// identity layout map.
81 ///
82 /// Currently only supports no layout map or identity layout map in the memref.
83 /// Returns false if the memref has a non-identity layoutMap. This behavior is
84 /// conservative.
85 template <typename LoadOrStoreOp>
86 bool isContiguousAccess(Value iv, LoadOrStoreOp memoryOp, int *memRefDim);
87 
88 using VectorizableLoopFun = std::function<bool(AffineForOp)>;
89 
90 /// Checks whether the loop is structurally vectorizable; i.e.:
91 /// 1. no conditionals are nested under the loop;
92 /// 2. all nested load/stores are to scalar MemRefs.
93 /// TODO: relax the no-conditionals restriction
94 bool isVectorizableLoopBody(AffineForOp loop,
95  NestedPattern &vectorTransferMatcher);
96 
97 /// Checks whether the loop is structurally vectorizable and that all the LoadOp
98 /// and StoreOp matched have access indexing functions that are either:
99 /// 1. invariant along the loop induction variable created by 'loop';
100 /// 2. varying along at most one memory dimension. If such a unique dimension
101 /// is found, it is written into `memRefDim`.
102 bool isVectorizableLoopBody(AffineForOp loop, int *memRefDim,
103  NestedPattern &vectorTransferMatcher);
104 
105 /// Checks where SSA dominance would be violated if a for op's body
106 /// operations are shifted by the specified shifts. This method checks if a
107 /// 'def' and all its uses have the same shift factor.
108 // TODO: extend this to check for memory-based dependence violation when we have
109 // the support.
110 bool isOpwiseShiftValid(AffineForOp forOp, ArrayRef<uint64_t> shifts);
111 
112 /// Checks whether hyper-rectangular loop tiling of the nest represented by
113 /// `loops` is valid. The validity condition is from Irigoin and Triolet,
114 /// which states that two tiles cannot depend on each other. We simplify such
115 /// condition to just checking whether there is any negative dependence
116 /// direction, since we have the prior knowledge that the tiling results will be
117 /// hyper-rectangles, which are scheduled in the lexicographically increasing
118 /// order on the vector of loop indices. This function will return failure when
119 /// any dependence component is negative along any of `loops`.
121 
122 } // namespace affine
123 } // namespace mlir
124 
125 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_LOOPANALYSIS_H
std::optional< uint64_t > getConstantTripCount(AffineForOp forOp)
Returns the trip count of the loop if it's a constant, std::nullopt otherwise.
bool isTilingValid(ArrayRef< AffineForOp > loops)
Checks whether hyper-rectangular loop tiling of the nest represented by loops is valid.
bool isVectorizableLoopBody(AffineForOp loop, NestedPattern &vectorTransferMatcher)
Checks whether the loop is structurally vectorizable; i.e.
DenseSet< Value, DenseMapInfo< Value > > getInvariantAccesses(Value iv, ArrayRef< Value > indices)
Given an induction variable iv of type AffineForOp and indices of type IndexType, returns the set of ...
void getTripCountMapAndOperands(AffineForOp forOp, AffineMap *map, SmallVectorImpl< Value > *operands)
Returns the trip count of the loop as an affine map with its corresponding operands if the latter is ...
bool isInvariantAccess(LoadOrStoreOp memOp, AffineForOp forOp)
Checks if an affine read or write operation depends on forOp's IV, i.e., if the memory access is inva...
uint64_t getLargestDivisorOfTripCount(AffineForOp forOp)
Returns the greatest known integral divisor of the trip count.
bool isContiguousAccess(Value iv, LoadOrStoreOp memoryOp, int *memRefDim)
Given:
std::function< bool(AffineForOp)> VectorizableLoopFun
Definition: LoopAnalysis.h:88
bool isOpwiseShiftValid(AffineForOp forOp, ArrayRef< uint64_t > shifts)
Checks where SSA dominance would be violated if a for op's body operations are shifted by the specifi...
Include the generated interface declarations.