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 3995, Sat Jun 18 20:00:19 2016 UTC revision 4516, Mon Sep 5 16:19:47 2016 UTC
# Line 28  Line 28 
28    (* a property set on state variables that are read by other strands *)    (* a property set on state variables that are read by other strands *)
29      val sharedStateVar : SimpleVar.t -> bool      val sharedStateVar : SimpleVar.t -> bool
30    
31      (* a property set on top-level blocks that tracks the globals that are read in the block *)
32        val globalsOfBlock : Simple.block -> SimpleVar.Set.set
33    
34    end = struct    end = struct
35    
36      structure S = Simple      structure S = Simple
# Line 36  Line 39 
39      structure VSet = SV.Set      structure VSet = SV.Set
40    
41      datatype context      datatype context
42        = ConstInit | GlobalInit | StateInit        = ConstInit | UserFunc | GlobalInit | StateInit
43        | InitMeth | UpdateMeth | StabilizeMeth        | InitMeth | UpdateMeth | StabilizeMeth
44        | Create | GlobalUpdate        | Create | GlobalUpdate
45    
46      (* for debugging *)
47        fun cxtToString cxt = (case cxt
48               of ConstInit => "ConstInit"
49                | UserFunc => "UserFunc"
50                | GlobalInit => "GlobalInit"
51                | StateInit => "StateInit"
52                | InitMeth => "InitMeth"
53                | UpdateMeth => "UpdateMeth"
54                | StabilizeMeth => "StabilizeMeth"
55                | Create => "Create"
56                | GlobalUpdate => "GlobalUpdate"
57              (* end case *))
58    
59      local      local
60        val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)        val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
61      in      in
# Line 89  Line 105 
105            (* end case *))            (* end case *))
106      end (* local *)      end (* local *)
107    
108        local
109          val {getFn, setFn, ...} =
110                PropList.newProp (fn (S.Block{props, ...}) => props, fn _ => VSet.empty)
111        in
112        val globalsOfBlock = getFn
113        val setGlobalsOfBlock = setFn
114        end (* local *)
115    
116      fun markUpdate (cxt, x) = (case (cxt, SV.kindOf x)      fun markUpdate (cxt, x) = (case (cxt, SV.kindOf x)
117             of (ConstInit, SV.ConstVar) => ()             of (ConstInit, SV.ConstVar) => ()
118              | (_, SV.ConstVar) => raise Fail "update of ConstVar"              | (_, SV.ConstVar) => raise Fail "update of ConstVar"
# Line 103  Line 127 
127              | _ => ()              | _ => ()
128            (* end case *))            (* end case *))
129    
130    (* does a variable have local scope *)      fun analyzeBlock cxt blk = let
131      fun isLocal x = (case SV.kindOf x            val globals = ref VSet.empty
132             of SV.LocalVar => true            fun addGlobal x = (globals := VSet.add(!globals, x))
133              | SV.IterVar => true            fun addVar (x, vs) = let
134              | _ => false                  fun addGlobal x = (globals := VSet.add(!globals, x); vs)
135            (* end case *))                  in
136                      case (SV.kindOf x, cxt)
137      fun addVar (x, vs) = if isLocal x then VSet.add(vs, x) else vs                     of (SV.ConstVar, ConstInit) => vs
138                        | (SV.ConstVar, _) => addGlobal x
139                        | (SV.InputVar, ConstInit) => vs
140                        | (SV.InputVar, _) => addGlobal x
141                        | (SV.GlobalVar, ConstInit) => vs
142                        | (SV.GlobalVar, GlobalInit) => vs
143                        | (SV.GlobalVar, _) => addGlobal x
144                        | (SV.StrandStateVar, _) => VSet.add(vs, x)
145                        | (SV.StrandOutputVar, _) => VSet.add(vs, x)
146                        | (SV.LocalVar, _) => VSet.add(vs, x)
147                        | (SV.IterVar, _) => VSet.add(vs, x)
148                        | _ => vs
149                      (* end case *)
150                    end
151      fun addList (xs, vs) = List.foldl addVar vs xs      fun addList (xs, vs) = List.foldl addVar vs xs
152            (* compute the used local and global variables of a Simple AST expression *)
   (* compute the used local variables of a Simple AST expression *)  
153      fun addUses (e, vs) = let      fun addUses (e, vs) = let
154            val u = (case e            val u = (case e
155                   of S.E_Var x => [x]                   of S.E_Var x => [x]
156                    | S.E_Lit _ => []                    | S.E_Lit _ => []
157                    | S.E_Select _ => raise Fail "unexpected E_Select" (* should be handled by doStm *)                          | S.E_Kernel _ => []
158                    | S.E_Apply _ => raise Fail "unexpected E_Apply"                          | S.E_Select(y, z) => (
159                                markSharedStateVar z;
160                                [y])
161                            | S.E_Apply(_, xs) => xs
162                    | S.E_Prim(_, _, xs, _) => xs                    | S.E_Prim(_, _, xs, _) => xs
163                    | S.E_Tensor(xs, _) => xs                    | S.E_Tensor(xs, _) => xs
164                    | S.E_Seq(xs, _) => xs                    | S.E_Seq(xs, _) => xs
165                            | S.E_Tuple xs => xs
166                            | S.E_Project(x, i) => [x]
167                    | S.E_Slice(x, _, _) => [x]                    | S.E_Slice(x, _, _) => [x]
168                    | S.E_Coerce{x, ...} => [x]                    | S.E_Coerce{x, ...} => [x]
169                            | S.E_BorderCtl(BorderCtl.Default x, y) => [x, y]
170                            | S.E_BorderCtl(_, x) => [x]
171                    | S.E_LoadSeq _ => []                    | S.E_LoadSeq _ => []
172                    | S.E_LoadImage _ => []                    | S.E_LoadImage _ => []
173                            | S.E_InsideImage(pos, img, _) => [pos, img]
174                  (* end case *))                  (* end case *))
175            in            in
176              addList (u, vs)              addList (u, vs)
177            end            end
   
     fun analyzeBlock cxt blk = let  
