ARM: Predicated returns considered analyzable?

Hello,

The function ARMBaseInstrInfo::AnalyzeBranch contains the following piece of code:

      } else if (I->isReturn()) {
        // Returns can't be analyzed, but we should run cleanup.
        CantAnalyze = !isPredicated(I);
      } else {

This could lead to cases where for a block that ends with a
conditional return, AnalyzeBranch returns false (i.e. analyzed),
both TBB and FBB are nullptr, and Cond is empty, that is, indicating
no branches at all. Since returns do not have any additional CFG edges corresponding to the "returning", it may happen that the block will appear to have no branches and a single fall-through successor. This may lead to merging the block with its successor, and an example of this is test/CodeGen/Thumb2/thumb2-ifcvt2.ll:

$ llc < test/CodeGen/Thumb2/thumb2-ifcvt2.ll -mtriple=thumbv7-apple-ios

# *** IR Dump After If Converter ***:
# Machine code for function foo: Post SSA
Frame Objects:
   fi#0: size=4, align=4, at location [SP-4]
   fi#1: size=4, align=4, at location [SP-8]
Function Live Ins: %R0, %R1

BB#0: derived from LLVM BB %entry
     Live Ins: %R0 %R1 %R7 %LR %LR %R7
         %SP<def,tied1> = t2STMDB_UPD %SP<tied0>, pred:14, pred:%noreg, %R7<kill>, %LR<kill>; flags: FrameSetup
         CFI_INSTRUCTION <call frame instruction>; flags: FrameSetup
         %R7<def> = tMOVr %SP<kill>, pred:14, pred:%noreg; flags: FrameSetup
         CFI_INSTRUCTION <call frame instruction>; flags: FrameSetup
         t2CMPri %R1<kill>, 0, pred:14, pred:%noreg, %CPSR<imp-def>
         t2CMPri %R0<kill>, 3, pred:1, pred:%CPSR, %CPSR<imp-def>, %CPSR<imp-use,undef>
--> %SP<def,tied1> = t2LDMIA_RET %SP<tied0>, pred:8, pred:%CPSR, %R7<def>, %PC<def>, %SP<imp-use,undef>, %R7<imp-use,undef>, %PC<imp-use,undef>
         tBLXi pred:14, pred:%noreg, <ga:@bar>, <regmask>, %LR<imp-def,dead>, %SP<imp-use>, %SP<imp-def>, %R0<imp-def,dead>
         %SP<def,tied1> = t2LDMIA_RET %SP<tied0>, pred:14, pred:%noreg, %R7<def>, %PC<def>

Here the instruction t2LDMIA_RET is a terminator and yet it's followed by a non-terminator tBLXi. This looks wrong. Does anyone have any comments on this?

-Krzysztof

Isn't it because one of the predicates is CPSR, which means it's a
conditional instruction, so not really a terminator?

This lowers to the expected:

    str lr, [sp, #-4]!
    cmp r1, #0
    it ne
    cmpne r0, #3
    bhi .LBB0_2 <-- Turned into a conditional jump

    bl bar

.LBB0_2:
    ldr lr, [sp], #4
    bx lr

cheers,
--renato

Doh. I missed the list in my first reply... Here's the replay of the conversation:

----- Renato:

> --> %SP<def,tied1> = t2LDMIA_RET %SP<tied0>, pred:8, pred:%CPSR,
> %R7<def>, %PC<def>, %SP<imp-use,undef>, %R7<imp-use,undef>,
> %PC<imp-use,undef>
>
> Here the instruction t2LDMIA_RET is a terminator and yet it's followed by a
> non-terminator tBLXi. This looks wrong. Does anyone have any comments on
> this?

Isn't it because one of the predicates is CPSR, which means it's a
conditional instruction, so not really a terminator?

This lowers to the expected:

     str lr, [sp, #-4]!
     cmp r1, #0
     it ne
     cmpne r0, #3
     bhi .LBB0_2 <-- Turned into a conditional jump

     bl bar

.LBB0_2:
     ldr lr, [sp], #4
     bx lr

cheers,
--renato

----- Me:

>> --> %SP<def,tied1> = t2LDMIA_RET %SP<tied0>, pred:8, pred:%CPSR,
>> %R7<def>, %PC<def>, %SP<imp-use,undef>, %R7<imp-use,undef>,
>> %PC<imp-use,undef>
>>
>> Here the instruction t2LDMIA_RET is a terminator and yet it's followed by a
>> non-terminator tBLXi. This looks wrong. Does anyone have any comments on
>> this?
>
> Isn't it because one of the predicates is CPSR, which means it's a
> conditional instruction, so not really a terminator?

It is marked as a terminator in the table-gen output (ARMGenInstrInfo.inc):

   { 2399, 5, 1, 4, 355, 0|(1ULL<<MCID::Pseudo)|(1ULL<<MCID::Return)|(1ULL<<MCID::Barrier)|(1ULL<<MCID::MayLoad)|(1ULL<<MCID::Predicable)|(1ULL<<MCID::Terminator)|(1ULL<<MCID::Variadic)|(1ULL<<MCID::UnmodeledSideEffects)|(1ULL<<MCID::ExtraDefRegAllocReq), 0x0ULL, nullptr, nullptr, OperandInfo52, -1 ,nullptr }, // Inst #2399 = t2LDMIA_RET

The test isTerminator only checks the MCInstrDesc:

   /// Various passes use this to insert code into the bottom of a basic block,
   /// but before control flow occurs.
   bool isTerminator() const { return Flags & (1 << MCID::Terminator); }

-Krzysztof

----- Renato:

> The test isTerminator only checks the MCInstrDesc:
>
> /// Various passes use this to insert code into the bottom of a basic
> block,
> /// but before control flow occurs.
> bool isTerminator() const { return Flags & (1 << MCID::Terminator); }

I'm guessing this only means "can be terminator". With conditional
terminators there really isn't a way to be certain, and with so many
instructions being conditional in Thumb, it's probably not a good idea
to try and model it perfectly.

Are you relying on isTerminator() for something and getting it wrong?

--renato

----- Me:

>> The test isTerminator only checks the MCInstrDesc:
>>
>> /// Various passes use this to insert code into the bottom of a basic
>> block,
>> /// but before control flow occurs.
>> bool isTerminator() const { return Flags & (1 << MCID::Terminator); }
>
> I'm guessing this only means "can be terminator". With conditional
> terminators there really isn't a way to be certain, and with so many
> instructions being conditional in Thumb, it's probably not a good idea
> to try and model it perfectly.
>
> Are you relying on isTerminator() for something and getting it wrong?

This came up in our local build that has some extra code in if-conversion to predicate a "diamond", but with both sides returning. There was an unrelated problem there, and while I was working on it I found out that we can still generate a basic block with a conditional return in the middle of it. This is the late if-conversion, so it may be that some rules are relaxed at this point.
Still, MBB::getFirstTerminator would return the conditional return even though it may be followed by other instruction, and if it was to happen earlier in the optimization sequence, a lot of things could go wrong. It seems like this is not causing more trouble simply because there is no earlier optimization that could "exploit" this.

To answer your question---no, at this point nothing is catastrophically wrong, but it looks like a problem waiting to happen.

-Krzysztof

----- Renato:

> It seems like this is not causing more trouble simply because there is no
> earlier optimization that could "exploit" this.

I see. This is worrying, but without actual hard data, it's hard to
know how to fix it.

> To answer your question---no, at this point nothing is catastrophically
> wrong, but it looks like a problem waiting to happen.

I'd add a comment to isTerminator() to make sure that people using it
know that it can back-fire if used with predicated code.

--renato

----- Me:

>
> I'd add a comment to isTerminator() to make sure that people using it
> know that it can back-fire if used with predicated code.

Hmm. I'm not sure if this is a proper description. A conditional branch is "predicated". If we allow a conditional return to be in the middle of a basic block at a certain point, should we also allow (at least formally) conditional branches as well? That would imply that there is a point in the optimization sequence after which having "exiting" instructions is allowed in the middle of the block. Since having a conditional branch in the middle is not allowed during early optimizations, a predicated return should also be disallowed there.
Can such a point be formally defined (as in "after pass XYX, is it allowed to have predicated terminators in the middle of a block")?

-Krzysztof

Hi Krzystof,

I’m not sure what the problem is here. For me, the function name “MBB::getFirstTerminator” you quoted implies that there may be more than one terminator. So it not returning the last terminator doesn’t seem surprising at all.

In fact, at this stage a conditional branch (not to a fallthrough block) is represented as a sequence of “B.COND; B”, where both are terminators and one is predicated. I don’t see how conditional returns are any different.

Cheers,

James

The problem is that the first terminator is followed by a non-terminator.

The code snippet from the first email:
     t2CMPri %R1<kill>, 0, pred:14, pred:%noreg, %CPSR<imp-def>
     t2CMPri %R0<kill>, 3, pred:1, pred:%CPSR, %CPSR<imp-def>, %CPSR<imp-use,undef>
(1) %SP<def,tied1> = t2LDMIA_RET %SP<tied0>, pred:8, pred:%CPSR, %R7<def>, %PC<def>, %SP<imp-use,undef>, %R7<imp-use,undef>, %PC<imp-use,undef>
(2) tBLXi pred:14, pred:%noreg, <ga:@bar>, <regmask>, %LR<imp-def,dead>, %SP<imp-use>, %SP<imp-def>, %R0<imp-def,dead>
(3) %SP<def,tied1> = t2LDMIA_RET %SP<tied0>, pred:14, pred:%noreg, %R7<def>, %PC<def>

(1) is a terminator (predicated), (2) is a non-terminator, (3) is a terminator again.

-Krzysztof