3 ms·

Be careful: "x / 16" won't get converted to "x >> 4" by the compiler if x is a signed int. I lost an argument about this in a code review once. Look at the disa

by mierle 13y ago

Be careful: "x / 16" won't get converted to "x >> 4" by the compiler if x is a signed int. I lost an argument about this in a code review once. Look at the disassembly for the case that x is and is not signed if you don't believe me.

spc476 13y ago
Odd. The code: int main(int argc,char *argv[]) { int x = strtol(argv[1],NULL,10); printf("result is %d\n",x/16); return 0; } The resulting assembly contained no division instructions, nor a call to a divide routine, but there is one instruction that does an arithmetic right shift by 4. Changing x to unsigned changed the instruction to a logical right shift by 4. I think it really depends upon the compiler.
- mierle 13y ago
  Strangely, I can't reproduce the effect with a divide by 16. With GCC 4.5.2 -O2, I see a "shrl $4, %eax" for unsigned, and "sarl $4, %eax" for signed. However, if I divide by 2, the results are different; the function: int div_by_2(int x) {return x/2;} compiles to: div_by_2: movl %edi, %eax shrl $31, %eax addl %edi, %eax sarl %eax ret Meanwhile, the signed variant: unsigned int div_by_2(unsigned int x) {return x/2;} compiles to: div_by_2: movl %edi, %eax shrl %eax ret My conclusion remains that for hot loops, you should check the compilers assembly to make sure the compiler is applying the strength reduction you expect.
- to3m 13y ago
  I got the following (-O6 -fstrength-reduce). A single arithmetic shift is no good, so the code adjusts the value first. movl %eax, %esi sarl $31, %esi ; ESI = FFFFFFFF (-) / 00000000 (+) shrl $28, %esi ; ESI = 0000000F (-) / 00000000 (+) addl %eax, %esi ; offset to cancel invalid values sarl $4, %esi ; shift It first generates an offset value in ESI: 15 if the value to divide was negative, or 0 if it was positive. Then it adds this to the original value. This is the cunning part - well I think so anyway. It ensures that for the values where x>>4 would give the wrong value (i.e., -15<=x<0), x is made positive and smaller than 16, so that x>>4 gives the correct value of zero. For all other values, the bottom 4 bits don't affect the result of the division, so it's fine to offset them as well. (Don't think I've ever seen VC++ generate anything like this, but I'd pretty much always have an explicit shift rather than a divide by 16 so maybe it does and I'd just never noticed. The choice of 16 usually comes from having some 4-bit field somewhere, and when dealing with bitfields you're best off using bitwise instructions.)

by mierle 13y ago

spc476 13y ago

Odd. The code: int main(int argc,char *argv[]) { int x = strtol(argv[1],NULL,10); printf("result is %d\n",x/16); return 0; } The resulting assembly contained no division instructions, nor a call to a divide routine, but there is one instruction that does an arithmetic right shift by 4. Changing x to unsigned changed the instruction to a logical right shift by 4. I think it really depends upon the compiler.

mierle 13y ago
Strangely, I can't reproduce the effect with a divide by 16. With GCC 4.5.2 -O2, I see a "shrl $4, %eax" for unsigned, and "sarl $4, %eax" for signed. However, if I divide by 2, the results are different; the function: int div_by_2(int x) {return x/2;} compiles to: div_by_2: movl %edi, %eax shrl $31, %eax addl %edi, %eax sarl %eax ret Meanwhile, the signed variant: unsigned int div_by_2(unsigned int x) {return x/2;} compiles to: div_by_2: movl %edi, %eax shrl %eax ret My conclusion remains that for hot loops, you should check the compilers assembly to make sure the compiler is applying the strength reduction you expect.
to3m 13y ago
I got the following (-O6 -fstrength-reduce). A single arithmetic shift is no good, so the code adjusts the value first. movl %eax, %esi sarl $31, %esi ; ESI = FFFFFFFF (-) / 00000000 (+) shrl $28, %esi ; ESI = 0000000F (-) / 00000000 (+) addl %eax, %esi ; offset to cancel invalid values sarl $4, %esi ; shift It first generates an offset value in ESI: 15 if the value to divide was negative, or 0 if it was positive. Then it adds this to the original value. This is the cunning part - well I think so anyway. It ensures that for the values where x>>4 would give the wrong value (i.e., -15<=x<0), x is made positive and smaller than 16, so that x>>4 gives the correct value of zero. For all other values, the bottom 4 bits don't affect the result of the division, so it's fine to offset them as well. (Don't think I've ever seen VC++ generate anything like this, but I'd pretty much always have an explicit shift rather than a divide by 16 so maybe it does and I'd just never noticed. The choice of 16 usually comes from having some 4-bit field somewhere, and when dealing with bitfields you're best off using bitwise instructions.)