446 lines · cpp
1//===- Liveness.cpp - Liveness analysis for MLIR --------------------------===//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// Implementation of the liveness analysis.10//11//===----------------------------------------------------------------------===//12 13#include "mlir/Analysis/Liveness.h"14#include "mlir/IR/Block.h"15#include "mlir/IR/Operation.h"16#include "mlir/IR/Region.h"17#include "mlir/IR/Value.h"18#include "llvm/ADT/STLExtras.h"19#include "llvm/ADT/SetOperations.h"20#include "llvm/ADT/SetVector.h"21#include "llvm/Support/raw_ostream.h"22 23using namespace mlir;24 25namespace {26/// Builds and holds block information during the construction phase.27struct BlockInfoBuilder {28 using ValueSetT = Liveness::ValueSetT;29 30 /// Constructs an empty block builder.31 BlockInfoBuilder() = default;32 33 /// Fills the block builder with initial liveness information.34 BlockInfoBuilder(Block *block) : block(block) {35 auto gatherOutValues = [&](Value value) {36 // Check whether this value will be in the outValues set (its uses escape37 // this block). Due to the SSA properties of the program, the uses must38 // occur after the definition. Therefore, we do not have to check39 // additional conditions to detect an escaping value.40 for (Operation *useOp : value.getUsers()) {41 Block *ownerBlock = useOp->getBlock();42 // Find an owner block in the current region. Note that a value does not43 // escape this block if it is used in a nested region.44 ownerBlock = block->getParent()->findAncestorBlockInRegion(*ownerBlock);45 assert(ownerBlock && "Use leaves the current parent region");46 if (ownerBlock != block) {47 outValues.insert(value);48 break;49 }50 }51 };52 53 // Mark all block arguments (phis) as defined.54 for (BlockArgument argument : block->getArguments()) {55 // Insert value into the set of defined values.56 defValues.insert(argument);57 58 // Gather all out values of all arguments in the current block.59 gatherOutValues(argument);60 }61 62 // Gather out values of all operations in the current block.63 for (Operation &operation : *block)64 for (Value result : operation.getResults())65 gatherOutValues(result);66 67 // Mark all nested operation results as defined, and nested operation68 // operands as used. All defined value will be removed from the used set69 // at the end.70 block->walk([&](Operation *op) {71 defValues.insert_range(op->getResults());72 useValues.insert_range(op->getOperands());73 for (Region ®ion : op->getRegions())74 for (Block &child : region.getBlocks())75 defValues.insert_range(child.getArguments());76 });77 llvm::set_subtract(useValues, defValues);78 }79 80 /// Updates live-in information of the current block. To do so it uses the81 /// default liveness-computation formula: newIn = use union out \ def. The82 /// methods returns true, if the set has changed (newIn != in), false83 /// otherwise.84 bool updateLiveIn() {85 ValueSetT newIn = useValues;86 llvm::set_union(newIn, outValues);87 llvm::set_subtract(newIn, defValues);88 89 // It is sufficient to check the set sizes (instead of their contents) since90 // the live-in set can only grow monotonically during all update operations.91 if (newIn.size() == inValues.size())92 return false;93 94 inValues = std::move(newIn);95 return true;96 }97 98 /// Updates live-out information of the current block. It iterates over all99 /// successors and unifies their live-in values with the current live-out100 /// values.101 void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {102 for (Block *succ : block->getSuccessors()) {103 const BlockInfoBuilder &builder = builders.find(succ)->second;104 llvm::set_union(outValues, builder.inValues);105 }106 }107 108 /// The current block.109 Block *block{nullptr};110 111 /// The set of all live in values.112 ValueSetT inValues;113 114 /// The set of all live out values.115 ValueSetT outValues;116 117 /// The set of all defined values.118 ValueSetT defValues;119 120 /// The set of all used values.121 ValueSetT useValues;122};123} // namespace124 125/// Builds the internal liveness block mapping.126static void buildBlockMapping(Operation *operation,127 DenseMap<Block *, BlockInfoBuilder> &builders) {128 SetVector<Block *> toProcess;129 130 operation->walk<WalkOrder::PreOrder>([&](Block *block) {131 BlockInfoBuilder &builder =132 builders.try_emplace(block, block).first->second;133 134 if (builder.updateLiveIn())135 toProcess.insert(block->pred_begin(), block->pred_end());136 });137 138 // Propagate the in and out-value sets (fixpoint iteration).139 while (!toProcess.empty()) {140 Block *current = toProcess.pop_back_val();141 BlockInfoBuilder &builder = builders[current];142 143 // Update the current out values.144 builder.updateLiveOut(builders);145 146 // Compute (potentially) updated live in values.147 if (builder.updateLiveIn())148 toProcess.insert(current->pred_begin(), current->pred_end());149 }150}151 152//===----------------------------------------------------------------------===//153// Liveness154//===----------------------------------------------------------------------===//155 156/// Creates a new Liveness analysis that computes liveness information for all157/// associated regions.158Liveness::Liveness(Operation *op) : operation(op) { build(); }159 160/// Initializes the internal mappings.161void Liveness::build() {162 // Build internal block mapping.163 DenseMap<Block *, BlockInfoBuilder> builders;164 buildBlockMapping(operation, builders);165 166 // Store internal block data.167 for (auto &entry : builders) {168 BlockInfoBuilder &builder = entry.second;169 LivenessBlockInfo &info = blockMapping[entry.first];170 171 info.block = builder.block;172 info.inValues = std::move(builder.inValues);173 info.outValues = std::move(builder.outValues);174 }175}176 177/// Gets liveness info (if any) for the given value.178Liveness::OperationListT Liveness::resolveLiveness(Value value) const {179 OperationListT result;180 SmallPtrSet<Block *, 32> visited;181 SmallVector<Block *, 8> toProcess;182 183 // Start with the defining block184 Block *currentBlock;185 if (Operation *defOp = value.getDefiningOp())186 currentBlock = defOp->getBlock();187 else188 currentBlock = cast<BlockArgument>(value).getOwner();189 toProcess.push_back(currentBlock);190 visited.insert(currentBlock);191 192 // Start with all associated blocks193 for (OpOperand &use : value.getUses()) {194 Block *useBlock = use.getOwner()->getBlock();195 if (visited.insert(useBlock).second)196 toProcess.push_back(useBlock);197 }198 199 while (!toProcess.empty()) {200 // Get block and block liveness information.201 Block *block = toProcess.pop_back_val();202 const LivenessBlockInfo *blockInfo = getLiveness(block);203 204 // Note that start and end will be in the same block.205 Operation *start = blockInfo->getStartOperation(value);206 Operation *end = blockInfo->getEndOperation(value, start);207 208 result.push_back(start);209 while (start != end) {210 start = start->getNextNode();211 result.push_back(start);212 }213 214 for (Block *successor : block->getSuccessors()) {215 if (getLiveness(successor)->isLiveIn(value) &&216 visited.insert(successor).second)217 toProcess.push_back(successor);218 }219 }220 221 return result;222}223 224/// Gets liveness info (if any) for the block.225const LivenessBlockInfo *Liveness::getLiveness(Block *block) const {226 auto it = blockMapping.find(block);227 return it == blockMapping.end() ? nullptr : &it->second;228}229 230/// Returns a reference to a set containing live-in values.231const Liveness::ValueSetT &Liveness::getLiveIn(Block *block) const {232 return getLiveness(block)->in();233}234 235/// Returns a reference to a set containing live-out values.236const Liveness::ValueSetT &Liveness::getLiveOut(Block *block) const {237 return getLiveness(block)->out();238}239 240/// Returns true if `value` is not live after `operation`.241bool Liveness::isDeadAfter(Value value, Operation *operation) const {242 Block *block = operation->getBlock();243 const LivenessBlockInfo *blockInfo = getLiveness(block);244 245 // The given value escapes the associated block.246 if (blockInfo->isLiveOut(value))247 return false;248 249 Operation *endOperation = blockInfo->getEndOperation(value, operation);250 // If the operation is a real user of `value` the first check is sufficient.251 // If not, we will have to test whether the end operation is executed before252 // the given operation in the block.253 return endOperation == operation || endOperation->isBeforeInBlock(operation);254}255 256/// Dumps the liveness information in a human readable format.257void Liveness::dump() const { print(llvm::errs()); }258 259/// Dumps the liveness information to the given stream.260void Liveness::print(raw_ostream &os) const {261 os << "// ---- Liveness -----\n";262 263 // Builds unique block/value mappings for testing purposes.264 DenseMap<Block *, size_t> blockIds;265 DenseMap<Operation *, size_t> operationIds;266 DenseMap<Value, size_t> valueIds;267 operation->walk<WalkOrder::PreOrder>([&](Block *block) {268 blockIds.insert({block, blockIds.size()});269 for (BlockArgument argument : block->getArguments())270 valueIds.insert({argument, valueIds.size()});271 for (Operation &operation : *block) {272 operationIds.insert({&operation, operationIds.size()});273 for (Value result : operation.getResults())274 valueIds.insert({result, valueIds.size()});275 }276 });277 278 // Local printing helpers279 auto printValueRef = [&](Value value) {280 if (value.getDefiningOp())281 os << "val_" << valueIds[value];282 else {283 auto blockArg = cast<BlockArgument>(value);284 os << "arg" << blockArg.getArgNumber() << "@"285 << blockIds[blockArg.getOwner()];286 }287 os << " ";288 };289 290 auto printValueRefs = [&](const ValueSetT &values) {291 std::vector<Value> orderedValues(values.begin(), values.end());292 llvm::sort(orderedValues, [&](Value left, Value right) {293 return valueIds[left] < valueIds[right];294 });295 for (Value value : orderedValues)296 printValueRef(value);297 };298 299 // Dump information about in and out values.300 operation->walk<WalkOrder::PreOrder>([&](Block *block) {301 os << "// - Block: " << blockIds[block] << "\n";302 const auto *liveness = getLiveness(block);303 os << "// --- LiveIn: ";304 printValueRefs(liveness->inValues);305 os << "\n// --- LiveOut: ";306 printValueRefs(liveness->outValues);307 os << "\n";308 309 // Print liveness intervals.310 os << "// --- BeginLivenessIntervals";311 for (Operation &op : *block) {312 if (op.getNumResults() < 1)313 continue;314 os << "\n";315 for (Value result : op.getResults()) {316 os << "// ";317 printValueRef(result);318 os << ":";319 auto liveOperations = resolveLiveness(result);320 llvm::sort(liveOperations, [&](Operation *left, Operation *right) {321 return operationIds[left] < operationIds[right];322 });323 for (Operation *operation : liveOperations) {324 os << "\n// ";325 operation->print(os);326 }327 }328 }329 os << "\n// --- EndLivenessIntervals\n";330 331 // Print currently live values.332 os << "// --- BeginCurrentlyLive\n";333 for (Operation &op : *block) {334 auto currentlyLive = liveness->currentlyLiveValues(&op);335 if (currentlyLive.empty())336 continue;337 os << "// ";338 op.print(os);339 os << " [";340 printValueRefs(currentlyLive);341 os << "\b]\n";342 }343 os << "// --- EndCurrentlyLive\n";344 });345 os << "// -------------------\n";346}347 348//===----------------------------------------------------------------------===//349// LivenessBlockInfo350//===----------------------------------------------------------------------===//351 352/// Returns true if the given value is in the live-in set.353bool LivenessBlockInfo::isLiveIn(Value value) const {354 return inValues.count(value);355}356 357/// Returns true if the given value is in the live-out set.358bool LivenessBlockInfo::isLiveOut(Value value) const {359 return outValues.count(value);360}361 362/// Gets the start operation for the given value (must be referenced in this363/// block).364Operation *LivenessBlockInfo::getStartOperation(Value value) const {365 Operation *definingOp = value.getDefiningOp();366 // The given value is either live-in or is defined367 // in the scope of this block.368 if (isLiveIn(value) || !definingOp)369 return &block->front();370 return definingOp;371}372 373/// Gets the end operation for the given value using the start operation374/// provided (must be referenced in this block).375Operation *LivenessBlockInfo::getEndOperation(Value value,376 Operation *startOperation) const {377 // The given value is either dying in this block or live-out.378 if (isLiveOut(value))379 return &block->back();380 381 // Resolve the last operation (must exist by definition).382 Operation *endOperation = startOperation;383 for (Operation *useOp : value.getUsers()) {384 // Find the associated operation in the current block (if any).385 useOp = block->findAncestorOpInBlock(*useOp);386 // Check whether the use is in our block and after the current end387 // operation.388 if (useOp && endOperation->isBeforeInBlock(useOp))389 endOperation = useOp;390 }391 return endOperation;392}393 394/// Return the values that are currently live as of the given operation.395LivenessBlockInfo::ValueSetT396LivenessBlockInfo::currentlyLiveValues(Operation *op) const {397 ValueSetT liveSet;398 399 // Given a value, check which ops are within its live range. For each of400 // those ops, add the value to the set of live values as-of that op.401 auto addValueToCurrentlyLiveSets = [&](Value value) {402 // Determine the live range of this value inside this block.403 Operation *startOfLiveRange = value.getDefiningOp();404 Operation *endOfLiveRange = nullptr;405 // If it's a live in or a block argument, then the start is the beginning406 // of the block.407 if (isLiveIn(value) || isa<BlockArgument>(value))408 startOfLiveRange = &block->front();409 else410 startOfLiveRange = block->findAncestorOpInBlock(*startOfLiveRange);411 412 // If it's a live out, then the end is the back of the block.413 if (isLiveOut(value))414 endOfLiveRange = &block->back();415 416 // We must have at least a startOfLiveRange at this point. Given this, we417 // can use the existing getEndOperation to find the end of the live range.418 if (startOfLiveRange && !endOfLiveRange)419 endOfLiveRange = getEndOperation(value, startOfLiveRange);420 421 assert(endOfLiveRange && "Must have endOfLiveRange at this point!");422 // If this op is within the live range, insert the value into the set.423 if (!(op->isBeforeInBlock(startOfLiveRange) ||424 endOfLiveRange->isBeforeInBlock(op)))425 liveSet.insert(value);426 };427 428 // Handle block arguments if any.429 for (Value arg : block->getArguments())430 addValueToCurrentlyLiveSets(arg);431 432 // Handle live-ins. Between the live ins and all the op results that gives us433 // every value in the block.434 for (Value in : inValues)435 addValueToCurrentlyLiveSets(in);436 437 // Now walk the block and handle all values used in the block and values438 // defined by the block.439 for (Operation &walkOp :440 llvm::make_range(block->begin(), ++op->getIterator()))441 for (auto result : walkOp.getResults())442 addValueToCurrentlyLiveSets(result);443 444 return liveSet;445}446