[MLton-devel] improvement for Int.{div,mod}

[Stephen Weeks]

> I don't believe that the x86 codegen is doing anything tricky.
> z = Prim.Int_quot(x,y) and z = Prim.Int_mod(x,y) are both translated to:
> mov x, z
> idiv z, y

Sorry, I wasn't entirely clear.  I was referring to the case from
Franck's mail where the divisor is constant.

> Note that Int.{quot,rem} are _not_ used to implement Int.{div,mod}.  The
> Integer functor implements Int.{quot,rem,div,mod} in terms of I.{quot,rem}
> (where I : PRE_INTEGER_EXTRA).  That is, all of Int.{quot,rem,div,mod}
> wrap some additional tests around the primitives. 

Agreed.

> The actual primitives are implemented as efficiently as possible.

I think there is still room for improvement.  Here is the definition
of Int.div:

fun x div y =
  if x >= zero
    then if y > zero
	   then I.quot (x, y)
	   else if y < zero
		  then if x = zero
			 then zero
			 else I.quot (x - one, y) -? one
		  else raise Div
    else if y < zero
	   then if detectOverflow andalso x = minInt' andalso y = ~one
		  then raise Overflow
		  else I.quot (x, y)
	   else if y > zero
		  then I.quot (x + one, y) -? one
		  else raise Div

So, "x div 16" simplifies to

  if x >= zero
    then I.quot (x, 16)
    else I.quot (x + one, 16) -? one

The assembly I see for the then branch is

	movl %esi,%edi
	sarl $3,%edi
	shrl $28,%edi
	addl %edi,%esi
	sarl $4,%esi

The assembly I see for the else branch is

	incl %esi
	movl %esi,%edi
	sarl $3,%edi
	shrl $28,%edi
	addl %edi,%esi
	sarl $4,%esi
	decl %esi

Both of these branches appear to be doing stuff to handle both
negative and positive values of x (aka %esi).  For example, the then
branch could be simplified to a single shrl, since we know x >= 0.



-------------------------------------------------------
This SF.net email is sponsored by: VM Ware
With VMware you can run multiple operating systems on a single machine.
WITHOUT REBOOTING! Mix Linux / Windows / Novell virtual machines at the
same time. Free trial click here: http://www.vmware.com/wl/offer/345/0
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel