<div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div style="margin:0;">Hi,</div><div style="margin:0;">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:0;"><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; display: inline !important; white-space: pre-wrap; orphans: 2; float: none; -webkit-text-stroke-width: 0px; background-color: transparent;"><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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; 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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; 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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow: visible; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow: visible; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; 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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow: visible; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 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-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow: visible; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: pre-wrap; word-spacing: 0px;">A<br><br>br X<br><br>B<br><br>br Y<br><br><br>C<br><br>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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">[LLVMdev] Loop rotation and loop inversion in LLVM?</h1><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">Andrew Trick</b><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</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; orphans: 2; text-align: left; text-decoration: underline; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">atrick at apple.com
</a><br 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;"><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">Mon May 20 10:36:00 PDT 2013</i><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</span><p 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;"></p><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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
<li>Previous message: <a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/062185.html">[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">[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">[ date ]</a>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/thread.html#62260">[ thread ]</a>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/subject.html#62260">[ subject ]</a>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2013-May/author.html#62260">[ author ]</a>
</li>
</ul><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</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; orphans: 2; text-align: center; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;"><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</span><span style="display: inline !important; 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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space: normal; word-spacing: 0px;">
</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; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; 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">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">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">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">LLVMdev at cs.uiuc.edu</a> <a style="white-space: pre-wrap;" href="http://llvm.cs.uiuc.edu/">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">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">http://lists.llvm.org/pipermail/llvm-dev/attachments/20130520/49bb14f9/attachment.html</a>>
</pre><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br></span></font></font></div><b><i></i><u></u><sub></sub><sup></sup><strike></strike><i></i><u></u><sub></sub><sup></sup><strike></strike>
</b></span></font></font></div><div style="margin:0;"><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; display: inline !important; white-space: pre-wrap; orphans: 2; float: none; -webkit-text-stroke-width: 0px; background-color: transparent;"><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br></span></font></font><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br></div></div><br><br><span title="neteasefooter"><p> </p></span>