local refs

[Stephen Weeks]

> > Cool.  It looks like more refs (x_156, x_158) could be eliminated with
> > a subsequent pass.  
> 
> I don't think so.
...

OK.  Makes sense.

> Yes.  I've been sort of thinking about which passes are "idempotent," in
> the sense that running the pass twice in a row will never differ from
> running the pass once; 
...
> My guess is that the shrinker itself is not. 

It's not.  At some point, maybe 3 years ago, I went to the trouble to
write a shrinker for SXML that was idempotent, similar to the
description in the Appel/Jim paper.  It was, as they conjectured, very
messy and not worth the trouble, since the shrinker gets most redexes
on round 1, and almost all by round 2.  Especially in our case where
the shrinker runs 20 times or so anyways.  Although it probably
wouldn't hurt for us to run one extra round of shrinking at the end of
simplification.

> At present, localRef is not.  In particular if an 'a ref ref is
> localizable, then the 'a ref which it wraps might itself be localizable.

Exactly the case I was thinking of, and similarly the interaction with
local-flattening, where the ref is stuck in a locally-flattenable
tuple.

> I would think that idempotence is a desirable property, but not crucial.
> If nothing else, it drops the annoyance factor of seeing a pass look like
> it is leaving around the case it was supposed to optimize.

I agree it's nice, but not worth worrying about too much.

I have a couple more questions about localRefs.

1. Is it necessary for the transformation to traverse the dominator
tree instead of the DFS tree?

2. In the following program, why isn't func (aka global_17) localized?
I looked at the diagnostics and global_17's isLocal = true, but for
some reason, it still appears in the output.

val pi' = _ffi "printf": string * int -> int;
val pi = fn i => pi'("%i\n\000", i)

val ps' = _ffi "printf": string * string -> int;
val ps = fn s => ps'("%i\n\000", s)

fun fib 0 = 1
  | fib 1 = 1
  | fib n = (fib (n + 1)) + (fib (n + 1))

fun tak (x,y,z)
  = if not (y < x)
      then z
      else tak (tak (x - 1, y, z),
		tak (y - 1, z, x),
		tak (z - 1, x, y))

val w = MLton.Random.rand ()

val func = ref ""

val n = (if Word.andb(w,0wx1) = 0wx0
	   then (func := "fib";
		 fib 20)
	   else (func := "tak";
		 tak (1,2,3)))
        handle _ => (ps (!func); 0)

val _ = pi n