Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Diff of /trunk/src/compiler/high-il/high-opt.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 287, Fri Aug 13 21:40:04 2010 UTC revision 338, Mon Sep 13 14:49:12 2010 UTC
# Line 14  Line 14 
14    end = struct    end = struct
15    
16      structure IL = HighIL      structure IL = HighIL
17      structure Op = IL.Op      structure Op = HighOps
18      structure V = IL.Var      structure V = IL.Var
19        structure ST = Stats
20        structure F = FieldDef
21    
22        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        val firstCounter            = cntConstConvolve
30        val lastCounter             = cntUnused
31    
32      datatype binding      datatype binding
33        = Unknown        = Unknown
34        | OP of Op.rator * IL.var list        | OP of Op.rator * IL.var list
35          | PHI of IL.var list
36    
37        fun useCount (IL.V{useCnt, ...}) = !useCnt
38    
39    (* decrement a variable's use count *)    (* decrement a variable's use count *)
40      fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)      fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
# Line 28  Line 43 
43            = V.newProp (fn _ => Unknown)            = V.newProp (fn _ => Unknown)
44    
45    (* optimize the rhs of an assignment, returning NONE if there is no change *)    (* optimize the rhs of an assignment, returning NONE if there is no change *)
46      fun doAssignment rhs = (case rhs      fun doRHS rhs = (case rhs
47             of IL.OP(Op.Convolve, [v, h]) => (case (getBinding v, getBinding h)             of IL.OP(Op.Convolve, [v, h]) => (case (getBinding v, getBinding h)
48                   of ((Op.LoadImage v', []), (Op.Kernel h', [])) => (                   of (OP(Op.LoadImage v', []), OP(Op.Kernel h', [])) => (
49                          ST.tick cntConstConvolve;
50                        decUse v; decUse h;                        decUse v; decUse h;
51                        SOME(IL.Op(Op.Field(F.convolve(v', h')), [])))                        SOME(IL.OP(Op.Field(F.convolve(v', h')), [])))
52                    | _ => raise Fail "non-constant Convolve"                    | _ => raise Fail "non-constant Convolve"
53                  (* end case *))                  (* end case *))
54              | IL.OP(Op.AddField, [f, g]) => (case (getBinding f, getBinding g)              | IL.OP(Op.AddField, [f, g]) => (case (getBinding f, getBinding g)
55                   of ((Op.Field f', []), (Op.Field g', [])) => (                   of (OP(Op.Field f', []), OP(Op.Field g', [])) => (
56                          ST.tick cntConstField;
57                        decUse f; decUse g;                        decUse f; decUse g;
58                        SOME(IL.Op(Op.Field(F.SUM(f, g)), [])))                        SOME(IL.OP(Op.Field(F.SUM(f', g')), [])))
59                    | _ => NONE                    | _ => NONE
60                  (* end case *))                  (* end case *))
61              | IL.OP(Op.NegField, [f]) => (case (getBinding f)              | IL.OP(Op.NegField, [f]) => (case (getBinding f)
62                   of (Op.Field f', []) => (                   of OP(Op.Field f', []) => (
63                        decUse f';                        ST.tick cntConstField;
64                        SOME(IL.Op(Op.Field(F.neg f'), [])))                        decUse f;
65                          SOME(IL.OP(Op.Field(F.neg f'), [])))
66                    | _ => NONE                    | _ => NONE
67                  (* end case *))                  (* end case *))
68              | IL.OP(Op.DiffField, [f]) => (case (getBinding f)              | IL.OP(Op.DiffField, [f]) => (case (getBinding f)
69                   of (Op.Field f', []) => (                   of OP(Op.Field f', []) => (
70                        decUse f';                        ST.tick cntConstDiff;
71                        SOME(IL.Op(Op.Field(F.diff f'), [])))                        decUse f;
72                          SOME(IL.OP(Op.Field(F.diff f'), [])))
73                    | _ => raise Fail "non-constant DiffField"                    | _ => raise Fail "non-constant DiffField"
74                  (* end case *))                  (* end case *))
75              | _ => NONE              | _ => NONE
76            (* end case *))            (* end case *))
77    
78        fun setBindings nodes = let
79              fun doNode (IL.JOIN{phis, ...}) =
80                    List.app (fn (y, xs) => setBinding(y, PHI xs)) (!phis)
81                | doNode (IL.BLOCK{body, ...}) =
82                    List.app (fn (y, IL.OP rhs) => setBinding(y, OP rhs) | _ => ()) (!body)
83                | 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                     of SOME(rhs' as IL.OP t) => (setBinding(y, OP t); (y, rhs'))
92                      | SOME rhs' => (setBinding(y, Unknown); (y, rhs'))
93                      | NONE => (y, rhs)
94                    (* end case *))
95              fun doNode (IL.ND{kind=IL.BLOCK{body, ...}, ...}) = body := List.map doAssign (!body)
96                | 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              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                          in
113                            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              in
138                List.app doNode (List.rev nodes)
139              end
140    
141        fun clearBindings nodes = let
142              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              in
148                List.app doNode nodes
149              end
150    
151        fun loopToFixPt f prog = let
152              fun loop (n, prog) = let
153                    val () = f prog
154                    val n' = Stats.sum{from=firstCounter, to=lastCounter}
155                    in
156                      if (n = n') then () else loop(n', prog)
157                    end
158              in
159                loop (Stats.sum{from=firstCounter, to=lastCounter}, prog)
160              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    end    end

Legend:
Removed from v.287  
changed lines
  Added in v.338

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