<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: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:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
code
{mso-style-priority:99;
font-family:"Courier New";}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle20
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1453087775;
mso-list-type:hybrid;
mso-list-template-ids:-428561826 -1851627850 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:-;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:20.25pt;
text-indent:-18.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:"Times New Roman";}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:56.25pt;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:92.25pt;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:128.25pt;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:164.25pt;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:200.25pt;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:236.25pt;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:272.25pt;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:308.25pt;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></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>Let me try to explain the issue around typed memory. It<span style='font-family:"Times New Roman",serif'>’</span>s orthogonal to TBAA. Plus I agree the allocation type is irrelevant; it<span style='font-family:"Times New Roman",serif'>’</span>s the type of the load/store operations that matters.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Fact 1: LLVM needs an <span style='font-family:"Times New Roman",serif'>“</span>universal holder<span style='font-family:"Times New Roman",serif'>”</span> type in its IR.<o:p></o:p></p><p class=MsoNormal>Why?<o:p></o:p></p><ul style='margin-top:0cm' type=disc><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'>Frontends load data from memory and don<span style='font-family:"Times New Roman",serif'>’</span>t necessarily know the type they are loading. When you load a char in C, it can be part of a pointer or an integer, for example. Clang has no way to know.<o:p></o:p></li><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'>That<span style='font-family:"Times New Roman",serif'>’</span>s necessary to express implementations of memcpy in IR, as it copies raw data without knowing what the type is.<o:p></o:p></li><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'>LLVM lowers small memcpys into load/store.<o:p></o:p></li></ul><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I hope you agree LLVM needs a type that can contain any other type.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Fact 2: optimizations for this <span style='font-family:"Times New Roman",serif'>“</span>universal holder<span style='font-family:"Times New Roman",serif'>”</span> type need to be correct for any LLVM IR type.<o:p></o:p></p><p class=MsoNormal>Since this type can hold anything, optimizations that apply to this type must be correct for integers, pointers, etc. Otherwise, the results would be incorrect if the data was cast to the <span style='font-family:"Times New Roman",serif'>“</span>wrong<span style='font-family:"Times New Roman",serif'>”</span> type.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>The corollary of this fact is that GVN is not correct for the <span style='font-family:"Times New Roman",serif'>“</span>universal holder<span style='font-family:"Times New Roman",serif'>”</span> type in general. That<span style='font-family:"Times New Roman",serif'>’</span>s because GVN is not correct for pointers in general (though correct in some cases). GVN doesn<span style='font-family:"Times New Roman",serif'>’</span>t work for pointers since just because 2 pointers compare equal, it doesn<span style='font-family:"Times New Roman",serif'>’</span>t mean they have the same provenance. As LLVM<span style='font-family:"Times New Roman",serif'>’</span>s AA uses provenance information, this information must be preserved.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Hopefully you agree with everything I wrote so far. If not please stop me and ask.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Ok, so what<span style='font-family:"Times New Roman",serif'>’</span>s the solution?<o:p></o:p></p><p class=MsoNormal>We have two candidates for this <span style='font-family:"Times New Roman",serif'>“</span>universal holder<span style='font-family:"Times New Roman",serif'>”</span> type:<o:p></o:p></p><ul style='margin-top:0cm' type=disc><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'>integer (i<i><x></i>)<o:p></o:p></li><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'>byte (b<i><x></i>), a new dedicated type<o:p></o:p></li></ul><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>The advantage of going with integers is that they already exist. The disadvantage? To make LLVM correct, we would need to disable GVN in most cases or stop using provenance information in AA (make pointers == integers).<o:p></o:p></p><p class=MsoNormal>This sounds pretty bad to me due to the expect performance hit.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Introducing a new type requires work, yes. But it allows us to keep all integer optimizations as aggressive as we want, and only throttle down when encountering the byte type. Another benefit is that loading a byte from memory doesn<span style='font-family:"Times New Roman",serif'>’</span>t escape any pointer, while with the first solution you need to consider all stored pointers as escaped when loading an integer.<o:p></o:p></p><p class=MsoNormal>Introducing the byte type allow us to fix all the integer/pointer casts bugs in LLVM IR. And it enables more optimizations as we won<span style='font-family:"Times New Roman",serif'>’</span>t need to be careful because of the LLVM IR bug.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>A 3<sup>rd</sup> option is to keep everything as-is. That is, keep wrong optimizations in LLVM and keep adding hacks to limit the miscompilations in real-world programs.<o:p></o:p></p><p class=MsoNormal>That has bitten us multiple times. Last time someone told me my miscompilation example was academic, LLVM ended up miscompiling itself, and then miscompiled Google<span style='font-family:"Times New Roman",serif'>’</span>s code. Only this year we are planning to fully fix that bug (we have a hack right now).<o:p></o:p></p><p class=MsoNormal>Last week Alive2 caught a miscompilation in the Linux kernel, in the network stack. The optimization got the pointer arithmetic wrong. Pretty scary, and the bug may have security implications.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Anyway, just to argue that leaving things as-is is not an option. We have momentum and 3 GSoC students ready to help to fix the last few design bugs in LLVM IR.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I know this stuff is complex; please ask questions if something is not clear or if you disagree with anything I wrote above.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Thanks,<o:p></o:p></p><p class=MsoNormal>Nuno<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><div><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm'><p class=MsoNormal><b>From:</b> Chris Lattner via llvm-dev<br><b>Sent:</b> 06 June 2021 05:27<br><b>To:</b> John McCall <rjmccall@apple.com><br><b>Cc:</b> llvm-dev@lists.llvm.org; Ralf Jung <jung@mpi-sws.org>; cfe-dev@lists.llvm.org<br><b>Subject:</b> Re: [llvm-dev] [cfe-dev] [RFC] Introducing a byte type to LLVM<o:p></o:p></p></div></div><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>On Jun 4, 2021, at 11:25 AM, John McCall via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>> wrote:<span style='font-family:"Arial",sans-serif'>On 4 Jun 2021, at 11:24, George Mitenkov wrote:</span><o:p></o:p></p><div><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><div><div><div><div><blockquote style='border:none;border-left:solid #3983C4 1.5pt;padding:0cm 0cm 0cm 4.0pt;margin-left:0cm;margin-right:0cm;margin-bottom:3.75pt'><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Arial",sans-serif;color:#3983C4'>Hi all,<br><br>Together with Nuno Lopes and Juneyoung Lee we propose to add a new byte<br>type to LLVM to fix miscompilations due to load type punning. Please see<br>the proposal below. It would be great to hear the<br>feedback/comments/suggestions!<br><br><br>Motivation<br>==========<br><br>char and unsigned char are considered to be universal holders in C. They<br>can access raw memory and are used to implement memcpy. i8 is the LLVM’s<br>counterpart but it does not have such semantics, which is also not<br>desirable as it would disable many optimizations.<o:p></o:p></span></p></blockquote></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Arial",sans-serif'>I don’t believe this is correct. LLVM does not have an innate<br>concept of typed memory. The type of a global or local allocation<br>is just a roundabout way of giving it a size and default alignment,<br>and similarly the type of a load or store just determines the width<br>and default alignment of the access. There are no restrictions on<br>what types can be used to load or store from certain objects.<o:p></o:p></span></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Arial",sans-serif'>C-style type aliasing restrictions are imposed using </span><code><span style='font-size:10.0pt'>tbaa</span></code><span style='font-family:"Arial",sans-serif'><br>metadata, which are unrelated to the IR type of the access.<o:p></o:p></span></p></div></div></div></div></blockquote></div><div><p class=MsoNormal>I completely agree with John. “i8” in LLVM doesn’t carry any implications about aliasing (in fact, LLVM pointers are going towards being typeless). Any such thing occurs at the accesses, and are part of TBAA.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>I’m opposed to adding a byte type to LLVM, as such semantic carrying types are entirely unprecedented, and would add tremendous complexity to the entire system.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>-Chris<o:p></o:p></p></div></div></body></html>