Agner's CPU blog

RISC-V and AVX include instructions for variable bit shifts but not for rotations. What is the reason for this? Are variable rotations more expensive to implement in hardware than variable shifts?

Shift and rotate instructions require a barrel shifter. A barrel shifter is relatively expensive to implement, but once you have it, it can be used for both shift and rotate instructions.

Rotate instructions are not included in various instruction sets when designers have thought that they were not sufficiently important. Rotate instructions are useful for hashing and encryption algorithms.

AVX512 has rotate instructions in vector registers.

Variable shifts can be implemented with a log-shifter. However, there is a richer circuit available than a barrel shifter for rotations and the like.

A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations describes a way to build a recursive circuit from butterfly elements that also does the job. http://palms.princeton.edu/system/files ... ifters.pdf


Combined with a mask/merge on the output, this circuit can perform all of:

• shift
  insert / extract (ie, ARM's bit-field insert/extract)
  rotate
  parallel extract and insert (pext/pdep)
  reversals, all forms (ie, bytes in halfwords, bytes in words, halfwords in doublewords, etc)
  funnel shift with a pair of them (NEON's VEXTR).
  SIMD transpose step (NEON's VTRN)

It has about the same latency as an adder. Everything except the parallel extract/insert control bit generation is pretty small, too.

You can make a rotate from two shifts and an or. And there used to be no native rotate in C/C++ so it matched the language capability closely

marioxcc wrote: ↑

2020-06-14, 20:00:26

RISC-V and AVX include instructions for variable bit shifts but not for rotations. What is the reason for this? Are variable rotations more expensive to implement in hardware than variable shifts?

RISC-V has the bitmanip extension ( https://raw.githubusercontent.com/riscv ... p-0.92.pdf ) which fills in the missing rotate instruction, as well as many others.

To be honest, I don't want rotate as much as I want the SHLD/SHRD instructions (FSL/FSR/FSRI in RISC-V): rather than fill the shifted-out bits with zeroes, I want to fill them with bits shifted-in from another register of my choice. That allows fast and easy multi-precision shifts. Also, if that other register is zero, it's just a regular shift, and if the other register is the same register I'm shifting from in the first place, then it's just a rotate instruction.