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 320, Wed Aug 18 04:13:28 2010 UTC
# Line 16  Line 16 
16      structure IL = HighIL      structure IL = HighIL
17      structure Op = IL.Op      structure Op = IL.Op
18      structure V = IL.Var      structure V = IL.Var
19        structure ST = Stats
20    
21        structure Census = CensusFn (IL)
22    
23      (********** Counters for statistics **********)
24        val cntConstConvolve        = ST.newCounter "high-opt:const-convolve"
25        val cntConstField           = ST.newCounter "high-opt:const-field"
26        val cntConstDiff            = ST.newCounter "high-opt:const-diff"
27        val cntUnused               = ST.newCounter "high-opt:unused"
28        val firstCounter            = cntUnusedStmt
29        val lastCounter             = cntUnusedCFun
30    
31      datatype binding      datatype binding
32        = Unknown        = Unknown
33        | OP of Op.rator * IL.var list        | OP of Op.rator * IL.var list
34          | PHI of IL.var list
35    
36        fun useCount (IL.V{useCnt, ...}) = !useCnt
37    
38    (* decrement a variable's use count *)    (* decrement a variable's use count *)
39      fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)      fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
# Line 28  Line 42 
42            = V.newProp (fn _ => Unknown)            = V.newProp (fn _ => Unknown)
43    
44    (* 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 *)
45      fun doAssignment rhs = (case rhs      fun doRHS rhs = (case rhs
46             of IL.OP(Op.Convolve, [v, h]) => (case (getBinding v, getBinding h)             of IL.OP(Op.Convolve, [v, h]) => (case (getBinding v, getBinding h)
47                   of ((Op.LoadImage v', []), (Op.Kernel h', [])) => (                   of ((Op.LoadImage v', []), (Op.Kernel h', [])) => (
48                          ST.tick cntConstConvolve;
49                        decUse v; decUse h;                        decUse v; decUse h;
50                        SOME(IL.Op(Op.Field(F.convolve(v', h')), [])))                        SOME(IL.Op(Op.Field(F.convolve(v', h')), [])))
51                    | _ => raise Fail "non-constant Convolve"                    | _ => raise Fail "non-constant Convolve"
52                  (* end case *))                  (* end case *))
53              | IL.OP(Op.AddField, [f, g]) => (case (getBinding f, getBinding g)              | IL.OP(Op.AddField, [f, g]) => (case (getBinding f, getBinding g)
54                   of ((Op.Field f', []), (Op.Field g', [])) => (                   of ((Op.Field f', []), (Op.Field g', [])) => (
55                          ST.tick cntConstField;
56                        decUse f; decUse g;                        decUse f; decUse g;
57                        SOME(IL.Op(Op.Field(F.SUM(f, g)), [])))                        SOME(IL.Op(Op.Field(F.SUM(f, g)), [])))
58                    | _ => NONE                    | _ => NONE
59                  (* end case *))                  (* end case *))
60              | IL.OP(Op.NegField, [f]) => (case (getBinding f)              | IL.OP(Op.NegField, [f]) => (case (getBinding f)
61                   of (Op.Field f', []) => (                   of (Op.Field f', []) => (
62                          ST.tick cntConstField;
63                        decUse f';                        decUse f';
64                        SOME(IL.Op(Op.Field(F.neg f'), [])))                        SOME(IL.Op(Op.Field(F.neg f'), [])))
65                    | _ => NONE                    | _ => NONE
66                  (* end case *))                  (* end case *))
67              | IL.OP(Op.DiffField, [f]) => (case (getBinding f)              | IL.OP(Op.DiffField, [f]) => (case (getBinding f)
68                   of (Op.Field f', []) => (                   of (Op.Field f', []) => (
69                          ST.tick cntConstDiff;
70                        decUse f';                        decUse f';
71                        SOME(IL.Op(Op.Field(F.diff f'), [])))                        SOME(IL.Op(Op.Field(F.diff f'), [])))
72                    | _ => raise Fail "non-constant DiffField"                    | _ => raise Fail "non-constant DiffField"
# Line 56  Line 74 
74              | _ => NONE              | _ => NONE
75            (* end case *))            (* end case *))
76    
77        fun setBindings nodes = let
78              fun doNode (IL.JOIN{phis, ...}) =
79                    List.app (fn (y, _) => setBinding(y, PHI xs)) (!phis)
80                | doNode (IL.BLOCK{body, ...}) =
81                    List.app (fn (y, IL.OP rhs) => setBinding(y, RHS rhs) | _ => ()) (!body)
82                | doNode _ = ()
83              in
84                List.app doNode nodes
85              end
86    
87      (* simplify expressions *)
88        fun simplify nodes = let
89              fun doAssign (y, rhs) = (case doRHS rhs
90                     of SOME(rhs' as IL.OP t) => (setBinding(y, RHS t); (y, rhs'))
91                      | SOME rhs' => (setBinding(y, Unknown); (y, rhs'))
92                      | NONE => (y, rhs)
93                    (* end case *))
94              fun doNode (IL.BLOCK{body, ...}) = body := List.map doAssign (!body)
95                | doNode _ = ()
96              in
97                List.app doNode nodes
98              end
99    
100      (* reduce the code by removing variables with use counts of 0 *)
101        fun reduce nodes = let
102              fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)
103              fun doNode (IL.JOIN{phis, ...}) = let
104                    fun doVar (y, xs) = if (useCount y = 0)
105                          then (
106                            ST.tick cntUnused;
107                            List.app decUse xs;
108                            false)
109                          else true
110                    in
111                      phis := List.filter doVar (!phis)
112                    end
113                | doNode (IL.BLOCK{body, ...}) = let
114                  (* check for unused lhs variables in reverse order *)
115                    fun doAssigns [] = []
116                      | doAssigns ((y, rhs)::r) = let
117                          val r = doAssigns r
118                          in
119                            if (useCount y = 0)
120                              then (
121                                ST.tick cntUnused;
122                                case rhs
123                                 of IL VAR x => decUse x
124                                  | IL.OP(_, xs) => List.app decUse xs
125                                  | IL.CONS xs => List.app decUse xs
126                                (* end case *);
127                                r)
128                              else (y. rhs)::r
129                    in
130                      body := doAssigns (!body)
131                    end
132                | doNode _ = ()
133              in
134                List.app doNode (List.rev nodes)
135              end
136    
137        fun clearBindings nodes = let
138              fun doNode (IL.JOIN{phis, ...}) =
139                    List.app (fn (y, xs) => clrBinding y) (!phis)
140                | doNode (IL.BLOCK{body, ...}) =
141                    List.app (fn (y, _) => clrBinding y) (!body)
142                | doNode _ = ()
143              in
144                List.app doNode nodes
145              end
146    
147        fun loopToFixPt f = let
148              fun loop (n, prog) = let
149                    val prog = f prog
150                    val n' = Stats.sum{from=firstCounter, last=lastCounter}
151                    in
152                      if (n = n') then prog else loop(n', prog)
153                    end
154              in
155                loop (Stats.sum{from=firstCounter, last=lastCounter}, prog)
156              end
157    
158        fun optimize (prog as IL.Program{globals, globalInit, actors}) = let
159              val _ = Census.init prog
160              fun doStmt stm = let
161                    val nodes = IL.sortNodes stm
162                    in
163                      loopToFixPt simplify nodes;
164                      loopToFixPt reduce nodes;
165                      nodes
166                    end
167              val globInitNodes = doStmt globalInit
168              fun doMethod (IL.Method{body, ...}) = let
169                    val nodes = IL.sortNodes body
170                    in
171                      loopToFixPt simplify nodes;
172                      loopToFixPt reduce nodes;
173                      clearBindings nodes
174                    end
175              fun doActor (IL.Actor{stateInit, methods, ...}) = let
176                    val nodes = IL.sortNodes stateInit
177                    in
178                      loopToFixPt simplify nodes;
179                      loopToFixPt reduce nodes;
180                      List.app doMethod methods;
181                      clearBindings nodes
182                    end
183              val _ = List.app doActor actors
184            (* now we are done with the program body, so we can clean up the global initialization *)
185              val _ = clearBindings globInitNodes
186              in
187                IL.Program{
188                    globals = globals,
189                    globalInit = globalInit,
190                    actors = actors
191                  }
192              end
193    
194    end    end

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

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