From 17de7ed556ad8df3d2dcaa9322a792fc70243194 Mon Sep 17 00:00:00 2001
From: Rahul Joshi <jurahul@google.com>
Date: Fri, 23 Jul 2021 13:12:31 -0700
Subject: [PATCH] [MLIR][NFC] Minor cleanup in liveness.

- 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.

Differential Revision: https://reviews.llvm.org/D106702
---
 mlir/include/mlir/Analysis/Liveness.h |  7 +++----
 mlir/lib/Analysis/Liveness.cpp        | 31 ++++++++++++-------------------
 2 files changed, 15 insertions(+), 23 deletions(-)

diff --git a/mlir/include/mlir/Analysis/Liveness.h b/mlir/include/mlir/Analysis/Liveness.h
index 3bd298a..8c32a0f 100644
--- a/mlir/include/mlir/Analysis/Liveness.h
+++ b/mlir/include/mlir/Analysis/Liveness.h
@@ -43,7 +43,7 @@ class Value;
 ///   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 *>;
@@ -74,9 +74,8 @@ public:
   /// 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;
diff --git a/mlir/lib/Analysis/Liveness.cpp b/mlir/lib/Analysis/Liveness.cpp
index 1c26db1..3906167 100644
--- a/mlir/lib/Analysis/Liveness.cpp
+++ b/mlir/lib/Analysis/Liveness.cpp
@@ -63,21 +63,16 @@ struct BlockInfoBuilder {
       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);
+      for (Value operand : op->getOperands())
+        useValues.insert(operand);
     });
-
-    // 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);
-      }
-    });
+    llvm::set_subtract(useValues, defValues);
   }
 
   /// Updates live-in information of the current block. To do so it uses the
@@ -94,16 +89,16 @@ struct BlockInfoBuilder {
     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);
     }
   }
@@ -138,7 +133,7 @@ static void buildBlockMapping(Operation *operation,
       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];
@@ -162,7 +157,6 @@ 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);
@@ -242,9 +236,8 @@ 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);
 
-- 
2.7.4