<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 27, 2016 at 2:53 PM, Robinson, Paul <span dir="ltr"><<a href="mailto:paul.robinson@sony.com" target="_blank">paul.robinson@sony.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-US">
<div class="gmail-m_-1440165713298698961m_3613846446113043397WordSection1">
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)">It looks like the example doesn't use the encoding described in the text?<u></u><u></u></span></p><span>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal">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.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Let's take the original source as an example, after loop unrolling and peeling, the code may looks like:<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">for (i = 0; i < N & 3; i+= 4) {<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<u></u><u></u></p>
<p class="MsoNormal">}<u></u><u></u></p>
<p class="MsoNormal">if (i++ < N) {<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x100<u></u><u></u></p>
<p class="MsoNormal"> if (i++ < N) {<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x200<u></u><u></u></p>
<p class="MsoNormal"> if (i++ < N) {<u></u><u></u></p>
<p class="MsoNormal"> foo(); // discriminator: 0x300<u></u><u></u></p>
<p class="MsoNormal"> }<u></u><u></u></p>
<p class="MsoNormal"> }<u></u><u></u></p>
<p class="MsoNormal">}<u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
</span><p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)">If we allocate 8 bits to "traditional" discriminators, then 0x40 falls into that range, so I'd think the calls to foo() inside the loop should be using 0x400
to encode the unroll factor. </span></p></div></div></blockquote><div><br></div><div>You are right, thanks for pointing this out.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div lang="EN-US"><div class="gmail-m_-1440165713298698961m_3613846446113043397WordSection1"><p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)"> Note this requires 2 bytes for ULEB128 instead of 1.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)">And if we allocate another 8 bits to the unroll factor, then the trailing calls should use 0x10000, 0x20000, 0x30000. These will require 3 bytes for ULEB128
instead of 2.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)">I think it would be fine to allocate only 4 bits to "traditional" discriminators (as you need them to be unique across the same source location, but not across
different source locations, and 16 independent basic blocks for the same source location seems like plenty to me; but I haven't looked at a lot of cases with discriminators). This would allow you to use 0x40 to encode the unroll factor in this example. If
you still want to allocate 8 bits for unroll factor, then the trailing calls would use 0x1000, 0x2000, 0x3000 so as long as you had no more than 3 trailing calls you can still encode the discriminator in a 2-byte ULEB128.</span></p></div></div></blockquote><div><br></div><div>I did some evaluation on speccpu2006 c/c++ benchmarks. Among all source built, there are 268K non-zero discriminators emitted. The largest discriminator is 779 (coming from 471.omnetpp, which has significant amount of EH code.) The 99% percentile is 18. The 85% percentile is 3. For the duplication factor, the largest is 320, the 99% percentile is 40, the 85% percentile is 4.</div><div><br></div><div>If we want to encode this into the discriminator, I would propose encode something like:</div><div><br></div><div>high bits ----------> low bits</div><div>EEEEEEEECCCCCFFDDD CCCFFFFFFDDDDD</div><div><br></div><div>D: normal discriminator</div><div>F: duplication factor</div><div>C: code cloning</div><div>E: empty bits</div><div><br></div><div>So the lower 14 bits should be able to cover 99% percentile</div><div><br></div><div>Or something like:</div><div>high bits ----------> low bits<br></div><div><div>EEEEEEEECCCCCFFDDD CFFFDDD CCFFFDD</div></div><div><br></div><div>So the lower 7 bits should be able to cover 85% percentile and the lower 14 bits should be able to cover 99% percentile.</div><div><br></div><div>Dehao</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div lang="EN-US"><div class="gmail-m_-1440165713298698961m_3613846446113043397WordSection1"><p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif;color:rgb(31,73,125)">--paulr<u></u><u></u></span></p>
</div>
</div>
</blockquote></div><br></div></div>