<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.EmailStyle19
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1601840111;
mso-list-type:hybrid;
mso-list-template-ids:916763568 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">The way I understand it, the problem that the byte type is meant to solve is part of a broader-scoped problem, which is the inconsistency of pointer semantics in LLVM (and other compilers, for that matter). Subtle misunderstandings in how
pointer semantics works between different optimization passes causes misoptimizations to happen, and identifying which pass is the culprit is challenging. This is not helped by the LLVM language reference being outright incorrect here: it describes provenance
in terms of data dependence, even through integers, which is not how any of our analyses actually work, generally preferring to reason on a more escape-based analysis approach.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">However, the byte type proposal feels to me like it is motivated on a minor portion of the problem, so narrow that it feels like it only really solves “how to write memcpy in standard C” aspect of this problem. It doesn’t really address
how the addition of byte types would fix miscompilations, especially anything beyond memcpy (for example, C code compiled with -fno-strict-aliasing). It doesn’t suggest any fixes to the current known inconsistencies in the language specification. And as a
result, it’s kind of dismissive as to why isolated fixes to various optimization passes are insufficient to achieve coherent semantics.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Stepping back a bit, it’s helpful to understand that, for the purposes of building an operational semantics, a pointer is not an i64 but a { i64, BOOM (Bag Of Other Metadata) }, where the BOOM contains sufficient information to explain
when a load or store of a pointer is undefined behavior—including liveness information, provenance, and noalias rules [1]. Described like this, three things should be clear. First, the inttoptr instruction has to recreate the BOOM given no information, which
is necessarily a pessimistic assumption (it may be useful to have intrinsics that provide less pessimistic recreation of the BOOM). Second, loads and stores of pointers in memory needs to preserve the BOOM, presumably through a generally inaccessible shadow
memory feature. Finally, the interaction of non-pointer types with the representation of the BOOM in memory needs to be given a definition.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Fundamentally, then, the problem is inttoptr (and to a lesser degree, ptrtoint, as it constitutes a vehicle for escaping pointers), and memory is involved only insofar as it constitutes a ‘hidden’ inttoptr (and ptrtoint). But byte doesn’t
really expose the ‘hidden’ inttoptr, it just hides it in a different place. Indeed, it still retains the existing ones if you should load a pointer with an i64. To me, it appears only to be useful in giving a way to canonicalize @llvm.memcpy into a regular
load type, but an entirely new type doesn’t seem necessary for that—intrinsics that give access to reading and writing shadow BOOM seem like they would be sufficient. You might argue that such intrinsics would eliminate the ability of users to write their
own copies of memcpy, but even here, byte is an insufficient proposal—there’s no way to write a word-based memcpy in C with this proposal (assuming -fno-strict-aliasing, of course).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">With that in mind, I’d like to ask a few questions:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Have you been tracking the WG14 study group on provenance?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Have you attempted to put together some form of provenance semantics in a tool like Alive2 to more comprehensively catalogue miscompilations in existing optimizations?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">[1] My first instinct is to say that the BOOM is the set of allocations the pointer may point to, but there may be edge cases that I’m not immediately thinking of. Formal semantics is not my forte, after all.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>George Mitenkov via llvm-dev<br>
<b>Sent:</b> Friday, October 15, 2021 14:41<br>
<b>To:</b> llvm-dev <llvm-dev@lists.llvm.org>; cfe-dev@lists.llvm.org Developers <cfe-dev@lists.llvm.org><br>
<b>Subject:</b> [llvm-dev] Demystifying the byte type<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Hi all,<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">In May 2021, together with Nuno Lopes and Juneyoung Lee, we proposed to add a byte type in LLVM to fix load type punning issues. Initial RFC touched some subtle aspects of LLVM IR and its semantics, and sparked a lot of questions, concerns, and
discussions.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">We decided to write a post that would summarise the thread and the complicated topic:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><a href="https://gist.github.com/georgemitenkov/3def898b8845c2cc161bd216cbbdb81f">https://gist.github.com/georgemitenkov/3def898b8845c2cc161bd216cbbdb81f</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">We hope that our post clarifies initial concerns raised on the mailing list. As always, any questions, suggestions and advice are welcome!<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">George<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>