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