<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Malgun Gothic";
panose-1:2 11 5 3 2 0 0 2 0 4;}
@font-face
{font-family:"\@Malgun Gothic";}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:60716718;
mso-list-template-ids:1630682302;}
@list l1
{mso-list-id:461192335;
mso-list-type:hybrid;
mso-list-template-ids:1659956624 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2
{mso-list-id:1093471723;
mso-list-template-ids:1770817678;}
@list l3
{mso-list-id:1629971250;
mso-list-type:hybrid;
mso-list-template-ids:1659956624 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l3:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:18.0pt;
text-indent:-18.0pt;}
@list l3:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:54.0pt;
text-indent:-18.0pt;}
@list l3:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:90.0pt;
text-indent:-9.0pt;}
@list l3:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:126.0pt;
text-indent:-18.0pt;}
@list l3:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:162.0pt;
text-indent:-18.0pt;}
@list l3:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:198.0pt;
text-indent:-9.0pt;}
@list l3:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:234.0pt;
text-indent:-18.0pt;}
@list l3:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:270.0pt;
text-indent:-18.0pt;}
@list l3:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:306.0pt;
text-indent:-9.0pt;}
@list l4
{mso-list-id:1658414031;
mso-list-template-ids:-1553444962;}
@list l4:level1
{mso-level-start-at:3;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l5
{mso-list-id:1844398539;
mso-list-template-ids:-2116878964;}
@list l5:level1
{mso-level-start-at:2;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Hi Eli,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have checked the separateNestedLoop function and it seems we can extend the function to handle more cases.<o:p></o:p></p>
<p class="MsoNormal">I have created a review for it. <a href="https://reviews.llvm.org/D105700">
https://reviews.llvm.org/D105700</a><o:p></o:p></p>
<p class="MsoNormal">Please feel free to review it.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks<o:p></o:p></p>
<p class="MsoNormal">JinGu Kang<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Jingu Kang via llvm-dev<br>
<b>Sent:</b> 06 July 2021 11:02<br>
<b>To:</b> Eli Friedman <efriedma@quicinc.com>; llvm-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [llvm-dev] Question about Loop with multiple latches and LICM<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Eli, I appreciate your kind comments.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0cm" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:-18.0pt;mso-list:l3 level1 lfo3">
<i>Why does LoopInfo partition loops the way it does? It’s the most straightforward way to define a “loop”. See
<a href="https://llvm.org/docs/LoopTerminology.html">https://llvm.org/docs/LoopTerminology.html</a> .<o:p></o:p></i></li></ol>
<p class="MsoNormal">Yep, I agree. <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0cm" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:-18.0pt;mso-list:l3 level1 lfo3">
<i>Why doesn’t LoopSimplify split the loop into a nested loop? See separateNestedLoop in llvm/lib/Transforms/Utils/LoopSimplify.cpp; essentially, separating out a nested loop is based on a heuristic, and your example doesn’t trigger that heuristic. I don’t
think anyone has looked at this in a long time</i>.<o:p></o:p></li></ol>
<p class="MsoNormal">Thank you very much for letting me know. It looks like that is what I want to know. Let me have a look.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0cm" start="3" type="1">
<li class="MsoListParagraph" style="margin-left:-18.0pt;mso-list:l3 level1 lfo3">
<i>Why does LICM hoist out conditionally executed instructions? Fewer instructions inside the loop means it’s easier to analyze/optimize. LoopSink can reverse the transform later if it makes sense.<o:p></o:p></i></li></ol>
<p class="MsoNormal">OK, I agree. During reducing the test case, I made a mistake. There was originally nested loop from goto statement and the gep was executed at every iteration of outer loop. I am sorry for wrong explanation.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If I can transform the loop with multiple latches to a nested Loop Simplify Form, it looks like the issues could be gone.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks for good comments again,<o:p></o:p></p>
<p class="MsoNormal">JinGu Kang<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>From:</b> Eli Friedman <<a href="mailto:efriedma@quicinc.com">efriedma@quicinc.com</a>>
<br>
<b>Sent:</b> 06 July 2021 01:42<br>
<b>To:</b> Jingu Kang <<a href="mailto:Jingu.Kang@arm.com">Jingu.Kang@arm.com</a>>;
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> RE: [llvm-dev] Question about Loop with multiple latches and LICM<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I see three questions here:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0cm" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo8">Why does LoopInfo partition loops the way it does? It’s the most straightforward way to define a “loop”. See
<a href="https://llvm.org/docs/LoopTerminology.html">https://llvm.org/docs/LoopTerminology.html</a> .<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo8">Why doesn’t LoopSimplify split the loop into a nested loop? See separateNestedLoop in llvm/lib/Transforms/Utils/LoopSimplify.cpp; essentially, separating out a nested loop is based
on a heuristic, and your example doesn’t trigger that heuristic. I don’t think anyone has looked at this in a long time.<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo8">Why does LICM hoist out conditionally executed instructions? Fewer instructions inside the loop means it’s easier to analyze/optimize. LoopSink can reverse the transform later if
it makes sense.<o:p></o:p></li></ol>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">-Eli<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>From:</b> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>>
<b>On Behalf Of </b>Jingu Kang via llvm-dev<br>
<b>Sent:</b> Monday, July 5, 2021 5:53 AM<br>
<b>To:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> [EXT] [llvm-dev] Question about Loop with multiple latches and LICM<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Hi All,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have a couple of questions about loop multiple latches and LICM. Let see a simple LLVM IR code snippet.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">define void @test(i1 %a, i32 %b, i8* noalias %src, i8* noalias %dst) {<o:p></o:p></p>
<p class="MsoNormal">entry:<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.cond: ; preds = %sw.bb4001, %while.body, %while.body, %entry<o:p></o:p></p>
<p class="MsoNormal"> br i1 %a, label %while.end6895, label %while.body<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.body: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal"> switch i32 %b, label %sw.default6833 [<o:p></o:p></p>
<p class="MsoNormal"> i32 82, label %no_ret<o:p></o:p></p>
<p class="MsoNormal"> i32 30, label %sw.bb4001<o:p></o:p></p>
<p class="MsoNormal"> i32 40, label %while.cond<o:p></o:p></p>
<p class="MsoNormal"> i32 41, label %while.cond<o:p></o:p></p>
<p class="MsoNormal"> ]<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">sw.bb4001: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal"> %addr = getelementptr i8, i8* %src, i32 31<o:p></o:p></p>
<p class="MsoNormal"> %res = load i8, i8* %addr<o:p></o:p></p>
<p class="MsoNormal"> store i8 %res, i8* %dst<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">sw.default6833: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal"> unreachable<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.end6895: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal"> unreachable<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">no_ret: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal"> ret void<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">LLVM detects loop as below.<o:p></o:p></p>
<p class="MsoNormal">Loop at depth 1 containing: %while.cond<header><exiting>,%while.body<latch><exiting>,%sw.bb4001<latch><o:p></o:p></p>
<p class="MsoNormal">Loop at depth 1 containing: <o:p></o:p></p>
<p class="MsoNormal"><header><exiting><o:p></o:p></p>
<p class="MsoNormal">while.cond: ; preds = %sw.bb4001, %while.body, %while.body, %entry<o:p></o:p></p>
<p class="MsoNormal"> br i1 %a, label %while.end6895, label %while.body<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><latch><exiting><o:p></o:p></p>
<p class="MsoNormal">while.body: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal"> switch i32 %b, label %sw.default6833 [<o:p></o:p></p>
<p class="MsoNormal"> i32 82, label %no_ret<o:p></o:p></p>
<p class="MsoNormal"> i32 30, label %sw.bb4001<o:p></o:p></p>
<p class="MsoNormal"> i32 40, label %while.cond<o:p></o:p></p>
<p class="MsoNormal"> i32 41, label %while.cond<o:p></o:p></p>
<p class="MsoNormal"> ]<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><latch><o:p></o:p></p>
<p class="MsoNormal">sw.bb4001: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal" style="text-indent:4.8pt">br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I can see llvm checks header and its backedges and goes through the predecessors of the latches. At this point, I wonder why llvm allows loops to have multiple latches. There is something good from it? Can we choose only one latch from
multiple latches like closest one to header in domtree please?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">After detecting the loop from above IR code, If we run LoopSimplify and LICM pass, we can see below output.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">define void @test(i1 %a, i32 %b, i8* noalias %src, i8* noalias %dst) {<o:p></o:p></p>
<p class="MsoNormal">entry:<o:p></o:p></p>
<p class="MsoNormal"> %addr = getelementptr i8, i8* %src, i32 31 -<span style="font-family:Wingdings">à</span> Hoisted<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.cond: ; preds = %while.cond.backedge, %entry<o:p></o:p></p>
<p class="MsoNormal"> br i1 %a, label %while.end6895, label %while.body<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.body: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal"> switch i32 %b, label %sw.default6833 [<o:p></o:p></p>
<p class="MsoNormal"> i32 82, label %no_ret<o:p></o:p></p>
<p class="MsoNormal"> i32 30, label %sw.bb4001<o:p></o:p></p>
<p class="MsoNormal"> i32 40, label %while.cond.backedge<o:p></o:p></p>
<p class="MsoNormal"> i32 41, label %while.cond.backedge<o:p></o:p></p>
<p class="MsoNormal"> ]<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.cond.backedge: ; preds = %while.body, %while.body, %sw.bb4001<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">sw.bb4001: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal"> %res = load i8, i8* %addr, align 1<o:p></o:p></p>
<p class="MsoNormal"> store i8 %res, i8* %dst, align 1<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond.backedge<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">sw.default6833: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal"> unreachable<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">while.end6895: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal"> unreachable<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">no_ret: ; preds = %while.body<o:p></o:p></p>
<p class="MsoNormal"> ret void<o:p></o:p></p>
<p class="MsoNormal">} <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As you can see, the getelementptr instruction is hoisted to the preheader. If the control flow just reaches to the while.body, the gep is just redundant but it is executed at every iteration of the loop. I can see LICM pass checks the instructions
with isSafeToSpeculativelyExecute but it looks like it is not good enough. At this point, I have other question. LICM pass need to consider something for the instructions which are conditionally executed? Rather than just checking safety of unconditional execution
of the instruction.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Additionally, goto statement causes above CFG.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If there is already something in llvm to handle above case correctly or I missed something, please let me know.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks<o:p></o:p></p>
<p class="MsoNormal">JinGu Kang<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>