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

SCM Repository

[diderot] View of /branches/vis12/src/compiler/tree-il/var-analysis.sml
ViewVC logotype

View of /branches/vis12/src/compiler/tree-il/var-analysis.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2802 - (download) (annotate)
Sat Nov 8 14:17:50 2014 UTC (4 years, 11 months ago) by jhr
File size: 9597 byte(s)
  new version of the Variable Analysis phase.  This mostly fixes bug 031, but
  there are still some C code generation issues that may (or may not) be
  related, so I'm not closing it yet.
(* var-analysis.sml
 *
 * COPYRIGHT (c) 2014 The Diderot Project (http://diderot-language.cs.uchicago.edu)
 * All rights reserved.
 *
 * The variable analysis phase does the following things:
 *
 *   1) determine which strand parameters are used in methods (and thus have to be
 *      shadowed by instance variables).
 *
 *   2) determine which strand state variables are invariant across the strand
 *      execution.
 *
 *   3) determine strand state variables that are only used in strand initialization and thus
 *	can be demoted to locals (not outputs!)
 *
 * TODO
 *
 *   4) determine which strand state variables are invariant over all strands and thus
 *      can be lifted to global scope
 *)

structure VarAnalysis : sig

    structure IL : SSA

    val optimize : IL.program -> IL.program

  (* returns true if the state variable is invariant over strand execution *)
    val isVarying : IL.state_var -> bool

  end = struct

    structure IL = LowIL
    structure V = IL.Var
    structure StV = IL.StateVar
    structure VMap = V.Map
    structure SVMap = StV.Map
    structure ST = Stats

  (********** Counters for statistics **********)
    val cntPromote              = ST.newCounter "low-var:promote-param"
    val cntInv                  = ST.newCounter "low-var:invariant"
    val cntUnusedState          = ST.newCounter "low-var:unused-state"
    val cntUnused               = ST.newCounter "low-var:unused"
    val firstCounter            = cntPromote
    val lastCounter             = cntUnused

    structure UnusedElim = UnusedElimFn (
        structure IL = IL
        val cntUnused = cntUnused)

    fun reduce cfg = if UnusedElim.reduce cfg then reduce cfg else cfg

  (* boolean flag on strand parameters that are referenced in methods *)
    val {getFn=paramUsedInMethod, setFn=setParamUsedInMethod} = V.newFlag ()

  (* boolean flag on strand-state variables that vary across method executions *)
    val {getFn=isVarying, setFn=setVarying} = StV.newFlag ()

  (* boolean flag on strand-state variables that are referenced in methods *)
    val {getFn=stateUsedInMethod, setFn=setStateUsedInMethod} = StV.newFlag ()

  (* general iterator for processing state-variable defs and uses, and regular variable uses
   * in a CFG.
   *)
    fun checkCFG {svDef, svUse, vUse} cfg = let
	  fun doNode nd = (case IL.Node.kind nd
		 of IL.ASSIGN{stm=(lhs, IL.STATE rhs), ...} => svUse rhs
		  | IL.SAVE{lhs, rhs, ...} => svDef (lhs, rhs)
		  | _ => List.app vUse (IL.Node.uses nd)
		(* end case *))
	  in
	    IL.CFG.apply doNode cfg
	  end

    fun analyseStrand (params, state, methods) = let
	(* check the code of a method for state-variable updates, state-variable uses,
	 * and references to parameters
	 *)
	  fun analMethod (IL.Method{body, ...}) = checkCFG {
		  svDef = fn (lhs, rhs) => (case V.binding rhs
		     of IL.VB_RHS(IL.STATE x) =>
			  if StV.same(x, lhs)
			    then ()
			    else setVarying(lhs, true)
		      | _ => setVarying(lhs, true)
		    (* end case *)),
		  svUse = fn x => setStateUsedInMethod(x, true),
		  vUse = fn x => (case V.binding x
		     of IL.VB_PARAM => setParamUsedInMethod(x, true)
		      | _ => ()
		    (* end case *))
		} body
	(* analyse the methods *)
	  val _ = List.app analMethod methods
	(* mark output state variables as being used in methods (even if they are not) *)
	  val _ = List.app
		(fn x => if StV.isOutput x then setStateUsedInMethod(x, true) else ())
		  state
	(* compute the list of parameters that need to be shadowed by state variables
	 * because they are referenced in a method.
	 *)
	  val shadowParams = List.filter paramUsedInMethod params
	  val _ = ST.bump (cntPromote, List.length shadowParams)
	(* compute the list of state variables that can be demoted to local variables, because
	 * they are not used in any method.
	 *)
	  val (used, unused) = List.partition stateUsedInMethod state
	  val _ = ST.bump (cntUnusedState, List.length unused)
	(* are there any invariant state variables? *)
	  val numInvariant = let
		fun chk (x, n) = if (not (isVarying x)) then n+1 else n
		in
		  List.foldl chk 0 state
		end
	  val _ = ST.bump (cntInv, numInvariant)
	  in {
	    anyInvariant = (numInvariant > 0),
	    shadowParams = shadowParams,
	    usedState = used,
	    unusedState = unused
	  } end

  (* create new state variables to shadow strand parameters that are referenced in methods.
   *)
    fun mkShadowState [] = ([], [], fn () => ([], VMap.empty))
      | mkShadowState xs = let
	  fun mk (x, (svs, stms, mapping)) = let
		val sv = StV.new(false, V.name x, V.ty x)
		val stm = IL.SAV(sv, x)
		in
		  LowILCensus.inc x;
		  (sv::svs, stm::stms, (x, sv)::mapping)
		end
	  val (svs, stms, mapping) = List.foldr mk ([], [], []) xs
	  fun loadParamShadows () = let
		fun f ((x, sv), (stms, env)) = let
		      val x' = V.copy x
		      in
			(IL.ASSGN(x', IL.STATE sv)::stms, VMap.insert(env, x, x'))
		      end
		in
		  List.foldr f ([], VMap.empty) mapping
		end
	  in
	    (svs, stms, loadParamShadows)
	  end

  (* rewrite the state initialization CFG.  We need to add code to initialize the new state
   * variables and we need to remove initialization for any unused state variables.  The
   * arguments are the original CFG, the new initialization statements, and a flag that
   * is true if there are unused state variables to be eliminated.
   *)
    fun rewriteStateInit (stateInit, [], false) = stateInit
      | rewriteStateInit (stateInit, initStms, anyUnused) = let
	(* process the CFG nodes by removing SAVEs of unused state variables *)
	  fun doNode nd = (case IL.Node.kind nd
		 of IL.SAVE{lhs, rhs, ...} => if (stateUsedInMethod lhs)
		      then ()
		      else (LowILCensus.dec rhs; IL.CFG.deleteNode nd)
		  | _ => ()
		(* end case *))
	  val _ = if anyUnused then IL.CFG.apply doNode stateInit else ()
	  val cfg = IL.CFG.appendBlock (stateInit, initStms)
	  in
	    reduce cfg
	  end

    fun rewriteMethod loadParamShadows (IL.Method{name, body}) = let
	  val (loadStms, env) = loadParamShadows()
	(* rename used parameters *)
	  fun rename x = (case VMap.find (env, x)
		 of NONE => x
		  | SOME x' => (
		    (* replacing x with x', so adjust census counts *)
		      LowILCensus.dec x; LowILCensus.inc x';
		      x')
		(* end case *))
	(* process method-body nodes.  We rename parameters to the local variable that
	 * is read out from the shadow state variable and we remove save nodes for non-varying
	 * state variables.
	 *)
	  fun doNode nd = let
		fun changed x = VMap.inDomain(env, x)
		val renameList = List.map rename
		in
		  case IL.Node.kind nd
		   of IL.JOIN{phis, ...} => let
			fun doPhi (lhs, rhs) = (lhs, renameList rhs)
			in
			  phis := List.map doPhi (!phis)
			end
		    | IL.COND{pred, cond, trueBranch, falseBranch} =>
			if changed cond
			  then let
			    val newNd = IL.Node.mkCOND {
				    cond = rename cond,
				    trueBranch = !trueBranch,
				    falseBranch = !falseBranch
				  }
			    in
			      IL.Node.replaceInEdge {src = !pred, oldDst = nd, dst = newNd};
			      IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !trueBranch};
			      IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !falseBranch}
			    end
			  else ()
		    | IL.ASSIGN{stm=(lhs, rhs), ...} => let
			fun replace rhs = IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(lhs, rhs))
			in
			  case rhs
			   of IL.GLOBAL x => ()
			    | IL.STATE x => if stateUsedInMethod x
				then ()
				else IL.CFG.deleteNode nd
			    | IL.VAR x => if changed x
				then replace (IL.VAR(rename x))
				else ()
			    | IL.LIT _ => ()
			    | IL.OP(rator, args) => if List.exists changed args
				then replace (IL.OP(rator, renameList args))
				else ()
			    | IL.APPLY(f, args) => if List.exists changed args
				then replace (IL.APPLY(f, renameList args))
				else ()
			    | IL.CONS(ty, args) => if List.exists changed args
				then replace (IL.CONS(ty, renameList args))
				else ()
			  (* end case *)
			end
		    | IL.MASSIGN{stm=(lhs, rator, args), ...} =>
			if List.exists changed args
			  then IL.CFG.replaceNode(nd, IL.Node.mkMASSIGN(lhs, rator, renameList args))
			  else ()
		    | IL.NEW{strand, args, ...} =>
			if List.exists changed args
			  then IL.CFG.replaceNode(
			    nd,
			    IL.Node.mkNEW{strand=strand, args=renameList args})
			  else ()
		    | IL.SAVE{lhs, rhs, ...} => if (isVarying lhs)
			then ()
			else (LowILCensus.dec rhs; IL.CFG.deleteNode nd)
		    | _ => ()
		  (* end case *)
		end
	  val _ = IL.CFG.apply doNode body
	  in
	    IL.Method{
		name = name,
		body = reduce (IL.CFG.prependBlock (loadStms, body))
	      }
	  end

    fun rewriteStrand (strand as IL.Strand{name, params, state, stateInit, methods}) = (
	  case analyseStrand (params, state, methods)
	   of {anyInvariant=false, shadowParams=[], unusedState=[], ...} => strand
	    | {shadowParams, usedState, unusedState, ...} => let
		val (newState, initStms, loadParamShadows) = mkShadowState shadowParams
		in
		  IL.Strand{
		      name = name,
		      params = params,
		      state = usedState @ newState,
		      stateInit = rewriteStateInit (stateInit, initStms, List.null unusedState),
		      methods = List.map (rewriteMethod loadParamShadows) methods
		    }
		end
	  (* end case *))

    fun optimize prog = let
          val IL.Program{props, globals, inputInit, globalInit, initially, strands} = prog
          in
            IL.Program{
		props = props,
		globals = globals,
		inputInit = inputInit,
		globalInit = globalInit,
		initially = initially,
		strands = List.map rewriteStrand strands
	      }
          end

  end

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