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
18 #include "mlir/Analysis/Presburger/IntegerRelation.h"
19 #include "mlir/Dialect/Arith/IR/Arith.h"
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.
43 Value value;
44 };
45
46 /// Populate `supportedReductions` with descriptors of the supported reductions.
47 void getSupportedReductions(
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.
67 void getReachableAffineApplyOps(ArrayRef<Value> operands,
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.
78 LogicalResult getIndexSet(MutableArrayRef<Operation *> ops,
79 FlatAffineValueConstraints *domain);
80
81 /// Encapsulates a memref load or store access information.
82 struct MemRefAccess {
83 Value memref;
84 Operation *opInst;
85 SmallVector<Value, 4> indices;
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.
141 struct DependenceComponent {
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;
DependenceComponentDependenceComponent148 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.
161 struct DependenceResult {
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;
DependenceResultDependenceResult167 DependenceResult(ResultEnum v) : value(v) {}
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.
hasDependence(DependenceResult 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.
noDependence(DependenceResult result)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].
192 void getDependenceComponents(
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
200