[MBP] Reduce code size by running tail merging in MBP

[haicheng]

Summary

The code layout that TailMerging (inside BranchFolding) works on is not the final layout optimized based on the branch probability. Generally, after BlockPlacement, many new merging opportunities emerge. My motivation example (also the test case) is like this in ARM assembly

     b       L5
L1:
     mov     w9, w8
     b       L5
L2:
     mov     w9, w8
     b       L5
L3:
     mov     w9, w8
     b       L5
L4:
     mov     w9, w8
L5:
      ldr     x8, [x21,#624]

L1-L5 can only be branched into. The example can be reduced to

     b       L5
L4:
     mov     w9, w8
L5:
   ldr     x8, [x21,#624]

The predecessors of L1-L4 now all branch into L4. Branch Folding should be able to simplify the code in the tail-merge phase, but it fails. In this example, the tiny MBBs (L1-L4) in the Branch Folding pass are at the places where they are fallthroughs of their individual predecessors. Merging L1-L4 in the Branch Folding requires inserting extra unconditional branches which makes Tail Merging give up. After MBP, L1-L4 are no long fallthroughs and can be easily merged as shown in the example.

This patch calls Tail Merging when it finds MBP changes the branches and calls MBP again if Tail Merging merges anything. Tail merging updates MachineLoopInfo and MachineBlockFreqInfo so that MBP can use them later. The table below shows the number of instructions removed and the impact to the performance in a AArch64 device (plus is improvement) when running SPEC2006.

	perf (%)	static instruction count
INT
astar	-0.49	-7
bzip2	0.40	-110
gcc	-0.11	-13,006
gobmk	1.48	-1,716
h264ref	0.47	-684
hmmer	-0.32	-391
libquantum	0.90	-4
mcf	-0.14	-4
omnetpp	-0.58	-1,980
perlbench	1.53	-4,176
sjeng	-0.77	-338
xalancbmk	-0.55	-4,183
FLOAT
soplex	-0.22	-395
dealII	0.34	-186
milc	-0.16	-34
namd	-0.18	-104
povray	2.07	-1,785
sphinx3	-0.11	-112

This patch also depends on three other trivial patches: D20177 (make it possible to optimize the branch directions after tail merging), D20184 (make it possible to use updated MachineBlockFreqInfo in MBP), and D19955 (make it possible to know the branches are updated by MBP or not)

One test case (arm-and-tst-peephole.ll) is slightly rewritten by reversing one branch condition. The probability of both branch directions are 50/50 so I think the modification is okay.

[deadalnix]

I've noticed this bad pattern in my code, thanks for tackling this.

lib/CodeGen/MachineBlockPlacement.cpp

1350

This is a bit confusing as this can return false in cases where basic blocks are scrambled but no branch was updated. Not that it is incorrect, but it goes against conventions. Also are we sure that this is the only cases that can crate opportunity for the optimization to take place ? Have you tried to just run the optimization every time ? I'd be interested to know if there is any changes.

1467

Maybe you could use a unique pointer here.

1479

Out of curiosity, do you have example of hardware doing this ?

1496

Worth looping maybe ?

1518

Remove once you use unique ptr.

[majnemer]

lib/CodeGen/MachineBlockPlacement.cpp

1479

WebAssembly IIRC.

[haicheng]

lib/CodeGen/MachineBlockPlacement.cpp

1479

I know old AMD GPU had this requirement. Its IL has instructions like "if_xxx" and "endif".

[sunfish]

lib/CodeGen/MachineBlockPlacement.cpp

1479

WebAssembly has flexible control flow and is ok with tail merging and most other optimizations, so we're no longer using the requiresStructuredCFG() hook.

[haicheng]

lib/CodeGen/MachineBlockPlacement.cpp

1350

Thank you very much, Amaury. I did some research about this. In short, running the optimization every time can capture more cases and I think I will do it in my next version. Below is the detail of my findings

1. Running the optimization every time captures five more cases in spec2000/2006. The same reason behind these cases is that the CFG is changed after the last time we call BranchFolding. These new opportunities exist before we start MBP.
2. You are right that it is possible to change the layout without changing any branch. I managed to create such a case, but there is no new tail merging opportunity in this case.
3. On average across spec2006, 74% of MFs need to update at least one branch to change the layout. The rest either does not need to change the layout or can change the layout without modifying any branch.
4. I think updateTerminator() can capture all the changes of fallthrough MBBs which is the only thing interesting to me. In D19955, if updateTerminator() finds its layout successor is inconsistent with the current branch, it always returns true. So, if running tail merging every time is too much, my current approach can still find all the cases caused by the MBP (I definitely need to make some changes to comply with the convention).

I will look into your looping suggestion as next.

[gberry]

Removing myself as others seem to be handling review

[haicheng]

Post Escha's comment.

lib/CodeGen/MachineBlockPlacement.cpp

1479

Ours has that requirement. We don’t generally allow any CFG modification after structurization, which takes place in the pre-ISel phase. Generic block placement is fine though.

—escha

[haicheng]

lib/CodeGen/MachineBlockPlacement.cpp

1496

I did some research on spec2006 about looping. Nine benchmarks can further remove instructions. gcc, omnetpp, and perlbench can remove 1000+ instructions. 83.5% MFs across spec2006 only need one iteration, 15.3% MFs need two iterations. The largest iteration number is five which is needed by 0.03% MFs.

It seems promising to pursue, but I think I will do the looping in the next patch after this one stays in the tree for a while.

[mcrosier]

Officially adding Amaury as a review.

[haicheng]

Address Amaury's comments. Rebase, use unique_ptr, always call tail merging.

[mcrosier]

Looks to be in good shape.

test/CodeGen/AArch64/tailmerging_in_mbp.ll

2

Please add a space before RUN.

[deadalnix]

lib/CodeGen/MachineBlockPlacement.cpp

1352

Alright, that is some very good findings. I don't mind if this is taken care of now or in subsequent diffs, but it seems like there is some more juice to squeeze on that one.

lib/CodeGen/BranchFolding.h

 #include "llvm/Support/BlockFrequency.h"
 #include <vector>
 
 namespace llvm {
   class MachineBlockFrequencyInfo;
   class MachineBranchProbabilityInfo;
   class MachineFunction;
   class MachineModuleInfo;
+  class MachineLoopInfo;
   class RegScavenger;
   class TargetInstrInfo;
   class TargetRegisterInfo;
 
   /// \brief This class keeps track of branch frequencies of newly created
   /// blocks and tail-merged blocks.
   class MBFIWrapper {
   public:
namespace llvm {
   };
 
   class LLVM_LIBRARY_VISIBILITY BranchFolder {
   public:
     explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
                           MBFIWrapper &MBFI,
                           const MachineBranchProbabilityInfo &MBPI);
 
-    bool OptimizeFunction(MachineFunction &MF,
-                          const TargetInstrInfo *tii,
-                          const TargetRegisterInfo *tri,
-                          MachineModuleInfo *mmi);
+    bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
+                          const TargetRegisterInfo *tri, MachineModuleInfo *mmi,
+                          MachineLoopInfo *mli = nullptr,
+                          bool AfterPlacement = false);
+
   private:
     class MergePotentialsElt {
       unsigned Hash;
       MachineBasicBlock *Block;
     public:
       MergePotentialsElt(unsigned h, MachineBasicBlock *b)
         : Hash(h), Block(b) {}
 
public:
         getMergePotentialsElt().setBlock(MBB);
       }
       void setTailStartPos(MachineBasicBlock::iterator Pos) {
         TailStartPos = Pos;
       }
     };
     std::vector<SameTailElt> SameTails;
 
+    bool AfterBlockPlacement;
     bool EnableTailMerge;
     bool EnableHoistCommonCode;
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     MachineModuleInfo *MMI;
+    MachineLoopInfo *MLI;
     RegScavenger *RS;
 
     MBFIWrapper &MBBFreqInfo;
     const MachineBranchProbabilityInfo &MBPI;
 
     bool TailMergeBlocks(MachineFunction &MF);
     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
                        MachineBasicBlock* PredBB);

lib/CodeGen/BranchFolding.cpp

 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
while (!MBB->succ_empty())
     MBB->removeSuccessor(MBB->succ_end()-1);
 
   // Avoid matching if this pointer gets reused.
   TriedMerging.erase(MBB);
 
   // Remove the block.
   MF->erase(MBB);
   FuncletMembership.erase(MBB);
+  if (MLI)
+    MLI->removeBlock(MBB);
 }
 
 /// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
 /// followed by terminators, and if the implicitly defined registers are not
 /// used by the terminators, remove those implicit_def's. e.g.
 /// BB1:
 ///   r0 = implicit_def
 ///   r1 = implicit_def