178            fun doBlock (blk as S.Block{code, ...}, liveIn) = let            fun doBlock (blk as S.Block{code, ...}, liveIn) = let
179                  val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code                  val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
180                  in                  in
# Line 146  Line 187 
187                  (VSet.subtract(live, x), VSet.subtract(assigns, x))                  (VSet.subtract(live, x), VSet.subtract(assigns, x))
188              | doStm (S.S_Var(x, SOME e), (live, assigns)) =              | doStm (S.S_Var(x, SOME e), (live, assigns)) =
189                  (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))                  (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)))  
190              | doStm (S.S_Assign(x, e), (live, assigns)) = (              | doStm (S.S_Assign(x, e), (live, assigns)) = (
191                  markUpdate (cxt, x);                  markUpdate (cxt, x);
192                  (addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))                  (addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))
193              | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let              | doStm (S.S_Foreach(x, xs, b), (liveIn, assignsIn)) = let
194                    val liveIn = addVar(xs, liveIn)
195                  val (liveOut, assigns) = doBlock (b, liveIn)                  val (liveOut, assigns) = doBlock (b, liveIn)
196                  val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)                  val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
197                  val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)                  val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
# Line 161  Line 199 
199  (* QUESTION: do we want to modify the properties of b? *)  (* QUESTION: do we want to modify the properties of b? *)
200                    (liveOut, assigns)                    (liveOut, assigns)
201                  end                  end
202              | doStm (S.S_IfThenElse(_, b1, b2), (liveIn, assignsIn)) = let              | doStm (S.S_IfThenElse(x, b1, b2), (liveIn, assignsIn)) = let
203                    val liveIn = addVar(x, liveIn)
204                  val (live1, assigns1) = doBlock (b1, liveIn)                  val (live1, assigns1) = doBlock (b1, liveIn)
205                  val (live2, assigns2) = doBlock (b2, liveIn)                  val (live2, assigns2) = doBlock (b2, liveIn)
206                  val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))                  val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
# Line 170  Line 209 
209                  end                  end
210              | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)              | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
211              | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)              | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
212              | doStm (S.S_MapReduce{results, ...}, acc) = (              | doStm (S.S_MapReduce mrs, acc) = (
213                  List.app (fn x => markUpdate (cxt, x)) results;                  List.app (fn (S.MapReduce{result, ...}) => markUpdate (cxt, result)) mrs;
214                  acc)                  acc)
215              | doStm (_, acc) = acc              | doStm (_, acc) = acc
216            val (bnd, assigns) = doBlock (blk, VSet.empty)            val (bnd, assigns) = doBlock (blk, VSet.empty)
217            in            in
218              ()              setGlobalsOfBlock (blk, !globals)
219            end            end
220    
221      fun analyze (S.Program{constInit, globInit, strand, create, init, update, ...}) = let      fun analyze prog = let
222            val S.Strand{stateInit, initM, updateM, stabilizeM, ...} = strand            val S.Program{
223            val S.Create{code, ...} = create                    props, constInit, funcs, globInit, strand, create, start, update, ...
224            in                  } = prog
225              val S.Strand{state, stateInit, startM, updateM, stabilizeM, ...} = strand
226              in
227              (* if the program has communication then the "pos" variable is shared *)
228                if Properties.hasProp Properties.StrandCommunication props
229                  then (case List.find (fn x => (SV.nameOf x = "pos")) state
230                     of SOME x => markSharedStateVar x
231                      | NONE => raise Fail "impossible: missing 'pos' state variable"
232                    (* end case *))
233                  else ();
234              analyzeBlock ConstInit constInit;              analyzeBlock ConstInit constInit;
235                List.app (fn (S.Func{f, body, ...}) => analyzeBlock UserFunc body) funcs;
236              analyzeBlock GlobalInit globInit;              analyzeBlock GlobalInit globInit;
237              analyzeBlock StateInit stateInit;              analyzeBlock StateInit stateInit;
238              Option.app (analyzeBlock InitMeth) initM;              Option.app (analyzeBlock InitMeth) startM;
239              analyzeBlock UpdateMeth updateM;              analyzeBlock UpdateMeth updateM;
240              Option.app (analyzeBlock StabilizeMeth) stabilizeM;              Option.app (analyzeBlock StabilizeMeth) stabilizeM;
241              analyzeBlock Create code;              Create.app (analyzeBlock Create) create;
242              Option.app (analyzeBlock GlobalUpdate) init;              Option.app (analyzeBlock GlobalUpdate) start;
243              Option.app (analyzeBlock GlobalUpdate) update              Option.app (analyzeBlock GlobalUpdate) update
244            end            end
245    

Legend:
Removed from v.3995  
changed lines
  Added in v.4516

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