<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="">
<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="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>
</div>
</div>
<div>
<blockquote type="cite" class="">
<div class="">On Sep 13, 2017, at 5:43 PM, Hal Finkel <<a 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><br class="">
</div>
<div>… snip</div>
<div><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><br class="">
</div>
<div>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><br class="">
</div>
<div> 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><br class="">
</div>
<div> 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>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>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><br class="">
</div>
<div> 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><br class="">
</div>
<div>DFT (1) </div>
<div>%iv = phi [%v1], [%iv.inc] (ret true)</div>
<div>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>%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="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class=""></div>
</div>
</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>
<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>
<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>---</div>
<div>Daniel Neilson, Ph.D.</div>
<div>Azul Systems</div>
</div>
<div class=""><br class="">
</div>
</body>
</html>