Extended Liveness analysis to support nested regions.

[dfki-mako]

Summary

The current Liveness analysis does not support operations with nested regions. This causes issues when querying liveness information about blocks nested within operations. Furthermore, the live-in and live-out sets are not computed properly in these cases.

[dfki-mako]

Addressed formatting issues introduced by clang-format-6.

[herhut]

This still does not handle the case where values flow through operations (and that is fine, we lack the interface). A good example might be a loop.for with iter_args

I am OK with this to land with the two comments addressed but wait for @rriddle to comment and approve.

mlir/lib/Analysis/Liveness.cpp

49

What does it mean if there is no ownerBlock. Can this ever happen? It would mean that the use was in a block that does not have the current operation as parent. Values cannot escape regions, though. Maybe rather assert than hiding this case.

104

Is this a spurious reformat?

301

Use valueIds here?

mlir/test/Analysis/test-liveness.mlir

312

I think this would be easier to read if the function arguments were already named %argX in the input. Also, please make the value names unique, either by using the counter or you could use an instruction position trace, using block numbers and trace back via parent ops.

i1@b0@i5 for the second instruction in block zero of the fifth instruction. These are easier to map back to the actual code than global numbers.

In any case, something to make the printout non-ambiguous.

[dfki-mako]

Applied comments and adapted test cases.

[dfki-mako]

mlir/lib/Analysis/Liveness.cpp

104

Was wrongly formatted.

[rriddle]

Thanks for tackling this! Left a few comments.

mlir/lib/Analysis/Liveness.cpp

40

nit: Use getUsers if you are only accessing the use owners.

45

Can you just add a utility Region::findAncestorOpInRegion(Operation *op) method that finds the ancestor of an operation within a given region? It's effectively similar to the block variant.

390–391

nit: Same here, can you change this to getUsers?

391

Are you trying to find an ancestor of useOperation that exists within block? Seems like block->findAncestorOpInBlock(useOperation) is intended for this use case.

[dfki-mako]

Applied comments and refactored findInCurrent functionality.

[dfki-mako]

We have introduced a new utility function

Block *Region::findAncestorBlockInRegion(Block &block)

in order to remove the findInCurrent implementation.

[herhut]

Thanks for adding this!

[rriddle]

mlir/include/mlir/IR/Region.h

114

nit: ancestor block -> ancestor

(There are a lot of 'block's in that sentence)

mlir/lib/Analysis/Liveness.cpp

42–43

Can you reflow these comments to wrap at 80 characters.

[dfki-mako]

Reformatted and upated comments.

mlir/include/mlir/IR/Region.h

public:
   }
 
   /// Check that this does not use any value defined outside it.
   /// Emit errors if `noteLoc` is provided; this location is used to point
   /// to the operation containing the region, the actual error is reported at
   /// the operation with an offending use.
   bool isIsolatedFromAbove(Optional<Location> noteLoc = llvm::None);
 
+  /// Returns 'block' if 'block' lies in this region, or otherwise finds the
+  /// ancestor of 'block' that lies in this region. Returns nullptr if the
+  /// latter fails.
+  Block *findAncestorBlockInRegion(Block &block);
+
   /// Drop all operand uses from operations within this region, which is
   /// an essential step in breaking cyclic dependences between references when
   /// they are to be deleted.
   void dropAllReferences();
 
   /// Walk the operations in this region in postorder, calling the callback for
   /// each operation. This method is invoked for void-returning callbacks.
   /// See Operation::walk for more details.

