Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] View of /trunk/src/compiler/IL/ssa-sig.sml
ViewVC logotype

View of /trunk/src/compiler/IL/ssa-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1232 - (download) (annotate)
Mon May 16 23:37:52 2011 UTC (8 years, 4 months ago) by jhr
File size: 9231 byte(s)
  Porting many changes from the pure-cfg branch, including value numbering
  and support for parallel execution on SMP systems.
(* ssa-sig.sml
 *
 * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
 * All rights reserved.
 *
 * The SSA signature is the signature of the HighIL, MidIL, and LowIL modules, which implement
 * the core intermediate languages of the Diderot compiler.  These ILs have the same program
 * and control-flow structure, but differ in their types and operators.
 *
 * Some properties:
 *
 *	1) The exit of the globalInit CFG has kind RETURN and the scope of the live variables
 *	   is the whole program.
 *
 *	2) The scope of the parameters of a strand is the stateInit CFG and the methods of the
 *	   strand.
 *
 *	3) Each strand has a list of strand-state variables (the "state" field).  These variables
 *	   are not defined or used in the code, but serve as the "master template" for the
 *	   strand's state.
 *
 *	4) The exit of the stateInit CFG in a strand has kind SINIT and the number of live
 *	   variables should be the same as the number of variables in the strand's state-variable
 *	   list.
 *
 *	5) Each method has a list of variables, called stateIn, which corresponds to the
 *	   variables in the strand's state-variable list.
 *
 *	6) The exit node(s) of the update method should have kind ACTIVE, STABILIZE, or DIE.
 *	   The live variables at a ACTIVE or STABILIZE exit correspond to the variables in
 *	   the strand's state-variable list.  (Note that this property is modified after the
 *	   variable-analysis phase).
 *)

signature SSA =
  sig

    val ilName : string

    structure Ty : SSA_TYPES
    structure Op : OPERATORS where type ty = Ty.ty

  (***** CFG *****)

    datatype cfg = CFG of {
	entry : node,	(* the entry node of a graph; not necessarily an ENTRY node *)
	exit : node	(* the exit node of a graph; not necessarily an EXIT node. *)
      }

    and node = ND of {
	id : Stamp.stamp,
	props : PropList.holder,
	kind : node_kind
      }

    and node_kind
      = NULL
      | ENTRY of {
	    succ : node ref
	  }
      | JOIN of {
	    preds : node list ref,
	    phis : phi list ref,
	    succ : node ref
	  }
      | COND of {
	    pred : node ref,
	    cond : var,
	    trueBranch : node ref,
	    falseBranch : node ref
	  }
      | COM of  {			(* comment *)
	    pred : node ref,
	    text : string list,
	    succ : node ref
	  }
      | ASSIGN of {			(* assignment *)
	    pred : node ref,
	    stm : assign,
	    succ : node ref
	  }
      | NEW of {			(* create new strand instance *)
	    pred : node ref,
	    strand : Atom.atom,
	    args : var list,
	    succ : node ref
	  }
      | EXIT of {			(* includes die and stabilize *)
	    pred : node ref,
	    kind : ExitKind.kind,	(* kind of exit node *)
	    live : var list		(* live variables *)
	  }

    and rhs
      = VAR of var
      | LIT of Literal.literal
      | OP of Op.rator * var list
      | APPLY of ILBasis.name * var list (* basis function application *)
      | CONS of Ty.ty * var list	(* tensor/sequence-value construction *)

    and var = V of {
	name : string,			(* name *)
	id : Stamp.stamp,		(* unique ID *)
	ty : Ty.ty,			(* type *)
	bind : var_bind ref,		(* binding *)
	useCnt : int ref,		(* count of uses *)
	props : PropList.holder
      }

    and var_bind
      = VB_NONE
      | VB_RHS of rhs			(* defined by an assignment (includes globals and state variables) *)
      | VB_PHI of var list		(* defined by a phi node *)
      | VB_PARAM			(* parameter to a strand *)

    withtype assign = (var * rhs)
	 and phi = (var * var list)


  (***** Program representation *****)

    datatype program = Program of {
	globalInit : cfg,
	initially : initially,
	strands : strand list
      }

    and initially = Initially of {
	isArray : bool,			(* true for initially array, false for collection *)
	rangeInit : cfg,		(* code to compute bounds of iteration *)
	iters : (var * var * var) list, (* "for" i = min .. max *)
	create : (cfg * Atom.atom * var list)
      }

    and strand = Strand of {
	name : Atom.atom,
	params : var list,
	state : (bool * var) list,	(* output variables are marked with true *)
	stateInit : cfg,
	methods : method list
      }

    and method = Method of {
	name : Atom.atom,
	stateIn : var list,	(* names of state variables on method entry *)
	body : cfg		(* method body *)
      }

  (* operations on CFGs *)
    structure CFG : sig
      (* the empty CFG *)
	val empty : cfg
      (* is a CFG empty? *)
	val isEmpty : cfg -> bool
      (* create a basic block from a list of assignments *)
	val mkBlock : assign list -> cfg
      (* entry/exit nodes of a CFG *)
	val entry : cfg -> node
	val exit : cfg -> node
      (* return the list of variables that are live at exit from a CFG *)
	val liveAtExit : cfg -> var list
      (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will
       * be in preorder with parents before children.
       *)
	val sort : cfg -> node list
      (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)
	val apply : (node -> unit) -> cfg -> unit
