RSSA

[Stephen Weeks]

Here's my first attempt at RSSA, an IL that sits between SSA and
MACHINE.  It is like SSA in that it has variables and functions.  It
is like MACHINE in that representations are explicit.

The idea is to split what is currently the backend into two pieces,
one to translate from SSA to RSSA, and the other from RSSA to MACHINE.

SSA -> RSSA involves
	* implementing handlers
	* deciding representations (of tuples, datatypes)
	* making allocation explicit
	* inserting limit checks

RSSA -> MACHINE involves
	* deciding stack layout
	* computing liveness info
	* pseudoregister allocation

I don't claim that RSSA is type checkable.  But I do hope to be able
to do limit check insertion and verification on it.

The main things to notice are the new Exps for allocting and offsets,
the new Transfer for limit checks, and the fact that RSSA only uses
simple machine types.

Comments solicited.  :-)

--------------------------------------------------------------------------------

type int = Int.t
type word = Word.t
   
signature RSSA_STRUCTS = 
   sig
      include ATOMS
   end

signature RSSA = 
   sig
      include RSSA_STRUCTS

      structure Func: HASH_ID
      structure Label: HASH_ID
      structure Type: MTYPE

      structure Exp:
	 sig
	    datatype t =
	       Allocate of {numPointers: int,
			    numWordsNonPointers: int,
			    stores: {offset: int,
				     value: Var.t} Vector}
	     | AllocateArray of {numBytesNonPointers: int,
				 numElts: Var.t,
				 numPointers: int}
	     | ArrayOffset of {base: Var.t,
			       offset: Var.t,
			       ty: Type.t}
	     | Const of Const.t
	     | Offset of {base: Var.t,
			  offset: int} (* offset in bytes *)
	     | PrimApp of {prim: Prim.t,
			   args: Var.t vector}
	     | SetExnStackLocal
	     | SetExnStackSlot
	     | SetHandler of Label.t
	     | SetSlotExnStack
	 end

      structure Statement:
	 sig
	    datatype t = T of {var: Var.t option,
			       ty: Type.t,
			       exp: Exp.t}
	 end
      
      structure Cases: MACHINE_CASES sharing Label = Cases.Label

      structure Handler:
	 sig
	    datatype t =
	       CallerHandler
	     | None
	     | Handle of Label.t
	 end

      structure Return:
	 sig
	    datatype t =
	       Dead
	     | HandleOnly
	     | NonTail of {cont: Label.t, handler: Handler.t}
	     | Tail
	 end

      structure LimitCheck:
	 sig
	    datatype t =
	       Array of {numElts: Var.t,
			 bytesPerElt: int,
			 extraBytes: int} (* for subsequent allocation *)
	     | Heap of {bytes: int,
			stackToo: bool}
	     | Signal
	     | Stack
	 end
      
      structure Transfer:
	 sig
	    datatype t =
	       Arith of {prim: Prim.t,
			 args: Var.t vector,
			 overflow: Label.t, (* Must be nullary. *)
			 success: Label.t (* Must be unary. *)
			}
	     | Bug  (* MLton thought control couldn't reach here. *)
	     | Call of {func: Func.t,
			args: Var.t vector,
			return: Return.t}
	     | Case of {test: Var.t,
			cases: Label.t Cases.t,
			default: Label.t option (* Must be nullary. *)
		       }
	     | Goto of {dst: Label.t,
			args: Var.t vector
			}
	     | LimitCheck of {kind: LimitCheck.t,
			      return: Label.t}
	     (* Raise implicitly raises to the caller.  
	      * I.E. the local handler stack must be empty.
	      *)
	     | Raise of Var.t vector
	     | Return of Var.t vector
	     | Runtime of {prim: Prim.t,
			   args: Var.t vector,
			   return: Label.t (* Must be nullary. *)
			  }
	 end

      structure Block:
	 sig
	    datatype t =
	       T of {
		     label: Label.t,
		     args: (Var.t * Type.t) vector,
		     statements: Statement.t vector,
		     transfer: Transfer.t
		     }
	 end

      structure Function:
	 sig
	    datatype t = T of {args: (Var.t * Type.t) vector,
			       blocks: Block.t vector,
			       name: Func.t,
			       raises: Type.t vector option,
			       returns: Type.t vector option,
			       start: Label.t}
	 end
     
      structure Program:
	 sig
	    datatype t =
	       T of {
		     globals: Statement.t vector,
		     functions: Function.t list,
		     main: Func.t (* Must be nullary. *)
		    } 
	 end
   end