<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:"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;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"Segoe UI Symbol";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
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.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;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.m-6971828876095942576msoplaintext, li.m-6971828876095942576msoplaintext, div.m-6971828876095942576msoplaintext
{mso-style-name:m_-6971828876095942576msoplaintext;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.hoenzb
{mso-style-name:hoenzb;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@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:235675324;
mso-list-type:hybrid;
mso-list-template-ids:-367128988 -882855820 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;
margin-left:20.25pt;
text-indent:-18.0pt;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:56.25pt;
text-indent:-18.0pt;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:92.25pt;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:128.25pt;
text-indent:-18.0pt;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:164.25pt;
text-indent:-18.0pt;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:200.25pt;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:236.25pt;
text-indent:-18.0pt;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:272.25pt;
text-indent:-18.0pt;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:308.25pt;
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><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Regarding the patches, there are two concerns AFAICT:<o:p></o:p></span></p><ol style='margin-top:0cm' start=1 type=1><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>It</span><span style='font-size:11.0pt'>’</span><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>s a new instruction and as usual when introducing a new instruction it will require work for some time until most optimizations know about it, and to get rid of any potential perf regression. No big deal; we just need to do the work (and we have already done some of it).<o:p></o:p></span></li><li class=MsoListParagraph style='margin-left:-15.75pt;mso-list:l0 level1 lfo1'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>The patch was written by a student, which may not have time to support it properly going forward. That means that someone needs to step in and take ownership. Of course we will be here to help, but none of us at the moment can commit to own this. The blog post that John mentioned below describes our machinery to find bugs in optimizations and in new semantics, and we will put it to use to test LLVM periodically.<o:p></o:p></span></li></ol><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>On the plus side, freeze can helps us get rid of a bunch of miscompilations, which no one enjoys.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>The usage of freeze can be incremental; we can try out with a few things to see how it goes. We have more radical ideas down the road, like replace undef with poison, but one thing at a time :)<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Regarding SDAG, and given that poison is already there, we would need to adopt a similar solution to the IR. Maybe right now we can get away with it because nsw is not exploited significantly (as you say). Just because there</span><span style='font-size:11.0pt'>’</span><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>s no explicit poison in SDAG, just having nsw is sufficient to cause miscompilations when combined with other transformations.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>See, for example, this bug report for InstCombine regarding select+nsw: <a href="https://bugs.llvm.org/show_bug.cgi?id=31633">https://bugs.llvm.org/show_bug.cgi?id=31633</a><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Nuno<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'><o:p> </o:p></span></p><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'> Sanjay Patel [mailto:spatel@rotateright.com] <br><b>Sent:</b> 23 de maio de 2017 14:25<br><b>To:</b> Nuno Lopes <nuno.lopes@ist.utl.pt><br><b>Cc:</b> John Regehr <regehr@cs.utah.edu>; llvm-dev <llvm-dev@lists.llvm.org>; Matthias Braun <mbraun@apple.com>; Sanjoy Das <sanjoy@playingwithpointers.com>; David Majnemer <david.majnemer@gmail.com>; Hal Finkel <hfinkel@anl.gov>; Friedman, Eli <efriedma@codeaurora.org><br><b>Subject:</b> Re: [poison] is select-of-select to logic+select allowed?<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><div><div><div><div><p class=MsoNormal style='margin-bottom:12.0pt'>The examples and table are great! That at least makes it clear what we need to think about and fix (and just how complex the problem is). <br><br>Are there known limitations/objections to the freeze instruction patches that John listed? Or are we just being cautious and/or waiting for more people to review those?<o:p></o:p></p></div><p class=MsoNormal>I can answer some of the DAG questions: <br>(a) Yes, we have nsw/nuw/exact down there. They've been around since: <a href="https://reviews.llvm.org/rL210467">https://reviews.llvm.org/rL210467</a> .<o:p></o:p></p></div><p class=MsoNormal>(b) Yes, we use those bits to enable transforms, but it's not nearly as common as in IR. It's also likely that we'll drop those bits during transforms.<o:p></o:p></p></div><p class=MsoNormal>(c) Yes, we do all kinds of select transforms without regard for poison.<o:p></o:p></p></div><p class=MsoNormal>(d) AFAIK, there is no accounting for poison in the DAG for any transforms, but it's possible that I just didn't find it in the source.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Tue, May 23, 2017 at 4:16 AM, Nuno Lopes <<a href="mailto:nuno.lopes@ist.utl.pt" target="_blank">nuno.lopes@ist.utl.pt</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><p class=m-6971828876095942576msoplaintext>Hi,<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Let me try to give a bit more context on why select is so tricky.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>First thing to consider is which transformations we would like to support:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext><u>1) Control-flow -> select (SimplifyCFG)</u><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>if (c)</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>a = x</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>else</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>a = y</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'> </span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'> =></span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%a = select %c, %x, %y</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext><u>2) select -> control-flow</u>; reverse of 1)<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Not sure if this is done at IR level, or only later at SDAG.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext><u>3) select -> arithmetic</u><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%a = select %c, true, %y</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'> =></span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%a = or %c, %y</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext><u>4) select removal</u><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%c = icmp eq %x, C</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%r = select %c, C, %x</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'> =></span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%r = %x</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span lang=PT> </span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span lang=PT> </span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><u><span lang=PT>5) select hoisting past binops</span></u><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%a = udiv %x, %y</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%b = udiv %x, %z</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%r = select %c, %a, %b</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'> =></span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%t = select %c, %y, %z</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='font-size:10.0pt;font-family:Consolas'>%r = udiv %x, %t</span><o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext><u>6) Bonus: easy to move</u> select instructions around. Should be possible to hoist selects out of loops easily.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Ideally we want semantics for select that allow all transformations 1-6. It's hard because:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>1) %a can only be poison conditionally on %c, i.e., %a is poison if %c=true and %x is poison, or %c=false and %y is poison<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>2) since we introduce a branch on %c, select on poison has to be UB like branch on poison<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>3) with arithmetic all operands are always evaluated, so conditional poison like in 1) doesn’t work<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>4) the example provided replaces C with %x in case %x=C. C is never poison, but %x might be.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>5) We cannot introduce a division by poison if %y and %z are not poison<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>6) Making select trigger UB for some cases makes movement harder because then we need to prove that it won’t trigger UB before e.g. hoisting it out of loops.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Summary table of what each transformation allows for %z = select %c, %x, %y. Each column is a different alternative of semantics for select:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 style='border-collapse:collapse'><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border:solid windowtext 1.0pt;border-left:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>UB if %c poison<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>+ conditional poison<o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border:solid windowtext 1.0pt;border-left:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>UB if %c poison + poison if either<br>%x/%y poison<o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border:solid windowtext 1.0pt;border-left:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Conditional poison<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>+ non-det choice if %c poison<o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border:solid windowtext 1.0pt;border-left:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Conditional poison + poison if %c poison**<o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border:solid windowtext 1.0pt;border-left:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Poison if any of<br>%c/%x/%y are poison<o:p></o:p></p></td></tr><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;border-top:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>SimplifyCFG<o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td></tr><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;border-top:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Select->control-flow<o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td></tr><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;border-top:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Select->arithmetic<o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td></tr><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;border-top:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Select removal<o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td></tr><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;border-top:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Select hoist<o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td></tr><tr><td width=141 valign=top style='width:105.95pt;border:solid windowtext 1.0pt;border-top:none;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext>Easy movement<o:p></o:p></p></td><td width=108 valign=top style='width:81.05pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'> <o:p></o:p></p></td><td width=128 valign=top style='width:96.1pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=132 valign=top style='width:99.25pt;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td><td width=151 valign=top style='width:4.0cm;border-top:none;border-left:none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;padding:0cm 5.4pt 0cm 5.4pt'><p class=m-6971828876095942576msoplaintext align=center style='text-align:center'><span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span><o:p></o:p></p></td></tr></table><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Modulo bugs in the table, you can see there’s no single column with all rows with a <span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span>. That means there’s no way (that I’m aware of) to make all transformations that we are interested in doing to be correct. A solution is to introduce something like the freeze instruction that can land a <span style='font-family:"Segoe UI Symbol",sans-serif'>✓</span> on any cell you want.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>So unless someone has a clever idea and proposes a new column that has ticks in all rows, we are left with picking a trade-off: either we disable some optimizations, or we introduce something like freeze to continue doing them.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>BTW, this table assumes that branch on poison is UB, otherwise optimizations like GVN are wrong (for more details see our paper: <a href="http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf" target="_blank">http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf</a>). The column marked with ** is the one that Alive currently implements.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Regarding SDAG: it has undef, and I believe there was some discussion regarding introducing poison there as well. I don’t recall if it was introduce already, but I believe there’s already nsw/nuw there. If that’s the case, the (il)legality of transformations should be exactly the same as in LLVM IR. Otherwise some transformations may be easier.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Sorry for the longish email; just wanted to give some background about the problem so that we can reach some consensus at some point.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext><span style='color:#888888'> <o:p></o:p></span></p><p class=m-6971828876095942576msoplaintext><span style='color:#888888'>Nuno<o:p></o:p></span></p><div><div><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>-----Original Message-----<br>From: John Regehr<br>Sent: 22 de maio de 2017 21:45<br>Subject: Re: [poison] is select-of-select to logic+select allowed?<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Nuno and I have been looking through the results of experiments like the one reported here:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <a href="https://blog.regehr.org/archives/1510" target="_blank"><span style='color:windowtext;text-decoration:none'>https://blog.regehr.org/archives/1510</span></a><o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>Indeed there are some select-related transformations in LLVM that are illegal in terms of Alive's semantics. As far as we know, they cannot be made legal (by adjusting the semantics of instructions) without breaking a bunch of other optimizations.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>The optimizations currently in LLVM are not only inconsistent but they can lead to end-to-end miscompilations. Sorting this out is going to require (1) figuring out what select means WRT poison/undef and (2) backing out some optimizations. This is going to be slightly painful but it is the only way forward.<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>John<o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>On 5/22/17 2:32 PM, Sanjay Patel wrote:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> Some InstCombine transforms for select-of-select were added here:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> <a href="https://reviews.llvm.org/rL228409" target="_blank"><span style='color:windowtext;text-decoration:none'>https://reviews.llvm.org/rL228409</span></a><o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> But Alive says this is more poisonous:<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> Name: selsel<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> %s1 = select i1 %cond1, i8 C1, i8 C2<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> %s2 = select i1 %cond2, i8 %s1, i8 C2<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> =><o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> %andcond = and i1 %cond1, %cond2<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> %s2 = select i1 %andcond, i8 C1, i8 C2<o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> <a href="http://rise4fun.com/Alive/JT6" target="_blank"><span style='color:windowtext;text-decoration:none'>http://rise4fun.com/Alive/JT6</span></a><o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> <o:p></o:p></p><p class=m-6971828876095942576msoplaintext>> Are those transforms legal?<o:p></o:p></p></div></div></div></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>