[MLton] Constant Folding of FP Operations

[Matthew Fluet]

On Fri, 23 May 2008, Vesa Karvonen wrote:
> Attached is an experimental patch that improves MLton's constant folding
> of floating point operations.  The problem with constant folding FP
> operations in SML is that the FP ops are subject to rounding mode
> settings:
>
>  http://www.standardml.org/Basis/ieee-float.html#SIG:IEEE_REAL.setRoundingMode:VAL
>
> The workaround used in the patch is to evaluate the operations in all
> rounding modes (actually in only TO_NEGINF and TO_POSINF) and check that
> the results agree.  This ensures that constant folding is correct in all
> rounding modes.

Seems like a good optimization, and a sound one.  Did you run the 
benchmarks and observe any speedups?

> Personally I'm inclined to think that the inclusion of get/setRoundingMode
> in the Basis library is a design mistake, because it makes some FP
> optimizations very difficult.

FP optimizations seem to be very difficult in general.  It is particularly 
difficult because IEEE 754 says nothing about many floating-point 
operations; for example, sin/cos/tan are not specified to follow an 
implicit or explicit rounding mode.

> An alternative design would be to have
> multiple modules, say Real[ToNearest], RealToNegInf, RealToPosInf, and
> RealToZero, each corresponding to a specific rounding mode.  FP ops could
> then be treated as functional and it would then likely become
> straightforward to make the same kind of aggressive constant folding and
> simplification of FP ops as is done for integer ops.  Of course, this
> would introduce the need for the compiler to insert code to switch the
> rounding modes when necessary, but this doesn't seem extremely difficult.

The C-- specification of floating-point expressions makes the rounding 
mode an explicit argument; e.g.:

   fsub  \forall \alpha. bits \alpha * bits \alpha * bits 2 -> bits \alpha
         Floating-point subtract with explicit rounding mode.
   round_down  bits2
         IEEE 754 rounding mode for rounding down.

The C-- specification of floating-point expressions also does not include 
any operations not specified by the IEEE 754 standard; that is, C-- does 
not provide trancendentals, etc.  Instead, one must call the system's math 
library.

> About the patch.  The compiler changes do not compile with SML/NJ, which
> does not support 32-bit floating point (Real32), and it should be made so
> that the FP simplifications aren't performed (and would be replaced with
> dummy functions) when the compiler has been compiled with SML/NJ.

You might consider dynamically checking the value of Real32.precision, 
which would allow you to distinguish a "real" Real32 from a "dummy" Real32 
that is bound to Real64.

> This is
> the reason why I consider this an experimental patch and haven't committed
> it.  Some of the floating point simplifications should probably also be
> disabled when cross compiling.  These should not be very difficult to do,
> but it seems that I'm unlikely get around to implementing them.

There also seems to be a little-endian assumption for constant-folding 
castToWord and castFromWord.  It should be easy enough to use:

val r64 =
     R {...
        subVec = fn arg =>
                 if Control.Target.bigEndian
                 then P.PackWord64Big.subVec arg
                 else P.PackWord64Little.subVec arg,
        ...}

> The "decon" datatype has some constructors that aren't currently used
> (although they are produced by the decon function) in the patch.  I
> planned those constructors for some optimizations (e.g. replace divide by
> a power of 2 with a multiply) that aren't currently possible with MLton's
> Prim.apply, because it does not allow the introduction of an operation
> with constants in the result of Prim.apply.  This restriction of
> Prim.apply could probably be lifted without huge problems.  The limitation
> is probably due to the design of the SSA and SSA2 intermediate languages
> of MLton that do not allow constants as operands.

It shouldn't be difficult to allow Prim.apply to return more complicated 
expressions.  There aren't that many (static) uses of Prim.apply in the 
compiler; you would simply need to allow uses of Prim.apply to yield a 
sequence of IL statements, so that you could bind constants to variables 
before using them in the IL primitive.

With the exception of the caveats noted above (SML/NJ builds, 
cross-compiling, and target endiannes), I think the patch looks good.