llvm dev - Mar 2012 - [LLVMdev] How to unroll loop with non-constant boundary

Hi guys, 
I attached the modified patch that handles cases with low==end and stride!=1.
Please find it for review.

-Stepan

28.02.2012, 17:41, "Benjamin Kramer" <benny.kra at
googlemail.com>:
> On 27.02.2012, at 20:17, Duncan Sands wrote:
>
>>  Hi Benjamin,
>>>  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.
>>  instsimplify could also be enhanced to clean it up in this particular
case, but
>>  it would be better to make scev smarter.
>
> I filed http://llvm.org/bugs/show_bug.cgi?id=12110 to track this.
>
> - Ben
>
>>  Ciao, Duncan.
>>  _______________________________________________
>>  LLVM Developers mailing list
>>  LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>  http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr12110.patch
Type: application/octet-stream
Size: 5358 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120307/61ebd16b/attachment.obj>

Stepan Dyatkovskiy wrote:
> Hi guys,
> I attached the modified patch that handles cases with low==end and
stride!=1.
I don't see how this could be correct. Your patch treats 'X s<=
Y' as 'X
s< Y+1', which is incorrect when Y is INT_MAX. Wouldn't that turn an 
infinite loop into a zero-trip loop?

To be clear, this is the flaw in Benjamin's patch which you appear to 
have extended that makes it unsuitable for committing to the compiler. 
It would cause miscompiles.

That said, I haven't had the chance to look into fixing this, but 
wouldn't testing AddRec for nsw/nuw be an easy fix that would salvage 
the rest of the logic?

Nick
> Please find it for review.
>
> -Stepan
>
> 28.02.2012, 17:41, "Benjamin Kramer"<benny.kra at
googlemail.com>:
>> On 27.02.2012, at 20:17, Duncan Sands wrote:
>>
>>>   Hi Benjamin,
>>>>   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.
>>>   instsimplify could also be enhanced to clean it up in this
particular case, but
>>>   it would be better to make scev smarter.
>>
>> I filed http://llvm.org/bugs/show_bug.cgi?id=12110 to track this.
>>
>> - Ben
>>
>>>   Ciao, Duncan.
>>>   _______________________________________________
>>>   LLVM Developers mailing list
>>>   LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>   http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

I treat "X s<= Y + Step" as "X s<= Y + 1". If X == Y
(even if Y == INT_MAX) only two cases are possible:
1. Step == 0. Means infinite loop. Could not be unrolled.
2. Step != 0. Loop with only iteration. May be unrolled.

I forgot to fix comments "X s<= Y+1" with the "X s<=
Y+Step". Sorry. Fixed.

-Stepan.

07.03.2012, 12:20, "Nick Lewycky" <nicholas at
mxc.ca>:
> Stepan Dyatkovskiy wrote:
>
>>  Hi guys,
>>  I attached the modified patch that handles cases with low==end and
stride!=1.
>
> I don't see how this could be correct. Your patch treats 'X s<=
Y' as 'X
> s< Y+1', which is incorrect when Y is INT_MAX. Wouldn't that
turn an
> infinite loop into a zero-trip loop?
>
> To be clear, this is the flaw in Benjamin's patch which you appear to
> have extended that makes it unsuitable for committing to the compiler.
> It would cause miscompiles.
>
> That said, I haven't had the chance to look into fixing this, but
> wouldn't testing AddRec for nsw/nuw be an easy fix that would salvage
> the rest of the logic?
>
> Nick
>
>>  Please find it for review.
>>
>>  -Stepan
>>
>>  28.02.2012, 17:41, "Benjamin Kramer"<benny.kra at
googlemail.com>:
>>>  On 27.02.2012, at 20:17, Duncan Sands wrote:
>>>>    Hi Benjamin,
>>>>>    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.
>>>>    instsimplify could also be enhanced to clean it up in this
particular case, but
>>>>    it would be better to make scev smarter.
>>>  I filed http://llvm.org/bugs/show_bug.cgi?id=12110 to track this.
>>>
>>>  - Ben
>>>>    Ciao, Duncan.
>>>>    _______________________________________________
>>>>    LLVM Developers mailing list
>>>>    LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>>    http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>  _______________________________________________
>>>  LLVM Developers mailing list
>>>  LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>  http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>>  _______________________________________________
>>>  LLVM Developers mailing list
>>>  LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>  http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr12110.patch
Type: application/octet-stream
Size: 5370 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120308/e0fa5cc5/attachment.obj>