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

[Benjamin Kramer]

On 27.02.2012, at 18:49, Eli Friedman wrote:

> 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.

No doubt, it was just a test if this would work at all.

Looking deeper into SCEV, this should really be canonicalized in SimplifyICmpOperands. Currently it checks whether the value cannot possibly be the maximum or minimum signed value and only does the transform if that's the case.

I wonder if that condition could be weakened a bit.

- Ben