<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 09/13/2017 01:01 PM, Daniel Neilson
via llvm-dev wrote:<br>
</div>
<blockquote cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div class=""><br class="">
</div>
Hi all,
<div class=""> I’ve most recently been grappling with a difficult
to reproduce bug. I’ve traced the source of the difficulty in
reproduction to the IVUsers analysis pass that is used by Loop
Strength Reduction. Specifically, the IVUsers pass’s output is
very sensitive to both the use list ordering of the instructions
that it is looking at and the ordering of the Phi nodes in the
header block of the loop that it’s analyzing. I would like to
resolve this fragility, but I’m not sure what correct/expected
output should look like for IVUsers. Some sort of guiding light
documentation or source comments that explain what the analysis
is supposed to be doing seem to be missing.</div>
<div class=""><br class="">
</div>
<div class=""> For example, the following IR will produce
different sets of IV users if either:</div>
<div class="">i) The order of the PHI nodes in the %loop block are
reordered; or</div>
<div class="">ii) The uselistorder directive is uncommented</div>
<div class=""><br class="">
</div>
<div class="">---</div>
<div class="">target datalayout =
"e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"<br class="">
target triple = "x86_64-unknown-linux-gnu"<br class="">
<br class="">
define void @test(i64 %v1, i32 %v2, i64* %addr) {<br class="">
entry:<br class="">
br label %loop<br class="">
<br class="">
loop:<br class="">
%iv = phi i64 [%v1, %entry], [%iv.inc, %loop]<br class="">
%iv2 = phi i32 [%v2, %entry], [%5, %loop]<br class="">
%0 = trunc i64 %iv to i32<br class="">
%1 = sub i32 %iv2, %0<br class="">
%2 = sitofp i32 %1 to double<br class="">
%3 = sub i64 0, %iv<br class="">
%4 = trunc i64 %3 to i32<br class="">
%5 = sub i32 %1, %4<br class="">
%iv.inc = add i64 %iv, 1<br class="">
store i64 %iv.inc, i64* %addr, align 8<br class="">
br i1 undef, label %loop, label %exit<br class="">
<br class="">
exit:<br class="">
ret void<br class="">
<br class="">
; uselistorder directives ----<br class="">
; uselistorder i64 %iv, {2, 1, 0}<br class="">
}<br class="">
—</div>
<div class=""><br class="">
</div>
<div class=""> IVUsers output (opt -analyze -iv-users -S <
file.ll):</div>
<div class="">1) IR as-is:</div>
<div class=""> %0 = {(trunc i64 %v1 to i32),+,1}<%loop> in
%1 = sub i32 %iv2, %0<br class="">
%1 = {((-1 * (trunc i64 %v1 to i32)) + %v2),+,(-1 + (-1 *
(trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop> in %2 = sitofp i32 %1 to double<br
class="">
%1 = {((-1 * (trunc i64 %v1 to i32)) + %v2),+,(-1 + (-1 *
(trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop> in %5 = sub i32 %1, %4<br class="">
%iv.inc = {(1 + %v1),+,1}<%loop> in store i64
%iv.inc, i64* %addr, align 8<br class="">
<br class="">
</div>
<div class="">2) Original phi ordering with uselistorder
uncommented</div>
<div class=""> %1 = {((-1 * (trunc i64 %v1 to i32)) + %v2),+,(-1
+ (-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop> in %2 = sitofp i32 %1 to double<br
class="">
%4 = {(trunc i64 (-1 * %v1) to i32),+,-1}<%loop> in
%5 = sub i32 %1, %4<br class="">
%iv.inc = {(1 + %v1),+,1}<%loop> in store i64
%iv.inc, i64* %addr, align 8<br class="">
%iv2 = {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 *
(trunc i64 %v1 to i32)))}<%loop> in %1 = sub i32 %iv2,
%0</div>
<div class=""><br class="">
</div>
<div class="">3) Re-order Phi nodes:</div>
<div class=""> %0 = {(trunc i64 %v1 to i32),+,1}<%loop> in
%1 = sub i32 %iv2, %0<br class="">
%1 = {((-1 * (trunc i64 %v1 to i32)) + %v2),+,(-1 + (-1 *
(trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop> in %2 = sitofp i32 %1 to double<br
class="">
%4 = {(trunc i64 (-1 * %v1) to i32),+,-1}<%loop> in
%5 = sub i32 %1, %4<br class="">
%iv.inc = {(1 + %v1),+,1}<%loop> in store i64
%iv.inc, i64* %addr, align 8</div>
<div class=""><br class="">
</div>
<div class=""> As you can see, there’s clearly commonalities in
these results but there are also SCEVs that will, or will not,
appear in the IVUsers results depending on just simple
differences in phi-instruction or use list ordering.</div>
<div class=""><br class="">
</div>
<div class=""> Basically, IVUsers starts a series of DFTs at each
of the phi nodes in the loop header. Each DFT traverses through
the def-use chains of defs with “interesting” SCEVs. At each
step of the DFT it is deciding whether to add users of the
current instruction’s SCEV to the IVUsers set based on
properties of the user itself. The reason for the differences
that I am seeing in these IVUsers results is that if a
particular user is seen more than once during this series of
DFTs then the subsequent times can result in a different
decision for the def’s SCEV.</div>
<div class=""><br class="">
</div>
<div class=""> To clarify what I mean, I’ll go back to the
example… </div>
<div class=""><br class="">
</div>
<div class=""> In version (1), we find ourselves looking at the
users of the SCEV for %1 = sub i32 %iv2, %0. We decide to add
both users (%2 = sitofp i32 %1 to double & %5 = sub i32 %1,
%4) as IVUsers of the SCEV for %1. Specifically, we add the def
of %5 as a user of %1’s SCEV because we have seen the def of %5
as a user earlier in the traversal.</div>
<div class=""><br class="">
</div>
<div class=""> In version (2), we similarly find ourselves looking
at the users of the SCEV for %1 = sub i32 %iv2, %0. However,
this time we only add "%2 = sitofp i32 %1 to double" as a user
of the SCEV for %1. Unlike in (1), we do not add the def of %5
as a user of %1’s SCEV because this is the first time (in any
DFT) that we have seen the def of %5 and the def of %5 is
considered to be an “interesting” SCEV.</div>
<div class=""><br class="">
</div>
<div class=""> So, to get back to the original questions:</div>
<div class="">1) What exactly is IVUsers supposed to be finding?
For instance, in the example above, what would be the
ideal/correct set of IVUsers that the analysis should be
finding?</div>
</blockquote>
<br>
I don't have a good answer to this question, other than the obvious
one (that it's supposed to find all values that have interesting
SCEV expressions making use of the induction variable). Interesting
here means that it's an affine addrec or has a starting value that
is one (recursively). It also helps support post-inc
transformations.<br>
<br>
The problem here is that we're trying to avoid calling getSCEV on
all instructions just to see if they end up being an addrec of the
given loop. Maybe we should do this in two steps? First, walk the
users to find the instruction on which to call getSCEV. Then, go
through the instructions in BB order, calling getSCEV on those
identified instructions.<br>
<br>
<blockquote cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">2) Is it acceptable that there is this sort of
difference in the IVUsers analysis results based on nothing more
than instruction or use list ordering? I personally hope not; it
has been mildly infuriating having to narrow down on a bug with
this difference in place.</div>
</blockquote>
<br>
Technically speaking, the dependency on the order of the phis is
okay (i.e., it's possible they'll be no good way to avoid that). Not
having it is clearly better. The dependency on the use-list ordering
is highly discouraged. As you've noticed, this makes problems very
hard to track down.<br>
<br>
Part of the problem here may be that, because what SCEV proves, and
thus returns, is dependent on what SCEV's have been previously
constructed (unfortunately), it's not hard to develop these kinds of
processing-order dependencies with analyses that use SCEV.<br>
<br>
-Hal<br>
<br>
<blockquote cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">Thanks,</div>
<div class=""> Daniel</div>
<div class=""><br class="">
<div class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space;
-webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px;">
---</div>
<div style="color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px;">
Daniel Neilson, Ph.D.</div>
<div style="color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px;">
Azul Systems</div>
<div style="color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px;" class="">
<br class="">
</div>
<br class="Apple-interchange-newline">
</div>
<br class="Apple-interchange-newline">
</div>
<br class="">
</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>