<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 06:50 AM, Björn
Pettersson A wrote:<br>
</div>
<blockquote type="cite"
cite="mid:HE1PR0702MB37880FD200DA7B6447ED302EB0470@HE1PR0702MB3788.eurprd07.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<meta name="Generator" content="Microsoft Exchange Server">
<!-- converted from rtf -->
<style><!-- .EmailQuote { margin-left: 1pt; padding-left: 4pt; border-left: #800000 2px solid; } --></style>
<font size="2" face="Calibri"><span style="font-size:11pt;">
<div>I tried using FindFunctionBackedges first, before using
LoopInfo.</div>
<div><font face="Calibri">But then the verifier would complain
when having a for-loop like this:</font></div>
<div> </div>
<div><font face="Calibri">define void
@_Z28loop_with_vectorize_metadatav() {</font></div>
<div><font face="Calibri">entry:</font></div>
<div><font face="Calibri"> %i = alloca i32, align 4</font></div>
<div><font face="Calibri"> store i32 0, i32* %i, align 4</font></div>
<div><font face="Calibri"> br label %for.cond</font></div>
<div><font face="Calibri"> </font></div>
<div><font face="Calibri">for.cond:
; preds = %for.inc, %entry</font></div>
<div><font face="Calibri"> %0 = load i32, i32* %i, align 4</font></div>
<div><font face="Calibri"> %cmp = icmp slt i32 %0, 16</font></div>
<div><font face="Calibri"> br i1 %cmp, label %for.body, label
%for.end, !llvm.loop !0</font></div>
<div><font face="Calibri"> </font></div>
<div><font face="Calibri">for.body:
; preds = %for.cond</font></div>
<div><font face="Calibri"> br label %for.inc</font></div>
<div><font face="Calibri"> </font></div>
<div><font face="Calibri">for.inc:
; preds = %for.body</font></div>
<div><font face="Calibri"> %1 = load i32, i32* %i, align 4</font></div>
<div><font face="Calibri"> %inc = add nsw i32 %1, 1</font></div>
<div><font face="Calibri"> store i32 %inc, i32* %i, align 4</font></div>
<div><font face="Calibri"> br label %for.cond</font></div>
<div><font face="Calibri"> </font></div>
<div><font face="Calibri">for.end:
; preds = %for.cond</font></div>
<div><font face="Calibri"> ret void</font></div>
<div><font face="Calibri">}</font></div>
<div> </div>
<div><font face="Calibri">The metadata is on the branch in the
latch (the for.cond block), while the backedge is the
branch in the for.inc block.</font></div>
<div> </div>
<div><font face="Calibri">The LangRef says “Currently, loop
metadata is implemented as metadata attached to the branch
instruction in the loop latch block.”,</font></div>
<div><font face="Calibri">but when I tried generating code
from a for-loop with latest clang on trunk the metadata is
put on the backedge. So maybe it is a fault in the
LangRef?</font></div>
<div> </div>
<div><font face="Calibri">The code above is from
test/Bitcode/upgrade-loop-metadata.ll.bc. But if the
LangRef is wrong, then I assume test case is wrong.</font></div>
</span></font></blockquote>
<br>
My reading of Loop::getLoopID() is that it would miss the llvm.loop
metadata in the loop above (because it checks whether the terminator
has a successor which is the loop header, and if for.cond is the
loop header, then that it's true for that conditional branch).<br>
<br>
Looks to me like the LangRef is correct, in that it matches what the
backend actually recognizes, and the test is wrong.<br>
<br>
-Hal<br>
<br>
<blockquote type="cite"
cite="mid:HE1PR0702MB37880FD200DA7B6447ED302EB0470@HE1PR0702MB3788.eurprd07.prod.outlook.com"><font
size="2" face="Calibri"><span style="font-size:11pt;">
<div> </div>
<div><font face="Calibri">/Björn</font></div>
<div> </div>
<div><b>From:</b> Hal Finkel <a class="moz-txt-link-rfc2396E" href="mailto:hfinkel@anl.gov"><hfinkel@anl.gov></a> <br>
<b>Sent:</b> den 6 juli 2018 13:07<br>
<b>To:</b> Björn Pettersson A
<a class="moz-txt-link-rfc2396E" href="mailto:bjorn.a.pettersson@ericsson.com"><bjorn.a.pettersson@ericsson.com></a>;
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Cc:</b> <a class="moz-txt-link-abbreviated" href="mailto:deepak2427@gmail.com">deepak2427@gmail.com</a><br>
<b>Subject:</b> Re: [llvm-dev] Verify that we only get loop
metadata on latches</div>
<div> </div>
<div> </div>
<div>On 07/06/2018 03:57 AM, Björn Pettersson A via llvm-dev
wrote:</div>
<div>In <a href="https://bugs.llvm.org/show_bug.cgi?id=38011"
moz-do-not-send="true"><font color="blue"><u>https://bugs.llvm.org/show_bug.cgi?id=38011</u></font></a>
(see also <a href="https://reviews.llvm.org/D48721"
moz-do-not-send="true"><font color="blue"><u>https://reviews.llvm.org/D48721</u></font></a>)
a problem was revealed related to llvm.loop metadata.</div>
<div> </div>
<div>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):</div>
<div> </div>
<div>```</div>
<div>!2 = distinct !{!2, !3}</div>
<div>!3 = !{!"llvm.loop.unroll.count", i32 3}</div>
<div>!8 = distinct !{!8, !9}</div>
<div>!9 = !{!"llvm.loop.unroll.count", i32 5}</div>
<div>*** IR Dump After Combine redundant instructions ***</div>
<div>; Function Attrs: nounwind</div>
<div>define i32 @test(i32* %a, i32 %n) {</div>
<div>entry:</div>
<div> br label %do.body, !llvm.loop !2</div>
<div> </div>
<div>do.body: ; preds
= %do.body, %entry</div>
<div> …</div>
<div> br i1 %cmp, label %do.body, label %do.end, !llvm.loop
!2</div>
<div> </div>
<div>do.end: ; preds
= %do.body</div>
<div> br label %do.body6, !llvm.loop !8</div>
<div> </div>
<div>do.body6: ; preds
= %do.body6, %do.end</div>
<div> …</div>
<div> br i1 %cmp17, label %do.body6, label %do.end18,
!llvm.loop !8</div>
<div> </div>
<div>do.end18: ; preds
= %do.body6</div>
<div> ret i32 %add14</div>
<div>}</div>
<div>*** IR Dump After Simplify the CFG ***</div>
<div>; Function Attrs: nounwind</div>
<div>define i32 @test(i32* %a, i32 %n) local_unnamed_addr #0 {</div>
<div>entry:</div>
<div> br label %do.body, !llvm.loop !2</div>
<div> </div>
<div>do.body: ; preds
= %do.body, %entry</div>
<div> …</div>
<div> br i1 %cmp, label %do.body, label %do.body6, !llvm.loop
!8</div>
<div> </div>
<div>do.body6: ; preds
= %do.body, %do.body6</div>
<div> %i.1 = phi i32 [ %inc15, %do.body6 ], [ 0, %do.body ]</div>
<div> …</div>
<div> br i1 %cmp17, label %do.body6, label %do.end18,
!llvm.loop !8</div>
<div> </div>
<div>do.end18: ; preds
= %do.body6</div>
<div> ret i32 %add14</div>
<div>}</div>
<div>```</div>
<div> </div>
<div>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.</div>
<div> </div>
<div>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.</div>
<div>I assume the idea of having the loop metadata on latches
is that a latch can’t be shared between different loops
(right?).</div>
<div>Wouldn’t it be nice to simply forbid having loop metadata
on branches that aren’t latches, by adding such checks in
the Verifier?</div>
<div><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>
</div>
<div> </div>
<div>I played around a little bit with teaching the IR
Verifier in opt to check that !llvm.loop only is put in loop
latches.</div>
<div>Something like this might do the trick, when added to
Verifier::visitInstruction in lib/IR/Verifier.cpp:</div>
<div> </div>
<div>```</div>
<div>#include "llvm/Analysis/LoopInfo.h"</div>
<div> </div>
<div>if (I.getMetadata(LLVMContext::MD_loop)) {</div>
<div> // FIXME: Is SwitchInst also allowed?</div>
<div> Assert(isa<BranchInst>(I), "llvm.loop only
expected on branches", &I);</div>
<div> LoopInfo LI;</div>
<div> LI.analyze(DT);</div>
<div> Loop* L = LI.getLoopFor(BB);</div>
<div> Assert(L, "llvm.loop not in a loop", &I);</div>
<div> Assert(L->isLoopLatch(BB), "llvm.loop not in a
latch", &I);</div>
<div>}</div>
<div>```</div>
<div> </div>
<div>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.</div>
<div>Also note that the above only checks that the branch is
in a latch block, not that the branch itself is the latch.</div>
<div>Another problem is that the Verifier is used by lots of
tools that currently do not link with LoopInfo from the
Analysis code module.</div>
<div> </div>
<div>My question are:</div>
<ul style="margin:0 36pt 0 0;padding-left:72pt;">
<li>Is it a good idea to detect misplaced llvm.loop metadata
or should we protect us from faulty rewrites in some other
way?</li>
<li>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)?</li>
<li>Would it be correct to use LoopInfo, or can we do the
checks in some other way?</li>
</ul>
<div> </div>
<div>/Björn</div>
<div><br>
<br>
</div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">_______________________________________________</span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">LLVM Developers mailing list</span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;"><a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true"><font color="blue"><u>llvm-dev@lists.llvm.org</u></font></a></span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;"><a
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
moz-do-not-send="true"><font color="blue"><u>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</u></font></a></span></font></div>
<div><br>
</div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">-- </span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">Hal Finkel</span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">Lead, Compiler Technology and
Programming Languages</span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">Leadership Computing Facility</span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;">Argonne National Laboratory</span></font></div>
<div><font size="2" face="Courier New"><span
style="font-size:10pt;"> </span></font></div>
</span></font>
</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>