[LLVMdev] Construction of SCEVAddRecExpr

[Nick Lewycky]

Beckert Frey wrote:
> Hello,
>
> I'm studying how the SCEV analyzis works and how to use it and I could
> not create an example where the SCEV analyzis identifies an expression
> as "SCEVAddRecExpr".
>
> Aren't the expressions below the kind of pattern that should be
> represented as a "AddRecExpr" ?
>
> SCEV: (1 + (2 * %3)
> or
> SCEV: (%1 + (2 * %3)
> or
> SCEV: (%1 + (%2 * %3)

You want a PHI node. It's not an add recurrence unless it's making a 
trip around the loop.

Take a look at test/Analysis/ScalarEvolution/trip-count.ll :

$ opt -analyze -scalar-evolution trip-count.ll
Printing analysis 'Scalar Evolution Analysis' for function 'test':
Classifying expressions for: @test
   %tmp = getelementptr [1000 x i32]* @A, i32 0, i32 %i.0
   -->  {@A,+,sizeof(i32)}<%bb3>         Exits: ((10000 * sizeof(i32)) + @A)
   %tmp2 = add i32 %i.0, 1
   -->  {1,+,1}<nw><%bb3>                Exits: 10001
   %i.0 = phi i32 [ 0, %entry ], [ %tmp2, %bb ]
   -->  {0,+,1}<nuw><%bb3>               Exits: 10000
Determining loop execution counts for: @test
Loop %bb3: backedge-taken count is 10000
Loop %bb3: max backedge-taken count is 10000


> In my experiments they are always recognized as just "AddExpr" (not
> *Rec*). Can someone help me on this? What I'm misunderstanding here?
>
> I'm using the attached code to perform my experiments and this example
> as test input:
>
> int main() {
> int vet1[100], i=0;
>
> for (i=0; i<10; i++) {
> vet1[3*i + 2] = vet1[i];
> }
>
> return 0;
> }

Remember that SCEV runs on IR not C. If you want to discuss what C code 
you're running SCEV over, we need to talk about how you've transformed 
this C into IR. For instance, if you built that with clang -O0 then ran 
SCEV over that it won't work at all because SCEV assumes some basic 
optimizations have already been performed (ie., it works on 
canonicalized IR and doesn't try to replicate the work of other 
optimizations. That would be outside its scope.)

Nick