[MLIR][Liveness] Add `currentlyLiveValues`, a way to get a set of values that are live as of a given operation.

[bzcheeseman]

Summary

This change allows the user of LivenessBlockInfo to specify an op within the block and get a set of all values that are live as of that op. Semantically it relies on having a dominance-based region that has ordered operations. For DFG regions, computing liveness statically this way doesn't really make sense, it likely needs to be done at runtime.

[bzcheeseman]

I had also considered a version of this patch that iterated the block with a set of refcounts for each value - that also works but this version felt a little closer to the way that the rest of the analysis is performed. I'm totally fine either way, happy to update the patch to use the other method.

[rriddle]

mlir/include/mlir/Analysis/Liveness.h

151

This is building a map from every operation to every value that is live over that operation? This feels extremely expensive. I'm not really sure this scales beyond simple cases.

mlir/lib/Analysis/Liveness.cpp

450

This is returning a copy of the set? I would have expected a reference, a copy is going to be expensive.

[bzcheeseman]

mlir/include/mlir/Analysis/Liveness.h

151

Yep, it is pretty expensive. The other option I can think of is to keep a simpler data structure and make the query operation do some of the computation which I'm not a huge fan of because you'd pay the cost of walking the block repeatedly - both options are bad in extreme cases I think?

mlir/lib/Analysis/Liveness.cpp

450

Good point, should be a const reference. I'll fix it.

[bzcheeseman]

mlir/lib/Analysis/Liveness.cpp

450

Actually, with the changes making this do the analysis on-demand, we no longer can keep a reference to this so we have to return it by value.

[rriddle]

mlir/lib/Analysis/Liveness.cpp

452

Why do we need this here? Can't we just have ValueSetT variable and ignore the cases we don't care about (i.e. any other op)?

461–467

Can you rework to have control flow like this? Having the assignments so close together for me mitigates the need for an assert.

493

nit: Can you spell out auto on each of these?

504

nit: op? o isn't really used to refer to operation variables anywhere else.

[bzcheeseman]

mlir/lib/Analysis/Liveness.cpp

452

That's a good point! I'll fix this.

461–467

works for me!

493

sure thing :)

504

op is the argument to the function so I needed a different name. I can switch to something like walkOp?

[rriddle]

mlir/lib/Analysis/Liveness.cpp

490–491

Do you need to check live outs? Wouldn't those already be covered by checking live-ins+ops within the block?

495

walk is recursive, but for the sake of this computation you don't want that right?

496–497

If you are already tracking live ins, do you need to check the operands of each op? I would expect that checking live-ins+results of operations in the block would give you what you need.

[bzcheeseman]

mlir/lib/Analysis/Liveness.cpp

490–491

You're right, an old implementation did need it but this one does not. I think at one point I had a bad version of the live range checking and improving that has made this unnecessary.

495

Actually I do want that - the scf.for example is one where I want to know the values that are live *within* the loop as well.

496–497

same as above - at one point I improved the live range thing and didn't realize I didn't need this :)

[rriddle]

mlir/lib/Analysis/Liveness.cpp

495

For nested operations though, we would handle them differently that operations in the current block, right?

[bzcheeseman]

mlir/lib/Analysis/Liveness.cpp

495

I mean for a concrete example, in the scf.for loop below it's useful to have a list of values that are live even only for the body of the loop. That's the main reason for it - that's the semantic that I needed in the past. That said, for the current use case I have in mind, the operation that I want this analysis for doesn't have nested ops so I'm semi-okay with changing the semantics, we just gotta agree that's the way to move forward.

[rriddle]

clang-format isn't happy, please look into that.

[bzcheeseman]

In D129447#3656775, @rriddle wrote:

clang-format isn't happy, please look into that.

Done, thanks :)

mlir/include/mlir/Analysis/Liveness.h

public:
   /// operation of the current block (in case the value is live-in) or the
   /// operation that defines the given value (must be referenced in this block).
   Operation *getStartOperation(Value value) const;
 
   /// Gets the end operation for the given value using the start operation
   /// provided (must be referenced in this block).
   Operation *getEndOperation(Value value, Operation *startOperation) const;
 
