[MLton-devel] Re: PRE in MLton

[Stephen Weeks]

> The PRE that we implement often won't be able to hoist loop-invariant
> code because it is "while ..." style rather than "do ... while". 
...
> 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.

This is a standard problem and the standard solution is to insert loop
preheaders.  See, e.g., page 410 of Appel's Modern Compiler
Implementation in ML.  Also, take a look at MLton's
ssa/loop-invariant.fun, which inserts preheaders for a very simple
kind of loop-invariant motion.  That pass was written a long time ago,
before we had SSA.  If I were going to write it today, I would use
loop forests (see DirectedGraph.LoopForest), which are a nice
generalization of simple one-node-entry loops.  We already have the
code for computing loop forests, DirectedGraph.loopForestSteensgaard.
We use it for signal check insertion and limit check insertion if you
want to see an example.  In any case its performance is OK and it
works.

One way or the other, it should be easy enough to write a simple
prepass to your pass that inserts preheaders, if not for loop forests
then at least for single entry loops.  And of course don't run the
simplifier in between, or it will eliminate useless preheaders.

> To get started, I was wondering if there's a good way to run the
> compiler from within SML/NJ's interactive loop?

There isn't.  I always use it from the shell, after doing a 'make
nj-mlton' if I've made changes.  You could modify main.sml and
main.sig to export the first definition of commandLine and then pass
it the arguments that the bin/mlton script does.  But I don't see any
advantage to doing so over just exporting the heap, since the time
spent in remaking is usually in the CM.make, not in writing the heap.

Here's a few more tips.  You can compile "-type-check true" to have
the IL display the types of variables.  You can compile "-keep ssa
-keep dot" to save .dot files in addition to the .ssa file.  This also
works if you use "-diag <ssa-pass-name>" to save the .ssa files before
and after a pass.  For example, I compiled your example with
"-detect-overflow false -keep dot -keep ssa" to generate the following
graph.

// MLton 20030312 (built Wed Mar 12 13:12:01 2003 on redhat71)
//   created this file on Tue Apr 15 15:05:19 2003.
// Do not edit this file.
// Flag settings: 
//    basis library: basis-2002
//    log2 (card size): 8
//    chunk: chunk per function
//    debug: false
//    defines: []
//    detect overflow: false
//    drop passes: []
//    eliminate overflow: true
//    exn history: false
//    gc check: Limit
//    handlers: Flow
//    host: self
//    host type: Linux
//    indentation: 3
//    includes: [mlton.h]
//    inline: NonRecursive {product = 320, small = 60}
//    input file: loop.ssa.main_0.cfg.dot
//    instrument: false
//    instrument Sxml: false
//    keep Machine: false
//    keep RSSA: false
//    keep SSA: true
//    keep diagnostics: []
//    keep dot: true
//    keep passes: []
//    lib dir: /usr/lib/mlton/self
//    limit check: loop headers (fullCFG = false, loopExits = true)
//    limit check counts: false
//    loop passes: 1
//    mark cards: true
//    may load world: true
//    native: true
//    native commented: 0
//    native live stack: false
//    native optimize: 1
//    native move hoist: true
//    native copy prop: true
//    native cutoff: 100
//    native live transfer: 8
//    native future: 64
//    native shuffle: true
//    native ieee fp: false
//    native split: Some 20000
//    new return: false
//    polyvariance: Some {rounds = 2, small = 30, product = 300}
//    profile: None
//    profile basis: false
//    profile IL: ProfileSource
//    profile split: [[]]
//    profile stack: false
//    safe: true
//    show basis used: false
//    show types: false
//    stack cont: false
//    static: false
//    TextIO buffer size: 4096
//    type check: false
//    use basis library: true
//    variant: header
//    verbosity: Top
digraph "main_0 control-flow graph" {
label = "main_0 control-flow graph"; { rank  = "min"; n0 }
n1 [fontcolor = "Black", shape = "box", label = "L_11 ()\lreturn ()\l"]
n2 [fontcolor = "Black", shape = "box", label = "L_10 (x_7)\lStdio_print (\"Toplevel ...)\lMLton_halt (1)\l"]
n2 -> n1 [label = "\n", style = "solid"]
n3 [fontcolor = "Black", shape = "box", label = "L_9 ()\lbug\l"]
n4 [fontcolor = "Black", shape = "box", label = "L_8 ()\lStdio_print (\"\\\\n\")\lexit_0 (1)\l"]
n4 -> n2 [label = "\n", style = "dashed"]
n4 -> n3 [label = "\n", style = "dotted"]
n5 [fontcolor = "Black", shape = "box", label = "print_0 (x_5)\lStdio_print (x_5)\lL_8 ()\l"]
n5 -> n4 [label = "\n", style = "solid"]
n6 [fontcolor = "Black", shape = "box", label = "L_5 ()\lprint_0 (\"Size\")\l"]
n6 -> n5 [label = "\n", style = "solid"]
n7 [fontcolor = "Black", shape = "box", label = "L_6 ()\lprint_0 (\"Subscript...)\l"]
n7 -> n5 [label = "\n", style = "solid"]
n8 [fontcolor = "Black", shape = "box", label = "L_7 (x_6)\lStdio_print (x_6)\lL_8 ()\l"]
n8 -> n4 [label = "\n", style = "solid"]
n9 [fontcolor = "Black", shape = "box", label = "L_4 (x_4)\lStdio_print (\"unhandled...)\lcase x_4\l"]
n9 -> n6 [label = "Size_0\n", style = "solid"]
n9 -> n7 [label = "Subscript_0\n", style = "solid"]
n9 -> n8 [label = "Fail_0\n", style = "solid"]
n10 [fontcolor = "Black", shape = "box", label = "L_3 ()\lbug\l"]
n11 [fontcolor = "Black", shape = "box", label = "L_2 ()\lx_3 = x_0 -? y_0\lg (x_3)\lx_2 = x_1 -? 1\lf_0 (x_2)\l"]
n11 -> n12 [label = "\n", style = "solid"]
n13 [fontcolor = "Black", shape = "box", label = "L_1 ()\lexit_0 (0)\l"]
n13 -> n9 [label = "\n", style = "dashed"]
n13 -> n10 [label = "\n", style = "dotted"]
n12 [fontcolor = "Black", shape = "box", label = "f_0 (x_1)\lcase x_1\l"]
n12 -> n11 [label = "default\n", style = "solid"]
n12 -> n13 [label = "0\n", style = "solid"]
n0 [fontcolor = "Black", shape = "box", label = "L_0 ()\lx_0 = x ()\ly_0 = y ()\lf_0 (10)\l"]
n0 -> n12 [label = "\n", style = "solid"]
}


-------------------------------------------------------
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