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

Parent Directory | Revision Log

---

Revision 338 - (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 :	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