llvm dev - Feb 2012 - [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

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

2012/2/27 Benjamin Kramer <benny.kra at googlemail.com>
>
> 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

Hi, Benjamin!
   Thank you for your answer, with your patch it works better.
   But I still have a problem - loops are unrolled only with stride equal
one.
   For example,
   {
    int i = lowerBound;
    int s = 0;
    while(i <= upperBound)
    {
        s += i;
        i+=32;
    }
  }  is not urolled!
  At first, I think that reason is at condition
  if (isSigned) {
        APInt Max = APInt::getSignedMaxValue(BitWidth);
        if ((Max - getSignedRange(getMinusSCEV(Step, One)).getSignedMax())
              .slt(getSignedRange(RHS).getSignedMax()))
          return getCouldNotCompute();
      }
  in "ScalarEvolution::ExitLimit ScalarEvolution::HowManyLessThans(const
SCEV *LHS, const SCEV *RHS,
                                  const Loop *L, bool isSigned)",
    which, In my understanding, is performed for all LHS and RHS with same
bit size and not equal one Step, so function returns getCouldNotCompute(),
please, correct me, if it is not.
   But next, I change type of i to int64_t, that condition become false,
function continued, but loop still was not unrolled.
   So, the questions:
    1. How to overcome upper condition for LHS and RHS with same bit size
and not equal one stride?
    2. What more prevents the calculation of number of interations and how
to deal with it?

Best regards,
      Nicolas
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120228/2abc2cef/attachment.html>