[BasicBlockSections] avoid insertting redundant branch to fall through blocks

[rahmanl]

Summary

Originally authored by @sinan

blocks reached by an explicit unconditional branch from its layout predecessor are also recognized as a fallthrough block via MachineBasicBlock::getFallThrough. For such cases, we do not need an extra unconditional branch.

If test case basic-block-sections_2.ll is run with O0, then you can see the instruction sequence like:

__cxx_global_var_init:                  # @__cxx_global_var_init
	.cfi_startproc
# %bb.0:                                # %entry
	pushq	%rax
	.cfi_def_cfa_offset 16
	movl	$5, %edi
	callq	_Z3bari
	movb	%al, %cl
	xorl	%eax, %eax
                                        # kill: def $al killed $al killed $eax
	testb	$1, %cl
	movb	%al, 7(%rsp)                    # 1-byte Spill
	jne	__cxx_global_var_init.__part.1
	jmp	__cxx_global_var_init.__part.2
	jmp	__cxx_global_var_init.__part.1
.LBB_END0_0:
	.cfi_endproc
	.section	.text.startup,"ax",@progbits,unique,2
__cxx_global_var_init.__part.1:         # %cond.true
	.cfi_startproc
	.cfi_def_cfa %rsp, 16
	movl	$3, %edi
	callq	_Z3bari

after this patch, the redundant branch jmp __cxx_global_var_init.__part.1 could be removed.

__cxx_global_var_init:                  # @__cxx_global_var_init
	.cfi_startproc
# %bb.0:                                # %entry
	pushq	%rax
	.cfi_def_cfa_offset 16
	movl	$5, %edi
	callq	_Z3bari
	movb	%al, %cl
	xorl	%eax, %eax
                                        # kill: def $al killed $al killed $eax
	testb	$1, %cl
	movb	%al, 7(%rsp)                    # 1-byte Spill
	jne	__cxx_global_var_init.__part.1
	jmp	__cxx_global_var_init.__part.2
.LBB_END0_0:
	.cfi_endproc
	.section	.text.startup,"ax",@progbits,unique,2
__cxx_global_var_init.__part.1:         # %cond.true
	.cfi_startproc
	.cfi_def_cfa %rsp, 16
	movl	$3, %edi
	callq	_Z3bari

This issue happens much more frequently when I test bb section option with AArch64.

[sinan]

simplify code

[rahmanl]

Thanks for the fix. Does this every trigger with -O2?

llvm/lib/CodeGen/BasicBlockSections.cpp

133

I suggest we change the name to hasUncoditionalBranch and flip the return value and the condition below, to make it more readable.

134–141

Can we simply write:
return !MBB.terminators.empty() && MBB.terminators.back().isUncoditionalBranch()

168

Or simply change this to
MBB.terminators.empty() || !MBB.terminators.back().isUnconditionalBranch() and add a comment.

llvm/test/CodeGen/X86/basic-block-sections_2.ll

21–25

Can we use a different file for this test? The file header describes a different purpose for this test. Also __cxx_global_var_init is an automatically-generated function. It would be better if we come up a with a standalone test with a normal function -- if possible.

[sinan]

Hi @rahmanl, I tested with -O2, and the redundant branch can be removed by machine code sinking pass.

[sinan]

llvm/lib/CodeGen/BasicBlockSections.cpp

134–141

I implemented it in this way since I have encountered code pieces like

0000000000400c98 <main.eh>:
  400c98:	d503201f 	nop
  400c9c:	aa0003f3 	mov	x19, x0
  400ca0:	7100043f 	cmp	w1, #0x1
  400ca4:	54ffff61 	b.ne	400c90 <main.__part.9>  // b.any
  400ca8:	17ffffef 	b	400c64 <main.__part.6>
  400cac:	aa0003f3 	mov	x19, x0
  400cb0:	97ffff50 	bl	4009f0 <__cxa_end_catch@plt>
  400cb4:	17fffff7 	b	400c90 <main.__part.9>
  400cb8:	94000001 	bl	400cbc <__clang_call_terminate>

But I just checked it and they seem to come from two eh-related basic blocks.

I will update it according to your suggestion.

[sinan]

update according to comments

[sinan]

Hi @rahmanl, Sorry for the delay. I did not find any countercase for just checking the last terminator, and I spent some time investigating a pattern:

jne  func.part2
jmp func.part1
nop
nop

and it turns out that the nops are inserted during emitting asm.

[rahmanl]

Thanks for the revision.

lld/test/ELF/lto/basic-block-sections-redundant-br.ll

1 ↗

