Create utility function to Merge Adjacent Basic Blocks

[sidbav]

Summary

The following code from /llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp can be used by other transformations:

while (!MergeBlocks.empty()) {	
    BasicBlock *BB = *MergeBlocks.begin();
    BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator());	
    if (Term && Term->isUnconditional() && L->contains(Term->getSuccessor(0))) {	
      BasicBlock *Dest = Term->getSuccessor(0);	
      BasicBlock *Fold = Dest->getUniquePredecessor();	
      if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {	
        // Don't remove BB and add Fold as they are the same BB	
        assert(Fold == BB);	
        (void)Fold;	
        MergeBlocks.erase(Dest);	
      } else	
        MergeBlocks.erase(BB);	
    } else	
      MergeBlocks.erase(BB);	
  }

Hence it should be separated into its own utility function.

[asbirlea]

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

106

Include a comment that if L is given, the blocks merged into their predecessors must be in L.

A pretty verbose renaming suggestion: MergeBlockSuccessorsIntoGivenBlocks, since this is not merging any adjacent blocks.

If the intent was "if L not given, then MergeBlocks.contains(Dest)", include that in code; this is not a usecase in unrollAndJam, so I cannot tell, but reading the method comment and name this is what I'd assume the method does. Or, rename to something more specific than "adjacentBlocks".

I do not understand this comment:

In addition, a call to MergeBlockIntoPredecessor where
/// the block following the terminal branch is passed must
/// return true.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

330

I don't think the UniquePredecessor argument is needed. The method MergeBlockIntoPredecessor will not merge unless Dest has a unique predecessor.

[sidbav]

Updated the code based on review.

[sidbav]

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

106

Updated comments to include a comment regarding L.
Updated function name to be more verbose, and updated comments so the last sentences makes more sense.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

330

Yes that is a good point, and the code has been updated to reflect this change.

[asbirlea]

Thanks! LGTM with 2 nits in the comment section.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

103

Nit: s/branch and if L/branch. If L/

104

This reads as: the call to MergeBlockIntoPredecessor must always return true, which is not the case.
I think what you mean is:

"This utility calls on another utility: MergeBlockIntoPredecessor. Blocks are successfully merged when the call to MergeBlockIntoPredecessor returns true."

[sidbav]

Update function description comments based on review.

[sidbav]

Updated comments based on review.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstrTypes.h"

                                MemoryDependenceResults *MemDep = nullptr,
                                bool PredecessorWithTwoSuccessors = false);
 
+/// Merge block(s) sucessors, if possible. Return true if at least two
+/// of the blocks were merged together.
+/// In order to merge, each block must be terminated by an unconditional
+/// branch. If L is provided, then the blocks merged into their predecessors
+/// must be in L. In addition, This utility calls on another utility:
+/// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to
+/// MergeBlockIntoPredecessor returns true.
+bool MergeBlockSuccessorsIntoGivenBlocks(
+    SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L = nullptr,
+    DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr);
+
 /// Try to remove redundant dbg.value instructions from given basic block.
 /// Returns true if at least one instruction was removed.
 bool RemoveRedundantDbgInstrs(BasicBlock *BB);

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

   return true;
 }
 
+bool llvm::MergeBlockSuccessorsIntoGivenBlocks(
+    SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
+    LoopInfo *LI) {
+  assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");
+
+  bool BlocksHaveBeenMerged = false;
+  while (!MergeBlocks.empty()) {
+    BasicBlock *BB = *MergeBlocks.begin();
+    BasicBlock *Dest = BB->getSingleSuccessor();
+    if (Dest && (!L || L->contains(Dest))) {
+      BasicBlock *Fold = Dest->getUniquePredecessor();
+      if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {
+        assert(Fold == BB &&
+               "Expecting BB to be unique predecessor of the Dest block");
+        MergeBlocks.erase(Dest);
+        BlocksHaveBeenMerged = true;
+      } else
+        MergeBlocks.erase(BB);
+    } else
+      MergeBlocks.erase(BB);
+  }
+  return BlocksHaveBeenMerged;
+}
+
 /// Remove redundant instructions within sequences of consecutive dbg.value
 /// instructions. This is done using a backward scan to keep the last dbg.value
 /// describing a specific variable/fragment.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

   MergeBlocks.insert(ForeBlocksLast.begin(), ForeBlocksLast.end());
   MergeBlocks.insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end());
   MergeBlocks.insert(AftBlocksLast.begin(), AftBlocksLast.end());
-  while (!MergeBlocks.empty()) {
-    BasicBlock *BB = *MergeBlocks.begin();
-    BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator());
-    if (Term && Term->isUnconditional() && L->contains(Term->getSuccessor(0))) {
-      BasicBlock *Dest = Term->getSuccessor(0);
-      BasicBlock *Fold = Dest->getUniquePredecessor();
-      if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
-        // Don't remove BB and add Fold as they are the same BB
-        assert(Fold == BB);
-        (void)Fold;
-        MergeBlocks.erase(Dest);
-      } else
-        MergeBlocks.erase(BB);
-    } else
-      MergeBlocks.erase(BB);
-  }
+
+  MergeBlockSuccessorsIntoGivenBlocks(MergeBlocks, L, &DTU, LI);
+
   // Apply updates to the DomTree.
   DT = &DTU.getDomTree();