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

SCM Repository

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

Diff of /branches/vis12/src/compiler/high-il/high-opt.sml

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

revision 511, Tue Feb 8 17:01:43 2011 UTC revision 1116, Thu May 5 04:49:02 2011 UTC
# Line 20  Line 20 
20      structure F = FieldDef      structure F = FieldDef
21    
22    (********** Counters for statistics **********)    (********** Counters for statistics **********)
23      val cntConstConvolve        = ST.newCounter "high-opt:const-convolve"      val cntProbeAdd             = ST.newCounter "high-opt:probe-add"
24      val cntConstField           = ST.newCounter "high-opt:const-field"      val cntProbeSub             = ST.newCounter "high-opt:probe-sub"
25      val cntConstDiff            = ST.newCounter "high-opt:const-diff"      val cntProbeScale           = ST.newCounter "high-opt:probe-scale"
26        val cntProbeNeg             = ST.newCounter "high-opt:probe-neg"
27        val cntDiffField            = ST.newCounter "high-opt:diff-field"
28        val cntDiffAdd              = ST.newCounter "high-opt:diff-add"
29        val cntDiffScale            = ST.newCounter "high-opt:diff-scale"
30        val cntDiffNeg              = ST.newCounter "high-opt:diff-neg"
31      val cntUnused               = ST.newCounter "high-opt:unused"      val cntUnused               = ST.newCounter "high-opt:unused"
32      val firstCounter            = cntConstConvolve      val firstCounter            = cntProbeAdd
33      val lastCounter             = cntUnused      val lastCounter             = cntUnused
34    
35        structure UnusedElim = UnusedElimFn (
36            structure IL = IL
37            val cntUnused = cntUnused)
38    
39      fun useCount (IL.V{useCnt, ...}) = !useCnt      fun useCount (IL.V{useCnt, ...}) = !useCnt
40    
41    (* decrement a variable's use count *)    (* adjust a variable's use count *)
42        fun incUse (IL.V{useCnt, ...}) = (useCnt := !useCnt + 1)
43      fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)      fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
44    
45      fun getRHS x = (case V.binding x      fun getRHS x = (case V.binding x
46             of IL.VB_RHS(IL.OP arg) => SOME arg             of IL.VB_RHS(IL.OP arg) => SOME arg
47                | IL.VB_RHS(IL.VAR x') => getRHS x'
48              | _ => NONE              | _ => NONE
49            (* end case *))            (* end case *))
50    
51    (* 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 *)
52      fun doRHS rhs = (case rhs      fun doRHS (lhs, IL.OP rhs) = (case rhs
53             of IL.OP(Op.Convolve, [v, h]) => (case (getRHS v, getRHS h)             of (Op.Probe(domTy, rngTy), [f, pos]) => (case getRHS f
54                   of (SOME(Op.LoadImage v', []), SOME(Op.Kernel h', [])) => (                   of SOME(Op.Field _, _) => NONE (* direct probe does not need rewrite *)
55                        ST.tick cntConstConvolve;                    | SOME(Op.AddField, [f', g']) => let
56                        decUse v; decUse h;                      (* rewrite to (f@pos) + (g@pos) *)
57                        SOME(IL.OP(Op.Field(F.convolve(v', h')), [])))                        val lhs1 = IL.Var.copy lhs
58                    | _ => raise Fail "non-constant Convolve"                        val lhs2 = IL.Var.copy lhs
59                  (* end case *))                        in
60              | IL.OP(Op.AddField, [f, g]) => (case (getRHS f, getRHS g)                          ST.tick cntProbeAdd;
                  of (SOME(Op.Field f', []), SOME(Op.Field g', [])) => (  
                       ST.tick cntConstField;  
                       decUse f; decUse g;  
                       SOME(IL.OP(Op.Field(F.SUM(f', g')), [])))  
                   | _ => NONE  
                 (* end case *))  
             | IL.OP(Op.NegField, [f]) => (case (getRHS f)  
                  of SOME(Op.Field f', []) => (  
                       ST.tick cntConstField;  
61                        decUse f;                        decUse f;
62                        SOME(IL.OP(Op.Field(F.neg f'), [])))                          incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;
63                    | _ => NONE                          SOME[
64                  (* end case *))                              (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
65              | IL.OP(Op.DiffField, [f]) => (case (getRHS f)                              (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),
66                   of SOME(Op.Field f', []) => (                              (lhs, IL.OP(Op.Add rngTy, [lhs1, lhs2]))
67                        ST.tick cntConstDiff;                            ]
68                          end
69                      | SOME(Op.SubField, [f', g']) => let
70                        (* rewrite to (f@pos) - (g@pos) *)
71                          val lhs1 = IL.Var.copy lhs
72                          val lhs2 = IL.Var.copy lhs
73                          in
74                            ST.tick cntProbeSub;
75                            decUse f;
76                            incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;
77                            SOME[
78                                (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
79                                (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),
80                                (lhs, IL.OP(Op.Sub rngTy, [lhs1, lhs2]))
81                              ]
82                          end
83                      | SOME(Op.ScaleField, [s, f']) => let
84                        (* rewrite to s*(f'@pos) *)
85                          val lhs' = IL.Var.copy lhs
86                          in
87                            ST.tick cntProbeScale;
88                        decUse f;                        decUse f;
89                        SOME(IL.OP(Op.Field(F.diff f'), [])))                          incUse lhs'; incUse f'; incUse s;
90                    | _ => raise Fail "non-constant DiffField"                          SOME[
91                                (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
92                                (lhs, IL.OP(Op.Scale rngTy, [s, lhs']))
93                              ]
94                          end
95                      | SOME(Op.NegField, [f']) => let
96                        (* rewrite to -(f'@pos) *)
97                          val lhs' = IL.Var.copy lhs
98                          in
99                            ST.tick cntProbeNeg;
100                            decUse f;
101                            incUse lhs'; incUse f';
102                            SOME[
103                                (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),
104                                (lhs, IL.OP(Op.Neg rngTy, [lhs']))
105                              ]
106                          end
107                      | _ => raise Fail(concat[
108                            "bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)
109                          ])
110                    (* end case *))
111                | (Op.DiffField, [f]) => (case (getRHS f)
112                     of SOME(Op.Field dim, [v, h]) => (case getRHS h
113                           of SOME(Op.Kernel(kernel, k), []) => let
114                                val h' = IL.Var.copy h
115                                in
116                                  ST.tick cntDiffField;
117                                  decUse f;
118                                  incUse h'; incUse v;
119                                  SOME[
120                                      (h', IL.OP(Op.Kernel(kernel, k+1), [])),
121                                      (lhs, IL.OP(Op.Field dim, [v, h']))
122                                    ]
123                                end
124                            | _ => raise Fail(concat[
125                                  "bogus kernel binding ", V.toString h, " = ", IL.vbToString(V.binding h)
126                                ])
127                          (* end case *))
128                      | SOME(Op.AddField, [f, g]) => raise Fail "Diff(f+g)"
129                      | SOME(Op.SubField, [f, g]) => raise Fail "Diff(f-g)"
130                      | SOME(Op.ScaleField, [s, f']) => let
131                        (* rewrite to s*(D f) *)
132                          val lhs' = IL.Var.copy lhs
133                          in
134                            ST.tick cntDiffScale;
135                            decUse f;
136                            incUse lhs'; incUse f'; incUse s;
137                            SOME[
138                                (lhs', IL.OP(Op.DiffField, [f'])),
139                                (lhs, IL.OP(Op.ScaleField, [s, lhs']))
140                              ]
141                          end
142                      | SOME(Op.NegField, [f']) => let
143                        (* rewrite to -(D f') *)
144                          val lhs' = IL.Var.copy lhs
145                          in
146                            ST.tick cntDiffNeg;
147                            decUse f;
148                            incUse lhs'; incUse f';
149                            SOME[
150                                (lhs', IL.OP(Op.DiffField, [f'])),
151                                (lhs, IL.OP(Op.NegField, [lhs']))
152                              ]
153                          end
154                      | _ => NONE
155                  (* end case *))                  (* end case *))
156              | _ => NONE              | _ => NONE
157            (* end case *))            (* end case *))
158          | doRHS _ = NONE
159    
160    (* simplify expressions *)    (* simplify expressions *)
161      fun simplify nodes = let      fun simplify (nd as IL.ND{kind=IL.ASSIGN{stm=(y, rhs), ...}, ...}) =
162            fun doAssign (y, rhs) = (case doRHS rhs            if (useCount y = 0)
163                   of SOME rhs' => (V.setBinding(y, IL.VB_RHS rhs'); (y, rhs'))              then () (* skip unused assignments *)
164                    | NONE => (y, rhs)              else (case doRHS(y, rhs)
165                  (* end case *))                 of SOME[] => IL.CFG.deleteNode nd
166            fun doNode (IL.ND{kind=IL.BLOCK{body, ...}, ...}) =                  | SOME assigns => (
167                  body := List.map doAssign (!body)                      List.app (fn (y, rhs) => V.setBinding(y, IL.VB_RHS rhs)) assigns;
168              | doNode _ = ()                      IL.CFG.replaceNodeWithCFG (nd, IL.CFG.mkBlock assigns))
169            in                  | NONE => ()
170              List.app doNode nodes                (* end case *))
171            end        | simplify _ = ()
172    
173    (* reduce the code by removing variables with use counts of 0 *)    (* reduce the code by removing variables with use counts of 0 *)
174      fun reduce nodes = let      local
175            fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)            fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)
176            fun doNode (IL.ND{kind, ...}) = (case kind      in
177        fun reduce (nd as IL.ND{kind, ...}) = (case kind
178                   of IL.JOIN{phis, ...} => let                   of IL.JOIN{phis, ...} => let
179                        fun doVar (y, xs) = if (useCount y = 0)                        fun doVar (y, xs) = if (useCount y = 0)
180                              then (                              then (
# Line 97  Line 185 
185                        in                        in
186                          phis := List.filter doVar (!phis)                          phis := List.filter doVar (!phis)
187                        end                        end
188                    | IL.BLOCK{body, ...} => let              | IL.ASSIGN{stm=(y, rhs), ...} =>
                     (* check for unused lhs variables in reverse order *)  
                       fun doAssigns [] = []  
                         | doAssigns ((y, rhs)::r) = let  
                             val r = doAssigns r  
                             in  
189                                if (useCount y = 0)                                if (useCount y = 0)
190                                  then (                                  then (
191                                    ST.tick cntUnused;                                    ST.tick cntUnused;
# Line 110  Line 193 
193                                     of IL.VAR x => decUse x                                     of IL.VAR x => decUse x
194                                      | IL.LIT _ => ()                                      | IL.LIT _ => ()
195                                      | IL.OP(_, xs) => List.app decUse xs                                      | IL.OP(_, xs) => List.app decUse xs
196                                      | IL.CONS xs => List.app decUse xs                        | IL.APPLY(_, xs) => List.app decUse xs
197                          | IL.CONS(_, xs) => List.app decUse xs
198                                    (* end case *);                                    (* end case *);
199                                    r)                      IL.CFG.deleteNode nd)
200                                  else (y, rhs)::r                    else ()
                             end  
                       in  
                         body := doAssigns (!body)  
                       end  
201                    | _ => ()                    | _ => ()
202                  (* end case *))                  (* end case *))
203            in      end (* local *)
             List.app doNode (List.rev nodes)  
           end  
204    
205      fun loopToFixPt f prog = let      fun loopToFixPt f = let
206            fun loop (n, prog) = let            fun loop n = let
207                  val () = f prog                  val () = f ()
208                  val n' = Stats.sum{from=firstCounter, to=lastCounter}                  val n' = Stats.sum{from=firstCounter, to=lastCounter}
209                  in                  in
210                    if (n = n') then () else loop(n', prog)                    if (n = n') then () else loop n'
211                  end                  end
212            in            in
213              loop (Stats.sum{from=firstCounter, to=lastCounter}, prog)              loop (Stats.sum{from=firstCounter, to=lastCounter})
214            end            end
215    
216      fun optimize (prog as IL.Program{globals, globalInit, strands}) = let      fun optimize (prog as IL.Program{globalInit, initially, strands}) = let
217            fun doStmt stm = let            fun doCFG cfg = (
218                  val nodes = IL.sortNodes stm                  loopToFixPt (fn () => IL.CFG.apply simplify cfg);
219                  in                  loopToFixPt (fn () => ignore(UnusedElim.reduce cfg)))
220                    loopToFixPt simplify nodes;            fun doMethod (IL.Method{body, ...}) = doCFG body
221                    loopToFixPt reduce nodes;            fun doStrand (IL.Strand{stateInit, methods, ...}) = (
222                    nodes                  doCFG stateInit;
223                  end                  List.app doMethod methods)
224            val globInitNodes = doStmt globalInit            fun optPass () = (
225            fun doMethod (IL.Method{body, ...}) = let                  doCFG globalInit;
226                  val nodes = IL.sortNodes body                  List.app doStrand strands)
                 in  
                   loopToFixPt simplify nodes;  
                   loopToFixPt reduce nodes  
                 end  
           fun doStrand (IL.Strand{stateInit, methods, ...}) = let  
                 val nodes = IL.sortNodes stateInit  
                 in  
                   loopToFixPt simplify nodes;  
                   loopToFixPt reduce nodes;  
                   List.app doMethod methods  
                 end  
           val _ = List.app doStrand strands  
227            in            in
228                loopToFixPt optPass;
229    (* FIXME: after optimization, we should filter out any globals that are now unused *)
230              IL.Program{              IL.Program{
                 globals = globals,  
231                  globalInit = globalInit,                  globalInit = globalInit,
232                    initially = initially,  (* FIXME: we should optimize this code *)
233                  strands = strands                  strands = strands
234                }                }
235            end            end

Legend:
Removed from v.511  
changed lines
  Added in v.1116

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