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

SCM Repository

[diderot] Annotation of /branches/vis12/src/compiler/high-il/normalize.sml
ViewVC logotype

Annotation of /branches/vis12/src/compiler/high-il/normalize.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2173 - (view) (download)

1 : jhr 1232 (* normalize.sml
2 :     *
3 :     * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *)
6 :    
7 :     structure Normalize : sig
8 :    
9 :     val transform : HighIL.program -> HighIL.program
10 :    
11 :     end = struct
12 :    
13 :     structure IL = HighIL
14 :     structure Op = HighOps
15 :     structure V = IL.Var
16 : jhr 2165 structure Ty = HighILTypes
17 : jhr 1232 structure ST = Stats
18 :    
19 :     (********** Counters for statistics **********)
20 : jhr 2173 val cntInsideScale = ST.newCounter "high-opt:inside-scale"
21 :     val cntInsideOffset = ST.newCounter "high-opt:inside-offset"
22 :     val cntInsideNeg = ST.newCounter "high-opt:inside-meg"
23 :     val cntInsideCurl = ST.newCounter "high-opt:inside-curl"
24 :     val cntInsideDiff = ST.newCounter "high-opt:inside-diff"
25 : jhr 1232 val cntProbeAdd = ST.newCounter "high-opt:probe-add"
26 :     val cntProbeSub = ST.newCounter "high-opt:probe-sub"
27 :     val cntProbeScale = ST.newCounter "high-opt:probe-scale"
28 : jhr 2173 val cntProbeOffset = ST.newCounter "high-opt:probe-offset"
29 : jhr 1232 val cntProbeNeg = ST.newCounter "high-opt:probe-neg"
30 : jhr 2173 val cntProbeCurl = ST.newCounter "high-opt:probe-curl"
31 : jhr 1232 val cntDiffField = ST.newCounter "high-opt:diff-field"
32 :     val cntDiffAdd = ST.newCounter "high-opt:diff-add"
33 :     val cntDiffScale = ST.newCounter "high-opt:diff-scale"
34 : jhr 2173 val cntDiffOffset = ST.newCounter "high-opt:diff-offset"
35 : jhr 1232 val cntDiffNeg = ST.newCounter "high-opt:diff-neg"
36 :     val cntUnused = ST.newCounter "high-opt:unused"
37 :     val firstCounter = cntProbeAdd
38 :     val lastCounter = cntUnused
39 :    
40 :     structure UnusedElim = UnusedElimFn (
41 :     structure IL = IL
42 :     val cntUnused = cntUnused)
43 :    
44 :     fun useCount (IL.V{useCnt, ...}) = !useCnt
45 :    
46 :     (* adjust a variable's use count *)
47 :     fun incUse (IL.V{useCnt, ...}) = (useCnt := !useCnt + 1)
48 :     fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
49 : jhr 2165 fun use x = (incUse x; x)
50 : jhr 1232
51 :     fun getRHS x = (case V.binding x
52 :     of IL.VB_RHS(IL.OP arg) => SOME arg
53 :     | IL.VB_RHS(IL.VAR x') => getRHS x'
54 :     | _ => NONE
55 :     (* end case *))
56 :    
57 : jhr 2165 (* get the binding of a kernel variable *)
58 :     fun getKernelRHS h = (case getRHS h
59 :     of SOME(Op.Kernel(kernel, k), []) => (kernel, k)
60 :     | _ => raise Fail(concat[
61 :     "bogus kernel binding ", V.toString h, " = ", IL.vbToString(V.binding h)
62 :     ])
63 :     (* end case *))
64 :    
65 : jhr 1232 (* optimize the rhs of an assignment, returning NONE if there is no change *)
66 :     fun doRHS (lhs, IL.OP rhs) = (case rhs
67 : jhr 2173 of (Op.Inside dim, [pos, f]) => (case getRHS f
68 :     of SOME(Op.Field _, _) => NONE (* direct inside test does not need rewrite *)
69 :     | SOME(Op.AddField, [f', g']) => raise Fail "inside(f+g)"
70 :     | SOME(Op.SubField, [f', g']) => raise Fail "inside(f-g)"
71 :     | SOME(Op.ScaleField, [_, f']) => (
72 :     ST.tick cntInsideScale;
73 :     decUse f;
74 :     SOME[(lhs, IL.OP(Op.Inside dim, [pos, use f']))])
75 :     | SOME(Op.OffsetField, [f', _]) => (
76 :     ST.tick cntInsideOffset;
77 :     decUse f;
78 :     SOME[(lhs, IL.OP(Op.Inside dim, [pos, use f']))])
79 :     | SOME(Op.NegField, [f']) => (
80 :     ST.tick cntInsideNeg;
81 :     decUse f;
82 :     SOME[(lhs, IL.OP(Op.Inside dim, [pos, use f']))])
83 :     | SOME(Op.CurlField _, [f']) => (
84 :     ST.tick cntInsideCurl;
85 :     decUse f;
86 :     SOME[(lhs, IL.OP(Op.Inside dim, [pos, use f']))])
87 :     | SOME(Op.DiffField, [f']) => (
88 :     ST.tick cntInsideDiff;
89 :     decUse f;
90 :     SOME[(lhs, IL.OP(Op.Inside dim, [pos, use f']))])
91 :     | _ => raise Fail(concat[
92 :     "inside: bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)
93 :     ])
94 :     (* end case *))
95 :     | (Op.Probe(domTy, rngTy), [f, pos]) => (case getRHS f
96 : jhr 1232 of SOME(Op.Field _, _) => NONE (* direct probe does not need rewrite *)
97 :     | SOME(Op.AddField, [f', g']) => let
98 :     (* rewrite to (f@pos) + (g@pos) *)
99 :     val lhs1 = IL.Var.copy lhs
100 :     val lhs2 = IL.Var.copy lhs
101 :     in
102 :     ST.tick cntProbeAdd;
103 :     decUse f;
104 :     incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;
105 :     SOME[
106 :     (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
107 :     (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),
108 :     (lhs, IL.OP(Op.Add rngTy, [lhs1, lhs2]))
109 :     ]
110 :     end
111 :     | SOME(Op.SubField, [f', g']) => let
112 :     (* rewrite to (f@pos) - (g@pos) *)
113 :     val lhs1 = IL.Var.copy lhs
114 :     val lhs2 = IL.Var.copy lhs
115 :     in
116 :     ST.tick cntProbeSub;
117 :     decUse f;
118 :     incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;
119 :     SOME[
120 :     (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
121 :     (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),
122 :     (lhs, IL.OP(Op.Sub rngTy, [lhs1, lhs2]))
123 :     ]
124 :     end
125 :     | SOME(Op.ScaleField, [s, f']) => let
126 :     (* rewrite to s*(f'@pos) *)
127 :     val lhs' = IL.Var.copy lhs
128 :     in
129 :     ST.tick cntProbeScale;
130 :     decUse f;
131 :     SOME[
132 : jhr 2173 (lhs', IL.OP(Op.Probe(domTy, rngTy), [use f', pos])),
133 :     (lhs, IL.OP(Op.Scale rngTy, [use s, use lhs']))
134 : jhr 1232 ]
135 :     end
136 : jhr 2173 | SOME(Op.OffsetField, [f', s]) => let
137 :     (* rewrite to (f'@pos) + s *)
138 :     val lhs' = IL.Var.copy lhs
139 :     in
140 :     ST.tick cntProbeOffset;
141 :     decUse f;
142 :     SOME[
143 :     (lhs', IL.OP(Op.Probe(domTy, rngTy), [use f', pos])),
144 :     (lhs, IL.OP(Op.Add rngTy, [use lhs', use s]))
145 :     ]
146 :     end
147 : jhr 1232 | SOME(Op.NegField, [f']) => let
148 :     (* rewrite to -(f'@pos) *)
149 :     val lhs' = IL.Var.copy lhs
150 :     in
151 :     ST.tick cntProbeNeg;
152 :     decUse f;
153 :     incUse lhs'; incUse f';
154 :     SOME[
155 :     (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
156 :     (lhs, IL.OP(Op.Neg rngTy, [lhs']))
157 :     ]
158 :     end
159 : jhr 2165 | SOME(Op.CurlField 2, [f']) => (case getRHS f'
160 :     of SOME(Op.Field dim, [v, h]) => let
161 :     (* rewrite to (D f')@pos[1,0] - (D f')@pos[0,1] *)
162 :     val (kernel, k) = getKernelRHS h
163 :     val h' = IL.Var.copy h
164 :     val f'' = IL.Var.copy f'
165 :     val mat22 = Ty.TensorTy[2,2]
166 :     val m = IL.Var.new("m", mat22)
167 :     val zero = IL.Var.new("zero", Ty.intTy)
168 :     val one = IL.Var.new("one", Ty.intTy)
169 :     val m10 = IL.Var.new("m_10", Ty.realTy)
170 :     val m01 = IL.Var.new("m_01", Ty.realTy)
171 :     in
172 : jhr 2173 ST.tick cntProbeCurl;
173 : jhr 2165 decUse f;
174 :     SOME[
175 :     (h', IL.OP(Op.Kernel(kernel, k+1), [])),
176 :     (f'', IL.OP(Op.Field dim, [use v, use h'])),
177 :     (m, IL.OP(Op.Probe(domTy, mat22), [use f'', pos])),
178 :     (zero, IL.LIT(Literal.Int 0)),
179 :     (one, IL.LIT(Literal.Int 1)),
180 :     (m10, IL.OP(Op.TensorSub mat22, [use m, use one, use zero])),
181 :     (m01, IL.OP(Op.TensorSub mat22, [use m, use zero, use one])),
182 :     (lhs, IL.OP(Op.Sub Ty.realTy, [use m10, use m01]))
183 :     ]
184 :     end
185 :     | _ => raise Fail(concat[
186 :     "bogus field binding ", V.toString f', " = ", IL.vbToString(V.binding f')
187 :     ])
188 :     (* end case *))
189 :     | SOME(Op.CurlField 3, [f']) => (case getRHS f'
190 :     of SOME(Op.Field dim, [v, h]) => let
191 :     (* rewrite to
192 :     * [ (D f')@pos[2,1] - (D f')@pos[1,2] ]
193 :     * [ (D f')@pos[0,2] - (D f')@pos[2,0] ]
194 :     * [ (D f')@pos[1,0] - (D f')@pos[0,1] ]
195 :     *)
196 :     val (kernel, k) = getKernelRHS h
197 :     val h' = IL.Var.copy h
198 :     val f'' = IL.Var.copy f'
199 :     val mat33 = Ty.TensorTy[3,3]
200 :     val m = IL.Var.new("m", mat33)
201 :     val zero = IL.Var.new("zero", Ty.intTy)
202 :     val one = IL.Var.new("one", Ty.intTy)
203 :     val two = IL.Var.new("two", Ty.intTy)
204 :     val m21 = IL.Var.new("m_21", Ty.realTy)
205 :     val m12 = IL.Var.new("m_12", Ty.realTy)
206 :     val m02 = IL.Var.new("m_02", Ty.realTy)
207 :     val m20 = IL.Var.new("m_20", Ty.realTy)
208 :     val m10 = IL.Var.new("m_10", Ty.realTy)
209 :     val m01 = IL.Var.new("m_01", Ty.realTy)
210 :     val lhs0 = IL.Var.new("lhs0", Ty.realTy)
211 :     val lhs1 = IL.Var.new("lhs1", Ty.realTy)
212 :     val lhs2 = IL.Var.new("lhs2", Ty.realTy)
213 :     in
214 : jhr 2173 ST.tick cntProbeCurl;
215 : jhr 2165 decUse f;
216 :     SOME[
217 :     (h', IL.OP(Op.Kernel(kernel, k+1), [])),
218 :     (f'', IL.OP(Op.Field dim, [use v, use h'])),
219 :     (m, IL.OP(Op.Probe(domTy, mat33), [use f'', pos])),
220 :     (zero, IL.LIT(Literal.Int 0)),
221 :     (one, IL.LIT(Literal.Int 1)),
222 :     (two, IL.LIT(Literal.Int 2)),
223 :     (m21, IL.OP(Op.TensorSub mat33, [use m, use two, use one])),
224 :     (m12, IL.OP(Op.TensorSub mat33, [use m, use one, use two])),
225 :     (lhs0, IL.OP(Op.Sub Ty.realTy, [use m21, use m12])),
226 :     (m02, IL.OP(Op.TensorSub mat33, [use m, use zero, use two])),
227 :     (m20, IL.OP(Op.TensorSub mat33, [use m, use two, use zero])),
228 :     (lhs1, IL.OP(Op.Sub Ty.realTy, [use m02, use m20])),
229 :     (m10, IL.OP(Op.TensorSub mat33, [use m, use one, use zero])),
230 :     (m01, IL.OP(Op.TensorSub mat33, [use m, use zero, use one])),
231 :     (lhs2, IL.OP(Op.Sub Ty.realTy, [use m10, use m01])),
232 :     (lhs, IL.CONS(Ty.TensorTy[3], [lhs0, lhs1, lhs2]))
233 :     ]
234 :     end
235 :     | _ => raise Fail(concat[
236 : jhr 2173 "curl: bogus field binding ", V.toString f', " = ", IL.vbToString(V.binding f')
237 : jhr 2165 ])
238 :     (* end case *))
239 : jhr 2173 | SOME(Op.DiffField, _) => NONE (* need further rewriting *)
240 : jhr 1232 | _ => raise Fail(concat[
241 : jhr 2173 "probe: bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)
242 : jhr 1232 ])
243 :     (* end case *))
244 :     | (Op.DiffField, [f]) => (case (getRHS f)
245 : jhr 2165 of SOME(Op.Field dim, [v, h]) => let
246 :     val (kernel, k) = getKernelRHS h
247 :     val h' = IL.Var.copy h
248 :     in
249 :     ST.tick cntDiffField;
250 :     decUse f;
251 :     incUse h'; incUse v;
252 :     SOME[
253 :     (h', IL.OP(Op.Kernel(kernel, k+1), [])),
254 :     (lhs, IL.OP(Op.Field dim, [v, h']))
255 :     ]
256 :     end
257 : jhr 1232 | SOME(Op.AddField, [f, g]) => raise Fail "Diff(f+g)"
258 :     | SOME(Op.SubField, [f, g]) => raise Fail "Diff(f-g)"
259 :     | SOME(Op.ScaleField, [s, f']) => let
260 :     (* rewrite to s*(D f) *)
261 :     val lhs' = IL.Var.copy lhs
262 :     in
263 :     ST.tick cntDiffScale;
264 :     decUse f;
265 :     incUse lhs'; incUse f'; incUse s;
266 :     SOME[
267 :     (lhs', IL.OP(Op.DiffField, [f'])),
268 :     (lhs, IL.OP(Op.ScaleField, [s, lhs']))
269 :     ]
270 :     end
271 : jhr 2173 | SOME(Op.OffsetField, [f', s]) => (
272 :     (* rewrite to (D f) *)
273 :     ST.tick cntDiffOffset;
274 :     decUse f;
275 :     SOME[(lhs, IL.OP(Op.DiffField, [use f']))])
276 : jhr 1232 | SOME(Op.NegField, [f']) => let
277 :     (* rewrite to -(D f') *)
278 :     val lhs' = IL.Var.copy lhs
279 :     in
280 :     ST.tick cntDiffNeg;
281 :     decUse f;
282 :     incUse lhs'; incUse f';
283 :     SOME[
284 :     (lhs', IL.OP(Op.DiffField, [f'])),
285 :     (lhs, IL.OP(Op.NegField, [lhs']))
286 :     ]
287 :     end
288 :     | _ => NONE
289 :     (* end case *))
290 : jhr 2165 | (Op.CurlField _, [f]) => (case (getRHS f)
291 :     (* FIXME: the following is just the constant 0 field, but we don't have
292 :     * a representation of constant fields
293 :     *)
294 :     of SOME(Op.AddField, [f, g]) => raise Fail "curl(f+g)"
295 :     | SOME(Op.SubField, [f, g]) => raise Fail "curl(f-g)"
296 :     | SOME(Op.ScaleField, [s, f']) => raise Fail "curl(s*f)"
297 :     | SOME(Op.NegField, [f']) => raise Fail "curl(-f)"
298 :     | SOME(Op.DiffField, _) => raise Fail "curl of del"
299 :     | _ => NONE
300 :     (* end case *))
301 : jhr 1232 | _ => NONE
302 :     (* end case *))
303 :     | doRHS _ = NONE
304 :    
305 :     (* simplify expressions *)
306 :     fun simplify (nd as IL.ND{kind=IL.ASSIGN{stm=(y, rhs), ...}, ...}) =
307 :     if (useCount y = 0)
308 :     then () (* skip unused assignments *)
309 :     else (case doRHS(y, rhs)
310 :     of SOME[] => IL.CFG.deleteNode nd
311 : jhr 1640 | SOME assigns => let
312 :     val assigns = List.map
313 :     (fn (y, rhs) => (V.setBinding(y, IL.VB_RHS rhs); IL.ASSGN(y, rhs)))
314 :     assigns
315 :     in
316 :     IL.CFG.replaceNodeWithCFG (nd, IL.CFG.mkBlock assigns)
317 :     end
318 : jhr 1232 | NONE => ()
319 :     (* end case *))
320 :     | simplify _ = ()
321 :    
322 :     fun loopToFixPt f = let
323 :     fun loop n = let
324 :     val () = f ()
325 :     val n' = Stats.sum{from=firstCounter, to=lastCounter}
326 :     in
327 :     if (n = n') then () else loop n'
328 :     end
329 :     in
330 :     loop (Stats.sum{from=firstCounter, to=lastCounter})
331 :     end
332 :    
333 : jhr 1640 fun transform (prog as IL.Program{props, globalInit, initially, strands}) = let
334 : jhr 1232 fun doCFG cfg = (
335 :     loopToFixPt (fn () => IL.CFG.apply simplify cfg);
336 :     loopToFixPt (fn () => ignore(UnusedElim.reduce cfg)))
337 :     fun doMethod (IL.Method{body, ...}) = doCFG body
338 :     fun doStrand (IL.Strand{stateInit, methods, ...}) = (
339 :     doCFG stateInit;
340 :     List.app doMethod methods)
341 :     fun optPass () = (
342 :     doCFG globalInit;
343 :     List.app doStrand strands)
344 :     in
345 :     loopToFixPt optPass;
346 :     (* FIXME: after optimization, we should filter out any globals that are now unused *)
347 :     IL.Program{
348 : jhr 1640 props = props,
349 : jhr 1232 globalInit = globalInit,
350 :     initially = initially, (* FIXME: we should optimize this code *)
351 :     strands = strands
352 :     }
353 :     end
354 :    
355 :     end

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