[MLIR][NFC] Minor cleanup in liveness.

[jurahul]

Summary

• Rename isLastUse to isDeadAfter to reflect what the function does.
• Avoid a second walk over all operations in BlockInfoBuilder constructor.
• use std::move() to save the new in set.

[rriddle]

mlir/include/mlir/Analysis/Liveness.h

78

You'll also need to update usages in comments.

mlir/lib/Analysis/Liveness.cpp

69

This changes the behavior of nested regions with multiple blocks, though I don't think nested operations should necessarily be handled by all ancestor blocks.

[jurahul]

mlir/lib/Analysis/Liveness.cpp

69

Not sure how it changes the behavior: it looks like all defs in all nested operations are added to defValues and all uses in all nested operations (except the ones in defValues) and that's the behavior of the new code. Note that useValues is empty before this code.

[jurahul]

Update usage in comment

[rriddle]

mlir/lib/Analysis/Liveness.cpp

69

Right right, misread the comment there.

mlir/include/mlir/Analysis/Liveness.h

 /// computes liveness information for every value and block that are
 /// included in the mentioned regions. It relies on a fixpoint iteration
 /// to compute all live-in and live-out values of all included blocks.
 /// Sample usage:
 ///   Liveness liveness(topLevelOp);
 ///   auto &allInValues = liveness.getLiveIn(block);
 ///   auto &allOutValues = liveness.getLiveOut(block);
 ///   auto allOperationsInWhichValueIsLive = liveness.resolveLiveness(value);
-///   bool lastUse = liveness.isLastUse(value, operation);
+///   bool isDeafAfter = liveness.isDeadAfter(value, operation);
 class Liveness {
 public:
   using OperationListT = std::vector<Operation *>;
   using BlockMapT = DenseMap<Block *, LivenessBlockInfo>;
   using ValueSetT = SmallPtrSet<Value, 16>;
 
 public:
   /// Creates a new Liveness analysis that computes liveness
public:
   const LivenessBlockInfo *getLiveness(Block *block) const;
 
   /// Returns a reference to a set containing live-in values (unordered).
   const ValueSetT &getLiveIn(Block *block) const;
 
   /// Returns a reference to a set containing live-out values (unordered).
   const ValueSetT &getLiveOut(Block *block) const;
 
-  /// Returns true if the given operation represent the last use of the
-  /// given value.
-  bool isLastUse(Value value, Operation *operation) const;
+  /// Returns true if `value` is not live after `operation`.
+  bool isDeadAfter(Value value, Operation *operation) const;
 
   /// Dumps the liveness information in a human readable format.
   void dump() const;
 
   /// Dumps the liveness information to the given stream.
   void print(raw_ostream &os) const;
 
 private:

mlir/lib/Analysis/Liveness.cpp

for (BlockArgument argument : block->getArguments()) {
       gatherOutValues(argument);
     }
 
     // Gather out values of all operations in the current block.
     for (Operation &operation : *block)
       for (Value result : operation.getResults())
         gatherOutValues(result);
 
-    // Mark all nested operation results as defined.
+    // Mark all nested operation results as defined, and nested operation
+    // operands as used. All defined value will be removed from the used set
+    // at the end.
     block->walk([&](Operation *op) {
       for (Value result : op->getResults())
         defValues.insert(result);
-    });
-
-    // Check all operations for used operands.
-    block->walk([&](Operation *op) {
-      for (Value operand : op->getOperands()) {
-        // If the operand is already defined in the scope of this
-        // block, we can skip the value in the use set.
-        if (!defValues.count(operand))
-          useValues.insert(operand);
-      }
+      for (Value operand : op->getOperands())
     });
+    llvm::set_subtract(useValues, defValues);
   }
 
   /// Updates live-in information of the current block. To do so it uses the
   /// default liveness-computation formula: newIn = use union out \ def. The
   /// methods returns true, if the set has changed (newIn != in), false
   /// otherwise.
   bool updateLiveIn() {
     ValueSetT newIn = useValues;
     llvm::set_union(newIn, outValues);
     llvm::set_subtract(newIn, defValues);
 
     // It is sufficient to check the set sizes (instead of their contents) since
     // the live-in set can only grow monotonically during all update operations.
     if (newIn.size() == inValues.size())
       return false;
 
-    inValues = newIn;
+    inValues = std::move(newIn);
     return true;
   }
 
   /// Updates live-out information of the current block. It iterates over all
   /// successors and unifies their live-in values with the current live-out
   /// values.
-  template <typename SourceT> void updateLiveOut(SourceT &source) {
+  void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {
     for (Block *succ : block->getSuccessors()) {
-      BlockInfoBuilder &builder = source[succ];
+      const BlockInfoBuilder &builder = builders.find(succ)->second;
       llvm::set_union(outValues, builder.inValues);
     }
   }
 
   /// The current block.
   Block *block;
 
   /// The set of all live in values.
static void buildBlockMapping(Operation *operation,
   operation->walk<WalkOrder::PreOrder>([&](Block *block) {
     BlockInfoBuilder &builder =
         builders.try_emplace(block, block).first->second;
 
     if (builder.updateLiveIn())
       toProcess.insert(block->pred_begin(), block->pred_end());
   });
 
-  // Propagate the in and out-value sets (fixpoint iteration)
+  // Propagate the in and out-value sets (fixpoint iteration).
   while (!toProcess.empty()) {
     Block *current = toProcess.pop_back_val();
     BlockInfoBuilder &builder = builders[current];
 
     // Update the current out values.
     builder.updateLiveOut(builders);
 
     // Compute (potentially) updated live in values.
     if (builder.updateLiveIn())
       toProcess.insert(current->pred_begin(), current->pred_end());
   }
 }
 
 //===----------------------------------------------------------------------===//
 // Liveness
 //===----------------------------------------------------------------------===//
 
 /// Creates a new Liveness analysis that computes liveness information for all
 /// associated regions.
 Liveness::Liveness(Operation *op) : operation(op) { build(); }
 
 /// Initializes the internal mappings.
 void Liveness::build() {
-
   // Build internal block mapping.
   DenseMap<Block *, BlockInfoBuilder> builders;
   buildBlockMapping(operation, builders);
 
   // Store internal block data.
   for (auto &entry : builders) {
     BlockInfoBuilder &builder = entry.second;
     LivenessBlockInfo &info = blockMapping[entry.first];
const Liveness::ValueSetT &Liveness::getLiveIn(Block *block) const {
   return getLiveness(block)->in();
 }
 
 /// Returns a reference to a set containing live-out values.
 const Liveness::ValueSetT &Liveness::getLiveOut(Block *block) const {
   return getLiveness(block)->out();
 }
 
-/// Returns true if the given operation represent the last use of the given
-/// value.
-bool Liveness::isLastUse(Value value, Operation *operation) const {
+/// Returns true if `value` is not live after `operation`.
+bool Liveness::isDeadAfter(Value value, Operation *operation) const {
   Block *block = operation->getBlock();
   const LivenessBlockInfo *blockInfo = getLiveness(block);
 
   // The given value escapes the associated block.
   if (blockInfo->isLiveOut(value))
     return false;
 
   Operation *endOperation = blockInfo->getEndOperation(value, operation);