<div dir="ltr">Your proposal seem reasonable to me. Another approach is, instead of using total frequency, use max frequency to scale. This prevents the cases when partial branch probability is missing, which makes BFI mistakenly increase/decrease the frequency of some BB.<div><br></div><div>I'm curious what optimizations relies on global hotness of a basic block. Inliner is one of them and we already address the issue by extractProfTotalWeight. But if you want to use this after inliner, inliner actually need to scale/update metadata to make it correct.</div><div><br></div><div>Dehao<br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 7, 2016 at 1:18 AM, Jonas Wagner <span dir="ltr"><<a href="mailto:jonas.wagner@epfl.ch" target="_blank">jonas.wagner@epfl.ch</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div><div class="gmail_quote"><span class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="m_8896230008981777530gmail_msg">Jonas, I assume you are talking about Sample-Based PGO. Yes, the problem you mentioned exists -- and your proposed solution seems reasonable. +dehao for comments.</div></blockquote><div><br></div></span><div>Yes, the problem is present in sample-based PGO, and so far this is the only case I've tested.</div><div><br></div><div>The patch contains a little bit of code to also compute the total number of samples for instrumentation-based PGO, and so it should not break this case. But I don't expect improvements for instrumentation-based PGO, because is has accurate function entry counts.</div><div><br></div><div>Best,</div><div>Jonas</div><span class=""><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_extra m_8896230008981777530gmail_msg"><div class="gmail_quote m_8896230008981777530gmail_msg"></div></div><div class="gmail_extra m_8896230008981777530gmail_msg"><div class="gmail_quote m_8896230008981777530gmail_msg">On Fri, Dec 2, 2016 at 1:40 AM, Jonas Wagner via llvm-dev <span dir="ltr" class="m_8896230008981777530gmail_msg"><<a href="mailto:llvm-dev@lists.llvm.org" class="m_8896230008981777530gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br class="m_8896230008981777530gmail_msg"></div></div><div class="gmail_extra m_8896230008981777530gmail_msg"><div class="gmail_quote m_8896230008981777530gmail_msg"><blockquote class="gmail_quote m_8896230008981777530gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="m_8896230008981777530gmail_msg"><div dir="ltr" class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">Hello,<div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">I'm working on an application that would benefit from knowing the weight of a basic block, as in "fraction of the program's execution time spent in this block".</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">Currently, I'm computing this using the block's frequency from BlockFrequencyInfo, relative to the function's entry block frequency, and scaled by the function's entry count. This is also the computation that's done by <a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/BlockFrequencyInfoImpl.cpp#L540" class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg" target="_blank">getBlockProfileCount</a> in lib/Analysis/<wbr>BlockFrequencyInfoImpl.cpp.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">The problem is that this method can be extremely imprecise, because many functions have an entry count of zero. The entry count is computed from the number of profile samples in the entry block. Depending on the function's CFG, this count can be arbitrarily low even though the function is frequently called or hot.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">Here's an idea to address this. I'd like to collect a bit of feedback from the community before trying it out.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">1) Instead of relying on a function's <i class="m_8896230008981777530gmail_msg">entry count</i>, store the <i class="m_8896230008981777530gmail_msg">total number of samples</i> in a function. This number is readily available from the profile loader.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">2) Compute a block's weight as `function_samples * block_weight / sum_of_block_weights_in_<wbr>function`</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">Why do I like this?</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">- Total samples in a function gives a good impression of the importance of a function, better than the entry count.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">- This scheme "preserves mass" in that all samples of a function are taken into account. The samples in a BB are compared to samples in the entire function, rather than a few (arbitrarily) selected samples from the entry block.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">- The computation avoids imprecision from multiplying by small numbers.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">Disadvantages?</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">- BlockFrequencyInfo needs to keep track of the total frequency in a function.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">- BlockFrequencyInfo would probably scale the frequencies w.r.t. that total, rather then the maximum frequency. This loses a few bits of precision</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">Note that the entry count would not be lost in this scheme; one could easily compute it as `function_samples * entry_weight / sum_of_block_weights_in_<wbr>function`.</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">I believe using an entire function as unit of reference is a good compromise between precision and modularity. Precision is high because there's a sufficient number of samples available in a function. Modularity is preserved because the computation does not need to take other functions into account (in fact, BlockFrequencyInfo already processes one function at at time).</div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg"><br class="m_8896230008981777530gmail_msg"></div><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">What do people think about this?</div><span class="m_8896230008981777530m_8356086414900213547HOEnZb m_8896230008981777530gmail_msg"><font color="#888888" class="m_8896230008981777530gmail_msg"><div class="m_8896230008981777530m_8356086414900213547m_5182031958386667586gmail_msg m_8896230008981777530gmail_msg">- Jonas</div></font></span></div></div>
<br class="m_8896230008981777530gmail_msg"></blockquote></div></div><div class="gmail_extra m_8896230008981777530gmail_msg"><div class="gmail_quote m_8896230008981777530gmail_msg"><blockquote class="gmail_quote m_8896230008981777530gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">______________________________<wbr>_________________<br class="m_8896230008981777530gmail_msg">
LLVM Developers mailing list<br class="m_8896230008981777530gmail_msg">
<a href="mailto:llvm-dev@lists.llvm.org" class="m_8896230008981777530gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a><br class="m_8896230008981777530gmail_msg">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" class="m_8896230008981777530gmail_msg" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br class="m_8896230008981777530gmail_msg">
<br class="m_8896230008981777530gmail_msg"></blockquote></div><br class="m_8896230008981777530gmail_msg"></div>
</blockquote></span></div></div></div>
</blockquote></div><br></div></div></div>