+  /// Get the set of values that are currently live (if any) for the current op.
+  /// This analysis takes an expansive view of "live" in that if a value is
+  /// defined by or within the operation or is fully consumed (as in last user)
+  /// by or within the operation the value is considered "live".
+  ///
+  /// The values in the list are not ordered.
+  ValueSetT currentlyLiveValues(Operation *op) const;
+
 private:
   /// The underlying block.
   Block *block = nullptr;
 
   /// The set of all live in values.
   ValueSetT inValues;
 
   /// The set of all live out values.
   ValueSetT outValues;
 
+  /// The map from operation to the values live as-of that op.
+  DenseMap<Operation *, ValueSetT> opToLiveValues;
+
   friend class Liveness;
 };
 
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_LIVENESS_H

mlir/lib/Analysis/Liveness.cpp

void Liveness::build() {
   // Store internal block data.
   for (auto &entry : builders) {
     BlockInfoBuilder &builder = entry.second;
     LivenessBlockInfo &info = blockMapping[entry.first];
 
     info.block = builder.block;
     info.inValues = std::move(builder.inValues);
     info.outValues = std::move(builder.outValues);
+
+    // Given a value, check which ops are within its live range. For each of
+    // those ops, add the value to the set of live values as-of that op.
+    auto addValueToCurrentlyLiveSets = [&](Value value) {
+      // Determine the live range of this value inside this block.
+      Operation *startOfLiveRange = value.getDefiningOp();
+      Operation *endOfLiveRange = nullptr;
+      // If it's a live in or a block argument, then the start is the beginning
+      // of the block.
+      if (info.isLiveIn(value) || value.isa<BlockArgument>())
+        startOfLiveRange = &info.block->front();
+
+      // Ensure the start of the live range is in the block we want.
+      assert(startOfLiveRange && "Must have startOfLiveRange at this point!");
+      startOfLiveRange = info.block->findAncestorOpInBlock(*startOfLiveRange);
+
+      // If it's a live out, then the end is the back of the block.
+      if (info.isLiveOut(value))
+        endOfLiveRange = &info.block->back();
+
+      // We must have at least a startOfLiveRange at this point. Given this, we
+      // can use the existing getEndOperation to find the end of the live range.
+      if (startOfLiveRange && !endOfLiveRange)
+        endOfLiveRange = info.getEndOperation(value, startOfLiveRange);
+
+      assert(endOfLiveRange && "Must have endOfLiveRange at this point!");
+      // For all the ops in the block (op under test) if it's within the live
+      // range, add this value to the op under test's set of live values.
+      for (auto &op : *info.block) {
+        Operation *opUnderTest = info.block->findAncestorOpInBlock(op);
+        // If we're outside the live range, don't attempt to add the op
+        if (opUnderTest->isBeforeInBlock(startOfLiveRange) ||
+            endOfLiveRange->isBeforeInBlock(opUnderTest))
+          continue;
+
+        info.opToLiveValues[opUnderTest].insert(value);
+      }
+    };
+
+    // Just walk every value the builder/the info object have available and add
+    // the values to the sets as appropriate. We're effectively just collecting
+    // values and then filtering them into the correct buckets.
+
+    for (auto value : builder.defValues)
+      addValueToCurrentlyLiveSets(value);
+
+    for (auto value : builder.useValues)
+      addValueToCurrentlyLiveSets(value);
+
+    for (auto value : info.inValues)
+      addValueToCurrentlyLiveSets(value);
+
+    for (auto value : info.outValues)
+      addValueToCurrentlyLiveSets(value);
   }
 }
 
 /// Gets liveness info (if any) for the given value.
 Liveness::OperationListT Liveness::resolveLiveness(Value value) const {
   OperationListT result;
   SmallPtrSet<Block *, 32> visited;
   SmallVector<Block *, 8> toProcess;
operation->walk<WalkOrder::PreOrder>([&](Block *block) {
     const auto *liveness = getLiveness(block);
     os << "// --- LiveIn: ";
     printValueRefs(liveness->inValues);
     os << "\n// --- LiveOut: ";
     printValueRefs(liveness->outValues);
     os << "\n";
 
     // Print liveness intervals.
-    os << "// --- BeginLiveness";
+    os << "// --- BeginLivenessIntervals";
     for (Operation &op : *block) {
       if (op.getNumResults() < 1)
         continue;
       os << "\n";
       for (Value result : op.getResults()) {
         os << "// ";
         printValueRef(result);
         os << ":";
         auto liveOperations = resolveLiveness(result);
         std::sort(liveOperations.begin(), liveOperations.end(),
                   [&](Operation *left, Operation *right) {
                     return operationIds[left] < operationIds[right];
                   });
         for (Operation *operation : liveOperations) {
           os << "\n//     ";
           operation->print(os);
         }
       }
     }
-    os << "\n// --- EndLiveness\n";
+    os << "\n// --- EndLivenessIntervals\n";
+
+    // Print currently live values.
+    os << "// --- BeginCurrentlyLive\n";
+    for (Operation &op : *block) {
+      auto currentlyLive = liveness->currentlyLiveValues(&op);
+      if (currentlyLive.empty())
+        continue;
+      os << "//     ";
+      op.print(os);
+      os << " [";
+      printValueRefs(currentlyLive);
+      os << "\b]\n";
+    }
+    os << "// --- EndCurrentlyLive\n";
   });
   os << "// -------------------\n";
 }
 
 //===----------------------------------------------------------------------===//
 // LivenessBlockInfo
 //===----------------------------------------------------------------------===//
 
