<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Sep 1, 2015 at 11:47 AM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On Tue, Sep 1, 2015 at 11:03 AM, Rong Xu <span dir="ltr"><<a href="mailto:xur@google.com" target="_blank">xur@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Justin, Sean and other people interested in this proposal,<div><br></div><div>I'm wondering if you have chances to read the new experiment results in my last email sent 2 weeks ago.  Can you share you thoughts, or you have other tests that you want to to run? </div></div></blockquote><div><br></div></span><div>See my email from Aug 11 (3 weeks ago). Adding an IR-level instrumentation pass makes sense (you didn't need to provide any performance data to support this; there are plenty of good reasons), but there are a couple independent parts. Have you been able to work on splitting out any of them?</div></div></div></div></blockquote><div><br></div><div>I re-read your comments from Aug 11. </div><div>>As far as I see it, Rong's proposal has a couple different parts:<br></div><div><div>></div><div>>1. Infrastructure for IR-level instrumentation-based PGO</div><div>>2. Changes to the pass pipeline so that a hypothetical IR-level instrumentation-based PGO is more effective</div><div>>3. MST algorithm with profile feedback for optimal placement of counter updates.</div></div><div><br></div><div>In my implementation, MST algorithm is the main component of 1.  The only IR change is to insert instrprof_increment intrinsic calls (which will be lower in createInstrProfilingPass).  </div><div>I'm not quite sure about 3. Do you mean MST algorithm, or using one profile to guide the MST algorithm to get the optimal placement? I do have the code for both. But the latter one was just for experimental purpose. It gonna be hard to use in the real applications (for example, the profile-use would also need the bootstrap profile to read the real profile).</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class=""><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>I'm in the final stage of preparing the patch. If you are OK, I can sent out the patch soon.</div></div></blockquote><div><br></div></span><div>I'm not sure what you mean by "the" patch. It seems pretty clear that there are multiple sub-parts to this. Could you send an RFC for part 1 that I described? We especially need to discuss the interface for frontends e.g. clang command line interface, when a user passes a profile file how do we thread that information back to the middle-end, details for the runtime interoperation (things like function hash will have different meaning between IR-level and Clang instrumentation), etc.</div></div></div></div></blockquote><div><br></div><div>I agree with your approach. When I said "the patch", I really meant 'a series of patches'.</div><div><br></div><div>Thanks for the suggestion.</div><div><br></div><div>-Rong</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class=""><font color="#888888"><div><br></div><div>-- Sean Silva</div></font></span><div><div class="h5"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>Thanks,</div><div><br></div><div>-Rong</div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Aug 19, 2015 at 5:18 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000">
    Thank you for sharing the data.  I haven't been following the
    discussion, but this data made for very interesting reading on it's
    own.  <br>
    <br>
    Philip<div><div><br>
    <br>
    <div>On 08/19/2015 03:39 PM, Rong Xu via
      llvm-dev wrote:<br>
    </div>
    </div></div><blockquote type="cite"><div><div>
      <div dir="ltr">
        <div>We collected more data to address some of the questions
          from the reviewers. Note this time we use clang itself as the
          benchmark. We choose clang because we think it's a typical C++
          program and the reviewers here have good knowledge of the code
          base.</div>
        <div><br>
        </div>
        <div>What we measure is running time for clang to compile a
          large preprocessed source file (4.98M lines of .ii file),
          using different compilation modes. All the numbers reported
          here are the average running time of 5 runs in seconds.</div>
        <div><br>
        </div>
        <div><b>(1) Performance b/w late instrumentation v.s. not
            instrumenting single BB functions</b></div>
        <div><br>
        </div>
        <div>We first compare various instrumentation performance.</div>
        <div><font face="monospace, monospace">----------------------------------------------------------------------------</font></div>
        <div><font face="monospace, monospace">  Config                
              wall_time_for_instr   ratio_vs_base   profile_size</font></div>
        <div><font face="monospace, monospace">(1) base O2              
                  80.386             100.0%           --</font></div>
        <div><font face="monospace, monospace">(2) FE-based Instr      
                  201.658             250.8%         65238880</font></div>
        <div><font face="monospace, monospace">(3) late Instr          
                  103.662             129.0%         14860144</font></div>
        <div><font face="monospace, monospace">(4) (3) + w/o pre-inline
                  199.924             248.7%         70762720</font></div>
        <div><font face="monospace, monospace">(5) (4) + Silva          
                 119.904             149.2%         24499528</font></div>
        <div><br>
        </div>
        <div>Config(5) used the simple heuristic that Sean Silva
          proposed: not instrumenting single BB functions that contain
          less than 10 instructions (excluding debug and phi stmts).</div>
        <div><br>
        </div>
        <div>We can see:</div>
        <div>1) Simple heuristic of not instrumenting small single BB
          functions improves instrumentation performance as expected.</div>
        <div>2) Using simple heuristic is still slower than late
          instrumentation with pre-inlining: the later is 15% faster.</div>
        <div>3) Late instrumentation produces the smallest profile size:
          it's 39% smaller than using the simple heuristic.</div>
        <div><br>
        </div>
        <div>The result is expected as pre-inlining can handle more
          cases than the simple heuristic. There is significant
          performance gap between the simple heuristic (5) and late
          instrumentation (2).</div>
        <div><br>
        </div>
        <div>We also used a few larger internal benchmarks to further
          validate the above result. The following table shows the
          slowdown compared to the base O2. The labels (2) to (5) refer
          to the same config as in the previous table.</div>
        <div><font face="monospace, monospace">------------------------------------------------------</font></div>
        <div><font face="monospace, monospace">Program              
             (2)      (3)      (4)      (5)</font></div>
        <div><font face="monospace, monospace">C++benchmark16    
             -45.24%  -12.93%  -43.84%  -24.74%</font></div>
        <div><font face="monospace, monospace">C++benchmark17    
             -90.86%  -58.19%  -87.77%  -80.62%</font></div>
        <div><font face="monospace, monospace">C++benchmark18    
             -95.32%  -54.75%  -91.21%  -82.56%</font></div>
        <div><br>
        </div>
        <div><br>
        </div>
        <div>We can see the same trend as the clang benchmark: the
          simple heuristic (5) recovers a lot of performance loss
          compared with FE base instrumentation, but is still
          significantly worse than late instrumentation (3).</div>
        <div><br>
        </div>
        <div><b>(2) Performance impact of context sensitivity</b></div>
        <div><br>
        </div>
        <div>LLVM does not use the profile information fully in the
          back-end optimizations, for instance, inlining does not fully
          use the profile counts -- it only marks hot/cold function
          attribute based on function entry counts. To evaluate the
          impact of profile context sensitivity, GCC is used in the
          experiment. Note that GCC PGO improves clang performance a lot
          more than clang PGO.</div>
        <div><br>
        </div>
        <div>First we summarize the methodology used in the experiment:</div>
        <div>0)  build clang with GCC O2 without early inlining and
          measure clang's performance. GCC early inlining (einline) is
          similar to pre-inline used by late instrumentation.<br>
        </div>
        <div>1) build clang with GCC O2 with early inlining and measure
          performance.</div>
        <div><br>
        </div>
        <div>The performance difference of 1) and 0) is denoted as E
          which measures the contribution of early inlining.</div>
        <div><br>
        </div>
        <div>2) build clang with GCC O2 + PGO without early inlining.</div>
        <div>3) build clang with GCC O2 + PGO with early inlining.</div>
        <div><br>
        </div>
        <div>The performance difference of 3) and 2) is denoted as EC.
          It constitutes roughly two parts a) early inlining
          contribution b) context sensitive profiling enabled with early
          inlining.</div>
        <div><br>
        </div>
        <div>The contribution of context sensitive profiling can be
          estimated by EC - E above.</div>
        <div><font face="monospace, monospace">-------------------------------------------------------------------------------</font></div>
        <div><font face="monospace, monospace">Config                  
                 wall_time_for_use  speedup_vs_(0)  speedup_vs_(1)</font></div>
        <div><font face="monospace, monospace">(0) base w/o einline    
                    84.946            1.000          0.934</font></div>
        <div><font face="monospace, monospace">(1) base O2              
                   79.310            1.071          1.000</font></div>
        <div><font face="monospace, monospace">(2) profile-arcs w/o
            einline     63.518            1.337          1.249</font></div>
        <div><font face="monospace, monospace">(3) profile-arcs        
                    48.364            1.756          1.640</font></div>
        <div><br>
        </div>
        <div>We see the following:</div>
        <div>1) GCC PGO with early inlining improves clang performance
          by 64.0% (v.s. base O2 w/ early inline).</div>
        <div>2) GCC PGO w/o early inlining improves clang performance by
          33.7% (v.s. base O2 w/o early inline).</div>
        <div>3) Early inlining performance contribution is about 7.1%.</div>
        <div>4) Profile context sensitivity contribution is estimated to
          be 22.2% (i.e. 64.0% -33.7% - 7.1%), which is pretty
          significant.</div>
        <div><br>
        </div>
        <div><b>(3) Pre-inline pass impact on the value profiling</b></div>
        <div><br>
        </div>
        <div>Again, we use GCC as the platform to estimate:</div>
        <div><br>
        </div>
        <div><font face="monospace, monospace">--------------------------------------------------------</font></div>
        <div><font face="monospace, monospace">  Config                
                       wall_time for_instr</font></div>
        <div><font face="monospace, monospace">(2) profile-arcs        
                         115.720</font></div>
        <div><font face="monospace, monospace">(3) profile-arcs w/o
            einline          310.560</font></div>
        <div><font face="monospace, monospace">(4) profile-generate    
                         139.952</font></div>
        <div><font face="monospace, monospace">(5) profile-generate w/o
            einline      680.910</font></div>
        <div><br>
        </div>
        <div>In GCC, -fprofile-generate does -fprofile-arcs as well as
          the value profiling. The above table shows that with value
          profile, the impact of pre-inlining is even larger for
          instrumented binary performance. Without value  profiling,
          disabling pre-inlining increases runtime by 1.7x, while with
          value profiling, its impact is 3.9x increase in runtime.</div>
        <div><br>
        </div>
      </div>
      <div class="gmail_extra"><br>
        <div class="gmail_quote">On Tue, Aug 11, 2015 at 10:11 PM, Sean
          Silva via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
          wrote:<br>
          <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
            <div dir="ltr"><br>
              <div class="gmail_extra"><br>
                <div class="gmail_quote"><span>On Tue, Aug 11,
                    2015 at 11:07 AM, Diego Novillo via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
                    wrote:<br>
                    <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
                      <div dir="ltr">
                        <div class="gmail_extra">One aspect of this that
                          I have not seen discussed is that middle-end
                          instrumentation enables PGO optimizations to
                          front-ends other than Clang.</div>
                        <div class="gmail_extra"><br>
                        </div>
                        <div class="gmail_extra">While I agree that FE
                          instrumentation could be improved, it still
                          requires every FE to implement essentially the
                          same common functionality.  Having PGO
                          instrumentation generated in the middle-end,
                          allows us every FE to automatically take
                          advantage of PGO.</div>
                      </div>
                    </blockquote>
                    <div><br>
                    </div>
                  </span>
                  <div>This is a really good point, and I agree with it.
                    We may have gotten off on the wrong foot since
                    Rong's email focused so heavily on comparing with
                    the frontend instrumentation. As far as I see it,
                    Rong's proposal has a couple different parts:</div>
                  <div><br>
                  </div>
                  <div>1. Infrastructure for IR-level
                    instrumentation-based PGO</div>
                  <div>2. Changes to the pass pipeline so that a
                    hypothetical IR-level instrumentation-based PGO is
                    more effective</div>
                  <div>3. MST algorithm with profile feedback for
                    optimal placement of counter updates.</div>
                  <div><br>
                  </div>
                  <div>I think 1. is a no-brainer, if only so that all
                    LLVM clients can benefit from PGO, and also (as you
                    pointed out below) so that it can have an exclusive
                    focus on performance. If it is sufficiently
                    flexible, it may even make sense to restrict clang's
                    frontend instrumentation-based profiling to
                    non-performance stuff, and have clang directly
                    interoperate with the IR-level PGO for
                    performance-related PGO use cases, just like any
                    other frontend would.</div>
                  <div><br>
                  </div>
                  <div>Philip and Sanjoy, out of curiosity do you guys
                    use your own instrumentation placement for PGO? Is
                    an IR-level PGO infrastructure upstream something
                    you guys would be interested in?</div>
                  <div><br>
                  </div>
                  <div>I think that 2. is something that once we have 1.
                    we will be able to evaluate better, but for now my
                    opinion is that we should be able to make good
                    progress without digging into that.</div>
                  <div><br>
                  </div>
                  <div>I think that 3. is a no-brainer if it provides a
                    really significant win, but without 1. we can't
                    really measure its effect in isolation. It also has
                    a usability problem since it requires feeding in an
                    existing profile for the *instrumented* build, but
                    if the benefit is very significant this may be worth
                    it for some users. We will probably be able to
                    easily refactor 1. as needed into an MST approach
                    that degrades gracefully to using static heuristics
                    in the absence of real profile information, so is
                    not a maintenance burden (maybe even helps by
                    providing a good framework in which to develop
                    effective static heuristics).</div>
                  <div><br>
                  </div>
                  <div>For the time being, I think we can avoid
                    discussion of 2. and 3. until we have more of 1.
                    working. So I think it would be most productive if
                    we focus this discussion on 1.</div>
                  <span>
                    <div><br>
                    </div>
                    <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
                      <div dir="ltr">
                        <div class="gmail_extra"><br>
                        </div>
                        <div class="gmail_extra">Additionally, some of
                          the overhead imposed by FE instrumentation is
                          not really all that easy to get rid of.  You
                          end up duplicating functionality that is more
                          naturally implemented in the middle end.</div>
                      </div>
                    </blockquote>
                    <div><br>
                    </div>
                  </span>
                  <div>Yeah, I was looking into a couple of other simple
                    approaches and quickly found out that I was
                    basically replicating much of the sort of logic that
                    the inliner already has.</div>
                  <div><br>
                  </div>
                  <div>-- Sean Silva</div>
                  <div> </div>
                  <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span>
                      <div dir="ltr">
                        <div class="gmail_extra"><br>
                        </div>
                        <div class="gmail_extra">I see the two
                          approaches as supplementary, rather than
                          complementary.  One does not negate the
                          other.  Some of the optimizations we'd do in
                          the FE, may hurt coverage.  Instead, by
                          instrumenting in the middle end, you can focus
                          exclusively on performance (coverage be
                          damned).</div>
                        <div class="gmail_extra"><br>
                        </div>
                        <div class="gmail_extra"><br>
                        </div>
                        <div class="gmail_extra">Diego.</div>
                      </div>
                      <br>
                    </span><span>_______________________________________________<br>
                      LLVM Developers mailing list<br>
                      <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>     
                         <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
                      <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
                      <br>
                    </span></blockquote>
                </div>
                <br>
              </div>
            </div>
            <br>
            _______________________________________________<br>
            LLVM Developers mailing list<br>
            <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> 
                   <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
            <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
            <br>
          </blockquote>
        </div>
        <br>
      </div>
      <br>
      <fieldset></fieldset>
      <br>
      </div></div><pre><div><div>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
</div></div><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
    </blockquote>
    <br>
  </div>

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