1 //===- DependenceAnalysis.h - Dependence analysis on SSA views --*- 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 #ifndef MLIR_DIALECT_LINALG_ANALYSIS_DEPENDENCEANALYSIS_H_ 10 #define MLIR_DIALECT_LINALG_ANALYSIS_DEPENDENCEANALYSIS_H_ 11 12 #include "mlir/Dialect/Linalg/IR/LinalgOps.h" 13 #include "mlir/IR/Builders.h" 14 #include "mlir/IR/OpDefinition.h" 15 16 namespace mlir { 17 class FuncOp; 18 19 namespace linalg { 20 21 class LinalgOp; 22 23 /// A very primitive alias analysis which just records for each view, either: 24 /// 1. The base buffer, or 25 /// 2. The block argument view 26 /// that it indexes into. 27 /// This does not perform inter-block or inter-procedural analysis and assumes 28 /// that different block argument views do not alias. 29 class Aliases { 30 public: 31 /// Returns true if v1 and v2 alias. alias(Value v1,Value v2)32 bool alias(Value v1, Value v2) { return find(v1) == find(v2); } 33 34 private: 35 /// Returns the base buffer or block argument into which the view `v` aliases. 36 /// This lazily records the new aliases discovered while walking back the 37 /// use-def chain. 38 Value find(Value v); 39 40 DenseMap<Value, Value> aliases; 41 }; 42 43 /// Data structure for holding a dependence graph that operates on LinalgOp and 44 /// views as SSA values. 45 class LinalgDependenceGraph { 46 public: 47 enum DependenceType { RAR = 0, RAW, WAR, WAW, NumTypes }; 48 struct LinalgOpView { 49 Operation *op; 50 unsigned operandIndex; 51 }; 52 struct LinalgDependenceGraphElem { 53 // dependentOpView may be either: 54 // 1. src in the case of dependencesIntoGraphs. 55 // 2. dst in the case of dependencesFromDstGraphs. 56 LinalgOpView dependentOpView; 57 // View in the op that is used to index in the graph: 58 // 1. src in the case of dependencesFromDstGraphs. 59 // 2. dst in the case of dependencesIntoGraphs. 60 LinalgOpView indexingOpView; 61 // Type of the dependence. 62 DependenceType dependenceType; 63 }; 64 using LinalgDependences = SmallVector<LinalgDependenceGraphElem, 8>; 65 using DependenceGraph = DenseMap<Operation *, LinalgDependences>; 66 using dependence_iterator = LinalgDependences::const_iterator; 67 using dependence_range = iterator_range<dependence_iterator>; 68 69 static StringRef getDependenceTypeStr(DependenceType depType); 70 71 // Builds a linalg dependence graph for the ops of type LinalgOp under `f`. 72 static LinalgDependenceGraph buildDependenceGraph(Aliases &aliases, FuncOp f); 73 LinalgDependenceGraph(Aliases &aliases, ArrayRef<LinalgOp> ops); 74 75 /// Returns the X such that op -> X is a dependence of type dt. 76 dependence_range getDependencesFrom(Operation *src, DependenceType dt) const; 77 dependence_range getDependencesFrom(LinalgOp src, DependenceType dt) const; 78 79 /// Returns the X such that X -> op is a dependence of type dt. 80 dependence_range getDependencesInto(Operation *dst, DependenceType dt) const; 81 dependence_range getDependencesInto(LinalgOp dst, DependenceType dt) const; 82 83 /// Returns the operations that are interleaved between `srcLinalgOp` and 84 /// `dstLinalgOp` and that are involved in any RAW, WAR or WAW dependence 85 /// relation with `srcLinalgOp`, on any view. 86 /// Any such operation prevents reordering. 87 SmallVector<Operation *, 8> 88 findCoveringDependences(LinalgOp srcLinalgOp, LinalgOp dstLinalgOp) const; 89 90 /// Returns the operations that are interleaved between `srcLinalgOp` and 91 /// `dstLinalgOp` and that are involved in a RAR or RAW with `srcLinalgOp`. 92 /// Dependences are restricted to views aliasing `view`. 93 SmallVector<Operation *, 8> findCoveringReads(LinalgOp srcLinalgOp, 94 LinalgOp dstLinalgOp, 95 Value view) const; 96 97 /// Returns the operations that are interleaved between `srcLinalgOp` and 98 /// `dstLinalgOp` and that are involved in a WAR or WAW with `srcLinalgOp`. 99 /// Dependences are restricted to views aliasing `view`. 100 SmallVector<Operation *, 8> findCoveringWrites(LinalgOp srcLinalgOp, 101 LinalgOp dstLinalgOp, 102 Value view) const; 103 104 /// Returns true if the two operations have the specified dependence from 105 /// `srcLinalgOp` to `dstLinalgOp`. 106 bool hasDependenceFrom(LinalgOp srcLinalgOp, LinalgOp dstLinalgOp, 107 ArrayRef<DependenceType> depTypes = { 108 DependenceType::RAW, DependenceType::WAW}) const; 109 110 /// Returns true if the `linalgOp` has dependences into it. 111 bool hasDependentOperationsInto(LinalgOp linalgOp, 112 ArrayRef<DependenceType> depTypes = { 113 DependenceType::RAW, 114 DependenceType::WAW}) const; 115 116 /// Returns true if the `linalgOp` has dependences from it. 117 bool hasDependentOperationsFrom(LinalgOp linalgOp, 118 ArrayRef<DependenceType> depTypes = { 119 DependenceType::RAW, 120 DependenceType::WAW}) const; 121 122 /// Returns true if the `linalgOp` has dependences into or from it. 123 bool hasDependentOperations(LinalgOp linalgOp, 124 ArrayRef<DependenceType> depTypes = { 125 DependenceType::RAW, 126 DependenceType::WAW}) const; 127 128 /// Returns all operations that have a dependence into `linalgOp` of types 129 /// listed in `depTypes`. 130 SmallVector<LinalgDependenceGraphElem, 2> getDependentOperationsInto( 131 LinalgOp linalgOp, ArrayRef<DependenceType> depTypes = { 132 DependenceType::RAW, DependenceType::WAW}) const; 133 134 /// Returns all operations that have a dependence from `linalgOp` of types 135 /// listed in `depTypes`. 136 SmallVector<LinalgDependenceGraphElem, 2> getDependentOperationsFrom( 137 LinalgOp linalgOp, ArrayRef<DependenceType> depTypes = { 138 DependenceType::RAW, DependenceType::WAW}) const; 139 140 /// Returns all dependent operations (into and from) given `operation`. 141 SmallVector<LinalgDependenceGraphElem, 2> 142 getDependentOperations(LinalgOp linalgOp, 143 ArrayRef<DependenceType> depTypes = { 144 DependenceType::RAW, DependenceType::WAW}) const; 145 146 private: 147 // Keep dependences in both directions, this is not just a performance gain 148 // but it also reduces usage errors. 149 // Dependence information is stored as a map of: 150 // (source operation -> LinalgDependenceGraphElem) 151 DependenceGraph dependencesFromGraphs[DependenceType::NumTypes]; 152 // Reverse dependence information is stored as a map of: 153 // (destination operation -> LinalgDependenceGraphElem) 154 DependenceGraph dependencesIntoGraphs[DependenceType::NumTypes]; 155 156 /// Analyses the aliasing views between `src` and `dst` and inserts the proper 157 /// dependences in the graph. 158 void addDependencesBetween(LinalgOp src, LinalgOp dst); 159 160 // Adds an new dependence unit in the proper graph. 161 // Uses std::pair to keep operations and view together and avoid usage errors 162 // related to src/dst and producer/consumer terminology in the context of 163 // dependences. 164 void addDependenceElem(DependenceType dt, LinalgOpView indexingOpView, 165 LinalgOpView dependentOpView); 166 167 /// Implementation detail for findCoveringxxx. 168 SmallVector<Operation *, 8> 169 findOperationsWithCoveringDependences(LinalgOp srcLinalgOp, 170 LinalgOp dstLinalgOp, Value view, 171 ArrayRef<DependenceType> types) const; 172 173 Aliases &aliases; 174 SmallVector<LinalgOp, 8> linalgOps; 175 DenseMap<Operation *, unsigned> linalgOpPositions; 176 }; 177 } // namespace linalg 178 } // namespace mlir 179 180 #endif // MLIR_DIALECT_LINALG_ANALYSIS_DEPENDENCEANALYSIS_H_ 181