[LLVMdev] Cast to SCEVAddRecExpr

[Sanjoy Das]

On Mon, Mar 30, 2015 at 8:47 PM, Nema, Ashutosh <Ashutosh.Nema at amd.com> wrote:
> Sorry typo in test case, Please ignore previous mail.
>
> Consider below case:
>
> for (j=1; j < itr; j++) {
>      - - - -
>      for (i=1; i < itr; i++) {
>      {
>        temp=  var[i << 1];
>         - - - - -
>      }
> }
>
> In the above example, we are unable to get "SCEVAddRecExpr" for "var[i  << 1]"

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.

If I run the following example through opt -analyze -scalar-evolution:

define void @x(i1* %c, i64* %ptr) {
 entry:
  br label %loop

 loop:
  %i = phi i64 [ 0, %entry ], [ %i.inc, %loop ]
  %i.inc = add i64 %i, 1
  %d = shl i64 %i.inc, 1
  %gep = getelementptr i64, i64* %ptr, i64 %d
  %cc = load volatile i1, i1* %c
  br i1 %cc, label %exit, label %loop

 exit:
  ret void
}


I get the SCEV -->  {(16 + %ptr),+,16}<%loop> for %gep.  So SCEV /can/
interpret i<<1 as i*2 under some specific circumstances.

Going back to your original question:

> Instead if I change "var[i << 1]" to "var[i * 2]" then I'm getting "SCEVAddRecExpr".

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.

Caveat: I have not looked at the C specification to determine that
left shifts are allowed to sign-overflow.  I concluded that left
shifts are not nsw by looking at the llvm IR emitted by clang (the
left shift generated from "i << 1" is not marked nsw).

-- Sanjoy