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 320 - (view) (download)

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

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