<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)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@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: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;}
p
{mso-style-priority:99;
margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hal,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> To simplify this discussion, lets first just focus on code without asserts and assumes,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I don’t follow your logic, you seem to be implying we don’t optimize property-propagation through “if-then” and “while-do” well ?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">--Peter.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Hal Finkel [mailto:hfinkel@anl.gov]
<br>
<b>Sent:</b> Tuesday, June 14, 2016 11:12 AM<br>
<b>To:</b> Lawrence, Peter <c_plawre@qca.qualcomm.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org; Daniel Berlin <dberlin@dberlin.org><br>
<b>Subject:</b> Re: [llvm-dev] Early CSE clobbering llvm.assume<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black">
<hr size="2" width="100%" align="center" id="zwchr">
</span></div>
<blockquote style="border:none;border-left:solid #1010FF 1.5pt;padding:0in 0in 0in 4.0pt;margin-left:3.75pt;margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-bottom:12.0pt"><b><span style="font-family:"Helvetica",sans-serif;color:black">From:
</span></b><span style="font-family:"Helvetica",sans-serif;color:black">"Daniel Berlin via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>To: </b>"Peter Lawrence" <<a href="mailto:c_plawre@qca.qualcomm.com">c_plawre@qca.qualcomm.com</a>><br>
<b>Cc: </b><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Sent: </b>Tuesday, June 14, 2016 12:45:50 PM<br>
<b>Subject: </b>Re: [llvm-dev] Early CSE clobbering llvm.assume<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
<div id="DWT2444">
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">On Tue, Jun 14, 2016 at 10:36 AM, Lawrence, Peter <<a href="mailto:c_plawre@qca.qualcomm.com" target="_blank">c_plawre@qca.qualcomm.com</a>> wrote:<o:p></o:p></span></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Daniel,</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> What am I missing in the following chain of logic:</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">As far as constant-prop, value-prop, range-prop, and general property-propagation,</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">1. the compiler/optimizer *<b>has</b>* to get it right for if-then-else and while-do or else we should
all start over </span><span style="font-size:11.0pt;font-family:Wingdings;color:#1F497D">J</span><span style="color:black"><o:p></o:p></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">Only certain parts of the compiler know how to do this.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">This is precisely one of the reasons i'm proposing we've gotten it wrong.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"> <o:p></o:p></span></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">2. “assert” takes advantage of this by being translated into if-then logic early on in the compilation</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">3. “assume” should also take advantage of this the same way. (generate a call to “pseudoabort” which</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">At some late stage gets deleted)</span><span style="color:black"><o:p></o:p></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">This would fix precisely nothing, because of the above.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"> <o:p></o:p></span></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Sanjoy’s argument is faulty, if it were true we would also find our handling of “assert” to be unacceptable</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">but this is not the case, no one is arguing that we need to re-design “assert”</span><span style="color:black"><o:p></o:p></span></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black">Sure, but no one should make this argument anyway: assert is not for optimization. In fact, we don't really want it to be used for optimization, because if we do,
then we might end up in a situation where the -DNDEBUG build generates worse code than the build with asserts enabled.<br>
<br>
Also, I'll note that the reason that assume is an intrinsic, instead of a branch around unreachable, is that we aggressively remove branches around unreachable as part of our canonicalization process. We do this in order to simplify code, and this is important
in order to remove abstraction penalties. Note that unreachables are also generated from undefined behavior, and one of the ways we use undefined behavior is to assume it is unreachable, enabling us to eliminate what should be dead code. This is an important
technique for limiting abstraction penalties from, for example, heavily templated C++ code.<br>
<br>
Thus, somewhat unfortunately, Sanjoy's argument is not faulty. <o:p></o:p></span></p>
<blockquote style="border:none;border-left:solid #1010FF 1.5pt;padding:0in 0in 0in 4.0pt;margin-left:3.75pt;margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">Asserts occur much more often than assumes, it may or may not be sensible to handle them the same way.<o:p></o:p></span></p>
</div>
<div id="DWT1315">
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">I would argue it is sensible, but it's also reasonable to argue it is not.<o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</blockquote>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black">We need to be careful what we mean by "in the same way". For clarify, I'll note that:<br>
<br>
1. assert is defined to be a macro that does not result in semantically-analyzable code when NDEBUG is defined. We cannot elide this, it how the feature is defined. The body of the assert might not even be parsable code when NDEBUG is defined. It might, for
example, refer to variables that are only declared when NDEBUG is not defined.<br>
<br>
2. Even saying that we'd get around this by ignoring parsing errors within the assert when NDEBUG is defined, but otherwise assuming the result is not desirable. There are large bodies of code which do this;<br>
<br>
assert(i > 5);<br>
if (i <= 5) throw a_strange_error();<br>
<br>
so that, in production builds, the program does not crash, but instead unwinds. There are all sorts of reasons we can use to argue this is a bad coding practice, and I personally agree, but that does not change the fact that braking this idiom is not something
we should do.<br>
<br>
The contracts features being discussed for future versions of the C++ standard should be better in this regard.<br>
<br>
We can certainly improve the representations of assumes, perhaps as Danny has suggested by converting their control dependencies into extended SSA token vales, and better capture knowledge from conditional branches, but the tradeoffs here are not trivial.<br>
<br>
-Hal<o:p></o:p></span></p>
<blockquote style="border:none;border-left:solid #1010FF 1.5pt;padding:0in 0in 0in 4.0pt;margin-left:3.75pt;margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">I would also argue our current way of propagating information for if-then conditions is in fact, quite crappy. Only a small number of passes know how to do it, and they do it
either by ad-hoc analysis (GVN) or very expensive methods (LVI).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"> <o:p></o:p></span></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">And any argument you can make about needing to handle “assume” conditions in some special way can be</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Turned around and applied to “if-then” conditions, but again no one is arguing that we need to re-design
“if-then”</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Information propagation.</span><span style="color:black"><o:p></o:p></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">I would argue we do, in fact need to do that.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">That said, it is a larger longer term change.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">Fixing assume is a good start on that, and by fixing assume, we can prove out whether a new model will work well and expand it.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">If we start by trying to fix the general propagation problem, that's a huge job to start, and if we get it wrong, a lot larger to fix.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black">Better to start small and go from there.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><span style="font-family:"Helvetica",sans-serif;color:black"><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black"><br>
<br>
<br>
-- <o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:black">Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<o:p></o:p></span></p>
</div>
</div>
</div>
</body>
</html>