<div dir="ltr">Also, now that I paid more attention to the mentioned thread: First of all, unfortunately loop rotation is very misunderstood I think. We<br>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<br>textbook terminology.<br>So, to anyone else that read this thread: Loop rotation does a lot of "textbook" things.<br>For one, it does loop inversion. But also, it does loop peeling continuously so that everything in the loop is executed<br>at least once (we may need to put some examples about that online).<br>Then finally, apart from the fact that it is an enabling optimization for transforms such as LICM, it also may do<br>some simplistic movement of invariant code (to the preheader).<br><br>Best,<br>Stefanos</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Παρ, 20 Μαρ 2020 στις 1:54 μ.μ., ο/η Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" target="_blank">stefanos.baziotis@gmail.com</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Jerry,<br><br>I also didn't understand the example. Note that very recently, documentation about loop terminology was added<br>to the loop terminology: <a href="https://llvm.org/docs/LoopTerminology.html#rotated-loops" target="_blank">https://llvm.org/docs/LoopTerminology.html#rotated-loops</a>. We tried to do it in a tutorial style so it may help.<br>If it does not answer your question, please post the LLVM IR example.<br><br>Kind regards,<br>Stefanos</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Παρ, 20 Μαρ 2020 στις 9:26 π.μ., ο/η Johannes Doerfert via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<p>Hi Jerry,</p>
<p><br>
</p>
<p>I cannot follow your example nor do I understand your question.<br>
</p>
<p>Could you please post a minimal but complete LLVM-IR example and
rephrase the question.</p>
<p><br>
</p>
<p>Thanks,</p>
<p> Johannes</p>
<p><br>
</p>
<p><br>
</p>
<div>On 3/19/20 8:47 PM, 林政宗 via llvm-dev
wrote:<br>
</div>
<blockquote type="cite">
<div style="line-height:1.7;color:rgb(0,0,0);font-size:14px;font-family:Arial">
<div style="margin:0px">Hi,</div>
<div style="margin:0px">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.</div>
<div style="margin:0px"><font face="Consolas"><font size="2"><span style="text-align:left;color:rgb(0,0,0);text-transform:none;text-indent:0px;letter-spacing:normal;font-variant:normal;word-spacing:0px;white-space:pre-wrap;float:none;background-color:transparent;display:inline"><div style="background-color:transparent;color:rgb(0,0,0);font-family:Arial;font-size:14px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;margin:0px;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">--------------------------------------------------------------------------</div><div style="background-color:transparent;color:rgb(0,0,0);font-family:Arial;font-size:14px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;margin:0px;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><font style="background-color:transparent;color:rgb(0,0,0);font-family:Consolas;font-size:14px;line-height:23.8px;margin:0px;overflow:visible;padding:0px" face="Consolas"><font style="background-color:transparent;color:rgb(0,0,0);font-family:Consolas;font-size:13.33px;line-height:22.66px;margin:0px;overflow:visible;padding:0px" size="2">loop:</font></font></div><div style="background-color:transparent;color:rgb(0,0,0);font-family:Arial;font-size:14px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;margin:0px;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><font style="background-color:transparent;color:rgb(0,0,0);font-family:Consolas;font-size:14px;line-height:23.8px;margin:0px;overflow:visible;padding:0px" face="Consolas"><font style="background-color:transparent;color:rgb(0,0,0);font-family:Consolas;font-size:13.33px;line-height:22.66px;margin:0px;overflow:visible;padding:0px" size="2"><span style="background-color:transparent;color:rgb(0,0,0);display:inline;float:none;font-family:Consolas;font-size:13.33px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:pre-wrap;word-spacing:0px">A
br X
B
br Y
C
br loop, Z
-------------------------------------------------
Thanks!
Jerry
<h1 style="background-color:transparent;color:rgb(0,0,0);font-family:"Times New Roman";font-size:32px;font-style:normal;font-variant:normal;font-weight:700;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">[LLVMdev] Loop rotation and loop inversion in LLVM?</h1><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><b style="background-color:transparent;color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:700;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">Andrew Trick</b><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><a title="[LLVMdev] Loop rotation and loop inversion in LLVM?" style="background-color:transparent;color:rgb(0,102,204);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:underline;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">atrick at apple.com
</a>
<span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><i style="background-color:transparent;color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:italic;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">Mon May 20 10:36:00 PDT 2013</i><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><ul style="background-color:transparent;color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
<li>Previous message: <a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/062185.html" target="_blank">[LLVMdev] Loop rotation and loop inversion in LLVM?
</a></li>
<li>Next message: <a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/062186.html" target="_blank">[LLVMdev] Vararg Intrinsics still supported?
</a></li>
<li> <b>Messages sorted by:</b>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/date.html#62260" target="_blank">[ date ]</a>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/thread.html#62260" target="_blank">[ thread ]</a>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/subject.html#62260" target="_blank">[ subject ]</a>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/author.html#62260" target="_blank">[ author ]</a>
</li>
</ul><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><hr style="background-color:transparent;color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:center;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:"Times New Roman";font-size:16px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline">
</span><pre style="background-color:transparent;color:rgb(0,0,0);font-family:Consolas;font-size:13.33px;font-style:normal;font-variant:normal;font-weight:400;letter-spacing:normal;text-align:left;text-decoration:none;text-indent:0px;text-transform:none;white-space:pre-wrap;word-spacing:0px">On May 16, 2013, at 5:07 PM, Paul Sokolovsky <<a style="white-space:pre-wrap" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">pmiscml at gmail.com</a>> wrote:
><i style="white-space:pre-wrap"> Hello,
</i>><i style="white-space:pre-wrap">
</i>><i style="white-space:pre-wrap"> I'd be interested in knowing which pass performs loop inversion, i.e.
</i>><i style="white-space:pre-wrap"> transforms while loop into do/while wrapped with if. So, it's pretty
</i>><i style="white-space:pre-wrap"> easy to understand concept, <a style="white-space:pre-wrap" href="http://en.wikipedia.org/wiki/Loop_inversion" target="_blank">http://en.wikipedia.org/wiki/Loop_inversion</a>
</i>><i style="white-space:pre-wrap"> provides description of how its done and motivation, googling gives
</i>><i style="white-space:pre-wrap"> several relevant references, i.e. it's pretty settled term.
</i>><i style="white-space:pre-wrap">
</i>><i style="white-space:pre-wrap"> I also see this transform to be actually performed on trivial strlen
</i>><i style="white-space:pre-wrap"> function by clang -O2. However opt --help or grepping LLVM doesn't give
</i>><i style="white-space:pre-wrap"> any hints.
</i>><i style="white-space:pre-wrap">
</i>><i style="white-space:pre-wrap"> However, -loop-rotate calls attention, described as "A simple loop
</i>><i style="white-space:pre-wrap"> rotation transformation." However, Wikipedia doesn't gives hits for
</i>><i style="white-space:pre-wrap"> that related to compilation/optimization theory, nor google hits are
</i>><i style="white-space:pre-wrap"> relevant either - mostly LLVM-related hits just mentioning the term.
</i>><i style="white-space:pre-wrap">
</i>><i style="white-space:pre-wrap"> Trying -loop-rotate, I see loop being converted to post-condition, but
</i>><i style="white-space:pre-wrap"> don't see if wrapper around it.
</i>><i style="white-space:pre-wrap">
</i>><i style="white-space:pre-wrap"> So, can anyone suggest if LLVM loop rotation is related to loop
</i>><i style="white-space:pre-wrap"> inversion in Wikipedia terms, and if not, what it is.
</i>
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.
><i style="white-space:pre-wrap"> And I hope that this feedback will allow maintainers to make
</i>><i style="white-space:pre-wrap"> documentation clearer and more user-friendly.
</i>
Me too :) Not sure if I’ll get around to it, but I’d be happy to review a patch.
-Andy
><i style="white-space:pre-wrap"> Thanks,
</i>><i style="white-space:pre-wrap"> Paul mailto:<a style="white-space:pre-wrap" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">pmiscml at gmail.com</a>
</i>><i style="white-space:pre-wrap"> _______________________________________________
</i>><i style="white-space:pre-wrap"> LLVM Developers mailing list
</i>><i style="white-space:pre-wrap"> <a style="white-space:pre-wrap" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">LLVMdev at cs.uiuc.edu</a> <a style="white-space:pre-wrap" href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a>
</i>><i style="white-space:pre-wrap"> <a style="white-space:pre-wrap" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</i>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <<a style="white-space:pre-wrap" href="http://lists.llvm.org/pipermail/llvm-dev/attachments/20130520/49bb14f9/attachment.html" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/attachments/20130520/49bb14f9/attachment.html</a>>
</pre>
</span></font></font></div><b>
</b></span></font></font></div>
<div style="margin:0px"><font face="Consolas"><font size="2"><span style="text-align:left;color:rgb(0,0,0);text-transform:none;text-indent:0px;letter-spacing:normal;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;white-space:pre-wrap;float:none;background-color:transparent;display:inline">
</span></font></font><br>
</div>
</div>
<br>
<br>
<span title="neteasefooter">
<p> </p>
</span><br>
<fieldset></fieldset>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</blockquote></div>