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 1232 - (view) (download)
Original Path: trunk/src/compiler/high-il/normalize.sml

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

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