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