<div dir="ltr">You are right, this problem also exists in GCC. And it was not solved there, we just left it open. As now we are tuning aggressively for LLVM, I think it's a good time to raise this issue and have a thorough solution so that we have a good chance of gaining more better performance than GCC afdo.<div><br></div><div>Dehao<br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 27, 2016 at 11:44 AM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@gmail.com</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">Is there prior art for this sort of thing (in GCC, for example) - I take it this isn't the first time this has come up as a problem for profile accuracy? (so it'd be helpful to know prior solutions to this (& if we're not doing whatever was done before, what it is about our situation that's different, etc), or why it hasn't been a problem, etc)</div><div class="HOEnZb"><div class="h5"><br><div class="gmail_quote"><div dir="ltr">On Thu, Oct 27, 2016 at 11:39 AM Dehao Chen <<a href="mailto:dehao@google.com" target="_blank">dehao@google.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="m_4937211271393304677gmail_msg">Motivation:<div class="m_4937211271393304677gmail_msg">Many optimizations duplicate code. E.g. loop unroller duplicates the loop body, GVN duplicates computation, etc. The duplicated code will share the same debug info with the original code. For SamplePGO, the debug info is used to present the profile. Code duplication will affect profile accuracy. Taking loop unrolling for example:</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">#1 foo();</div><div class="m_4937211271393304677gmail_msg">#2 for (i = 0; i < N; i++) {<br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">#3 bar();</div><div class="m_4937211271393304677gmail_msg">#4 }</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">If N is 8 during runtime, a reasonable profile will look like:</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">#1: 10</div><div class="m_4937211271393304677gmail_msg">#3: 80<br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">But if the compiler unrolls the loop by a factor of 4, the callsite to bar() is duplicated 4 times and the profile will look like:</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">#1: 10</div><div class="m_4937211271393304677gmail_msg">#3: 20</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">The sample count for #3 is 20 because all 4 callsites to bar() are sampled 20 times each, and they shared the same debug loc (#3) so that 20 will be attributed to #3 (If one debugloc is mapped by multiple instructions, the max sample count of these instructions is used as debugloc's sample count).</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">When loading this profile into compiler, it will think the loop trip count is 2 instead of 8.</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">Proposal:</div><div class="m_4937211271393304677gmail_msg">When compiler duplicates code, it encodes the duplication info in the debug info. As the duplication is not interesting to debugger, I propose to encode this as part of the discriminator.</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">There are 2 types of code duplication:</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">1. duplicated code are guaranteed to have the same execution count (e.g. loop unroll and loop vectorize). We can record the duplication factor, for the above example "4" is recorded in the discriminator.</div><div class="m_4937211271393304677gmail_msg">2. duplicated code that may have different execution count (e.g. loop peel and gvn). For a same debugloc, a unique number is assigned to each copy and encoded in the discriminator.</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">Assume that the discriminator is uint32. The traditional discriminator is less than 256, let's take 8 bit for it. For duplication factor (type 1 duplication), we assume the maximum unroll_factor * vectorize_factor is less than 256, thus 8 bit for it. For unique number(type 2 duplication), we assume code is at most duplicated 32 times, thus 5 bit for it. Overall, we still have 11 free bits left in the discriminator encoding.</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">Let's take the original source as an example, after loop unrolling and peeling, the code may looks like:</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">for (i = 0; i < N & 3; i+= 4) {</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x40</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x40</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x40</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x40</div><div class="m_4937211271393304677gmail_msg">}</div><div class="m_4937211271393304677gmail_msg">if (i++ < N) {</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x100</div><div class="m_4937211271393304677gmail_msg"> if (i++ < N) {</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x200</div><div class="m_4937211271393304677gmail_msg"> if (i++ < N) {</div><div class="m_4937211271393304677gmail_msg"> foo(); // discriminator: 0x300</div><div class="m_4937211271393304677gmail_msg"> }</div><div class="m_4937211271393304677gmail_msg"> }</div><div class="m_4937211271393304677gmail_msg">}</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">The cost of this change would be increased debug_line size because: 1. we are recording more discriminators 2. discriminators become larger and will take more ULEB128 encoding.</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">The benefit is that the sample pgo profile can accurately represent the code execution frequency. And we do not need to introduce new building blocks to debug info.</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">Comments?</div><div class="m_4937211271393304677gmail_msg"><br class="m_4937211271393304677gmail_msg"></div><div class="m_4937211271393304677gmail_msg">Thanks,</div><div class="m_4937211271393304677gmail_msg">Dehao</div></div>
</blockquote></div>
</div></div></blockquote></div><br></div></div></div>