<div dir="ltr"><div>Initial patch proposal:</div><div><a href="https://reviews.llvm.org/D49242" rel="noreferrer" target="_blank">https://reviews.llvm.org/<wbr>D49242</a></div><div><br></div><div>I tried to add anyone that replied to this thread as a potential reviewer. Please add yourself if I missed you.<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jul 8, 2018 at 9:23 AM, Sanjay Patel <span dir="ltr"><<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Yes, if we're going to define this as the more general 2-operand funnel shift, then we might as well add the matching DAG defs and adjust the existing ROTL/ROTR defs to match the modulo.<br></div><div><br></div><div>I hadn't heard the "funnel shift" terminology before, but let's go with that because it's more descriptive/accurate than concat+shift.</div><div><br></div><div>We will need to define both left and right variants. Otherwise, we risk losing the negation/subtraction of the shift amount via other transforms and defeat the point of defining the full operation.</div><div><br></div><div>A few more examples to add to Fabian's:</div><div> - x86 AVX512 added vprol* / vpror* instructions for 32/64-bit element vector types with constant and variable rotate amounts. The "<span></span><span style="font-size:9pt;font-family:"Verdana"">count operand modulo the data size (32 or 64) is used".</span>
<span></span>
<br></div><div><br></div><div>- PowerPC defined scalar rotates with 'rl*' (everything is based on rotating left). Similarly, Altivec only has 'vrl*' instructions for vectors and all ops rotate modulo the element size. The funnel op is called "vsldoi". So again, it goes left.<br></div><div><br></div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jul 8, 2018 at 7:23 AM, Simon Pilgrim <span dir="ltr"><<a href="mailto:llvm-dev@redking.me.uk" target="_blank">llvm-dev@redking.me.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="m_7482088467200219200HOEnZb"><div class="m_7482088467200219200h5"><br>
<br>
On 02/07/2018 23:36, Fabian Giesen via llvm-dev wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 7/2/2018 3:16 PM, Sanjay Patel wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I also agree that the per-element rotate for vectors is what we want for this intrinsic.<br>
<br>
So I have this so far:<br>
<br>
declare i32 @llvm.catshift.i32(i32 %a, i32 %b, i32 %shift_amount)<br>
declare <2 x i32> @llvm.catshift.v2i32(<2 x i32> %a, <2 x i32> %b, <2 x i32> %shift_amount)<br>
<br>
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>
For vectors, that operation occurs for each element of the vector:<br>
result[i] = trunc(concat(a[i], b[i]) >> c[i])<br>
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.<br>
</blockquote>
<br>
Or just negating, iff the shift amount is defined to be modulo and the machine is two's complement.<br>
<br>
I'm a bit worried that while modulo is the Obviously Right Thing for rotates, the situation is less clear for general funnel shifts.<br>
<br>
I looked over some of the ISAs I have docs at hand for:<br>
<br>
- x86 (32b/64b variants) has SHRD/SHLD, so both right and left variants. Count is modulo (mod 32 for 32b instruction variants, mod 64 for 64b instruction variants). As of BMI2, we also get RORX (non-flag-setting ROR) but no ROLX.<br>
<br>
- ARM AArch64 has EXTR, which is a right funnel shift, but shift distances must be literal constants. EXTR with both source registers equal disassembles as ROR and is often special-cased in implementations. (EXTR with source 1 != source 2 often has an extra cycle of latency). There is RORV which is right rotate by a variable (register) amount; there is no EXTRV.<br>
<br>
- NVPTX has SHF (<a href="https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#logic-and-shift-instructions-shf" rel="noreferrer" target="_blank">https://docs.nvidia.com/cuda/<wbr>parallel-thread-execution/inde<wbr>x.html#logic-and-shift-instruc<wbr>tions-shf</a>) with both left/right shift variants and with both "clamp" (clamps shift count at 32) and "wrap" (shift count taken mod 32) modes.<br>
<br>
- GCN has v_alignbit_b32 which is a right funnel shift, and it seems to be defined to take shift distances mod 32.<br>
<br>
based on that sampling, modulo behavior seems like a good choice for a generic IR instruction, and if you're going to pick one direction, right shifts are the one to use. Not sure about other ISAs.<br>
<br>
-Fabian<br>
</blockquote></div></div>
Sorry for the late reply to this thread, I'd like to mention that the existing ISD ROTL/ROTR opcodes currently do not properly assume modulo behaviour so that definition would need to be tidied up and made explicit; the recent legalization code might need fixing as well. Are you intending to add CONCATSHL/CONCATSRL ISD opcodes as well?<br>
<br>
Additionally the custom SSE lowering that I added doesn't assume modulo (although I think the vXi8 lowering might work already), and it only lowers for ROTL at the moment (mainly due to a legacy of how the XOP instructions work), but adding ROTR support shouldn't be difficult.<br>
<br>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>