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 4333 - (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 3840 | InitMeth | UpdateMeth | StabilizeMeth
44 :     | 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 :     | InitMeth => "InitMeth"
53 :     | 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 :     | (InitMeth, SV.StrandStateVar) => markVaryingStateVar x
120 :     | (InitMeth, SV.StrandOutputVar) => markVaryingStateVar x
121 :     | (UpdateMeth, SV.StrandStateVar) => markVaryingStateVar x
122 :     | (UpdateMeth, SV.StrandOutputVar) => markVaryingStateVar x
123 :     | (StabilizeMeth, SV.StrandStateVar) => markVaryingStateVar x
124 :     | (StabilizeMeth, SV.StrandOutputVar) => markVaryingStateVar x
125 :     | (GlobalUpdate, SV.InputVar) => markUpdatedGlobal x
126 :     | (GlobalUpdate, SV.GlobalVar) => markUpdatedGlobal x
127 :     | _ => ()
128 :     (* end case *))
129 : jhr 3840
130 :     fun analyzeBlock cxt blk = let
131 : jhr 4317 val globals = ref VSet.empty
132 :     fun addGlobal x = (globals := VSet.add(!globals, x))
133 : jhr 4333 fun addVar (x, vs) = let
134 :     fun addGlobal x = (globals := VSet.add(!globals, x); vs)
135 :     in
136 :     case (SV.kindOf x, cxt)
137 :     of (SV.ConstVar, ConstInit) => vs
138 : jhr 4317 | (SV.ConstVar, _) => addGlobal x
139 : jhr 4333 | (SV.InputVar, ConstInit) => vs
140 : jhr 4317 | (SV.InputVar, _) => addGlobal x
141 : jhr 4333 | (SV.GlobalVar, ConstInit) => vs
142 :     | (SV.GlobalVar, GlobalInit) => vs
143 : jhr 4317 | (SV.GlobalVar, _) => addGlobal x
144 : jhr 4333 | (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 : jhr 4317 fun addList (xs, vs) = List.foldl addVar vs xs
152 :     (* compute the used local and global variables of a Simple AST expression *)
153 :     fun addUses (e, vs) = let
154 :     val u = (case e
155 :     of S.E_Var x => [x]
156 :     | S.E_Lit _ => []
157 :     | S.E_Kernel _ => []
158 :     | S.E_Select _ => raise Fail "unexpected E_Select" (* should be handled by doStm *)
159 :     | S.E_Apply(_, xs) => xs
160 :     | S.E_Prim(_, _, xs, _) => xs
161 :     | S.E_Tensor(xs, _) => xs
162 :     | S.E_Seq(xs, _) => xs
163 :     | S.E_Tuple xs => xs
164 :     | S.E_Project(x, i) => [x]
165 :     | S.E_Slice(x, _, _) => [x]
166 :     | S.E_Coerce{x, ...} => [x]
167 :     | S.E_BorderCtl(BorderCtl.Default x, y) => [x, y]
168 :     | S.E_BorderCtl(_, x) => [x]
169 :     | S.E_LoadSeq _ => []
170 :     | S.E_LoadImage _ => []
171 :     | S.E_InsideImage(pos, img, _) => [pos, img]
172 :     (* end case *))
173 :     in
174 :     addList (u, vs)
175 :     end
176 :     fun doBlock (blk as S.Block{code, ...}, liveIn) = let
177 :     val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
178 :     in
179 :     setAssigned (blk, assigns);
180 :     setLiveIn (blk, liveIn);
181 :     setLiveOut (blk, liveOut);
182 :     result
183 :     end
184 :     and doStm (S.S_Var(x, NONE), (live, assigns)) =
185 :     (VSet.subtract(live, x), VSet.subtract(assigns, x))
186 :     | doStm (S.S_Var(x, SOME e), (live, assigns)) =
187 :     (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
188 :     | doStm (S.S_Assign(x, S.E_Select(y, z)), (live, assigns)) = (
189 :     markUpdate (cxt, x);
190 :     markSharedStateVar z;
191 :     (addVar (y, VSet.subtract(live, x)), addVar(x, assigns)))
192 :     | doStm (S.S_Assign(x, e), (live, assigns)) = (
193 :     markUpdate (cxt, x);
194 :     (addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))
195 : jhr 4333 | doStm (S.S_Foreach(x, xs, b), (liveIn, assignsIn)) = let
196 :     val liveIn = addVar(xs, liveIn)
197 : jhr 4317 val (liveOut, assigns) = doBlock (b, liveIn)
198 :     val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
199 :     val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
200 :     in
201 : jhr 3501 (* QUESTION: do we want to modify the properties of b? *)
202 : jhr 4317 (liveOut, assigns)
203 :     end
204 :     | doStm (S.S_IfThenElse(x, b1, b2), (liveIn, assignsIn)) = let
205 :     val liveIn = addVar(x, liveIn)
206 :     val (live1, assigns1) = doBlock (b1, liveIn)
207 :     val (live2, assigns2) = doBlock (b2, liveIn)
208 :     val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
209 :     in
210 :     (VSet.union(live1, live2), assigns)
211 :     end
212 :     | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
213 :     | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
214 :     | doStm (S.S_MapReduce{results, ...}, acc) = (
215 :     List.app (fn x => markUpdate (cxt, x)) results;
216 :     acc)
217 :     | doStm (_, acc) = acc
218 :     val (bnd, assigns) = doBlock (blk, VSet.empty)
219 :     in
220 :     setGlobalsOfBlock (blk, !globals)
221 :     end
222 : jhr 3501
223 : jhr 4166 fun analyze (S.Program{constInit, funcs, globInit, strand, create, init, update, ...}) = let
224 : jhr 4317 val S.Strand{stateInit, initM, updateM, stabilizeM, ...} = strand
225 :     in
226 :     analyzeBlock ConstInit constInit;
227 :     List.app (fn (S.Func{f, body, ...}) => analyzeBlock UserFunc body) funcs;
228 :     analyzeBlock GlobalInit globInit;
229 :     analyzeBlock StateInit stateInit;
230 :     Option.app (analyzeBlock InitMeth) initM;
231 :     analyzeBlock UpdateMeth updateM;
232 :     Option.app (analyzeBlock StabilizeMeth) stabilizeM;
233 :     Create.app (analyzeBlock Create) create;
234 :     Option.app (analyzeBlock GlobalUpdate) init;
235 :     Option.app (analyzeBlock GlobalUpdate) update
236 :     end
237 : jhr 3538
238 : jhr 3501 end

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