ssa restore

[Matthew Fluet]

How "broken" an ssa function should the ssa restore pass handle?

The localRef pass will introduce specific violations
 1. multiple let bindings of a variable
with specific properties
 2. one binding dominates all uses and other bindings

This let me simplify the restore pass in localRef, because only blocks
dominated by the first binding of a local ref were candidates for carring
the ref in arguments.

The knownCase pass will probably introduce multiple let and arg bindings
of a variable, every path through the CFG to a use of a variable will pass
through a binding (but, no single binding dominates all uses and other
bindings).  Here's the transformation I have in mind:

Input program:

L_CS ()
  val z = SOME g
  L_C (z)
L_CN ()
  val y = NONE
  L_C (y)
L_X ()
  L_C (f ())
L_C (x)
  case x
    of SOME => L_S 
     | NONE => L_N
L_S (a)
  val _ = print "Returning SOME"
  x
L_N ()
  val _ = print "Returning NONE"
  x

At L_C, the case is sometimes "known", so rewrite to

L_CS ()
  val z = SOME g
  val x = z
  L_S (g)
L_CN ()
  val y = NONE
  val x = z
  L_N ()
L_X ()
  L_C (f ())
L_C (x)
  case x
    of SOME => L_S 
     | NONE => L_N
L_S (a)
  val _ = print "Returning SOME"
  x
L_N ()
  val _ = print "Returning NONE"
  x

There are now three bindings of x, two let bindings and one arg binding.


What other kinds of optimizations do we think will be sent at the ssa
restore?  And how will they break the ssa invariants?