<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=Windows-1252">
<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;}
h1
{mso-style-priority:9;
mso-style-link:"Heading 1 Char";
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:24.0pt;
font-family:"Calibri",sans-serif;
font-weight:bold;}
h2
{mso-style-priority:9;
mso-style-link:"Heading 2 Char";
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:18.0pt;
font-family:"Calibri",sans-serif;
font-weight:bold;}
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.Heading1Char
{mso-style-name:"Heading 1 Char";
mso-style-priority:9;
mso-style-link:"Heading 1";
font-family:"Calibri Light";
color:#2F5496;}
span.Heading2Char
{mso-style-name:"Heading 2 Char";
mso-style-priority:9;
mso-style-link:"Heading 2";
font-family:"Calibri Light";
color:#2F5496;}
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:353264852;
mso-list-template-ids:-1059837950;}
@list l1
{mso-list-id:976493347;
mso-list-template-ids:-2050980836;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7 ;
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:\F0A7 ;
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:\F0A7 ;
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:\F0A7 ;
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:\F0A7 ;
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:\F0A7 ;
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:\F0A7 ;
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:\F0A7 ;
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:1224877280;
mso-list-type:hybrid;
mso-list-template-ids:2013415784 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:1849130014;
mso-list-template-ids:-646039342;}
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 Teresa, Snehasish and David,<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.75in"> <o:p></o:p></p>
<p class="MsoNormal">Thanks for the RFC and follow-up clarification. I have a few questions regarding the use of the metadata and how they are manipulated.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:27.0pt"> <o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo4">While the proposed !callsite metadata and its compression through chaining sounds efficient, have you considered using the existing !dbg metadata as an alternative?
<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo4">Do !callisite metadata need to be maintained on MIR?<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo4">For the !callsite metadata, in order to make sure the metadata not accidentally dropped, how much extra care is needed in passes such as tail call optimization?<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo4">When two callsites are merged by some CFG optimizations, how are their !callsite metadata handled?<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo4">How do we identify a call path in the presence of indirect call sites?<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo4">I was wondering how the !memprof metadata is consumed. Will they be passed into the runtime allocator in some way?
<o:p></o:p></li></ol>
<p class="MsoNormal" style="margin-left:27.0pt"> <o:p></o:p></p>
<p class="MsoNormal">Thanks!<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:27.0pt"> <o:p></o:p></p>
<p class="MsoNormal">Hongtao<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><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">Teresa Johnson <tejohnson@google.com><br>
<b>Date: </b>Monday, November 1, 2021 at 12:06 PM<br>
<b>To: </b>llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Cc: </b>Snehasish Kumar <snehasishk@google.com>, David Li <davidxl@google.com>, Vedant Kumar <vsk@apple.com>, Wenlei He <wenlei@fb.com>, Andrey Bokhanko <andreybokhanko@gmail.com>, Hongtao Yu <hoy@fb.com><br>
<b>Subject: </b>Re: RFC: IR metadata format for MemProf<o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in">One change below along with another clarification. Also, you can view the original RFC here with better formatting for the examples: <a href="https://groups.google.com/g/llvm-dev/c/aWHsdMxKAfE/m/WtEmRqyhAgAJ" target="_blank">https://groups.google.com/g/llvm-dev/c/aWHsdMxKAfE/m/WtEmRqyhAgAJ</a><o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in">On Wed, Oct 27, 2021 at 1:01 PM Teresa Johnson <<a href="mailto:tejohnson@google.com" target="_blank">tejohnson@google.com</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">This RFC describes the IR metadata format for the sanitizer-based heap profiler (MemProf) data when it is fed back into a subsequent compile for profile guided heap optimization. Additional background
can be found in the following RFCs:</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:1.0in;text-indent:-.25in;mso-list:l1 level1 lfo1;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-family:"Arial",sans-serif;color:black">RFC: Sanitizer-based Heap Profiler [1]<o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:1.0in;text-indent:-.25in;mso-list:l1 level1 lfo1;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-family:"Arial",sans-serif;color:black">RFC: A binary serialization format for MemProf [2]<o:p></o:p></span></p>
<div>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Arial",sans-serif;color:black"><br>
<br>
</span><o:p></o:p></p>
</div>
<div>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">We look forward to your feedback.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:"Arial",sans-serif;color:black">Authors:
</span><a href="mailto:tejohnson@google.com" target="_blank"><span style="font-family:"Arial",sans-serif">tejohnson@google.com</span></a><span style="font-family:"Arial",sans-serif;color:black">,
</span><a href="mailto:snehasishk@google.com" target="_blank"><span style="font-family:"Arial",sans-serif">snehasishk@google.com</span></a><span style="font-family:"Arial",sans-serif;color:black">,
</span><a href="mailto:davidxl@google.com" target="_blank"><span style="font-family:"Arial",sans-serif">davidxl@google.com</span></a><o:p></o:p></p>
</div>
<h1 style="mso-margin-top-alt:20.0pt;margin-right:0in;margin-bottom:6.0pt;margin-left:.5in">
<span style="font-size:20.0pt;font-family:"Arial",sans-serif;color:black;font-weight:normal">Requirements</span><o:p></o:p></h1>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">The profile format will need to be reasonably compact within IR, but also facilitate efficiently identifying callsites within the stack contexts for use in interprocedural (and cross module) optimization
for context disambiguation. These optimizations will require transformations to disambiguate the context at a particular allocation, which will require call graph based analysis and optimization.</span><o:p></o:p></p>
<h1 style="mso-margin-top-alt:20.0pt;margin-right:0in;margin-bottom:6.0pt;margin-left:.5in">
<span style="font-size:20.0pt;font-family:"Arial",sans-serif;color:black;font-weight:normal">Input Profile Format</span><o:p></o:p></h1>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">The profile will be in an index binary format, which is detailed in [2]. In the index format, the profiles for each allocation site will be located with the profile data for the function containing the
allocation call site. Each allocation may have multiple profile entries (known as a MIB, or Memory Info Block) uniquely identified by stack context. The entries in the stack context will be symbolized and include file, line and discriminator.</span><o:p></o:p></p>
<h1 style="mso-margin-top-alt:20.0pt;margin-right:0in;margin-bottom:6.0pt;margin-left:.5in">
<span style="font-size:20.0pt;font-family:"Arial",sans-serif;color:black;font-weight:normal">Metadata Format</span><o:p></o:p></h1>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">Similar to branch weights and value profile data from regular PGO, the PGHO profile will be annotated as metadata onto relevant instructions. A natural instruction to attach the profile metadata is on
the allocation callsite, so these allocation calls can be identified and handled by the subsequent heap optimization pass. As an example, this profile data can be used to enable automatic application of hot and cold hints to allocations, for use by a runtime
allocator such as tcmalloc, where support for such allocation hints was recently added [3].</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">However, in order to identify ancestor callsites within an allocation’s call stack context that require modification for disambiguating the context at the allocation site, e.g. via cloning, we will also
want to attach metadata to these callsites. This is particularly important for contexts that cross module boundaries, so that we can identify them in ThinLTO summaries for cross module coordination of context transformations.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">To identify and correlate entries in a context, we will use a unique identifier for each stack entry. Specifically, we will use the 64-bit value from the stack entry table in the indexed profile format
which is formed from the index into the file path table along with the line and discriminator. Another option would be to represent the stack entries using existing debug metadata. However, for stack entries in another module we would need to synthesize additional
debug location metadata in the module containing MIB profile data that references that stack context entry.</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">Assume the following working example. For simplicity, all are shown as being in the same module, however, these function definitions could theoretically be located in multiple different modules.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">x.cc</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 1 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">main() {</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 2 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> foo(); // stack entry id: 123</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 3 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">}</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 4 </span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 5 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">foo() {</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 6 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> baz(); // stack entry id: 234</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 7 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">} </span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 8 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> </span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 9 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">baz() {</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 10 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> if (x)</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 11 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> bar(); // stack entry id: 345</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 12 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> else</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 13 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> bar(); // stack entry id: 456</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 14 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">} </span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 15 </span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 16 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">bar() {</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 17 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> malloc(4); // stack entry id: 567</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:#C1651C"> 18 </span>
<span style="font-size:9.0pt;font-family:"Courier New";color:black">} </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">The call to malloc has 2 possible calling contexts:</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:1.0in;text-indent:-.25in;mso-list:l3 level1 lfo2;vertical-align:baseline">
<![if !supportLists]><span style="font-family:"Arial",sans-serif;color:black"><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-family:"Arial",sans-serif;color:black">main -> foo (x.cc:2) -> baz (x.cc:6) -> bar (x.cc:11) -> malloc (x.cc:17)<o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:1.0in;text-indent:-.25in;mso-list:l3 level1 lfo2;vertical-align:baseline">
<![if !supportLists]><span style="font-family:"Arial",sans-serif;color:black"><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-family:"Arial",sans-serif;color:black">main -> foo (x.cc:2) -> baz (x.cc:6) -> bar (x.cc:13) -> malloc (x.cc:17)<o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">where the stack entry id for each callsite, taken from the profile’s stack entry table contents, is shown in the code comments. The corresponding full contexts in terms of stack entry ids, listed from
the leaf allocation callsite up to the root are:</span><o:p></o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:1.0in;text-indent:-.25in;mso-list:l0 level1 lfo3;vertical-align:baseline">
<![if !supportLists]><span style="font-family:"Arial",sans-serif;color:black"><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-family:"Arial",sans-serif;color:black">567, 345, 234, 123<o:p></o:p></span></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:1.0in;text-indent:-.25in;mso-list:l0 level1 lfo3;vertical-align:baseline">
<![if !supportLists]><span style="font-family:"Arial",sans-serif;color:black"><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-family:"Arial",sans-serif;color:black">567, 456, 234, 123<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">Assuming both contexts execute at runtime, the allocation will end up with 2 MIBs in the profile, one for each of the above contexts.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">To represent this in the IR, we propose 2 new metadata attachment types, as described below.</span><o:p></o:p></p>
<h2 style="mso-margin-top-alt:.25in;margin-right:0in;margin-bottom:6.0pt;margin-left:.5in">
<span style="font-size:16.0pt;font-family:"Arial",sans-serif;color:black;font-weight:normal">Callsite metadata</span><o:p></o:p></h2>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">The </span><span style="font-family:"Courier New";color:black">!callsite</span><span style="font-family:"Arial",sans-serif;color:black"> metadata is used to associate a callsite with its corresponding
references in MIB stack contexts. It contains the associated 64-bit stack entry table value for that callsite from the indexed profile, and is initially only on non-allocation callsites. As will be described later, after inlining it can contain multiple entry
ids or be propagated onto allocation callsites.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">In the above example, for the call to foo(), which had stack entry id 123, the IR callsite would be decorated with a
</span><span style="font-family:"Courier New";color:black">!callsite</span><span style="font-family:"Arial",sans-serif;color:black"> metadata containing that stack entry id:</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:black"> tail call void @_Z3foov(), !dbg !12,
</span><span style="font-size:9.0pt;font-family:"Courier New";color:red">!callsite !14</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-size:9.0pt;font-family:"Courier New";color:red">!14 = !{i64 123}</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">Note that this call may be in a different module initially than the referencing MIB metadata. In order to disambiguate the context across modules, some form of LTO would be required. ThinLTO summary support
will be added to reflect the cross-module contexts and enable cross module optimization of the contexts.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">Also, while for MemProf the ids will be assigned uniquely using information from the MemProf profile, other types of context sensitive profiles could simply reuse the same id after matching with line
table information, or at least leverage the same metadata attachment to assign their own unique ids if there is no MemProf profile.</span><o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">To clarify, the callsite metadata value can be any globally unique identifier. While in this proposal we simply describe using the indexed profile's associated 64-bit stack entry table value, an alternative could
be to compute this from the MD5 hash of the debug information (file:line:discriminator). It doesn't affect the format and its usage described in this RFC.<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<h2 style="mso-margin-top-alt:.25in;margin-right:0in;margin-bottom:6.0pt;margin-left:.5in">
<span style="font-size:16.0pt;font-family:"Arial",sans-serif;color:black;font-weight:normal">Memprof metadata</span><o:p></o:p></h2>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">The </span><span style="font-family:"Courier New";color:black">!memprof</span><span style="font-family:"Arial",sans-serif;color:black"> metadata describes the MIBs for the leaf allocation callsite it
is attached to. If there are multiple stack contexts leading to that allocation, it will have a single
</span><span style="font-family:"Courier New";color:black">!memprof</span><span style="font-family:"Arial",sans-serif;color:black"> metadata attachment, with a level of indirection used to list all related MIB, as shown in the later example.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">As with the indexed profile format, we need to be able to add or modify fields of the MIB entries while maintaining backwards compatibility with older bitcode. Therefore, we use a schema format with the
MIB profile entry fields described by a “Memprof Schema” module level metadata, for example:</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">!llvm.module.flags = !{!1}</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">!1 = !{i32 1, !”Memprof Schema”,!”Stack”, !”AllocCount”, !”AveSize”, !”MinSize”, !”MaxSize”, !”AveAccessCount”, !”MinAccessCount”, !”MaxAccessCount”, !”AveLifetime”, !”MinLifetime”, !”MaxLifetime”, !”NumMigration”,
!”NumLifetimeOverlaps” }</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in">
<span style="font-family:"Arial",sans-serif;color:black">The first (merge behavior) field is 1 (ModFlagBehavior::Error), meaning that it is an error to merge modules with different values, or in other words, merging modules compiled with different profiles
generated with different versions of the indexed profile format.</span><o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">Using module flags for the schema doesn't work, because it only supports a single string tag and an integer flag value, not arbitrary contents. Instead, I have implemented this using a new named metadata:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">!memprof.schema = !{!0}<br>
!0 = !{!"Stack", !"AllocCount", !"AveSize", !"MinSize", !"MaxSize", !"AveAccessCount", !"MinAccessCount", !"MaxAccessCount", !"AveLifetime", !"MinLifetime", !"MaxLifetime", !"NumMigration", !"NumLifetimeOverlaps"}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">Named metadata must only hold metadata nodes as operands. Here we use a single operand to point to metadata that describes the schema.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">The advantage of using a single metadata operand in the new !memprof.schema metadata, vs for example a list of metadata operands each pointing to a single MDString schema field, is that it simplifies detection of
different schemas when modules are merged for LTO. If the schemas are identical, the merged !memprof.schema metadata will continue to hold a single metadata node as the node holding the schema (!0 above) will be shared. If they are not identical, the merged
module's !memprof.schema metadata will hold more than one metadata operand, one for each unique schema.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">An alternative, which is what I originally had in a prototype, was to include the MDString field tags in each !memprof metadata, for example:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">!274 = !{!"Stack", !273, !"AllocCount", i32 1, !"AveSize", i32 4, !"MinSize", i32 4, !"MaxSize", i32 4, !"AveAccessCount", i64 5, !"MinAccessCount", i64 1, !"MaxAccessCount", i64 10, !"AveLifetime", i32 10, !"MinLifetime",
i32 10, !"MaxLifetime", i32 10, !"NumMigration", i32 0, !"NumLifetimeOverlaps", i32 0}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">This provides maximal flexibility of merging modules using different schemas, at the expense of additional overhead in operands (doubling the number of operands of !memprof metadata). But if we need to support merging
modules with different schemas, we could alternatively just support unifying the named metadata schemas and fixing up the associated !memprof metadata during the merging process, rather than carrying this extra overhead.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<p class="MsoNormal" style="margin-left:.5in">-- <o:p></o:p></p>
<div>
<div>
<div>
<table class="MsoNormalTable" border="0" cellspacing="0" cellpadding="0" style="margin-left:.5in">
<tbody>
<tr>
<td nowrap="" style="border:none;border-top:solid #D50F25 1.5pt;padding:0in 0in 0in 0in">
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:#555555">Teresa Johnson |<o:p></o:p></span></p>
</td>
<td nowrap="" style="border:none;border-top:solid #3369E8 1.5pt;padding:0in 0in 0in 0in">
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:#555555"> Software Engineer |<o:p></o:p></span></p>
</td>
<td nowrap="" style="border:none;border-top:solid #009939 1.5pt;padding:0in 0in 0in 0in">
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:#555555"> <a href="mailto:tejohnson@google.com" target="_blank">tejohnson@google.com</a> |<o:p></o:p></span></p>
</td>
<td nowrap="" style="border:none;border-top:solid #EEB211 1.5pt;padding:0in 0in 0in 0in">
</td>
</tr>
</tbody>
</table>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</div>
</body>
</html>