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

SCM Repository

[diderot] Annotation of /trunk/src/compiler/high-il/high-opt.sml
ViewVC logotype

Annotation of /trunk/src/compiler/high-il/high-opt.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1116 - (view) (download)

1 : jhr 287 (* high-opt.sml
2 :     *
3 : jhr 435 * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 : jhr 287 * All rights reserved.
5 :     *
6 :     * Optimization of the HighIL representation of Diderot terms. The main
7 :     * task of this phase is to statically resolve field definitions.
8 :     *)
9 :    
10 :     structure HighOptimizer : sig
11 :    
12 :     val optimize : HighIL.program -> HighIL.program
13 :    
14 :     end = struct
15 :    
16 :     structure IL = HighIL
17 : jhr 338 structure Op = HighOps
18 : jhr 287 structure V = IL.Var
19 : jhr 320 structure ST = Stats
20 : jhr 338 structure F = FieldDef
21 : jhr 287
22 : jhr 320 (********** Counters for statistics **********)
23 : jhr 1116 val cntProbeAdd = ST.newCounter "high-opt:probe-add"
24 :     val cntProbeSub = ST.newCounter "high-opt:probe-sub"
25 :     val cntProbeScale = ST.newCounter "high-opt:probe-scale"
26 :     val cntProbeNeg = ST.newCounter "high-opt:probe-neg"
27 :     val cntDiffField = ST.newCounter "high-opt:diff-field"
28 :     val cntDiffAdd = ST.newCounter "high-opt:diff-add"
29 :     val cntDiffScale = ST.newCounter "high-opt:diff-scale"
30 :     val cntDiffNeg = ST.newCounter "high-opt:diff-neg"
31 : jhr 320 val cntUnused = ST.newCounter "high-opt:unused"
32 : jhr 1116 val firstCounter = cntProbeAdd
33 : jhr 338 val lastCounter = cntUnused
34 : jhr 320
35 : jhr 1116 structure UnusedElim = UnusedElimFn (
36 :     structure IL = IL
37 :     val cntUnused = cntUnused)
38 :    
39 : jhr 320 fun useCount (IL.V{useCnt, ...}) = !useCnt
40 :    
41 : jhr 1116 (* adjust a variable's use count *)
42 :     fun incUse (IL.V{useCnt, ...}) = (useCnt := !useCnt + 1)
43 : jhr 287 fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
44 :    
45 : jhr 372 fun getRHS x = (case V.binding x
46 :     of IL.VB_RHS(IL.OP arg) => SOME arg
47 : jhr 1116 | IL.VB_RHS(IL.VAR x') => getRHS x'
48 : jhr 372 | _ => NONE
49 :     (* end case *))
50 : jhr 287
51 :     (* optimize the rhs of an assignment, returning NONE if there is no change *)
52 : jhr 1116 fun doRHS (lhs, IL.OP rhs) = (case rhs
53 :     of (Op.Probe(domTy, rngTy), [f, pos]) => (case getRHS f
54 :     of SOME(Op.Field _, _) => NONE (* direct probe does not need rewrite *)
55 :     | SOME(Op.AddField, [f', g']) => let
56 :     (* rewrite to (f@pos) + (g@pos) *)
57 :     val lhs1 = IL.Var.copy lhs
58 :     val lhs2 = IL.Var.copy lhs
59 :     in
60 :     ST.tick cntProbeAdd;
61 :     decUse f;
62 :     incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;
63 :     SOME[
64 :     (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
65 :     (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),
66 :     (lhs, IL.OP(Op.Add rngTy, [lhs1, lhs2]))
67 :     ]
68 :     end
69 :     | SOME(Op.SubField, [f', g']) => let
70 :     (* rewrite to (f@pos) - (g@pos) *)
71 :     val lhs1 = IL.Var.copy lhs
72 :     val lhs2 = IL.Var.copy lhs
73 :     in
74 :     ST.tick cntProbeSub;
75 :     decUse f;
76 :     incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;
77 :     SOME[
78 :     (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
79 :     (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),
80 :     (lhs, IL.OP(Op.Sub rngTy, [lhs1, lhs2]))
81 :     ]
82 :     end
83 :     | SOME(Op.ScaleField, [s, f']) => let
84 :     (* rewrite to s*(f'@pos) *)
85 :     val lhs' = IL.Var.copy lhs
86 :     in
87 :     ST.tick cntProbeScale;
88 :     decUse f;
89 :     incUse lhs'; incUse f'; incUse s;
90 :     SOME[
91 :     (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
92 :     (lhs, IL.OP(Op.Scale rngTy, [s, lhs']))
93 :     ]
94 :     end
95 :     | SOME(Op.NegField, [f']) => let
96 :     (* rewrite to -(f'@pos) *)
97 :     val lhs' = IL.Var.copy lhs
98 :     in
99 :     ST.tick cntProbeNeg;
100 :     decUse f;
101 :     incUse lhs'; incUse f';
102 :     SOME[
103 :     (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
104 :     (lhs, IL.OP(Op.Neg rngTy, [lhs']))
105 :     ]
106 :     end
107 :     | _ => raise Fail(concat[
108 :     "bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)
109 :     ])
110 : jhr 287 (* end case *))
111 : jhr 1116 | (Op.DiffField, [f]) => (case (getRHS f)
112 :     of SOME(Op.Field dim, [v, h]) => (case getRHS h
113 :     of SOME(Op.Kernel(kernel, k), []) => let
114 :     val h' = IL.Var.copy h
115 :     in
116 :     ST.tick cntDiffField;
117 :     decUse f;
118 :     incUse h'; incUse v;
119 :     SOME[
120 :     (h', IL.OP(Op.Kernel(kernel, k+1), [])),
121 :     (lhs, IL.OP(Op.Field dim, [v, h']))
122 :     ]
123 :     end
124 :     | _ => raise Fail(concat[
125 :     "bogus kernel binding ", V.toString h, " = ", IL.vbToString(V.binding h)
126 :     ])
127 :     (* end case *))
128 :     | SOME(Op.AddField, [f, g]) => raise Fail "Diff(f+g)"
129 :     | SOME(Op.SubField, [f, g]) => raise Fail "Diff(f-g)"
130 :     | SOME(Op.ScaleField, [s, f']) => let
131 :     (* rewrite to s*(D f) *)
132 :     val lhs' = IL.Var.copy lhs
133 :     in
134 :     ST.tick cntDiffScale;
135 :     decUse f;
136 :     incUse lhs'; incUse f'; incUse s;
137 :     SOME[
138 :     (lhs', IL.OP(Op.DiffField, [f'])),
139 :     (lhs, IL.OP(Op.ScaleField, [s, lhs']))
140 :     ]
141 :     end
142 :     | SOME(Op.NegField, [f']) => let
143 :     (* rewrite to -(D f') *)
144 :     val lhs' = IL.Var.copy lhs
145 :     in
146 :     ST.tick cntDiffNeg;
147 :     decUse f;
148 :     incUse lhs'; incUse f';
149 :     SOME[
150 :     (lhs', IL.OP(Op.DiffField, [f'])),
151 :     (lhs, IL.OP(Op.NegField, [lhs']))
152 :     ]
153 :     end
154 : jhr 287 | _ => NONE
155 :     (* end case *))
156 :     | _ => NONE
157 :     (* end case *))
158 : jhr 1116 | doRHS _ = NONE
159 : jhr 287
160 : jhr 320 (* simplify expressions *)
161 : jhr 1116 fun simplify (nd as IL.ND{kind=IL.ASSIGN{stm=(y, rhs), ...}, ...}) =
162 :     if (useCount y = 0)
163 :     then () (* skip unused assignments *)
164 :     else (case doRHS(y, rhs)
165 :     of SOME[] => IL.CFG.deleteNode nd
166 :     | SOME assigns => (
167 :     List.app (fn (y, rhs) => V.setBinding(y, IL.VB_RHS rhs)) assigns;
168 :     IL.CFG.replaceNodeWithCFG (nd, IL.CFG.mkBlock assigns))
169 :     | NONE => ()
170 :     (* end case *))
171 :     | simplify _ = ()
172 : jhr 320
173 :     (* reduce the code by removing variables with use counts of 0 *)
174 : jhr 1116 local
175 :     fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)
176 :     in
177 :     fun reduce (nd as IL.ND{kind, ...}) = (case kind
178 :     of IL.JOIN{phis, ...} => let
179 :     fun doVar (y, xs) = if (useCount y = 0)
180 :     then (
181 :     ST.tick cntUnused;
182 :     List.app decUse xs;
183 :     false)
184 :     else true
185 :     in
186 :     phis := List.filter doVar (!phis)
187 :     end
188 :     | IL.ASSIGN{stm=(y, rhs), ...} =>
189 :     if (useCount y = 0)
190 :     then (
191 :     ST.tick cntUnused;
192 :     case rhs
193 :     of IL.VAR x => decUse x
194 :     | IL.LIT _ => ()
195 :     | IL.OP(_, xs) => List.app decUse xs
196 :     | IL.APPLY(_, xs) => List.app decUse xs
197 :     | IL.CONS(_, xs) => List.app decUse xs
198 :     (* end case *);
199 :     IL.CFG.deleteNode nd)
200 :     else ()
201 :     | _ => ()
202 :     (* end case *))
203 :     end (* local *)
204 : jhr 320
205 : jhr 1116 fun loopToFixPt f = let
206 :     fun loop n = let
207 :     val () = f ()
208 : jhr 338 val n' = Stats.sum{from=firstCounter, to=lastCounter}
209 : jhr 320 in
210 : jhr 1116 if (n = n') then () else loop n'
211 : jhr 320 end
212 :     in
213 : jhr 1116 loop (Stats.sum{from=firstCounter, to=lastCounter})
214 : jhr 320 end
215 :    
216 : jhr 1116 fun optimize (prog as IL.Program{globalInit, initially, strands}) = let
217 :     fun doCFG cfg = (
218 :     loopToFixPt (fn () => IL.CFG.apply simplify cfg);
219 :     loopToFixPt (fn () => ignore(UnusedElim.reduce cfg)))
220 :     fun doMethod (IL.Method{body, ...}) = doCFG body
221 :     fun doStrand (IL.Strand{stateInit, methods, ...}) = (
222 :     doCFG stateInit;
223 :     List.app doMethod methods)
224 :     fun optPass () = (
225 :     doCFG globalInit;
226 :     List.app doStrand strands)
227 : jhr 320 in
228 : jhr 1116 loopToFixPt optPass;
229 :     (* FIXME: after optimization, we should filter out any globals that are now unused *)
230 : jhr 320 IL.Program{
231 :     globalInit = globalInit,
232 : jhr 1116 initially = initially, (* FIXME: we should optimize this code *)
233 : jhr 511 strands = strands
234 : jhr 320 }
235 :     end
236 :    
237 : jhr 287 end

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