shrinker checked in

[Stephen Weeks]

> How does the shrinker deal with blocks that do nothing but goto another
> block?  The way the SSA shrinker works, it is completely nullifying the
> effect of commonBlock.  I can also find a number of instances of
> gotos-to-gotos that aren't eliminated.

Gotos-to-gotos, and in particular "eta" gotos like f (x) = g (x), are
not handled as well as in the CPS shrinker.  I think they could be,
but I wanted to go for a slightly simpler shrinker first just to get
it working.

> >   - Added mayRaise: bool to functions to record whether or not a function may
> >     raise.
> 
> Would it be worth replacing mayRaise with raises : Type.t vector option to
> match returns?  I know that this vector should be identical in all
> functions, but it would make things a little more uniform.

No objection here.  I can even imagine an optimization that represents
exceptions differently in different parts of the program.

> >   - Changed returns to the following datatype
> > 
> > 	    datatype t =
> > 	       Dead
> > 	     | HandleOnly
> > 	     | NonTail of {cont: Label.t, handler: Handler.t}
> > 	     | Tail
> 
> Seems a little complicated to me, but if it works.
> 
> I still don't quite understand why Caller/None is disallowed.  If the
> callee doesn't raise, won't the exception stack be exactly the same as it
> was at the call when the callee returns -- even if the callee installs and
> uninstalls handlers?  Maybe I'm missing some aspect of what a callee is
> allowed to do when it is called with a continuation or handler of None.

It's not what the callee can do.  I agree that our current convention
is that the callee preserves the exception stack, essentially treating
the global (per thread) exception stack pointer as a callee save
register.  The problem is that None means that the *caller* can leave
the exception stack in *any* state that it likes.  But that means that
when the callee returns (as it is allowed to do with a Caller cont),
the exception stack will be in that same *any* state.  But the
continuation may refer to the exception stack.  Hence, Caller/None
doesn't make sense -- it only makes sense to have Caller/Caller,
i.e. Tail.

Thinking of it from a continuation-passing, exception-stack passing
style with callee-save registers, the continuation expects to be
passed the exception stack pointer, so it must be set to whatever the
continuation needs before calling the callee.

> was thinking that while the callee won't return to either the continuation
> or exception stack, it should preserve both stacks.  For example, we could
> conceivable implement a None/None (Dead) call by a "tail call" that
> adjusts the stack all the way to stackBottom; i.e., trash the entire stack
> (continuation and exception) because we can't possibly return to them.

I would like to do this.  In fact, I bet Henry would argue we are
required to.

> Similarly, None/Caller (HandleOnly) is implemented as a normal tail
> call.  This makes sense, because the handler stack is intertwined in the
> continuation stack, so we can't really trash the continuation stack; 
> although, again, conceivably we could implement it as a tail call that
> trashes the stack down to the frame that has the top handler. 

I would like to do this too.