Remove equal BBs from a function

[avt77]

Summary

It's one of the issues raised in PR27136: the duplicated epilog BBs in a function. This patch introduces the possible decision. It's only the preliminary version of the patch that's why we have a lot of DEBUGs inside it and that's why it's still buggy, e.g. we can't build bootstrap if apply this patch. The main purpose of this patch is to introduce intention and to get the first feedback on the suggested approach.

[davide]

Is it possible to address this at IR level? Anyway, comments inline.

lib/CodeGen/RemoveEqualBB.cpp

2

FuncletLayout ?

11–13

This comment doesn't seem quite right.

48–49

You seem to pass MLI around but you don't use for anything real (the only line that actually uses it is commented out).

54

Why do you need the dominator here?

192–197

Commented out code.

253–257

Commented out code.

264–267

ditto.

lib/CodeGen/TargetPassConfig.cpp

670–671

Why are you putting at this point in the pipeline?

test/CodeGen/X86/loop-search.ll

1–3

This needs more tests.

[avt77]

I implemented requirements raised by Davide and fix an issue with bootstrap: now it works properly. Next steps: I'm going to collect statistic on bootsrap such as: number of removed BBs and instructions inside those BBs, the total size changing, compile time. When it's done I'm going to extend transformation with other kinds of BBs (e.g. parts of EH, -O1 (size) optimizations) and/or terminators.

[davide]

You fixed all the style comments, so thanks. But you glossed over the design questions I asked. In particular, before getting performance numbers, there are two questions unanswered:

1. Why can't you do this in the middle-end? I assume there's a valid reason, but I'll be happy if you can actually elaborate.
2. Granted we want this in the backend, why are you putting the pass at that specific point in the pipeline?

[avt77]

Now I found and fixed issues raised during bootstrap. The bootstrap works perfectly now. And I got some numbers: on such huge files like clang, llc, etc. we have about 0.1% size of file decreasing. At the moment I'm using the most possible conservative approach but collected numbers show that we can get better results: it's for sure.

Davide, I'm doing this transformation at this point of pipeline because I'd like to do it after all other layout related transformations. Is it the answer on your question? And the same answer about middle level: I'd like to do this transformation when all others are done but there are still something what can be optimized. Maybe I'm wrong?

[MatzeB]

Did you see the new MachineOutliner yet? It is also merging equivalent code but is not restricted to a single basic block but find duplicate sequences of instructions and can also merge across functions.

[MatzeB]

We also have TailMerging (part of BranchFolding) which should merges equivalent instruction sequences going to a return and is enabled by default. Apparently it doesn't catch the case in loop-search.ll (and you didn't provide additional examples/tests unfortunately) but we should better search for bugs there instead of adding a new pass.

[avt77]

Matthias,
Thank you for the fast reply.

! In D30572#707521, @MatzeB wrote:
Did you see the new MachineOutliner yet? It is also merging equivalent code but is not restricted to a single basic block but find duplicate sequences of instructions and can also merge across functions.

Now, I did not see it but it seems it does more complex thing: inside my patch I'm calling it "candidates for -O1 optimizations. That's fine that you did it already!

In D30572#707532, @MatzeB wrote:

We also have TailMerging (part of BranchFolding) which should merges equivalent instruction sequences going to a return and is enabled by default. Apparently it doesn't catch the case in loop-search.ll (and you didn't provide additional examples/tests unfortunately) but we should better search for bugs there instead of adding a new pass.

I've seen this code but it did not work for me that's why I implemented the new pass. But I deadly agree that it's better to fix the possible bugs inside this pass instead of adding a new pass: I'll try to redesign my job.
One comment: I bootstrapped Clang with my patch and found hundreds of duplicated BBs. Especially many of them were accessed through Jump Tables. Do you know about this issue?
And more: TailMerging works with return only or with unconditional jumps as well?

[MatzeB]

In D30572#707568, @avt77 wrote:

And more: TailMerging works with return only or with unconditional jumps as well?

Given something like

BB0:

