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 3995 - (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 3501 end = struct
32 :    
33 :     structure S = Simple
34 :     structure SV = SimpleVar
35 :     structure VMap = SV.Map
36 :     structure VSet = SV.Set
37 :    
38 : jhr 3840 datatype context
39 :     = ConstInit | GlobalInit | StateInit
40 :     | InitMeth | UpdateMeth | StabilizeMeth
41 :     | Create | GlobalUpdate
42 :    
43 : jhr 3501 local
44 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
45 :     in
46 :     val assignedVars = getFn
47 :     val setAssigned = setFn
48 :     end
49 :    
50 :     local
51 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
52 :     in
53 : jhr 3502 val liveIn = getFn
54 :     val setLiveIn = setFn
55 : jhr 3501 end
56 :    
57 : jhr 3502 local
58 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
59 :     in
60 :     val liveOut = getFn
61 :     val setLiveOut = setFn
62 :     end
63 :    
64 : jhr 3538 (* track if a global variable is updated in the global-update code *)
65 :     local
66 :     val {setFn, getFn} = SV.newFlag()
67 :     in
68 :     val updatedGlobal = getFn
69 : jhr 3840 fun markUpdatedGlobal x = setFn(x, true)
70 :     end (* local *)
71 :    
72 :     (* 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 : jhr 3538 | _ => ()
89 :     (* end case *))
90 :     end (* local *)
91 :    
92 : jhr 3840 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 : jhr 3501 (* does a variable have local scope *)
107 :     fun isLocal x = (case SV.kindOf x
108 :     of SV.LocalVar => true
109 :     | SV.IterVar => true
110 :     | _ => false
111 :     (* end case *))
112 :    
113 :     fun addVar (x, vs) = if isLocal x then VSet.add(vs, x) else vs
114 :    
115 :     fun addList (xs, vs) = List.foldl addVar vs xs
116 :    
117 :     (* compute the used local variables of a Simple AST expression *)
118 :     fun addUses (e, vs) = let
119 :     val u = (case e
120 :     of S.E_Var x => [x]
121 :     | S.E_Lit _ => []
122 : jhr 3840 | S.E_Select _ => raise Fail "unexpected E_Select" (* should be handled by doStm *)
123 : jhr 3501 | S.E_Apply _ => raise Fail "unexpected E_Apply"
124 :     | S.E_Prim(_, _, xs, _) => xs
125 :     | S.E_Tensor(xs, _) => xs
126 :     | S.E_Seq(xs, _) => xs
127 : jhr 3797 | S.E_Slice(x, _, _) => [x]
128 : jhr 3501 | S.E_Coerce{x, ...} => [x]
129 :     | S.E_LoadSeq _ => []
130 :     | S.E_LoadImage _ => []
131 :     (* end case *))
132 :     in
133 : jhr 3840 addList (u, vs)
134 : jhr 3501 end
135 :    
136 : jhr 3840 fun analyzeBlock cxt blk = let
137 : jhr 3502 fun doBlock (blk as S.Block{code, ...}, liveIn) = let
138 :     val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
139 : jhr 3501 in
140 :     setAssigned (blk, assigns);
141 : jhr 3502 setLiveIn (blk, liveIn);
142 :     setLiveOut (blk, liveOut);
143 : jhr 3501 result
144 :     end
145 :     and doStm (S.S_Var(x, NONE), (live, assigns)) =
146 :     (VSet.subtract(live, x), VSet.subtract(assigns, x))
147 :     | doStm (S.S_Var(x, SOME e), (live, assigns)) =
148 :     (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
149 : jhr 3840 | doStm (S.S_Assign(x, S.E_Select(y, z)), (live, assigns)) = (
150 :     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 : jhr 3502 | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let
157 :     val (liveOut, assigns) = doBlock (b, liveIn)
158 :     val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
159 :     val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
160 : jhr 3501 in
161 :     (* QUESTION: do we want to modify the properties of b? *)
162 :     (liveOut, assigns)
163 :     end
164 : jhr 3502 | doStm (S.S_IfThenElse(_, b1, b2), (liveIn, assignsIn)) = let
165 :     val (live1, assigns1) = doBlock (b1, liveIn)
166 :     val (live2, assigns2) = doBlock (b2, liveIn)
167 :     val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
168 : jhr 3501 in
169 : jhr 3502 (VSet.union(live1, live2), assigns)
170 : jhr 3501 end
171 :     | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
172 :     | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
173 : jhr 3840 | doStm (S.S_MapReduce{results, ...}, acc) = (
174 :     List.app (fn x => markUpdate (cxt, x)) results;
175 :     acc)
176 : jhr 3501 | doStm (_, acc) = acc
177 : jhr 3502 val (bnd, assigns) = doBlock (blk, VSet.empty)
178 : jhr 3501 in
179 :     ()
180 :     end
181 :    
182 : jhr 3995 fun analyze (S.Program{constInit, globInit, strand, create, init, update, ...}) = let
183 : jhr 3840 val S.Strand{stateInit, initM, updateM, stabilizeM, ...} = strand
184 :     val S.Create{code, ...} = create
185 : jhr 3538 in
186 : jhr 3840 analyzeBlock ConstInit constInit;
187 : jhr 3995 analyzeBlock GlobalInit globInit;
188 : jhr 3840 analyzeBlock StateInit stateInit;
189 :     Option.app (analyzeBlock InitMeth) initM;
190 :     analyzeBlock UpdateMeth updateM;
191 :     Option.app (analyzeBlock StabilizeMeth) stabilizeM;
192 :     analyzeBlock Create code;
193 : jhr 3995 Option.app (analyzeBlock GlobalUpdate) init;
194 : jhr 3840 Option.app (analyzeBlock GlobalUpdate) update
195 : jhr 3538 end
196 :    
197 : jhr 3501 end

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