Zero Sound

How GCC Divide

七月 17, 2007 at 1:57 上午 | In Default, Technology, compiler |

While I’m working on the module of my project which translating arithmetic operations into machine code,I think I should take a look at how gcc does it,especially (one of)the most wierd operation in i386 instruction set,div.After examining gcc’s output(using -S option when compiling),I find something interesting.When divisor is a constant integer,for example,an expression like x/3 (assuming x is a local variable with type int)in C source code,gcc will translate it into a seemingly strange sequence of instructions:

movl  $1431655766, %eax
imull x
movl  %edx, %ecx
movl  x, %eax
sarl  $31, %eax
subl  %eax, %ecx

(the result is stored in %ecx)

Obviously,gcc replaces the expensive idivl instruction with a series cheaper ones which generate the same result.I believe everyone will feel confused about the magic $1431655766 number.Where does this number come from?In fact,it is just .The above code is essentially the following identity:

Why?First,the code computes x*1431655766.The low 32 bits of the result is in eax,high 32 bits in edx.Then the value of edx is just the left side of the above equation,and should be what we want.But what the left instructions do?Here is a subtle problem:we assume that x is a signed int.If x is negative,then gives .So we have to compensate the extra 1.Here we can make use of x’s sign bit.This is actually what the code does:load x to eax,and perform

sarl $31,%eax

If x > 0,this will result in 0;if x < 0,then -1.Substracting this result from eax,the final result is achieved.

A problem:I try another example,say x/13.The generated code is similar to previous one,but a little difference:the magic number becomes ,therefore you have to do an extra

sarl $2,%edx

For other numbers,gcc will multiply a certain power of 2 when computing the magic number,for example,if divisor is 45,then 32 is multiplied.I can’t figure out why gcc does this.

阅读(985 次)