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

SCM Repository

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

View of /branches/vis12-cl/src/compiler/IL/ssa-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2819 - (download) (annotate)
Sun Nov 9 02:20:26 2014 UTC (4 years, 9 months ago) by jhr
File size: 15831 byte(s)
  porting changes from vis12 branch
(* 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 {                     (* local-variable assignment *)
            pred : node ref,
            stm : assign,
            succ : node ref
          }
      | MASSIGN of {                    (* multi-assignment *)
            pred : node ref,
            stm : massign,
            succ : node ref
          }
      | GASSIGN of {                    (* global variable assignment *)
            pred: node ref,
            lhs : global_var,
            rhs : var,
            succ : node ref
          }
      | NEW of {                        (* create new strand instance *)
            pred : node ref,
            strand : Atom.atom,
            args : var list,
            succ : node ref
          }
      | SAVE of {                       (* save state variable *)
            pred: node ref,
            lhs : state_var,
            rhs : var,
            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
      = GLOBAL of global_var            (* read global variable *)
      | STATE of state_var              (* read strand state variable *)
      | VAR of var
      | LIT of Literal.literal
      | OP of Op.rator * var list
      | APPLY of MathFuns.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_MULTIOP of int * Op.rator * var list
                                        (* n'th result of operator in multi-assignment *)
      | VB_PHI of var list              (* defined by a phi node *)
      | VB_PARAM                        (* parameter to a strand *)

  (***** global variables *****)
    and global_var = GV of {
        id : Stamp.stamp,               (* variable's unique ID *)
        name : string,                  (* variable's name *)
        ty : Ty.ty,                     (* variable's type *)
        bind : var ref,                 (* binding *)
        useCnt : int ref,               (* count of uses *)
        input : bool,                   (* true for input variables *)
        props : PropList.holder
      }

  (***** strand state variables *****)
    and state_var = SV of {
        id : Stamp.stamp,               (* variable's unique ID *)
        name : string,                  (* variable's name *)
        ty : Ty.ty,                     (* variable's type *)
        output : bool,                  (* true for output variables *)
        props : PropList.holder
      }

    withtype assign = (var * rhs)
         and massign = (var list * Op.rator * var list)
         and phi = (var * var list)

    datatype assignment
      = ASSGN of assign
      | MASSGN of massign
      | GASSGN of (global_var * var)
      | SAV of (state_var * var)

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

    datatype program = Program of {
        props : StrandUtil.program_prop list,
        globals : global_var list,      (* global variables (both input and non-input) *)
        inputInit : cfg,                (* CFG to initialize input globals (if any) *)
        globalInit : cfg,               (* CFG to initialize other globals (if any) *)
        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 : state_var list,
        stateInit : cfg,
        methods : method list
      }

    and method = Method of {
        name : StrandUtil.method_name,
        body : cfg              (* method body *)
      }

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

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

  (* 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 : assignment 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 CFG *)
        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
      (* prepend a node to a CFG *)
        val prependNode : node * cfg -> cfg
      (* append a node to a CFG *)
        val appendNode : cfg * node -> cfg
      (* insert a block of assignments at the beginning of the CFG.  If the CFG has an ENTRY
       * node, then the block is inserted immediatly following the entry.
       *)
        val prependBlock : assignment list * cfg -> cfg
      (* insert a block of assignments at the end of the CFG argument  If the CFG has an EXIT
       * node, then the block is inserted immediatly following the exit.
       *)
        val appendBlock : cfg * assignment list -> 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 with NULL kind *)
        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 mkMASSIGN : massign -> node
        val mkGASSIGN : (global_var * var) -> node
        val mkNEW : {strand : Atom.atom, args : var list} -> node
        val mkSAVE : (state_var * var) -> node
        val mkEXIT : ExitKind.kind * var list -> node
        val mkFRAGMENT : var list -> node
        val mkSINIT : unit -> node
        val mkRETURN : var list -> node
        val mkACTIVE : unit -> node
        val mkSTABILIZE : unit -> 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
    val massignToString : massign -> string
    val assignmentToString : assignment -> string

  end

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