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.