while (I != FirstTerm) {
     ++I;
     MBB->erase(ImpDefMI);
   }
 
   return true;
 }
 
 /// OptimizeFunction - Perhaps branch folding, tail merging and other
-/// CFG optimizations on the given function.
+/// CFG optimizations on the given function.  Block placement changes the layout
+/// and may create new tail merging opportunities.
 bool BranchFolder::OptimizeFunction(MachineFunction &MF,
                                     const TargetInstrInfo *tii,
                                     const TargetRegisterInfo *tri,
-                                    MachineModuleInfo *mmi) {
+                                    MachineModuleInfo *mmi,
+                                    MachineLoopInfo *mli, bool AfterPlacement) {
   if (!tii) return false;
 
   TriedMerging.clear();
 
+  AfterBlockPlacement = AfterPlacement;
   TII = tii;
   TRI = tri;
   MMI = mmi;
+  MLI = mli;
   RS = nullptr;
 
   // Use a RegScavenger to help update liveness when required.
   MachineRegisterInfo &MRI = MF.getRegInfo();
   if (MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF))
     RS = new RegScavenger();
   else
     MRI.invalidateLiveness();
bool BranchFolder::OptimizeFunction(MachineFunction &MF,
   }
 
   // Recalculate funclet membership.
   FuncletMembership = getFuncletMembership(MF);
 
   bool MadeChangeThisIteration = true;
   while (MadeChangeThisIteration) {
     MadeChangeThisIteration    = TailMergeBlocks(MF);
-    MadeChangeThisIteration   |= OptimizeBranches(MF);
+    // No need to clean up if tail merging does not change anything after the
+    // block placement.
+    if (!AfterBlockPlacement || MadeChangeThisIteration)
+      MadeChangeThisIteration |= OptimizeBranches(MF);
     if (EnableHoistCommonCode)
       MadeChangeThisIteration |= HoistCommonCode(MF);
     MadeChange |= MadeChangeThisIteration;
   }
 
   // See if any jump tables have become dead as the code generator
   // did its thing.
   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
   NewMBB->transferSuccessors(&CurMBB);
 
   // Add an edge from CurMBB to NewMBB for the fall-through.
   CurMBB.addSuccessor(NewMBB);
 
   // Splice the code over.
   NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
 
