<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=us-ascii">
<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;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
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;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@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:999697856;
mso-list-type:hybrid;
mso-list-template-ids:1757947150 -317790244 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:%1-;
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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">Hello,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I recently observed a curious interaction between the code generated by Clang and the optimizations that OPT is capable of performing, so I’d appreciate if anyone could shed some light into the rationale for this decision in code generation.
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">When we have code like:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">int foo(int idx) {<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> int array[10] = {1,2,3,4,5,6};<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> return array[idx];<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Clang generates a memset to 0, followed by 6 stores (pattern A). Abridged version:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">define i32 @_Z3fooi(i32 %idx) #0 {<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">entry:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %array = alloca [10 x i32], align 16<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 %idx, i32* %idx.addr, align 4, !tbaa !2<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %1 = bitcast [10 x i32]* %array to i8*<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> call void @llvm.memset.p0i8.i64(i8* %1, i8 0, i64 40, i32 16, i1 false)<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %2 = bitcast i8* %1 to [10 x i32]*<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %3 = getelementptr [10 x i32], [10 x i32]* %2, i32 0, i32 0<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 1, i32* %3<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">[…]<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Now, if we add one extra element to the array (notice that the size of the array is still 10), we get a memcpy from a constant internal global (pattern B). Abridged version:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">int foo(int idx) {<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> int array[10] = {1,2,3,4,5,6, 7};<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> return array[idx];<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">@_ZZ3fooiE5array = private unnamed_addr constant [10 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 0, i32 0, i32 0], align 16<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">define i32 @_Z3fooi(i32 %idx) #0 {<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">entry:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %idx.addr = alloca i32, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %array = alloca [10 x i32], align 16<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 %idx, i32* %idx.addr, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %0 = bitcast [10 x i32]* %array to i8*<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast ([10 x i32]* @_ZZ3fooiE5array to i8*), i64 40, i32 16, i1 false)<o:p></o:p></p>
<p class="MsoNormal"> […]<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">OPT with –O3 on pattern B is able to transform uses of the alloca with uses of the constant global. In particular, the InstructionCombining pass has code to pattern match an alloca followed by a memcpy followed by reads, transforming them
into reads from the global constant array and removing the alloca altogether. On pattern A, on the other hand, OPT can’t do anything, and the code stays pretty much untouched. (note that adding a const to the array would make the whole issue go away, but
for the purposes of this discussion, let’s ignore it)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The decision on which pattern to use is made by lib/CodeGen/CGDecl.cpp::shouldUseMemSetToInitialize but the comments there weren’t very enlightning.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Any insight on this, examples where pattern A is better or maybe suggestions for a different heuristic would be appreciated. This might be a case for improving OPT, but I’d like to hear from the Clang side too.<o:p></o:p></p>
<p class="MsoNormal">Recently, rC337887 added a few extra possibilities to this, by considering a memset to values != 0, but it doesn’t address the problem presented here.<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">--<o:p></o:p></p>
<p class="MsoNormal">Felipe de Azevedo Piovezan<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>