<div dir="ltr"><div>I also agree that the per-element rotate for vectors is what we want for this intrinsic.</div><div><br></div><div>So I have this so far:</div><div><pre><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">declare</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">i32</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-nd">@llvm</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">.</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">catshift</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">.</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">i32</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-p">(</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">i32 </span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">%</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">a</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">, i32 %b</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-p">, i32 %shift_amount)</span>
<span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">declare</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-o"><</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-mi">2</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">x</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">i32</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">></span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-nd">@llvm</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">.</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">catshift</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">.</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">v2i32</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-p">(</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o"><</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-mi">2</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">x</span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">i32</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">></span> <span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">%</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-n">a</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-o">, <2 x i32> %b, <2 x i32> %shift_amount</span><span class="gmail-m_168559858411044128m_5764598562723153792gmail-p">)</span></pre>For
scalars, @llvm.catshift concatenates %a and %b, shifts the concatenated value
right by the number of bits specified by %shift_amount modulo the bit-width, and truncates to
the original bit-width. <br></div><div> For vectors, that operation
occurs for each element of the vector:</div><div>
result[i] = trunc(concat(a[i], b[i]) >> c[i])<br></div><div> If %a == %b, this is equivalent to a bitwise rotate right. Rotate left may be
implemented by subtracting the shift amount from the bit-width of the
scalar type or vector element type.</div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 2, 2018 at 2:37 PM, Fabian Giesen <span dir="ltr"><<a href="mailto:fabiang@radgametools.com" target="_blank">fabiang@radgametools.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">1. I'm not sure what you mean by "full vector" here - using the same shift distance for all lanes (as opposed to per-lane distances), or doing a treat-the-vector-as-bag-of-bit<wbr>s shift that doesn't have any internal lane boundaries? If the latter, that doesn't really help you much with implementing a per-lane rotate.<br>
<br>
I think the most useful generalization of a vector funnel shift in this context is lane-wise<br>
<br>
result[i] = trunc(concat(a[i], b[i]) >> c[i])<br>
<br>
(or the equivalent for a left shift); the special case a==b is a rotate.<br>
<br>
2. For operand sizes that have native rotate instructions, at least x86, x86-64, ARM A32/T32 and AArch64 A64 agree that rotate distances are modulo the operand width. I believe PPC and MIPS do the same but am not sure (it's been a while), no clue about other architectures.<br>
<br>
It certainly seems the most natural way to define it, since rotates are cyclic to begin with.<br>
<br>
8- and 16-bit rotates will need to be lowered into multi-instruction sequences on most targets (x86 and x86-64 can do them directly, but RISC-lineage archs usually don't have rotates at smaller than word size). Having explicit modulo semantics might end up forcing an explicit extra AND there, so that's an extra cost there, but it would certainly be nice to have the rotate definition be total.<br>
<br>
-Fabian<span class=""><br>
<br>
On 07/02/2018 09:27 AM, Sanjay Patel wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
I'm guessing nobody has started implementing any of the suggested rotate functionality since there are still open questions, but let me know if I'm wrong.<br>
<br></span>
We're still getting patches that try to work around the current limitations (<a href="https://reviews.llvm.org/D48705" rel="noreferrer" target="_blank">https://reviews.llvm.org/D487<wbr>05</a> <<a href="https://reviews.llvm.org/D48705" rel="noreferrer" target="_blank">https://reviews.llvm.org/D487<wbr>05</a>> ), so we should move forward since we've approximated/justified the cost and benefits.<span class=""><br>
<br>
Let's settle on the intrinsic definition(s).<br>
<br>
1. There was a suggestion to generalize rotate to a "valign" or "double shift" (that's what x86 means with its poorly worded "double precision shift"). How does that work with vector types? The options are a full vector-size shift or a per-element shift. If it's the full vector, do we still want/need a specialized rotate intrinsic for per-element? If it's per-element, do we still want/need the other form for a full vector?<br>
<br>
2. What is the behavior for a shift/rotate amount that is equal or greater than the bit-width of the operand (or the bit width of a vector element type?)? Can we modulo that operand by the bit width, or does that not map well to the hardware semantics?<br>
<br></span><div><div class="h5">
On Thu, May 17, 2018 at 5:23 PM, John Regehr <<a href="mailto:regehr@cs.utah.edu" target="_blank">regehr@cs.utah.edu</a> <mailto:<a href="mailto:regehr@cs.utah.edu" target="_blank">regehr@cs.utah.edu</a>>> wrote:<br>
<br>
Thanks Sanjay!<br>
<br>
At this point the cost/benefit tradeoff for rotate intrinsics<br>
seems pretty good.<br>
<br>
John<br>
<br>
<br>
On 05/17/2018 11:14 AM, Sanjay Patel wrote:<br>
<br>
A rotate intrinsic should be relatively close in<br>
cost/complexity to the existing bswap.<br>
<br>
A grep of intrinsic::bswap says we'd probably add code in:<br>
InstCombine<br>
InstructionSimplify<br>
ConstantFolding<br>
DemandedBits<br>
ValueTracking<br>
VectorUtils<br>
SelectionDAGBuilder<br>
<br>
But I don't think it's fair to view those additions as pure<br>
added cost. As an example, consider that we have to add hacks<br>
to EarlyCSE to recognize multi-IR-instruction min/max/abs<br>
patterns. Intrinsics just work as-is there. So if you search<br>
for 'matchSelectPattern', you get an idea (I see 32 hits in 10<br>
files) of the cost of *not* having intrinsics for those<br>
operations that we've decided are not worthy of intrinsics.<br>
<br>
<br>
On Wed, May 16, 2018 at 2:20 PM, John Regehr via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a>><br></div></div>
<mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a><div><div class="h5"><br>
<mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a>>>> wrote:<br>
<br>
On 5/16/18 1:58 PM, Sanjay Patel via llvm-dev wrote:<br>
<br>
An informal metric might be: if the operation is<br>
supported as a<br>
primitive op or built-in in source languages and it is<br>
supported<br>
as a single target instruction, can we guarantee that<br>
1-to-1<br>
translation through optimization?<br>
<br>
<br>
It seems perfectly reasonable for LLVM users to expect this to<br>
happen reliably.<br>
<br>
I'd like to take a look at the other side of the equation:<br>
the cost<br>
of adding a new intrinsic in terms of teaching passes to<br>
see through<br>
it, so we don't lose optimizations that worked before the<br>
intrinsic<br>
was added.<br>
<br>
For example, clearly ValueTracking needs a few lines added<br>
so that<br>
computeKnownBits and friends don't get stopped by a<br>
rotate. Anyone<br>
have a reasonably complete list of files that need similar<br>
changes?<br>
<br>
John<br>
<br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a>><br></div></div>
<mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a>>><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin<wbr>/mailman/listinfo/llvm-dev</a>><br>
<<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin<wbr>/mailman/listinfo/llvm-dev</a><br>
<<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin<wbr>/mailman/listinfo/llvm-dev</a>>><br>
<br>
<br>
<br>
</blockquote>
<br>
</blockquote></div><br></div>