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.

OnFunction.cpp (3.92 KB)

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!

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}<%bb3> Exits: 10001
%i.0 = phi i32 [ 0, %entry ], [ %tmp2, %bb ]
→ {0,+,1}<%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