+  // NewMBB belongs to the same loop as CurMBB.
+  if (MLI) 
+    if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
+      ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
+
   // NewMBB inherits CurMBB's block frequency.
   MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
 
   // For targets that use the register scavenger, we must maintain LiveIns.
   MaintainLiveIns(&CurMBB, NewMBB);
 
   // Add the new block to the funclet.
   const auto &FuncletI = FuncletMembership.find(&CurMBB);
bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
   return MadeChange;
 }
 
 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
   bool MadeChange = false;
   if (!EnableTailMerge) return MadeChange;
 
   // First find blocks with no successors.
+  // Block placement does not create new tail merging opportunities for these
+  // blocks.
+  if (!AfterBlockPlacement) {
     MergePotentials.clear();
     for (MachineBasicBlock &MBB : MF) {
       if (MergePotentials.size() == TailMergeThreshold)
         break;
       if (!TriedMerging.count(&MBB) && MBB.succ_empty())
         MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
     }
 
     // If this is a large problem, avoid visiting the same basic blocks
     // multiple times.
     if (MergePotentials.size() == TailMergeThreshold)
       for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
         TriedMerging.insert(MergePotentials[i].getBlock());
 
     // See if we can do any tail merging on those.
     if (MergePotentials.size() >= 2)
       MadeChange |= TryTailMergeBlocks(nullptr, nullptr);
+  }
 
   // Look at blocks (IBB) with multiple predecessors (PBB).
   // We change each predecessor to a canonical form, by
   // (1) temporarily removing any unconditional branch from the predecessor
   // to IBB, and
   // (2) alter conditional branches so they branch to the other block
   // not IBB; this may require adding back an unconditional branch to IBB
   // later, where there wasn't one coming in.  E.g.
