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/high-opt.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 338 - (view) (download)
Original Path: trunk/src/compiler/high-il/high-opt.sml

1 : jhr 287 (* high-opt.sml
2 :     *
3 :     * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :     * 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 structure Census = CensusFn (IL)
23 :    
24 :     (********** Counters for statistics **********)
25 :     val cntConstConvolve = ST.newCounter "high-opt:const-convolve"
26 :     val cntConstField = ST.newCounter "high-opt:const-field"
27 :     val cntConstDiff = ST.newCounter "high-opt:const-diff"
28 :     val cntUnused = ST.newCounter "high-opt:unused"
29 : jhr 338 val firstCounter = cntConstConvolve
30 :     val lastCounter = cntUnused
31 : jhr 320
32 : jhr 287 datatype binding
33 :     = Unknown
34 :     | OP of Op.rator * IL.var list
35 : jhr 320 | PHI of IL.var list
36 : jhr 287
37 : jhr 320 fun useCount (IL.V{useCnt, ...}) = !useCnt
38 :    
39 : jhr 287 (* decrement a variable's use count *)
40 :     fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
41 :    
42 :     val {getFn=getBinding, setFn=setBinding, clrFn=clrBinding, ...}
43 :     = V.newProp (fn _ => Unknown)
44 :    
45 :     (* optimize the rhs of an assignment, returning NONE if there is no change *)
46 : jhr 320 fun doRHS rhs = (case rhs
47 : jhr 287 of IL.OP(Op.Convolve, [v, h]) => (case (getBinding v, getBinding h)
48 : jhr 338 of (OP(Op.LoadImage v', []), OP(Op.Kernel h', [])) => (
49 : jhr 320 ST.tick cntConstConvolve;
50 : jhr 287 decUse v; decUse h;
51 : jhr 338 SOME(IL.OP(Op.Field(F.convolve(v', h')), [])))
52 : jhr 287 | _ => raise Fail "non-constant Convolve"
53 :     (* end case *))
54 :     | IL.OP(Op.AddField, [f, g]) => (case (getBinding f, getBinding g)
55 : jhr 338 of (OP(Op.Field f', []), OP(Op.Field g', [])) => (
56 : jhr 320 ST.tick cntConstField;
57 : jhr 287 decUse f; decUse g;
58 : jhr 338 SOME(IL.OP(Op.Field(F.SUM(f', g')), [])))
59 : jhr 287 | _ => NONE
60 :     (* end case *))
61 :     | IL.OP(Op.NegField, [f]) => (case (getBinding f)
62 : jhr 338 of OP(Op.Field f', []) => (
63 : jhr 320 ST.tick cntConstField;
64 : jhr 338 decUse f;
65 :     SOME(IL.OP(Op.Field(F.neg f'), [])))
66 : jhr 287 | _ => NONE
67 :     (* end case *))
68 :     | IL.OP(Op.DiffField, [f]) => (case (getBinding f)
69 : jhr 338 of OP(Op.Field f', []) => (
70 : jhr 320 ST.tick cntConstDiff;
71 : jhr 338 decUse f;
72 :     SOME(IL.OP(Op.Field(F.diff f'), [])))
73 : jhr 287 | _ => raise Fail "non-constant DiffField"
74 :     (* end case *))
75 :     | _ => NONE
76 :     (* end case *))
77 :    
78 : jhr 320 fun setBindings nodes = let
79 :     fun doNode (IL.JOIN{phis, ...}) =
80 : jhr 338 List.app (fn (y, xs) => setBinding(y, PHI xs)) (!phis)
81 : jhr 320 | doNode (IL.BLOCK{body, ...}) =
82 : jhr 338 List.app (fn (y, IL.OP rhs) => setBinding(y, OP rhs) | _ => ()) (!body)
83 : jhr 320 | doNode _ = ()
84 :     in
85 :     List.app doNode nodes
86 :     end
87 :    
88 :     (* simplify expressions *)
89 :     fun simplify nodes = let
90 :     fun doAssign (y, rhs) = (case doRHS rhs
91 : jhr 338 of SOME(rhs' as IL.OP t) => (setBinding(y, OP t); (y, rhs'))
92 : jhr 320 | SOME rhs' => (setBinding(y, Unknown); (y, rhs'))
93 :     | NONE => (y, rhs)
94 :     (* end case *))
95 : jhr 338 fun doNode (IL.ND{kind=IL.BLOCK{body, ...}, ...}) = body := List.map doAssign (!body)
96 : jhr 320 | doNode _ = ()
97 :     in
98 :     List.app doNode nodes
99 :     end
100 :    
101 :     (* reduce the code by removing variables with use counts of 0 *)
102 :     fun reduce nodes = let
103 :     fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)
104 : jhr 338 fun doNode (IL.ND{kind, ...}) = (case kind
105 :     of IL.JOIN{phis, ...} => let
106 :     fun doVar (y, xs) = if (useCount y = 0)
107 :     then (
108 :     ST.tick cntUnused;
109 :     List.app decUse xs;
110 :     false)
111 :     else true
112 : jhr 320 in
113 : jhr 338 phis := List.filter doVar (!phis)
114 :     end
115 :     | IL.BLOCK{body, ...} => let
116 :     (* check for unused lhs variables in reverse order *)
117 :     fun doAssigns [] = []
118 :     | doAssigns ((y, rhs)::r) = let
119 :     val r = doAssigns r
120 :     in
121 :     if (useCount y = 0)
122 :     then (
123 :     ST.tick cntUnused;
124 :     case rhs
125 :     of IL.VAR x => decUse x
126 :     | IL.OP(_, xs) => List.app decUse xs
127 :     | IL.CONS xs => List.app decUse xs
128 :     (* end case *);
129 :     r)
130 :     else (y, rhs)::r
131 :     end
132 :     in
133 :     body := doAssigns (!body)
134 :     end
135 :     | _ => ()
136 :     (* end case *))
137 : jhr 320 in
138 :     List.app doNode (List.rev nodes)
139 :     end
140 :    
141 :     fun clearBindings nodes = let
142 : jhr 338 fun doNode (IL.ND{kind, ...}) = (case kind
143 :     of IL.JOIN{phis, ...} => List.app (fn (y, xs) => clrBinding y) (!phis)
144 :     | IL.BLOCK{body, ...} => List.app (fn (y, _) => clrBinding y) (!body)
145 :     | _ => ()
146 :     (* end case *))
147 : jhr 320 in
148 :     List.app doNode nodes
149 :     end
150 :    
151 : jhr 338 fun loopToFixPt f prog = let
152 : jhr 320 fun loop (n, prog) = let
153 : jhr 338 val () = f prog
154 :     val n' = Stats.sum{from=firstCounter, to=lastCounter}
155 : jhr 320 in
156 : jhr 338 if (n = n') then () else loop(n', prog)
157 : jhr 320 end
158 :     in
159 : jhr 338 loop (Stats.sum{from=firstCounter, to=lastCounter}, prog)
160 : jhr 320 end
161 :    
162 :     fun optimize (prog as IL.Program{globals, globalInit, actors}) = let
163 :     val _ = Census.init prog
164 :     fun doStmt stm = let
165 :     val nodes = IL.sortNodes stm
166 :     in
167 :     loopToFixPt simplify nodes;
168 :     loopToFixPt reduce nodes;
169 :     nodes
170 :     end
171 :     val globInitNodes = doStmt globalInit
172 :     fun doMethod (IL.Method{body, ...}) = let
173 :     val nodes = IL.sortNodes body
174 :     in
175 :     loopToFixPt simplify nodes;
176 :     loopToFixPt reduce nodes;
177 :     clearBindings nodes
178 :     end
179 :     fun doActor (IL.Actor{stateInit, methods, ...}) = let
180 :     val nodes = IL.sortNodes stateInit
181 :     in
182 :     loopToFixPt simplify nodes;
183 :     loopToFixPt reduce nodes;
184 :     List.app doMethod methods;
185 :     clearBindings nodes
186 :     end
187 :     val _ = List.app doActor actors
188 :     (* now we are done with the program body, so we can clean up the global initialization *)
189 :     val _ = clearBindings globInitNodes
190 :     in
191 :     IL.Program{
192 :     globals = globals,
193 :     globalInit = globalInit,
194 :     actors = actors
195 :     }
196 :     end
197 :    
198 : jhr 287 end

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