(*
      (* rewrite a CFG by applying a partial function to the nodes in the graph.  If NONE is returned,
       * then no change to the node, if SOME(cfg) is returned, then the node is replaced by the
       * subgraph, which may be empty.  This function returns true if any nodes were rewritten.
       *)
	val rewrite : (node -> cfg option) -> cfg -> bool
*)
      (* delete a simple node from a CFG *)
	val deleteNode : node -> unit
      (* replace a simple node in a cfg with a different simple node *)
	val replaceNode : (node * node) -> unit
      (* replace a simple node in a cfg with a subgraph *)
	val replaceNodeWithCFG : (node * cfg) -> unit
      (* concatenate two CFGs *)
	val concat : cfg * cfg -> cfg
      (* append a node to a CFG *)
	val appendNode : cfg * node -> cfg
      (* update the exit of a CFG by modifying the live variable list *)
	val updateExit : cfg * (var list -> var list) -> cfg
      end

  (* operations on CFG nodes *)
    structure Node : sig
	val id : node -> Stamp.stamp
	val kind : node -> node_kind
	val same : node * node -> bool
	val compare : node * node -> order
	val hash : node -> word
	val toString : node -> string
	val isNULL : node -> bool
      (* variable defs and uses; may include duplicates *)
	val uses : node -> var list
	val defs : node -> var list
      (* dummy node *)
	val dummy : node
      (* CFG edges *)
	val hasPred : node -> bool
	val preds : node -> node list
	val setPred : node * node -> unit
	val hasSucc : node -> bool
	val succs : node -> node list
	val setSucc : node * node -> unit
	val setTrueBranch : node * node -> unit	 (* set trueBranch successor for COND node *)
	val setFalseBranch : node * node -> unit (* set falseBranch successor for COND node *)
	val addEdge : node * node -> unit
      (* replace the edge src-->oldDst by the edge src-->dst *)
	val replaceInEdge : {src : node, oldDst : node, dst : node} -> unit
      (* replace the edge oldSrc-->dst by the edge src-->dst *)
	val replaceOutEdge : {oldSrc : node, src : node, dst : node} -> unit
      (* constructors *)
	val mkENTRY : unit -> node
	val mkJOIN : (var * var list) list -> node
	val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node
	val mkCOM : string list -> node
	val mkASSIGN : assign -> node
	val mkNEW : {strand : Atom.atom, args : var list} -> node
	val mkEXIT : ExitKind.kind * var list -> node
	val mkFRAGMENT : var list -> node
	val mkSINIT : var list -> node
	val mkRETURN : var list -> node
	val mkACTIVE : var list -> node
	val mkSTABILIZE : var list -> node
	val mkDIE : unit -> node
      (* properties *)
	val newProp : (node -> 'a) -> {
		getFn : node -> 'a,
		peekFn : node -> 'a option,
		setFn : node * 'a -> unit,
		clrFn : node -> unit
	      }
	val newFlag : unit -> {
		getFn : node -> bool,
		setFn : node * bool -> unit
	      }
      end

  (* operations on variables *)
    structure Var : sig
	val new : string * Ty.ty -> var
	val copy : var -> var
	val name : var -> string
	val ty : var -> Ty.ty
	val binding : var -> var_bind
	val setBinding : var * var_bind -> unit
	val useCount : var -> int
	val same : var * var -> bool
	val compare : var * var -> order
	val hash : var -> word
	val toString : var -> string
      (* properties *)
	val newProp : (var -> 'a) -> {
		getFn : var -> 'a,
		peekFn : var -> 'a option,
		setFn : var * 'a -> unit,
		clrFn : var -> unit
	      }
	val newFlag : unit -> {
		getFn : var -> bool,
		setFn : var * bool -> unit
	      }
      (* collections *)
	structure Map : ORD_MAP where type Key.ord_key = var
	structure Set : ORD_SET where type Key.ord_key = var
	structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var
      end

  (* operations on RHS expressions *)
    structure RHS : sig
	val toString : rhs -> string
	val vars : rhs -> var list
	val map : (var -> var) -> rhs -> rhs
	val app : (var -> unit) -> rhs -> unit
      end

  (* return a string representation of a variable binding *)
    val vbToString : var_bind -> string

  (* return a string representation of a PHI node *)
    val phiToString : phi -> string

  (* return a string representation of an assignment *)
    val assignToString : assign -> string

  end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0