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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5574 - (view) (download)

1 : jhr 3501 (* analyze-simple.sml
2 :     *
3 :     * Analysis for Simple AST blocks. We compute the set of free local variables that
4 :     * are assigned in the block and the live variables. These pieces of information
5 :     * are stored as properties in the block and are used to generate the phi nodes in
6 :     * the CFG representation.
7 :     *
8 :     * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
9 :     *
10 :     * COPYRIGHT (c) 2015 The University of Chicago
11 :     * All rights reserved.
12 :     *)
13 :    
14 :     structure AnalyzeSimple : sig
15 :    
16 : jhr 3840 val analyze : Simple.program -> unit
17 : jhr 3501
18 :     val assignedVars : Simple.block -> SimpleVar.Set.set
19 : jhr 3502 val liveIn : Simple.block -> SimpleVar.Set.set
20 :     val liveOut : Simple.block -> SimpleVar.Set.set
21 : jhr 3501
22 : jhr 3538 (* a property set on global variables that are modified during the global-update code *)
23 :     val updatedGlobal : SimpleVar.t -> bool
24 :    
25 : jhr 3840 (* 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 : jhr 4164 (* 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 : jhr 3501 end = struct
35 :    
36 :     structure S = Simple
37 :     structure SV = SimpleVar
38 :     structure VMap = SV.Map
39 :     structure VSet = SV.Set
40 :    
41 : jhr 3840 datatype context
42 : jhr 4166 = ConstInit | UserFunc | GlobalInit | StateInit
43 : jhr 4895 | StartMeth | UpdateMeth | StabilizeMeth
44 : jhr 3840 | Create | GlobalUpdate
45 :    
46 : jhr 4168 (* for debugging *)
47 :     fun cxtToString cxt = (case cxt
48 : jhr 4317 of ConstInit => "ConstInit"
49 :     | UserFunc => "UserFunc"
50 :     | GlobalInit => "GlobalInit"
51 :     | StateInit => "StateInit"
52 : jhr 4895 | StartMeth => "StartMeth"
53 : jhr 4317 | UpdateMeth => "UpdateMeth"
54 :     | StabilizeMeth => "StabilizeMeth"
55 :     | Create => "Create"
56 :     | GlobalUpdate => "GlobalUpdate"
57 :     (* end case *))
58 : jhr 4168
59 : jhr 3501 local
60 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
61 :     in
62 :     val assignedVars = getFn
63 :     val setAssigned = setFn
64 :     end
65 :    
66 :     local
67 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
68 :     in
69 : jhr 3502 val liveIn = getFn
70 :     val setLiveIn = setFn
71 : jhr 3501 end
72 :    
73 : jhr 3502 local
74 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
75 :     in
76 :     val liveOut = getFn
77 :     val setLiveOut = setFn
78 :     end
79 :    
80 : jhr 3538 (* track if a global variable is updated in the global-update code *)
81 :     local
82 :     val {setFn, getFn} = SV.newFlag()
83 :     in
84 :     val updatedGlobal = getFn
85 : jhr 3840 fun markUpdatedGlobal x = setFn(x, true)
86 :     end (* local *)
87 :    
88 :     (* track if a state variable is modified during super steps *)
89 :     local
90 :     val {setFn, getFn} = SV.newFlag()
91 :     in
92 :     val varyingStateVar = getFn
93 :     fun markVaryingStateVar x = setFn(x, true)
94 :     end (* local *)
95 :    
96 :     (* track if a state variable is read by other strands *)
97 :     local
98 :     val {setFn, getFn} = SV.newFlag()
99 :     in
100 :     val sharedStateVar = getFn
101 :     fun markSharedStateVar x = (case SV.kindOf x
102 : jhr 4317 of SV.StrandStateVar => setFn(x, true)
103 :     | SV.StrandOutputVar => setFn(x, true)
104 :     | _ => ()
105 :     (* end case *))
106 : jhr 3538 end (* local *)
107 :    
108 : jhr 4164 local
109 :     val {getFn, setFn, ...} =
110 : jhr 4317 PropList.newProp (fn (S.Block{props, ...}) => props, fn _ => VSet.empty)
111 : jhr 4164 in
112 :     val globalsOfBlock = getFn
113 :     val setGlobalsOfBlock = setFn
114 :     end (* local *)
115 :    
116 : jhr 3840 fun markUpdate (cxt, x) = (case (cxt, SV.kindOf x)
117 : jhr 4317 of (ConstInit, SV.ConstVar) => ()
118 :     | (_, SV.ConstVar) => raise Fail "update of ConstVar"
119 : jhr 4895 (* QUESTION: is it the case that state variables that are updated during
120 :     * the start method but not later can be treated as invariant?
121 :     *)
122 :     | (StartMeth, SV.StrandStateVar) => markVaryingStateVar x
123 :     | (StartMeth, SV.StrandOutputVar) => markVaryingStateVar x
124 : jhr 4317 | (UpdateMeth, SV.StrandStateVar) => markVaryingStateVar x
125 :     | (UpdateMeth, SV.StrandOutputVar) => markVaryingStateVar x
126 :     | (StabilizeMeth, SV.StrandStateVar) => markVaryingStateVar x
127 :     | (StabilizeMeth, SV.StrandOutputVar) => markVaryingStateVar x
128 :     | (GlobalUpdate, SV.InputVar) => markUpdatedGlobal x
129 :     | (GlobalUpdate, SV.GlobalVar) => markUpdatedGlobal x
130 :     | _ => ()
131 :     (* end case *))
132 : jhr 3840
133 :     fun analyzeBlock cxt blk = let
134 : jhr 4317 val globals = ref VSet.empty
135 :     fun addGlobal x = (globals := VSet.add(!globals, x))
136 : jhr 4333 fun addVar (x, vs) = let
137 :     fun addGlobal x = (globals := VSet.add(!globals, x); vs)
138 :     in
139 :     case (SV.kindOf x, cxt)
140 :     of (SV.ConstVar, ConstInit) => vs
141 : jhr 4317 | (SV.ConstVar, _) => addGlobal x
142 : jhr 4333 | (SV.InputVar, ConstInit) => vs
143 : jhr 4317 | (SV.InputVar, _) => addGlobal x
144 : jhr 4333 | (SV.GlobalVar, ConstInit) => vs
145 :     | (SV.GlobalVar, GlobalInit) => vs
146 : jhr 4317 | (SV.GlobalVar, _) => addGlobal x
147 : jhr 4333 | (SV.StrandStateVar, _) => VSet.add(vs, x)
148 :     | (SV.StrandOutputVar, _) => VSet.add(vs, x)
149 :     | (SV.LocalVar, _) => VSet.add(vs, x)
150 :     | (SV.IterVar, _) => VSet.add(vs, x)
151 :     | _ => vs
152 :     (* end case *)
153 :     end
154 : jhr 4317 fun addList (xs, vs) = List.foldl addVar vs xs
155 :     (* compute the used local and global variables of a Simple AST expression *)
156 :     fun addUses (e, vs) = let
157 :     val u = (case e
158 :     of S.E_Var x => [x]
159 :     | S.E_Lit _ => []
160 :     | S.E_Kernel _ => []
161 : jhr 4375 | S.E_Select(y, z) => (
162 :     markSharedStateVar z;
163 :     [y])
164 : jhr 4317 | S.E_Apply(_, xs) => xs
165 :     | S.E_Prim(_, _, xs, _) => xs
166 :     | S.E_Tensor(xs, _) => xs
167 : jhr 5574 | S.E_Field(xs, _) => xs
168 : jhr 4317 | S.E_Seq(xs, _) => xs
169 :     | S.E_Tuple xs => xs
170 :     | S.E_Project(x, i) => [x]
171 :     | S.E_Slice(x, _, _) => [x]
172 :     | S.E_Coerce{x, ...} => [x]
173 :     | S.E_BorderCtl(BorderCtl.Default x, y) => [x, y]
174 :     | S.E_BorderCtl(_, x) => [x]
175 :     | S.E_LoadSeq _ => []
176 :     | S.E_LoadImage _ => []
177 :     | S.E_InsideImage(pos, img, _) => [pos, img]
178 : jhr 5564 | S.E_FieldFn f => []
179 : jhr 4317 (* end case *))
180 :     in
181 :     addList (u, vs)
182 :     end
183 :     fun doBlock (blk as S.Block{code, ...}, liveIn) = let
184 :     val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
185 :     in
186 :     setAssigned (blk, assigns);
187 :     setLiveIn (blk, liveIn);
188 :     setLiveOut (blk, liveOut);
189 :     result
190 :     end
191 :     and doStm (S.S_Var(x, NONE), (live, assigns)) =
192 :     (VSet.subtract(live, x), VSet.subtract(assigns, x))
193 :     | doStm (S.S_Var(x, SOME e), (live, assigns)) =
194 :     (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
195 :     | doStm (S.S_Assign(x, e), (live, assigns)) = (
196 :     markUpdate (cxt, x);
197 :     (addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))
198 : jhr 4636 | doStm (S.S_IfThenElse(x, b1, b2), (liveIn, assignsIn)) = let
199 :     val liveIn = addVar(x, liveIn)
200 :     val (live1, assigns1) = doBlock (b1, liveIn)
201 :     val (live2, assigns2) = doBlock (b2, liveIn)
202 :     val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
203 :     in
204 :     (VSet.union(live1, live2), assigns)
205 :     end
206 : jhr 4333 | doStm (S.S_Foreach(x, xs, b), (liveIn, assignsIn)) = let
207 :     val liveIn = addVar(xs, liveIn)
208 : jhr 4317 val (liveOut, assigns) = doBlock (b, liveIn)
209 :     val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
210 :     val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
211 :     in
212 : jhr 3501 (* QUESTION: do we want to modify the properties of b? *)
213 : jhr 4317 (liveOut, assigns)
214 :     end
215 : jhr 5151 | doStm (S.S_New(_, xs), (live, assigns)) = (addList (xs, live), assigns)
216 : jhr 4317 | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
217 :     | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
218 : jhr 4570 | doStm (S.S_MapReduce mrs, acc) = let
219 : jhr 5151 fun doMR (S.MapReduce{result, args, source, ...}, (live, assigns)) = (
220 :     markUpdate (cxt, result);
221 : jhr 4570 (* QUESTION: do we need to remove result from live? *)
222 : jhr 5151 (addList(args, live), assigns))
223 :     in
224 :     List.foldl doMR acc mrs
225 :     end
226 : jhr 4317 | doStm (_, acc) = acc
227 :     val (bnd, assigns) = doBlock (blk, VSet.empty)
228 :     in
229 :     setGlobalsOfBlock (blk, !globals)
230 :     end
231 : jhr 3501
232 : jhr 4516 fun analyze prog = let
233 : jhr 5151 val S.Program{
234 :     props, constInit, funcs, globInit, strand, create, start, update, ...
235 :     } = prog
236 : jhr 4516 val S.Strand{state, stateInit, startM, updateM, stabilizeM, ...} = strand
237 : jhr 4317 in
238 : jhr 5151 (* if the program has communication then the "pos" variable is shared *)
239 :     if Properties.hasProp Properties.StrandCommunication props
240 :     then (case List.find (fn x => (SV.nameOf x = "pos")) state
241 :     of SOME x => markSharedStateVar x
242 :     | NONE => let
243 :     fun pr s = TextIO.output(TextIO.stdErr, concat s)
244 :     in
245 :     pr ["**** impossible: missing 'pos' state variable\n"];
246 :     pr [" ** state variables:\n"];
247 :     List.app
248 :     (fn x => pr[
249 :     " nameOf(", SV.uniqueNameOf x, ") = \"",
250 :     SV.nameOf x, "\"\n"
251 :     ])
252 :     state;
253 :     raise Fail "impossible: missing 'pos' state variable"
254 :     end
255 :     (* end case *))
256 :     else ();
257 : jhr 4317 analyzeBlock ConstInit constInit;
258 :     List.app (fn (S.Func{f, body, ...}) => analyzeBlock UserFunc body) funcs;
259 :     analyzeBlock GlobalInit globInit;
260 :     analyzeBlock StateInit stateInit;
261 : jhr 4895 Option.app (analyzeBlock StartMeth) startM;
262 : jhr 4317 analyzeBlock UpdateMeth updateM;
263 :     Option.app (analyzeBlock StabilizeMeth) stabilizeM;
264 : jhr 4491 Option.app (analyzeBlock GlobalUpdate) start;
265 : jhr 4636 Option.app (analyzeBlock GlobalUpdate) update;
266 :     Create.app (analyzeBlock Create) create
267 : jhr 4317 end
268 : jhr 3538
269 : jhr 3501 end

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