<div dir="ltr">Hi Jerry,<br><br>First of all, it's useful if you send the examples in <a href="https://godbolt.org/">https://godbolt.org/</a>. It's useful for you too, because you can run llvm parts remotely.<br>Second, it's useful if you pass your examples through a pass like -sroa [1] or -mem2reg [2] so that you can have a code<br>that follows SSA kind flow (i.e. using PHI nodes) and not memory kind flow (i.e. using loads and stores).<br>Probably your example came straight out of Clang which generates the simplest possible IR.<br><br>If you put your example through -sroa, you will end with something like that: <a href="https://godbolt.org/z/EKW_YQ">https://godbolt.org/z/EKW_YQ</a><br>I also removed the BB %for.cond.2 because it was unused (you can actually see that it has no preds).<br>Same for %cmp1 and %cmp2. Finally, I put the C equivalent code on the top.<br><br>Ok now, what loop rotation will do. You can see that in godbolt actually by passing the -loop-rotate argument.<br>But let's understand more. If you read the loop terminology part I referenced above, you can see that loop rotation<br>converts loops to do-while loops. So, this is what we expect. We also expect that it will insert a guard.<br>Because it can't guarantee in any way that the loop will execute at least once.<br><br>Here's the output: <a href="https://godbolt.org/z/FTced-">https://godbolt.org/z/FTced-</a><br><br>At the LLVM IR level there are a couple of important things. First of all, the check was previously on the "top"<br>(which is the header which is the BB of the loop that dominates all others) while now has been moved to the "bottom"<br>(i.e. the latch, which is the block that branches back to the header).<br><br>There is also another thing that happened: The loop is simplified. You can read when a loop is simplified<br>in the loop terminology. It was before, because the %entry was the preheader, it had a latch<br>and it had dedicated exists. But loop rotation broke that, so it had to re-simplify it. In that case,<br>it inserted 2 blocks: <a href="http://for.body.lr.ph">for.body.lr.ph</a>, so that the loop has a preheader.<br>Also, for.cond.for.end_crit_edge, so that the loop has dedicated exists. Because otherwise,<br>an exiting block of the loop jumps to %for.end but also %entry jumps there, which is not part of the loop.<br><br>Although in this case this block also acts as an LCSSA closing phi node but that's another story.<br>I'll not go into that because there's no doc yet.<br><br>This is not a representative case of loop rotation because it does not really enable other optimizations<br>that e.g. could hoist things into the preheader because they know that the loop is executed at least<br>once (check the loop terminology examples in the end).<br><br>As for loop peeling, I don't think there's a specific pass that does that. There's a part of loop unrolling<br>that does loop peeling but I think it needs PGO last time I saw. I don't think loop peeling in this<br>loop would do anything. It doesn't seem to be anything interesting to do here. If you had a comparison<br>inside, like let's say if (i < 2), _then_ it could start doing very interesting things. Consider<br>that loop rotation, because of the guard, will guarantee that the loop will execute at least once.<br>So then you can peel off the first 2 iterations outside (and before) the loop (but inside the guard) and remove this if<br>completely.<br><br>Btw, off-topic but you might want to see what -indvars does to this loop. It's one of the amazing cases<br>that a O(n) algorithm is converted to O(1).<br><br>Best,<br>Stefanos<br><br>[1] <a href="https://llvm.org/docs/Passes.html#sroa-scalar-replacement-of-aggregates">https://llvm.org/docs/Passes.html#sroa-scalar-replacement-of-aggregates</a><br>[2] <a href="https://llvm.org/docs/Passes.html#mem2reg-promote-memory-to-register">https://llvm.org/docs/Passes.html#mem2reg-promote-memory-to-register</a></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Τρί, 24 Μαρ 2020 στις 3:43 π.μ., ο/η 林政宗 via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">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 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"><span style="float:none;background-color:rgb(255,255,255);color:rgb(0,0,0);font-family:Arial;font-size:14px;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">Johannes</span></div><div style="margin:0px"><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br></div><div style="margin:0px">Maybe I'm not that clear, my question is how the loop rotation pass would transform the example I sent you before. </div><div style="margin:0px">what would loop rotation do? And what would loop peeling do?</div><div style="margin:0px"><br></div><div style="margin:0px">Thanks,</div><div style="margin:0px">Jerry</div><div style="margin:0px"><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br></div><p style="margin:0px"><br></p><p style="margin:0px"><br></p><p style="margin:0px"><br></p><p style="margin:0px"><br></p><div style="zoom:1"></div><div id="gmail-m_8970981123089705498divNeteaseMailCard"></div><p style="margin:0px"><br></p><p>At 2020-03-20 15:25:28, "Johannes Doerfert" <<a href="mailto:johannesdoerfert@gmail.com" target="_blank">johannesdoerfert@gmail.com</a>> wrote:</p><blockquote id="gmail-m_8970981123089705498isReplyContent" style="padding-left:1ex;margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)">
<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 face="Consolas" 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"><font size="2" 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">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 face="Consolas" 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"><font size="2" 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"><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>
</blockquote></div><br><br><span title="neteasefooter"><p> </p></span>_______________________________________________<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>