[BOLT] Remove peephole useless-branches pass

[yota9]

Summary

Currently this pass is useless since the cfg-normalization pass contains
this functionality.
Also this patch refactors peephole options enum by placing it Peepholes class.

Vladislav Khmelevsky,
Advanced Software Technology Lab, Huawei

[yota9]

nit

[yota9]

Remove enum name for in-class usage

[yota9]

Clang format

[Amir]

Hi Vladislav,

I've added the clang-icp.test to binary tests repo (https://github.com/rafaelauler/bolt-tests) and this test breaks with this diff. Please let me know if you can reproduce it.

[Amir]

In D118364#3277620, @Amir wrote:

Hi Vladislav,

I've added the clang-icp.test to binary tests repo (https://github.com/rafaelauler/bolt-tests) and this test breaks with this diff. Please let me know if you can reproduce it.

Please use bolt/utils/llvm-bolt-wrapper.py script (rGc2a961e414e0) to run binary matching.

1. Build BOLT without this diff, rename the binary as llvm-bolt.old
2. Build BOLT with this diff, rename the binary as llvm-bolt.new
3. Run the script to produce llvm-bolt-wrapper.ini:

/path/to/llvm-bolt-wrapper.py /path/to/llvm-bolt.old /path/to/llvm-bolt.new > bin/llvm-bolt-wrapper.ini

4. Symlink the script in place of llvm-bolt:

ln -sf /path/to/llvm-bolt-wrapper.py /path/to/llvm-bolt

5. Run binary test:

bin/llvm-lit -a tools/bolttests/clang-icp.test

The mismatch in text section should be reported.

[yota9]

Call fixBranches in fixDoubleJumps.
@Amir could you please check the test? I think it shold be identical now :)

[Amir]

In D118364#3280931, @yota9 wrote:

Call fixBranches in fixDoubleJumps.
@Amir could you please check the test? I think it shold be identical now :)

No, it's still not matching.
I've used the script in D118516 to test it (cherry-pick it and move under this diff):

• in repo: checkout this diff (D118364)
• in BOLT build directory: invoke python3 <llvm-project>/bolt/utils/nfc-check-setup.py --run_sequentially
• run the test: bin/llvm-lit -a tools/bolttests/X86/clang.test (no need to run the binary)

[yota9]

@Amir Hello! Yes, you're right, there are 256 bytes mismatch in .text.cold between binaries (the new binary becomes smaller). But now we not only remove the useless condition branches, we are also removing the useless unconditional branches. The example you can see in small function "_ZN4llvm11InstVisitorINS_26PGOIndirectCallSiteVisitorEvE16delegateCallInstERNS_8CallInstE"

Previously after-bolt we had:

38bd9e5:	eb f3                	jmp    38bd9da <_ZN4llvm11InstVisitorINS_26PGOIndirectCallSiteVisitorEvE16delegateCallInstERNS_8CallInstE+0x16>
38bd9e7:	eb f1                	jmp    38bd9da <_ZN4llvm11InstVisitorINS_26PGOIndirectCallSiteVisitorEvE16delegateCallInstERNS_8CallInstE+0x16>

And now:

38bd9e5:	eb f3                	jmp    38bd9da <_ZN4llvm11InstVisitorINS_26PGOIndirectCallSiteVisitorEvE16delegateCallInstERNS_8CallInstE+0x16>
38bd9e7:	90                   	nop

The second jump was emitted since previously we didn't run eraseInvalidBBs() after peephole pass, although in fact this instruction (which is in separate BB) becomes unreachable.

Also fixBranches() makes some work. E.g. in "_ZN4llvm13ScheduleDAGMID1Ev"

Previously we had jump on the next instruction:

47b1c51:	e8 da 35 cb fe       	callq  3465230 <_ZN12_GLOBAL__N_113CopyConstrainD0Ev>
47b1c56:	eb 07                	jmp    47b1c5f <_ZN4llvm13ScheduleDAGMID1Ev+0x51>
47b1c58:	eb 05                	jmp    47b1c5f <_ZN4llvm13ScheduleDAGMID1Ev+0x51>
47b1c5a:	ff 50 10             	callq  *0x10(%rax)
47b1c5d:	eb 00                	jmp    47b1c5f <_ZN4llvm13ScheduleDAGMID1Ev+0x51>
47b1c5f:	48 8d 53 08          	lea    0x8(%rbx),%rdx

And now no extra jump on 47b1c5d:

