Николай Лихогруд
2012-Feb-27 16:13 UTC
[LLVMdev] How to unroll loop with non-constant boundary
Dear LLVM,
Consider two loops with one interation -
First with constant lower bound, second with usual non-constant lower
bound:
int main(int argc, char ** argv)
{
int numOfIterations= 1;
int stride=1;
int lowerBound = 1000; - 1st | int lowerBound = argc; - 2nd
int upperBound = lowerBound + (numOfIterations - 1)*stride;
int i = lowerBound;
int s = 0;
while(i <= upperBound)
{
s += i;
i++;
}
return s;
}
After the application of -O3 optimization:
The first loop was unrolled:
define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable
readnone {
entry:
ret i32 1000
}
But the second was not:
define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable
readnone {
entry:
br label %"3"
"3": ; preds =
%entry,
%"3"
%0 = phi i32 [ 0, %entry ], [ %2, %"3" ]
%1 = phi i32 [ %argc, %entry ], [ %3, %"3" ]
%2 = add i32 %0, %1
%3 = add i32 %1, 1
%4 = icmp sgt i32 %3, %argc
br i1 %4, label %"5", label %"3"
"5": ; preds =
%"3"
ret i32 %2
}
The questions:
Is it possible to unroll loop with non-constant boundary using
standard LLVM 3.1 facilities, and, if it is, how I can do that?
Best regards,
Nicolas
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120227/930d1070/attachment.html>
Benjamin Kramer
2012-Feb-27 17:30 UTC
[LLVMdev] How to unroll loop with non-constant boundary
On 27.02.2012, at 17:13, Николай Лихогруд wrote:> Dear LLVM, > > Consider two loops with one interation - > First with constant lower bound, second with usual non-constant lower bound: > > int main(int argc, char ** argv) > { > int numOfIterations= 1; > int stride=1; > int lowerBound = 1000; - 1st | int lowerBound = argc; - 2nd > int upperBound = lowerBound + (numOfIterations - 1)*stride; > > int i = lowerBound; > > int s = 0; > while(i <= upperBound) > { > s += i; > i++; > } > return s; > } > After the application of -O3 optimization: > > The first loop was unrolled: > > define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable readnone { > entry: > ret i32 1000 > } > > But the second was not: > > define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable readnone { > entry: > br label %"3" > > "3": ; preds = %entry, %"3" > %0 = phi i32 [ 0, %entry ], [ %2, %"3" ] > %1 = phi i32 [ %argc, %entry ], [ %3, %"3" ] > %2 = add i32 %0, %1 > %3 = add i32 %1, 1 > %4 = icmp sgt i32 %3, %argc > br i1 %4, label %"5", label %"3" > > "5": ; preds = %"3" > ret i32 %2 > } > > The questions: > Is it possible to unroll loop with non-constant boundary using standard LLVM 3.1 facilities, and, if it is, how I can do that?Hi Nicolas, LLVM misses this optimization because ScalarEvolution's ComputeExitLimitFromICmp doesn't handle signed <= (SLE) and thus can't compute the number of times the loop is executed. I wonder if there's a reason for this, it seems like something simple to add. Attached is a completely untested patch that adds the missing logic. -------------- next part -------------- A non-text attachment was scrubbed... Name: SCEV-compare-equal.patch Type: application/octet-stream Size: 2101 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120227/c9673e93/attachment.obj> -------------- next part -------------- - Ben> > Best regards, > Nicolas > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Eli Friedman
2012-Feb-27 17:49 UTC
[LLVMdev] How to unroll loop with non-constant boundary
On Mon, Feb 27, 2012 at 9:30 AM, Benjamin Kramer <benny.kra at googlemail.com> wrote:> > On 27.02.2012, at 17:13, Николай Лихогруд wrote: > >> Dear LLVM, >> >> Consider two loops with one interation - >> First with constant lower bound, second with usual non-constant lower bound: >> >> int main(int argc, char ** argv) >> { >> int numOfIterations= 1; >> int stride=1; >> int lowerBound = 1000; - 1st | int lowerBound = argc; - 2nd >> int upperBound = lowerBound + (numOfIterations - 1)*stride; >> >> int i = lowerBound; >> >> int s = 0; >> while(i <= upperBound) >> { >> s += i; >> i++; >> } >> return s; >> } >> After the application of -O3 optimization: >> >> The first loop was unrolled: >> >> define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable readnone { >> entry: >> ret i32 1000 >> } >> >> But the second was not: >> >> define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable readnone { >> entry: >> br label %"3" >> >> "3": ; preds = %entry, %"3" >> %0 = phi i32 [ 0, %entry ], [ %2, %"3" ] >> %1 = phi i32 [ %argc, %entry ], [ %3, %"3" ] >> %2 = add i32 %0, %1 >> %3 = add i32 %1, 1 >> %4 = icmp sgt i32 %3, %argc >> br i1 %4, label %"5", label %"3" >> >> "5": ; preds = %"3" >> ret i32 %2 >> } >> >> The questions: >> Is it possible to unroll loop with non-constant boundary using standard LLVM 3.1 facilities, and, if it is, how I can do that? > > Hi Nicolas, > > LLVM misses this optimization because ScalarEvolution's ComputeExitLimitFromICmp doesn't handle signed <= (SLE) and thus can't compute the number of times the loop is executed. I wonder if there's a reason for this, it seems like something simple to add. > > Attached is a completely untested patch that adds the missing logic.Off the top of my head, the attached is missing a check for whether the increment is nsw, and the upper bound computation is wrong. -Eli
Duncan Sands
2012-Feb-27 19:17 UTC
[LLVMdev] How to unroll loop with non-constant boundary
Hi Benjamin,> LLVM misses this optimization because ScalarEvolution's ComputeExitLimitFromICmp doesn't handle signed<= (SLE) and thus can't compute the number of times the loop is executed. I wonder if there's a reason for this, it seems like something simple to add.instsimplify could also be enhanced to clean it up in this particular case, but it would be better to make scev smarter. Ciao, Duncan.
Apparently Analagous Threads
- [LLVMdev] How to unroll loop with non-constant boundary
- [LLVMdev] How to unroll loop with non-constant boundary
- [LLVMdev] How to unroll loop with non-constant boundary
- [LLVMdev] RFC: change BoundsChecking.cpp to use address-based tests
- [LLVMdev] RFC: change BoundsChecking.cpp to use address-based tests