for (Operation *useOp : value.getUsers()) {
     useOp = block->findAncestorOpInBlock(*useOp);
     // Check whether the use is in our block and after the current end
     // operation.
     if (useOp && endOperation->isBeforeInBlock(useOp))
       endOperation = useOp;
   }
   return endOperation;
 }
+
+/// Return the values that are currently live as of the given operation.
+LivenessBlockInfo::ValueSetT
+LivenessBlockInfo::currentlyLiveValues(Operation *op) const {
+  return opToLiveValues.lookup(op);
+}

mlir/test/Analysis/test-liveness.mlir

 // RUN: mlir-opt %s -pass-pipeline="func.func(test-print-liveness)" -split-input-file 2>&1 | FileCheck %s
 
 // CHECK-LABEL: Testing : func_empty
 func.func @func_empty() {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut:{{ *$}}
-  // CHECK-NEXT: BeginLiveness
-  // CHECK-NEXT: EndLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
+  // CHECK-NEXT: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK-NEXT: EndCurrentlyLive
   return
 }
 
 // -----
 
 // CHECK-LABEL: Testing : func_simpleBranch
 func.func @func_simpleBranch(%arg0: i32, %arg1 : i32) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut: arg0@0 arg1@0
-  // CHECK-NEXT: BeginLiveness
-  // CHECK-NEXT: EndLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
+  // CHECK-NEXT: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: cf.br
+  // CHECK-SAME:   arg0@0 arg1@0
+  // CHECK-NEXT: EndCurrentlyLive
   cf.br ^exit
 ^exit:
   // CHECK: Block: 1
   // CHECK-NEXT: LiveIn: arg0@0 arg1@0
   // CHECK-NEXT: LiveOut:{{ *$}}
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK: val_2
   // CHECK-NEXT:     %0 = arith.addi
   // CHECK-NEXT:     return
-  // CHECK-NEXT: EndLiveness
+  // CHECK-NEXT: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: arith.addi
+  // CHECK-SAME:    arg0@0 arg1@0 val_2
+  // CHECK: return
+  // CHECK-SAME:    val_2
+  // CHECK-NEXT EndCurrentlyLive
   %result = arith.addi %arg0, %arg1 : i32
   return %result : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : func_condBranch
 func.func @func_condBranch(%cond : i1, %arg1: i32, %arg2 : i32) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut: arg1@0 arg2@0
-  // CHECK-NEXT: BeginLiveness
-  // CHECK-NEXT: EndLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
+  // CHECK-NEXT: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: cf.cond_br
+  // CHECK-SAME:   arg0@0 arg1@0 arg2@0
+  // CHECK-NEXT: EndCurrentlyLive
   cf.cond_br %cond, ^bb1, ^bb2
 ^bb1:
   // CHECK: Block: 1
   // CHECK-NEXT: LiveIn: arg1@0 arg2@0
   // CHECK-NEXT: LiveOut: arg1@0 arg2@0
+  // CHECK: BeginCurrentlyLive
+  // CHECK: cf.br
+  // COM: arg0@0 had its last user in the previous block.
+  // CHECK-SAME:   arg1@0 arg2@0
+  // CHECK-NEXT: EndCurrentlyLive
   cf.br ^exit
 ^bb2:
   // CHECK: Block: 2
   // CHECK-NEXT: LiveIn: arg1@0 arg2@0
   // CHECK-NEXT: LiveOut: arg1@0 arg2@0
