<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jul 1, 2020 at 7:34 AM Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<p><br>
</p>
<div>On 7/1/20 12:40 AM, Michael Kruse via
llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">To illustrate some difficulties with FileCheck,
lets make a non-semantic change in LLVM:<br>
<br>
<font face="monospace"> ---
a/llvm/lib/Analysis/VectorUtils.cpp<br>
+++ b/llvm/lib/Analysis/VectorUtils.cpp<br>
@@ -642,8 +642,8 @@ MDNode *llvm::uniteAccessGroups(MDNode
*AccGroups1, MDNode *AccGroups2) {<br>
return AccGroups1;<br>
<br>
SmallSetVector<Metadata *, 4> Union;<br>
- addToAccessGroupList(Union, AccGroups1);<br>
addToAccessGroupList(Union, AccGroups2);<br>
+ addToAccessGroupList(Union, AccGroups1);<br>
<br>
if (Union.size() == 0)<br>
return nullptr;</font><br>
<br>
This changes the order of access groups when merging them.<br>
Same background: Access groups are used to mark that a
side-effect (e.g. memory access) does not limit the
parallelization of a loop, added by e.g. #pragma clang loop
vectorize(assume_safety). Therefore a loop can be assumed to be
parallelizable without further dependency analysis if all its
side-effect instructions are marked this way (and has no
loop-carried scalar dependencies).<br>
An access group represents the instructions marked for a
specific loop. A single instruction can be parallel with regrads
to multiple loop, i.e. belong to multiple access groups. The
order of the access groups is insignificant, i.e. whether either
`AccGroups1` or `AccGroups2` comes first, the instruction is
marked parallel for both loops.<br>
<br>
Even the change should have no effect on correctness, `ninja
check-llvm` fails:<br>
<br>
test/Transforms/Inline/parallel-loop-md-merge.ll<br>
<br>
<font face="monospace"> string not found in input<br>
; CHECK: ![[ACCESSES_INNER]] =
!{!"llvm.loop.parallel_accesses", ![[ACCESS_GROUP_INNER]]}<br>
^<br>
<stdin>:45:1: note: scanning from here<br>
!7 = !{!"llvm.loop.parallel_accesses", !5}<br>
^<br>
<stdin>:45:1: note: with "ACCESSES_INNER" equal to
"7"<br>
!7 = !{!"llvm.loop.parallel_accesses", !5}<br>
^<br>
<stdin>:45:1: note: with "ACCESS_GROUP_INNER" equal
to "4"<br>
!7 = !{!"llvm.loop.parallel_accesses", !5}<br>
^</font><br>
<br>
The line FileCheck points to has nothing to do with the changed
order of access groups.<br>
(what's the point of annotating the `!7 = ...` line repeatedly?
Why not pointing to the lines where
ACCESSES_INNER/ACCESS_GROUP_INNER have their values from?)<br>
<br>
The CHECK lines, annotated with their line numbers from
parallel-loop-md-merge.ll, are:<br>
<br>
<font face="monospace"> 68 ; CHECK: store double
4.200000e+01, {{.*}} !llvm.access.group
![[ACCESS_GROUP_LIST_3:[0-9]+]]<br>
69 ; CHECK: br label %for.cond.i, !llvm.loop
![[LOOP_INNER:[0-9]+]]<br>
70 ; CHECK: br label %for.cond, !llvm.loop
![[LOOP_OUTER:[0-9]+]]<br>
71<br>
72 ; CHECK: ![[ACCESS_GROUP_LIST_3]] =
!{![[ACCESS_GROUP_INNER:[0-9]+]],
![[ACCESS_GROUP_OUTER:[0-9]+]]}<br>
73 ; CHECK: ![[ACCESS_GROUP_INNER]] = distinct !{}<br>
74 ; CHECK: ![[ACCESS_GROUP_OUTER]] = distinct !{}<br>
75 ; CHECK: ![[LOOP_INNER]] = distinct !{![[LOOP_INNER]],
![[ACCESSES_INNER:[0-9]+]]}<br>
76 ; CHECK: ![[ACCESSES_INNER]] =
!{!"llvm.loop.parallel_accesses", ![[ACCESS_GROUP_INNER]]}<br>
77 ; CHECK: ![[LOOP_OUTER]] = distinct !{![[LOOP_OUTER]],
![[ACCESSES_OUTER:[0-9]+]]}<br>
78 ; CHECK: ![[ACCESSES_OUTER]] =
!{!"llvm.loop.parallel_accesses", ![[ACCESS_GROUP_OUTER]]}</font><br>
<br>
And the output of `FileCheck --dump-input -v` is:<br>
<br>
<font face="monospace"> 38: !0 = !{!1}<br>
39: !1 = distinct !{!1, !2, !"callee: %A"}<br>
40: !2 = distinct !{!2, !"callee"}<br>
41: !3 = !{!4, !5}<br>
check:72 ^~~~~~~~~~~~~~<br>
42: !4 = distinct !{}<br>
check:73 ^~~~~~~~~~~~~~~~~<br>
43: !5 = distinct !{}<br>
check:74 ^~~~~~~~~~~~~~~~~<br>
44: !6 = distinct !{!6, !7}<br>
check:75 ^~~~~~~~~~~~~~~~~~~~~~~<br>
45: !7 = !{!"llvm.loop.parallel_accesses", !5}<br>
check:76 X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error:
no match found<br>
46: !8 = distinct !{!8, !9}<br>
check:76 ~~~~~~~~~~~~~~~~~~~~~~~<br>
47: !9 = !{!"llvm.loop.parallel_accesses", !4}<br>
check:76 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~</font><br>
<br>
To fix this regression test, one needs to solve the following
questions:
<ul>
<li> Is `!0 = !{!1}` supposed to match with anything?</li>
<li> Which of the CHECK lines are the ones that are important
for the regression tests?</li>
<li> The `![[SOMETHING]] = distinct !{}` line appears twice.
Which one is ACCESS_GROUP_INNER/ACCESS_GROUP_OUTER? </li>
<li> There are two lines with `llvm.loop.parallel_accesses` as
well. The author of this regression test was kind enough to
give the placeholders descriptive names, but do they match
with what FileCheck matched? </li>
<li> LOOP_INNER and LOOP_OUTER are only distinguished by
position and `.i`. Why does the inner loop come first? </li>
<li> Before the patch that modifies the order, the output of
--dump-input=always was:</li>
</ul>
<font face="monospace"> 38: !0 = !{!1}<br>
39: !1 = distinct !{!1, !2, !"callee: %A"}<br>
40: !2 = distinct !{!2, !"callee"}<br>
41: !3 = !{!4, !5}<br>
42: !4 = distinct !{}<br>
43: !5 = distinct !{}<br>
44: !6 = distinct !{!6, !7}<br>
45: !7 = !{!"llvm.loop.parallel_accesses", !4}<br>
46: !8 = distinct !{!8, !9}<br>
47: !9 = !{!"llvm.loop.parallel_accesses", !5}</font><br>
<br>
This seems to suggest that our change caused !4 and !5 in lines
45 and 47 to swap. This is not what the patch did, which changes
to order of two MDNode arguments. The only MDNode that has two
other MDNodes as operands is line (line !6 and !8 are
representing loops as they reference themselves as first
arguments; noalias scopes do this as well, but there is no
noalias metadata in this example).<br>
<br>
An hasty fix is to change CHECK lines 76 and 77 to<br>
<font face="monospace"><br>
76 ; CHECK: ![[ACCESSES_INNER]] =
!{!"llvm.loop.parallel_accesses", ![[ACCESS_GROUP_OUTER]]}<br>
78 ; CHECK: ![[ACCESSES_OUTER]] =
!{!"llvm.loop.parallel_accesses", ![[ACCESS_GROUP_INNER]]}</font><br>
<br>
However, ACCESS_GROUP_OUTER belongs to ACCESSES_INNER and
ACCESS_GROUP_INNER to ACCESSES_OUTER? This cannot be true.<br>
<br>
<br>
The reason is that MDNodes are emitted in topological order of a
depth-first search. The patch changed the order of
ACCESS_GROUP_INNER and ACCESS_GROUP_OUTER in line 41 but because
in the mitted IR file, the first argument of !3 is emitted
before the second argument, ACCESS_GROUP_OUTER is on line 42 and
ACCESS_GROUP_INNER on line 43 instead.<br>
<br>
Even though this regression test uses proper regex-ing of
metadata node numbers, it is still fragile as it fails on
irrelevant changes. Once it fails, it requires time to fix
properly because it is non-obvious which lines are intended to
match which output lines. The hasty fix would have mixed up
ACCESS_GROUP_OUTER/ACCESS_GROUP_INNER and I wouldn't expect
someone who is working on the inliner to take the time to
understand all the loop metadata. Set-semantics of metadata
occurs often, such as noalias metadata, loop properties, tbaa
metadata, etc.<br>
<br>
The difficulty gets amplified when there are multiple functions
in the regression tests; metadata of all functions all appended
to the end and MDNodes with same content uniqued, making it
impossible to associate particular MDNodes with specific
functions.<br>
<br>
<br>
Ideally the regression test would be robust and understandable,
achievable with two asserts in a unittest:<br>
<br>
<font face="monospace"> Loop &OuterLoop =
*LI->begin();<br>
ASSERT_TRUE(OuterLoop.isAnnotatedParallel());<br>
Loop &InnerLoop = *OuterLoop.begin();<br>
ASSERT_TRUE(InnerLoop.isAnnotatedParallel());</font><br>
</div>
</blockquote>
<p><br>
</p>
<p>I definitely agree that we should not be trying to do this kind
of checking using textual metadata-node matching in FileCheck. The
alternative already available is to add an analysis pass with some
kind of verifier output. This output, not the raw metadata itself,
can be checked by FileCheck. We also need to check the
verification code, but at least that's something we can keep just
in one place. For parallel annotations, we already have such a
thing (we can run opt -loops -analyze; e.g., in
test/Analysis/LoopInfo/annotated-parallel-complex.ll). We also do
this kind of thing for the cost model (by running with -cost-model
-analyze). To what extent would making more-extensive use of this
technique address the use cases you're trying to address?</p></div></blockquote><div>In MLIR we create passes specifically for the purpose of testing this kind of thing: the pass would traverse a structure and dump it in a textual form. This is useful as a tool for developers, but mostly makes it really nice to write FileCheck tests.</div><div><br></div><div>For example our dominance test is: <a href="https://github.com/llvm/llvm-project/blob/master/mlir/test/Analysis/test-dominance.mlir">https://github.com/llvm/llvm-project/blob/master/mlir/test/Analysis/test-dominance.mlir</a></div><div>The test pass is here: <a href="https://github.com/llvm/llvm-project/blob/master/mlir/test/lib/Transforms/TestDominance.cpp">https://github.com/llvm/llvm-project/blob/master/mlir/test/lib/Transforms/TestDominance.cpp</a></div><div><br></div><div>-- </div><div>Mehdi</div><div><br></div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div>
<p>Maybe we should, also, just make more-extensive use of unit
tests?<br>
</p>
<p>Thanks again,</p>
<p>Hal<br>
</p>
<p><br>
</p>
<p><br>
</p>
<blockquote type="cite"><br>
<fieldset></fieldset>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div></div></div></div>