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 499 - (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 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 :     fun useCount (IL.V{useCnt, ...}) = !useCnt
33 :    
34 : jhr 287 (* decrement a variable's use count *)
35 :     fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
36 :    
37 : jhr 372 fun getRHS x = (case V.binding x
38 :     of IL.VB_RHS(IL.OP arg) => SOME arg
39 :     | _ => NONE
40 :     (* end case *))
41 : jhr 287
42 :     (* optimize the rhs of an assignment, returning NONE if there is no change *)
43 : jhr 320 fun doRHS rhs = (case rhs
44 : jhr 372 of IL.OP(Op.Convolve, [v, h]) => (case (getRHS v, getRHS h)
45 :     of (SOME(Op.LoadImage v', []), SOME(Op.Kernel h', [])) => (
46 : jhr 320 ST.tick cntConstConvolve;
47 : jhr 287 decUse v; decUse h;
48 : jhr 338 SOME(IL.OP(Op.Field(F.convolve(v', h')), [])))
49 : jhr 287 | _ => raise Fail "non-constant Convolve"
50 :     (* end case *))
51 : jhr 372 | IL.OP(Op.AddField, [f, g]) => (case (getRHS f, getRHS g)
52 :     of (SOME(Op.Field f', []), SOME(Op.Field g', [])) => (
53 : jhr 320 ST.tick cntConstField;
54 : jhr 287 decUse f; decUse g;
55 : jhr 338 SOME(IL.OP(Op.Field(F.SUM(f', g')), [])))
56 : jhr 287 | _ => NONE
57 :     (* end case *))
58 : jhr 372 | IL.OP(Op.NegField, [f]) => (case (getRHS f)
59 :     of SOME(Op.Field f', []) => (
60 : jhr 320 ST.tick cntConstField;
61 : jhr 338 decUse f;
62 :     SOME(IL.OP(Op.Field(F.neg f'), [])))
63 : jhr 287 | _ => NONE
64 :     (* end case *))
65 : jhr 372 | IL.OP(Op.DiffField, [f]) => (case (getRHS f)
66 :     of SOME(Op.Field f', []) => (
67 : jhr 320 ST.tick cntConstDiff;
68 : jhr 338 decUse f;
69 :     SOME(IL.OP(Op.Field(F.diff f'), [])))
70 : jhr 287 | _ => raise Fail "non-constant DiffField"
71 :     (* end case *))
72 :     | _ => NONE
73 :     (* end case *))
74 :    
75 : jhr 320 (* simplify expressions *)
76 :     fun simplify nodes = let
77 :     fun doAssign (y, rhs) = (case doRHS rhs
78 : jhr 372 of SOME rhs' => (V.setBinding(y, IL.VB_RHS rhs'); (y, rhs'))
79 : jhr 320 | NONE => (y, rhs)
80 :     (* end case *))
81 : jhr 491 fun doNode (nd as IL.ND{kind=IL.ASSIGN{stm=(y, rhs), ...}, ...}) = (case doRHS rhs
82 :     of SOME rhs' => (
83 :     V.setBinding(y, IL.VB_RHS rhs');
84 :     IL.CFG.replaceNode (nd, IL.Node.mkASSIGN(y, rhs')))
85 :     | NONE => ()
86 :     (* end case *))
87 : jhr 320 | doNode _ = ()
88 :     in
89 :     List.app doNode nodes
90 :     end
91 :    
92 :     (* reduce the code by removing variables with use counts of 0 *)
93 :     fun reduce nodes = let
94 :     fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)
95 : jhr 491 fun doNode (nd as IL.ND{kind, ...}) = (case kind
96 : jhr 338 of IL.JOIN{phis, ...} => let
97 :     fun doVar (y, xs) = if (useCount y = 0)
98 :     then (
99 :     ST.tick cntUnused;
100 :     List.app decUse xs;
101 :     false)
102 :     else true
103 : jhr 320 in
104 : jhr 338 phis := List.filter doVar (!phis)
105 :     end
106 : jhr 491 | IL.ASSIGN{stm=(y, rhs), ...} =>
107 :     if (useCount y = 0)
108 :     then (
109 :     ST.tick cntUnused;
110 :     case rhs
111 :     of IL.VAR x => decUse x
112 :     | IL.LIT _ => ()
113 :     | IL.OP(_, xs) => List.app decUse xs
114 :     | IL.CONS xs => List.app decUse xs
115 :     (* end case *);
116 :     IL.CFG.deleteNode nd)
117 :     else ()
118 : jhr 338 | _ => ()
119 :     (* end case *))
120 : jhr 320 in
121 :     List.app doNode (List.rev nodes)
122 :     end
123 :    
124 : jhr 338 fun loopToFixPt f prog = let
125 : jhr 320 fun loop (n, prog) = let
126 : jhr 338 val () = f prog
127 :     val n' = Stats.sum{from=firstCounter, to=lastCounter}
128 : jhr 320 in
129 : jhr 338 if (n = n') then () else loop(n', prog)
130 : jhr 320 end
131 :     in
132 : jhr 338 loop (Stats.sum{from=firstCounter, to=lastCounter}, prog)
133 : jhr 320 end
134 :    
135 : jhr 499 fun optimize (prog as IL.Program{globals, globalInit, strands}) = let
136 : jhr 320 val _ = Census.init prog
137 : jhr 491 fun doCFG cfg = let
138 :     val nodes = IL.CFG.sort cfg
139 : jhr 320 in
140 :     loopToFixPt simplify nodes;
141 :     loopToFixPt reduce nodes;
142 :     nodes
143 :     end
144 : jhr 491 val globInitNodes = doCFG globalInit
145 : jhr 320 fun doMethod (IL.Method{body, ...}) = let
146 : jhr 491 val nodes = IL.CFG.sort body
147 : jhr 320 in
148 :     loopToFixPt simplify nodes;
149 : jhr 372 loopToFixPt reduce nodes
150 : jhr 320 end
151 : jhr 499 fun doStrand (IL.Strand{stateInit, methods, ...}) = let
152 : jhr 491 val nodes = IL.CFG.sort stateInit
153 : jhr 320 in
154 :     loopToFixPt simplify nodes;
155 :     loopToFixPt reduce nodes;
156 : jhr 372 List.app doMethod methods
157 : jhr 320 end
158 : jhr 499 val _ = List.app doStrand strands
159 : jhr 320 in
160 :     IL.Program{
161 :     globals = globals,
162 :     globalInit = globalInit,
163 : jhr 499 strands = strands
164 : jhr 320 }
165 :     end
166 :    
167 : jhr 287 end

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