A
B
C
RET

BB1:

C
RET

BB2:

B
C
RET

tail merging should give you something like:

BB0:

A
B
# fallthrough

BB1:

C
RET

BB2:

B
JMP BB1

That's at least my understanding, but I am no expert in the pass. Better do your own experiments/code reading.

[paquette]

I think the comments in this pass could use some improvement. It would be nice to be able to get the gist of what's going on without having to read through all of the code.

Does this pass only remove identical MachineBasicBlocks that end in returns/tail calls? If so, like Matthias said, we might just have a TailMerging bug. If it's more general, then what does this pass do aside from fix the bug in the test?

Also, since this is a new pass, there should be a new test written for it as well as the modification to the test you already included.

(... also I'm apparently also jpaquette in the reviewer list. Apparently I signed up to Phabricator once years ago and forgot entirely. Weird.)

lib/CodeGen/RemoveEqualBB.cpp

10–11

I don't really understand this comment. It makes it sound like what you're trying to do is remove any two equal basic blocks in the program. Maybe expand on it a bit and give some motivation? It would make the rest of the code easier to understand.

It also might be good to rename the pass for similar reasons; if I saw this as a command line option I might be a little confused.

71

MBB ought to never be null, so you can pass it as a reference.

72

Generally try to avoid use of auto when the type isn't some huge template soup. In more complicated functions, it makes it a bit clearer what's going on.

78

This function should probably have a function explaining what it's doing and the responsibilities of each parameter.

Also, a bunch of these could probably be references rather than pointers. That'd make it clear when things can't be null.

100–101

Might seem a tad pedantic, but comments should be full sentences. :) Also, watch out for spelling/grammar errors.

http://llvm.org/docs/CodingStandards.html#commenting

106

There are enough instances of MBB4Replace->getNumber() around here that it might be worth it to just give it its own variable. Say, MBB4ReplaceNumber or something?

130

The code above or below? The stuff below alters stuff in JTI, while this skips Pred if the condition holds.

147

You don't have to comment out asserts. In fact, it's a pretty good idea to use them a lot:

http://llvm.org/docs/CodingStandards.html#assert-liberally

165

This doesn't seem to be used anywhere.

167–170

This can probably all be removed?

177

Maybe "Basic blocks that will not be removed from F by the pass."

179–180

Similarly, "Basic blocks that will no longer be in F at the end of the pass."

183

I'd like it if X and Y were named more descriptively if only to remind me what they are later in the code. Even MBB1 and MBB2 or BB1 and BB2 would be helpful, since at least then I would know I'm talking about two MachineBasicBlocks.

http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

202

Variable names should start with capital letters. I would also give this a better name. Maybe EqualMBBs?

http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

242

Is this only an X86 pass? I would keep target-specific stuff out of the pass.

245

If you aren't using the commented out stuff yet, I'd remove it.

265–267

If there's only one statement in your if, you don't need the braces.

293–294

This seems like it can be removed.

[davide]

In D30572#699284, @avt77 wrote:

Now I found and fixed issues raised during bootstrap. The bootstrap works perfectly now. And I got some numbers: on such huge files like clang, llc, etc. we have about 0.1% size of file decreasing. At the moment I'm using the most possible conservative approach but collected numbers show that we can get better results: it's for sure.

Davide, I'm doing this transformation at this point of pipeline because I'd like to do it after all other layout related transformations. Is it the answer on your question? And the same answer about middle level: I'd like to do this transformation when all others are done but there are still something what can be optimized. Maybe I'm wrong?

Sorry, missed this one.
44 kilobytes on llc release (44MB in release) seem a saving really small to justify the complexity of a new pass.
You should really consider leveraging existing pass to do this transformation as already pointed out and even before that, you may want to conduct an analysis on small/medium/large size executables in order to understand what's the number of duplicated basic block and therefore what's the hypothetical gain.

Last but not least, why do you want this transformation ;) ?

[avt77]

