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

SCM Repository

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

Annotation of /branches/vis15/src/compiler/simplify/simple-contract.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4043 - (view) (download)

1 : jhr 3468 (* simple-contract.sml
2 :     *
3 :     * This is a limited contraction phase for the SimpleAST representation. The purpose is
4 :     * to eliminate unused variables and dead code. Specifically, the following transformations
5 :     * are performed:
6 :     *
7 :     * -- unused constant and global variables are elminated
8 :     *
9 :     * -- unused strand state variables are eliminated (but not outputs)
10 :     *
11 :     * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
12 :     *
13 :     * COPYRIGHT (c) 2015 The University of Chicago
14 :     * All rights reserved.
15 :     *)
16 :    
17 :     structure SimpleContract : sig
18 :    
19 :     val transform : Simple.program -> Simple.program
20 :    
21 :     end = struct
22 :    
23 :     structure S = Simple
24 :     structure SV = SimpleVar
25 :     structure ST = Stats
26 :    
27 :     (********** Counters for statistics **********)
28 :     val cntUnusedConst = ST.newCounter "simple-contract:unused-constant"
29 :     val cntUnusedGlobal = ST.newCounter "simple-contract:unused-global-var"
30 :     val cntUnusedState = ST.newCounter "simple-contract:unused-state-var"
31 :     val cntUnusedLocal = ST.newCounter "simple-contract:unused-local-var"
32 :     val cntDeadAssign = ST.newCounter "simple-contract:dead-assign"
33 :     val cntDeadIf = ST.newCounter "simple-contract:dead-if"
34 :     val cntDeadForeach = ST.newCounter "simple-contract:dead-foreach"
35 :     val firstCounter = cntUnusedConst
36 :     val lastCounter = cntDeadForeach
37 :    
38 :     fun sumChanges () = ST.sum {from=firstCounter, to=lastCounter}
39 :    
40 : jhr 3510 (* for constant, global, strand-state variables, and local variables we count uses *)
41 : jhr 3468 local
42 :     val {clrFn, getFn, peekFn, ...} = SV.newProp (fn _ => ref 0)
43 :     in
44 :     fun use x = let val r = getFn x in r := !r + 1 end
45 :     fun unuse x = let val r = getFn x in r := !r - 1 end
46 :     fun markUsed x = (case SV.kindOf x
47 :     of SV.ConstVar => use x
48 :     | SV.GlobalVar => use x
49 :     | SV.StrandStateVar => use x
50 :     | SV.StrandOutputVar => use x
51 :     | SV.LocalVar => use x
52 :     | _ => ()
53 :     (* end case *))
54 : jhr 3510 fun useCnt x = (case peekFn x of SOME(ref n) => n | _ => 0)
55 :     fun isUsed x = (case SV.kindOf x
56 :     of SV.InputVar => true (* inputs are always in use *)
57 :     | SV.StrandOutputVar => true (* outputs are always in use *)
58 :     | _ => (case peekFn x of SOME(ref n) => (n > 0) | _ => false)
59 :     (* end case *))
60 : jhr 3468 fun clrUsedMark x = clrFn x
61 :     end (* local *)
62 :    
63 :     (* analyze a block for unused variables *)
64 :     fun analyzeBlock blk = let
65 : jhr 3501 fun analyzeBlk (S.Block{code, ...}) = List.app analyzeStm code
66 : jhr 3468 and analyzeStm stm = (case stm
67 :     of S.S_Var(x, NONE) => ()
68 :     | S.S_Var(x, SOME e) => analyzeExp e
69 :     | S.S_Assign(x, e) => analyzeExp e
70 :     | S.S_IfThenElse(x, b1, b2) => (markUsed x; analyzeBlk b1; analyzeBlk b2)
71 : jhr 3509 | S.S_Foreach(x, xs, blk) => (markUsed xs; analyzeBlk blk)
72 : jhr 3468 | S.S_New(strnd, xs) => List.app markUsed xs
73 :     | S.S_Continue => ()
74 :     | S.S_Die => ()
75 :     | S.S_Stabilize => ()
76 :     | S.S_Return x => markUsed x
77 :     | S.S_Print xs => List.app markUsed xs
78 :     | S.S_MapReduce{args, ...} => List.app markUsed args
79 :     (* end case *))
80 :     and analyzeExp exp = (case exp
81 :     of S.E_Var x => markUsed x
82 :     | S.E_Lit _ => ()
83 : jhr 4043 | S.E_Kernel _ => ()
84 : jhr 3468 | S.E_Select(x, fld) => (markUsed x; markUsed fld)
85 :     | S.E_Apply(f, xs, _) => List.app markUsed xs
86 :     | S.E_Prim(_, _, xs, _) => List.app markUsed xs
87 :     | S.E_Tensor(xs, _) => List.app markUsed xs
88 :     | S.E_Seq(xs, _) => List.app markUsed xs
89 : jhr 3797 | S.E_Slice(x, _, _) => markUsed x
90 : jhr 3468 | S.E_Coerce{x, ...} => markUsed x
91 :     | S.E_LoadSeq _ => ()
92 :     | S.E_LoadImage _ => ()
93 : jhr 4043 | S.E_InsideImage(pos, img, _) => (markUsed pos; markUsed img)
94 : jhr 3468 (* end case *))
95 :     in
96 :     analyzeBlk blk
97 :     end
98 :    
99 :     (* count the variable uses in a strand *)
100 :     fun analyzeStrand (S.Strand{state, stateInit, initM, updateM, stabilizeM, ...}) = (
101 :     (* mark all outputs as being used *)
102 :     List.app
103 :     (fn x => (case SV.kindOf x of SV.StrandOutputVar => use x | _ => ()))
104 :     state;
105 :     analyzeBlock stateInit;
106 :     Option.app analyzeBlock initM;
107 :     analyzeBlock updateM;
108 :     Option.app analyzeBlock stabilizeM)
109 :    
110 :     (* an initial pass to count the variable uses over the entire program *)
111 : jhr 3995 fun analyze (S.Program{constInit, globInit, strand, create, init, update, ...}) = (
112 : jhr 3468 analyzeBlock constInit;
113 : jhr 3995 analyzeBlock globInit;
114 : jhr 3468 analyzeStrand strand;
115 : jhr 3485 case create of S.Create{code, ...} => analyzeBlock code;
116 : jhr 3995 Option.app analyzeBlock init;
117 : jhr 3468 Option.app analyzeBlock update)
118 :    
119 :     (* rewrite a block and remove references to unused variables *)
120 :     fun contractBlock blk = let
121 :     fun delete exp = (case exp
122 :     of S.E_Var x => unuse x
123 :     | S.E_Lit _ => ()
124 : jhr 4043 | S.E_Kernel _ => ()
125 : jhr 3468 | S.E_Select(x, fld) => (unuse x; unuse fld)
126 :     | S.E_Apply(f, xs, _) => List.app unuse xs
127 :     | S.E_Prim(_, _, xs, _) => List.app unuse xs
128 :     | S.E_Tensor(xs, _) => List.app unuse xs
129 :     | S.E_Seq(xs, _) => List.app unuse xs
130 : jhr 3797 | S.E_Slice(x, _, _) => unuse x
131 : jhr 3468 | S.E_Coerce{x, ...} => unuse x
132 :     | S.E_LoadSeq _ => ()
133 :     | S.E_LoadImage _ => ()
134 : jhr 4043 | S.E_InsideImage(pos, img, _) => (unuse pos; unuse img)
135 : jhr 3468 (* end case *))
136 : jhr 3501 fun contractBlk (S.Block{props, code}) = let
137 : jhr 3468 fun contractStms [] = []
138 :     | contractStms (stm::stms) = (case stm
139 :     of S.S_Var(x, NONE) => if isUsed x
140 :     then stm :: contractStms stms
141 :     else (ST.tick cntUnusedLocal; contractStms stms)
142 :     | S.S_Var(x, SOME e) => if isUsed x
143 :     then stm :: contractStms stms
144 :     else (ST.tick cntUnusedLocal; delete e; contractStms stms)
145 :     | S.S_Assign(x, e) => if isUsed x
146 :     then stm :: contractStms stms
147 :     else (ST.tick cntDeadAssign; delete e; contractStms stms)
148 :     | S.S_IfThenElse(x, b1, b2) => (
149 :     case (contractBlk b1, contractBlk b2)
150 : jhr 3502 of (S.Block{code=[], ...}, S.Block{code=[], ...}) => (
151 : jhr 3468 ST.tick cntDeadIf; unuse x; contractStms stms)
152 :     | (b1, b2) => S.S_IfThenElse(x, b1, b2) :: contractStms stms
153 :     (* end case *))
154 :     | S.S_Foreach(x, xs, blk) => (
155 :     case contractBlk blk
156 : jhr 3501 of S.Block{code=[], ...} => (
157 : jhr 3468 ST.tick cntDeadForeach; unuse xs; contractStms stms)
158 :     | blk => S.S_Foreach(x, xs, blk) :: contractStms stms
159 :     (* end case *))
160 :     | _ => stm :: contractStms stms
161 :     (* end case *))
162 :     in
163 : jhr 3501 S.Block{props = props, code = contractStms code}
164 : jhr 3468 end
165 :     fun loop (nChanges, blk) = let
166 :     val blk = contractBlk blk
167 :     val n = sumChanges()
168 :     in
169 :     if (n <> nChanges) then loop (n, blk) else blk
170 :     end
171 :     in
172 :     loop (sumChanges(), blk)
173 :     end
174 :    
175 :     (* contract a strand *)
176 :     fun contractStrand strand = let
177 :     val S.Strand{name, params, state, stateInit, initM, updateM, stabilizeM} = strand
178 :     in
179 :     S.Strand{
180 :     name = name, params = params, state = state,
181 :     stateInit = contractBlock stateInit,
182 :     initM = Option.map contractBlock initM,
183 :     updateM = contractBlock updateM,
184 :     stabilizeM = Option.map contractBlock stabilizeM
185 :     }
186 :     end
187 :    
188 :     (* contract a program *)
189 :     fun contractProg (nChanges, prog) = let
190 :     val S.Program{
191 : jhr 3995 props, consts, inputs, constInit, globals, funcs,
192 :     globInit, strand, create, init, update
193 : jhr 3468 } = prog
194 :     val constInit = contractBlock constInit
195 : jhr 3995 val globInit = contractBlock globInit
196 : jhr 3468 val strand = contractStrand strand
197 : jhr 3995 val init = Option.map contractBlock init
198 : jhr 3468 val update = Option.map contractBlock update
199 :     val n = sumChanges()
200 :     in
201 :     if n = nChanges
202 :     then (n, prog)
203 :     else (n, S.Program{
204 :     props = props, consts = consts, inputs = inputs,
205 :     constInit = constInit, globals = globals, funcs = funcs,
206 : jhr 3995 globInit = globInit, strand = strand, create = create,
207 :     init = init, update = update
208 : jhr 3468 })
209 :     end
210 :    
211 :     (* remove unused state variables from a strand and clear properties *)
212 :     fun finishStrand strand = let
213 :     val S.Strand{name, params, state, stateInit, initM, updateM, stabilizeM} = strand
214 :     val (used, unused) = List.partition isUsed state
215 :     in
216 :     List.app clrUsedMark used;
217 :     if List.null unused
218 :     then strand
219 : jhr 3509 else (
220 :     List.app (fn _ => ST.tick cntUnusedState) unused;
221 :     S.Strand{
222 :     name = name, params = params, state = used,
223 :     stateInit = stateInit,
224 :     initM = initM, updateM = updateM, stabilizeM = stabilizeM
225 :     })
226 : jhr 3468 end
227 :    
228 :     (* remove unused constant, global, and state variables from the program *)
229 :     fun finishProg prog = let
230 :     val S.Program{
231 : jhr 3995 props, consts, inputs, constInit, globals, funcs,
232 :     globInit, strand, create, init, update
233 : jhr 3468 } = prog
234 : jhr 3509 fun removeUnused cntr x = if isUsed x
235 :     then true
236 :     else (ST.tick cntr; false)
237 : jhr 3510 val prog = S.Program{
238 :     props = props,
239 :     consts = List.filter (removeUnused cntUnusedConst) consts,
240 :     inputs = inputs,
241 :     constInit = constInit,
242 :     globals = List.filter (removeUnused cntUnusedGlobal) globals,
243 :     funcs = funcs,
244 : jhr 3995 globInit = globInit,
245 : jhr 3510 strand = finishStrand strand,
246 :     create = create,
247 : jhr 3995 init = init,
248 : jhr 3510 update = update
249 :     }
250 : jhr 3468 in
251 : jhr 3510 List.app clrUsedMark consts;
252 :     List.app clrUsedMark globals;
253 :     prog
254 : jhr 3468 end
255 :    
256 :     fun transform prog = let
257 :     (* first we count the variable uses over the entire program *)
258 :     val () = analyze prog
259 :     (* then contract until there are no more changes *)
260 :     val n = sumChanges()
261 :     val (nChanges, prog) = let
262 :     fun loop (nChanges, prog) = let
263 :     val (n, prog) = contractProg (nChanges, prog)
264 :     in
265 :     if (n <> nChanges) then loop (n, prog) else (n, prog)
266 :     end
267 :     in
268 :     loop (n, prog)
269 :     end
270 :     in
271 :     (* finally we finish the program by removing unused constant, global, and state variables *)
272 :     if (n <> nChanges)
273 :     then finishProg prog
274 :     else prog (* no contraction occurred *)
275 :     end
276 :    
277 :     end

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