<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=iso-8859-1">
<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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
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;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 70.85pt 70.85pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1778018477;
mso-list-type:hybrid;
mso-list-template-ids:-213493946 530462360 69009411 69009413 69009409 69009411 69009413 69009409 69009411 69009413;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:-;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:Calibri;
mso-bidi-font-family:"Times New Roman";}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1
{mso-list-id:1833443841;
mso-list-type:hybrid;
mso-list-template-ids:-550202564 -1149492028 69009411 69009413 69009409 69009411 69009413 69009409 69009411 69009413;}
@list l1:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:-;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:Calibri;
mso-bidi-font-family:"Times New Roman";}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
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="SV" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US">In <a href="https://bugs.llvm.org/show_bug.cgi?id=38011">
https://bugs.llvm.org/show_bug.cgi?id=38011</a> (see also </span><a href="https://reviews.llvm.org/D48721"><span lang="EN-US">https://reviews.llvm.org/D48721</span></a><span lang="EN-US">) a problem was revealed related to llvm.loop metadata.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">The fault was that clang added the !llvm.loop metadata to branches outside of the loop (not only the loop latch). That was not handled properly by some opt passes (simplifying cfg) since it ended up merging branch instructions
with different !llvm.loop annotations (and then it kept the wrong metadata on the branch):<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">```<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">!2 = distinct !{!2, !3}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">!3 = !{!"llvm.loop.unroll.count", i32 3}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">!8 = distinct !{!8, !9}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">!9 = !{!"llvm.loop.unroll.count", i32 5}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">*** IR Dump After Combine redundant instructions ***<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">; Function Attrs: nounwind<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">define i32 @test(i32* %a, i32 %n) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">entry:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br label %do.body, !llvm.loop !2<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.body: ; preds = %do.body, %entry<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br i1 %cmp, label %do.body, label %do.end, !llvm.loop !2<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.end: ; preds = %do.body<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br label %do.body6, !llvm.loop !8<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.body6: ; preds = %do.body6, %do.end<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.end18: ; preds = %do.body6<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> ret i32 %add14<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">*** IR Dump After Simplify the CFG ***<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">; Function Attrs: nounwind<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">define i32 @test(i32* %a, i32 %n) local_unnamed_addr #0 {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">entry:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br label %do.body, !llvm.loop !2<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.body: ; preds = %do.body, %entry<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br i1 %cmp, label %do.body, label %do.body6, !llvm.loop !8<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.body6: ; preds = %do.body, %do.body6<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> %i.1 = phi i32 [ %inc15, %do.body6 ], [ 0, %do.body ]<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">do.end18: ; preds = %do.body6<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> ret i32 %add14<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">```<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">As seen above, when do.end is eliminated the metadata on the backward branch in do.body is changed from !2 to !8 due to the misplaced metadata on the branch in do.end.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">D48721 is solving the current problem in clang, but I was thinking that it would be nice to do some improvements in opt as well. Getting the wrong metadata on a loop is probably bad.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">I assume the idea of having the loop metadata on latches is that a latch can’t be shared between different loops (right?).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Wouldn’t it be nice to simply forbid having loop metadata on branches that aren’t latches, by adding such checks in the Verifier?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">I played around a little bit with teaching the IR Verifier in opt to check that !llvm.loop only is put in loop latches.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Something like this might do the trick, when added to Verifier::visitInstruction in lib/IR/Verifier.cpp:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">```<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">#include "llvm/Analysis/LoopInfo.h"<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">if (I.getMetadata(LLVMContext::MD_loop)) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> // FIXME: Is SwitchInst also allowed?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> Assert(isa<BranchInst>(I), "llvm.loop only expected on branches", &I);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> LoopInfo LI;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> LI.analyze(DT);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> Loop* L = LI.getLoopFor(BB);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> Assert(L, "llvm.loop not in a loop", &I);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> Assert(L->isLoopLatch(BB), "llvm.loop not in a latch", &I);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">```<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Note that the above just was a simple test. For example, we do not want to reinitialize LoopInfo for each found occurence of !llvm.loop if doing this properly.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Also note that the above only checks that the branch is in a latch block, not that the branch itself is the latch.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Another problem is that the Verifier is used by lots of tools that currently do not link with LoopInfo from the Analysis code module.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">My question are:<o:p></o:p></span></p>
<ul style="margin-top:0cm" type="disc">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l0 level1 lfo2"><span lang="EN-US">Is it a good idea to detect misplaced llvm.loop metadata or should we protect us from faulty rewrites in some other way?<o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l0 level1 lfo2"><span lang="EN-US">Is the Verifier a good place for this kind of checks, or is there a better place (such as the LoopVerifier pass, but I guess that is not always run before CFG simplification
etc)?<o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l0 level1 lfo2"><span lang="EN-US">Would it be correct to use LoopInfo, or can we do the checks in some other way?<o:p></o:p></span></li></ul>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">/Björn<o:p></o:p></span></p>
</div>
</body>
</html>