Conversation

Notices

1. Embed this notice
   Jessica Paquette (barrelshifter@mastodon.social)'s status on Thursday, 29-May-2025 02:15:06 JST Jessica Paquette

   why doesn’t mlir arith have rotates

   • Embed this notice
     Owen Anderson (resistor@mastodon.online)'s status on Thursday, 29-May-2025 02:15:02 JST Owen Anderson

     in reply to

     • Fabian Giesen

     @rygorous @barrelshifter I think SimplifyDemandedBits was an area where GCC didn’t do much optimization at the time, so leaning heavily into it made LLVM look more compelling in microbenchmarks.

     ✧✦Catherine✦✧ repeated this.
   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 02:15:02 JST Fabian Giesen

     in reply to

     • Owen Anderson

     @resistor @barrelshifter Either way, I like the way the funnel shift solution worked out. (And will always be grateful for Sanjay doing the legwork!)

     They're a good normal form, funnel shift<->rotate (where applicable) is canonical and trivial in both directions, they can be formed early (which avoids destroying the pattern), they're reasonably common in target ISAs on their own right, and are still pretty straightforward to lower where they're not available

   • Embed this notice
     Owen Anderson (resistor@mastodon.online)'s status on Thursday, 29-May-2025 02:15:04 JST Owen Anderson

     in reply to

     • Fabian Giesen

     @rygorous @barrelshifter I think this and the ADD -> OR thing are downstream of a bit of an obsession Chris had for SimplifyDemandedBits transformations in the early days.

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 02:15:04 JST Fabian Giesen

     in reply to

     • Owen Anderson

     @resistor @barrelshifter The ADD->OR thing is another frequent monkey wrench especially wrt matching things that could be addressing modes, yeah.

     It's not a worthless transformation for larger-than-native-register integers (where not having cross-limb carries is a solid win) but for <=pointer size, I'd argue it hurts more than it helps.

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 02:15:05 JST Fabian Giesen

     in reply to

     @barrelshifter this is now years ago, but I vividly recall how much resistance there was to adding rotates to LLVM IR too because "can't you just build them out of simpler shifts?"

     (in short: yes, but not reliably for variable shifts; the patterns to match for rotates with variable shift amount are quite fragile and easily - and frequently - broken by unrelated opts in the middle end)

   • Embed this notice
     John Regehr (regehr@mastodon.social)'s status on Thursday, 29-May-2025 03:16:55 JST John Regehr

     in reply to

     • Fabian Giesen
     • Owen Anderson

     @rygorous @resistor @barrelshifter well TIL. I had thought it was just LLVM folk making shit up.

     ✧✦Catherine✦✧ repeated this.
   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 03:16:55 JST Fabian Giesen

     in reply to

     • John Regehr
     • Owen Anderson

     @regehr @resistor @barrelshifter I've you're wondering why they're called funnel shifters, just look at the wiring diagram.

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 03:16:57 JST Fabian Giesen

     in reply to

     • John Regehr
     • Owen Anderson

     @regehr @resistor @barrelshifter For some examples:
     - PPC and ARM A64 very visibly go for the rotate+mask approach. PPC does everything with rot left + mask (see e.g. https://devblogs.microsoft.com/oldnewthing/20180810-00/?p=99465), A64 is rot right + mask (https://www.scs.stanford.edu/~zyedidia/arm64/ubfm.html), and the A64 logic immediates use basically the same mask generation logic. (So it can be shared if desired, in a small design.)
     - I have seen datapath details for some Intel designs that used funnel shift right for all usual shifts.

   • Embed this notice
     John Regehr (regehr@mastodon.social)'s status on Thursday, 29-May-2025 03:16:58 JST John Regehr

     in reply to

     • Fabian Giesen
     • Owen Anderson

     @rygorous @resistor @barrelshifter good to know! one of these years I'll learn about GPUs for real 😭

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 03:16:58 JST Fabian Giesen

     in reply to

     • John Regehr
     • Owen Anderson

     @regehr @resistor @barrelshifter anyway I know about the funnel variants mostly from the HW side, e.g. stuff like this https://iccd.et.tudelft.nl/2008/proceedings/626huntzicker.pdf ("Energy-Delay Tradeoffs in 32-bit Static Shifter Designs", Huntzicker et al. 2008). Data-reversal shifters are e.g. in https://web.archive.org/web/20170706054724id_/https://www.princeton.edu/~rblee/ELE572Papers/Fall04Readings/Shifter_Schulte.pdf ("Design alternatives for barrel shifters", Pillmeier et al. 2002)

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 03:16:59 JST Fabian Giesen

     in reply to

     • John Regehr
     • Owen Anderson

     @regehr @resistor @barrelshifter actual funnel shift as an exposed operation is much rarer, especially the variable-shift-amount variant, because it absolutely needs a 3-operand architecture on the datapath. GPUs usually pervasively have that, and it's fairly common to see native funnel shift operations exposed on GPUs. (e.g. AMD has v_alignbit_b32, NV has SHF https://docs.nvidia.com/cuda/cuda-binary-utilities/index.html#maxwell-pascal)

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 03:17:00 JST Fabian Giesen

     in reply to

     • John Regehr
     • Owen Anderson

     @regehr @resistor @barrelshifter If you want to just shift right or just shift left, that's straightforward, but if you need both (plus variants like arithmetic shifts), you end up making two or more full shifters, which is not great.

     The main standard solutions are:
     1. build a rotator, reduce everything to rotate+masking
     2. set up into unidirectional funnel shift
     3. data reversal shifter: optional bit reverse, uni-directional shifter, optional bit reverse.

   • Embed this notice
     Fabian Giesen (rygorous@mastodon.gamedev.place)'s status on Thursday, 29-May-2025 03:17:01 JST Fabian Giesen

     in reply to

     • John Regehr
     • Owen Anderson

     @regehr @resistor @barrelshifter I know about them originally as one of the standard topologies to implement a generic shifter.

   • Embed this notice
     John Regehr (regehr@mastodon.social)'s status on Thursday, 29-May-2025 03:17:02 JST John Regehr

     in reply to

     • Fabian Giesen
     • Owen Anderson

     @rygorous @resistor @barrelshifter is there more written up about this anywhere? I guess I haven't thought about funnel shift that deeply but I kind of regarded it as a fun, quirky rotate. sometimes our superoptimizers come up with clever uses for it, which I enjoy.