conts, handlers, and liveness

[Stephen Weeks]

> allocate-registers.sig now uses the following Info.t type and just returns
> jumpInfo and funcInfo functions that return Info.t's (and handlerOffset
> for funcInfo).  All in all, a little bit cleaner now.
...

Why not the following?

      structure Info:
	 sig
	    datatype t =
	       T of {
		     limitCheck: Machine.LimitCheck.t,
		     (* Live operands at the beginning of the block.
		      *)
		     live: Machine.Operand.t list,
		     (* Live operands at the beginning of the block,
		      * excepting its formals
		      *)
		     liveNoFormals: Machine.Operand.t list,
		     (* Number of bytes in frame including return address.
		      * Live variables at the frame corresponding to the block.
		      *)
		     cont: {size: int,
			    live: Machine.Operand.t list} option,
		     (* Amount to subtract to get to the next frame.
		      *)
		     handler: {size: int} option
		     }
	 end

> I've run through all of the regression and benchmarks and after the
> initial translation from MachineIL to pseudo-x86, I find no differences
> between the liveness passed down from the MachineIL and the liveness I
> compute.  (I don't think this guarantees that the MachineIL's liveness
> info is correct (as in lfp of the liveness equations) -- just that it is a
> fixed point, because I'm just verifying that for each block, given what's
> stated as being live into the destinations of the transfers and what's
> stated as being live into the block are consistent with what's used and
> defed in the block.) 

Agreed.  Still, very good progress.

> Looking through all the examples, there are two reasons why I need to
> patch.  One is the unused argument example that I sent out earlier;
> something that might be of interest, in all of these cases, the jump that
> has the unused argument is a block of the form:
> 
>    fun L_2226 (x_3673) =
>       let
> 	 val _ = HandlerPop
>       in
> 	 (* some transfer, often a raise, but not always *)
>       end

L_2226 is a handler, and so must follow the handler calling convention, which
means it takes one argument, the exception.  That unused argument is
unavoidable.  But, x_3673 should not appear in any live list.

> The second reason I think I can fix in the backend.  Essentially, there
> are occasionally extraneous switch statements:
...
> So, the switch is first a switch on IntOrPointer and the int branch does a
> further switch (and backend adds the test to the live in variables), but
> both cases jump to L_148.  The function that builds the switch should
> check to see if all branches and the default have the same label, and if
> so turn it into a jump and not add the test to the live in variables.

This can sometimes be expressed in CPS.  If all non-value-carrying branches lead
to the same label, and there is no _ case, then create an _ case to that label
and remove the non-value-carrying branches.  But, if there is already a _ case,
then there is nothing that can be done.  Similarly, if all value-carrying
branches ignore their arguments and then jump to the same label, that could be
collapsed.

But somehow CPS doesn't feel like the right place for this.  It really belongs
an a lower level IL.  And since that doesn't exist right now :-), I guess
backend is the place to do it.