local refs

[Matthew Fluet]

> Cool.  It looks like more refs (x_156, x_158) could be eliminated with
> a subsequent pass.  

I don't think so.

  L_161 ()
    x_268 = Ref_ref (global_26)
    x_197 = Ref_ref (global_26)
    x_156 = Ref_ref (global_2)
    x_158 = Ref_ref (global_2)
    x_155 = Array_array (global_25)
    x_296 = (x_155, x_197, x_268, x_220, x_156, x_158)
    x_297 = Ref_deref (openIns_0)
    x_295 = ::_5 (x_297, x_296)
    Ref_assign (openIns_0, x_295)
    loop_21 (global_2)

x_156 and x_158 "escape" into tuple x_296, which is added to the openIns_0
list ref.  They are subsequently used and assigned to via a loop over the
openIns_0 list.

Now, it does turn out that the openIns_0 list ref is sort of localizable,
because it is only ever escapes at
    x_380 = Env_0 (openIns_0, openIns_0)
which is the only value with tag Env_0 constructed in the program, so at
the one case on Env_0, we could replace the arguments there with
openIns_0, which would make openIns_0 localizable.  I still don't think
that will make x_156 and x_158 localizable.

> Or maybe you could do a more precise analysis
> (possibly combined with local flattening?) to catch them all on one
> pass?  

Maybe.  I don't think this applies to the case above.  You are correct
that the analysis is somewhat simplistic.  A ref "escapes" whenever it is
used in any expression or transfer other than Ref_assign or Ref_deref.

> Actually, it looks to me like local flattening suffers from the
> same weakness -- it won't flatten a tuple that is stored inside
> another tuple, even if that other tuple is flattened.  To do so
> requires a more complex analysis that does a dataflow analysis on the
> entire type, not just the topmost level in the type.

And a more complicated transformation.

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; (you probably have to take this modulo the
shrinker, because a serious ammount of constant propagation may reveal new
opportunities; although, that complicates the definition, because some
passes require the shrinker to clean up an ill formed program, meaning
that the output of the pass may not be suitable for input to the pass.)
Contification certainly is. RemoveUnused is.  I believe commonSubexp is. 
PolyEqual is (although that probably shouldn't count).  IntroduceLoops
should be.  LocalFlatten is not.  My guess is that the shrinker itself is
not.  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.

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.

In thinking about the knownCase analysis/transformation, a "simple"
version is easy, but I've been trying to think about how to write it so
that it is idempotent.  But, it's not clear how.