llvm dev - Feb 2010 - [LLVMdev] How to check for "SPARC code generation" in MachineBasicBlock.cpp?

Hi, Chris
> That is target independent code, so you should not put sparc specific
changes there.  It sounds like one of the sparc-specific target hooks is wrong.
Since sparc does not provide any hooks for operation of branches (e.g.
AnalyzeBranch and friends) it might be possible that generic codegen
code is broken in absence of these hooks.

-- 
With best regards, Anton Korobeynikov
Faculty of Mathematics and Mechanics, Saint Petersburg State University

On 11/12/2009, at 10:43 AM, Anton Korobeynikov wrote:
> Hi, Chris
> 
>> That is target independent code, so you should not put sparc specific
changes there.  It sounds like one of the sparc-specific target hooks is wrong.
> Since sparc does not provide any hooks for operation of branches (e.g.
> AnalyzeBranch and friends) it might be possible that generic codegen
> code is broken in absence of these hooks.
Hi Anton,

   I've had a little time to look into this now, and I think there's
actually two separate problems here. By way of example, what's happening is
that the following pair of MBBs:

BB#315: derived from LLVM BB %bb
    Predecessors according to CFG: BB#314
        %reg1731<def> = SETHIi 1856
        %reg1732<def> = ORri %G0, 1
        %reg1733<def> = SLLrr %reg1732, %reg1729
        %reg1734<def> = ORri %reg1731, 1
        %reg1735<def> = ANDrr %reg1733, %reg1734
        %reg1736<def> = SUBCCri %reg1735, 0, %ICC<imp-def>
        BCOND <BB#3>, 9, %ICC<imp-use>
        BA <BB#53>
    Successors according to CFG: BB#3 BB#53

BB#3: derived from LLVM BB %bb1
    Predecessors according to CFG: BB#315
        %reg1740<def> = ANDri %reg1067, 255
        %reg1741<def> = SUBCCri %reg1740, 1, %ICC<imp-def>;
dbg:expr.c:757
        BCOND <BB#5>, 1, %ICC<imp-use>; dbg:expr.c:757
    Successors according to CFG: BB#5 BB#4


is compiled down to 

! BB#7:                                                     ! %bb
                                                            !   in Loop:
Header=BB1_2 Depth=2
        sethi 1856, %l5
        or %g0, 1, %l6
        sll %l6, %l3, %l3
        or %l5, 1, %l5
        and %l3, %l5, %l3
        subcc %l3, 0, %l3
        bne .LBB1_8
        nop
        ba .LBB1_68
        nop
! BB#8:                                                     ! %bb1
                                                            !   in Loop:
Header=BB1_2 Depth=2
        ld [%fp+-212], %l3
        and %l3, 255, %l3
.Llabel18:
        subcc %l3, 1, %l3
                                                            ! expr.c:757
        be .LBB1_10
                                                            ! expr.c:757
        nop

(Note the missing .LBB1_8:, which is the immediate problem). 

Firstly, the BNE/BA pair should be reduced to a BE (I assume this is the
responsibility of AnalyzeBranch and friends that you mention). However I still
wouldn't have expected that to result in the label being omitted (assuming
multiple branches are legal in an MBB). It appears that the branch delay-slots
are specifically to blame here - the above BB#315 immediately prior to output is

BB#7: derived from LLVM BB %bb
    Live Ins: %L1 %L0 %L3 %L2 %L4
    Predecessors according to CFG: BB#6
        %L5<def> = SETHIi 1856
        %L6<def> = ORri %G0, 1
        %L3<def> = SLLrr %L6<kill>, %L3<kill>
        %L5<def> = ORri %L5<kill>, 1
        %L3<def> = ANDrr %L3<kill>, %L5<kill>
        %L3<def,dead> = SUBCCri %L3<kill>, 0, %ICC<imp-def>
        BCOND <BB#8>, 9, %ICC<imp-use,kill>
        NOP
        BA <BB#68>
        NOP

which leads MachineBasicBlock::isOnlyReachableByFallthrough() to return TRUE for
BB#8, since the final NOP is not a 'barrier instruction', and so the
label is skipped. Assuming I've got this right so far, I'd expect this
to be affecting MIPS as well as SPARC.

So I guess the question I have is, are MBBs like BB#7 above legal, and if so
would something like

BB#7:
    ...
    BCOND cond1, BB#8
    BCOND cond2, BB#57
BB#8:
    ...
also be legal - ie BB7 contains both a branch and a fallthrough to the same
successor block?

If so, it seems that isOnlyReachableByFallthrough() would need to check all
label references in the predecessor to ensure none of them correspond to the
target block rather than just the final instruction (or alternatively one could
add additional tracking information to the MBB for this purpose?).

Cheers,
Nathan

On Feb 8, 2010, at 12:37 AM, Nathan Keynes wrote:
> Firstly, the BNE/BA pair should be reduced to a BE (I assume this is  
> the responsibility of AnalyzeBranch and friends that you mention).
Right.  Implementing AnalyzeBranch will allow a bunch of block layout  
and branch optimizations to happen.
> However I still wouldn't have expected that to result in the label  
> being omitted (assuming multiple branches are legal in an MBB). It  
> appears that the branch delay-slots are specifically to blame here
Yes, most certainly.
> - the above BB#315 immediately prior to output is
>
> BB#7: derived from LLVM BB %bb
>    Live Ins: %L1 %L0 %L3 %L2 %L4
>    Predecessors according to CFG: BB#6
>        %L5<def> = SETHIi 1856
>        %L6<def> = ORri %G0, 1
>        %L3<def> = SLLrr %L6<kill>, %L3<kill>
>        %L5<def> = ORri %L5<kill>, 1
>        %L3<def> = ANDrr %L3<kill>, %L5<kill>
>        %L3<def,dead> = SUBCCri %L3<kill>, 0,
%ICC<imp-def>
>        BCOND <BB#8>, 9, %ICC<imp-use,kill>
>        NOP
>        BA <BB#68>
>        NOP
>
> which leads MachineBasicBlock::isOnlyReachableByFallthrough() to  
> return TRUE for BB#8, since the final NOP is not a 'barrier  
> instruction', and so the label is skipped.
Yep, that sounds like the problem.
> So I guess the question I have is, are MBBs like BB#7 above legal,
Funny question :).  When I was working on the sparc backend, it was  
unclear how best to represent delay slots.  The approach I took was to  
pretend that they didn't exist for most of the compiler backend, then  
have DelaySlotFiller create them right before the asmprinter ran. The  
idea was to eventually extend DelaySlotFiller to put something better  
than a nop in them :)

This all works as long as the asmprinter is a simple pass through that  
doesn't look at the code, which isOnlyReachableByFallthrough violates.

As far as a proposed solution, since asmprinter is the only user of  
isOnlyReachableByFallthrough, I'd recommend moving  
isOnlyReachableByFallthrough to be  
AsmPrinter::IsBlockOnlyReachableByFallthrough.  Then you can make it  
virtual, and have the sparc backend provide its own implementation of  
it (which might as well just return false all the time).
> and if so would something like
>
> BB#7:
>    ...
>    BCOND cond1, BB#8
>    BCOND cond2, BB#57
> BB#8:
>    ...
> also be legal - ie BB7 contains both a branch and a fallthrough to  
> the same successor block?
That form is legal, but not desirable because AnalyzeBranch isn't able  
to model it.  This will cause a bunch of useful optimizations to get  
disabled.

-Chris