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