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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 3839, Mon May 9 20:05:59 2016 UTC revision 3840, Mon May 9 20:42:08 2016 UTC
# Line 13  Line 13 
13    
14  structure AnalyzeSimple : sig  structure AnalyzeSimple : sig
15    
16      val analyze : Simple.block -> unit      val analyze : Simple.program -> unit
   
     val analyzeGlobalUpdate : Simple.block option -> unit  
17    
18      val assignedVars : Simple.block -> SimpleVar.Set.set      val assignedVars : Simple.block -> SimpleVar.Set.set
19      val liveIn  : Simple.block -> SimpleVar.Set.set      val liveIn  : Simple.block -> SimpleVar.Set.set
# Line 24  Line 22 
22    (* a property set on global variables that are modified during the global-update code *)    (* a property set on global variables that are modified during the global-update code *)
23      val updatedGlobal : SimpleVar.t -> bool      val updatedGlobal : SimpleVar.t -> bool
24    
25      (* a property set on state variables that are modified during super steps *)
26        val varyingStateVar : SimpleVar.t -> bool
27    
28      (* a property set on state variables that are read by other strands *)
29        val sharedStateVar : SimpleVar.t -> bool
30    
31    end = struct    end = struct
32    
33      structure S = Simple      structure S = Simple
# Line 31  Line 35 
35      structure VMap = SV.Map      structure VMap = SV.Map
36      structure VSet = SV.Set      structure VSet = SV.Set
37    
38        datatype context
39          = ConstInit | GlobalInit | StateInit
40          | InitMeth | UpdateMeth | StabilizeMeth
41          | Create | GlobalUpdate
42    
43      local      local
44        val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)        val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
45      in      in
# Line 57  Line 66 
66        val {setFn, getFn} = SV.newFlag()        val {setFn, getFn} = SV.newFlag()
67      in      in
68      val updatedGlobal = getFn      val updatedGlobal = getFn
69      fun markUpdatedGlobal x = (case SV.kindOf x      fun markUpdatedGlobal x = setFn(x, true)
70             of SV.ConstVar => raise Fail "update of ConstVar"      end (* local *)
71              | SV.InputVar => setFn(x, true)  
72              | SV.GlobalVar => setFn(x, true)    (* track if a state variable is modified during super steps *)
73        local
74          val {setFn, getFn} = SV.newFlag()
75        in
76        val varyingStateVar = getFn
77        fun markVaryingStateVar x = setFn(x, true)
78        end (* local *)
79    
80      (* track if a state variable is read by other strands *)
81        local
82          val {setFn, getFn} = SV.newFlag()
83        in
84        val sharedStateVar = getFn
85        fun markSharedStateVar x = (case SV.kindOf x
86               of SV.StrandStateVar => setFn(x, true)
87                | SV.StrandOutputVar => setFn(x, true)
88              | _ => ()              | _ => ()
89            (* end case *))            (* end case *))
90      end (* local *)      end (* local *)
91    
92        fun markUpdate (cxt, x) = (case (cxt, SV.kindOf x)
93               of (ConstInit, SV.ConstVar) => ()
94                | (_, SV.ConstVar) => raise Fail "update of ConstVar"
95                | (InitMeth, SV.StrandStateVar) => markVaryingStateVar x
96                | (InitMeth, SV.StrandOutputVar) => markVaryingStateVar x
97                | (UpdateMeth, SV.StrandStateVar) => markVaryingStateVar x
98                | (UpdateMeth, SV.StrandOutputVar) => markVaryingStateVar x
99                | (StabilizeMeth, SV.StrandStateVar) => markVaryingStateVar x
100                | (StabilizeMeth, SV.StrandOutputVar) => markVaryingStateVar x
101                | (GlobalUpdate, SV.InputVar) => markUpdatedGlobal x
102                | (GlobalUpdate, SV.GlobalVar) => markUpdatedGlobal x
103                | _ => ()
104              (* end case *))
105    
106    (* does a variable have local scope *)    (* does a variable have local scope *)
107      fun isLocal x = (case SV.kindOf x      fun isLocal x = (case SV.kindOf x
108             of SV.LocalVar => true             of SV.LocalVar => true
# Line 81  Line 119 
119            val u = (case e            val u = (case e
120                   of S.E_Var x => [x]                   of S.E_Var x => [x]
121                    | S.E_Lit _ => []                    | S.E_Lit _ => []
122                    | S.E_Select(x, _) => [x]                    | S.E_Select _ => raise Fail "unexpected E_Select" (* should be handled by doStm *)
123                    | S.E_Apply _ => raise Fail "unexpected E_Apply"                    | S.E_Apply _ => raise Fail "unexpected E_Apply"
124                    | S.E_Prim(_, _, xs, _) => xs                    | S.E_Prim(_, _, xs, _) => xs
125                    | S.E_Tensor(xs, _) => xs                    | S.E_Tensor(xs, _) => xs
# Line 92  Line 130 
130                    | S.E_LoadImage _ => []                    | S.E_LoadImage _ => []
131                  (* end case *))                  (* end case *))
132            in            in
133              addList (u, VSet.empty)              addList (u, vs)
134            end            end
135    
136      fun analyze blk = let      fun analyzeBlock cxt blk = let
137            fun doBlock (blk as S.Block{code, ...}, liveIn) = let            fun doBlock (blk as S.Block{code, ...}, liveIn) = let
138                  val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code                  val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
139                  in                  in
# Line 108  Line 146 
146                  (VSet.subtract(live, x), VSet.subtract(assigns, x))                  (VSet.subtract(live, x), VSet.subtract(assigns, x))
147              | doStm (S.S_Var(x, SOME e), (live, assigns)) =              | doStm (S.S_Var(x, SOME e), (live, assigns)) =
148                  (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))                  (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
149              | doStm (S.S_Assign(x, e), (live, assigns)) =              | doStm (S.S_Assign(x, S.E_Select(y, z)), (live, assigns)) = (
150                  (addUses(e, VSet.subtract(live, x)), addVar(x, assigns))                  markUpdate (cxt, x);
151                    markSharedStateVar z;
152                    (addVar (y, VSet.subtract(live, x)), addVar(x, assigns)))
153                | doStm (S.S_Assign(x, e), (live, assigns)) = (
154                    markUpdate (cxt, x);
155                    (addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))
156              | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let              | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let
157                  val (liveOut, assigns) = doBlock (b, liveIn)                  val (liveOut, assigns) = doBlock (b, liveIn)
158                  val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)                  val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
# Line 127  Line 170 
170                  end                  end
171              | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)              | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
172              | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)              | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
173                | doStm (S.S_MapReduce{results, ...}, acc) = (
174                    List.app (fn x => markUpdate (cxt, x)) results;
175                    acc)
176              | doStm (_, acc) = acc              | doStm (_, acc) = acc
177            val (bnd, assigns) = doBlock (blk, VSet.empty)            val (bnd, assigns) = doBlock (blk, VSet.empty)
178            in            in
179              ()              ()
180            end            end
181    
182      fun analyzeGlobalUpdate NONE = ()      fun analyze (S.Program{constInit, init, strand, create, update, ...}) = let
183        | analyzeGlobalUpdate (SOME blk) = let            val S.Strand{stateInit, initM, updateM, stabilizeM, ...} = strand
184          (* identify and mark globals that are modified in the global-update code *)            val S.Create{code, ...} = create
185            fun doBlk (S.Block{code, ...}) = List.app doStm code            in
186            and doStm stm = (case stm              analyzeBlock ConstInit constInit;
187                   of S.S_Assign(x, _) => markUpdatedGlobal x              analyzeBlock GlobalInit init;
188                    | S.S_IfThenElse(_, b1, b2) => (doBlk b1; doBlk b2)              analyzeBlock StateInit stateInit;
189                    | S.S_Foreach(_, _, blk) => doBlk blk              Option.app (analyzeBlock InitMeth) initM;
190                    | S.S_MapReduce{results, ...} => List.app markUpdatedGlobal results              analyzeBlock UpdateMeth updateM;
191                    | _ => ()              Option.app (analyzeBlock StabilizeMeth) stabilizeM;
192                  (* end case *))              analyzeBlock Create code;
193            in              Option.app (analyzeBlock GlobalUpdate) update
             doBlk blk  
194            end            end
195    
196    end    end

Legend:
Removed from v.3839  
changed lines
  Added in v.3840

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