for (MachineBasicBlock *PBB : I->predecessors()) {
       // Visit each predecessor only once.
       if (!UniquePreds.insert(PBB).second)
         continue;
 
       // Skip blocks which may jump to a landing pad. Can't tail merge these.
       if (PBB->hasEHPadSuccessor())
         continue;
 
+      // Bail out if the loop header (IBB) is not the top of the loop chain
+      // after the block placement.  Otherwise, the common tail of IBB's
+      // predecessors may become the loop top if block placement is called again
+      // and the predecessors may branch to this common tail.
+      // FIXME: Relaxed this check if the algorithm of finding loop top is
+      // changed in MBP.
+      if (AfterBlockPlacement && MLI)
+        if (MachineLoop *ML = MLI->getLoopFor(IBB))
+          if (IBB == ML->getHeader() && ML == MLI->getLoopFor(PBB))
+            continue;
+
       MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
       SmallVector<MachineOperand, 4> Cond;
       if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) {
         // Failing case: IBB is the target of a cbr, and we cannot reverse the
         // branch.
         SmallVector<MachineOperand, 4> NewCond(Cond);
         if (!Cond.empty() && TBB == IBB) {
           if (TII->ReverseBranchCondition(NewCond))

lib/CodeGen/MachineBlockPlacement.cpp

 // sequential chains where allowed by the CFG (or demanded by heavy
 // probabilities). Finally, it walks the blocks in topological order, and the
 // first time it reaches a chain of basic blocks, it schedules them in the
 // function in-order.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
+#include "BranchFolding.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
cl::desc("Cost that models the probablistic risk of an instruction "
              "misfetch due to a jump comparing to falling through, whose cost "
              "is zero."),
     cl::init(1), cl::Hidden);
 
 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
                                       cl::desc("Cost of jump instructions."),
                                       cl::init(1), cl::Hidden);
 
+static cl::opt<bool>
+BranchFoldPlacement("branch-fold-placement",
+              cl::desc("Perform branch folding during placement. "
+                       "Reduces code size."),
+              cl::init(true), cl::Hidden);
+
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
 }
 
 namespace {
 /// \brief A chain of blocks which will be laid out contiguously.

 class MachineBlockPlacement : public MachineFunctionPass {
   /// \brief A typedef for a block filter set.
   typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
 
   /// \brief A handle to the branch probability pass.
   const MachineBranchProbabilityInfo *MBPI;
 
   /// \brief A handle to the function-wide block frequency pass.
-  const MachineBlockFrequencyInfo *MBFI;
+  MBFIWrapper *MBFI;
 
   /// \brief A handle to the loop info.
-  const MachineLoopInfo *MLI;
+  MachineLoopInfo *MLI;
 
   /// \brief A handle to the target's instruction info.
   const TargetInstrInfo *TII;
 
   /// \brief A handle to the target's lowering info.
   const TargetLoweringBase *TLI;
 
   /// \brief A handle to the post dominator tree.
class MachineBlockPlacement : public MachineFunctionPass {
   MachineBasicBlock *findBestLoopExit(MachineFunction &F, MachineLoop &L,
                                       const BlockFilterSet &LoopBlockSet);
   BlockFilterSet collectLoopBlockSet(MachineFunction &F, MachineLoop &L);
   void buildLoopChains(MachineFunction &F, MachineLoop &L);
   void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB,
                   const BlockFilterSet &LoopBlockSet);
   void rotateLoopWithProfile(BlockChain &LoopChain, MachineLoop &L,
                              const BlockFilterSet &LoopBlockSet);
-  void buildCFGChains(MachineFunction &F);
+  bool buildCFGChains(MachineFunction &F);
   void optimizeBranches(MachineFunction &F);
   void alignBlocks(MachineFunction &F);
 
 public:
   static char ID; // Pass identification, replacement for typeid
   MachineBlockPlacement() : MachineFunctionPass(ID) {
     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnMachineFunction(MachineFunction &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineBranchProbabilityInfo>();
     AU.addRequired<MachineBlockFrequencyInfo>();
     AU.addRequired<MachineDominatorTree>();
     AU.addRequired<MachineLoopInfo>();
+    AU.addRequired<TargetPassConfig>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 };
 }
 
 char MachineBlockPlacement::ID = 0;
 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement",
if (!LoopBlockSet.empty()) {
                << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
                << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
                << "  Bad block:    " << getBlockName(LoopBB) << "\n";
     }
     assert(!BadLoop && "Detected problems with the placement of this loop.");
   });
 }
 
-void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
+bool MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
   // Ensure that every BB in the function has an associated chain to simplify
   // the assumptions of the remaining algorithm.
   SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
   for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
     MachineBasicBlock *BB = &*FI;
     BlockChain *Chain =
         new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
     // Also, merge any blocks which we cannot reason about and must preserve