+  // CHECK: BeginCurrentlyLive
+  // CHECK: cf.br
+  // CHECK-SAME:   arg1@0 arg2@0
+  // CHECK-NEXT: EndCurrentlyLive
   cf.br ^exit
 ^exit:
   // CHECK: Block: 3
   // CHECK-NEXT: LiveIn: arg1@0 arg2@0
   // CHECK-NEXT: LiveOut:{{ *$}}
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK: val_3
   // CHECK-NEXT:     %0 = arith.addi
   // CHECK-NEXT:     return
-  // CHECK-NEXT: EndLiveness
+  // CHECK-NEXT: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: arith.addi
+  // CHECK-SAME:   arg1@0 arg2@0 val_3
+  // CHECK: return
+  // CHECK-SAME:  val_3
+  // CHECK-NEXT: EndCurrentlyLive
   %result = arith.addi %arg1, %arg2 : i32
   return %result : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : func_loop
 func.func @func_loop(%arg0 : i32, %arg1 : i32) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut: arg1@0
+  // CHECK: BeginCurrentlyLive
+  // CHECK: arith.constant
+  // CHECK-SAME:  arg0@0 arg1@0 val_2
+  // CHECK: cf.br
+  // CHECK-SAME:  arg0@0 arg1@0 val_2
+  // CHECK-NEXT: EndCurrentlyLive
   %const0 = arith.constant 0 : i32
   cf.br ^loopHeader(%const0, %arg0 : i32, i32)
 ^loopHeader(%counter : i32, %i : i32):
   // CHECK: Block: 1
   // CHECK-NEXT: LiveIn: arg1@0
   // CHECK-NEXT: LiveOut: arg1@0 arg0@1
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK-NEXT: val_5
   // CHECK-NEXT:     %2 = arith.cmpi
   // CHECK-NEXT:     cf.cond_br
-  // CHECK-NEXT: EndLiveness
+  // CHECK-NEXT: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: arith.cmpi
+  // CHECK-SAME:  arg1@0 arg0@1 arg1@1 val_5
+  // CHECK: cf.cond_br
+  // CHECK-SAME:  arg1@0 arg0@1 arg1@1 val_5
+  // CHECK-NEXT: EndCurrentlyLive
   %lessThan = arith.cmpi slt, %counter, %arg1 : i32
   cf.cond_br %lessThan, ^loopBody(%i : i32), ^exit(%i : i32)
 ^loopBody(%val : i32):
   // CHECK: Block: 2
   // CHECK-NEXT: LiveIn: arg1@0 arg0@1
   // CHECK-NEXT: LiveOut: arg1@0
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK-NEXT: val_7
   // CHECK-NEXT:     %c
   // CHECK-NEXT:     %4 = arith.addi
   // CHECK-NEXT:     %5 = arith.addi
   // CHECK-NEXT: val_8
   // CHECK-NEXT:     %4 = arith.addi
   // CHECK-NEXT:     %5 = arith.addi
   // CHECK-NEXT:     cf.br
-  // CHECK: EndLiveness
+  // CHECK: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: arith.constant
+  // CHECK-SAME:  arg1@0 arg0@1 arg0@2 val_7
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg1@0 arg0@1 arg0@2 val_7 val_8
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg1@0 arg0@1 val_7 val_8 val_9
+  // CHECK: cf.br
+  // CHECK-SAME:  arg1@0 val_8 val_9
+  // CHECK-NEXT: EndCurrentlyLive
   %const1 = arith.constant 1 : i32
   %inc = arith.addi %val, %const1 : i32
   %inc2 = arith.addi %counter, %const1 : i32
   cf.br ^loopHeader(%inc, %inc2 : i32, i32)
 ^exit(%sum : i32):
   // CHECK: Block: 3
   // CHECK-NEXT: LiveIn: arg1@0
   // CHECK-NEXT: LiveOut:{{ *$}}
+  // CHECK: BeginCurrentlyLive
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg1@0 arg0@3 val_11
+  // CHECK: return
+  // CHECK-SAME:  val_11
+  // CHECK-NEXT: EndCurrentlyLive
   %result = arith.addi %sum, %arg1 : i32
   return %result : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : func_ranges
 func.func @func_ranges(%cond : i1, %arg1 : i32, %arg2 : i32, %arg3 : i32) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut: arg2@0 val_9 val_10
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK-NEXT: val_4
   // CHECK-NEXT:    %0 = arith.addi
   // CHECK-NEXT:    %c
   // CHECK-NEXT:    %1 = arith.addi
   // CHECK-NEXT:    %2 = arith.addi
   // CHECK-NEXT:    %3 = arith.muli
   // CHECK-NEXT: val_5
   // CHECK-NEXT:    %c
