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

SCM Repository

[diderot] View of /branches/vis15/src/compiler/translate/analyze-simple.sml
ViewVC logotype

View of /branches/vis15/src/compiler/translate/analyze-simple.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4043 - (download) (annotate)
Sun Jun 26 14:00:38 2016 UTC (3 years, 3 months ago) by jhr
File size: 6585 byte(s)
  Working on merge: changed the way that we handle kernels in the AST and SimpleAST IRs (treat
  them like literals, instead of like variables).  Added code to rewrite Inside tests in Simple
  IR to use the image instead of the field, which fixes a problem with trying to do inside tests
  on Ein fields.  Added code to promote locals to globals as part of the simplify-vars phase.
(* analyze-simple.sml
 *
 * Analysis for Simple AST blocks.  We compute the set of free local variables that
 * are assigned in the block and the live variables.  These pieces of information
 * are stored as properties in the block and are used to generate the phi nodes in
 * the CFG representation.
 *
 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
 *
 * COPYRIGHT (c) 2015 The University of Chicago
 * All rights reserved.
 *)

structure AnalyzeSimple : sig

    val analyze : Simple.program -> unit

    val assignedVars : Simple.block -> SimpleVar.Set.set
    val liveIn  : Simple.block -> SimpleVar.Set.set
    val liveOut : Simple.block -> SimpleVar.Set.set

  (* a property set on global variables that are modified during the global-update code *)
    val updatedGlobal : SimpleVar.t -> bool

  (* a property set on state variables that are modified during super steps *)
    val varyingStateVar : SimpleVar.t -> bool

  (* a property set on state variables that are read by other strands *)
    val sharedStateVar : SimpleVar.t -> bool

  end = struct

    structure S = Simple
    structure SV = SimpleVar
    structure VMap = SV.Map
    structure VSet = SV.Set

    datatype context
      = ConstInit | GlobalInit | StateInit
      | InitMeth | UpdateMeth | StabilizeMeth
      | Create | GlobalUpdate

    local
      val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
    in
    val assignedVars = getFn
    val setAssigned = setFn
    end

    local
      val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
    in
    val liveIn = getFn
    val setLiveIn = setFn
    end

    local
      val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
    in
    val liveOut = getFn
    val setLiveOut = setFn
    end

  (* track if a global variable is updated in the global-update code *)
    local
      val {setFn, getFn} = SV.newFlag()
    in
    val updatedGlobal = getFn
    fun markUpdatedGlobal x = setFn(x, true)
    end (* local *)

  (* track if a state variable is modified during super steps *)
    local
      val {setFn, getFn} = SV.newFlag()
    in
    val varyingStateVar = getFn
    fun markVaryingStateVar x = setFn(x, true)
    end (* local *)

  (* track if a state variable is read by other strands *)
    local
      val {setFn, getFn} = SV.newFlag()
    in
    val sharedStateVar = getFn
    fun markSharedStateVar x = (case SV.kindOf x
	   of SV.StrandStateVar => setFn(x, true)
	    | SV.StrandOutputVar => setFn(x, true)
	    | _ => ()
	  (* end case *))
    end (* local *)

    fun markUpdate (cxt, x) = (case (cxt, SV.kindOf x)
	   of (ConstInit, SV.ConstVar) => ()
	    | (_, SV.ConstVar) => raise Fail "update of ConstVar"
	    | (InitMeth, SV.StrandStateVar) => markVaryingStateVar x
	    | (InitMeth, SV.StrandOutputVar) => markVaryingStateVar x
	    | (UpdateMeth, SV.StrandStateVar) => markVaryingStateVar x
	    | (UpdateMeth, SV.StrandOutputVar) => markVaryingStateVar x
	    | (StabilizeMeth, SV.StrandStateVar) => markVaryingStateVar x
	    | (StabilizeMeth, SV.StrandOutputVar) => markVaryingStateVar x
	    | (GlobalUpdate, SV.InputVar) => markUpdatedGlobal x
	    | (GlobalUpdate, SV.GlobalVar) => markUpdatedGlobal x
	    | _ => ()
	  (* end case *))

  (* does a variable have local scope *)
    fun isLocal x = (case SV.kindOf x
	   of SV.LocalVar => true
	    | SV.IterVar => true
	    | _ => false
	  (* end case *))

    fun addVar (x, vs) = if isLocal x then VSet.add(vs, x) else vs

    fun addList (xs, vs) = List.foldl addVar vs xs

  (* compute the used local variables of a Simple AST expression *)
    fun addUses (e, vs) = let
	  val u = (case e
		 of S.E_Var x => [x]
		  | S.E_Lit _ => []
		  | S.E_Kernel _ => []
		  | S.E_Select _ => raise Fail "unexpected E_Select" (* should be handled by doStm *)
		  | S.E_Apply _ => raise Fail "unexpected E_Apply"
		  | S.E_Prim(_, _, xs, _) => xs
		  | S.E_Tensor(xs, _) => xs
		  | S.E_Seq(xs, _) => xs
		  | S.E_Slice(x, _, _) => [x]
		  | S.E_Coerce{x, ...} => [x]
		  | S.E_LoadSeq _ => []
		  | S.E_LoadImage _ => []
		  | S.E_InsideImage(pos, img, _) => [pos, img]
		(* end case *))
	  in
	    addList (u, vs)
	  end

    fun analyzeBlock cxt blk = let
	  fun doBlock (blk as S.Block{code, ...}, liveIn) = let
		val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
		in
		  setAssigned (blk, assigns);
		  setLiveIn (blk, liveIn);
		  setLiveOut (blk, liveOut);
		  result
		end
	  and doStm (S.S_Var(x, NONE), (live, assigns)) =
		(VSet.subtract(live, x), VSet.subtract(assigns, x))
	    | doStm (S.S_Var(x, SOME e), (live, assigns)) =
		(addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
	    | doStm (S.S_Assign(x, S.E_Select(y, z)), (live, assigns)) = (
		markUpdate (cxt, x);
		markSharedStateVar z;
		(addVar (y, VSet.subtract(live, x)), addVar(x, assigns)))
	    | doStm (S.S_Assign(x, e), (live, assigns)) = (
		markUpdate (cxt, x);
		(addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))
	    | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let
		val (liveOut, assigns) = doBlock (b, liveIn)
		val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
		val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
		in
(* QUESTION: do we want to modify the properties of b? *)
		  (liveOut, assigns)
		end
	    | doStm (S.S_IfThenElse(_, b1, b2), (liveIn, assignsIn)) = let
		val (live1, assigns1) = doBlock (b1, liveIn)
		val (live2, assigns2) = doBlock (b2, liveIn)
		val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
		in
		  (VSet.union(live1, live2), assigns)
		end
	    | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
	    | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
	    | doStm (S.S_MapReduce{results, ...}, acc) = (
		List.app (fn x => markUpdate (cxt, x)) results;
		acc)
	    | doStm (_, acc) = acc
	  val (bnd, assigns) = doBlock (blk, VSet.empty)
	  in
	    ()
	  end

    fun analyze (S.Program{constInit, globInit, strand, create, init, update, ...}) = let
	  val S.Strand{stateInit, initM, updateM, stabilizeM, ...} = strand
	  val S.Create{code, ...} = create
	  in
	    analyzeBlock ConstInit constInit;
	    analyzeBlock GlobalInit globInit;
	    analyzeBlock StateInit stateInit;
	    Option.app (analyzeBlock InitMeth) initM;
	    analyzeBlock UpdateMeth updateM;
	    Option.app (analyzeBlock StabilizeMeth) stabilizeM;
	    analyzeBlock Create code;
	    Option.app (analyzeBlock GlobalUpdate) init;
	    Option.app (analyzeBlock GlobalUpdate) update
	  end

  end

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