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>