[LLVMdev] Cast to SCEVAddRecExpr

[Sanjoy Das]

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