[MLton-devel] Re: PRE in MLton

[Tom Murphy]

> Hi Tom.  I was curious to hear how your PRE implementation was coming
> along.  Any problems or MLton questions?  Any successes?

Hi,

We haven't really started on the implementation yet; we have been
spending most of our time understanding the SSAPRE algorithm and
trying to figure out how to make it work for MLton's SSA form. The
tricky thing is that SSAPRE assumes all arguments to a phi function
are different versions of the same variable, and that no two versions
of the same variable are active at the same time. This can be violated
in MLton SSA, like:

L1 (a, b)
   x = a - b
   GOTO L1(b, a)

Here both 'b' and 'a' are arguments to the same phi function, but are
active at the same time.

SSAPRE uses the variable names to identify instances of an expression
to optimize and to determine which writes to variables will change the
value of the expression. For instance, it treats a_0 - b_3 and a_1 -
b_4 as the same expression, and considers writes to any version of a
or b to change its value.

So what we need are a set of expression instances to optimize together
and the set of variables that invalidate those expressions. We think
we know how to do this, but any insight is welcome. It will be nice to
fix this anyway, since I agree with Matthew that an algorithm that is
sensitive to the names of variables is pretty tasteless!

Some other stuff we discovered:

The PRE that we implement often won't be able to hoist loop-invariant
code because it is "while ..." style rather than "do ... while". This
code:

val g = _ffi "g" : int -> unit ;
val x = _ffi "x" : int ;
val y = _ffi "y" : int ;

fun f 0 = ()
  | f n =
    let in
      g (x - y);
      f (n - 1)
    end

val _ = f 10

.. becomes:

  L_0 ()
    x_3 = x
    y_0 = y
    f_0 (global_1)
  f_0 (x_1)
    case x_1 of
      0 => L_4 | _ => L_5
  L_5 ()
    x_2 = Int_sub (x_3, y_0)
    g (x_2)
    x_0 = Int_sub (x_1, global_2)
    f_0 (x_0)
  L_4 ()
    L_3 (MLton_halt (global_0))

Here x - y is loop invariant, but can't be hoisted because it is not
anticipated anywhere outside of L_5. (The loop may not be executed at
all). I understand that most C compilers rewrite a "while(cond) stmts"
to "if (cond) do stmts while(cond)", which gives hoisting a safe place
to put code. I'm not sure what the corresponding translation would be
for (mutually) recursive functions, and I don't think we'll have time
to implement it in our project.


Also, I don't think we will be able to optimize overflowing arithmetic
(ie Transfer.Arith) for fear of crossing other effects. (Being
anticipated doesn't ensure that we'll conform to the meaning of the
original program in terms of order-of-effects.) But unchecked math and
all the other functional stuff should be fine, and the prospect of
moving the expensive stuff like datatype constructor application is
more appealing, anyway.


Later this week we're going to try to implement it. I'm sure I'll have
some questions then. To get started, I was wondering if there's a good
way to run the compiler from within SML/NJ's interactive loop? I can
compile it (CM.make "sources.cm" after "make" to build the lex/yacc
stuff) but I don't know how to invoke it. (Main.commandLine wants to
be called from the shell script with a heap..)


 - Tom


[ NEW! : http://tom7.org/       ]
[ OLD! : http://fonts.tom7.com/ ]



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel