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/ArithAttributes.h"
20#include "mlir/IR/Value.h"
21#include "llvm/ADT/SmallVector.h"
22#include <optional>
23
24namespace mlir {
25class Operation;
26
27namespace affine {
28class AffineApplyOp;
29class AffineForOp;
30class AffineValueMap;
31class FlatAffineRelation;
32class FlatAffineValueConstraints;
33
34/// A description of a (parallelizable) reduction in an affine loop.
35struct 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.
47void 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.
53bool 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.
62bool 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.
67void 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.
78LogicalResult getIndexSet(MutableArrayRef<Operation *> ops,
79 FlatAffineValueConstraints *domain);
80
81/// Encapsulates a memref load or store access information.
82struct MemRefAccess {
83 Value memref;
84 Operation *opInst = nullptr;
85 SmallVector<Value, 4> indices;
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.
143struct DependenceComponent {
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.
163struct DependenceResult {
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;
169 DependenceResult(ResultEnum v) : value(v) {}
170};
171
172DependenceResult 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/// Builds in `rel` the access relation of an access that reads or writes
180/// `accessValueMap` over the iteration `domain`, relating the iterations of
181/// the domain to the elements they touch. Unlike `MemRefAccess`'s method of
182/// the same name, it takes the access and its domain as they are, rather than
183/// reading them from an operation, so it can describe an access that is going
184/// to exist (for example, one a transformation is deciding whether to create)
185/// as well as one that already does.
186LogicalResult getAccessRelation(const AffineValueMap &accessValueMap,
187 const FlatAffineValueConstraints &domain,
188 presburger::IntegerRelation &rel);
189
190/// Checks whether the accesses two relations describe touch the same element,
191/// i.e. whether there is a dependence between them carried at `loopDepth`.
192/// This is `checkMemrefAccessDependence` from the point where it has nothing
193/// but the relations left to work on, so it serves an access built by hand out
194/// of an access map and a domain just as well as one read off an operation.
195///
196/// Returns 'NoDependence' if it can be determined conclusively that the two do
197/// not touch the same element. Note that a caller working from relations it
198/// built itself has to have established what the operation-based entry point
199/// checks on its own account: that the two access the same memref, that at
200/// least one of them writes, and, where `loopDepth` is past the loops they
201/// share, that the source precedes the destination.
202///
203/// The check composes `srcRel` and `dstRel` in place, so their contents are
204/// unspecified on return.
205DependenceResult checkAccessDependence(
206 presburger::IntegerRelation &&srcRel, presburger::IntegerRelation &&dstRel,
207 unsigned loopDepth,
208 FlatAffineValueConstraints *dependenceConstraints = nullptr,
209 SmallVector<DependenceComponent, 2> *dependenceComponents = nullptr);
210
211/// Utility function that returns true if the provided DependenceResult
212/// corresponds to a dependence result.
213inline bool hasDependence(DependenceResult result) {
214 return result.value == DependenceResult::HasDependence;
215}
216
217/// Returns true if the provided DependenceResult corresponds to the absence of
218/// a dependence.
219inline bool noDependence(DependenceResult result) {
220 return result.value == DependenceResult::NoDependence;
221}
222
223/// Returns in 'depCompsVec', dependence components for dependences between all
224/// load and store ops in loop nest rooted at 'forOp', at loop depths in range
225/// [1, maxLoopDepth].
226void getDependenceComponents(
227 AffineForOp forOp, unsigned maxLoopDepth,
228 std::vector<SmallVector<DependenceComponent, 2>> *depCompsVec);
229
230} // namespace affine
231} // namespace mlir
232
233#endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINEANALYSIS_H
234