llvm dev - Aug 2015 - ARM: Predicated returns considered analyzable?

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

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

On Wed, 12 Aug 2015 at 15:43 Krzysztof Parzyszek via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org         http://llvm.cs.uiuc.edu
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150813/1c3a21a7/attachment.html>

On 8/13/2015 2:46 AM, James Molloy wrote:
>
> 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.
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


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