<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, May 16, 2018 at 11:27 AM, Manuel Jacob <span dir="ltr"><<a href="mailto:me@manueljacob.de" target="_blank">me@manueljacob.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_-6283250949438751851m_-3308799904405102434m_7691605663874911140gmail-m_-6175264811447545492m_2665971240252776982gmail-">On 2018-05-16 00:34, Sanjay Patel via llvm-dev wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_-6283250949438751851m_-3308799904405102434m_7691605663874911140gmail-m_-6175264811447545492m_2665971240252776982gmail-">
Vectorization goes overboard because the throughput cost model used by the<br>
vectorizers doesn't match the 6 IR instructions that correspond to 1 x86<br>
rotate instruction. Instead, we have:<br>
<br></span>
[...]<span class="m_-6283250949438751851m_-3308799904405102434m_7691605663874911140gmail-m_-6175264811447545492m_2665971240252776982gmail-"><br>
<br>
The broken cost model also affects unrolling and inlining. Size costs are<br>
overestimated for a target that has a rotate instruction.<br>
This cost problem isn't limited to rotate patterns (it's come up in the<br>
context of min/max/abs/fma too). But it would be simpler if we had a rotate<br>
intrinsic, and the 6-to-1 margin is the biggest I've seen.<br>
</span></blockquote>
<br>
Given that this is a general problem that occurs with other instruction sequences as well, wouldn't it make more sense to make the cost model handle more than one instruction, as suggested in PR31274 [1]?<br>
<br>
[1] <a href="https://bugs.llvm.org/show_bug.cgi?id=31274" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug<wbr>.cgi?id=31274</a><br>
<br></blockquote><div><br></div>Yes, I think everyone agrees that we need to improve the cost model interface. Note that there's a proposal for review for the 1 IR -> many machine ops variant of this question:<br></div><div class="gmail_quote"><a href="https://reviews.llvm.org/D46276" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4627<wbr>6</a><br></div><div class="gmail_quote"><div><br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
In all these cases (rotate, min, max, abs, fma, add-with-overflow, and probably many more) there's a tradeoff between elaborating them as simpler IR instructions and modelling them as its own instruction / intrinsic.  A big disadvantage of introducing new instructions / intrinsics is that all optimizations have to be told about this, increasing the compiler code base and maintainability burden.  On the other hand, too few instructions can make optimization difficult as well (in theory, one instruction like "subtract and branch if not equal to zero" could emulate all the others, but this wouldn't be very helpful for optimization).  Since you put a lot of thought into how to canonicalize IR, can you eleborate more on this tradeoff?  Can we find a set of criteria to determine whether an instruction pattern should get an intrinsic or not?<span class="m_-6283250949438751851m_-3308799904405102434m_7691605663874911140gmail-m_-6175264811447545492m_2665971240252776982gmail-HOEnZb"></span></blockquote><div><br></div><div>I don't have formal criteria for this. Someone more knowledgeable may give us an answer.<br></div><br>An informal metric might be: if the operation is supported as a primitive op or built-in in source languages and it is supported as a single target instruction, can we guarantee that 1-to-1 translation through optimization?<br></div><div class="gmail_quote">We are failing that test in the loop-invariant C example presented here. We're
 also failing that test when operands have different sizes. Rotate goes 
in, logic and shifts come out.<br>We even failed that test for an even more basic case before this fix: <a href="https://reviews.llvm.org/D46656" target="_blank">https://reviews.llvm.org/D4665<wbr>6</a><br></div><div class="gmail_quote">We may still be failing the basic case for other source languages/flavors because encoding this operation in existing IR ops isn't obvious?<br></div><div class="gmail_quote"><br>Another informal measure is: how do programmers express this operation without a builtin? If they're resorting to inline asm, that's a strong sign that the compiler needs an intrinsic.<br></div><div class="gmail_quote"><br></div><div class="gmail_quote">Another metric could be: what is the probability that the optimizer can improve the codegen if the operation is broken down into multiple IR instructions?<br></div><div class="gmail_quote">As noted here, it's unlikely for rotate. If it is possible, then adding folds to instcombine for this intrinsic isn't hard. Are any other passes affected?<br></div><div class="gmail_quote"><br></div><div class="gmail_quote">For reference, these are the current target-independent bit-manipulation intrinsics - bswap, bitreverse, ctpop, ctlz, cttz:<br></div><div class="gmail_quote"><a href="http://llvm.org/docs/LangRef.html#bit-manipulation-intrinsics" target="_blank">http://llvm.org/docs/LangRef.h<wbr>tml#bit-manipulation-intrinsic<wbr>s</a> <br></div><div class="gmail_quote"><br></div><div class="gmail_quote">The LLVM cost for the proposed rotate intrinsic should be in the same range as those? Note that we would not just be adding code to support an intrinsic. There are already ~200 lines of DAG matching code for rotate, so we already have a cost for trying to get this optimized. We can remove that after adding canonicalization to the intrinsic in IR.<br></div><div class="gmail_quote"><div><br></div></div><br></div></div>