(On Diff #473587)

Please add a one line comment, explaining the purpose of this test.

20–24 ↗

(On Diff #473587)

You don't need this since you have CHECKS for mapping.__part.1 and mapping.__part.2. I suggest we just check the jumps.

27 ↗

(On Diff #473587)

CHECK-NOT: jmp is sufficient.

llvm/lib/CodeGen/BasicBlockSections.cpp

125–126

This comment seems to be explaining something about the context in which this function is called. I suggest we remove it from here.

129

Looking again, it seems that terminators is simply a range starting at the first terminator and ending at MachineBasicBlock::end().https://llvm.org/doxygen/classllvm_1_1MachineBasicBlock.html#a7f0521fa2de44271fd4b909ea7351ef3
So I think we can simply do:
!MBB.empty() && MBB.back().isUnconditionalBranch().

164–169

This comment is incorrect. If it has an unconditional branch to its fallthrough, then we *don't* need an additional jump.

[sinan]

update the patch according to suggestions.

[rahmanl]

Has this been revised yet? I see you have updated the patch but my comments are still "Not Done".

llvm/lib/CodeGen/BasicBlockSections.cpp

164–169

Still pending.
You can just remove the third item (it's implicitly followed from "needs an explicit unconditional branch").

llvm/test/CodeGen/X86/basic-block-sections-redundant-br.ll

1 ↗

(On Diff #474418)

[sinan]

remove the incorrect description.

[rahmanl]

Apply final changes.

[rahmanl]

Rename the test.

[rahmanl]

clang-format.

[rahmanl]

fix comment.

[sinan]

LGTM, thanks for continuing this work.

[rahmanl]

I think D158674 handled this. So abandoning this revision.

llvm/lib/CodeGen/BasicBlockSections.cpp

public:
 
   /// Identify basic blocks that need separate sections and prepare to emit them
   /// accordingly.
   bool runOnMachineFunction(MachineFunction &MF) override;
 };
 
 } // end anonymous namespace
 
 char BasicBlockSections::ID = 0;
 INITIALIZE_PASS(BasicBlockSections, "bbsections-prepare",
                 "Prepares for basic block sections, by splitting functions "
                 "into clusters of basic blocks.",
                 false, false)
 
+/// Basic blocks with an explicit unconditional branch to its fallthrough block
+/// do not need an extra unconditional branch.
+static bool needInsertUncondBranch(const MachineBasicBlock &MBB) {
+  auto B = MBB.terminators().begin(), E = MBB.end(), I = B;
+  if (I == E)
+    return true;
+
+  if (I->isUnconditionalBranch())
+    return false;
+
+  while (I != E) {
+    if (I->isUnconditionalBranch())
+      return false;
+    I++;
+  }
+  return true;
+}
+
 // This function updates and optimizes the branching instructions of every basic
 // block in a given function to account for changes in the layout.
 static void updateBranches(
     MachineFunction &MF,
     const SmallVector<MachineBasicBlock *, 4> &PreLayoutFallThroughs) {
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   SmallVector<MachineOperand, 4> Cond;
   for (auto &MBB : MF) {
     auto NextMBBI = std::next(MBB.getIterator());
     auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
     // If this block had a fallthrough before we need an explicit unconditional
     // branch to that block if either
     //     1- the block ends a section, which means its next block may be
-    //        reorderd by the linker, or
+    //        reorderd by the linker,
     //     2- the fallthrough block is not adjacent to the block in the new
-    //        order.
-    if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
+    //        order, or
+    //     3- the terminator of the block is an unconditional branch to its
+    //        fallthrough.
+    if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB) &&
+        needInsertUncondBranch(MBB))
       TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
 
     // We do not optimize branches for machine basic blocks ending sections, as
     // their adjacent block might be reordered by the linker.
     if (MBB.isEndSection())
       continue;
 
     // It might be possible to optimize branches by flipping the branch
     // condition.

llvm/test/CodeGen/X86/basic-block-sections_2.ll

 ; Check that the basic block sections suffix naming does not conflict with __cxx_global_var_init.N naming.
 ; How to  generate this file:
 ;; class A {
 ;;  public:
 ;;    A(bool a) { }
 ;; };
 ;;
 ;; extern bool bar(int);
 ;; A g_a(bar(5) ? bar(3) : false), g_b(true);
 ;;
 ;; $ clang -O1 -emit-llvm -S
 ;;
 ; __cxx_global_var_init has multiple basic blocks which will produce many sections.
 ; RUN: llc < %s -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=all -unique-basic-block-section-names | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=all -O0 -unique-basic-block-section-names | FileCheck %s --check-prefix=REDUNDANT
 
 ; CHECK-LABEL: __cxx_global_var_init:
 ; CHECK-LABEL: __cxx_global_var_init.__part.1:
 ; CHECK-LABEL: __cxx_global_var_init.1:
 
+; REDUNDANT-LABEL: __cxx_global_var_init:
+; REDUNDANT: jmp __cxx_global_var_init.__part.2
+; REDUNDANT-NOT: jmp __cxx_global_var_init.__part.1
+; REDUNDANT-LABEL: __cxx_global_var_init.__part.1:
+; REDUNDANT-LABEL: __cxx_global_var_init.1:
+
 %class.A = type { i8 }
 
 $_ZN1AC2Eb = comdat any
 
 @g_a = dso_local global %class.A zeroinitializer, align 1
 @g_b = dso_local global %class.A zeroinitializer, align 1
 @llvm.global_ctors = appending global [1 x { i32, ptr, ptr }] [{ i32, ptr, ptr } { i32 65535, ptr @_GLOBAL__sub_I_symcollision.cc, ptr null }]