[MLton] IntInf implementation questions

[Stephen Weeks]

>        fun bigPlus (lhs: bigInt, rhs: bigInt): bigInt =
>           let
>              val res =
>                 if areSmall (lhs, rhs)
>                    then let val ansv = Word.+ (stripTag lhs, stripTag rhs)
>                             val ans = addTag ansv
>                         in if sameSign (ans, ansv)
>                               then SOME (Prim.fromWord ans)
>                            else NONE
>                         end
>                 else NONE
...
> On the small fast path, I count 6 bitops and one comparison test. 

Yep.  I'd say that makes sense to count areSmall as being on the path
too, so you get 8 bitops and two tests.

  func		bitops		tests
  --------	----------	-----
  areSmall  	andb, andb	<>
  stripTag	~>>
  stripTag	~>>
  Word.+	+
  addTag 	<<, orb
  sameSign	xorb		>=

> I think the following is equivalent:
> 
>        fun bigPlus (lhs: bigInt, rhs: bigInt): bigInt =
>           let
>              val res =
>                 if areSmall (lhs, rhs)
>                    then let val ansv = Int.+ (Word.toIntX (Prim.toWord lhs),
>                                               Word.toIntX (zeroTag rhs))
>                         in SOME (Prim.fromWord (Word.fromInt ansv))
>                         end handle Overflow => NONE
>                 else NONE
...
> On the small fast path, I count 2 bitops and one overflow test.  I think 
> you can do the same thing for bigMinus.

Yes, this is a good trick.  Again, counting areSmall, this gives 4
bitops, one test, and one overflow check.  So we can hope for maybe
even a factor of two speedup.  Nice.

BTW, this trick is pretty well known.  It is what SML/NJ does (at
least did) and is described on page 162 of Appel's book, Compiling
With Continuations (http://mlton.org/References#Appel92).  Appel also
explains there how to do multiplication, and points out that one can
do subtraction and division too.  I think the same tricks work in our
situation.

Another nice observation that Appel makes is that if one of the
arguments is constant, the zeroTag can be done at compile time.
Unfortunately, since this is user code, we have to get lucky and hope
that rhs is the constant.  Hmmm, I wonder if we could add a primitive:

  val isConstant: 'a -> bool

The semantics of isConstant is that it returns false, unless the
optimizer is able to prove that its argument is a constant.
Obviously, one can only use isConstant sensibly in symmetric
situations where the behavior of the program (other than performance)
doesn't depend on whether it returns true or false.  For example, we
could then write something like:

  if areSmall (lhs, rhs) then
     let  
        val (x, c) = if isConstant lhs then (rhs, lhs) else (lhs, rhs)
     in
        SOME (Prim.fromWord 
              (Word.fromInt
	       (Int.+ (Word.toIntX (Prim.toWord x), Word.toIntX (zeroTag c)))))
        handle Overflow => NONE
     end
  else
     NONE

Now, if either lhs or rhs is constant, the zeroTag will happen at
compile time and we will save one (of four) bitops.  That seems worth
it.