<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=""><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>
<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>
<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>
</body>
</html>