if (!FunctionBlockSet.empty()) {
       for (MachineBasicBlock *RemainingBB : FunctionBlockSet)
         dbgs() << "Function contains blocks never placed into a chain!\n"
                << "  Bad block:    " << getBlockName(RemainingBB) << "\n";
     }
     assert(!BadFunc && "Detected problems with the block placement.");
   });
 
   // Splice the blocks into place.
+  bool isBrUpdated = false;
   MachineFunction::iterator InsertPos = F.begin();
   for (MachineBasicBlock *ChainBB : FunctionChain) {
     DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain "
                                                        : "          ... ")
                  << getBlockName(ChainBB) << "\n");
     if (InsertPos != MachineFunction::iterator(ChainBB))
       F.splice(InsertPos, ChainBB);
     else
if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) {
       //      before layout, and no longer fall-through it after layout; or
       //   o. just opposite.
       //
       // AnalyzeBranch() may return erroneous value for FBB when these two
       // situations take place. For the first scenario FBB is mistakenly set
       // NULL; for the 2nd scenario, the FBB, which is expected to be NULL,
       // is mistakenly pointing to "*BI".
       //
-      PrevBB->updateTerminator();
+      isBrUpdated |= PrevBB->updateTerminator();
     }
   }
 
   // Fixup the last block.
   Cond.clear();
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
   if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond))
