361 lines · cpp
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-exception6//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 25using namespace mlir;26using namespace mlir::dataflow;27 28//===----------------------------------------------------------------------===//29// Liveness30//===----------------------------------------------------------------------===//31 32void Liveness::print(raw_ostream &os) const {33 os << (isLive ? "live" : "not live");34}35 36ChangeResult Liveness::markLive() {37 bool wasLive = isLive;38 isLive = true;39 return wasLive ? ChangeResult::NoChange : ChangeResult::Change;40}41 42ChangeResult 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// LivenessAnalysis49//===----------------------------------------------------------------------===//50 51/// For every value, liveness analysis determines whether or not it is "live".52///53/// A value is considered "live" iff it:54/// (1) has memory effects OR55/// (2) is returned by a public function OR56/// (3) is used to compute a value of type (1) or (2) OR57/// (4) is returned by a return-like op whose parent isn't a callable58/// nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...)59/// These ops have their own semantics, so we conservatively mark the60/// the yield value as live.61/// It is also to be noted that a value could be of multiple types (1/2/3) at62/// the same time.63///64/// A value "has memory effects" iff it:65/// (1.a) is an operand of an op with memory effects OR66/// (1.b) is a non-forwarded branch operand and its branch op could take the67/// control to a block that has an op with memory effects OR68/// (1.c) is a non-forwarded branch operand and its branch op could result69/// in different live result OR70/// (1.d) is a non-forwarded call operand.71///72/// A value `A` is said to be "used to compute" value `B` iff `B` cannot be73/// computed in the absence of `A`. Thus, in this implementation, we say that74/// value `A` is used to compute value `B` iff:75/// (3.a) `B` is a result of an op with operand `A` OR76/// (3.b) `A` is used to compute some value `C` and `C` is used to compute77/// `B`.78 79LogicalResult80LivenessAnalysis::visitOperation(Operation *op, ArrayRef<Liveness *> operands,81 ArrayRef<const Liveness *> results) {82 LDBG() << "[visitOperation] Enter: "83 << OpWithFlags(op, OpPrintingFlags().skipRegions());84 // This marks values of type (1.a) and (4) liveness as "live".85 if (!isMemoryEffectFree(op) || op->hasTrait<OpTrait::ReturnLike>()) {86 LDBG() << "[visitOperation] Operation has memory effects or is "87 "return-like, marking operands live";88 for (auto *operand : operands) {89 LDBG() << " [visitOperation] Marking operand live: " << operand << " ("90 << operand->isLive << ")";91 propagateIfChanged(operand, operand->markLive());92 }93 }94 95 // This marks values of type (3) liveness as "live".96 bool foundLiveResult = false;97 for (const Liveness *r : results) {98 if (r->isLive && !foundLiveResult) {99 LDBG() << "[visitOperation] Found live result, "100 "meeting all operands with result: "101 << r;102 // It is assumed that each operand is used to compute each result of an103 // op. Thus, if at least one result is live, each operand is live.104 for (Liveness *operand : operands) {105 LDBG() << " [visitOperation] Meeting operand: " << operand106 << " with result: " << r;107 meet(operand, *r);108 }109 foundLiveResult = true;110 }111 LDBG() << "[visitOperation] Adding dependency for result: " << r112 << " after op: " << OpWithFlags(op, OpPrintingFlags().skipRegions());113 addDependency(const_cast<Liveness *>(r), getProgramPointAfter(op));114 }115 return success();116}117 118void LivenessAnalysis::visitBranchOperand(OpOperand &operand) {119 Operation *op = operand.getOwner();120 LDBG() << "Visiting branch operand: " << operand.get()121 << " in op: " << OpWithFlags(op, OpPrintingFlags().skipRegions());122 // We know (at the moment) and assume (for the future) that `operand` is a123 // non-forwarded branch operand of a `RegionBranchOpInterface`,124 // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op.125 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||126 isa<RegionBranchTerminatorOpInterface>(op)) &&127 "expected the op to be `RegionBranchOpInterface`, "128 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");129 130 // The lattices of the non-forwarded branch operands don't get updated like131 // the forwarded branch operands or the non-branch operands. Thus they need132 // to be handled separately. This is where we handle them.133 134 // This marks values of type (1.b/1.c) liveness as "live". A non-forwarded135 // branch operand will be live if a block where its op could take the control136 // has an op with memory effects or could result in different results.137 // Populating such blocks in `blocks`.138 bool mayLive = false;139 SmallVector<Block *, 4> blocks;140 SmallVector<BlockArgument> argumentNotOperand;141 if (auto regionBranchOp = dyn_cast<RegionBranchOpInterface>(op)) {142 if (op->getNumResults() != 0) {143 // This mark value of type 1.c liveness as may live, because the region144 // branch operation has a return value, and the non-forwarded operand can145 // determine the region to jump to, it can thereby control the result of146 // the region branch operation.147 // Therefore, if the result value is live, we conservatively consider the148 // non-forwarded operand of the region branch operation with result may149 // live and record all result.150 for (auto [resultIndex, result] : llvm::enumerate(op->getResults())) {151 if (getLatticeElement(result)->isLive) {152 mayLive = true;153 LDBG() << "[visitBranchOperand] Non-forwarded branch operand may be "154 "live due to live result #"155 << resultIndex << ": "156 << OpWithFlags(op, OpPrintingFlags().skipRegions());157 break;158 }159 }160 } else {161 // When the op is a `RegionBranchOpInterface`, like an `scf.for` or an162 // `scf.index_switch` op, its branch operand controls the flow into this163 // op's regions.164 for (Region ®ion : op->getRegions()) {165 for (Block &block : region)166 blocks.push_back(&block);167 }168 }169 170 // In the block of the successor block argument of RegionBranchOpInterface,171 // there may be arguments of RegionBranchOpInterface, such as the IV of172 // scf.forOp. Explicitly set this argument to live.173 for (Region ®ion : op->getRegions()) {174 SmallVector<RegionSuccessor> successors;175 regionBranchOp.getSuccessorRegions(region, successors);176 for (RegionSuccessor successor : successors) {177 if (successor.isParent())178 continue;179 auto arguments = successor.getSuccessor()->getArguments();180 ValueRange regionInputs = successor.getSuccessorInputs();181 for (auto argument : arguments) {182 if (llvm::find(regionInputs, argument) == regionInputs.end()) {183 argumentNotOperand.push_back(argument);184 }185 }186 }187 }188 } else if (isa<BranchOpInterface>(op)) {189 // We cannot track all successor blocks of the branch operation(More190 // specifically, it's the successor's successor). Additionally, different191 // blocks might also lead to the different block argument described in 1.c.192 // Therefore, we conservatively consider the non-forwarded operand of the193 // branch operation may live.194 mayLive = true;195 LDBG() << "[visitBranchOperand] Non-forwarded branch operand may "196 "be live due to branch op interface";197 } else {198 Operation *parentOp = op->getParentOp();199 assert(isa<RegionBranchOpInterface>(parentOp) &&200 "expected parent op to implement `RegionBranchOpInterface`");201 if (parentOp->getNumResults() != 0) {202 // This mark value of type 1.c liveness as may live, because the region203 // branch operation has a return value, and the non-forwarded operand can204 // determine the region to jump to, it can thereby control the result of205 // the region branch operation.206 // Therefore, if the result value is live, we conservatively consider the207 // non-forwarded operand of the region branch operation with result may208 // live and record all result.209 for (Value result : parentOp->getResults()) {210 if (getLatticeElement(result)->isLive) {211 mayLive = true;212 LDBG() << "[visitBranchOperand] Non-forwarded branch "213 "operand may be live due to parent live result: "214 << result;215 break;216 }217 }218 } else {219 // When the op is a `RegionBranchTerminatorOpInterface`, like an220 // `scf.condition` op or return-like, like an `scf.yield` op, its branch221 // operand controls the flow into this op's parent's (which is a222 // `RegionBranchOpInterface`'s) regions.223 for (Region ®ion : parentOp->getRegions()) {224 for (Block &block : region)225 blocks.push_back(&block);226 }227 }228 }229 for (Block *block : blocks) {230 if (mayLive)231 break;232 for (Operation &nestedOp : *block) {233 if (!isMemoryEffectFree(&nestedOp)) {234 mayLive = true;235 LDBG() << "Non-forwarded branch operand may be "236 "live due to memory effect in block: "237 << block;238 break;239 }240 }241 }242 243 if (mayLive) {244 Liveness *operandLiveness = getLatticeElement(operand.get());245 LDBG() << "Marking branch operand live: " << operand.get();246 propagateIfChanged(operandLiveness, operandLiveness->markLive());247 for (BlockArgument argument : argumentNotOperand) {248 Liveness *argumentLiveness = getLatticeElement(argument);249 LDBG() << "Marking RegionBranchOp's argument live: " << argument;250 // TODO: this is overly conservative: we should be able to eliminate251 // unused values in a RegionBranchOpInterface operation but that may252 // requires removing operation results which is beyond current253 // capabilities of this pass right now.254 propagateIfChanged(argumentLiveness, argumentLiveness->markLive());255 }256 }257 258 // Now that we have checked for memory-effecting ops in the blocks of concern,259 // we will simply visit the op with this non-forwarded operand to potentially260 // mark it "live" due to type (1.a/3) liveness.261 SmallVector<Liveness *, 4> operandLiveness;262 operandLiveness.push_back(getLatticeElement(operand.get()));263 for (BlockArgument argument : argumentNotOperand)264 operandLiveness.push_back(getLatticeElement(argument));265 SmallVector<const Liveness *, 4> resultsLiveness;266 for (const Value result : op->getResults())267 resultsLiveness.push_back(getLatticeElement(result));268 LDBG() << "Visiting operation for non-forwarded branch operand: "269 << OpWithFlags(op, OpPrintingFlags().skipRegions());270 (void)visitOperation(op, operandLiveness, resultsLiveness);271 272 // We also visit the parent op with the parent's results and this operand if273 // `op` is a `RegionBranchTerminatorOpInterface` because its non-forwarded274 // operand depends on not only its memory effects/results but also on those of275 // its parent's.276 if (!isa<RegionBranchTerminatorOpInterface>(op))277 return;278 Operation *parentOp = op->getParentOp();279 SmallVector<const Liveness *, 4> parentResultsLiveness;280 for (const Value parentResult : parentOp->getResults())281 parentResultsLiveness.push_back(getLatticeElement(parentResult));282 LDBG() << "Visiting parent operation for non-forwarded branch operand: "283 << *parentOp;284 (void)visitOperation(parentOp, operandLiveness, parentResultsLiveness);285}286 287void LivenessAnalysis::visitCallOperand(OpOperand &operand) {288 LDBG() << "Visiting call operand: " << operand.get()289 << " in op: " << *operand.getOwner();290 // We know (at the moment) and assume (for the future) that `operand` is a291 // non-forwarded call operand of an op implementing `CallOpInterface`.292 assert(isa<CallOpInterface>(operand.getOwner()) &&293 "expected the op to implement `CallOpInterface`");294 295 // The lattices of the non-forwarded call operands don't get updated like the296 // forwarded call operands or the non-call operands. Thus they need to be297 // handled separately. This is where we handle them.298 299 // This marks values of type (1.c) liveness as "live". A non-forwarded300 // call operand is live.301 Liveness *operandLiveness = getLatticeElement(operand.get());302 LDBG() << "Marking call operand live: " << operand.get();303 propagateIfChanged(operandLiveness, operandLiveness->markLive());304}305 306void LivenessAnalysis::setToExitState(Liveness *lattice) {307 LDBG() << "setToExitState for lattice: " << lattice;308 if (lattice->isLive) {309 LDBG() << "Lattice already live, nothing to do";310 return;311 }312 // This marks values of type (2) liveness as "live".313 LDBG() << "Marking lattice live due to exit state";314 (void)lattice->markLive();315 propagateIfChanged(lattice, ChangeResult::Change);316}317 318//===----------------------------------------------------------------------===//319// RunLivenessAnalysis320//===----------------------------------------------------------------------===//321 322RunLivenessAnalysis::RunLivenessAnalysis(Operation *op) {323 LDBG() << "Constructing RunLivenessAnalysis for op: " << op->getName();324 SymbolTableCollection symbolTable;325 326 loadBaselineAnalyses(solver);327 solver.load<LivenessAnalysis>(symbolTable);328 LDBG() << "Initializing and running solver";329 (void)solver.initializeAndRun(op);330 LDBG() << "RunLivenessAnalysis initialized for op: " << op->getName()331 << " check on unreachable code now:";332 // The framework doesn't visit operations in dead blocks, so we need to333 // explicitly mark them as dead.334 op->walk([&](Operation *op) {335 for (auto result : llvm::enumerate(op->getResults())) {336 if (getLiveness(result.value()))337 continue;338 LDBG() << "Result: " << result.index() << " of "339 << OpWithFlags(op, OpPrintingFlags().skipRegions())340 << " has no liveness info (unreachable), mark dead";341 solver.getOrCreateState<Liveness>(result.value());342 }343 for (auto ®ion : op->getRegions()) {344 for (auto &block : region) {345 for (auto blockArg : llvm::enumerate(block.getArguments())) {346 if (getLiveness(blockArg.value()))347 continue;348 LDBG() << "Block argument: " << blockArg.index() << " of "349 << OpWithFlags(op, OpPrintingFlags().skipRegions())350 << " has no liveness info, mark dead";351 solver.getOrCreateState<Liveness>(blockArg.value());352 }353 }354 }355 });356}357 358const Liveness *RunLivenessAnalysis::getLiveness(Value val) {359 return solver.lookupState<Liveness>(val);360}361