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

SCM Repository

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

Annotation of /branches/pure-cfg/src/compiler/high-il/high-opt.sml

Parent Directory Parent Directory | Revision Log Revision Log


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

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