mlir/lib/Analysis/Liveness.cpp

 struct BlockInfoBuilder {
   using ValueSetT = Liveness::ValueSetT;
 
   /// Constructs an empty block builder.
   BlockInfoBuilder() : block(nullptr) {}
 
   /// Fills the block builder with initial liveness information.
   BlockInfoBuilder(Block *block) : block(block) {
+    auto gatherOutValues = [&](Value value) {
+      // Check whether this value will be in the outValues set (its uses escape
+      // this block). Due to the SSA properties of the program, the uses must
+      // occur after the definition. Therefore, we do not have to check
+      // additional conditions to detect an escaping value.
+      for (Operation *useOp : value.getUsers()) {
+        Block *ownerBlock = useOp->getBlock();
+        // Find an owner block in the current region. Note that a value does not
+        // escape this block if it is used in a nested region.
+        ownerBlock = block->getParent()->findAncestorBlockInRegion(*ownerBlock);
+        assert(ownerBlock && "Use leaves the current parent region");
+        if (ownerBlock != block) {
+          outValues.insert(value);
+          break;
+        }
+      }
+    };
+
     // Mark all block arguments (phis) as defined.
-    for (BlockArgument argument : block->getArguments())
+    for (BlockArgument argument : block->getArguments()) {
+      // Insert value into the set of defined values.
       defValues.insert(argument);
 
-    // Check all result values and whether their uses
-    // are inside this block or not (see outValues).
+      // Gather all out values of all arguments in the current block.
+      gatherOutValues(argument);
+    }
+
+    // Gather out values of all operations in the current block.
     for (Operation &operation : *block)
-      for (Value result : operation.getResults()) {
-        defValues.insert(result);
+      for (Value result : operation.getResults())
+        gatherOutValues(result);
 
-        // Check whether this value will be in the outValues
-        // set (its uses escape this block). Due to the SSA
-        // properties of the program, the uses must occur after
-        // the definition. Therefore, we do not have to check
-        // additional conditions to detect an escaping value.
-        for (OpOperand &use : result.getUses())
-          if (use.getOwner()->getBlock() != block) {
-            outValues.insert(result);
-            break;
-          }
-      }
+    // Mark all nested operation results as defined.
+    block->walk([&](Operation *op) {
+      for (Value result : op->getResults())
+        defValues.insert(result);
+    });
 
     // Check all operations for used operands.
-    for (Operation &operation : block->getOperations())
-      for (Value operand : operation.getOperands()) {
+    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);
       }
+    });
   }
 
-  /// 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.
+  /// 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.
+    // 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;
     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.
+  /// 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) {
     for (Block *succ : block->getSuccessors()) {
       BlockInfoBuilder &builder = source[succ];
       llvm::set_union(outValues, builder.inValues);
     }
   }
 
   /// The current block.
   Block *block;
 
   /// The set of all live in values.
   ValueSetT inValues;
 
   /// The set of all live out values.
   ValueSetT outValues;
 
   /// The set of all defined values.
   ValueSetT defValues;
 
   /// The set of all used values.
   ValueSetT useValues;
 };
 } // namespace
 
