0

I came across code similar to this in the ARM CMSIS-NN library:

int32_t val, shift;

// code that initializes val and shift

int32_t result = val * (1 << shift);

which aims to multiply val by some power of two value x, with shift being the exponent, i.e. x=pow(2,shift). Why are they not simply shifting? Like so

int32_t result = val << shift;

Is there something special that I am missing? Can the compiler optimize the former operation in some special way?

EDIT: What confuses me is that they are using "simple shifts" throughout the code. Additionally, the code should be highly optimized. But I guess modern compilers will figure out by themselves, that shifting is the way to go (instead of multiplying)?

Fabian
  • 312
  • 3
  • 13
  • What type is `q31_t`? Are you sure that it supports the `<<` operator? For instance, floating point types don't. – Nate Eldredge Oct 31 '21 at 00:02
  • The shift is limited to the number of bits in a machine word. The pow() is not. [this restriction was probably caused by a limitation in the x86 instructions, where the shift was treated as (shift %32) ] – wildplasser Oct 31 '21 at 00:03
  • @Nate Eldredge `q31_t` is a fixed-point data type (see here https://en.wikipedia.org/wiki/Q_(number_format)). In CMSIS-NN its just a typedef to int32_t- – Fabian Oct 31 '21 at 00:04
  • @wildplasser all variables (including the result) are 32bit. So this shouldn't matter here, right? – Fabian Oct 31 '21 at 00:09
  • BTW: you should always perform shifts like these in the largest unsigned datatype available: `(1ull < – wildplasser Oct 31 '21 at 00:11
  • @wildplasser wouldn't the result be simply 0 if I shifted by more than 32? The same would happen in the multiply variant when casting back to int32, right? – Fabian Oct 31 '21 at 00:15
  • In short: no. [just wait untill the language lawyers kick in ...] – wildplasser Oct 31 '21 at 00:19
  • @wildplasser You are indeed correct according to [this](https://stackoverflow.com/questions/11270492/what-does-the-c-standard-say-about-bitshifting-more-bits-than-the-width-of-type). It would be undefined. But is that justification enough? Or is there more to it? – Fabian Oct 31 '21 at 00:25
  • [Yes, modern compilers can figure out this optimization](https://godbolt.org/z/8Gf5b4rzj) – Nate Eldredge Oct 31 '21 at 00:33

1 Answers1

1

It is always sign correct and forces the use of the proper FPU instructions and works with any type of data.

0___________
  • 60,014
  • 4
  • 34
  • 74
  • I should have mentioned that this is all fixed-point arithmetic. So there are only integers involved here (int32_t to be exact). But preserving the sign could be the reason. This way the leading bit won't be shifted out, correct? Thanks for pointing that out. I have to think about it just a little bit longer. – Fabian Oct 31 '21 at 00:03
  • @fabian not only fixed – 0___________ Oct 31 '21 at 00:05
  • what do you mean by that? – Fabian Oct 31 '21 at 00:10
  • 2
    they wanted to be type agnostic – 0___________ Oct 31 '21 at 00:10
  • But why would they want to be type agnostic if all types are fixed to int32_t? – Fabian Oct 31 '21 at 00:12
  • it is called: "implementation" – 0___________ Oct 31 '21 at 00:18
  • I don't see what you mean by "preserving sign". If there's no overflow then both expressions should yield the same result, as far as I can tell, including the correct sign. If there is overflow then both are UB. – Nate Eldredge Oct 31 '21 at 00:29
  • Also, I don't see how it "works with any type of data". For instance if `int` is 32 bits, and `val` is `int64_t` with a relatively small value, then `val << 33` is well-defined while `val * (1 << 33)` is UB. – Nate Eldredge Oct 31 '21 at 00:31
  • @NateEldredge if `val` is negative, then `val << shift` is undefined, even for `shift == 0`. If the compiler accepted it, and even supposing that it didn't use the undefinedness as an excuse to do something stupid, there is no reason to expect that the result would be the same as that of `val * (1 << shift)`. The most natural implementation of the former would shift the sign bit off the left end for any non-trivial left shift. – John Bollinger Oct 31 '21 at 00:39
  • @JohnBollinger: You're right, left-shift of negative is UB. I always forget that case. But if the compiler doesn't "do something stupid", then for two's complement representations, the result is correct if it doesn't overflow: the sign bit is shifted off the end, but the bit that replaces it has the same value. – Nate Eldredge Oct 31 '21 at 00:46
  • No, @NateEldredge, that is guaranteed only if `val` is -1. For all other negative numbers, there are some shifts (of less than the width of the data type) that would put a zero bit in the sign position, sign extension notwithstanding. – John Bollinger Oct 31 '21 at 00:54
  • @NateEldredge you do not understand that it is ARM Cortex implementation. Implementation very often use constructs which in portable C are undefined. Like shift if shift is larger than the type size. But ARM Cortex behaviour is well defined and author of the implementation can use it safely. – 0___________ Oct 31 '21 at 01:05
  • @NateEldredge why could not they use ULL? https://godbolt.org/z/76n1jq3bs – 0___________ Oct 31 '21 at 01:10
  • @0___________ if you remove the part about the FPU (I updated my question) I would accept your answer. EDIT: Maybe removing is not a good idea as it is another important reason when using floats. – Fabian Oct 31 '21 at 01:16
  • @fabian not only, DSP instructions may help as well in NN – 0___________ Oct 31 '21 at 01:21
  • @JohnBollinger: Right, but those are precisely the shifts that would overflow. For instance, take `val = -16 = 0xfffffff0`. Then for instance `val << 4 = 0xffffff00 = -256` which is correct. It's correct all the way up to `val << 27 = 0x80000000`. It's true that `val << 28` is incorrect (0) but `-16 * 2**28` doesn't fit in `int` anyway, which is what I mean by "overflow". Similarly for `val = 16 = 0x10`, it's correct up to `val << 26`, and `val << 27` overflows because `16 * 2**27` does not fit in `int`. – Nate Eldredge Oct 31 '21 at 01:40
  • Ok, @NateEldredge, point made. – John Bollinger Oct 31 '21 at 01:48