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 4228 - (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 :     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 : 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 :     of SV.StrandStateVar => setFn(x, true)
103 :     | SV.StrandOutputVar => setFn(x, true)
104 : jhr 3538 | _ => ()
105 :     (* end case *))
106 :     end (* local *)
107 :    
108 : jhr 4164 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 : jhr 3840 fun markUpdate (cxt, x) = (case (cxt, SV.kindOf x)
117 :     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 :    
130 : jhr 3501 (* does a variable have local scope *)
131 :     fun isLocal x = (case SV.kindOf x
132 :     of SV.LocalVar => true
133 :     | SV.IterVar => true
134 :     | _ => false
135 :     (* end case *))
136 :    
137 : jhr 4164 (* FIXME: need to use context to filter out globals in some situations *)
138 : jhr 3840 fun analyzeBlock cxt blk = let
139 : jhr 4164 val globals = ref VSet.empty
140 : jhr 4166 fun addGlobal x = (globals := VSet.add(!globals, x))
141 :     fun addVar (x, vs) =
142 :     if isLocal x then VSet.add(vs, x)
143 :     else (case (SV.kindOf x, cxt)
144 :     of (SV.ConstVar, ConstInit) => ()
145 :     | (SV.ConstVar, _) => addGlobal x
146 :     | (SV.InputVar, ConstInit) => ()
147 :     | (SV.InputVar, _) => addGlobal x
148 :     | (SV.GlobalVar, ConstInit) => ()
149 :     | (SV.GlobalVar, GlobalInit) => ()
150 :     | (SV.GlobalVar, _) => addGlobal x
151 :     | _ => ()
152 :     (* end case *);
153 :     vs)
154 :     fun addList (xs, vs) = List.foldl addVar vs xs
155 : jhr 4164 (* 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 :     | S.E_Select _ => raise Fail "unexpected E_Select" (* should be handled by doStm *)
162 :     | S.E_Apply(_, xs) => xs
163 :     | S.E_Prim(_, _, xs, _) => xs
164 :     | S.E_Tensor(xs, _) => xs
165 :     | S.E_Seq(xs, _) => xs
166 :     | S.E_Slice(x, _, _) => [x]
167 :     | S.E_Coerce{x, ...} => [x]
168 : jhr 4228 | S.E_BorderCtl(BorderCtl.Default x, y) => [x, y]
169 :     | S.E_BorderCtl(_, x) => [x]
170 : jhr 4164 | S.E_LoadSeq _ => []
171 :     | S.E_LoadImage _ => []
172 :     | S.E_InsideImage(pos, img, _) => [pos, img]
173 :     (* end case *))
174 :     in
175 : jhr 4166 addList (u, vs)
176 : jhr 4164 end
177 : jhr 3502 fun doBlock (blk as S.Block{code, ...}, liveIn) = let
178 :     val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
179 : jhr 3501 in
180 :     setAssigned (blk, assigns);
181 : jhr 3502 setLiveIn (blk, liveIn);
182 :     setLiveOut (blk, liveOut);
183 : jhr 3501 result
184 :     end
185 :     and doStm (S.S_Var(x, NONE), (live, assigns)) =
186 :     (VSet.subtract(live, x), VSet.subtract(assigns, x))
187 :     | doStm (S.S_Var(x, SOME e), (live, assigns)) =
188 :     (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
189 : jhr 3840 | doStm (S.S_Assign(x, S.E_Select(y, z)), (live, assigns)) = (
190 :     markUpdate (cxt, x);
191 :     markSharedStateVar z;
192 :     (addVar (y, VSet.subtract(live, x)), addVar(x, assigns)))
193 :     | doStm (S.S_Assign(x, e), (live, assigns)) = (
194 :     markUpdate (cxt, x);
195 :     (addUses(e, VSet.subtract(live, x)), addVar(x, assigns)))
196 : jhr 3502 | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let
197 :     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 : jhr 3501 in
201 :     (* QUESTION: do we want to modify the properties of b? *)
202 :     (liveOut, assigns)
203 :     end
204 : jhr 4168 | doStm (S.S_IfThenElse(x, b1, b2), (liveIn, assignsIn)) = let
205 :     val liveIn = addVar(x, liveIn)
206 : jhr 3502 val (live1, assigns1) = doBlock (b1, liveIn)
207 :     val (live2, assigns2) = doBlock (b2, liveIn)
208 :     val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
209 : jhr 3501 in
210 : jhr 3502 (VSet.union(live1, live2), assigns)
211 : jhr 3501 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 : jhr 3840 | doStm (S.S_MapReduce{results, ...}, acc) = (
215 :     List.app (fn x => markUpdate (cxt, x)) results;
216 :     acc)
217 : jhr 3501 | doStm (_, acc) = acc
218 : jhr 3502 val (bnd, assigns) = doBlock (blk, VSet.empty)
219 : jhr 3501 in
220 : jhr 4164 setGlobalsOfBlock (blk, !globals)
221 : jhr 3501 end
222 :    
223 : jhr 4166 fun analyze (S.Program{constInit, funcs, globInit, strand, create, init, update, ...}) = let
224 : jhr 3840 val S.Strand{stateInit, initM, updateM, stabilizeM, ...} = strand
225 : jhr 3538 in
226 : jhr 3840 analyzeBlock ConstInit constInit;
227 : jhr 4168 List.app (fn (S.Func{f, body, ...}) => analyzeBlock UserFunc body) funcs;
228 : jhr 3995 analyzeBlock GlobalInit globInit;
229 : jhr 3840 analyzeBlock StateInit stateInit;
230 :     Option.app (analyzeBlock InitMeth) initM;
231 :     analyzeBlock UpdateMeth updateM;
232 :     Option.app (analyzeBlock StabilizeMeth) stabilizeM;
233 : jhr 4045 Create.app (analyzeBlock Create) create;
234 : jhr 3995 Option.app (analyzeBlock GlobalUpdate) init;
235 : jhr 3840 Option.app (analyzeBlock GlobalUpdate) update
236 : jhr 3538 end
237 :    
238 : jhr 3501 end

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