+/// Walks all regions (including nested regions recursively) and invokes the
+/// given function for every block.
+template <typename FuncT>
+static void walkRegions(MutableArrayRef<Region> regions, const FuncT &func) {
+  for (Region &region : regions)
+    for (Block &block : region) {
+      func(block);
+
+      // Traverse all nested regions.
+      for (Operation &operation : block)
+        walkRegions(operation.getRegions(), func);
+    }
+}
+
 /// Builds the internal liveness block mapping.
 static void buildBlockMapping(MutableArrayRef<Region> regions,
                               DenseMap<Block *, BlockInfoBuilder> &builders) {
   llvm::SetVector<Block *> toProcess;
 
-  // Initialize all block structures
-  for (Region &region : regions)
-    for (Block &block : region) {
-      BlockInfoBuilder &builder =
-          builders.try_emplace(&block, &block).first->second;
+  walkRegions(regions, [&](Block &block) {
 
-      if (builder.updateLiveIn())
-        toProcess.insert(block.pred_begin(), block.pred_end());
-    }
+  });
 
   // 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.
+/// Creates a new Liveness analysis that computes liveness information for all
+/// associated regions.
 Liveness::Liveness(Operation *op) : operation(op) { build(op->getRegions()); }
 
 /// Initializes the internal mappings.
 void Liveness::build(MutableArrayRef<Region> regions) {
 
   // Build internal block mapping.
   DenseMap<Block *, BlockInfoBuilder> builders;
   buildBlockMapping(regions, builders);
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.
+/// Returns true if the given operation represent the last use of the given
+/// value.
 bool Liveness::isLastUse(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;
 

 /// Dumps the liveness information to the given stream.
 void Liveness::print(raw_ostream &os) const {
   os << "// ---- Liveness -----\n";
 
   // Builds unique block/value mappings for testing purposes.
   DenseMap<Block *, size_t> blockIds;
   DenseMap<Operation *, size_t> operationIds;
   DenseMap<Value, size_t> valueIds;
-  for (Region &region : operation->getRegions())
-    for (Block &block : region) {
-      blockIds.insert({&block, blockIds.size()});
-      for (BlockArgument argument : block.getArguments())
-        valueIds.insert({argument, valueIds.size()});
-      for (Operation &operation : block) {
-        operationIds.insert({&operation, operationIds.size()});
-        for (Value result : operation.getResults())
-          valueIds.insert({result, valueIds.size()});
-      }
-    }
+  walkRegions(operation->getRegions(), [&](Block &block) {
+  });
 
   // Local printing helpers
   auto printValueRef = [&](Value value) {
     if (Operation *defOp = value.getDefiningOp())
-      os << "val_" << defOp->getName();
+      os << "val_" << valueIds[value];
     else {
       auto blockArg = value.cast<BlockArgument>();
       os << "arg" << blockArg.getArgNumber() << "@"
          << blockIds[blockArg.getOwner()];
     }
     os << " ";
   };
 
   auto printValueRefs = [&](const ValueSetT &values) {
     std::vector<Value> orderedValues(values.begin(), values.end());
     std::sort(orderedValues.begin(), orderedValues.end(),
               [&](Value left, Value right) {
                 return valueIds[left] < valueIds[right];
               });
     for (Value value : orderedValues)
       printValueRef(value);
   };
 
   // Dump information about in and out values.
-  for (Region &region : operation->getRegions())
-    for (Block &block : region) {
-      os << "// - Block: " << blockIds[&block] << "\n";
-      auto liveness = getLiveness(&block);
-      os << "// --- LiveIn: ";
-      printValueRefs(liveness->inValues);
-      os << "\n// --- LiveOut: ";
-      printValueRefs(liveness->outValues);
-      os << "\n";
+  walkRegions(operation->getRegions(), [&](Block &block) {
 
-      // Print liveness intervals.
-      os << "// --- BeginLiveness";
-      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";
 }
 
 //===----------------------------------------------------------------------===//
 // LivenessBlockInfo
 //===----------------------------------------------------------------------===//
 
 /// Returns true if the given value is in the live-in set.
 bool LivenessBlockInfo::isLiveIn(Value value) const {
   return inValues.count(value);
 }
 
 /// Returns true if the given value is in the live-out set.
 bool LivenessBlockInfo::isLiveOut(Value value) const {
   return outValues.count(value);
 }
 
-/// Gets the start operation for the given value
-/// (must be referenced in this block).
+/// Gets the start operation for the given value (must be referenced in this
+/// block).
 Operation *LivenessBlockInfo::getStartOperation(Value value) const {
   Operation *definingOp = value.getDefiningOp();
   // The given value is either live-in or is defined
   // in the scope of this block.
   if (isLiveIn(value) || !definingOp)
     return &block->front();
   return definingOp;
 }
 
 /// Gets the end operation for the given value using the start operation
 /// provided (must be referenced in this block).
 Operation *LivenessBlockInfo::getEndOperation(Value value,
                                               Operation *startOperation) const {
   // The given value is either dying in this block or live-out.
   if (isLiveOut(value))
     return &block->back();
 
   // Resolve the last operation (must exist by definition).
   Operation *endOperation = startOperation;
-  for (OpOperand &use : value.getUses()) {
-    Operation *useOperation = use.getOwner();
-    // Check whether the use is in our block and after
-    // the current end operation.
-    if (useOperation->getBlock() == block &&
-        endOperation->isBeforeInBlock(useOperation))
-      endOperation = useOperation;
+  for (Operation *useOp : value.getUsers()) {
+    // Find the associated operation in the current block (if any).
+    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;
 }

mlir/lib/IR/Region.cpp

for (auto &succOp : op->getBlockOperands())
       if (auto *mappedOp = mapper.lookupOrNull(succOp.get()))
         succOp.set(mappedOp);
   };
 
   for (iterator it(mapper.lookup(&front())); it != destPos; ++it)
     it->walk(remapOperands);
 }
 
+/// Returns 'block' if 'block' lies in this region, or otherwise finds the
+/// ancestor of 'block' that lies in this region. Returns nullptr if the latter
+/// fails.
+Block *Region::findAncestorBlockInRegion(Block &block) {
+  auto currBlock = █
+  while (currBlock->getParent() != this) {
+    Operation *parentOp = currBlock->getParentOp();
+    if (!parentOp || !parentOp->getBlock())
+      return nullptr;
+    currBlock = parentOp->getBlock();
+  }
+  return currBlock;
+}
+
 void Region::dropAllReferences() {
   for (Block &b : *this)
     b.dropAllReferences();
 }
 
 /// Check if there are any values used by operations in `region` defined
 /// outside its ancestor region `limit`.  That is, given `A{B{C{}}}` with region
 /// `C` and limit `B`, the values defined in `B` can be used but the values

mlir/test/Analysis/test-liveness.mlir

func @func_simpleBranch(%arg0: i32, %arg1 : i32) -> i32 {
   // CHECK-NEXT: BeginLiveness
   // CHECK-NEXT: EndLiveness
   br ^exit
 ^exit:
   // CHECK: Block: 1
   // CHECK-NEXT: LiveIn: arg0@0 arg1@0
   // CHECK-NEXT: LiveOut:{{ *$}}
   // CHECK-NEXT: BeginLiveness
-  // CHECK: val_std.addi
+  // CHECK: val_2
   // CHECK-NEXT:     %0 = addi
   // CHECK-NEXT:     return
   // CHECK-NEXT: EndLiveness
   %result = addi %arg0, %arg1 : i32
   return %result : i32
 }
 
 // -----
^bb2:
   // CHECK-NEXT: LiveIn: arg1@0 arg2@0
   // CHECK-NEXT: LiveOut: arg1@0 arg2@0
   br ^exit
 ^exit:
   // CHECK: Block: 3
   // CHECK-NEXT: LiveIn: arg1@0 arg2@0
   // CHECK-NEXT: LiveOut:{{ *$}}
   // CHECK-NEXT: BeginLiveness
-  // CHECK: val_std.addi
+  // CHECK: val_3
   // CHECK-NEXT:     %0 = addi
   // CHECK-NEXT:     return
   // CHECK-NEXT: EndLiveness
   %result = addi %arg1, %arg2 : i32
   return %result : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : func_loop
 func @func_loop(%arg0 : i32, %arg1 : i32) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
   // CHECK-NEXT: LiveOut: arg1@0
   %const0 = constant 0 : i32
   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: val_std.cmpi
+  // CHECK-NEXT: val_5
   // CHECK-NEXT:     %2 = cmpi
   // CHECK-NEXT:     cond_br
   // CHECK-NEXT: EndLiveness
   %lessThan = cmpi "slt", %counter, %arg1 : i32
   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: val_std.constant
+  // CHECK-NEXT: val_7
   // CHECK-NEXT:     %c
   // CHECK-NEXT:     %4 = addi
   // CHECK-NEXT:     %5 = addi
-  // CHECK-NEXT: val_std.addi
+  // CHECK-NEXT: val_8
   // CHECK-NEXT:     %4 = addi
   // CHECK-NEXT:     %5 = addi
   // CHECK-NEXT:     br
   // CHECK: EndLiveness
   %const1 = constant 1 : i32
   %inc = addi %val, %const1 : i32
   %inc2 = addi %counter, %const1 : i32
   br ^loopHeader(%inc, %inc2 : i32, i32)
 ^exit(%sum : i32):
   // CHECK: Block: 3
   // CHECK-NEXT: LiveIn: arg1@0
   // CHECK-NEXT: LiveOut:{{ *$}}
   %result = addi %sum, %arg1 : i32
   return %result : i32
 }
 
 // -----
 
 // CHECK-LABEL: Testing : func_ranges
 func @func_ranges(%cond : i1, %arg1 : i32, %arg2 : i32, %arg3 : i32) -> i32 {
   // CHECK: Block: 0
   // CHECK-NEXT: LiveIn:{{ *$}}
-  // CHECK-NEXT: LiveOut: arg2@0 val_std.muli val_std.addi
+  // CHECK-NEXT: LiveOut: arg2@0 val_9 val_10
   // CHECK-NEXT: BeginLiveness
-  // CHECK-NEXT: val_std.addi
+  // CHECK-NEXT: val_4
   // CHECK-NEXT:    %0 = addi
   // CHECK-NEXT:    %c
   // CHECK-NEXT:    %1 = addi
   // CHECK-NEXT:    %2 = addi
   // CHECK-NEXT:    %3 = muli
-  // CHECK-NEXT: val_std.constant
+  // CHECK-NEXT: val_5
   // CHECK-NEXT:    %c
   // CHECK-NEXT:    %1 = addi
   // CHECK-NEXT:    %2 = addi
   // CHECK-NEXT:    %3 = muli
   // CHECK-NEXT:    %4 = muli
   // CHECK-NEXT:    %5 = addi
-  // CHECK-NEXT: val_std.addi
+  // CHECK-NEXT: val_6
   // CHECK-NEXT:    %1 = addi
   // CHECK-NEXT:    %2 = addi
   // CHECK-NEXT:    %3 = muli
-  // CHECK-NEXT: val_std.addi
+  // CHECK-NEXT: val_7
   // CHECK-NEXT    %2 = addi
   // CHECK-NEXT    %3 = muli
   // CHECK-NEXT    %4 = muli
-  // CHECK: val_std.muli
+  // CHECK:      val_8
   // CHECK-NEXT:    %3 = muli
   // CHECK-NEXT:    %4 = muli
-  // CHECK-NEXT: val_std.muli
+  // CHECK-NEXT: val_9
   // CHECK-NEXT:    %4 = muli
   // CHECK-NEXT:    %5 = addi
   // CHECK-NEXT:    cond_br
   // CHECK-NEXT:    %c
   // CHECK-NEXT:    %6 = muli
   // CHECK-NEXT:    %7 = muli
   // CHECK-NEXT:    %8 = addi
-  // CHECK-NEXT: val_std.addi
+  // CHECK-NEXT: val_10
   // CHECK-NEXT:    %5 = addi
   // CHECK-NEXT:    cond_br
   // CHECK-NEXT:    %7
   // CHECK: EndLiveness
   %0 = addi %arg1, %arg2 : i32
   %const1 = constant 1 : i32
   %1 = addi %const1, %arg2 : i32
   %2 = addi %const1, %arg3 : i32
   %3 = muli %0, %1 : i32
   %4 = muli %3, %2 : i32
   %5 = addi %4, %const1 : i32
   cond_br %cond, ^bb1, ^bb2
 
 ^bb1:
   // CHECK: Block: 1
-  // CHECK-NEXT: LiveIn: arg2@0 val_std.muli
+  // CHECK-NEXT: LiveIn: arg2@0 val_9
   // CHECK-NEXT: LiveOut: arg2@0
   %const4 = constant 4 : i32
   %6 = muli %4, %const4 : i32
   br ^exit(%6 : i32)
 
 ^bb2:
   // CHECK: Block: 2
-  // CHECK-NEXT: LiveIn: arg2@0 val_std.muli val_std.addi
+  // CHECK-NEXT: LiveIn: arg2@0 val_9 val_10
   // CHECK-NEXT: LiveOut: arg2@0
   %7 = muli %4, %5 : i32
   %8 = addi %4, %arg2 : i32
   br ^exit(%8 : i32)
 
 ^exit(%sum : i32):
   // CHECK: Block: 3
   // CHECK-NEXT: LiveIn: arg2@0
   // CHECK-NEXT: LiveOut:{{ *$}}
   %result = addi %sum, %arg2 : i32
   return %result : i32
-}
+}
+
+// -----
+
+// CHECK-LABEL: Testing : nested_region
+
+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: val_7
+  // CHECK-NEXT:    %0 = addi
+  // CHECK-NEXT:    %1 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // %2 = addi
+  // CHECK-NEXT:    %3 = addi
+  // CHECK-NEXT: val_8
+  // CHECK-NEXT:    %1 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // return %1
+  // CHECK: EndLiveness
+  %0 = addi %arg3, %arg4 : i32
+  %1 = addi %arg4, %arg5 : i32
+  loop.for %arg6 = %arg0 to %arg1 step %arg2 {
+    // CHECK: Block: 1
+    // CHECK-NEXT: LiveIn: arg5@0 arg6@0 val_7
+    // CHECK-NEXT: LiveOut:{{ *$}}
+    %2 = addi %0, %arg5 : i32
+    %3 = addi %2, %0 : i32
+    store %3, %buffer[] : memref<i32>
+  }
+  return %1 : i32
+}
+
+// -----
+
+// CHECK-LABEL: Testing : nested_region2
+
+func @nested_region2(
+  // CHECK: Block: 0
+  // CHECK-NEXT: LiveIn:{{ *$}}
+  // CHECK-NEXT: LiveOut:{{ *$}}
+  // CHECK-NEXT: BeginLiveness
+  // CHECK-NEXT: val_7
+  // CHECK-NEXT:    %0 = addi
+  // CHECK-NEXT:    %1 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // %2 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // %3 = addi
+  // CHECK-NEXT: val_8
+  // CHECK-NEXT:    %1 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // return %1
+  // CHECK: EndLiveness
+  %arg0 : index, %arg1 : index, %arg2 : index,
+  %arg3 : i32, %arg4 : i32, %arg5 : i32,
+  %buffer : memref<i32>) -> i32 {
+  %0 = addi %arg3, %arg4 : i32
+  %1 = addi %arg4, %arg5 : i32
+  loop.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: val_10
+    // CHECK-NEXT:    %2 = addi
+    // CHECK-NEXT:    loop.for
+    // CHECK:         // %3 = addi
+    // CHECK: EndLiveness
+    %2 = addi %0, %arg5 : i32
+    loop.for %arg7 = %arg0 to %arg1 step %arg2 {
+      %3 = addi %2, %0 : i32
+      store %3, %buffer[] : memref<i32>
+    }
+  }
+  return %1 : i32
+}
+
+// -----
+
+// CHECK-LABEL: Testing : nested_region3
+
+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: val_7
+  // CHECK-NEXT:    %0 = addi
+  // CHECK-NEXT:    %1 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // br ^bb1
+  // CHECK-NEXT:    %2 = addi
+  // CHECK-NEXT:    loop.for
+  // CHECK:         // %2 = addi
+  // CHECK: EndLiveness
+  %arg0 : index, %arg1 : index, %arg2 : index,
+  %arg3 : i32, %arg4 : i32, %arg5 : i32,
+  %buffer : memref<i32>) -> i32 {
+  %0 = addi %arg3, %arg4 : i32
+  %1 = addi %arg4, %arg5 : i32
+  loop.for %arg6 = %arg0 to %arg1 step %arg2 {
+    // CHECK: Block: 1
+    // CHECK-NEXT: LiveIn: arg5@0 arg6@0 val_7
+    // CHECK-NEXT: LiveOut:{{ *$}}
+    %2 = addi %0, %arg5 : i32
+    store %2, %buffer[] : memref<i32>
+  }
+  br ^exit
+
+^exit:
+  // CHECK: Block: 2
+  // CHECK-NEXT: LiveIn: arg0@0 arg1@0 arg2@0 arg6@0 val_7 val_8
+  // CHECK-NEXT: LiveOut:{{ *$}}
+  loop.for %arg7 = %arg0 to %arg1 step %arg2 {
+    // CHECK: Block: 3
+    // CHECK-NEXT: LiveIn: arg6@0 val_7 val_8
+    // CHECK-NEXT: LiveOut:{{ *$}}
+    %2 = addi %0, %1 : i32
+    store %2, %buffer[] : memref<i32>
+  }
+  return %1 : i32
+}