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

 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
 
 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
 
 #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"
 #include <cassert>
 
 namespace llvm {
 
 class BlockFrequencyInfo;

 /// successor Sing. In this case the branch will be updated with Sing instead of
 /// BB, and BB will still be merged into its predecessor and removed.
 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
                                LoopInfo *LI = nullptr,
                                MemorySSAUpdater *MSSAU = nullptr,
                                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);
 
 /// Replace all uses of an instruction (specified by BI) with a value, then
 /// remove and delete the original instruction.
 void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
                           BasicBlock::iterator &BI, Value *V);

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

if (DTU) {
     DTU->deleteBB(BB);
   } else {
     BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
   }
 
   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();
+      (void)Fold;
+      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.
 ///
 /// BackwardScan strategy:
 /// ----------------------
 /// Given a sequence of consecutive DbgValueInst like this
 ///

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

if (Count != 1) {
     DTU.applyUpdatesPermissive(DTUpdates);
   }
 
   // Merge adjacent basic blocks, if possible.
   SmallPtrSet<BasicBlock *, 16> MergeBlocks;
   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();
 
   // At this point, the code is well formed.  We now do a quick sweep over the
   // inserted code, doing constant propagation and dead code elimination as we
   // go.
   simplifyLoopAfterUnroll(SubLoop, true, LI, SE, DT, AC, TTI);
   simplifyLoopAfterUnroll(L, !CompletelyUnroll && Count > 1, LI, SE, DT, AC,