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 1231, Mon May 16 13:49:17 2011 UTC revision 1232, Mon May 16 23:37:52 2011 UTC
# Line 9  Line 9 
9    
10  structure HighOptimizer : sig  structure HighOptimizer : sig
11    
12        val controls : (string * bool ref * string) list
13    
14      val optimize : HighIL.program -> HighIL.program      val optimize : HighIL.program -> HighIL.program
15    
16    end = struct    end = struct
17    
18      structure IL = HighIL    (* Value numbering for HighIL *)
19      structure Op = HighOps      structure VN = ValueNumberingFn (DomTreeFn (HighIL))
20      structure V = IL.Var  
21      structure ST = Stats      val vnFlag = ref true               (* controls value numbering *)
22      structure F = FieldDef      val debugFlag = ref true            (* controls printing *)
23        val checkFlag = ref true            (* controls IL checking *)
24    (********** Counters for statistics **********)  
25      val cntProbeAdd             = ST.newCounter "high-opt:probe-add"      val controls = [
26      val cntProbeSub             = ST.newCounter "high-opt:probe-sub"              ("high-vn", vnFlag, "enable value-numbering for HighIL"),
27      val cntProbeScale           = ST.newCounter "high-opt:probe-scale"              ("high-debug", debugFlag, "enable printing HighIL to log file [debug]"),
28      val cntProbeNeg             = ST.newCounter "high-opt:probe-neg"              ("high-check", checkFlag, "enable consistency checking for HighIL [debug]")
     val cntDiffField            = ST.newCounter "high-opt:diff-field"  
     val cntDiffAdd              = ST.newCounter "high-opt:diff-add"  
     val cntDiffScale            = ST.newCounter "high-opt:diff-scale"  
     val cntDiffNeg              = ST.newCounter "high-opt:diff-neg"  
     val cntUnused               = ST.newCounter "high-opt:unused"  
     val firstCounter            = cntProbeAdd  
     val lastCounter             = cntUnused  
   
     structure UnusedElim = UnusedElimFn (  
         structure IL = IL  
         val cntUnused = cntUnused)  
   
     fun useCount (IL.V{useCnt, ...}) = !useCnt  
   
   (* adjust a variable's use count *)  
     fun incUse (IL.V{useCnt, ...}) = (useCnt := !useCnt + 1)  
     fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)  
   
     fun getRHS x = (case V.binding x  
            of IL.VB_RHS(IL.OP arg) => SOME arg  
             | IL.VB_RHS(IL.VAR x') => getRHS x'  
             | _ => NONE  
           (* end case *))  
   
   (* optimize the rhs of an assignment, returning NONE if there is no change *)  
     fun doRHS (lhs, IL.OP rhs) = (case rhs  
            of (Op.Probe(domTy, rngTy), [f, pos]) => (case getRHS f  
                  of SOME(Op.Field _, _) => NONE (* direct probe does not need rewrite *)  
                   | SOME(Op.AddField, [f', g']) => let  
                     (* rewrite to (f@pos) + (g@pos) *)  
                       val lhs1 = IL.Var.copy lhs  
                       val lhs2 = IL.Var.copy lhs  
                       in  
                         ST.tick cntProbeAdd;  
                         decUse f;  
                         incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;  
                         SOME[  
                             (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),  
                             (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),  
                             (lhs, IL.OP(Op.Add rngTy, [lhs1, lhs2]))  
                           ]  
                       end  
                   | SOME(Op.SubField, [f', g']) => let  
                     (* rewrite to (f@pos) - (g@pos) *)  
                       val lhs1 = IL.Var.copy lhs  
                       val lhs2 = IL.Var.copy lhs  
                       in  
                         ST.tick cntProbeSub;  
                         decUse f;  
                         incUse lhs1; incUse f'; incUse lhs2; incUse g'; incUse pos;  
                         SOME[  
                             (lhs1, IL.OP(Op.Probe(domTy, rngTy), [f', pos])),  
                             (lhs2, IL.OP(Op.Probe(domTy, rngTy), [g', pos])),  
                             (lhs, IL.OP(Op.Sub rngTy, [lhs1, lhs2]))  
                           ]  
                       end  
                   | SOME(Op.ScaleField, [s, f']) => let  
                     (* rewrite to s*(f'@pos) *)  
                       val lhs' = IL.Var.copy lhs  
                       in  
                         ST.tick cntProbeScale;  
                         decUse f;  
                         incUse lhs'; incUse f'; incUse s;  
                         SOME[  
                             (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),  
                             (lhs, IL.OP(Op.Scale rngTy, [s, lhs']))  
                           ]  
                       end  
                   | SOME(Op.NegField, [f']) => let  
                     (* rewrite to -(f'@pos) *)  
                       val lhs' = IL.Var.copy lhs  
                       in  
                         ST.tick cntProbeNeg;  
                         decUse f;  
                         incUse lhs'; incUse f';  
                         SOME[  
                             (lhs', IL.OP(Op.Probe(domTy, rngTy), [f', pos])),  
                             (lhs, IL.OP(Op.Neg rngTy, [lhs']))  
                           ]  
                       end  
                   | _ => raise Fail(concat[  
                         "bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)  
                       ])  
                 (* end case *))  
             | (Op.DiffField, [f]) => (case (getRHS f)  
                  of SOME(Op.Field dim, [v, h]) => (case getRHS h  
                        of SOME(Op.Kernel(kernel, k), []) => let  
                             val h' = IL.Var.copy h  
                             in  
                               ST.tick cntDiffField;  
                               decUse f;  
                               incUse h'; incUse v;  
                               SOME[  
                                   (h', IL.OP(Op.Kernel(kernel, k+1), [])),  
                                   (lhs, IL.OP(Op.Field dim, [v, h']))  
                                 ]  
                             end  
                         | _ => raise Fail(concat[  
                               "bogus kernel binding ", V.toString h, " = ", IL.vbToString(V.binding h)  
                             ])  
                       (* end case *))  
                   | SOME(Op.AddField, [f, g]) => raise Fail "Diff(f+g)"  
                   | SOME(Op.SubField, [f, g]) => raise Fail "Diff(f-g)"  
                   | SOME(Op.ScaleField, [s, f']) => let  
                     (* rewrite to s*(D f) *)  
                       val lhs' = IL.Var.copy lhs  
                       in  
                         ST.tick cntDiffScale;  
                         decUse f;  
                         incUse lhs'; incUse f'; incUse s;  
                         SOME[  
                             (lhs', IL.OP(Op.DiffField, [f'])),  
                             (lhs, IL.OP(Op.ScaleField, [s, lhs']))  
                           ]  
                       end  
                   | SOME(Op.NegField, [f']) => let  
                     (* rewrite to -(D f') *)  
                       val lhs' = IL.Var.copy lhs  
                       in  
                         ST.tick cntDiffNeg;  
                         decUse f;  
                         incUse lhs'; incUse f';  
                         SOME[  
                             (lhs', IL.OP(Op.DiffField, [f'])),  
                             (lhs, IL.OP(Op.NegField, [lhs']))  
29                            ]                            ]
30                        end  
31                    | _ => NONE      fun debugDump (phase, prog) = if !debugFlag
                 (* end case *))  
             | _ => NONE  
           (* end case *))  
       | doRHS _ = NONE  
   
   (* simplify expressions *)  
     fun simplify (nd as IL.ND{kind=IL.ASSIGN{stm=(y, rhs), ...}, ...}) =  
           if (useCount y = 0)  
             then () (* skip unused assignments *)  
             else (case doRHS(y, rhs)  
                of SOME[] => IL.CFG.deleteNode nd  
                 | SOME assigns => (  
                     List.app (fn (y, rhs) => V.setBinding(y, IL.VB_RHS rhs)) assigns;  
                     IL.CFG.replaceNodeWithCFG (nd, IL.CFG.mkBlock assigns))  
                 | NONE => ()  
               (* end case *))  
       | simplify _ = ()  
   
   (* reduce the code by removing variables with use counts of 0 *)  
     local  
       fun checkVar (y, _) = (useCount y > 0) orelse (ST.tick cntUnused; false)  
     in  
     fun reduce (nd as IL.ND{kind, ...}) = (case kind  
            of IL.JOIN{phis, ...} => let  
                 fun doVar (y, xs) = if (useCount y = 0)  
                       then (  
                         ST.tick cntUnused;  
                         List.app decUse xs;  
                         false)  
                       else true  
                 in  
                   phis := List.filter doVar (!phis)  
                 end  
             | IL.ASSIGN{stm=(y, rhs), ...} =>  
                 if (useCount y = 0)  
32                    then (                    then (
33                      ST.tick cntUnused;              HighPP.output (Log.logFile(), "HighIL after " ^ phase, prog);
34                      case rhs              prog)
35                       of IL.VAR x => decUse x            else prog
                       | IL.LIT _ => ()  
                       | IL.OP(_, xs) => List.app decUse xs  
                       | IL.APPLY(_, xs) => List.app decUse xs  
                       | IL.CONS(_, xs) => List.app decUse xs  
                     (* end case *);  
                     IL.CFG.deleteNode nd)  
                   else ()  
             | _ => ()  
           (* end case *))  
     end (* local *)  
   
     fun loopToFixPt f = let  
           fun loop n = let  
                 val () = f ()  
                 val n' = Stats.sum{from=firstCounter, to=lastCounter}  
                 in  
                   if (n = n') then () else loop n'  
                 end  
           in  
             loop (Stats.sum{from=firstCounter, to=lastCounter})  
           end  
36    
37      fun optimize (prog as IL.Program{globalInit, initially, strands}) = let      fun checkIL (phase, prog) = if !checkFlag
38            fun doCFG cfg = (            then if CheckHighIL.check ("after " ^ phase, prog)
39                  loopToFixPt (fn () => IL.CFG.apply simplify cfg);              then (
40                  loopToFixPt (fn () => ignore(UnusedElim.reduce cfg)))                TextIO.output(TextIO.stdErr, concat[
41            fun doMethod (IL.Method{body, ...}) = doCFG body                    "***** Internal error after ", phase,
42            fun doStrand (IL.Strand{stateInit, methods, ...}) = (                    ": see log file for details\n"
43                  doCFG stateInit;                  ]);
44                  List.app doMethod methods)                OS.Process.exit OS.Process.failure)
45            fun optPass () = (              else prog
46                  doCFG globalInit;            else prog
47                  List.app doStrand strands)  
48        fun transform (ctl, phase, transform, prog) =
49              if !ctl
50                then checkIL (phase, debugDump(phase, transform prog))
51                else prog
52    
53        fun optimize prog = let
54              val prog = checkIL ("translation to HighIL", prog)
55              val prog = transform (vnFlag, "value numbering", VN.transform, prog)
56              val prog = checkIL ("normalization",
57                    debugDump ("normalization", Normalize.transform prog))
58            in            in
59              loopToFixPt optPass;              prog
 (* FIXME: after optimization, we should filter out any globals that are now unused *)  
             IL.Program{  
                 globalInit = globalInit,  
                 initially = initially,  (* FIXME: we should optimize this code *)  
                 strands = strands  
               }  
60            end            end
61    
62    end    end

Legend:
Removed from v.1231  
changed lines
  Added in v.1232

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