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_ANALYSIS_AFFINE_ANALYSIS_H
16 #define MLIR_ANALYSIS_AFFINE_ANALYSIS_H
17
18 #include "mlir/IR/Value.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/SmallVector.h"
21
22 namespace mlir {
23
24 class AffineApplyOp;
25 class AffineForOp;
26 class AffineValueMap;
27 class FlatAffineConstraints;
28 class Operation;
29
30 /// Returns in `affineApplyOps`, the sequence of those AffineApplyOp
31 /// Operations that are reachable via a search starting from `operands` and
32 /// ending at those operands that are not the result of an AffineApplyOp.
33 void getReachableAffineApplyOps(ArrayRef<Value> operands,
34 SmallVectorImpl<Operation *> &affineApplyOps);
35
36 /// Builds a system of constraints with dimensional identifiers corresponding to
37 /// the loop IVs of the forOps and AffineIfOp's operands appearing in
38 /// that order. Bounds of the loop are used to add appropriate inequalities.
39 /// Constraints from the index sets of AffineIfOp are also added. Any symbols
40 /// founds in the bound operands are added as symbols in the system. Returns
41 /// failure for the yet unimplemented cases. `ops` accepts both AffineForOp and
42 /// AffineIfOp.
43 // TODO: handle non-unit strides.
44 LogicalResult getIndexSet(MutableArrayRef<Operation *> ops,
45 FlatAffineConstraints *domain);
46
47 /// Encapsulates a memref load or store access information.
48 struct MemRefAccess {
49 Value memref;
50 Operation *opInst;
51 SmallVector<Value, 4> indices;
52
53 /// Constructs a MemRefAccess from a load or store operation.
54 // TODO: add accessors to standard op's load, store, DMA op's to return
55 // MemRefAccess, i.e., loadOp->getAccess(), dmaOp->getRead/WriteAccess.
56 explicit MemRefAccess(Operation *opInst);
57
58 // Returns the rank of the memref associated with this access.
59 unsigned getRank() const;
60 // Returns true if this access is of a store op.
61 bool isStore() const;
62
63 /// Populates 'accessMap' with composition of AffineApplyOps reachable from
64 /// 'indices'.
65 void getAccessMap(AffineValueMap *accessMap) const;
66
67 /// Equal if both affine accesses can be proved to be equivalent at compile
68 /// time (considering the memrefs, their respective affine access maps and
69 /// operands). The equality of access functions + operands is checked by
70 /// subtracting fully composed value maps, and then simplifying the difference
71 /// using the expression flattener.
72 /// TODO: this does not account for aliasing of memrefs.
73 bool operator==(const MemRefAccess &rhs) const;
74 bool operator!=(const MemRefAccess &rhs) const { return !(*this == rhs); }
75 };
76
77 // DependenceComponent contains state about the direction of a dependence as an
78 // interval [lb, ub] for an AffineForOp.
79 // Distance vectors components are represented by the interval [lb, ub] with
80 // lb == ub.
81 // Direction vectors components are represented by the interval [lb, ub] with
82 // lb < ub. Note that ub/lb == None means unbounded.
83 struct DependenceComponent {
84 // The AffineForOp Operation associated with this dependence component.
85 Operation *op;
86 // The lower bound of the dependence distance.
87 Optional<int64_t> lb;
88 // The upper bound of the dependence distance (inclusive).
89 Optional<int64_t> ub;
DependenceComponentDependenceComponent90 DependenceComponent() : lb(llvm::None), ub(llvm::None) {}
91 };
92
93 /// Checks whether two accesses to the same memref access the same element.
94 /// Each access is specified using the MemRefAccess structure, which contains
95 /// the operation, indices and memref associated with the access. Returns
96 /// 'NoDependence' if it can be determined conclusively that the accesses do not
97 /// access the same memref element. If 'allowRAR' is true, will consider
98 /// read-after-read dependences (typically used by applications trying to
99 /// optimize input reuse).
100 // TODO: Wrap 'dependenceConstraints' and 'dependenceComponents' into a single
101 // struct.
102 // TODO: Make 'dependenceConstraints' optional arg.
103 struct DependenceResult {
104 enum ResultEnum {
105 HasDependence, // A dependence exists between 'srcAccess' and 'dstAccess'.
106 NoDependence, // No dependence exists between 'srcAccess' and 'dstAccess'.
107 Failure, // Dependence check failed due to unsupported cases.
108 } value;
DependenceResultDependenceResult109 DependenceResult(ResultEnum v) : value(v) {}
110 };
111
112 DependenceResult checkMemrefAccessDependence(
113 const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
114 unsigned loopDepth, FlatAffineConstraints *dependenceConstraints,
115 SmallVector<DependenceComponent, 2> *dependenceComponents,
116 bool allowRAR = false);
117
118 /// Utility function that returns true if the provided DependenceResult
119 /// corresponds to a dependence result.
hasDependence(DependenceResult result)120 inline bool hasDependence(DependenceResult result) {
121 return result.value == DependenceResult::HasDependence;
122 }
123
124 /// Returns in 'depCompsVec', dependence components for dependences between all
125 /// load and store ops in loop nest rooted at 'forOp', at loop depths in range
126 /// [1, maxLoopDepth].
127 void getDependenceComponents(
128 AffineForOp forOp, unsigned maxLoopDepth,
129 std::vector<SmallVector<DependenceComponent, 2>> *depCompsVec);
130
131 } // end namespace mlir
132
133 #endif // MLIR_ANALYSIS_AFFINE_ANALYSIS_H
134