[LLVMdev] How to unroll loop with non-constant boundary

[Benjamin Kramer]

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