<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 4 Oct 2019, at 18:00, Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:</div></blockquote><blockquote type="cite" class=""><br class=""></blockquote><blockquote type="cite" class="">Why not? It seems like we could pattern match the shifts back into selects/branches?</blockquote><div><br class=""></div><div>I don’t think that reverse pattern matching is the optimal approach in all cases. I have tried and certainly for some simple cases the undesired shifts can be reverted into selects producing better code. However, this does not work well for complex patterns or cases where second transforms have been applied on top of it. </div><div><br class=""></div><div>One typical case is a sequence of ‘selects’ that depend on a single common condition. If one of these selects is combined into non-branching code, then the backend has a very hard work to track back the origin of that common condition. Therefore, for targets that convert all selects into branches, these two selects get almost inevitably converted into either two branching sequences, or one branch sequence followed or preceded by the non-branching code of the other select.</div><div><br class=""></div><div>Scenarios like this are not a problem for pipelined processors with expensive branches and ’select’ like instructions because in this case the effort is put in removing branches by the insertion of speculative code which is usually cheaper. However, for simple processors where branches must be used and are cheap, we often want to do the opposite because the execution of speculative code or particular transforms is comparatively most costly than just branching.</div><div><br class=""></div><div>Going back to the case, if these two selects arrived together to the backend, then they could be identified and folded into a block preceded by a single conditional branch, resulting in faster and shorter code. The latter is the purpose of some function in the CodeGen prepare pass, but this doesn’t fire because the two selects are not there to work with them to begin with. </div><div><br class=""></div><div>Finally, generally speaking, I don’t regard complex reverse pattern matching as an elegant solution, compared with providing the right LLVM hooks for the affected targets, because this is like acknowledging that these targets are inferior, or not worth the effort to improve LLVM code. Also, whatever the way I look at it, I always find that it’s better to solve problems by working on the root causes rather than trying to apply late patches or corrections, which generally make things convoluted and difficult to maintain, not to mention suboptimal.</div><div><br class=""></div>John<br class=""><blockquote type="cite" class=""><div class="">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" class="">
<div bgcolor="#FFFFFF" text="#000000" class=""><p class=""><br class="">
</p>
<div class="moz-cite-prefix">On 10/4/19 5:46 AM, Joan Lluch via llvm-dev wrote:<br class="">
</div>
<blockquote type="cite" cite="mid:01C51DE9-24BB-43EF-BADC-C2384AA4DBBD@icloud.com" class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space;
-webkit-line-break: after-white-space;" class="">
Hi all,
<div class=""><br class="">
</div>
<div class="">As a continuation of this thread, I was about to fill a bug report requesting the modification of <font class="" size="3"><span style="white-space: pre-wrap;" class="">DAGTypeLegalizer::ExpandIntRes_SIGN_EXTEND, in order to avoid the creation
of Shifts for targets with no native support. For example by generating a ‘select' equivalent to a<0 ? -1 : 0
</span></font>instead of an arithmetic shift right. For targets with no multiple shifts or word extension instructions, the select is much cheaper.</div>
<div class=""><br class="">
</div>
<div class="">However, I found that the early InstCombine pass spoils such optimisation by creating shifts on their own as a transform of (supposedly) equivalent code. </div>
<div class=""><br class="">
</div>
...
<div class="">
<div class=""><br class="">
</div>
<div class=""><span style="background-color: rgb(255, 255,
255);" class="">I strongly suggest the above gets fixed. HOWEVER, even after the DAG combiner is fixed, the issues will remain due to InstCombine doing essentially the same thing </span><span style="background-color: rgb(255, 255,
255);" class="">much
earlier. Consider code like this:</span></div>
<div class=""><span style="background-color: rgb(255, 255,
255);" class=""><br class="">
</span></div>
<div class="">
<div style="margin: 0px; font-size: 11px; line-height:
normal; font-family: Monaco; background-color: rgb(255,
255, 255);" class="">
<span style="color: rgb(186, 45,
162);" class="">int</span> test0( <span style="color:
rgb(186, 45, 162);" class="">int</span> a )</div>
<div style="margin: 0px; font-size: 11px; line-height:
normal; font-family: Monaco; background-color: rgb(255,
255, 255);" class="">
{</div>
<div style="margin: 0px; font-size: 11px; line-height:
normal; font-family: Monaco; background-color: rgb(255,
255, 255);" class="">
<span style="color: rgb(186, 45,
162);" class="">return</span> a<<span style="color:
rgb(39, 42, 216);" class="">0</span> ? -<span style="color: rgb(39, 42, 216);" class="">1</span> : <span style="color: rgb(39, 42, 216);" class="">0</span>;</div>
<div style="margin: 0px; font-size: 11px; line-height:
normal; font-family: Monaco; background-color: rgb(255,
255, 255);" class="">
}</div>
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal;
font-family: Monaco; background-color: rgb(255, 255, 255);" class="">
<br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal;
font-family: Monaco; background-color: rgb(255, 255, 255);" class="">
<div style="margin: 0px; line-height: normal;" class=""><span style="color: rgb(186, 45, 162);" class="">int</span> test1( <span style="color: rgb(186, 45, 162);" class="">int</span> a )</div>
<div style="margin: 0px; line-height: normal;" class="">{</div>
<div style="margin: 0px; line-height: normal;" class=""> <span style="color: rgb(186, 45, 162);" class="">return</span> a<<span style="color: rgb(39, 42, 216);" class="">0</span> ?
<span style="color: rgb(39, 42, 216);" class="">1</span> : <span style="color: rgb(39, 42, 216);" class="">0</span>;</div>
<div style="margin: 0px; line-height: normal;" class="">}</div>
<div style="margin: 0px; line-height: normal;" class=""><br class="">
</div>
<div style="margin: 0px; line-height: normal;" class="">
<div style="margin: 0px; line-height: normal;" class=""><span style="color: rgb(186, 45, 162);" class="">int</span> test2( <span style="color: rgb(186, 45, 162);" class="">int</span> a )</div>
<div style="margin: 0px; line-height: normal;" class="">{</div>
<div style="margin: 0px; line-height: normal;" class=""> <span style="color: rgb(186, 45, 162);" class="">return</span> a<<span style="color: rgb(39, 42, 216);" class="">0</span> ? <font class="" color="#272ad8">2</font> : <span style="color: rgb(39, 42, 216);" class="">0</span>;</div>
<div style="margin: 0px; line-height: normal;" class="">}</div>
<div style="margin: 0px; line-height: normal;" class=""><br class="">
</div>
<div style="margin: 0px; line-height: normal;" class="">
<div style="margin: 0px; line-height: normal;" class=""><span style="color: rgb(186, 45, 162);" class="">int</span> test3( <span style="color: rgb(186, 45, 162);" class="">int</span> a )</div>
<div style="margin: 0px; line-height: normal;" class="">{</div>
<div style="margin: 0px; line-height: normal;" class=""> <span style="color: rgb(186, 45, 162);" class="">return</span> a<<span style="color: rgb(39, 42, 216);" class="">0</span> ?
<font class="" color="#272ad8">3</font> : <span style="color: rgb(39, 42, 216);" class="">0</span>;</div>
<div style="margin: 0px; line-height: normal;" class="">}</div>
</div>
</div>
</div>
<div class=""><span style="background-color: rgb(255, 255,
255);" class=""><br class="">
</span></div>
<div class=""><span style="background-color: rgb(255, 255,
255);" class="">In all cases, InstCombine converts the above into Shifts, right into the IR, which the backend can’t do anything about.</span></div>
</div>
</div>
</blockquote><p class=""><br class="">
</p><p class="">Why not? It seems like we could pattern match the shifts back into selects/branches?</p><p class=""> -Hal<br class="">
</p><p class=""><br class="">
</p>
<blockquote type="cite" cite="mid:01C51DE9-24BB-43EF-BADC-C2384AA4DBBD@icloud.com" class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space;
-webkit-line-break: after-white-space;" class="">
<div class="">...
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div style="overflow-wrap: break-word;" class="">
<div class=""><br class="">
</div>
</div>
</blockquote>
</div>
<div class="">
<div class="">
<blockquote type="cite" class="">
<div class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode:
space; -webkit-line-break: after-white-space;" class="">
<div class="">
<div class="">
<div class="">
<div class="">
<blockquote type="cite" class="">
<div class=""></div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
<br class="">
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div>
</div></blockquote></div><br class=""></body></html>