<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" 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 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:DengXian;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"\@DengXian";
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.gmaildefault
{mso-style-name:gmail_default;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:607590421;
mso-list-template-ids:248648074;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1
{mso-list-id:803543006;
mso-list-template-ids:-2007486746;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2
{mso-list-id:997996646;
mso-list-type:hybrid;
mso-list-template-ids:1867183910 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l2:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3
{mso-list-id:1426226046;
mso-list-template-ids:-917370890;}
@list l3:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4
{mso-list-id:1454515801;
mso-list-template-ids:-909057110;}
@list l4:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style>
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Hello <span style="font-size:12.0pt;color:black">Snehasish,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">It’s great to see this RFC about the profile format of the heap profiler since last the RFC. I have a couple questions about how calling contexts are stored and processed by the compiler:<o:p></o:p></span></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="color:black;margin-left:0in;mso-list:l2 level1 lfo7">
<span style="font-size:12.0pt">How are recursive allocation contexts stored? Wondering if there’s any recursive compression performed. For example, a tree-based construction algorithm may create tree nodes recursively. Is each tree node object modeled by its
unique dynamic context?<o:p></o:p></span></li><li class="MsoListParagraph" style="color:black;margin-left:0in;mso-list:l2 level1 lfo7">
<span style="font-size:12.0pt">Will the contexts of a leaf function merged during compilation when the leaf function is not inlined? If so, where does the merging happen?<o:p></o:p></span></li></ol>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">We have seen similar issues when working on CSSPGO (Context-sensitive PGO). I’m wondering if they could be a problem here.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Hongtao<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">Snehasish Kumar <snehasishk@google.com><br>
<b>Date: </b>Wednesday, September 29, 2021 at 3:17 PM<br>
<b>To: </b>llvm-dev <llvm-dev@lists.llvm.org>, Vedant Kumar <vsk@apple.com>, Wenlei He <wenlei@fb.com>, andreybokhanko@gmail.com <andreybokhanko@gmail.com>, David Li <davidxl@google.com>, Teresa Johnson <tejohnson@google.com><br>
<b>Subject: </b>RFC: A binary serialization format for MemProf<o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:10.0pt;font-family:"Courier New";color:black">This RFC contains the following:</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-size:12.0pt"><o:p> </o:p></span></p>
</div>
<div>
<div>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:7.5pt;font-family:"Courier New";color:black">* Proposal to introduce a new raw binary serialization format for heap allocation profiles</span><span style="font-size:7.5pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:7.5pt;font-family:"Courier New";color:black">* Proposal to extend the
<span class="gmaildefault">PGO </span>indexed format to hold heap allocation profiles</span><span style="font-size:7.5pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span class="gmaildefault"><span style="font-size:7.5pt;font-family:"Courier New"">We look forward to your feedback on the proposals.</span></span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:10.0pt;font-family:"Courier New";color:black">Authors:
<a href="mailto:snehasishk@google.com">snehasishk@google.com</a>, <a href="mailto:davidxl@google.com">davidxl@google.com</a>, <a href="mailto:tejohnson@google.com">tejohnson@google.com</a> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Introduction</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">—-----------</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The design of a sanitizer-based heap profiler (MemProf) was shared with llvm-dev in Jun 2020 [1]. Since then Teresa (@tejohnson) has added a sanitizer based heap profiler which can be enabled
with -fmemory-profile. Today it writes out the data in a text format which can be inspected by users. We have used this to drive analyses of heap behaviour at Google. This RFC shares details on a binary serialization format for heap profiling data which can
then be reused by the compiler to guide optimizations similar to traditional PGO. </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Similar to the existing instrumentation based PGO, the binary heap profile data for PGHO has two forms. One is the raw data format that is used by the profiler runtime, and the other is the
indexed profile format used by the compiler. The profile data with the indexed profile data format will be generated by llvm-profdata from the raw profile data offline. This allows a single binary profile file to hold the PGO and Memprof profiling data. Fig
1 below shows the binary format generation and use.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ┌──────────────────┐ Raw Profile ┌───────────────┐ Indexed Profile (v8) </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ Compiler Runtime ├─────────────► llvm-profdata ├───► with Memprof data ───► -fprofile-use</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> └──────────────────┘ └───────────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Fig 1: Memprof binary profile lifecycle</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Raw Binary Format</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">—----------------</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The raw binary format contains 4 sections</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">1. Memprof raw profile header</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">2. Memory mapping layout</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">3. Memory Info Block (MIB) records</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">4. Call stack information</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Magic |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ H</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Version | E</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ A</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Total Size | D </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ E </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------| Map Offset | R</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| +----------------------+ </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| +-----| MIB Offset | </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | +----------------------+ </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | | Call Stack Offset |---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | +----------------------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+-------->| Number of | M |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | Map Entries | A |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +----------------------+ P | </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | Map Entry | S |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +----------------------+ E |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | ... | C |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +----------------------+ T |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | | I |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | Map Entry | O |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +----------------------+ N |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +----------------------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +---->| Number of | M |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | MIB Entries | I |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ B | </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | MIB Entry | S |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ E |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | ... | C |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ T |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | I |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | MIB Entry | O |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ N |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Number of |<--------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Call Stack Entries | S S</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ T E</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Call Stack Entry | A C</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ C T</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | ... | K I</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+ O</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | Call Stack Entry | N</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Fig 2: Memprof Raw Format</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* Memprof raw profile header</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The header consists of a unique identifier, version number, total size of the profile as well as offset into the profile for each of the following sections - memory mapping layout, memprof
profile entries and call stack information. We do not intend to maintain backwards compatibility for the raw binary format.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* Memory mapping layout</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The process memory mappings for the executable segment during profiling are stored in this section. This allows symbolization during post processing for binaries which are built with position
independent code. For now all read only, executable mappings are recorded, however in the future, mappings for heap data can also potentially be stored. For each mapping, we record</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l0 level1 lfo3;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">Start (virtual address)<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l0 level1 lfo3;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">End (virtual address)<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l0 level1 lfo3;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">Offset (from the file it was mmap-ed from)<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l0 level1 lfo3;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">buildId (linker generated hash -Wl,build-id<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* MIB Records</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The profile information we collect is currently defined in [2]. The section begins with a 8 byte entry containing the number of profile entries in this section. Each entry is uniquely identified
by the dynamic calling context of the allocation site. For each entry, various metrics such as access counts, allocation sizes, object lifetimes etc are computed via profiling. This section may contain multiple entries identified by the same callstack id.
Subsequent processing to convert and merge multiple raw profiles will deduplicate any such entries.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* Call stack information<br>
Each memprof profile entry is uniquely identified by its dynamic calling context. In this section we record the identifier and its corresponding call stack trace. We use the sanitizer stack depot provided identifier and serialize the trace for each without
deduplication. The section begins with a 8b entry containing the number of call stack entries. Each call stack entry contains a 8b field which denotes how many contexts are recorded in this entry. Each frame is identified by an 8b program counter address which
holds the call instruction virtual address - 1. Further deduplication is possible though we do not do so at this time.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* Raw Profile Characteristics</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">To understand the characteristics of raw binary profiles generated by Memprof, we experimented with a clang bootstrap build. We ran 500 invocations of Memprof-instrumented clang on clang source
code. Each invocation produced a raw binary profile and we present some aggregate information about them below:</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------------------------------+--------+---------+---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | Min | Median | Max |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------------------------------+--------+---------+---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| Unique allocation contexts | 940 | 10661 | 35355 |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------------------------------+--------+---------+---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| MIB records size (bytes) | 101528 | 1151396 | 3818348 |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------------------------------+--------+---------+---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| Call stack section size (bytes) | 31080 | 419048 | 1439144 |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------------------------------+--------+---------+---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| Total Size (bytes) | 133336 | 1571680 | 5258220 |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="margin-left:.5in"><span style="font-size:10.0pt;font-family:"Courier New";color:black">+---------------------------------+--------+---------+---------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The size of the header is 48 bytes and the number of read only executable memory maps is usually small (12 in this case) with each map entry consuming 64 bytes. We find that the raw profiles
are highly compressible, on average files are compressed by 81%. The largest raw profile in the dataset is ~5M in size. It is compressed to 975K using zip on default settings. In contrast for the same clang build, the instrumented PGO raw profile is ~21M in
size (zip compressed 73%). Note that the Memprof profile size is proportional to the number of allocation contexts during profiling. </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Since these are profiles from individual invocations, they must be merged before use. This is performed implicitly during the conversion to indexed profile format by llvm-profdata. MIBs are
merged based on their call stack.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Memprof extensions for the indexed profile format</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">—------------------------------------------------</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| MAGIC |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| VERSION |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| HASHTYPE |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+--+----------+--+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">|HASHTAB OFFSET |-------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+--+----------+--+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| PROFILE | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| SUMMARY | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| DATA | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+ <----+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| OnDisk |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| Chained |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| HashTable |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Fig 3: Existing PGO indexed profile format</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">During the offline processing step (using llvm-profdata), allocation contexts are pruned and merged. The end result is a collection of unique allocation contexts with access, size and lifetime
properties. Contexts are uniquely identified based on the call stack and are stored using a prefix deduplication scheme described in Section “Symbolized Memprof call stack section”.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">To fit into the PGO profile format, we need to index the profile using the function name. The only functions that own Memprof profile data are those direct callers of the allocator primitive
functions. Thus the profile data mapping in the IR must account for potentially missing frames. Implications on matching of the profile data with the IR is touched upon in Section “Profile Data matching in IR” and will be further detailed in an upcoming RFC. </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The Memprof profile data for a particular function can then be just an array of MIB entries. One allocation site in the function can have multiple MIB entries each one of them corresponding
to one allocation context.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The change to the existing PGO indexed format is summarized as:</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l1 level1 lfo6;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">Augment the profile record data structure to include an optional MIB array after the value profile data [3].<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l1 level1 lfo6;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">Add one additional section before the existing OnDiskChainedHashtable to store the allocation stacks (referenced by the MIBs). This section is after the profile
summary data section [4].<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in;mso-list:l1 level1 lfo6;vertical-align:baseline">
<![if !supportLists]><span style="font-size:10.0pt;font-family:Symbol;color:black"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:10.0pt;font-family:"Courier New";color:black">Bump the version number.<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Memprof portable entry format</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">—----------------------------</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The raw memprof profile entry format is subject to change with version. However, the indexed profile entry must be backwards compatible to ensure that the PGO profile as a whole is backwards
compatible. We propose a schema based format - per function description of a Memprof profile entry. Each field is identified by a tag. We propose the following schema:</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">struct MIBMeta {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> enum MIBFieldTag {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> // The tag ids remain unchanged. </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> Unused = 0, </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> StackID = 1,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> AllocCount = 2,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> AveSize = 3,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MinSize = 4,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MaxSize = 5,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> AveAccessCount = 6,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MinAccessCount = 7,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MaxAccessCount = 8,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> AveLifetime = 9,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MinLifetime = 10,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MaxLifetime = 11,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> NumMigration = 12,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> NumLifetimeOverlaps = 13,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> NumSameAllocCPU = 14,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> NumSameDeallocCPU = 15</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> };</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> enum MIBFieldType {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> Unused = 0,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> UINT8 = 1,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> UINT16 = 2,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> UINT32 = 3, // Varint encoded</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> UINT64 = 4, // Varint encoded</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> };</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">};</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">// Mapping of tags to their descriptive names</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">const char *MIBFieldName[] = {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> "",</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> "StackID", </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> "AllocCount",</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> …</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> "NumSameDeallocCPU"</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">};</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">// Mapping of tags to their types</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">uint8 MIBFieldType [] = {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> 0, // unused</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MIBMeta::MIBFieldType::UINT64,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ….</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">};</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">To make the field tag, field name, and field type declarations always in sync, a shared .inc file will be used. This file will be shared between compiler-rt and llvm/lib/ProfileData libraries.
Dependencies across the compiler-rt project are not recommended for isolation.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">// MIBDef.inc file</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">// define MIBEntryDef(tag, name, type) before inclusion</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">MIBEntryDef(StackID = 1, "StackID",</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MIBMeta::MIBFieldType::UINT64)</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">MIBEntryDef(AllocCount = 2, "AllocCount", </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MIBMeta::MIBFieldType::UINT32)</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">...</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">MIBEntryDef(NumSameDeallocCPU=13,"NumSameDeallocCPU",
</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> MIBMeta::MIBFieldType:UINT8)</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">enum MIBFieldTag {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> StartTag = 0,</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #define MIBEntryDef(tag, name, type) tag</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #include "MIBDef.inc"</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #undef MIBEntryDef</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">};</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">const char *MIBFieldName {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #define MIBEntryDef(tag, name, type) name</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> "",</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #include "MIBEntryDef.inc"</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #undef MIBEntryDef</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">};</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">uint8 MIBFieldType {</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #define MIBEntryDef(tag, name, type) type</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> 0, // not used</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #include "MIBEntryDef.inc"</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> #undef MIBDefEntry</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">};</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">The InstrProfRecord for each function will hold the schema and an array of Memprof info blocks, one for each unique allocation context.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Symbolized Memprof call stack section </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">—------------------------------------<br>
<br>
</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">This section holds the symbolized version of the call stack section in the raw profile. This is necessary to enable the compiler to map recorded runtime PC addresses to source locations during
recompilation. For space efficiency, this section is split into three subsections: 1. stack entry table 2. file path table 3. string table.<br>
<br>
</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Fig 4 shows the relationship between the three tables.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> STACK ENTRY FILE PATH STRING</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> TABLE TABLE TABLE</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ┌────────┐ ┌──┬──┬──┐ ┌─────────┐</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │ │ │ │ │ │10 abc │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │ ├──┼──┼──┤ ├─────────┤</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │ │ │ │ │◄┐ │11 def │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │ ├──┼──┼──┤ │ ├─────────┤</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ├──┬──┬──┤ │ │ │ │ │ │12 ghi │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ┌───┤03│LN│DI│ ├──┼──┼──┤ │ ├─────────┤</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ ├──┴──┴──┤ ┌───►│03│13│01├─┘ ┌─►│13 XY.h │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ └────────┘ │ └──┴─┬┴──┘ │ └─────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │ │ │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> └────────────────┘ └────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Fig 4. The Stack Entry, File Path and String Table. </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> LN = Line Number, DI = Discriminator</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* Stack Entry Table: Each uniquely identified symbolized call stack consists of a variable number of callsites. In the indexed format, each callsite needs to be represented as file:line:discriminator
(as shown in Fig 4). The call stack location is a 64-bit field, but it is split into three subfields: file table index, line number, and the discriminator value. The file table index is a pointer to a leaf node in the prefix encoded scheme described below.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* File path table using prefix encoding: Full path filenames have lots of common substrings due to the directory structure so they can be compressed. One simple scheme is to use the reverse
prefix tree representation. In this representation, the name string of a directory at each level (not including prefixes) is represented by a node, and it is linked to its parent node. To summarize, the file path table is represented as an array of nodes organized
as a forest of reversed tree structures. </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">For instance, the strings
<br>
“abc/def/ghi/XY.c”, <br>
“abc/def/ghi/XY.h”, </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">“abc/def/jkl/UV.c” </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">are represented as </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +-----------+<------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | abc | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+----->+---->+-----------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | | def +-------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| | +-----------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| +-----+ ghi |<-------+----+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">| +-----------+ | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">+-+--------->| jkl | | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +-----------+ | | </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | | XY.c +--------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | +-----------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +----------+ UV.c | |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +-----------+ |</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> | XY.h +-------------+</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> +-----------+ </span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Fig 5. Prefix tree representation of paths in the file path table</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Each parent link implies a path separator ‘/’. Furthermore we represent each file or directory string as an integer offset into the string table (see Fig 4). Thus each node holds an offset
into the string table and a pointer to the parent (interior) directory node.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">* String table: To remove redundancies across prefix tree nodes in the file path encoding, we use a string table which stores the mapping of string to a unique id. The id can be simplified
as the implicit offset into the table.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Thus this representation exploits redundancy in the source file path prefix where there are a large number of source files in a small number of deeply nested directories.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Symbolizing the raw PC addresses in post-processing using llvm-profdata requires the binary to also be provided as input. As an alternative, we will also experiment with incrementally generating
the symbolized call stack section as part of the raw profile dump at the cost of increased profiling overhead.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Profile Data matching in IR</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">—--------------------------</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">When matching the profile data, we may have already early inlined the direct caller of the allocation into its caller(s). This means we need to take some additional steps to identify the matching
MIBs. For example, consider the following partial call graph:</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"><br>
<br>
</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ┌────────────────────┐ ┌────────────────────┐</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> A │ Call B; debug loc1 │ C │ Call B; debug loc2 │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> └───────┬────────────┘ └───────────┬────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ ┌─────────────────────────┐ │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> └────► Call malloc; debug loc3 ◄─────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> B └─────────────────────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">There will be 2 MIB entries, one for each context (A->B and C->B). As noted earlier, the MIB profile entries will be owned by the function calling the allocation function. Therefore, we will
keep both MIB entries associated with function B in the profile.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">If early inlining (i.e. before profile matching) inlines B into A but not into C it will look like the following when we try to match the profile:</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ┌────────────────────┐</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> ┌────────────────────────┐ C │ Call B; debug loc2 │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> A │Call malloc; debug loc3 │ └───────────┬────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ ; inlined at │ │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> │ ; debug loc1 │ ┌──────────────┴───────────┐</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> └────────────────────────┘ B │ Call malloc; debug loc3 │</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black"> └──────────────────────────┘</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">Because the MIB corresponding to the A->B context is associated with function B in the profile, we do not find it by looking at function A’s profile when we see function A’s malloc call during
matching. To address this we need to keep a correspondence from debug locations to the associated profile information. The details of the design will be shared in a separate RFC in the future.</span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">[1] <a href="https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html" target="_blank">https://lists.llvm.org/pipermail/llvm-dev/2020-June/142744.html</a></span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">[2] <a href="https://git.io/JzdRa" target="_blank">https://git.io/JzdRa</a></span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">[3] <a href="https://git.io/JzdRR" target="_blank">https://git.io/JzdRR</a></span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:10.0pt;font-family:"Courier New";color:black">[4] <a href="https://git.io/JzdRN" target="_blank">https://git.io/JzdRN</a></span><span style="font-size:10.0pt;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>