Hi All,
Reading the sources of TailMerging Pass I discovered that it has special switch "tail-merge-size" allowing to resolve the issue from loop-serch.ll test. The default value of the switch is 3 but if I change it as 2 then everything works fine.
Because of that I decided to abandon this review :-(
I'm going to investigate the possibility to change the default value. If it is not allowed for any reasons (compile time, target specific requirements, etc.) I'll implement special hook in Target as it's suggested in sources.

Any thoughts about possible default value for "tail-merge-size"? I suppose it could be 1 because we can have a lot of BBs with single "ret" (or "unconditional jump" or ...) instruction and we'd like to merge all such BBs. The compilation time should not increase dramatically (from my point of view) but we need investigations of course.

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   extern char &OptimizePHIsID;
 
   /// StackSlotColoring - This pass performs stack slot coloring.
   extern char &StackSlotColoringID;
 
   /// \brief This pass lays out funclets contiguously.
   extern char &FuncletLayoutID;
 
+  /// \brief This pass removes identical tail BBs leaving only one of them.
+  extern char &RemoveEqualBBID;
+
   /// This pass inserts the XRay instrumentation sleds if they are supported by
   /// the target platform.
   extern char &XRayInstrumentationID;
 
   /// This pass inserts FEntry calls
   extern char &FEntryInserterID;
 
   /// \brief This pass implements the "patchable-function" attribute.

include/llvm/InitializePasses.h

 void initializeExternalAAWrapperPassPass(PassRegistry&);
 void initializeFEntryInserterPass(PassRegistry &);
 void initializeFinalizeMachineBundlesPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeFloat2IntLegacyPassPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeForwardControlFlowIntegrityPass(PassRegistry&);
 void initializeFuncletLayoutPass(PassRegistry &);
+void initializeRemoveEqualBBPass(PassRegistry &);
 void initializeFunctionImportLegacyPassPass(PassRegistry &);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
 void initializeGCOVProfilerLegacyPassPass(PassRegistry&);
 void initializeGVNLegacyPassPass(PassRegistry&);
 void initializeGlobalDCELegacyPassPass(PassRegistry&);
 void initializeGlobalMergePass(PassRegistry&);
 void initializeGlobalOptLegacyPassPass(PassRegistry&);

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   RegAllocBasic.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp
+  RemoveEqualBB.cpp
   RenameIndependentSubregs.cpp
   RegisterUsageInfo.cpp
   RegUsageInfoCollector.cpp
   RegUsageInfoPropagate.cpp
   ResetMachineFunctionPass.cpp
   SafeStack.cpp
   SafeStackColoring.cpp
   SafeStackLayout.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeDetectDeadLanesPass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeEarlyIfConverterPass(Registry);
   initializeExpandISelPseudosPass(Registry);
   initializeExpandPostRAPass(Registry);
   initializeFinalizeMachineBundlesPass(Registry);
   initializeFEntryInserterPass(Registry);
   initializeFuncletLayoutPass(Registry);
+  initializeRemoveEqualBBPass(Registry);
   initializeGCMachineCodeAnalysisPass(Registry);
   initializeGCModuleInfoPass(Registry);
   initializeIfConverterPass(Registry);
   initializeInterleavedAccessPass(Registry);
   initializeLiveDebugVariablesPass(Registry);
   initializeLiveIntervalsPass(Registry);
   initializeLiveStacksPass(Registry);
   initializeLiveVariablesPass(Registry);

lib/CodeGen/RemoveEqualBB.cpp

+//===-- RemoveEqualBB.cpp - Remove Equal BBs from a function ----------------=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements removing of equal basic blocks if there are such BBs
+// inside a function. Only one of such BBs leaves in th function
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/Analysis.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/Passes.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "remove-equal-bb"
+
+STATISTIC(NumEqBBsSurvived, "Number of survived (after transformation) BBs");
+STATISTIC(SizeEqBBsSurvived, "Size(in intructions) of survived BBs");
+STATISTIC(NumEqBBsErased, "Number of erased (in result of) transformation BBs");
+STATISTIC(SizeEqBBsErased, "Size(in intructions) of erased BBs");
+STATISTIC(NumEqBBCandidates, "Number of candidates for -O1 optimization");
+STATISTIC(SizeEqBBCandidates,
+          "Number of intructions which could be optimizad with -O1");
+
+static cl::opt<bool> RemoveEqBBs("remove-equal-bbs", cl::init(false),
+                                 cl::Hidden,
+                                 cl::desc("Remove equal Basic Blocks."));
+
+namespace {
+class RemoveEqualBB : public MachineFunctionPass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+  RemoveEqualBB() : MachineFunctionPass(ID) {
+    initializeRemoveEqualBBPass(*PassRegistry::getPassRegistry());
+  }
+  /// \brief A handle to the loop info.
+  MachineLoopInfo *MLI;
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<MachineLoopInfo>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+};
+}
+
+char RemoveEqualBB::ID = 0;
+char &llvm::RemoveEqualBBID = RemoveEqualBB::ID;
+
+INITIALIZE_PASS_BEGIN(RemoveEqualBB, "remove-equal-bb", "Remove identical BBs",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineBlockPlacement)
+INITIALIZE_PASS_END(RemoveEqualBB, "remove-equal-bb", "Remove identical BBs",
+                    false, false)
+
+static MachineBasicBlock *hasLayoutPredecessor(MachineBasicBlock *MBB) {
+  for (auto *Pred : MBB->predecessors()) {
+    if (Pred->isLayoutSuccessor(MBB))
+      return Pred;
+  }
+  return nullptr;
+}
+
+static bool Mark4Remove(SmallMapVector<unsigned, unsigned, 16> &BBsForRemove,
+                        SmallSet<unsigned, 16> &SurvivedBBs,
+                        MachineLoopInfo *MLI, MachineBasicBlock *MBB4Remove,
+                        MachineBasicBlock *MBB4Replace, MachineBasicBlock *X,
+                        MachineBasicBlock *Y) {
+  if (MBB4Remove->hasAddressTaken() || MLI->getLoopFor(MBB4Remove)) {
+    DEBUG(dbgs() << "We have BB#" << MBB4Remove->getNumber();
+          dbgs() << (MLI->getLoopFor(MBB4Remove) ? " inside loop\n"
+                                                 : " with address taken\n"););
+    return X->getNumber() < Y->getNumber(); // Let's deal with it later
+  }
+  if (auto *LP = hasLayoutPredecessor(MBB4Remove)) {
+    // TODO: at the moment we can't remove BB with Layout Predecessor
+    DEBUG(dbgs() << "REQBB: BB#" << MBB4Remove->getNumber()
+                 << " can't be removed because it has Layout Predecesser BB#"
+                 << LP->getNumber() << "\n");
+    // TODO: should we add MBB4Remove to survived?
+    return X->getNumber() < Y->getNumber();
+  }
+
+#ifndef NDEBUG
+  // The Replacement (MBB4Replace) could be removed "recursivly"
+  // that's why we need a loop below
+  int second = 0;
+#endif
+  while (auto V = BBsForRemove.lookup(MBB4Replace->getNumber())) {
+    DEBUG(dbgs() << (second++ ? "\t" : "") << "REQBB: MBB4Replace #"
+                 << MBB4Replace->getNumber()
+                 << " was replaced with BB#" << V << "\n");
+    SurvivedBBs.erase(MBB4Replace->getNumber()); // It can't be in the survived list
+    MBB4Replace = MBB4Replace->getParent()->getBlockNumbered(V);
+  }
+
+    if (MBB4Remove == MBB4Replace) {
+      DEBUG(dbgs() << "REQBB: BB#" << MBB4Remove->getNumber()
+                   << " can't be removed because MBB4Remove == MBB4Replace\n");
+      return false;
+    }
+
+  DEBUG(dbgs() << "Change successors of predecessors of  BB#"
+               << MBB4Remove->getNumber() << "\n");
+  auto *JTI = MBB4Remove->getParent()->getJumpTableInfo();
+
+  // We can't use predecessors from MBB4Remove directly because
+  // ReplaceUsesOfBlockWith destroys iterators
+  SmallVector<MachineBasicBlock *, 8> Predecessors(MBB4Remove->pred_begin(),
+                                                   MBB4Remove->pred_end());
+
+  for (auto *Pred : Predecessors) {
+    if (Pred->isSuccessor(MBB4Replace) && !Pred->isSuccessor(MBB4Remove))
+      continue; // The MBB4Replace is already successor of Pred
+    // TODO: This should be removed or it should be assertion
+    if (Pred->isSuccessor(MBB4Remove)) {
+      DEBUG(dbgs() << "Change successors of predecessor BB#"
+                   << Pred->getNumber() << "(instead of successor BB#"
+                   << MBB4Remove->getNumber() << " another BB#"
+                   << MBB4Replace->getNumber() << " will be used now.)\n");
+      if (JTI)
+        JTI->ReplaceMBBInJumpTables(MBB4Remove, MBB4Replace);
+      Pred->ReplaceUsesOfBlockWith(MBB4Remove, MBB4Replace);
+    } else {
+      DEBUG(dbgs() << "!!! In function '" << MBB4Remove->getParent()->getName()
+                   << "' predecessor BB#" << Pred->getNumber()
+                   << " does not have successor BB#" << MBB4Remove->getNumber()
+                   << " !!!\n Predecessor\n";
+            Pred->dump(); dbgs() << "Successor\n"; MBB4Remove->dump());
+    }
+  }
+  //  assert(MBB4Remove->pred_empty() && "We can't have predecessors here");
+  if (BBsForRemove.insert({MBB4Remove->getNumber(), MBB4Replace->getNumber()})
+          .second) {
+    DEBUG(dbgs() << "BB#" << MBB4Remove->getNumber()
+                 << (MBB4Remove->pred_size() ? " with" : " without");
+          dbgs() << " pred(s) will be removed and replaced with BB#"
+                 << MBB4Replace->getNumber() << "\n");
+    NumEqBBsErased++;
+    SizeEqBBsErased += MBB4Remove->size();
+  }
+  return X->getNumber() < Y->getNumber();
+}
+
+bool RemoveEqualBB::runOnMachineFunction(MachineFunction &F) {
+  // TODO: what's real minimum of BBs should we use?
+  if (!RemoveEqBBs || F.getNumBlockIDs() < 2)
+    return false;
+
+  MLI = &getAnalysis<MachineLoopInfo>();
+
+  // Renumber all of the machine basic blocks in the function, guaranteeing that
+  // the numbers agree with the position of the block in the function.
+  // To minmize defferences in tests we'll keep current numbering
+  //F.RenumberBlocks();
+
+  // MBBs keeps pointers to all Machine BBs of the given Machine Function
+  std::vector<MachineBasicBlock *> MBBs;
+  for (auto &I : F) {
+    MBBs.push_back(&I);
+  }
+  // A list of BBs which will be alived after the transformation
+  SmallSet<unsigned, 16> SurvivedBBs;
+  // A list of BBs which will be erased from the function after the
+  // transformation
+  SmallMapVector<unsigned, unsigned, 16> BBsForRemove;
+
+  std::stable_sort(MBBs.begin(), MBBs.end(), [&](MachineBasicBlock *X,
+                                                 MachineBasicBlock *Y) {
+    if (!X->size() || X->size() != Y->size() ||
+        X->succ_size() != Y->succ_size())
+      return X->getNumber() < Y->getNumber();
+    MachineBasicBlock::instr_iterator IY = Y->instr_begin();
+    MachineBasicBlock::instr_iterator IXE = X->instr_end();
+    for (MachineBasicBlock::instr_iterator IX = X->instr_begin(); IX != IXE;
+         IX++) {
+      if (IX->isIdenticalTo(*IY)) {
+        IY++;
+        continue;
+      }
+      return X->getNumber() < Y->getNumber();
+    }
+    // TODO: it's better to check successors before checking of instructions
+    // because most probably the number of successors is less than the number
+    // of instrs but we'd like to extend the suppoort of -O1
+    // (optimize for size)
+    bool equal = true;
+    for (auto *S : X->successors()) {
+      if (!Y->isSuccessor(S)) {
+        equal = false;
+        break;
+      }
+    }
+    if (!equal) {
+      NumEqBBCandidates++;
+      SizeEqBBCandidates += X->size();
+      DEBUG(dbgs() << "REQBB: In '" << F.getName()
+                   << "' we have candidates for -O1: BB#" <<
+                   X->getNumber()
+                   << " and BB#" << Y->getNumber() << "\n");
+      return X->getNumber() < Y->getNumber();
+    } else {
+      // We have 2 equal BBs. If one of them was already marked as survived then
+      // simply erase the second one
+      if (X->isEHPad() || X->isEHFuncletEntry() || X->isCleanupFuncletEntry())
+        // TODO: We should support these kinds of BBs
+        return X->getNumber() < Y->getNumber();
+      // TODO: it's possible that the second BB is better choice for surviving
+      // e.g. IF hasLayoutPredecessor(Y) AND NOT hasLayoutPredecessor(X)
+      if (SurvivedBBs.count(X->getNumber())) {
+        return Mark4Remove(BBsForRemove, SurvivedBBs, MLI, Y, X, X, Y);
+      } else if (SurvivedBBs.count(Y->getNumber()))
+        return Mark4Remove(BBsForRemove, SurvivedBBs, MLI, X, Y, X, Y);
+      // No one BB was marked as survived. It means if the second one was marked
+      // for erasing then there is
+      // equal better BB somewhere: we should simply to erase the second BB
+      // TODO: it's possible that the second BB is better choice for surviving
+      // than the already marked
+      if (auto V = BBsForRemove.lookup(X->getNumber()))
+        return Mark4Remove(BBsForRemove, SurvivedBBs, MLI, Y,
+                           F.getBlockNumbered(V), X, Y);
+      if (auto V = BBsForRemove.lookup(Y->getNumber()))
+        return Mark4Remove(BBsForRemove, SurvivedBBs, MLI, X,
+                           F.getBlockNumbered(V), X, Y);
+
+      // We're here: it means no one of X and Y was previously marked in any way
+      // TODO: bool X86InstrInfo::isTailCall(const MachineInstr &Inst);
+      auto XTerm = X->getFirstInstrTerminator();
+      // TODO: we should support CatchReturnInst
+      if (!(XTerm == X->instr_end() || /*isa<CatchReturnInst*>(XTerm) ||*/
+            (!XTerm->isReturn() && !XTerm->isUnconditionalBranch()))) {
+        // TODO: Let's start from these kinds of terminators
+        if (XTerm-- != X->instr_begin() && XTerm->isTerminator()) {
+          DEBUG(dbgs() << "\nREQBB: We have at least 2 terminators: let's "
+                          "elaborate it later\n";
+                X->dump(););
+          return X->getNumber() < Y->getNumber();
+        }
+        MachineBasicBlock *XLayoutPred = hasLayoutPredecessor(X);
+        MachineBasicBlock *YLayoutPred = hasLayoutPredecessor(Y);
+        // TODO: We need to select BestBB to leave it alive but the selection
+        // algorythm should be re-implemented properly
+        if (XLayoutPred && YLayoutPred) {
+          DEBUG(dbgs() << "\nREQBB: Both X-BB#" << X->getNumber()
+                       << " and Y-BB#" << Y->getNumber()
+                       << " have Layout Predecessors: elaborate it later\n";
+                X->dump(); Y->dump());
+          return X->getNumber() < Y->getNumber();
+        }
+        if (!XLayoutPred && YLayoutPred) {
+          std::swap(X, Y);
+        }
+        // Now we have:
+        // X - should be alive
+        // Y - should be removed
+        Mark4Remove(BBsForRemove, SurvivedBBs, MLI, Y, X, X, Y);
+        if (SurvivedBBs.insert(X->getNumber()).second) {
+          NumEqBBsSurvived++;
+          SizeEqBBsSurvived += X->size();
+        }
+      } else {
+        DEBUG(dbgs() << "REQBB: In BB#" << X->getNumber()
+                     << "we have illegal terminator preventing the "
+                        "Equal BB optimization\n";);
+      }
+    }
+    return false;
+  });
+  if (BBsForRemove.size()) {
+    for (auto &Number : BBsForRemove) {
+      auto RemBB = F.getBlockNumbered(Number.first);
+      // TODO: it should be done later because at the moment we don't support
+      // BBs inside loops (see Mark4Remove)
+      // MLI->removeBlock(RemBB);
+      RemBB->eraseFromParent();
+      DEBUG(dbgs() << "BB#" << Number.first << " was removed\n");
+    }
+    // To minmize defferences in tests we'll keep current numbering
+    //F.RenumberBlocks();
+    return true;
+  }
+  return false;
+}

