[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

139

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

140–147

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

166

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 ↗

(On Diff #468887)

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

140–147

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().

162–163

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

162–163

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_BEGIN(
     BasicBlockSections, "bbsections-prepare",
     "Prepares for basic block sections, by splitting functions "
     "into clusters of basic blocks.",
     false, false)
 INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReader)
 INITIALIZE_PASS_END(BasicBlockSections, "bbsections-prepare",
                     "Prepares for basic block sections, by splitting functions "
                     "into clusters of basic blocks.",
                     false, false)
 
+
+// Returns whether the given basic block has an unconditional branch.
+bool hasUnconditionalBranch(const MachineBasicBlock &MBB) {
+  if (MBB.terminators().empty()) return false;
+  const MachineInstr &Terminator = *(--MBB.terminators().end());
+  return Terminator.isUnconditionalBranch();
+}
+
 // 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 *> &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
+    // branch to that block if either these two conditions hold and the block doesn't 
+    // currently have an unconditional branch.
     //     1- the block ends a section, which means its next block may be
     //        reorderd by the linker, or
     //     2- the fallthrough block is not adjacent to the block in the new
     //        order.
-    if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
+    if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB) && !hasUnconditionalBranch(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.
     Cond.clear();
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
     if (TII->analyzeBranch(MBB, TBB, FBB, Cond))

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

+; Tests that basic block sections avoids inserting an unconditional branch when a basic block
+; already has an unconditional branch to its fallthrough block.
+; RUN: llc < %s -mtriple=x86_64 -basic-block-sections=all -O0 | FileCheck %s
+; This test case is generated from code:
+; int
+; mapping (int len)
+; {
+;   switch (len)
+;   {
+;     case 7: return 333;
+;     default:
+;       goto unknown;
+;   }
+; unknown:
+;   return 0;
+; }
+; clang -O0 -fbasic-block-sections=all test.c
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local i32 @mapping(i32 noundef %len) {
+entry:
+  %retval = alloca i32, align 4
+  %len.addr = alloca i32, align 4
+  store i32 %len, ptr %len.addr, align 4
+  %0 = load i32, ptr %len.addr, align 4
+  switch i32 %0, label %sw.default [
+    i32 7, label %sw.bb
+  ]
+
+sw.bb:                                            ; preds = %entry
+  store i32 333, ptr %retval, align 4
+  br label %return
+
+sw.default:                                       ; preds = %entry
+  br label %unknown
+
+unknown:                                          ; preds = %sw.default
+  store i32 0, ptr %retval, align 4
+  br label %return
+
+return:                                           ; preds = %unknown, %sw.bb
+  %1 = load i32, ptr %retval, align 4
+  ret i32 %1
+}
+
+; CHECK: mapping:
+; CHECK-NEXT: .cfi_startproc
+; CHECK-NEXT: # %bb.0: # %entry
+; CHECK-NEXT: movl {{.*}}
+; CHECK-NEXT: movl {{.*}}
+; CHECK-NEXT: subl {{.*}}
+; CHECK-NEXT: jne mapping.__part.2
+; CHECK-NEXT: jmp mapping.__part.1
+; CHECK-NOT:  jmp
+; CHECK: mapping.__part.1:
+; CHECK: mapping.__part.2: