[llvm-dev] questionabout loop rotation

Fri Mar 20 05:10:09 PDT 2020

Also, now that I paid more attention to the mentioned thread: First of all,
unfortunately loop rotation is very misunderstood I think. We
hope that with the loop terminology part we can help in that matter. And
Michael (CC'd), it may be a good idea to add some
textbook terminology.
So, to anyone else that read this thread: Loop rotation does a lot of
"textbook" things.
For one, it does loop inversion. But also, it does loop peeling
continuously so that everything in the loop is executed
at least once (we may need to put some examples about that online).
Then finally, apart from the fact that it is an enabling optimization for
transforms such as LICM, it also may do
some simplistic movement of invariant code (to the preheader).

Best,
Stefanos

Στις Παρ, 20 Μαρ 2020 στις 1:54 μ.μ., ο/η Stefanos Baziotis <
stefanos.baziotis at gmail.com> έγραψε:

> Hi Jerry,
>
> I also didn't understand the example. Note that very recently,
> documentation about loop terminology was added
> to the loop terminology:
> https://llvm.org/docs/LoopTerminology.html#rotated-loops. We tried to do
> it in a tutorial style so it may help.
> If it does not answer your question, please post the LLVM IR example.
>
> Kind regards,
> Stefanos
>
> Στις Παρ, 20 Μαρ 2020 στις 9:26 π.μ., ο/η Johannes Doerfert via llvm-dev <
> llvm-dev at lists.llvm.org> έγραψε:
>
>> Hi Jerry,
>>
>>
>> I cannot follow your example nor do I understand your question.
>>
>> Could you please post a minimal but complete LLVM-IR example and rephrase
>> the question.
>>
>>
>> Thanks,
>>
>>   Johannes
>>
>>
>>
>> On 3/19/20 8:47 PM, 林政宗 via llvm-dev wrote:
>>
>> Hi,
>> I have read an email from the mail list. And I have a question about loop
>> rotation. What is it if it is the case below.
>> --------------------------------------------------------------------------
>> loop:
>> A br X B br Y C br loop, Z
>> ------------------------------------------------- Thanks! Jerry [LLVMdev]
>> Loop rotation and loop inversion in LLVM? *Andrew Trick* atrick at
>> apple.com *Mon May 20 10:36:00 PDT 2013*
>>
>>    - Previous message: [LLVMdev] Loop rotation and loop inversion in
>>    LLVM? <http://lists.llvm.org/pipermail/llvm-dev/2013-May/062185.html>
>>    - Next message: [LLVMdev] Vararg Intrinsics still supported?
>>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/062186.html>
>>    - *Messages sorted by:* [ date ]
>>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/date.html#62260> [
>>    thread ]
>>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/thread.html#62260> [
>>    subject ]
>>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/subject.html#62260> [
>>    author ]
>>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/author.html#62260>
>>
>> ------------------------------
>>
>> On May 16, 2013, at 5:07 PM, Paul Sokolovsky <pmiscml at gmail.com <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>> wrote:
>>
>> >* Hello,
>> *> >* I'd be interested in knowing which pass performs loop inversion, i.e.
>> *>* transforms while loop into do/while wrapped with if. So, it's pretty
>> *>* easy to understand concept, http://en.wikipedia.org/wiki/Loop_inversion <http://en.wikipedia.org/wiki/Loop_inversion>
>> *>* provides description of how its done and motivation, googling gives
>> *>* several relevant references, i.e. it's pretty settled term.
>> *> >* I also see this transform to be actually performed on trivial strlen
>> *>* function by clang -O2. However opt --help or grepping LLVM doesn't give
>> *>* any hints.
>> *> >* However, -loop-rotate calls attention, described as "A simple loop
>> *>* rotation transformation." However, Wikipedia doesn't gives hits for
>> *>* that related to compilation/optimization theory, nor google hits are
>> *>* relevant either - mostly LLVM-related hits just mentioning the term.
>> *> >* Trying -loop-rotate, I see loop being converted to post-condition, but
>> *>* don't see if wrapper around it.
>> *> >* So, can anyone suggest if LLVM loop rotation is related to loop
>> *>* inversion in Wikipedia terms, and if not, what it is.
>> *
>> On simple ‘for’ loops, rotation degenerates to inversion. Rotation is a more general transform that spans the range from inversion to loop peeling...
>>
>> loop:
>> A
>> br X
>> B
>> br loop, Y
>>
>> A’
>> br X
>> loop:
>> B
>> br Y
>> A
>> br loop, X
>>
>> Sorry I don’t know of a text-book reference off-hand. I’ve seen it in practice before and assumed it was pretty standard. In LLVM it’s mostly used to put loops in a canonical form, but it’s also a cheap and dirty way to expose LICM. Another benefit is simplifying trip count expressions.
>>
>> >* And I hope that this feedback will allow maintainers to make
>> *>* documentation clearer and more user-friendly.
>> *
>> Me too :) Not sure if I’ll get around to it, but I’d be happy to review a patch.
>>
>> -Andy
>>
>> >* Thanks,
>> *>* Paul                          mailto:pmiscml at gmail.com <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>> *>* _______________________________________________
>> *>* LLVM Developers mailing list
>> *>* LLVMdev at cs.uiuc.edu <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>         http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>> *>* http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>> *
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130520/49bb14f9/attachment.html>
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing listllvm-dev at lists.llvm.orghttps://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200320/94066c5b/attachment.html>