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

Parent Directory | Revision Log

---

Revision 649 - (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 :			| _ => NONE
43 :			(* end case *))
44 :	jhr	287
45 :			(* optimize the rhs of an assignment, returning NONE if there is no change *)
46 :	jhr	649	fun doRHS (lhs, IL.OP rhs) = (case rhs
47 :			of (Op.Probe(domTy, rngTy), [f, pos]) => (case getRHS f
48 :			of SOME(Op.Field _, _) => NONE (* direct probe does not need rewrite *)
49 :			| SOME(Op.AddField, [f, g]) => raise Fail "Probe(f+g)"
50 :			| SOME(Op.ScaleField, [s, f]) => raise Fail "Probe(s*f)"
51 :			| SOME(Op.NegField, [f]) => raise Fail "Probe(-f)"
52 :			| _ => raise Fail(concat[
53 :			"bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)
54 :			])
55 :			(* end case *))
56 :			| (Op.DiffField, [f]) => (case (getRHS f)
57 :			of SOME(Op.Field dim, [v, h]) => (case getRHS h
58 :			of SOME(Op.Kernel(kernel, k), []) => let
59 :			val h' = IL.Var.copy h
60 :			in
61 :			ST.tick cntDiffField;
62 :			decUse f;
63 :			incUse h'; incUse v;
64 :			SOME[
65 :			(h', IL.OP(Op.Kernel(kernel, k+1), [])),
66 :			(lhs, IL.OP(Op.Field dim, [v, h']))
67 :			]
68 :			end
69 :			| _ => raise Fail(concat[
70 :			"bogus kernel binding ", V.toString h, " = ", IL.vbToString(V.binding h)
71 :			])
72 :	jhr	516	(* end case *))
73 :	jhr	649	| SOME(Op.AddField, [f, g]) => raise Fail "Diff(f+g)"
74 :			| SOME(Op.ScaleField, [s, f]) => raise Fail "Diff(s*f)"
75 :			| SOME(Op.NegField, [f]) => raise Fail "Diff(-f)"
76 :			| _ => NONE
77 :	jhr	287	(* end case *))
78 :			| _ => NONE
79 :			(* end case *))
80 :	jhr	649	| doRHS _ = NONE
81 :	jhr	287
82 :	jhr	320	(* simplify expressions *)
83 :	jhr	649	fun simplify (nd as IL.ND{kind=IL.ASSIGN{stm=(y, rhs), ...}, ...}) =
84 :			if (useCount y = 0)
85 :			then () (* skip unused assignments *)
86 :			else (case doRHS(y, rhs)
87 :			of SOME[] => IL.CFG.deleteNode nd
88 :			| SOME assigns => (
89 :			List.app (fn (y, rhs) => V.setBinding(y, IL.VB_RHS rhs)) assigns;
90 :			IL.CFG.splice (nd, IL.CFG.mkBlock assigns))
91 :			| NONE => ()
92 :			(* end case *))
93 :	jhr	508	| simplify _ = ()
94 :	jhr	320
95 :			(* reduce the code by removing variables with use counts of 0 *)
96 :	jhr	508	local
97 :			fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)
98 :			in
99 :			fun reduce (nd as IL.ND{kind, ...}) = (case kind
100 :			of IL.JOIN{phis, ...} => let
101 :			fun doVar (y, xs) = if (useCount y = 0)
102 :			then (
103 :			ST.tick cntUnused;
104 :			List.app decUse xs;
105 :			false)
106 :			else true
107 :			in
108 :			phis := List.filter doVar (!phis)
109 :			end
110 :			| IL.ASSIGN{stm=(y, rhs), ...} =>
111 :			if (useCount y = 0)
112 :			then (
113 :			ST.tick cntUnused;
114 :			case rhs
115 :			of IL.VAR x => decUse x
116 :			| IL.LIT _ => ()
117 :			| IL.OP(_, xs) => List.app decUse xs
118 :			| IL.CONS xs => List.app decUse xs
119 :			(* end case *);
120 :			IL.CFG.deleteNode nd)
121 :			else ()
122 :			| _ => ()
123 :			(* end case *))
124 :			end (* local *)
125 :	jhr	320
126 :	jhr	508	fun loopToFixPt f cfg = let
127 :			fun loop n = let
128 :			val () = IL.CFG.apply f cfg
129 :	jhr	338	val n' = Stats.sum{from=firstCounter, to=lastCounter}
130 :	jhr	320	in
131 :	jhr	508	if (n = n') then () else loop n'
132 :	jhr	320	end
133 :			in
134 :	jhr	508	loop (Stats.sum{from=firstCounter, to=lastCounter})
135 :	jhr	320	end
136 :
137 :	jhr	613	fun optimize (prog as IL.Program{globals, globalInit, initially, strands}) = let
138 :	jhr	508	fun doCFG cfg = (
139 :			loopToFixPt simplify cfg;
140 :			loopToFixPt reduce cfg)
141 :	jhr	491	val globInitNodes = doCFG globalInit
142 :	jhr	508	fun doMethod (IL.Method{body, ...}) = doCFG body
143 :			fun doStrand (IL.Strand{stateInit, methods, ...}) = (
144 :			doCFG stateInit;
145 :			List.app doMethod methods)
146 :	jhr	499	val _ = List.app doStrand strands
147 :	jhr	320	in
148 :			IL.Program{
149 :			globals = globals,
150 :			globalInit = globalInit,
151 :	jhr	613	initially = initially, (* FIXME: we should optimize this code *)
152 :	jhr	499	strands = strands
153 :	jhr	320	}
154 :			end
155 :
156 :	jhr	287	end

---

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