<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/14/2017 10:31 PM, Daniel Neilson
wrote:<br>
</div>
<blockquote cite="mid:214627CD-16E5-40CC-AC17-738D1CEF0598@azul.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<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;">
<br class="">
</div>
</div>
</div>
<div>
<blockquote type="cite" class="">
<div class="">On Sep 14, 2017, at 9:30 PM, Hal Finkel <<a
moz-do-not-send="true" href="mailto:hfinkel@anl.gov"
class="">hfinkel@anl.gov</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<p class=""><br class="">
</p>
<div class="moz-cite-prefix">On 09/14/2017 10:43 AM,
Daniel Neilson wrote:<br class="">
</div>
<blockquote
cite="mid:4312CF89-E38D-45E6-9BE6-5AB153884A8F@azul.com"
type="cite" class="">
<div class="">Thank you for your thoughts, Hal. More
information below...</div>
<div class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode:
space; -webkit-line-break: after-white-space;"
class="">
<div style="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>
</div>
</div>
<div class="">
<blockquote type="cite" class="">
<div class="">On Sep 13, 2017, at 5:43 PM, Hal
Finkel <<a moz-do-not-send="true"
href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>>
wrote:</div>
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<div class="moz-cite-prefix">On 09/13/2017 01:01
PM, Daniel Neilson via llvm-dev wrote:<br
class="">
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">… snip</div>
<div class=""><br class="">
</div>
<blockquote type="cite" class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<blockquote
cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
type="cite" class="">
<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>
</blockquote>
</div>
</blockquote>
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class=""><br
class="">
</div>
</div>
<div bgcolor="#FFFFFF" text="#000000" class="">… snip</div>
<div bgcolor="#FFFFFF" text="#000000" class=""><br
class="">
</div>
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<blockquote
cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
type="cite" class="">
<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 class="">
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 class="">
<br class="">
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 class="">
<br class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">I’m not sure, either. What it looks
like, just from reading and interpreting the
implementation, is that it’s looking for the SCEVs
of instructions that terminate a def-use chain that
starts at a loop-header phi. There are are a few
criteria for what constitutes “terminating” a
def-use chain, but the most fundamental one (I
think) appears to be that a user of the SCEV isn’t
itself an “interesting” SCEV. </div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<blockquote
cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
type="cite" class="">
<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 class="">
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 class="">
<br class="">
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 class="">
<br class="">
-Hal<br class="">
<br class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class=""> Thankfully, it looks like the SCEVs
that are produced for each instruction in the DFT
that I’m looking at are consistent; there doesn’t
seem to be any affect on the SCEVs themselves as a
result of the traversal orders. </div>
<div class=""><br class="">
</div>
<div class=""> It looks to me that there are two
pieces of the implementation of IVUsers that are
leading to the fragility (i.e. dependence on input
ordering) that I am seeing.</div>
<div class="">A) The inclusion of
Processed.count(User) as a condition of the two if
statements at approx lines 235 & 241
in IVUsers::AddUsersImpl() of
lib/Analysis/IVUsers.cpp.</div>
<div class="">B) It doesn’t terminate a DFT if it
encounters a phi node in the loop-header that it
hasn’t seen before.</div>
<div class=""><br class="">
</div>
<div class=""> To help illustrate these, here are the
relevant DFT traces from the sample IR that I
provided in the original post. (1) is the IR as-is,
and (2) is with the uselistorder instruction active.</div>
<div class=""><br class="">
</div>
<div class="">DFT (1) </div>
<div class="">%iv = phi [%v1], [%iv.inc] (ret true)</div>
<div class="">SCEV: {%v1,+,1}<%loop><br class="">
* User: %iv.inc = add %iv, 1 (ret true)<br
class="">
SCEV: {(1 + %v1),+,1}<%loop><br
class="">
* User: store %iv.inc, %addr (ret false) ****
ADD as user of %iv.inc def ****<br class="">
* User: %iv = phi [%v1], [%iv.inc] (PHI
already processed)<br class="">
* User: %3 = sub 0, %iv (ret true)<br class="">
SCEV: {(-1 * %v1),+,-1}<%loop><br
class="">
* User: %4 = trunc %3 (ret true)<br class="">
SCEV: {(trunc i64 (-1 * %v1) to
i32),+,-1}<%loop><br class="">
* User: %5 = sub %1, %4 (ret true)<br
class="">
SCEV: {((-1 * (trunc i64 (-1 * %v1)
to i32)) + (-1 * (trunc i64 %v1 to i32)) +
%v2),+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 *
(trunc i64 %v1 to i32)))}<%loop><br class="">
* User: %iv2 = phi [%v2], [%5] (ret
true)<br class="">
SCEV: {%v2,+,((-1 * (trunc i64
(-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop><br class="">
* User: %1 = sub %iv2, %0 (ret true)<br
class="">
SCEV: {((-1 * (trunc i64 %v1
to i32)) + %v2),+,(-1 + (-1 * (trunc i64 (-1 * %v1)
to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop><br class="">
* User: %5 = sub %1, %4 (already
processed) **** ADD as user of %1 def ****<br
class="">
* User: %2 = sitofp %1 (ret false)
**** ADD as user of %1 def ****<br class="">
* User: %0 = trunc %iv (ret true)<br class="">
SCEV: {(trunc i64 %v1 to
i32),+,1}<%loop><br class="">
* User: %1 = sub %iv2, %0 (already processed)
**** ADD as user of %0 def ****<br class="">
<br class="">
IV Users for loop %loop:<br class="">
%iv.inc = {(1 + %v1),+,1}<%loop> in store
i64 %iv.inc, i64* %addr, align 8<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="">
%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="">
%0 = {(trunc i64 %v1 to i32),+,1}<%loop> in
%1 = sub i32 %iv2, %0<br class="">
<br class="">
DFT (2)</div>
<div class="">%iv = phi [%v1], [%iv.inc] (ret true)<br
class="">
SCEV: {%v1,+,1}<%loop><br class="">
* User: %0 = trunc %iv (ret true)<br class="">
SCEV: {(trunc i64 %v1 to
i32),+,1}<%loop><br class="">
* User: %1 = sub %iv2, %0 (ret true)<br
class="">
SCEV: {((-1 * (trunc i64 %v1 to i32))
+ %v2),+,(-1 + (-1 * (trunc i64 (-1 * %v1) to i32))
+ (-1 * (trunc i64 %v1 to i32)))}<%loop><br
class="">
* User: %5 = sub %1, %4 (ret true)<br
class="">
SCEV: {((-1 * (trunc i64 (-1 * %v1)
to i32)) + (-1 * (trunc i64 %v1 to i32)) +
%v2),+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 *
(trunc i64 %v1 to i32)))}<%loop><br class="">
* User: %iv2 = phi [%v2], [%5] (ret
true)<br class="">
SCEV: {%v2,+,((-1 * (trunc i64
(-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to
i32)))}<%loop><br class="">
* User: %1 = sub %iv2, %0 (already
processed) **** ADD as user of %iv2 def ****<br
class="">
* User: %2 = sitofp %1 (ret false) **** ADD
as user of %1 def ****<br class="">
* User: %3 = sub 0, %iv (ret true)<br class="">
SCEV: {(-1 * %v1),+,-1}<%loop><br
class="">
* User: %4 = trunc %3 (ret true)<br class="">
SCEV: {(trunc i64 (-1 * %v1) to
i32),+,-1}<%loop><br class="">
* User: %5 = sub %1, %4 (already processed)
**** ADD as user of %4 def ****<br class="">
* User: %iv.inc = add %iv, 1 (ret true)<br
class="">
SCEV: {(1 + %v1),+,1}<%loop><br
class="">
* User: store %iv.inc, %addr (ret false) ****
ADD as user of %iv.inc ****<br class="">
* User: %iv = phi [%v1], [%iv.inc] (PHI
already processed)<br class="">
<br class="">
IV Users for loop %loop:<br class="">
%iv2 = {%v2,+,((-1 * (trunc i64 (-1 * %v1) to
i32)) + (-1 * (trunc i64 %v1 to i32)))}<%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>
<blockquote type="cite" class="">
</blockquote>
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""> For point (A), first take a close look at
what the DFT does when it encounters the def of %1 as
a User in DFT (1). The first time that %1’s def is
encountered is as a user of %iv2. We continue
traversing through the def of %1 at this point to
process the users of it because we haven’t encountered
the def of %1 yet (i.e. Processed.count(%1) is 0).
However, we encounter the def of %1 again in this same
DFT later as a user of the def of %0. This second time
that we encounter %1 we don’t traverse its users
because we’ve seen %1 before (i.e. Processed.count(%1)
is 1), and so we add the SCEV of %0 to the IVUsers
set. In DFT (2) we encounter the def of %1 first as a
user of %0 — which allows the DFT to process the users
of %1 instead of adding the SCEV of %0 to the IVUsers
set.</div>
<div class=""><br class="">
</div>
<div class=""> For point (B), take a look at the
traversal order in DFT (1). You’ll see the chain %iv
-> %3 -> %4 -> %5 -> %iv2 -> %1 ->
%5. The def of %5 appears twice in the same def-use
chain, and the second time we see it will be the same
situation as in point (A). The reason that we revisit
%5 in the same def-use chain is that we allow the DFT
to continue through %iv2 (%iv2 is a phi node in the
loop-header) that will, in effect, allow the DFT to
loop-around and revisit. The result is adding the def
of %5 as a user of %1’s SCEV in DFT (1). We don’t do
the same in DFT (2) because we don’t visit the def of
%5 in the same way. Instead, in DFT (2) the def of %1
ends up being the value that appears twice in a
def-use chain.</div>
<div class=""><br class="">
</div>
<div class=""> What I *think* would be proper for
IVUsers is to have IVUsers::AddUserImpl() :</div>
<div class=""><br class="">
</div>
<div class="">A) Memoize its result for each given
instruction instead of having the
Processed.count(User) condition at lines 235 &
241. The presence of Processed.count(User) in the
conditions at lines 235 & 241 basically has the
effect of changing the return value of AddUsersImpl()
for “interesting” instructions from true to false,
which results in different behaviour depending on the
order in which instructions are visited.
Interestingly, if we don’t memoize the result of
AddUsersImpl() at all, but instead just remove the
Processed.count(User) parts of these two if
statements, then the return value of AddUsersImpl()
will *always* be true and we would have consistent
results for recursive calls on “interesting” SCEVS,
but inconsistent results for recursive calls on
instructions that aren’t interesting.</div>
<div class=""><br class="">
</div>
<div class="">B) Similar to the condition at line 212,
don’t let the DFT continue into Users that are phi
nodes in the loop-header. We’re going to visit every
phi node in the loop-header as the root of a DFT, in
turn, anyways, so this just prevents the possibility
of revisiting the same instruction multiple times in
the same def-use chain.</div>
</blockquote>
<br class="">
These seems sensible.<br class="">
<br class="">
<blockquote
cite="mid:4312CF89-E38D-45E6-9BE6-5AB153884A8F@azul.com"
type="cite" class="">
<div class=""><br class="">
</div>
<div class=""> If I mock these two changes up, the
IVUsers sets in all three of my original situations
(IR as-is, IR with header-phi’s rearranged, and IR
with use-list ordering) all produce the exact same set
of IVUsers. However, the set of IVUsers ends up being
a subset of what we previously had. I don’t know if
this is correct because the IVUsers analysis doesn’t
appear to be well-defined with respect to what it
should be generating. Specifically, with this test we
end up with slight variations of this DFT:</div>
<div class=""><br class="">
</div>
<div class="">%iv = phi i64 [ %v1, %entry ], [ %iv.inc,
%loop ]<br class="">
SCEV: {%v1,+,1}<%loop><br class="">
* User: %iv.inc = add i64 %iv, 1 (ret true)<br
class="">
SCEV: {(1 + %v1),+,1}<%loop><br
class="">
* User: store i64 %iv.inc, i64* %addr, align 8.
(ret false) **** ADD as user of %iv.inc def ****<br
class="">
* User: %iv = phi i64 [ %v1, %entry ], [
%iv.inc, %loop ] (already processed PHI, skip)<br
class="">
* User: %3 = sub i64 0, %iv (ret true)<br class="">
SCEV: {(-1 * %v1),+,-1}<%loop><br
class="">
* User: %4 = trunc i64 %3 to i32 (ret true)<br
class="">
SCEV: {(trunc i64 (-1 * %v1) to
i32),+,-1}<%loop><br class="">
* User: %5 = sub i32 %1, %4 (ret true)<br
class="">
SCEV: {((-1 * (trunc i64 (-1 * %v1)
to i32)) + (-1 * (trunc i64 %v1 to i32)) + %v2),+,((-1
* (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64
%v1 to i32)))}<%loop><br class="">
* User: %iv2 = phi i32 [ %v2, %entry ], [
%5, %loop ] (PHI in loop header, skip)<br class="">
* User: %0 = trunc i64 %iv to i32 (ret true)<br
class="">
SCEV: {(trunc i64 %v1 to
i32),+,1}<%loop><br class="">
* User: %1 = sub i32 %iv2, %0<br class="">
SCEV: {((-1 * (trunc i64 %v1 to i32)) +
%v2),+,(-1 + (-1 * (trunc i64 (-1 * %v1) to i32)) +
(-1 * (trunc i64 %v1 to i32)))}<%loop><br
class="">
* User: %5 = sub i32 %1, %4 (memoized - ret
true)<br class="">
* User: %2 = sitofp i32 %1 to double (ret
false) **** ADD as user of %1 def ****<br class="">
%iv2 = phi i32 [ %v2, %entry ], [ %5, %loop ]<br
class="">
SCEV: {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) +
(-1 * (trunc i64 %v1 to i32)))}<%loop><br
class="">
* User: %1 = sub i32 %iv2, %0 (memoized - ret true)<br
class="">
<br class="">
IVUsers:<br class="">
%iv.inc = {(1 + %v1),+,1}<%loop> in store
i64 %iv.inc, i64* %addr, align 8<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="">
<br class="">
</div>
<div class=""><br class="">
</div>
<div class=""> This looks sensible to me, but, again, I
don’t really have a good sense of what the “proper”
IVUsers results are expected to be.</div>
</blockquote>
<br class="">
Compared to the previous results, this is missing:<br
class="">
<br class="">
%0 = {(trunc i64 %v1 to i32),+,1}<%loop> in %1
= sub i32 %iv2, %0<br class="">
%4 = {(trunc i64 (-1 * %v1) to i32),+,-1}<%loop>
in %5 = sub i32 %1, %4<br class="">
%iv2 = {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) +
(-1 * (trunc i64 %v1 to i32)))}<%loop> in %1 =
sub i32 %iv2, %0<br class="">
<br class="">
Can you comment on why?<br class="">
<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Sure thing... </div>
<div><br class="">
</div>
<div>First:</div>
<div>%0 = {(trunc i64 %v1 to i32),+,1}<%loop> in %1 =
sub i32 %iv2, %0</div>
<div><br class="">
</div>
<div>This result was only present in the IVUsers when the
original IR was run, and when the phi nodes in the loop-header
are rearranged. It does not appears in the IVUsers when
altering the use-list order of the %iv phi.</div>
<div>It’s there due to both points (A) & (B). With the
original IR (i.e. DFT (1), above) we add this user when
looking at the chain:</div>
<div>%iv -> %0 -> %1</div>
<div><br class="">
</div>
<div>But, we look at this chain *after* we have looked at the
chains: %iv -> %iv.inc -> %3 -> %4 -> %5 ->
%iv2 -> %1 -> [%5, %2]</div>
<div><br class="">
</div>
<div>Because we are looking at %iv -> %0 -> %1 *after* we
have looked at a different chain that contains %1, we will
have Processed.count(%1) being 1. Thus, the condition on line
241 will read this as chain termination, and add the SCEV of
%0 to IVUsers as used by %1. However, this is a different
behaviour than we would get had we been looking at the chain
fragment %iv -> %0 -> %1 *without* having previously
visited %1 in a different part of the DFT; had we not
previously seen %1, then Processed.count(%1) would be 0 and we
would recurse into AddUsersImpl(%1) which would, ultimately,
return true and result in %1 not being added as a user of the
SCEV of %0.</div>
<div><br class="">
</div>
<div>It’s the same sort of situation in the IR with the phi
nodes in the loop-header rearranged.</div>
<div><br class="">
</div>
<div>This sort of thing strikes me as incorrect. It’s a
situation where the DFT’s behaviour changes just because we’re
revisiting a node instead of seeing it fresh. In the mocked-up
“fixed” code, every time that we see %1 in a def-use chain we,
effectively, treat it the same way — by recursing into it, and
returning ‘true’.</div>
<div><br class="">
</div>
<div>Second:</div>
<div>%iv2 = {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 *
(trunc i64 %v1 to i32)))}<%loop> in %1 = sub i32
%iv2, %0</div>
<div><br class="">
</div>
<div>This one only appears in the IVUsers list when the use-list
order of the %iv phi is rearranged. (i.e. DFT (2))</div>
<div><br class="">
</div>
<div>Specifically, it’s added when looking at this def-use
chain: %iv -> %0 -> %1 -> %5 -> %iv2 -> %1 —
notice that %1 appears as a user twice (once for each def it
uses) in this one def-use chain.</div>
<div><br class="">
</div>
<div>This one is only added because Processed.count(%1) is 1
when looking at the users of %iv2 in this chain. So, we’re in
the same situation where we do one thing the first time we see
%1 as a user and do something completely different the second
time. The condition on line 241 ends up being false the first
time we visit %1, and true the second time, which results in
the fragility/traversal-order-dependency that I’m seeing in
IVUsers.</div>
<div><br class="">
</div>
<div>Again, strikes me as incorrect because the behaviour is
inconsistent.</div>
<div><br class="">
</div>
<div>Actually, this sort of def-use chain traversal is why I
think that it’s important to stop the DFT if encountering a
use that’s a phi in the loop-header if we’re going to be
memoizing the result of AddUsersImpl(). If we don’t stop the
traversal in a header-phi, then we’d have a situation where we
haven’t memoized the result of AddUsersImpl(%1) yet when
calling AddUsersImpl(%1) for the second time — because we’re
still trying to determine what AddUsersImpl(%1) will return in
the first call. Depending on how the memoization is
implemented, the result is either an infinite loop, or a
potentially inconsistent result.</div>
<div><br class="">
</div>
<div>I can’t really comment on whether there’s value in having
the SCEVs of %iv2 and %0 in the IVUsers list for this example.
I genuinely don’t know whether there is or is not. </div>
<div><br class="">
</div>
<div>As a point that indicates to me, at least, that the fixes
that I tried are at least on the right track: The IVUsers
found with the mocked-up fix in place are exactly the
intersection of the three different IVUsers sets that I found
with this one IR example.</div>
</div>
</blockquote>
<br>
IVUsers is only used by LSR, right? Does making these changes cause
any regression tests to fail? Any performance changes in the test
suite?<br>
<br>
Can you turn your test case into a regression test and post your
patch for review?<br>
<br>
-Hal<br>
<br>
<blockquote cite="mid:214627CD-16E5-40CC-AC17-738D1CEF0598@azul.com"
type="cite">
<div>
<div><br class="">
</div>
<div>Cheers,</div>
<div> Daniel</div>
<div><br class="">
</div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">Thanks again,<br
class="">
Hal<br class="">
<br class="">
<blockquote
cite="mid:4312CF89-E38D-45E6-9BE6-5AB153884A8F@azul.com"
type="cite" class="">
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""> Thoughts anyone?</div>
<div class=""><br class="">
</div>
<div class="">Thanks,</div>
<div class=""> Daniel</div>
<br class="">
<div class="">
<div class="">---</div>
<div class="">Daniel Neilson, Ph.D.</div>
<div class="">Azul Systems</div>
</div>
<div class=""><br class="">
</div>
</blockquote>
<br class="">
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div>
</div>
</blockquote>
</div>
<div>---</div>
<div>Daniel Neilson, Ph.D.</div>
<div>Azul Systems</div>
<div class=""><br class="">
</div>
</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>