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 3797 - (download) (annotate)
Mon May 2 21:10:12 2016 UTC (3 years, 5 months ago) by jhr
File size: 4677 byte(s)
  Working on merge: clean up tensor slicing/indexing.
(* 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.block -> unit

    val analyzeGlobalUpdate : Simple.block option -> 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

  end = struct

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

    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 = (case SV.kindOf x
	   of SV.ConstVar => raise Fail "update of ConstVar"
	    | SV.InputVar => setFn(x, true)
	    | SV.GlobalVar => setFn(x, true)
	    | _ => ()
	  (* end case *))
    end (* local *)

  (* 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_Select(x, _) => [x] 
		  | 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 _ => []
		(* end case *))
	  in
	    addList (u, VSet.empty)
	  end

    fun analyze 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, e), (live, assigns)) =
		(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 (_, acc) = acc
	  val (bnd, assigns) = doBlock (blk, VSet.empty)
	  in
	    ()
	  end

    fun analyzeGlobalUpdate NONE = ()
      | analyzeGlobalUpdate (SOME blk) = let
	(* identify and mark globals that are modified in the global-update code *)
	  fun doBlk (S.Block{code, ...}) = List.app doStm code
	  and doStm stm = (case stm
                 of S.S_Assign(x, _) => markUpdatedGlobal x
                  | S.S_IfThenElse(_, b1, b2) => (doBlk b1; doBlk b2)
		  | S.S_Foreach(_, _, blk) => doBlk blk
		  | S.S_MapReduce{results, ...} => List.app markUpdatedGlobal results
		  | _ => ()
		(* end case *))
	  in
	    doBlk blk
	  end

  end

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