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

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