[LLVMdev] Cast to SCEVAddRecExpr

Nema, Ashutosh Ashutosh.Nema at amd.com
Tue Apr 7 07:32:22 PDT 2015


> That transform is not valid because these two expressions are not
> equivalent if the add recurrence can sign-overflow.  For instance, (i8
> for simplicity) if you consider {sext i8 2 to i16,+, sext i8 2 to i16}
> and (sext i8 {2,+,2} to i16) then in the 63rd iteration the first
> add-recs value is (i16 2) * 63 + (i16 2)  = 128 while the second
> add-rec's value in the same iteration is -128.  
Thanks for this detailed explanation Sanjoy.

> However, if LLVM can
> prove the second expression cannot sign-overflow (i.e. the loop will
> run for < 63 iterations) then transforming (sext i8 {2,+,2} to i16) to
> {sext i8 2 to i16,+, sext i8 2 to i16} is valid.  
Yes, but it's difficult to prove in all types of loop.

> Add recurrences that
> have been proven to not overflow are marked as <nsw>, and are printed
> like {S,+,X}<nsw>.
Where compiler is sure about *will not overflow* (i.e. var[i * 2] ) will be marked as 'nsw'.

Cases where we have power of two will be transformed to shift reduction by Instruction Combiner.
i.e. var[i * 2] will be transformed to var[i << 1] but 'nsw' property was not carried forward.

I have seen your mail thread on this.

If somehow we can preserve 'nsw' property then the 
transformation I suggested looks valid ?

i.e.:
(sext i32 Addrec{2,+,2}<nuw><%for.body4> to i64)
Transformed To:
Addrec{(sext i32 '2' to i64), + , (sext i32 '2' to i64)} <nsw><%for.body4>

This will open up optimization opportunities.

Regards,
Ashutosh

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Wednesday, April 01, 2015 10:11 PM
To: Nema, Ashutosh
Cc: Nick Lewycky; llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] Cast to SCEVAddRecExpr

On Wed, Apr 1, 2015 at 3:06 AM, Nema, Ashutosh <Ashutosh.Nema at amd.com> wrote:
> Thanks Sanjoy.
>
>> To be pedantic, "var[i<<1]" is not an add recurrence, but "&var[i <<
>> 1]" is an add recurrence.  I'll assume that's that you meant.
> Yes, I meant the same.
>
>> I think that is because in C, multiplication is nsw but left shift is
>> not and so "i << 1" can legitimately sign-overflow but i * 2 cannot
>> sign-overflow.  I'd venture a guess that this lets LLVM transform a
>> sign-extend of an add-rec to an add-rec sign-extends.
> I agree here, we want LLVM to transform sign-extend of add-rec to
> add-rec of sign extend in possible cases. Currently I don’t see LLVM is doing this.
> i.e.:
> (sext i32 addrec{2,+,2}<%for.body4> to i64)
> Will convert it to:
> addrec{(sext i32 '2' to i64), + , (sext i32 '2' to i64)} <%for.body4>

That transform is not valid because these two expressions are not
equivalent if the add recurrence can sign-overflow.  For instance, (i8
for simplicity) if you consider {sext i8 2 to i16,+, sext i8 2 to i16}
and (sext i8 {2,+,2} to i16) then in the 63rd iteration the first
add-recs value is (i16 2) * 63 + (i16 2)  = 128 while the second
add-rec's value in the same iteration is -128.  However, if LLVM can
prove the second expression cannot sign-overflow (i.e. the loop will
run for < 63 iterations) then transforming (sext i8 {2,+,2} to i16) to
{sext i8 2 to i16,+, sext i8 2 to i16} is valid.  Add recurrences that
have been proven to not overflow are marked as <nsw>, and are printed
like {S,+,X}<nsw>.

When compiling from C, left shifts operations are not marked nsw
(because in C they are allowed to sign overflow) but the equivalent
multiplies are marked nsw (because sign-overflow of a multiply is
undefined behavior).  This lets LLVM prove {2,+,2} is <nsw> when it
comes from a multiply and lets it commute a sign extend into the add
recurrence.  This explains the difference between var[i << 1] and
var[i * 2].

-- Sanjoy




More information about the llvm-dev mailing list