| 1 | //===- LivenessAnalysis.cpp - Liveness analysis ---------------------------===// |
| 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 | #include "mlir/IR/SymbolTable.h" |
| 10 | #include <cassert> |
| 11 | #include <mlir/Analysis/DataFlow/LivenessAnalysis.h> |
| 12 | |
| 13 | #include <llvm/Support/DebugLog.h> |
| 14 | #include <mlir/Analysis/DataFlow/SparseAnalysis.h> |
| 15 | #include <mlir/Analysis/DataFlow/Utils.h> |
| 16 | #include <mlir/Analysis/DataFlowFramework.h> |
| 17 | #include <mlir/IR/Operation.h> |
| 18 | #include <mlir/IR/Value.h> |
| 19 | #include <mlir/Interfaces/CallInterfaces.h> |
| 20 | #include <mlir/Interfaces/SideEffectInterfaces.h> |
| 21 | #include <mlir/Support/LLVM.h> |
| 22 | |
| 23 | #define DEBUG_TYPE "liveness-analysis" |
| 24 | |
| 25 | using namespace mlir; |
| 26 | using namespace mlir::dataflow; |
| 27 | |
| 28 | //===----------------------------------------------------------------------===// |
| 29 | // Liveness |
| 30 | //===----------------------------------------------------------------------===// |
| 31 | |
| 32 | void Liveness::print(raw_ostream &os) const { |
| 33 | os << (isLive ? "live" : "not live" ); |
| 34 | } |
| 35 | |
| 36 | ChangeResult Liveness::markLive() { |
| 37 | bool wasLive = isLive; |
| 38 | isLive = true; |
| 39 | return wasLive ? ChangeResult::NoChange : ChangeResult::Change; |
| 40 | } |
| 41 | |
| 42 | ChangeResult Liveness::meet(const AbstractSparseLattice &other) { |
| 43 | const auto *otherLiveness = reinterpret_cast<const Liveness *>(&other); |
| 44 | return otherLiveness->isLive ? markLive() : ChangeResult::NoChange; |
| 45 | } |
| 46 | |
| 47 | //===----------------------------------------------------------------------===// |
| 48 | // LivenessAnalysis |
| 49 | //===----------------------------------------------------------------------===// |
| 50 | |
| 51 | LogicalResult LivenessAnalysis::initialize(Operation *top) { |
| 52 | // Users outside the analysis root are not visited. Mark all root results live |
| 53 | // so that this missing information does not make their producers dead. For a |
| 54 | // region branch root, this keeps the yielded values and their producers live. |
| 55 | for (Value result : top->getResults()) |
| 56 | setToExitState(getLatticeElement(value: result)); |
| 57 | return SparseBackwardDataFlowAnalysis<Liveness>::initialize(top); |
| 58 | } |
| 59 | |
| 60 | /// For every value, liveness analysis determines whether or not it is "live". |
| 61 | /// |
| 62 | /// A value is considered "live" iff it: |
| 63 | /// (1) has memory effects OR |
| 64 | /// (2) is returned by a public function OR |
| 65 | /// (3) is used to compute a value of type (1) or (2) OR |
| 66 | /// (4) is returned by a return-like op whose parent isn't a callable |
| 67 | /// nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...) |
| 68 | /// These ops have their own semantics, so we conservatively mark the |
| 69 | /// the yield value as live. |
| 70 | /// It is also to be noted that a value could be of multiple types (1/2/3) at |
| 71 | /// the same time. |
| 72 | /// |
| 73 | /// A value "has memory effects" iff it: |
| 74 | /// (1.a) is an operand of an op with memory effects OR |
| 75 | /// (1.b) is a non-forwarded branch operand and its branch op could take the |
| 76 | /// control to a block that has an op with memory effects OR |
| 77 | /// (1.c) is a non-forwarded branch operand and its branch op could result |
| 78 | /// in different live result OR |
| 79 | /// (1.d) is a non-forwarded call operand. |
| 80 | /// |
| 81 | /// A value `A` is said to be "used to compute" value `B` iff `B` cannot be |
| 82 | /// computed in the absence of `A`. Thus, in this implementation, we say that |
| 83 | /// value `A` is used to compute value `B` iff: |
| 84 | /// (3.a) `B` is a result of an op with operand `A` OR |
| 85 | /// (3.b) `A` is used to compute some value `C` and `C` is used to compute |
| 86 | /// `B`. |
| 87 | |
| 88 | LogicalResult |
| 89 | LivenessAnalysis::visitOperation(Operation *op, ArrayRef<Liveness *> operands, |
| 90 | ArrayRef<const Liveness *> results) { |
| 91 | LDBG() << "[visitOperation] Enter: " |
| 92 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 93 | // This marks values of type (1.a) and (4) liveness as "live". |
| 94 | if (!wouldOpBeTriviallyDead(op)) { |
| 95 | LDBG() << "[visitOperation] Operation has memory effects or is " |
| 96 | "return-like, marking operands live" ; |
| 97 | for (auto *operand : operands) { |
| 98 | LDBG() << " [visitOperation] Marking operand live: " << operand << " (" |
| 99 | << operand->isLive << ")" ; |
| 100 | propagateIfChanged(state: operand, changed: operand->markLive()); |
| 101 | } |
| 102 | } |
| 103 | |
| 104 | // This marks values of type (3) liveness as "live". |
| 105 | bool foundLiveResult = false; |
| 106 | for (const Liveness *r : results) { |
| 107 | if (r->isLive && !foundLiveResult) { |
| 108 | LDBG() << "[visitOperation] Found live result, " |
| 109 | "meeting all operands with result: " |
| 110 | << r; |
| 111 | // It is assumed that each operand is used to compute each result of an |
| 112 | // op. Thus, if at least one result is live, each operand is live. |
| 113 | for (Liveness *operand : operands) { |
| 114 | LDBG() << " [visitOperation] Meeting operand: " << operand |
| 115 | << " with result: " << r; |
| 116 | meet(lhs: operand, rhs: *r); |
| 117 | } |
| 118 | foundLiveResult = true; |
| 119 | } |
| 120 | LDBG() << "[visitOperation] Adding dependency for result: " << r |
| 121 | << " after op: " << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 122 | addDependency(state: const_cast<Liveness *>(r), point: getProgramPointAfter(op)); |
| 123 | } |
| 124 | return success(); |
| 125 | } |
| 126 | |
| 127 | void LivenessAnalysis::visitBranchOperand(OpOperand &operand) { |
| 128 | Operation *op = operand.getOwner(); |
| 129 | LDBG() << "Visiting branch operand: " << operand.get() |
| 130 | << " in op: " << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 131 | // We know (at the moment) and assume (for the future) that `operand` is a |
| 132 | // non-forwarded branch operand of a `RegionBranchOpInterface`, |
| 133 | // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op. |
| 134 | assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) || |
| 135 | isa<RegionBranchTerminatorOpInterface>(op)) && |
| 136 | "expected the op to be `RegionBranchOpInterface`, " |
| 137 | "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`" ); |
| 138 | |
| 139 | // The lattices of the non-forwarded branch operands don't get updated like |
| 140 | // the forwarded branch operands or the non-branch operands. Thus they need |
| 141 | // to be handled separately. This is where we handle them. |
| 142 | |
| 143 | // 1. BranchOpInterface: We cannot track all successor blocks. Therefore, we |
| 144 | // conservatively consider the non-forwarded operand of the branch operation |
| 145 | // live. We can just call visitOperation, which treats any terminator as live. |
| 146 | // 2. RegionBranchOpInterface: We can simply visit it as a normal operation |
| 147 | // with this operand. The operand is live if the results of the op are used, |
| 148 | // or if it has any recursive memory side effects (which visitOperation will |
| 149 | // check). |
| 150 | // 3. RegionBranchOpTerminatorInterface, the operand is live if the |
| 151 | // surrounding RegionBranchOp is live, so we call visitOperation on the |
| 152 | // surrounding op, but with the operand that we are looking at. |
| 153 | auto *visitOp = |
| 154 | isa<RegionBranchTerminatorOpInterface>(Val: op) ? op->getParentOp() : op; |
| 155 | Liveness *operandLiveness[] = {getLatticeElement(value: operand.get())}; |
| 156 | SmallVector<const Liveness *, 4> resultsLiveness; |
| 157 | for (const Value result : visitOp->getResults()) |
| 158 | resultsLiveness.push_back(Elt: getLatticeElement(value: result)); |
| 159 | LDBG() << "Visiting operation for non-forwarded branch operand: " |
| 160 | << OpWithFlags(visitOp, OpPrintingFlags().skipRegions()); |
| 161 | (void)visitOperation(op: visitOp, operands: operandLiveness, results: resultsLiveness); |
| 162 | } |
| 163 | |
| 164 | void LivenessAnalysis::visitCallOperand(OpOperand &operand) { |
| 165 | LDBG() << "Visiting call operand: " << operand.get() |
| 166 | << " in op: " << *operand.getOwner(); |
| 167 | // We know (at the moment) and assume (for the future) that `operand` is a |
| 168 | // non-forwarded call operand of an op implementing `CallOpInterface`. |
| 169 | assert(isa<CallOpInterface>(operand.getOwner()) && |
| 170 | "expected the op to implement `CallOpInterface`" ); |
| 171 | |
| 172 | // The lattices of the non-forwarded call operands don't get updated like the |
| 173 | // forwarded call operands or the non-call operands. Thus they need to be |
| 174 | // handled separately. This is where we handle them. |
| 175 | |
| 176 | // This marks values of type (1.c) liveness as "live". A non-forwarded |
| 177 | // call operand is live. |
| 178 | Liveness *operandLiveness = getLatticeElement(value: operand.get()); |
| 179 | LDBG() << "Marking call operand live: " << operand.get(); |
| 180 | propagateIfChanged(state: operandLiveness, changed: operandLiveness->markLive()); |
| 181 | } |
| 182 | |
| 183 | void LivenessAnalysis::visitNonControlFlowArguments( |
| 184 | RegionSuccessor &successor, ArrayRef<BlockArgument> arguments) { |
| 185 | assert(successor.isRegion() && "expected a region successor" ); |
| 186 | Operation *parentOp = successor.getSuccessor()->getParentOp(); |
| 187 | LDBG() << "visitNonControlFlowArguments visit the region: #" |
| 188 | << successor.getSuccessor()->getRegionNumber() << " of " |
| 189 | << OpWithFlags(parentOp, OpPrintingFlags().skipRegions()); |
| 190 | auto valuesToLattices = [&](Value value) { return getLatticeElement(value); }; |
| 191 | SmallVector<Liveness *> argumentLattices = |
| 192 | llvm::map_to_vector(C&: arguments, F&: valuesToLattices); |
| 193 | SmallVector<Liveness *> parentResultLattices = |
| 194 | llvm::map_to_vector(C: parentOp->getResults(), F&: valuesToLattices); |
| 195 | |
| 196 | for (Liveness *resultLattice : parentResultLattices) { |
| 197 | if (resultLattice->isLive) { |
| 198 | for (Liveness *argumentLattice : argumentLattices) { |
| 199 | LDBG() << "make lattice: " << argumentLattice << " live" ; |
| 200 | propagateIfChanged(state: argumentLattice, changed: argumentLattice->markLive()); |
| 201 | } |
| 202 | return; |
| 203 | } |
| 204 | } |
| 205 | (void)visitOperation(op: parentOp, operands: argumentLattices, results: parentResultLattices); |
| 206 | } |
| 207 | |
| 208 | void LivenessAnalysis::setToExitState(Liveness *lattice) { |
| 209 | LDBG() << "setToExitState for lattice: " << lattice; |
| 210 | if (lattice->isLive) { |
| 211 | LDBG() << "Lattice already live, nothing to do" ; |
| 212 | return; |
| 213 | } |
| 214 | // This marks values of type (2) liveness as "live". |
| 215 | LDBG() << "Marking lattice live due to exit state" ; |
| 216 | (void)lattice->markLive(); |
| 217 | propagateIfChanged(state: lattice, changed: ChangeResult::Change); |
| 218 | } |
| 219 | |
| 220 | //===----------------------------------------------------------------------===// |
| 221 | // RunLivenessAnalysis |
| 222 | //===----------------------------------------------------------------------===// |
| 223 | |
| 224 | RunLivenessAnalysis::RunLivenessAnalysis(Operation *op) { |
| 225 | LDBG() << "Constructing RunLivenessAnalysis for op: " << op->getName(); |
| 226 | SymbolTableCollection symbolTable; |
| 227 | |
| 228 | loadBaselineAnalyses(solver); |
| 229 | solver.load<LivenessAnalysis>(args&: symbolTable); |
| 230 | LDBG() << "Initializing and running solver" ; |
| 231 | (void)solver.initializeAndRun(top: op); |
| 232 | LDBG() << "RunLivenessAnalysis initialized for op: " << op->getName() |
| 233 | << " check on unreachable code now:" ; |
| 234 | // The framework doesn't visit operations in dead blocks, so we need to |
| 235 | // explicitly mark them as dead. |
| 236 | op->walk(callback: [&](Operation *op) { |
| 237 | for (auto result : llvm::enumerate(First: op->getResults())) { |
| 238 | if (getLiveness(val: result.value())) |
| 239 | continue; |
| 240 | LDBG() << "Result: " << result.index() << " of " |
| 241 | << OpWithFlags(op, OpPrintingFlags().skipRegions()) |
| 242 | << " has no liveness info (unreachable), mark dead" ; |
| 243 | solver.getOrCreateState<Liveness>(anchor: result.value()); |
| 244 | } |
| 245 | for (auto ®ion : op->getRegions()) { |
| 246 | for (auto &block : region) { |
| 247 | for (auto blockArg : llvm::enumerate(First: block.getArguments())) { |
| 248 | if (getLiveness(val: blockArg.value())) |
| 249 | continue; |
| 250 | LDBG() << "Block argument: " << blockArg.index() << " of " |
| 251 | << OpWithFlags(op, OpPrintingFlags().skipRegions()) |
| 252 | << " has no liveness info, mark dead" ; |
| 253 | solver.getOrCreateState<Liveness>(anchor: blockArg.value()); |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | }); |
| 258 | } |
| 259 | |
| 260 | const Liveness *RunLivenessAnalysis::getLiveness(Value val) { |
| 261 | return solver.lookupState<Liveness>(anchor: val); |
| 262 | } |
| 263 | |