llvm dev - Aug 2015 - 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
         CFI_INSTRUCTION <call frame instruction>; 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


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

On 10 August 2015 at 14:05, Krzysztof Parzyszek via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> -->     %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

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



----- Renato:

On 10 August 2015 at 14:05, Krzysztof Parzyszek via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
 > -->     %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:

On 8/11/2015 8:32 AM, Renato Golin wrote:
 > On 10 August 2015 at 14:05, Krzysztof Parzyszek via llvm-dev
 > <llvm-dev at lists.llvm.org> wrote:
 >> -->     %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:

On 11 August 2015 at 14:54, Krzysztof Parzyszek 
<kparzysz at codeaurora.org> wrote:
 > 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:

On 8/11/2015 9:10 AM, Renato Golin wrote:
 > On 11 August 2015 at 14:54, Krzysztof Parzyszek 
<kparzysz at codeaurora.org> wrote:
 >> 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:

On 11 August 2015 at 15:28, Krzysztof Parzyszek 
<kparzysz at codeaurora.org> wrote:
 > 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:

On 8/11/2015 9:36 AM, Renato Golin wrote:
 >
 > 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




-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation