<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Sep 15, 2017, at 9:54 PM, Hal Finkel <<a 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:31 PM, Daniel Neilson wrote:<br class="">
</div>
<blockquote cite="mid:214627CD-16E5-40CC-AC17-738D1CEF0598@azul.com" type="cite" class="">
<br class="">
<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 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 class=""><br class="">
</div>
<div class="">Sure thing... </div>
<div class=""><br class="">
</div>
<div class="">First:</div>
<div class="">%0 = {(trunc i64 %v1 to i32),+,1}<%loop> in %1 = sub i32 %iv2, %0</div>
<div class=""><br class="">
</div>
<div class="">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 class="">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 class="">%iv -> %0 -> %1</div>
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">It’s the same sort of situation in the IR with the phi nodes in the loop-header rearranged.</div>
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">Second:</div>
<div 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="">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 class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">Again, strikes me as incorrect because the behaviour is inconsistent.</div>
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class="">
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 class="">
<br class="">
Can you turn your test case into a regression test and post your patch for review?<br class="">
<br class="">
-Hal<br class="">
<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Sorry for the delay; I was out of town with no access to a computer. We can continue the discussion under this review:</div>
<div><br class="">
</div>
<div><a href="https://reviews.llvm.org/D38097" class="">https://reviews.llvm.org/D38097</a></div>
<div><br class="">
</div>
<div>-Daniel</div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<blockquote cite="mid:214627CD-16E5-40CC-AC17-738D1CEF0598@azul.com" type="cite" class="">
<div class="">
<div class=""><br class="">
</div>
<div class="">Cheers,</div>
<div class=""> Daniel</div>
<div class=""><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 class="">---</div>
<div class="">Daniel Neilson, Ph.D.</div>
<div class="">Azul Systems</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>
<br class="">
</body>
</html>