local refs

[Stephen Weeks]

> I was getting tired of looking at the code for printing 
> "toplevel handler not installed" in every program when the toplevel
> handler was clearly installed.  

Ahh yes, the great motivator for new optimizations -- making the
empty program empty.  :-)

> So, I started in on a local ref
> elimination pass, which will also turn accumulation refs into function
> local variables.

Sounds good.  It's been on my todo list forever.  I would structure it
in three phases:

1. an analysis, much like you describe
2. a simple transformation, that rewrites Ref_assign as variable
   bind (assign) and Ref_deref as variable reference
3. an SSA transformation that takes an SSA program that does not meet
   the single assignment condition and restores the condition.

Your transformation combined (2) and (3), and included a
less-than-optimal SSA conversion.  Since we need SSA conversion for
some other optimizations as well, I would rather (someone) think a
while and write a good SSA conversion pass, but keep local refs
simple.

The handler problems are part of (3), not (2).  I see the problem, and
it is unfortunate that HandlerPush/Pop are creating so many problems.
I just can't seem to get stuff off the top of my todo fast enough to
get to the paper.  Anyways, if a handler is indeed a join point for a
variable that needs to be SSA'ed, I don't see any fix other than to
rewrite the handlers.  If we're going to have an SSA algorithm that
will work for any input in the current world with HandlerPush/Pop,
then I see no choice but to insert the approriate HandlerPush/Pop -- I
don't want to restrict the input to the SSA algorithm.

I think the fix can be done completely locally.  If L_5 is a join
point used in two different calls and you want to insert a new handler
at the calls, you need to put a HandlerPush before each call with the
new handler (L_41 or L_44) and have L_41 and L_44 start with a
HandlerPop and follow with a jump to L_5, passing the merged
variables.

Another fix would be to drop HandlerPush/Pop entirely.  I could be
convinced, but I do think it would be nice in the exceptions paper to
compare to the approach using them.

> There is currently one bug with the localization of global refs.  It
> doesn't suffice that the global ref is only used in one function -- it
> needs to be only used in one function that is invoked at most once.

Yep.

> I'm working on a fix and on speeding up the pass;
> Overall, though, I'm afraid that it is going to be overly expensive for
> little gain.

I don't see why it should be that expensive.  In particular, I don't
think the "flattening" of local refs should be any slower than, say,
LocalFlatten.  The SSA algorithm will take some work, but we need it
anyways.

I really want the flattening of local refs so that we will generate
exactly them same code for loops whether they are written in
functional or imperative style.