How to check for "SPARC code generation" in MachineBasicBlock.cpp?

Juergen_Zimmermann_S · December 10, 2009, 8:00am

Hi,
I'm almost finished to get a complete and seemingly working build of
LLVM-GCC (trunk) for SPARC (32-bit only, for now).

The only remaining problem is the code generation for one single
file (namely cp-demangle.c) where some labels are not put into
the assembler/object file due to some (until now) unknown
inconsistencies with 'isOnlyReachableByFallthrough' and
(most likely) the SPARC code generator.

For now, I'm looking for a way to determine within that function
if LLVM is supposed to generate code for SPARC and then
implement the logic that's needed.

Any 'quick' suggestions?

Regards,
Juergen

Chris_Lattner · December 10, 2009, 11:54pm

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.

-Chris

akorobeynikov · December 11, 2009, 12:43am

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.

Nathan_Keynes · February 8, 2010, 8:37am

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

Chris_Lattner · February 8, 2010, 5:57pm

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

Juergen_Zimmermann_S · February 9, 2010, 8:06am

Chris,
thanks for that in-depth explaination.

I like your idea making isOnlyReachableByFallthrough making a
virtual function and then overwrite it in the SPARC backend
for our purpose.

That way, I guess I would get a complete and clean bootstrap of LLVM/GCC 4.2 on SPARC in 32 bit (for now).

Let me see what I can do later.

Regards,
Juergen

Nathan_Keynes · February 9, 2010, 11:31pm

Sounds reasonable to me. The attached llvm-sparc-asmprinter1.patch implements what you've described above, with SparcAsmPrinter::isBlockOnlyReachableByFallthrough looking for the last terminator rather than the last instruction.

I've also included llvm-sparc-asmprinter2.patch which fixes a different issue in SparcAsmPrinter where multiple identical .LLGETPCHn symbols could be emitted in the same file (it was uniqued by block number, but not by function number).

These fix the symbol issues when bootstrapping gcc (and don't break any tests this time that I can see), although unfortunately there still appear to be other SPARC codegen issues that are blocking the bootstrap.

Cheers,
Nathan

llvm-sparc-asmprinter1.patch (6.72 KB)

llvm-sparc-asmprinter2.patch (1.22 KB)

To_ro_k_Edwin · February 14, 2010, 6:12pm

Hi Nathan,

What will the status of the Sparc backend be in LLVM 2.7? Can
llvm-gcc/clang [1] on Sparc produce working programs?

I would also be interested if there any plans for a Sparc JIT for LLVM 2.8.
Currently LLVM has a working JIT on x86, ppc (and perhaps arm?) AFAIK.
It'd be great if sparc had JIT support too.
I've seen that a very old version of LLVM had Sparc JIT support (don't
know how well it worked), but it got removed when the v8 and v9 code was
merged.

[1] not necessarely a bootstrapped llvm-gcc

Best regards,
--Edwin

Nathan_Keynes · February 14, 2010, 10:25pm

Hi Edwin,

The current subversion trunk produces _mostly_ working 32-bit SPARC code now with llvm-gcc, but as noted above it doesn't quite bootstrap gcc yet - there are still some bugs in the generated code. Which is to say, it's not at production level yet. I haven't tested clang, but I would expect it to behave similarly.

I'd also like to see SPARC JIT working, but I don't know when/if anyone will have time to do the work.

Cheers,
Nathan

Chris_Lattner · February 17, 2010, 6:58pm

Thanks Nathan, I applied these as r96492 / r96493. Sorry for the delay, do you have commit access? If not, please contact me offline.

-Chris