MLIR  20.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 {
86 
87  /// Constructs a MemRefAccess from a load or store operation.
88  // TODO: add accessors to standard op's load, store, DMA op's to return
89  // MemRefAccess, i.e., loadOp->getAccess(), dmaOp->getRead/WriteAccess.
90  explicit MemRefAccess(Operation *opInst);
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.
130  /// TODO: this does not account for aliasing of memrefs.
131  bool operator==(const MemRefAccess &rhs) const;
132  bool operator!=(const MemRefAccess &rhs) const { return !(*this == rhs); }
133 };
134 
135 // DependenceComponent contains state about the direction of a dependence as an
136 // interval [lb, ub] for an AffineForOp.
137 // Distance vectors components are represented by the interval [lb, ub] with
138 // lb == ub.
139 // Direction vectors components are represented by the interval [lb, ub] with
140 // lb < ub. Note that ub/lb == None means unbounded.
142  // The AffineForOp Operation associated with this dependence component.
143  Operation *op = nullptr;
144  // The lower bound of the dependence distance.
145  std::optional<int64_t> lb;
146  // The upper bound of the dependence distance (inclusive).
147  std::optional<int64_t> ub;
148  DependenceComponent() : lb(std::nullopt), ub(std::nullopt) {}
149 };
150 
151 /// Checks whether two accesses to the same memref access the same element.
152 /// Each access is specified using the MemRefAccess structure, which contains
153 /// the operation, indices and memref associated with the access. Returns
154 /// 'NoDependence' if it can be determined conclusively that the accesses do not
155 /// access the same memref element. If 'allowRAR' is true, will consider
156 /// read-after-read dependences (typically used by applications trying to
157 /// optimize input reuse).
158 // TODO: Wrap 'dependenceConstraints' and 'dependenceComponents' into a single
159 // struct.
160 // TODO: Make 'dependenceConstraints' optional arg.
162  enum ResultEnum {
163  HasDependence, // A dependence exists between 'srcAccess' and 'dstAccess'.
164  NoDependence, // No dependence exists between 'srcAccess' and 'dstAccess'.
165  Failure, // Dependence check failed due to unsupported cases.
166  } value;
168 };
169 
170 DependenceResult checkMemrefAccessDependence(
171  const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
172  unsigned loopDepth,
173  FlatAffineValueConstraints *dependenceConstraints = nullptr,
174  SmallVector<DependenceComponent, 2> *dependenceComponents = nullptr,
175  bool allowRAR = false);
176 
177 /// Utility function that returns true if the provided DependenceResult
178 /// corresponds to a dependence result.
179 inline bool hasDependence(DependenceResult result) {
180  return result.value == DependenceResult::HasDependence;
181 }
182 
183 /// Returns true if the provided DependenceResult corresponds to the absence of
184 /// a dependence.
185 inline bool noDependence(DependenceResult result) {
186  return result.value == DependenceResult::NoDependence;
187 }
188 
189 /// Returns in 'depCompsVec', dependence components for dependences between all
190 /// load and store ops in loop nest rooted at 'forOp', at loop depths in range
191 /// [1, maxLoopDepth].
193  AffineForOp forOp, unsigned maxLoopDepth,
194  std::vector<SmallVector<DependenceComponent, 2>> *depCompsVec);
195 
196 } // namespace affine
197 } // namespace mlir
198 
199 #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:1838
SmallVector< Value, 4 > indices
LogicalResult getAccessRelation(presburger::IntegerRelation &accessRel) const
Creates an access relation for the access.
bool operator!=(const MemRefAccess &rhs) const
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