<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: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: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;}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle18
{mso-style-type:personal-compose;
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:1626958256;
mso-list-type:hybrid;
mso-list-template-ids:134395586 -2069229870 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;
mso-fareast-font-family:Calibri;
mso-bidi-font-family:Arial;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1
{mso-list-id:1804034469;
mso-list-type:hybrid;
mso-list-template-ids:-330038080 -1878911018 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l1:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:12.0pt;
font-family:Wingdings;
mso-fareast-font-family:Calibri;
mso-bidi-font-family:"Times New Roman";
color:windowtext;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
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;color:#1F497D">Hi Sanjay,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hi Hal,<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"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Question about:<o:p></o:p></span></a></p>
<p class="MsoNormal">>… and canonicalize toward bool math in the DAG. I don't know of any target that does better lowering the select variants.<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">What about recognition of idioms that may be considered to be naturally composed of ‘select’ operations such as: min/max/saturate/clamp. Will this change impact
the target’s ability (or make it more difficult) to recognize these idioms?<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">Thanks, Zvi<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"><a name="_____replyseparator"></a><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"> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Sanjay Patel via llvm-dev<br>
<b>Sent:</b> Thursday, September 29, 2016 19:20<br>
<b>To:</b> Sanjoy Das <sanjoy@playingwithpointers.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [llvm-dev] IR canonicalization: select or bool math?<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">I hadn't thought about the no-wrap consequences. That does seem like a good argument to always favor select since propagating nsw/nuw correctly is a weak point as I understand it. It would also make the instcombine
behavior more consistent despite the fact that, as Chris points out, zext/sext are acknowledged as simpler ops.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Sadly (for me anyway since I want to clean this up!) this means, as Hal noted: in general we want to canonicalize toward select in IR, and canonicalize toward bool math in the DAG. I don't know of any target
that does better lowering the select variants. In some cases today, we even create control flow where there was none in the original code when we transform bool math into select in IR. Prejudiced by that knowledge, I've been enhancing IR transforms that effectively
assume that 2 cheap IR ops (ext+add/sub) are more canonical than 1 select.<o:p></o:p></p>
</div>
<p class="MsoNormal">So a proposal to move this forward:<br>
1. Add DAG combines (possibly with TLI hooks) to turn selects into bool math. This will be a translation of existing IR select instcombines + new transforms. We ca<span style="color:#1F497D">dc</span>n't knowingly create IR patterns that the backend is not
prepped to handle.<o:p></o:p></p>
</div>
<p class="MsoNormal">2. Remove existing IR instcombines that remove selects in favor of bool math.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt">3. Add IR instcombines to transform bool math into selects.<o:p></o:p></p>
</div>
<p class="MsoNormal">Here are the quiz answers based on current trunk - if you did actually try to compile the code, sorry about all of the typos that made that impossible! :<o:p></o:p></p>
</div>
<p class="MsoNormal">#1 - 4 are canonicalized to bool math. Ie, we don't care about the relative cost of sext vs. zext or if the transform needs an extra instruction (the 'not') for these cases.<o:p></o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">#5 is canonicalized to select.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#6 is not canonicalized either way; 5/6 were introduced together as you might expect, but 6 was backed out due to lousy codegen!<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#7 is not canonicalized either way; too rare to care about?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#8 is not canonicalized either way; this one is fun because it exists in the instcombine source code itself - and we do a lousy job with it.<o:p></o:p></p>
</div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Wed, Sep 28, 2016 at 11:12 PM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</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">
<p class="MsoNormal">My gut tells me that Hal is right, and we should prefer zexts as long<br>
as the select boils down to one instruction, but let me go against my<br>
intuition and try to list two reasons why we should prefer selects:<br>
<br>
* Folding operations into selects: it is trivial to transform<br>
f(select X, Const0, Const1) to select X, f(Const0), f(Const1),<br>
while doing that can be difficult for zexts.<br>
<br>
define i32 @sel_1_or_0(i1 %a) {<br>
%b = select i1 %a, i32 1, i32 0<br>
%k = add i32 %b, 50<br>
ret i32 %k<br>
}<br>
<br>
==><br>
<br>
define i32 @sel_1_or_0(i1 %a) {<br>
%b = select i1 %a, i32 51, i32 50<br>
ret i32 %b<br>
}<br>
<br>
but<br>
<br>
define i32 @sel_1_or_0(i1 %a) {<br>
%b = zext i1 %a to i32<br>
%k = add i32 %b, 50<br>
ret i32 %k<br>
}<br>
<br>
is not as natural to transform.<br>
<br>
* zexts (resp. sexts) lose information when combined with nuw<br>
(resp. nsw) operations.<br>
<br>
That is, if we inline<br>
<br>
define i32 @sel_1_or_0(i1 %a) {<br>
%b = zext i1 %a to i32<br>
ret i32 %b<br>
}<br>
<br>
into f and get<br>
<br>
define i32 @f(i32 %x, i32 %y) {<br>
%x.zext = ...<br>
%y.zext = ...<br>
;; There are some existing use of %x.zext and %y.zext<br>
%a = add nuw i1 %x, %y<br>
%b = zext i1 %a to i32<br>
ret i32 %b<br>
}<br>
<br>
then we'll get (following your instructions, I've not verified that<br>
this actually happens :) )<br>
<br>
define i32 @f(i1 %x, i1 %y) {<br>
%x.zext = ...<br>
%y.zext = ...<br>
%a = add nuw i32 %x.zext, %y.zext<br>
ret i32 %a<br>
}<br>
<br>
but we've now lost information -- we no longer know that %a is 0 or<br>
1 -- it can also be 2. This would not happen if we always<br>
canonicalized zext i1 C to iN to select C, iN 1, iN 0<span style="color:#888888"><br>
<br>
-- Sanjoy</span><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</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>