<br><br><div class="gmail_quote">2012/2/27 Benjamin Kramer <span dir="ltr"><<a href="mailto:benny.kra@googlemail.com">benny.kra@googlemail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5"><br>
On 27.02.2012, at 18:49, Eli Friedman wrote:<br>
<br>
> On Mon, Feb 27, 2012 at 9:30 AM, Benjamin Kramer<br>
> <<a href="mailto:benny.kra@googlemail.com">benny.kra@googlemail.com</a>> wrote:<br>
>><br>
>> On 27.02.2012, at 17:13, ๎ษหฯฬมส ์ษศฯวาีฤ wrote:<br>
>><br>
>>> Dear LLVM,<br>
>>><br>
>>> Consider two loops with one interation -<br>
>>> First with constant lower bound, second with usual non-constant lower bound:<br>
>>><br>
>>> int main(int argc, char ** argv)<br>
>>> {<br>
>>> int numOfIterations= 1;<br>
>>> int stride=1;<br>
>>> int lowerBound = 1000; - 1st | int lowerBound = argc; - 2nd<br>
>>> int upperBound = lowerBound + (numOfIterations - 1)*stride;<br>
>>><br>
>>> int i = lowerBound;<br>
>>><br>
>>> int s = 0;<br>
>>> while(i <= upperBound)<br>
>>> {<br>
>>> s += i;<br>
>>> i++;<br>
>>> }<br>
>>> return s;<br>
>>> }<br>
>>> After the application of -O3 optimization:<br>
>>><br>
>>> The first loop was unrolled:<br>
>>><br>
>>> define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable readnone {<br>
>>> entry:<br>
>>> ret i32 1000<br>
>>> }<br>
>>><br>
>>> But the second was not:<br>
>>><br>
>>> define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable readnone {<br>
>>> entry:<br>
>>> br label %"3"<br>
>>><br>
>>> "3": ; preds = %entry, %"3"<br>
>>> %0 = phi i32 [ 0, %entry ], [ %2, %"3" ]<br>
>>> %1 = phi i32 [ %argc, %entry ], [ %3, %"3" ]<br>
>>> %2 = add i32 %0, %1<br>
>>> %3 = add i32 %1, 1<br>
>>> %4 = icmp sgt i32 %3, %argc<br>
>>> br i1 %4, label %"5", label %"3"<br>
>>><br>
>>> "5": ; preds = %"3"<br>
>>> ret i32 %2<br>
>>> }<br>
>>><br>
>>> The questions:<br>
>>> 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?<br>
>><br>
>> Hi Nicolas,<br>
>><br>
>> 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.<br>
>><br>
>> Attached is a completely untested patch that adds the missing logic.<br>
><br>
> Off the top of my head, the attached is missing a check for whether<br>
> the increment is nsw, and the upper bound computation is wrong.<br>
<br>
</div></div>No doubt, it was just a test if this would work at all.<br>
<br>
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.<br>
<br>
I wonder if that condition could be weakened a bit.<br>
<br>
- Ben</blockquote></div><br><div><div>Hi, Benjamin!</div><div> Thank you for your answer, with your patch it works better.</div><div> But I still have a problem - loops are unrolled only with stride equal one.</div><div>
For example,</div><div> {</div><div> int i = lowerBound;</div><div> int s = 0;</div><div> while(i <= upperBound)</div><div> {</div><div> s += i;</div><div> i+=32;</div><div> }</div><div>
} is not urolled!</div><div> At first, I think that reason is at condition</div><div> if (isSigned) {</div><div> APInt Max = APInt::getSignedMaxValue(BitWidth);</div><div> if ((Max - getSignedRange(getMinusSCEV(Step, One)).getSignedMax())</div>
<div> .slt(getSignedRange(RHS).getSignedMax()))</div><div> return getCouldNotCompute();</div><div> }</div><div> in "ScalarEvolution::ExitLimit ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,</div>
<div> const Loop *L, bool isSigned)",</div><div> 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.</div>
<div> But next, I change type of i to int64_t, that condition become false, function continued, but loop still was not unrolled.</div><div> So, the questions:</div><div> 1. How to overcome upper condition for LHS and RHS with same bit size and not equal one stride?</div>
<div> 2. What more prevents the calculation of number of interations and how to deal with it?</div><div><br></div><div>Best regards,</div><div> Nicolas</div></div>