[llvm-dev] IVUsers pass is fragile. Is this okay? How can it be resolved?

[Daniel Neilson via llvm-dev]

Hi all,
 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.

 For example, the following IR will produce different sets of IV users if either:
i) The order of the PHI nodes in the %loop block are reordered; or
ii) The uselistorder directive is uncommented

---
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
target triple = "x86_64-unknown-linux-gnu"

define void @test(i64 %v1, i32 %v2, i64* %addr) {
entry:
 br label %loop

loop:
 %iv = phi i64 [%v1, %entry], [%iv.inc, %loop]
 %iv2 = phi i32 [%v2, %entry], [%5, %loop]
 %0 = trunc i64 %iv to i32
 %1 = sub i32 %iv2, %0
 %2 = sitofp i32 %1 to double
 %3 = sub i64 0, %iv
 %4 = trunc i64 %3 to i32
 %5 = sub i32 %1, %4
 %iv.inc = add i64 %iv, 1
 store i64 %iv.inc, i64* %addr, align 8
 br i1 undef, label %loop, label %exit

exit:
 ret void

; uselistorder directives ----
; uselistorder i64 %iv, {2, 1, 0}
}
—

 IVUsers output (opt -analyze -iv-users -S < file.ll):
1) IR as-is:
  %0 = {(trunc i64 %v1 to i32),+,1}<%loop> in    %1 = sub i32 %iv2, %0
  %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
  %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
  %iv.inc = {(1 + %v1),+,1}<%loop> in    store i64 %iv.inc, i64* %addr, align 8

2) Original phi ordering with uselistorder uncommented
  %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
  %4 = {(trunc i64 (-1 * %v1) to i32),+,-1}<%loop> in    %5 = sub i32 %1, %4
  %iv.inc = {(1 + %v1),+,1}<%loop> in    store i64 %iv.inc, i64* %addr, align 8
  %iv2 = {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to i32)))}<%loop> in    %1 = sub i32 %iv2, %0

3) Re-order Phi nodes:
  %0 = {(trunc i64 %v1 to i32),+,1}<%loop> in    %1 = sub i32 %iv2, %0
  %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
  %4 = {(trunc i64 (-1 * %v1) to i32),+,-1}<%loop> in    %5 = sub i32 %1, %4
  %iv.inc = {(1 + %v1),+,1}<%loop> in    store i64 %iv.inc, i64* %addr, align 8

 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.

 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.

 To clarify what I mean, I’ll go back to the example…

 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.

 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.

 So, to get back to the original questions:
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?

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.

Thanks,
 Daniel

---
Daniel Neilson, Ph.D.
Azul Systems




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170913/2c03181f/attachment.html>