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.
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:
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.
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.)
Comments
Odd. The code:
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.
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:
compiles to: Meanwhile, the signed variant: compiles to: 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.I got the following (-O6 -fstrength-reduce). A single arithmetic shift is no good, so the code adjusts the value first.
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.)