<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 14 (filtered medium)">
<style><!--
/* Font Definitions */
@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;
margin-bottom:.0001pt;
line-height:115%;
font-size:11.0pt;
font-family:"Calibri","sans-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;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
line-height:115%;
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;
font-family:"Calibri","sans-serif";}
.MsoPapDefault
{mso-style-type:export-only;
line-height:115%;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1096630430;
mso-list-type:hybrid;
mso-list-template-ids:257578110 67698705 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:-18.0pt;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@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:-18.0pt;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@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:-18.0pt;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:1890725956;
mso-list-type:hybrid;
mso-list-template-ids:279710134 -693890256 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-number-format:alpha-lower;
mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ascii-font-family:Calibri;
mso-fareast-font-family:Calibri;
mso-hansi-font-family:Calibri;
mso-bidi-font-family:Arial;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
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">
<div class="WordSection1">
<p class="MsoNormal">Hello,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Chris requested I start a fresh discussion on this, so, here goes. The previous iterations can be found here (and in follow-ups):<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130722/182590.html">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130722/182590.html</a><o:p></o:p></p>
<p class="MsoNormal"><a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-July/064047.html">http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-July/064047.html</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Cutting to the chase, the goal is to enhance llvm::isSafeToSpeculativelyExecute() to support call instructions.
<o:p></o:p></p>
<p class="MsoNormal">isSafeToSpeculativelyExecute() is a query that, basically, determines whether it is safe to move an instruction that is executed conditionally into an unconditional context. One common use-case is hoisting loop-invariant instructions out
of loops, during loop-invariant code motion.<o:p></o:p></p>
<p class="MsoNormal">For example:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int foo(int a, int b, int n)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int sum = 0;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> for(int i = 0; i < n; ++i)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> {<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int temp = a + b;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> sum += temp;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal">Can be transformed into:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int foo(int a, int b, int n)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int sum = 0;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int temp = a + b;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> for(int i = 0; i < n; ++i)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> {<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> sum += temp;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Because hoisting the addition is safe.</p>
<p class="MsoNormal">However, code that looks like this is more problematic:<o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int bar(int a);<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int foo(int n)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int sum = 0;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> for(int i = 0; i < n; ++i)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> {<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int temp = bar(n);<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> sum += temp;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">May not, in general, be transformed into<o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int foo_bad(int n)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int sum = 0;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> int temp = bar(n);<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> for(int i = 0; i < n; ++i)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> {<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> sum += temp;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The first issue is that bar() may have side effects, in which case this transformation is clearly unsafe.
<o:p></o:p></p>
<p class="MsoNormal">Unfortunately, even if bar() is marked “readnone, nounwind”, this is still not a safe transformation. The problem is that the loop is not guaranteed to have even a single iteration, and even readnone functions may not always be safe to
call.<o:p></o:p></p>
<p class="MsoNormal">So, if bar() is defined like this:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int bar(int a)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> while(a != 0) {}<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> return a;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal">Then foo(0) is safe, but foo_bad(0) is an infinite loop.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Similarly, if bar() is defined as: <o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int bar(int a)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> return 1000 / a;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Then foo(0) is safe, but foo_bad(0) has undefined behavior.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Unfortunately, right now, there is no way to specify that a function call IS safe to execute under any circumstances. Because of this, llvm::isSafeToSpeculativelyExecute() simply returns false for all Call instructions, except calls to
some intrinsics which are special-cased, and are hard-coded into the function. <o:p>
</o:p></p>
<p class="MsoNormal">What I would like to see instead is a function attribute – or a set of function attributes – that would allow isSafeToSpeculativelyExecute() to infer that it may return “true” for a given function call.
<o:p></o:p></p>
<p class="MsoNormal">This has two main uses:<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo2"><![if !supportLists]><span style="mso-list:Ignore">1)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>Intrinsics, including target-dependent intrinsics, can be marked with this attribute – hopefully a lot of intrinsics that do not have explicit side effects and do not rely on global state that is not currently
modeled by “readnone” (e.g. rounding mode) will also not have any of the other issues.<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo2"><![if !supportLists]><span style="mso-list:Ignore">2)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>DSL Frontends (e.g. OpenCL, my specific domain) will be able to mark library functions they know are safe.<o:p></o:p></p>
<p class="MsoNormal">(The optimizer marking user functions as safe seems, to me, like a less likely case)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I see two ways to approach this:<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo1"><![if !supportLists]><span style="mso-list:Ignore">a)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>Define a new attribute that says, specifically, that a function is safe to execute speculatively (“speculatable”).<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo1"><![if !supportLists]><span style="mso-list:Ignore">b)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>Try to define a set of orthogonal attributes that, when all of them are specified, ensure speculative execution is safe, and then add the missing ones.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Option (b) sounds better in theory, but I find it problematic for two reasons – it’s not clear both what the precise requirements for safety are (right now, “I know it when I see it”, and I’m not sure I want to set it in stone), and what
the granularity of these orthogonal attributes should be. For example, {readnone, nounwind, halting, welldefined} sounds like a good start, but I’m not sure whether “welldefined” is not too much of a catch-all, or whether this set is, in fact, exhaustive.
So I’m more inclined towards (a).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m attaching a patch that implements option (a) (the same patch from llvm-commits), but feel free to tell me it’s rubbish. :-)<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"> Michael<o:p></o:p></p>
</div>
<p>---------------------------------------------------------------------<br>
Intel Israel (74) Limited</p>
<p>This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</p></body>
</html>