47b1c11:	e8 1a 36 cb fe       	callq  3465230 <_ZN12_GLOBAL__N_113CopyConstrainD0Ev>
 47b1c16:	eb 03                	jmp    47b1c1b <_ZN4llvm13ScheduleDAGMID1Ev+0x4d>
 47b1c18:	ff 50 10             	callq  *0x10(%rax)
 47b1c1b:	48 8d 53 08          	lea    0x8(%rbx),%rdx

This example also contains one unreachable jump removed by eraseInvalidBBs right in one function :)
Although the binaries are not identical, but it seems to be reasonable change :) But I think we need to decide how to run the fixBranches() in more proper way I made now. Since for example after the SimplifyConditionalTailCalls we might have situations where the fixBranches() is needed to call, so I'm not sure how to fix it better, maybe you can suggest me. In my mind the easiest and the bests solution is to run the FixupBranches pass twice, the second time after peephole with the comment that no further pass should change the branches. This will help us to avoid such problems in future, but will cost some time of course..

[Amir]

Thanks for investigating! I'm checking it with more tests and will return to you shortly

[yota9]

The SCTC pass breaks CFG and we are unable to call fixBranches at that point anymore, closing review for now, thank you @Amir for your time :)

bolt/include/bolt/Passes/BinaryPasses.h

public:
 
   const char *getName() const override { return "shorten-instructions"; }
 
   void runOnFunctions(BinaryContext &BC) override;
 };
 
 /// Perform simple peephole optimizations.
 class Peepholes : public BinaryFunctionPass {
+public:
+  enum PeepholeOpts : char {
+    PEEP_NONE             = 0x0,
+    PEEP_DOUBLE_JUMPS     = 0x2,
+    PEEP_TAILCALL_TRAPS   = 0x4,
+    PEEP_ALL              = 0xf
+  };
+
+private:
   uint64_t NumDoubleJumps{0};
   uint64_t TailCallTraps{0};
-  uint64_t NumUselessCondBranches{0};
 
   /// Add trap instructions immediately after indirect tail calls to prevent
   /// the processor from decoding instructions immediate following the
   /// tailcall.
   void addTailcallTraps(BinaryFunction &Function);
 
-  /// Remove useless duplicate successors.  When the conditional
-  /// successor is the same as the unconditional successor, we can
-  /// remove the conditional successor and branch instruction.
-  void removeUselessCondBranches(BinaryFunction &Function);
-
 public:
   explicit Peepholes(const cl::opt<bool> &PrintPass)
       : BinaryFunctionPass(PrintPass) {}
 
   const char *getName() const override { return "peepholes"; }
   void runOnFunctions(BinaryContext &BC) override;
 };
 

bolt/lib/Passes/BinaryPasses.cpp

 static cl::opt<bool>
 MinBranchClusters("min-branch-clusters",
   cl::desc("use a modified clustering algorithm geared towards minimizing "
            "branches"),
   cl::ZeroOrMore,
   cl::Hidden,
   cl::cat(BoltOptCategory));
 
-enum PeepholeOpts : char {
-  PEEP_NONE             = 0x0,
-  PEEP_DOUBLE_JUMPS     = 0x2,
-  PEEP_TAILCALL_TRAPS   = 0x4,
-  PEEP_USELESS_BRANCHES = 0x8,
-  PEEP_ALL              = 0xf
-};
-
-static cl::list<PeepholeOpts>
+static cl::list<Peepholes::PeepholeOpts>
 Peepholes("peepholes",
   cl::CommaSeparated,
   cl::desc("enable peephole optimizations"),
   cl::value_desc("opt1,opt2,opt3,..."),
   cl::values(
-    clEnumValN(PEEP_NONE, "none", "disable peepholes"),
-    clEnumValN(PEEP_DOUBLE_JUMPS, "double-jumps",
+    clEnumValN(Peepholes::PEEP_NONE, "none", "disable peepholes"),
+    clEnumValN(Peepholes::PEEP_DOUBLE_JUMPS, "double-jumps",
                "remove double jumps when able"),
-    clEnumValN(PEEP_TAILCALL_TRAPS, "tailcall-traps", "insert tail call traps"),
-    clEnumValN(PEEP_USELESS_BRANCHES, "useless-branches",
-               "remove useless conditional branches"),
-    clEnumValN(PEEP_ALL, "all", "enable all peephole optimizations")),
+    clEnumValN(Peepholes::PEEP_TAILCALL_TRAPS, "tailcall-traps",
+               "insert tail call traps"),
+    clEnumValN(Peepholes::PEEP_ALL, "all", "enable all peephole optimizations")),
   cl::ZeroOrMore,
   cl::cat(BoltOptCategory));
 
 static cl::opt<unsigned>
 PrintFuncStat("print-function-statistics",
   cl::desc("print statistics about basic block ordering"),
   cl::init(0),
   cl::ZeroOrMore,
if (Inst && MIB->isTailCall(*Inst) && MIB->isIndirectBranch(*Inst)) {
       if (MIB->createTrap(Trap)) {
         BB.addInstruction(Trap);
         ++TailCallTraps;
       }
     }
   }
 }
 
