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
 [diderot] / branches / vis15 / src / compiler / translate / analyze-simple.sml View of /branches/vis15/src/compiler/translate/analyze-simple.sml

Thu Dec 17 20:07:13 2015 UTC (3 years, 10 months ago) by jhr
File size: 3218 byte(s)
working on merge
(* 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
*)

structure AnalyzeSimple : sig

val analyze : Simple.block -> unit

val assignedVars : Simple.block -> SimpleVar.Set.set
val liveVars : Simple.block -> SimpleVar.Set.set

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 liveVars = getFn
val setLive = setFn
end

(* 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, indices, _) => x :: List.mapPartial Fn.id indices
| S.E_Coerce{x, ...} => [x]
| S.E_LoadSeq _ => []
| S.E_LoadImage _ => []
(* end case *))
in
end

fun analyze blk = let
fun doBlock (blk as S.Block{code, ...}, acc) = let
val result as (liveOut, assigns) = List.foldr doStm acc code
in
setAssigned (blk, assigns);
setLive (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)) =
| doStm (S.S_Foreach(x, _, b), acc) = let
val (liveOut, assigns) = doBlock (b, acc)
val liveOut = VSet.subtract(liveOut, x)
val assigns = VSet.subtract(assigns, x)
in
(* QUESTION: do we want to modify the properties of b? *)
(liveOut, assigns)
end
| doStm (S.S_IfThenElse(_, b1, b2), acc) = let
val (live1, assigns1) = doBlock (b1, acc)
val (live2, assigns2) = doBlock (b2, acc)
in
(VSet.union(live1, live2), VSet.union(assigns1, assigns2))
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, VSet.empty))
in
()
end

end

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