-    F.back().updateTerminator();
+    isBrUpdated |= F.back().updateTerminator();
+
+  return isBrUpdated;
 }
 
 void MachineBlockPlacement::optimizeBranches(MachineFunction &F) {
   BlockChain &FunctionChain = *BlockToChain[&F.front()];
   SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
 
   // Now that all the basic blocks in the chain have the proper layout,
   // make a final call to AnalyzeBranch with AllowModify set.
   // Indeed, the target may be able to optimize the branches in a way we
   // cannot because all branches may not be analyzable.
bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
   // Check for single-block functions and skip them.
   if (std::next(F.begin()) == F.end())
     return false;
 
   if (skipFunction(*F.getFunction()))
     return false;
 
   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
-  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
+  MBFI = new MBFIWrapper(getAnalysis<MachineBlockFrequencyInfo>());
   MLI = &getAnalysis<MachineLoopInfo>();
   TII = F.getSubtarget().getInstrInfo();
   TLI = F.getSubtarget().getTargetLowering();
   MDT = &getAnalysis<MachineDominatorTree>();
   assert(BlockToChain.empty());
 
+  bool LayoutChange = buildCFGChains(F);
+
+  // Changing the layout can create new tail merging opportunities.
+  TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
+  // TailMerge can create jump into if branches that make CFG irreducible for
+  // HW that requires structurized CFG.
+  bool EnableTailMerge = !F.getTarget().requiresStructuredCFG() &&
+                         PassConfig->getEnableTailMerge() &&
+                         BranchFoldPlacement;
+  // No tail merging opportunities if the block number is less than four.
+  if (LayoutChange && F.size() > 3 && EnableTailMerge) {
+    BranchFolder BF(/*EnableTailMerge=*/true, /*CommonHoist=*/false, *MBFI,
+                    *MBPI);
+
+    if (BF.OptimizeFunction(F, TII, F.getSubtarget().getRegisterInfo(),
+                            getAnalysisIfAvailable<MachineModuleInfo>(), MLI,
+                            /*AfterBlockPlacement=*/true)) {
+      // Redo the layout if tail merging creates/removes/moves blocks.
+      BlockToChain.clear();
+      ChainAllocator.DestroyAll();
       buildCFGChains(F);
+    }
+  }
+
   optimizeBranches(F);
   alignBlocks(F);
 
   BlockToChain.clear();
   ChainAllocator.DestroyAll();
 
   if (AlignAllBlock)
     // Align all of the blocks in the function to a specific alignment.
     for (MachineBasicBlock &MBB : F)
       MBB.setAlignment(AlignAllBlock);
   else if (AlignAllNonFallThruBlocks) {
     // Align all of the blocks that have no fall-through predecessors to a
     // specific alignment.
     for (auto MBI = std::next(F.begin()), MBE = F.end(); MBI != MBE; ++MBI) {
       auto LayoutPred = std::prev(MBI);
       if (!LayoutPred->isSuccessor(&*MBI))
         MBI->setAlignment(AlignAllNonFallThruBlocks);
     }
   }
 
+  delete MBFI;
   // We always return true as we have no way to track whether the final order
   // differs from the original order.
   return true;
 }
 
 namespace {
 /// \brief A pass to compute block placement statistics.
 ///

test/CodeGen/AArch64/tailmerging_in_mbp.ll

+;RUN: llc <%s -march=aarch64 | FileCheck %s
+
+; CHECK-LABEL: test:
+; CHECK:       .LBB0_7
+; CHECK:         b.hi .LBB0_2
+; CHECK-NEXT:    b  .LBB0_9
+; CHECK-NEXT:  .LBB0_8
+; CHECK-NEXT:    mov   x8, x9
+; CHECK-NEXT:  .LBB0_9 
+define i64 @test(i64 %n, i64* %a, i64* %b, i64* %c, i64* %d, i64* %e, i64* %f) {
+entry:
+  %cmp28 = icmp sgt i64 %n, 1
+  br i1 %cmp28, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.body.lr.ph, %if.end
+  %j = phi i64 [ %n, %entry ], [ %div, %if.end ]
+  %div = lshr i64 %j, 1
+  %a.arrayidx = getelementptr inbounds i64, i64* %a, i64 %div
+  %a.j = load i64, i64* %a.arrayidx
+  %b.arrayidx = getelementptr inbounds i64, i64* %b, i64 %div
+  %b.j = load i64, i64* %b.arrayidx
+  %cmp.i = icmp slt i64 %a.j, %b.j
+  br i1 %cmp.i, label %for.end.loopexit, label %cond.false.i
+
+cond.false.i:                                     ; preds = %for.body
+  %cmp4.i = icmp sgt i64 %a.j, %b.j
+  br i1 %cmp4.i, label %if.end, label %cond.false6.i
+
+cond.false6.i:                                    ; preds = %cond.false.i
+  %c.arrayidx = getelementptr inbounds i64, i64* %c, i64 %div
+  %c.j = load i64, i64* %c.arrayidx
+  %d.arrayidx = getelementptr inbounds i64, i64* %d, i64 %div
+  %d.j = load i64, i64* %d.arrayidx
+  %cmp9.i = icmp slt i64 %c.j, %d.j
+  br i1 %cmp9.i, label %for.end.loopexit, label %cond.false11.i
+
+cond.false11.i:                                   ; preds = %cond.false6.i
+  %cmp14.i = icmp sgt i64 %c.j, %d.j
+  br i1 %cmp14.i, label %if.end, label %cond.false12.i
+
+cond.false12.i:                           ; preds = %cond.false11.i
+  %e.arrayidx = getelementptr inbounds i64, i64* %e, i64 %div
+  %e.j = load i64, i64* %e.arrayidx
+  %f.arrayidx = getelementptr inbounds i64, i64* %f, i64 %div
+  %f.j = load i64, i64* %f.arrayidx
+  %cmp19.i = icmp sgt i64 %e.j, %f.j
+  br i1 %cmp19.i, label %if.end, label %for.end.loopexit
+
+if.end:                                           ; preds = %cond.false12.i, %cond.false11.i, %cond.false.i
+  %cmp = icmp ugt i64 %j, 3
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %cond.false12.i, %cond.false6.i, %for.body, %if.end
+  %j.0.lcssa.ph = phi i64 [ %j, %cond.false12.i ], [ %j, %cond.false6.i ], [ %j, %for.body ], [ %div, %if.end ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %j.0.lcssa = phi i64 [ %n, %entry ], [ %j.0.lcssa.ph, %for.end.loopexit ]
+  %j.2 = add i64 %j.0.lcssa, %n
+  %j.3 = mul i64 %j.2, %n
+  %j.4 = add i64 %j.3, 10
+  ret i64 %j.4 
+}

test/CodeGen/ARM/arm-and-tst-peephole.ll

 ; V8-LABEL: %tailrecurse.switch
 ; V8: cmp
 ; V8-NEXT: beq
 ; V8-NEXT: %tailrecurse.switch
 ; V8: cmp
 ; V8-NEXT: beq
 ; V8-NEXT: %tailrecurse.switch
 ; V8: cmp
-; V8-NEXT: bne
+; V8-NEXT: beq
 ; V8-NEXT: b  
 ; The trailing space in the last line checks that the branch is unconditional
   switch i32 %and, label %sw.epilog [
     i32 1, label %sw.bb
     i32 3, label %sw.bb6
     i32 2, label %sw.bb8
   ], !prof !1