<div dir="auto">IIUC, this proposal is just saying that we should infer a static profile for entry counts just like we do for branch probabilities. In the case of entry counts, we do not hide that information behind an analysis like BPI, so currently just annotating synthetic PGO entry counts is a simple solution that piggybacks on the PGO mechanism and Just Works.<div dir="auto"><br></div><div dir="auto">If that is correct then this makes perfect sense to me.</div><div dir="auto"><br></div><div dir="auto">It could be argued that we ought to refactor things so that the raw PGO metadata is only ever accessed via a wrapper CGSCC analysis that falls back to interprocedural analysis (i.e. static profile heuristics) when the entry count metadata is missing, just like BPI does with static intraprocedural analysis and branch weight metadata. However, we probably don't want to do that while folks are still depending on the old PM in production since CGSCC analyses don't exist there which would force us to maintain an old and new way of doing it.</div><div dir="auto"><br></div><div dir="auto">(Also, it sounds like you want to compute this with a top-down CGSCC traversal, so it might not actually be computable incrementally as a bottom up CGSCC analysis which is what CGSCC analyses currently do; an auxiliary module analysis for the top-down part might work around this though)</div><div dir="auto"><br></div><div dir="auto">Also, the need to run this logic (or similar logic) as a "ThinLTO analysis" suggests not wedding it too much with the intricacies of the IR-level pass management (although admittedly we already do that with the inliner and then ThinLTO has to approximate those inlining decisions, so it might not be the end of the world to have some divergence).<br><div dir="auto"><br></div><div dir="auto">-- Sean Silva</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Dec 12, 2017 5:02 PM, "Easwaran Raman via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span id="m_2973652766175457581gmail-docs-internal-guid-54633d65-4d61-93c5-4945-401b16f25f9a"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Functions in LLVM IR have a function_entry_count metadata that is attached in PGO compilation. By using the entry count together with the block frequency info, the compiler computes the profile count of call instructions based on which the hotness/coldness of callsites can be determined. Experiments have shown that using a higher threshold for hot callsites results in improved runtime performance of the generated code without significant code size increases. We propose to generate synthetic function counts for non-PGO compilation and use the counts for boosting hot callsites during inlining. </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Synthetic function entry counts of functions are initialized based on properties of the function such as whether it is visible outside the module, whether it has an inline keyword and so on. Then, the callgraph SCC is traversed in reverse post-order. Counts of callsites are determined based on the entry count and the block frequency of the callsite. The callsite count gets added to the entry count of the callee. For targets of indirect calls, we will use the !callees metadata to find the possible targets and distribute the count equally among them. For functions in a non-trivial SCC, the algorithm has to ensure that the counts are stable and deterministic.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> In ThinLTO mode, the function summary contains the list of call edges from the function. We propose to add the relative block frequency on these edges. During the thinlink phase, we propagate the function counts on the entire call graph and update the function summary with the synthetic counts. Additionally, we plan to use the computed counts to drive the importing decisions. </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Alternative approach </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">-----------------------------</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">An alternative to generating synthetic counts is to make block frequency info an inter-procedural analysis. Such an analysis would allow comparing BFI of callsites in two different functions. This has several downsides:</span></p><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">The inter-procedural BFI computation is likely to be more expensive in terms of compile-time. </span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Many function passes invalidate the BFI. This will require selective invalidation of function BFIs.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Inliner correctly updates function counts of a callee after a callsite is inlined. We can piggyback on this mechanism by using synthetic counts. </span></p></li></ul></span></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div></div>