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

[Eli Friedman]

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