<html>
<head>
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<div class="moz-cite-prefix">On 07/06/2018 03:57 AM, Björn
Pettersson A via llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:HE1PR0702MB37887B4CBE6A2F76587AC273B0470@HE1PR0702MB3788.eurprd07.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<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]-->
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US">In <a
href="https://bugs.llvm.org/show_bug.cgi?id=38011"
moz-do-not-send="true">
https://bugs.llvm.org/show_bug.cgi?id=38011</a> (see also
</span><a href="https://reviews.llvm.org/D48721"
moz-do-not-send="true"><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?</span></p>
</div>
</blockquote>
<br>
I don't know. The existing rationale for not checking this, as I
recall, is to allow for non-loop-aware CFG restructuring operations
to operate on loops without worrying about what to do with this
metadata. This is consistent with our general philosophy of allowing
non-loop-aware CFG restructuring in general (although I'll point out
that SimplifyCFG, for example, has been made effectively loop aware
in order to avoid disturbing canonical loop forms).<br>
<br>
I can certainly see an argument for not allowing this, and that is
that, like for instructions, if a pass moves or changes an
instruction then it must clear all metadata it does not know to
still be valid, and for a transformation changing the CFG, that
would apply to the branch instructions it modified.<br>
<br>
I'll note, however, that it's possible to change a latch block for a
canonical loop into one for a non-canonical loop without touching
the latch itself. Imagine a transformation that examined a block
with many predecessors (this happens to be a loop header and the
predecessors are the pre-header and several different latch blocks,
but it doesn't know that), and introduces a new block and inserts it
into the CFG in between this block and most, but not all, of its
predecessors. Thus, I don't think that you can use LoopInfo to
verify the metadata. You'll need to collect backedges and verify
that the metadata is on such an edge. We have a function,
FindFunctionBackedges, for this purpose (this is what is used by
SimplifyCFGPass to find backedges for its pseudo-loop-awareness).<br>
<br>
-Hal<br>
<br>
<blockquote type="cite"
cite="mid:HE1PR0702MB37887B4CBE6A2F76587AC273B0470@HE1PR0702MB3788.eurprd07.prod.outlook.com">
<div class="WordSection1">
<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">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>
<!--'"--><br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>