-void Peepholes::removeUselessCondBranches(BinaryFunction &Function) {
-  for (BinaryBasicBlock &BB : Function) {
-    if (BB.succ_size() != 2)
-      continue;
-
-    BinaryBasicBlock *CondBB = BB.getConditionalSuccessor(true);
-    BinaryBasicBlock *UncondBB = BB.getConditionalSuccessor(false);
-    if (CondBB != UncondBB)
-      continue;
-
-    const MCSymbol *TBB = nullptr;
-    const MCSymbol *FBB = nullptr;
-    MCInst *CondBranch = nullptr;
-    MCInst *UncondBranch = nullptr;
-    bool Result = BB.analyzeBranch(TBB, FBB, CondBranch, UncondBranch);
-
-    // analyzeBranch() can fail due to unusual branch instructions,
-    // e.g. jrcxz, or jump tables (indirect jump).
-    if (!Result || !CondBranch)
-      continue;
-
-    BB.removeDuplicateConditionalSuccessor(CondBranch);
-    ++NumUselessCondBranches;
-  }
-}
-
 void Peepholes::runOnFunctions(BinaryContext &BC) {
   const char Opts = std::accumulate(
       opts::Peepholes.begin(), opts::Peepholes.end(), 0,
-      [](const char A, const opts::PeepholeOpts B) { return A | B; });
-  if (Opts == opts::PEEP_NONE || !BC.isX86())
+      [](const char A, const PeepholeOpts B) { return A | B; });
+  if (Opts == PeepholeOpts::PEEP_NONE || !BC.isX86())
     return;
 
   for (auto &It : BC.getBinaryFunctions()) {
     BinaryFunction &Function = It.second;
     if (shouldOptimize(Function)) {
-      if (Opts & opts::PEEP_DOUBLE_JUMPS)
+      if (Opts & PEEP_DOUBLE_JUMPS)
         NumDoubleJumps += fixDoubleJumps(Function, false);
-      if (Opts & opts::PEEP_TAILCALL_TRAPS)
+      if (Opts & PEEP_TAILCALL_TRAPS)
         addTailcallTraps(Function);
-      if (Opts & opts::PEEP_USELESS_BRANCHES)
-        removeUselessCondBranches(Function);
       assert(Function.validateCFG());
     }
   }
   outs() << "BOLT-INFO: Peephole: " << NumDoubleJumps
          << " double jumps patched.\n"
          << "BOLT-INFO: Peephole: " << TailCallTraps
-         << " tail call traps inserted.\n"
-         << "BOLT-INFO: Peephole: " << NumUselessCondBranches
-         << " useless conditional branches removed.\n";
+         << " tail call traps inserted.\n";
 }
 
 bool SimplifyRODataLoads::simplifyRODataLoads(BinaryFunction &BF) {
   BinaryContext &BC = BF.getBinaryContext();
   MCPlusBuilder *MIB = BC.MIB.get();
 
   uint64_t NumLocalLoadsSimplified = 0;
   uint64_t NumDynamicLocalLoadsSimplified = 0;

bolt/test/AArch64/useless-cond-branch.s

+## This test checks that the useless conditional branch is removed by bolt
+
+# RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown \
+# RUN:   %s -o %t.o
+# RUN: %clang %cflags %t.o -o %t.exe -Wl,-q
+# RUN: llvm-bolt %t.exe -o %t.bolt -print-normalized -print-only=main | FileCheck %s
+
+# CHECK:      cmp     x0, #0x1
+# CHECK-NEXT: b
+
+
+  .text
+  .align 4
+  .global main
+  .type main, %function
+main:
+  cmp x0, #2
+  b.eq 1f
+  cmp x0, #1
+  b.eq 2f
+  b 2f
+1:
+  add x0, x0, #1
+2:
+  ret
+  .size main, .-main