llvm dev - Apr 2014 - [LLVMdev] Construction of SCEVAddRecExpr

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)


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;
}


Any help will be apreciated.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140331/b4760dab/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OnFunction.cpp
Type: text/x-c++src
Size: 4013 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140331/b4760dab/attachment.cpp>

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

Hi Nick,

the problem was that I was compiling without any optimization. Now I could see
some AddRecs. Thanks!







On Tuesday, April 1, 2014 4:16 AM, Nick Lewycky <nicholas at mxc.ca>
wrote:
 
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140404/b5c4d495/attachment.html>