<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Sep 13, 2016 at 8:20 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000"><div><div class="h5">
    <p><br>
    </p>
    <br>
    <div>On 09/12/2016 08:51 AM, vivek pandya
      via llvm-dev wrote:<br>
    </div>
    <blockquote type="cite">
      <div dir="ltr">
        <div>Hello Developers,<br>
        </div>
        <div><br>
        </div>
        <div>I am working with my other batchmates to improve register
          remat in LLVM.</div>
        <div>We want to remat live ranges made of multiple instruction.</div>
        <div><br>
        </div>
        <div>Just to support our proposal here is a simple example that
          currently remat does</div>
        <div>not cover</div>
        <div><br>
        </div>
        <div>$ cat ~/tmp/tl.c</div>
        <div>void foo(long);</div>
        <div>void bar() {</div>
        <div>  for (int i = 0; i < 1600; ++i)</div>
        <div>    foo(3494348345984503943);</div>
        <div>}</div>
        <div><br>
        </div>
        <div>$ clang -O3 -S -o - ~/tmp/tl.c -target powerpc64</div>
        <div>...</div>
        <div># BB#0:                                 # %entry</div>
        <div>...</div>
        <div>        lis 3, 12414</div>
        <div>        ori 3, 3, 27470</div>
        <div>        sldi 3, 3, 32</div>
        <div>        oris 3, 3, 35809</div>
        <div>        ori 30, 3, 20615</div>
        <div>...</div>
        <div>.LBB0_1:                                # %for.body</div>
        <div>        mr 3, 30</div>
        <div>        bl foo</div>
        <div>...</div>
      </div>
    </blockquote></div></div>
    OT: Instead of viewing this as a *single* remat problem, can you
    view this as a series of remat problems?  If each instruction can be
    moved while only increasing the live range of a single register and
    shrinking the live range of another, then moving each instruction
    one by one and iterating gives the same effect.  Note that this only
    (obviously) works for single use defs.  Extending it to multiple
    uses would require a more complicated cost model as you point out.</div></blockquote><div><br></div><div>Hello Philip,</div><div><br></div><div>Your idea seems to be effective and can be tried out with few changes. But correct me if I got this wrong, by multiple uses do you mean a same remat sequence being remat again? In that case we can run the analysis again to decide which all instructions are required to be remat or we may add a simple caching layer which can hold analysis result for once compilation unit. </div><div>Any thoughts ?  </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"> 
    <br><span class="">
    <blockquote type="cite">
      <div dir="ltr">
        <div><br>
        </div>
        <div>There is a sequence of instructions used to materialize the
          constant, the first </div>
        <div>one (the lis) is trivially rematerialiable, and the others
          depend only on that one,</div>
        <div>and have no side effects. If we otherwise needed to spill
          the constant, we might</div>
        <div>wish to move the entire set of instructions that compute
          the value into the loop body.</div>
        <div>(Many thanks to Hal Finkel for this example and head start)</div>
        <div><br>
        </div>
        <div>We are following very old but effective paper
          "Rematerialization"</div>
        <div><a href="http://dl.acm.org/citation.cfm?id=143143" target="_blank">http://dl.acm.org/citation.<wbr>cfm?id=143143</a>
          ------------------------------<wbr>[1]</div>
        <div><br>
        </div>
        <div>This extension will specially improve code quality for RICS
          backends like </div>
        <div>powerpc, MIPS, ARM, AArch64 etc.</div>
        <div><br>
        </div>
        <div>Here is a tentative apporach ( after reading the above
          mentioned paper and current remat code) that I would like to
          follow.</div>
        <div><br>
        </div>
        <div>Please share your views because this may be totally wrong
          direction. Also I will</div>
        <div>be happy if this gets into main line LLVM code but if
          community don't want</div>
        <div>to make remat heavy than please guide me for my class
          project perspective.</div>
        <div><br>
        </div>
        <div>1 ) As LLVM MI is already in SSA form before reg allocation
          so for LLVM I think it does not require to build SSA graph and
          converting it back after optimization completed as mentioned
          in [1]</div>
        <div><br>
        </div>
        <div>2 ) We would like to add a pass similar to SCCP.cpp (Sparse
          Conditional Constant</div>
        <div>Propagation based on Wegman and Zadeck's work <a href="http://dl.acm.org/citation.cfm?id=103136" target="_blank">http://dl.acm.org/citation.<wbr>cfm?id=103136</a>)
          as desribed in [1]. This pass will be scheduled to run before
          register allocation.</div>
        <div><br>
        </div>
        <div>3 ) Output of the pass added in Step 2 will be a Map of def
          to instructions pointers (instructions which can be used to
          remat the given live range). The map will contain live ranges
          which is due to single instruction and multiple instructions.</div>
      </div>
    </blockquote></span>
    This sounds overly complex.  Can you implement this without needing
    the new side structure?  Maintaining extra state and keeping it up
    to date is expensive.  (From a maintenance and code complexity
    perspective.)<span class=""><br>
    <blockquote type="cite">
      <div dir="ltr">
        <div><br></div></div></blockquote></span></div></blockquote><div>Currently I don't think we have any facility to annotate instructions so to keep analysis available till register allocation we need an immutable pass.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><span class=""><blockquote type="cite"><div dir="ltr"><div>
        </div>
        <div>4 ) The remat APIs defined in LiveRangeEdit.cpp will use
          analysis from the Map</div>
        <div>when a spill is required for RA.</div>
        <div><br>
        </div>
        <div>5 ) The remat transformation APIs like rematerializeAt()
          will be teached to remat</div>
        <div>live ranges with multiple instructions too.</div>
        <div><br>
        </div>
        <div>6 ) A cost analysis will be require to decide between remat
          and spill. This should be based on at least two factors
          register pressure and spill cost</div>
        <div><br>
        </div>
        <div>Few points:</div>
        <div>--------------</div>
        <div>* The analysis pass to be addes as per (2) will use target
          specific information</div>
        <div>from TargetInstrInfo.cpp as the current remat
          infrastructure uses.</div>
        <div><br>
        </div>
        <div>* This approach will not be on demand as the current
          approach is (i.e remat specific</div>
        <div>code will be executed only if there is a spill) so the pass
          in (2) can be an</div>
        <div>overhead so we may want it to enable only for higher level
          of optimization.</div>
      </div>
    </blockquote></span>
    This would be unfortunate.  Not fatal, just unfortunate.<br>
    <blockquote type="cite"><span class="">
      <div dir="ltr">
        <div><br></div></div></span></blockquote></div></blockquote><div>-Vivek </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><blockquote type="cite"><span class=""><div dir="ltr"><div>
        </div>
        <div>* Will it be possible to use existing SCCP.cpp code with
          few modification to lattice</div>
        <div>and related mathematical operation so that it can serve
          both purpose?</div>
        <div><br>
        </div>
        <div>* No changes in current register allocators or spill
          framework will be required</div>
        <div>because remat entry point will be LiveRangeEdit.</div>
        <div><br>
        </div>
        <div>Any other way with less overhead is always welcomed.</div>
        <div>Please help us developing a plan to implement this.</div>
        <div><br>
        </div>
        <div>Hoping for comments!</div>
        <div><br>
        </div>
        <div>Sincerely,</div>
        <div>Vivek</div>
        <div><br>
        </div>
      </div>
      <br>
      <fieldset></fieldset>
      <br>
      </span><span class=""><pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</pre>
    </span></blockquote>
    <br>
  </div>

</blockquote></div><br></div></div>