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     });
  76     llvm::set_subtract(useValues, defValues);
  77   }
  78
  79   /// Updates live-in information of the current block. To do so it uses the
  80   /// default liveness-computation formula: newIn = use union out \ def. The
  81   /// methods returns true, if the set has changed (newIn != in), false
  82   /// otherwise.
  83   bool updateLiveIn() {
  84     ValueSetT newIn = useValues;
  85     llvm::set_union(newIn, outValues);
  86     llvm::set_subtract(newIn, defValues);
  87
  88     // It is sufficient to check the set sizes (instead of their contents) since
  89     // the live-in set can only grow monotonically during all update operations.
  90     if (newIn.size() == inValues.size())
  91       return false;
  92
  93     inValues = std::move(newIn);
  94     return true;
  95   }
  96
  97   /// Updates live-out information of the current block. It iterates over all
  98   /// successors and unifies their live-in values with the current live-out
  99   /// values.
 100   void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {
 101     for (Block *succ : block->getSuccessors()) {
 102       const BlockInfoBuilder &builder = builders.find(succ)->second;
 103       llvm::set_union(outValues, builder.inValues);
 104     }
 105   }
 106
 107   /// The current block.
 108   Block *block{nullptr};
 109
 110   /// The set of all live in values.
 111   ValueSetT inValues;
 112
 113   /// The set of all live out values.
 114   ValueSetT outValues;
 115
 116   /// The set of all defined values.
 117   ValueSetT defValues;
 118
 119   /// The set of all used values.
 120   ValueSetT useValues;
 121 };
 122 } // namespace
 123
 124 /// Builds the internal liveness block mapping.
 125 static void buildBlockMapping(Operation *operation,
 126                               DenseMap<Block *, BlockInfoBuilder> &builders) {
 127   SetVector<Block *> toProcess;
 128
 129   operation->walk<WalkOrder::PreOrder>([&](Block *block) {
 130     BlockInfoBuilder &builder =
 131         builders.try_emplace(block, block).first->second;
 132
 133     if (builder.updateLiveIn())
 134       toProcess.insert(block->pred_begin(), block->pred_end());
 135   });
 136
 137   // Propagate the in and out-value sets (fixpoint iteration).
 138   while (!toProcess.empty()) {
 139     Block *current = toProcess.pop_back_val();
 140     BlockInfoBuilder &builder = builders[current];
 141
 142     // Update the current out values.
 143     builder.updateLiveOut(builders);
 144
 145     // Compute (potentially) updated live in values.
 146     if (builder.updateLiveIn())
 147       toProcess.insert(current->pred_begin(), current->pred_end());
 148   }
 149 }
 150
 151 //===----------------------------------------------------------------------===//
 152 // Liveness
 153 //===----------------------------------------------------------------------===//
 154
 155 /// Creates a new Liveness analysis that computes liveness information for all
 156 /// associated regions.
 157 Liveness::Liveness(Operation *op) : operation(op) { build(); }
 158
 159 /// Initializes the internal mappings.
 160 void Liveness::build() {
 161   // Build internal block mapping.
 162   DenseMap<Block *, BlockInfoBuilder> builders;
 163   buildBlockMapping(operation, builders);
 164
 165   // Store internal block data.
 166   for (auto &entry : builders) {
 167     BlockInfoBuilder &builder = entry.second;
 168     LivenessBlockInfo &info = blockMapping[entry.first];
 169
 170     info.block = builder.block;
 171     info.inValues = std::move(builder.inValues);
 172     info.outValues = std::move(builder.outValues);
 173   }
 174 }
 175
 176 /// Gets liveness info (if any) for the given value.
 177 Liveness::OperationListT Liveness::resolveLiveness(Value value) const {
 178   OperationListT result;
 179   SmallPtrSet<Block *, 32> visited;
 180   SmallVector<Block *, 8> toProcess;
 181
 182   // Start with the defining block
 183   Block *currentBlock;
 184   if (Operation *defOp = value.getDefiningOp())
 185     currentBlock = defOp->getBlock();
 186   else
 187     currentBlock = value.cast<BlockArgument>().getOwner();
 188   toProcess.push_back(currentBlock);
 189   visited.insert(currentBlock);
 190
 191   // Start with all associated blocks
 192   for (OpOperand &use : value.getUses()) {
 193     Block *useBlock = use.getOwner()->getBlock();
 194     if (visited.insert(useBlock).second)
 195       toProcess.push_back(useBlock);
 196   }
 197
 198   while (!toProcess.empty()) {
 199     // Get block and block liveness information.
 200     Block *block = toProcess.back();
 201     toProcess.pop_back();
 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.
 225 const 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.
 231 const 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.
 236 const Liveness::ValueSetT &Liveness::getLiveOut(Block *block) const {
 237   return getLiveness(block)->out();
 238 }
 239
 240 /// Returns true if `value` is not live after `operation`.
 241 bool 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 before
 252   // 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.
 257 void Liveness::dump() const { print(llvm::errs()); }
 258
 259 /// Dumps the liveness information to the given stream.
 260 void 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 helpers
 279   auto printValueRef = [&](Value value) {
 280     if (value.getDefiningOp())
 281       os << "val_" << valueIds[value];
 282     else {
 283       auto blockArg = value.cast<BlockArgument>();
 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 // LivenessBlockInfo
 350 //===----------------------------------------------------------------------===//
 351
 352 /// Returns true if the given value is in the live-in set.
 353 bool 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.
 358 bool 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 this
 363 /// block).
 364 Operation *LivenessBlockInfo::getStartOperation(Value value) const {
 365   Operation *definingOp = value.getDefiningOp();
 366   // The given value is either live-in or is defined
 367   // 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 operation
 374 /// provided (must be referenced in this block).
 375 Operation *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 end
 387     // 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.
 395 LivenessBlockInfo::ValueSetT
 396 LivenessBlockInfo::currentlyLiveValues(Operation *op) const {
 397   ValueSetT liveSet;
 398
 399   // Given a value, check which ops are within its live range. For each of
 400   // 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 beginning
 406     // of the block.
 407     if (isLiveIn(value) || value.isa<BlockArgument>())
 408       startOfLiveRange = &block->front();
 409     else
 410       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, we
 417     // 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 us
 433   // 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 values
 438   // 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 }