MLIR  16.0.0git
AffineAnalysis.h
Go to the documentation of this file.
1 //===- AffineAnalysis.h - analyses for affine structures --------*- 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 that perform analysis
10 // involving affine structures (AffineExprStorage, AffineMap, IntegerSet, etc.)
11 // and other IR structures that in turn use these.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef MLIR_DIALECT_AFFINE_ANALYSIS_AFFINEANALYSIS_H
16 #define MLIR_DIALECT_AFFINE_ANALYSIS_AFFINEANALYSIS_H
17 
19 #include "mlir/IR/Value.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/SmallVector.h"
22 
23 namespace mlir {
24 
25 class AffineApplyOp;
26 class AffineForOp;
27 class AffineValueMap;
28 class FlatAffineRelation;
29 class FlatAffineValueConstraints;
30 class Operation;
31 
32 /// A description of a (parallelizable) reduction in an affine loop.
33 struct LoopReduction {
34  /// Reduction kind.
35  arith::AtomicRMWKind kind;
36 
37  /// Position of the iteration argument that acts as accumulator.
38  unsigned iterArgPosition;
39 
40  /// The value being reduced.
42 };
43 
44 /// Populate `supportedReductions` with descriptors of the supported reductions.
46  AffineForOp forOp, SmallVectorImpl<LoopReduction> &supportedReductions);
47 
48 /// Returns true if `forOp' is a parallel loop. If `parallelReductions` is
49 /// provided, populates it with descriptors of the parallelizable reductions and
50 /// treats them as not preventing parallelization.
51 bool isLoopParallel(
52  AffineForOp forOp,
53  SmallVectorImpl<LoopReduction> *parallelReductions = nullptr);
54 
55 /// Returns true if `forOp' doesn't have memory dependences preventing
56 /// parallelization. Memrefs that are allocated inside `forOp` do not impact its
57 /// dependences and parallelism. This function does not check iter_args (for
58 /// values other than memref types) and should be used only as a building block
59 /// for complete parallelism-checking functions.
60 bool isLoopMemoryParallel(AffineForOp forOp);
61 
62 /// Returns in `affineApplyOps`, the sequence of those AffineApplyOp
63 /// Operations that are reachable via a search starting from `operands` and
64 /// ending at those operands that are not the result of an AffineApplyOp.
66  SmallVectorImpl<Operation *> &affineApplyOps);
67 
68 /// Builds a system of constraints with dimensional variables corresponding to
69 /// the loop IVs of the forOps and AffineIfOp's operands appearing in
70 /// that order. Bounds of the loop are used to add appropriate inequalities.
71 /// Constraints from the index sets of AffineIfOp are also added. Any symbols
72 /// founds in the bound operands are added as symbols in the system. Returns
73 /// failure for the yet unimplemented cases. `ops` accepts both AffineForOp and
74 /// AffineIfOp.
75 // TODO: handle non-unit strides.
78 
79 /// Encapsulates a memref load or store access information.
80 struct MemRefAccess {
84 
85  /// Constructs a MemRefAccess from a load or store operation.
86  // TODO: add accessors to standard op's load, store, DMA op's to return
87  // MemRefAccess, i.e., loadOp->getAccess(), dmaOp->getRead/WriteAccess.
88  explicit MemRefAccess(Operation *opInst);
89 
90  // Returns the rank of the memref associated with this access.
91  unsigned getRank() const;
92  // Returns true if this access is of a store op.
93  bool isStore() const;
94 
95  /// Creates an access relation for the access. An access relation maps
96  /// elements of an iteration domain to the element(s) of an array domain
97  /// accessed by that iteration of the associated statement through some array
98  /// reference. For example, given the MLIR code:
99  ///
100  /// affine.for %i0 = 0 to 10 {
101  /// affine.for %i1 = 0 to 10 {
102  /// %a = affine.load %arr[%i0 + %i1, %i0 + 2 * %i1] : memref<100x100xf32>
103  /// }
104  /// }
105  ///
106  /// The access relation, assuming that the memory locations for %arr are
107  /// represented as %m0, %m1 would be:
108  ///
109  /// (%i0, %i1) -> (%m0, %m1)
110  /// %m0 = %i0 + %i1
111  /// %m1 = %i0 + 2 * %i1
112  /// 0 <= %i0 < 10
113  /// 0 <= %i1 < 10
114  ///
115  /// Returns failure for yet unimplemented/unsupported cases (see docs of
116  /// mlir::getIndexSet and mlir::getRelationFromMap for these cases).
117  LogicalResult getAccessRelation(FlatAffineRelation &accessRel) const;
118 
119  /// Populates 'accessMap' with composition of AffineApplyOps reachable from
120  /// 'indices'.
121  void getAccessMap(AffineValueMap *accessMap) const;
122 
123  /// Equal if both affine accesses can be proved to be equivalent at compile
124  /// time (considering the memrefs, their respective affine access maps and
125  /// operands). The equality of access functions + operands is checked by
126  /// subtracting fully composed value maps, and then simplifying the difference
127  /// using the expression flattener.
128  /// TODO: this does not account for aliasing of memrefs.
129  bool operator==(const MemRefAccess &rhs) const;
130  bool operator!=(const MemRefAccess &rhs) const { return !(*this == rhs); }
131 };
132 
133 // DependenceComponent contains state about the direction of a dependence as an
134 // interval [lb, ub] for an AffineForOp.
135 // Distance vectors components are represented by the interval [lb, ub] with
136 // lb == ub.
137 // Direction vectors components are represented by the interval [lb, ub] with
138 // lb < ub. Note that ub/lb == None means unbounded.
140  // The AffineForOp Operation associated with this dependence component.
141  Operation *op = nullptr;
142  // The lower bound of the dependence distance.
144  // The upper bound of the dependence distance (inclusive).
147 };
148 
149 /// Checks whether two accesses to the same memref access the same element.
150 /// Each access is specified using the MemRefAccess structure, which contains
151 /// the operation, indices and memref associated with the access. Returns
152 /// 'NoDependence' if it can be determined conclusively that the accesses do not
153 /// access the same memref element. If 'allowRAR' is true, will consider
154 /// read-after-read dependences (typically used by applications trying to
155 /// optimize input reuse).
156 // TODO: Wrap 'dependenceConstraints' and 'dependenceComponents' into a single
157 // struct.
158 // TODO: Make 'dependenceConstraints' optional arg.
160  enum ResultEnum {
161  HasDependence, // A dependence exists between 'srcAccess' and 'dstAccess'.
162  NoDependence, // No dependence exists between 'srcAccess' and 'dstAccess'.
163  Failure, // Dependence check failed due to unsupported cases.
164  } value;
165  DependenceResult(ResultEnum v) : value(v) {}
166 };
167 
169  const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
170  unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints,
171  SmallVector<DependenceComponent, 2> *dependenceComponents,
172  bool allowRAR = false);
173 
174 /// Utility function that returns true if the provided DependenceResult
175 /// corresponds to a dependence result.
176 inline bool hasDependence(DependenceResult result) {
177  return result.value == DependenceResult::HasDependence;
178 }
179 
180 /// Returns true if the provided DependenceResult corresponds to the absence of
181 /// a dependence.
182 inline bool noDependence(DependenceResult result) {
183  return result.value == DependenceResult::NoDependence;
184 }
185 
186 /// Returns in 'depCompsVec', dependence components for dependences between all
187 /// load and store ops in loop nest rooted at 'forOp', at loop depths in range
188 /// [1, maxLoopDepth].
190  AffineForOp forOp, unsigned maxLoopDepth,
191  std::vector<SmallVector<DependenceComponent, 2>> *depCompsVec);
192 
193 } // namespace mlir
194 
195 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINEANALYSIS_H
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints, SmallVector< DependenceComponent, 2 > *dependenceComponents, bool allowRAR=false)
Include the generated interface declarations.
void getDependenceComponents(AffineForOp forOp, unsigned maxLoopDepth, std::vector< SmallVector< DependenceComponent, 2 >> *depCompsVec)
Returns in &#39;depCompsVec&#39;, dependence components for dependences between all load and store ops in loo...
The OpAsmOpInterface, see OpAsmInterface.td for more details.
Definition: CallGraph.h:221
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...
Optional< int64_t > lb
bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)
Returns true if `forOp&#39; is a parallel loop.
unsigned iterArgPosition
Position of the iteration argument that acts as accumulator.
Checks whether two accesses to the same memref access the same element.
bool isLoopMemoryParallel(AffineForOp forOp)
Returns true if `forOp&#39; doesn&#39;t have memory dependences preventing parallelization.
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
bool operator!=(const MemRefAccess &rhs) const
arith::AtomicRMWKind kind
Reduction kind.
bool hasDependence(DependenceResult result)
Utility function that returns true if the provided DependenceResult corresponds to a dependence resul...
enum mlir::DependenceResult::ResultEnum value
bool noDependence(DependenceResult result)
Returns true if the provided DependenceResult corresponds to the absence of a dependence.
void getSupportedReductions(AffineForOp forOp, SmallVectorImpl< LoopReduction > &supportedReductions)
Populate supportedReductions with descriptors of the supported reductions.
SmallVector< Value, 4 > indices
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
LogicalResult getIndexSet(MutableArrayRef< Operation *> ops, FlatAffineValueConstraints *domain)
Builds a system of constraints with dimensional variables corresponding to the loop IVs of the forOps...
DependenceResult(ResultEnum v)
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable...
Optional< int64_t > ub
Encapsulates a memref load or store access information.
A description of a (parallelizable) reduction in an affine loop.
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
Value value
The value being reduced.
void getReachableAffineApplyOps(ArrayRef< Value > operands, SmallVectorImpl< Operation *> &affineApplyOps)
Returns in affineApplyOps, the sequence of those AffineApplyOp Operations that are reachable via a se...
Operation * opInst
bool operator==(StringAttr lhs, std::nullptr_t)
Define comparisons for StringAttr against nullptr and itself to avoid the StringRef overloads from be...