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

[Stepan Dyatkovskiy]

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>