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