| 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 | |
| 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 = 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. |
| 143 | struct 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. |
| 163 | struct 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 | |
| 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 | /// 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. |
| 186 | LogicalResult 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. |
| 205 | DependenceResult 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. |
| 213 | inline 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. |
| 219 | inline 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]. |
| 226 | void 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 | |