(* ssa-fn.sml * * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu) * All rights reserved. * * The IL is a combination of a block-structured tree and an SSA control-flow * graph of blocks. *) signature SSA = sig structure Op : OPERATORS datatype var = V of { name : string, (* name *) id : Stamp.stamp, (* unique ID *) useCnt : int ref, (* count of uses *) props : PropList.holder } datatype block = BLK of { id : Stamp.stamp, props : PropList.holder, preds : block list ref, succs : block list ref, phi : (var * var list) list ref, (* phi statements *) body : assign list ref, exit : transfer ref } and rhs = VAR of var | LIT of Literal.literal | OP of Op.rator * var list | CONS of var list (* tensor-value construction *) and transfer = EXIT | GOTO of block | COND of var * block * block | DIE | STABILIZE withtype assign = (var * rhs) (* we layer a block-structured statement tree over the CFG to preserve * the high-level control-flow structure for when we need to produce * code. *) datatype stmt = BLOCK of block | SEQ of stmt list | IF of { cond : var, trueBranch : stmt, falseBranch : stmt } | WHILE of { hdr : block, cond : var, body : stmt } val newVar : string -> var val newBlock : unit -> block (* val entryBlock : stmt -> block val nextBlock : stmt -> block *) end functor SSAFn (Op : OPERATORS) : SSA = struct structure Op = Op datatype var = V of { name : string, (* name *) id : Stamp.stamp, (* unique ID *) useCnt : int ref, (* count of uses *) props : PropList.holder } datatype block = BLK of { id : Stamp.stamp, props : PropList.holder, preds : block list ref, succs : block list ref, phi : (var * var list) list ref, (* phi statements *) body : assign list ref, exit : transfer ref } and rhs = VAR of var | LIT of Literal.literal | OP of Op.rator * var list | CONS of var list (* tensor-value construction *) and transfer = EXIT | GOTO of block | COND of var * block * block | DIE | STABILIZE withtype assign = (var * rhs) (* we layer a block-structured statement tree over the CFG to preserve * the high-level control-flow structure for when we need to produce * code. *) datatype stmt = BLOCK of block | SEQ of stmt list | IF of { cond : var, trueBranch : stmt, falseBranch : stmt } | WHILE of { hdr : block, cond : var, body : stmt } (* IL construction code *) fun newVar name = V{ name = name, id = Stamp.new(), useCnt = ref 0, props = PropList.newHolder() } fun newBlock () = BLK{ id = Stamp.new(), props = PropList.newHolder(), preds = ref[], succs = ref[], phi = ref[], body = ref[], exit = ref EXIT } (* local fun setParent (BLK{parent, ...}, s) = (parent := s) in fun mkIF (pre, cond, t, f) = let val s = IF{pre=pre, cond=cond, trueBranch=t, falseBranch=f} in setParent (pre, s); s end fun mkWHILE (hdr, cond, body) = let val s = WHILE{hdr=hdr, cond=cond, body=body} in setParent (hdr, s); s end end (* local *) *) (* fun entryBlock (BLOCK blk) = blk | entryBlock (SEQ(s1::_)) = entryBlock s1 | entryBlock (IF{pre, ...}) = entryBlock pre | entryBlock (WHILE{hdr, ...}) = entryBlock hdr fun nextBlock (BLOCK(_, next)) = nextBlock next | nextBlock (SEQ stms) = nextBlock(List.last stms) | nextBlock (IF{pre, ...}) = entryBlock pre | nextBlock (WHILE{hdr, ...}) = entryBlock hdr *) end