<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 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Arial","sans-serif";
color:#1F497D;}
.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;}
--></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">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Courier New"">define void @f(float* %value, i8* %b) {</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">entry:</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %0 = load float* %value, align 4</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %1 = bitcast i8* %b to float*</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> store float %0, float* %1, align 1</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> ret void</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">define void @g(float* %value, i8* %b) {</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">entry:</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %0 = bitcast float* %value to i32*</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %1 = load i32* %0, align 4</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %2 = bitcast i8* %b to i32*</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> store i32 %1, i32* %2, align 1</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> ret void</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">I don’t think these are equivalent representations. The one with the float loads and stores has the potential of FP exceptions<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">both during the load and during the store, depending on what exact instruction set is in use. For example, floating point loads when done with x87, aren’t even
guaranteed of giving the same bit pattern when using due to signaling Nans potentially being converted into quiet Nans by the fld instruction.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">Thus, I don’t think this is an example of a missing canonicalization, nor even a legal one in all circumstances. But maybe there is a subtlety of LLVM IR semantics
that I am unaware of.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">Kevin B. Smith<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu]
<b>On Behalf Of </b>Chandler Carruth<br>
<b>Sent:</b> Wednesday, January 21, 2015 2:17 PM<br>
<b>To:</b> LLVM Developers Mailing List<br>
<b>Subject:</b> [LLVMdev] RFC: Missing canonicalization in LLVM<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">So, we've run into some test cases which are pretty alarming.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">When inlining code in various different paths we can end up with this IR:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">define void @f(float* %value, i8* %b) {</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">entry:</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> %0 = load float* %value, align 4</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> %1 = bitcast i8* %b to float*</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> store float %0, float* %1, align 1</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> ret void</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">}</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">define void @g(float* %value, i8* %b) {</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">entry:</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> %0 = bitcast float* %value to i32*</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> %1 = load i32* %0, align 4</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> %2 = bitcast i8* %b to i32*</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> store i32 %1, i32* %2, align 1</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> ret void</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">}</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<div>
<p class="MsoNormal">Now, I don't really care one way or the other about these two IR inputs, but it's pretty concerning that we get these two equivalent bits of code and nothing canonicalizes to one or the other.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">So, the naive first blush approach here would be to canonicalize on the first -- it has fewer instructions after all -- but I don't think that's the right approach for two reasons:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">1) It will be a *very* narrow canonicalization that only works with overly specific sets of casted pointers.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">2) It doesn't effectively move us toward the optimizer treating IR with different pointee types for pointer types indistinguishably. Some day, I continue to think we should get rid of the pointee types entirely.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">To see why #1 and #2 are problematic, assume another round of inlining took place and we suddenly had the following IR:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">AFAICT, this is the same and we still don't have a good canonicalization story.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">What seems like the obvious important and missing canonicalization is that when we have a loaded value that is *only* used by storing it back into memory, we don't canonicalize the type of that *value* (ignoring the pointer types) to a
single value type.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">So, the only really suitable type for this kind of stuff is 'iN' where N matches the number of bits loaded or stored.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I have this change implemented. It is trivial and unsurprising. However, the effects of this are impossible to predict so I wanted to make sure it made sense to others. Essentially, I expect random and hard to track down performance fluctuations
across the board. Some things may get better, others may get worse, and they will probably all be bugs elsewhere in the stack.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">So, thoughts?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">-Chandler<o:p></o:p></p>
</div>
</div>
</div>
</body>
</html>