lib/CodeGen/TargetPassConfig.cpp

void TargetPassConfig::addMachinePasses() {
   addPreEmitPass();
 
   if (TM->Options.EnableIPRA)
     // Collect register usage information and produce a register mask of
     // clobbered registers, to be used to optimize call sites.
     addPass(createRegUsageInfoCollector());
 
   addPass(&FuncletLayoutID, false);
+  if (getOptLevel() != CodeGenOpt::None)
+    addPass(&RemoveEqualBBID, false);
 
   addPass(&StackMapLivenessID, false);
   addPass(&LiveDebugValuesID, false);
 
   // Insert before XRay Instrumentation.
   addPass(&FEntryInserterID, false);
 
   addPass(&XRayInstrumentationID, false);

test/CodeGen/X86/loop-search.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: llc < %s -mtriple=x86_64-apple-darwin | FileCheck %s
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-apple-darwin -remove-equal-bbs | FileCheck %s
 
 ; This test comes from PR27136
 ; We should hoist loop constant invariant
 
 define zeroext i1 @search(i32 %needle, i32* nocapture readonly %haystack, i32 %count) {
 ; CHECK-LABEL: search:
 ; CHECK:       ## BB#0: ## %entry
 ; CHECK-NEXT:    testl %edx, %edx
-; CHECK-NEXT:    jle LBB0_1
+; CHECK-NEXT:    jle LBB0_3
 ; CHECK-NEXT:  ## BB#4: ## %for.body.preheader
 ; CHECK-NEXT:    movslq %edx, %rax
 ; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB0_5: ## %for.body
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpl %edi, (%rsi,%rcx,4)
 ; CHECK-NEXT:    je LBB0_6
 ; CHECK-NEXT:  ## BB#2: ## %for.cond
 ; CHECK-NEXT:    ## in Loop: Header=BB0_5 Depth=1
 ; CHECK-NEXT:    incq %rcx
 ; CHECK-NEXT:    cmpq %rax, %rcx
 ; CHECK-NEXT:    jl LBB0_5
-;            ### FIXME: BB#3 and LBB0_1 should be merged
-; CHECK-NEXT:  ## BB#3:
-; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    ## kill: %AL<def> %AL<kill> %EAX<kill>
-; CHECK-NEXT:    retq
-; CHECK-NEXT:  LBB0_1:
+; CHECK-NEXT:  LBB0_3:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    ## kill: %AL<def> %AL<kill> %EAX<kill>
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  LBB0_6:
 ; CHECK-NEXT:    movb $1, %al
 ; CHECK-NEXT:    ## kill: %AL<def> %AL<kill> %EAX<kill>
 ; CHECK-NEXT:    retq
-;
 entry:
   %cmp5 = icmp sgt i32 %count, 0
   br i1 %cmp5, label %for.body.preheader, label %cleanup
 
 for.body.preheader:                               ; preds = %entry
   %0 = sext i32 %count to i64
   br label %for.body