<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">It looks like the example doesn't use the encoding described in the text?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Let's take the original source as an example, after loop unrolling and peeling, the code may looks like:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">for (i = 0; i < N & 3; i+= 4) {<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x40<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal">if (i++ < N) {<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x100<o:p></o:p></p>
<p class="MsoNormal"> if (i++ < N) {<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x200<o:p></o:p></p>
<p class="MsoNormal"> if (i++ < N) {<o:p></o:p></p>
<p class="MsoNormal"> foo(); // discriminator: 0x300<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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. Note this requires 2 bytes for ULEB128 instead of 1.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">--paulr<o:p></o:p></span></p>
</div>
</body>
</html>