local refs

Matthew Fluet fluet@CS.Cornell.EDU
Fri, 30 Nov 2001 13:58:15 -0500 (EST)


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

For (2), you mean that a single variable might be left bound multiple
times.

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

Sounds good.  There is also the penalty of rewriting the program multiple
times, but, (2) itself shouldn't be too bad, because we only need to touch
the blocks where a localizable ref is mentioned.

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

I agree that the fix is local, but it "alters" the HandlerPush/Pop
structure of the program in a non-trivial(?) way.

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

I don't mind them hanging around; I just keep a "when HandlerPush/Pop go
away" todo list.  The only problem I see is that multiple passes that
invoke an SSA restore pass that alters handler push/pops might
artificially bias the results towards the case when we ignore
HandlerPush/Pop "hints".  On the other hand, inhibiting optimizations
when trying to adhere to the HandlerPush/Pop constraints is an argument
for ignoring them and infering a "better" set of execption stack
manipulations.

> > 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 make some revisions; combining a couple of walks over the program,
avoiding unecessary rewrites, etc. I'm running benchmarks and will report
later.

I agree that the simple (1),(2),(3) version you describe above should be
fairly fast.  But, the SSA restore pass will take some time.