<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/13/2017 01:01 PM, Daniel Neilson
      via llvm-dev wrote:<br>
    </div>
    <blockquote cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
      type="cite">
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
      <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>
    </blockquote>
    <br>
    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>
    <br>
    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>
    <br>
    <blockquote cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
      type="cite">
      <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>
    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>
    <br>
    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>
    <br>
    Â -Hal<br>
    <br>
    <blockquote cite="mid:0E250E9D-303A-4C3C-93E0-0473B97DD17F@azul.com"
      type="cite">
      <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>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
    </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>