[llvm-dev] ARM: Predicated returns considered analyzable?

Wed Aug 12 07:43:07 PDT 2015

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