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

SCM Repository

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

View of /branches/charisee/src/compiler/tree-il-forvis-basevis/var-analysis.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3692 - (download) (annotate)
Sun Mar 20 01:17:08 2016 UTC (3 years, 5 months ago) by cchiw
File size: 12315 byte(s)
tree-il-forvis-base vis and charisee
(* var-analysis.sml
 *
 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
 *
 * COPYRIGHT (c) 2015 The University of Chicago
 * 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 IR : SSA

    val optimize : IR.program -> IR.program

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

  end = struct

    structure IR = LowIR
    structure V = IR.Var
    structure StV = IR.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 IR = IR
        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 IR.Node.kind nd
                 of IR.ASSIGN{stm=(lhs, IR.STATE rhs), ...} => svUse rhs
                  | IR.SAVE{lhs, rhs, ...} => svDef (lhs, rhs)
                  | _ => List.app vUse (IR.Node.uses nd)
                (* end case *))
          in
            IR.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 (IR.Method{body, ...}) = checkCFG {
                  svDef = fn (lhs, rhs) => (case V.binding rhs
                     of IR.VB_RHS(IR.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 IR.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 = IR.SAV(sv, x)
                in
                  LowCensus.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
                        (IR.ASSGN(x', IR.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 IR.Node.kind nd
                 of IR.SAVE{lhs, rhs, ...} => if (stateUsedInMethod lhs)
                      then ()
                      else (LowCensus.dec rhs; IR.CFG.deleteNode nd)
                  | _ => ()
                (* end case *))
          val _ = if anyUnused then IR.CFG.apply doNode stateInit else ()
          val cfg = IR.CFG.appendBlock (stateInit, initStms)
          in
            reduce cfg
          end

    fun rewriteMethod loadParamShadows (IR.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 *)
                      LowCensus.dec x; LowCensus.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 IR.Node.kind nd
                   of IR.JOIN{phis, ...} => let
                        fun doPhi (lhs, rhs) = (lhs, List.map (Option.map rename) rhs)
                        in
                          phis := List.map doPhi (!phis)
                        end
                    | IR.COND{pred, cond, trueBranch, falseBranch} =>
                        if changed cond
                          then let
                            val newNd = IR.Node.mkCOND (rename cond)
                            in
                              IR.Node.replaceInEdge {src = !pred, oldDst = nd, dst = newNd};
                              IR.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !trueBranch};
                              IR.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !falseBranch}
                            end
                          else ()
                    | IR.ASSIGN{stm=(lhs, rhs), ...} => let
                        fun replace rhs = IR.CFG.replaceNode(nd, IR.Node.mkASSIGN(lhs, rhs))
                        in
                          case rhs
                           of IR.GLOBAL x => ()
                            | IR.STATE x => if stateUsedInMethod x
                                then ()
                                else IR.CFG.deleteNode nd
                            | IR.VAR x => if changed x
                                then replace (IR.VAR(rename x))
                                else ()
                            | IR.LIT _ => ()
                            | IR.OP(rator, args) => if List.exists changed args
                                then replace (IR.OP(rator, renameList args))
                                else ()
(*                            | IR.APPLY(f, args) => if List.exists changed args
                                then replace (IR.APPLY(f, renameList args))
                                else ()
FIXME: remove this?
*)
                            | IR.CONS(ty, args) => if List.exists changed args
                                then replace (IR.CONS(ty, renameList args))
                                else ()
                          (* end case *)
                        end
                    | IR.MASSIGN{stm=(lhs, rator, args), ...} =>
                        if List.exists changed args
                          then IR.CFG.replaceNode(nd, IR.Node.mkMASSIGN(lhs, rator, renameList args))
                          else ()
                    | IR.NEW{strand, args, ...} =>
                        if List.exists changed args
                          then IR.CFG.replaceNode(
                            nd,
                            IR.Node.mkNEW{strand=strand, args=renameList args})
                          else ()
                    | IR.SAVE{lhs, rhs, ...} => if (changed rhs)
                          then IR.CFG.replaceNode(nd, IR.Node.mkSAVE(lhs, rename rhs))
                        else if (isVarying lhs)
                          then ()
                          else (LowCensus.dec rhs; IR.CFG.deleteNode nd)
                    | _ => ()
                  (* end case *)
                end
          val _ = IR.CFG.apply doNode body
          in
            IR.Method{
                name = name,
                body = reduce (IR.CFG.prependBlock (loadStms, body))
              }
          end

    fun rewriteStrand (strand as IR.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
                  IR.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 IR.Program{props, globals, inputInit, globalInit, initially, strands} = prog
          in
            IR.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