func.func @func_ranges(%cond : i1, %arg1 : i32, %arg2 : i32, %arg3 : i32) -> i32 {
   // CHECK-NEXT:    %c
   // CHECK-NEXT:    %6 = arith.muli
   // CHECK-NEXT:    %7 = arith.muli
   // CHECK-NEXT:    %8 = arith.addi
   // CHECK-NEXT: val_10
   // CHECK-NEXT:    %5 = arith.addi
   // CHECK-NEXT:    cf.cond_br
   // CHECK-NEXT:    %7
-  // CHECK: EndLiveness
+  // CHECK: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg0@0 arg1@0 arg2@0 arg3@0 val_4
+  // CHECK: arith.constant
+  // CHECK-SAME:  arg0@0 arg2@0 arg3@0 val_4 val_5
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg0@0 arg2@0 arg3@0 val_4 val_5 val_6
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg0@0 arg2@0 arg3@0 val_4 val_5 val_6 val_7
+  // CHECK: arith.muli
+  // CHECK-SAME:  arg0@0 arg2@0 val_4 val_5 val_6 val_7 val_8
+  // CHECK: arith.muli
+  // CHECK-SAME:  arg0@0 arg2@0 val_5 val_7 val_8 val_9
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg0@0 arg2@0 val_5 val_9 val_10
+  // CHECK: cf.cond_br
+  // CHECK-SAME:  arg0@0 arg2@0 val_9 val_10
+  // CHECK-NEXT: EndCurrentlyLive
   %0 = arith.addi %arg1, %arg2 : i32
   %const1 = arith.constant 1 : i32
   %1 = arith.addi %const1, %arg2 : i32
   %2 = arith.addi %const1, %arg3 : i32
   %3 = arith.muli %0, %1 : i32
   %4 = arith.muli %3, %2 : i32
   %5 = arith.addi %4, %const1 : i32
   cf.cond_br %cond, ^bb1, ^bb2
 
 ^bb1:
   // CHECK: Block: 1
   // CHECK-NEXT: LiveIn: arg2@0 val_9
   // CHECK-NEXT: LiveOut: arg2@0
+  // CHECK: BeginCurrentlyLive
+  // CHECK: arith.constant
+  // CHECK-SAME:  arg2@0 val_9
+  // CHECK: arith.muli
+  // CHECK-SAME:  arg2@0 val_9
+  // CHECK: cf.br
+  // CHECK-SAME:  arg2@0
+  // CHECK-NEXT: EndCurrentlyLive
   %const4 = arith.constant 4 : i32
   %6 = arith.muli %4, %const4 : i32
   cf.br ^exit(%6 : i32)
 
 ^bb2:
   // CHECK: Block: 2
   // CHECK-NEXT: LiveIn: arg2@0 val_9 val_10
   // CHECK-NEXT: LiveOut: arg2@0
+  // CHECK: BeginCurrentlyLive
+  // CHECK: arith.muli
+  // CHECK-SAME:  arg2@0 val_9 val_10
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg2@0
+  // CHECK: cf.br
+  // CHECK-SAME:  arg2@0
+  // CHECK: EndCurrentlyLive
   %7 = arith.muli %4, %5 : i32
   %8 = arith.addi %4, %arg2 : i32
   cf.br ^exit(%8 : i32)
 
 ^exit(%sum : i32):
   // CHECK: Block: 3
   // CHECK-NEXT: LiveIn: arg2@0
   // CHECK-NEXT: LiveOut:{{ *$}}
+  // CHECK: BeginCurrentlyLive
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg2@0
+  // CHECK: return
+  // CHECK-NOT: arg2@0
+  // CHECK: EndCurrentlyLive
   %result = arith.addi %sum, %arg2 : i32
   return %result : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : nested_region
 
 func.func @nested_region(
   %arg0 : index, %arg1 : index, %arg2 : index,
   %arg3 : i32, %arg4 : i32, %arg5 : i32,
   %buffer : memref<i32>) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut:{{ *$}}
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK-NEXT: val_7
   // CHECK-NEXT:    %0 = arith.addi
   // CHECK-NEXT:    %1 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // %2 = arith.addi
   // CHECK-NEXT:    %3 = arith.addi
   // CHECK-NEXT: val_8
   // CHECK-NEXT:    %1 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // func.return %1
-  // CHECK: EndLiveness
+  // CHECK: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg0@0 arg1@0 arg2@0 arg3@0 arg4@0 arg5@0 arg6@0 val_7
+  // CHECK: arith.addi
+  // CHECK-SAME:  arg0@0 arg1@0 arg2@0 arg4@0 arg5@0 arg6@0 val_7 val_8
+  // CHECK: scf.for
+  // CHECK-NEXT: arith.addi
+  // CHECK-NEXT: arith.addi
+  // CHECK-NEXT: memref.store
+  // COM: The values that are live/consumed in the loop body are considered live for the loop.
+  // CHECK-NEXT:  arg5@0 arg6@0 val_7 val_8 val_10 val_11
+  // CHECK: return
+  // CHECK-SAME:  val_8
+  // CHECK-NEXT: EndCurrentlyLive
   %0 = arith.addi %arg3, %arg4 : i32
   %1 = arith.addi %arg4, %arg5 : i32
   scf.for %arg6 = %arg0 to %arg1 step %arg2 {
     // CHECK: Block: 1
     // CHECK-NEXT: LiveIn: arg5@0 arg6@0 val_7
     // CHECK-NEXT: LiveOut:{{ *$}}
+    // CHECK: BeginCurrentlyLive
+    // CHECK-NEXT: arith.addi
+    // CHECK-SAME:   arg5@0 arg6@0 val_7 arg0@1 val_10
+    // CHECK-NEXT: arith.addi
+    // CHECK-SAME:   arg6@0 val_7 val_10 val_11
+    // CHECK-NEXT: memref.store
+    // CHECK-SAME:   arg6@0 val_11
+    // CHECK-NEXT: EndCurrentlyLive
     %2 = arith.addi %0, %arg5 : i32
     %3 = arith.addi %2, %0 : i32
     memref.store %3, %buffer[] : memref<i32>
   }
   return %1 : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : nested_region2
 
 func.func @nested_region2(
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut:{{ *$}}
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK-NEXT: val_7
   // CHECK-NEXT:    %0 = arith.addi
   // CHECK-NEXT:    %1 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // %2 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // %3 = arith.addi
   // CHECK-NEXT: val_8
   // CHECK-NEXT:    %1 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // func.return %1
-  // CHECK: EndLiveness
+  // CHECK: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK-NEXT: arith.addi
+  // CHECK-SAME:   arg0@0 arg1@0 arg2@0 arg3@0 arg4@0 arg5@0 arg6@0 val_7
+  // CHECK-NEXT: arith.addi
+  // CHECK-SAME:   arg0@0 arg1@0 arg2@0 arg4@0 arg5@0 arg6@0 val_7 val_8
+  // CHECK-NEXT: scf.for {{.*}}
+  // CHECK-NEXT:   arith.addi
+  // CHECK-NEXT:   scf.for {{.*}} {
+  // CHECK-NEXT:     arith.addi
+  // CHECK-NEXT:     memref.store
+  // CHECK-NEXT:   }
+  // CHECK-NEXT: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 val_8 val_10 val_12
+  // CHECK-NEXT: return
+  // CHECK-SAME:  val_8
   %arg0 : index, %arg1 : index, %arg2 : index,
   %arg3 : i32, %arg4 : i32, %arg5 : i32,
   %buffer : memref<i32>) -> i32 {
   %0 = arith.addi %arg3, %arg4 : i32
   %1 = arith.addi %arg4, %arg5 : i32
   scf.for %arg6 = %arg0 to %arg1 step %arg2 {
     // CHECK: Block: 1
     // CHECK-NEXT: LiveIn: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7
     // CHECK-NEXT: LiveOut:{{ *$}}
-    // CHECK-NEXT: BeginLiveness
+    // CHECK-NEXT: BeginLivenessIntervals
     // CHECK-NEXT: val_10
     // CHECK-NEXT:    %2 = arith.addi
     // CHECK-NEXT:    scf.for
     // CHECK:         // %3 = arith.addi
-    // CHECK: EndLiveness
+    // CHECK: EndLivenessIntervals
+    // CHECK-NEXT: BeginCurrentlyLive
+    // CHECK-NEXT: arith.addi
+    // CHECK-SAME:   arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 arg0@1 val_10
+    // CHECK-NEXT: scf.for {{.*}}
+    // CHECK-NEXT:   arith.addi
+    // CHECK-NEXT:   memref.store
+    // CHECK-NEXT: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_10 val_12
     %2 = arith.addi %0, %arg5 : i32
     scf.for %arg7 = %arg0 to %arg1 step %arg2 {
+      // CHECK: Block: 2
+      // CHECK: BeginCurrentlyLive
+      // CHECK-NEXT: arith.addi
+      // CHECK-SAME:   arg6@0 val_7 val_10 arg0@2 val_12
+      // CHECK-NEXT: memref.store
+      // CHECK-SAME:   arg6@0 val_12
+      // CHECK: EndCurrentlyLive
       %3 = arith.addi %2, %0 : i32
       memref.store %3, %buffer[] : memref<i32>
     }
   }
   return %1 : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : nested_region3
 
 func.func @nested_region3(
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8
-  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: BeginLivenessIntervals
   // CHECK-NEXT: val_7
   // CHECK-NEXT:    %0 = arith.addi
   // CHECK-NEXT:    %1 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // cf.br ^bb1
   // CHECK-NEXT:    %2 = arith.addi
   // CHECK-NEXT:    scf.for
   // CHECK:         // %2 = arith.addi
-  // CHECK: EndLiveness
+  // CHECK: EndLivenessIntervals
+  // CHECK-NEXT: BeginCurrentlyLive
+  // CHECK-NEXT: arith.addi
+  // CHECK-SAME:   arg0@0 arg1@0 arg2@0 arg3@0 arg4@0 arg5@0 arg6@0 val_7
+  // CHECK-NEXT: arith.addi
+  // CHECK-SAME:   arg0@0 arg1@0 arg2@0 arg4@0 arg5@0 arg6@0 val_7 val_8
+  // CHECK-NEXT: scf.for
+  // COM: Skipping the body of the scf.for...
+  // CHECK: arg0@0 arg1@0 arg2@0 arg5@0 arg6@0 val_7 val_8 val_10
+  // CHECK-NEXT: cf.br
+  // CHECK-SAME:   arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8
+  // CHECK-NEXT: EndCurrentlyLive
   %arg0 : index, %arg1 : index, %arg2 : index,
   %arg3 : i32, %arg4 : i32, %arg5 : i32,
   %buffer : memref<i32>) -> i32 {
   %0 = arith.addi %arg3, %arg4 : i32
   %1 = arith.addi %arg4, %arg5 : i32
   scf.for %arg6 = %arg0 to %arg1 step %arg2 {
     // CHECK: Block: 1
     // CHECK-NEXT: LiveIn: arg5@0 arg6@0 val_7
     // CHECK-NEXT: LiveOut:{{ *$}}
+    // CHECK: BeginCurrentlyLive
+    // CHECK-NEXT: arith.addi
+    // CHECK-SAME:   arg5@0 arg6@0 val_7 arg0@1 val_10
+    // CHECK-NEXT: memref.store
+    // CHECK-SAME:   arg6@0 val_10
+    // CHECK-NEXT: EndCurrentlyLive
     %2 = arith.addi %0, %arg5 : i32
     memref.store %2, %buffer[] : memref<i32>
   }
   cf.br ^exit
 
 ^exit:
   // CHECK: Block: 2
   // CHECK-NEXT: LiveIn: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8
   // CHECK-NEXT: LiveOut:{{ *$}}
+  // CHECK: BeginCurrentlyLive
+  // CHECK: scf.for
+  // CHECK: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8 val_12
+  // CHECK-NEXT: return
+  // CHECK-SAME:   val_8
+  // CHECK-NEXT: EndCurrentlyLive
   scf.for %arg7 = %arg0 to %arg1 step %arg2 {
     // CHECK: Block: 3
     // CHECK-NEXT: LiveIn: arg6@0 val_7 val_8
     // CHECK-NEXT: LiveOut:{{ *$}}
+    // CHECK: BeginCurrentlyLive
+    // CHECK-NEXT: arith.addi
+    // CHECK-SAME:   arg6@0 val_7 val_8 arg0@3 val_12
+    // CHECK-NEXT: memref.store
+    // CHECK-SAME:   arg6@0 val_12
+    // CHECK-NEXT: EndCurrentlyLive
     %2 = arith.addi %0, %1 : i32
     memref.store %2, %buffer[] : memref<i32>
   }
   return %1 : i32
 }