Removing a redundant fall-through branch to the following BB

Hi *

I have a LLVM learning project - a backend for the MC6809 processor.

I’m using GlobalISel, because its new and shiny and the way of the future :slight_smile:

In the below functions, which is a lowering of a very basic loop summing function, I am left with two JumpRelative instructions; they passed through G_BR on the way down. At the bottom, there are “bad machine code” errors, which are valid; those JumpRelative instructions should be removed.

The problem is - how? I didn’t put them there, so I am rather hoping that somehow LLVM knows how to get rid if them - If only I knew how to set things up correctly (or something).

G_BR seems to enjoy a magical existence. It’s hardly mentioned anywhere, and most (all?) backends fall back to SelectionDAG (I think) to lower it. I’ve tried both using a Pattern = [..]; in my pseudoinstruction definition and lowering by hand in the globalisel select() function. Both have the same result as below.

M

# Machine code for function loop: IsSSA, TracksLiveness, Legalized, RegBankSelected, Selected
Function Live Ins: $ix, $ab

bb.1.entry:
  successors: %bb.2(0x50000000), %bb.4(0x30000000); %bb.2(62.50%), %bb.4(37.50%)
  liveins: $ab, $ix
  %0:index16 = COPY $ix
  %1:abc = COPY $ab
  %14:acc16 = Load16Imm i16 0
  Compare8Imm %1:abc, 0, implicit-def $nz, implicit-def $v, implicit-def $c
  JumpConditionalRelative 15, %bb.4, implicit $nz, implicit $v, implicit $c
  JumpRelative %bb.2    <<<<<==================================================

bb.2.for.body.preheader:
; predecessors: %bb.1
  successors: %bb.3(0x80000000); %bb.3(100.00%)

  %22:acc16 = Load16Imm i16 0
  %4:adc = ZEX16Implicit %1:abc

bb.3.for.body:
; predecessors: %bb.2, %bb.3
  successors: %bb.4(0x04000000), %bb.3(0x7c000000); %bb.4(3.12%), %bb.3(96.88%)

  %5:acc16 = PHI %4:adc, %bb.2, %13:acc16, %bb.3
  %6:index16 = PHI %0:index16, %bb.2, %11:index16, %bb.3
  %7:acc16 = PHI %22:acc16, %bb.2, %9:acc16, %bb.3
  %8:acc16 = Load16Idx %0:index16, 0, implicit-def $nz, implicit-def $v :: (load (s16) from %ir.lsr.iv, align 1, !tbaa !3)
  %9:acc16, %26:cc, %27:vc = Add16Reg %8:acc16(tied-def 0), %7:acc16, implicit-def $nz
  %10:acc16 = Load16Imm i16 2
  %11:index16 = LEAPtrAdd %6:index16, %10:acc16
  %13:acc16, %24:cc, %25:vc = Add16Imm %5:acc16(tied-def 0), -1, implicit-def $nz
  Compare16Imm %13:acc16, 0, implicit-def $nz, implicit-def $v, implicit-def $c
  JumpConditionalRelative 6, %bb.3, implicit $nz, implicit $v, implicit $c
  JumpRelative %bb.4    <<<<<==================================================

bb.4.for.end:
; predecessors: %bb.1, %bb.3

  %16:acc16 = PHI %14:acc16, %bb.1, %9:acc16, %bb.3
  $ad = COPY %16:acc16
  ReturnImplicit implicit $ad

# End machine code for function loop.

I understand these errors, i think. What I don’t know is how to fix them:

*** Bad machine code: MBB exits via unconditional fall-through but ends with a barrier instruction! ***
- function:    loop
- basic block: %bb.1 entry (0x7fdbf980efb0)

*** Bad machine code: MBB has unexpected successors which are not branch targets, fallthrough, EHPads, or inlineasm_br targets. ***
- function:    loop
- basic block: %bb.1 entry (0x7fdbf980efb0)

*** Bad machine code: MBB exits via unconditional fall-through but ends with a barrier instruction! ***
- function:    loop
- basic block: %bb.3 for.body (0x7fdbf980f180)

*** Bad machine code: MBB has unexpected successors which are not branch targets, fallthrough, EHPads, or inlineasm_br targets. ***
- function:    loop
- basic block: %bb.3 for.body (0x7fdbf980f180)
LLVM ERROR: Found 4 machine code errors.

I think there are two issues here, both related to analyzeBranch (which you’ve hopefully implemented, otherwise I’m thoroughly confused).

First, those verifier errors don’t look correct to me, or at least not the 1st & 3rd. Those errors should only occur when analyzeBranch returns success while leaving both TrueBB and FalseBB as nullptr, indicating that there are no control-flow instructions at the end of the block and it always falls through. In that case finding a barrier would be worrying. But that’s not what’s happening here. analyzeBranch should set TrueBB to the JumpConditionalRelative destination, and FalseBB to the JumpRelative destination.

Second, the code would be better if the unconditional jumps were removed. I think there are generic passes like MachineBlockPlacement that do this, but they rely on you implementing InstrInfo hooks. Starting with analyzeBranch, but also things like insertBranch and removeBranch. Those passes would tell your callbacks to insert a block-terminator with just the conditional branch and a fallthrough (by calling insertBranch with a nullptr FalseBB). I kind of think they’ll kick in automatically if you implement the hooks, but I’m not 100% sure.

1 Like

Thank you! That gives me something to work with.

I do have an analyzeBranch(), but it’s one that I’ve inherited from llvm-mos, which I used as a starting point. At a first reading it looks kinda OK - time to trace it, methinks.

As for the InstrInfo hooks, I’ll go a-looking.

M

Fixed!

My analyzeBranch, insertBranch and removeBranch needed some TLC. Thanks for pointing me in the right direction.

M