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

SCM Repository

[diderot] Diff of /branches/pure-cfg/src/compiler/IL/value-numbering-fn.sml
ViewVC logotype

Diff of /branches/pure-cfg/src/compiler/IL/value-numbering-fn.sml

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

revision 740, Mon Apr 4 02:07:42 2011 UTC revision 741, Mon Apr 4 16:37:33 2011 UTC
# Line 34  Line 34 
34        | LIT of Literal.literal        | LIT of Literal.literal
35        | OP of Op.rator * exp list        | OP of Op.rator * exp list
36        | APPLY of ILBasis.name * exp list        | APPLY of ILBasis.name * exp list
37        | CONS of exp list        | CONS of IL.Ty.ty * exp list
38          | PHI of exp list
39    
40      fun hashArgs (args, base) =      fun hashArgs (args, base) =
41            List.foldl (fn (E{uid, ...}, h) => uid+h) base args            List.foldl (fn (E{uid, ...}, h) => uid+h) base args
# Line 43  Line 44 
44        | hashNode (LIT l) = Literal.hash l        | hashNode (LIT l) = Literal.hash l
45        | hashNode (OP(rator, args)) = hashArgs (IL.Op.hash rator, args)        | hashNode (OP(rator, args)) = hashArgs (IL.Op.hash rator, args)
46        | hashNode (APPLY(f, args)) = hashArgs (ILBasis.hash f, args)        | hashNode (APPLY(f, args)) = hashArgs (ILBasis.hash f, args)
47        | hashNode (CONS args) = hashArgs (0w49, args)        | hashNode (CONS(ty, args)) = hashArgs (IL.Ty.hash ty + 0w49, args)
48          | hashNode (PHI args) = hashArgs (0w57, args)
49    
50      fun sameNode (VAR x, VAR y) = IL.Var.same(x, y)      fun sameNode (VAR x, VAR y) = IL.Var.same(x, y)
51        | sameNode (LIT l1, LIT l2) = Literal.same(l1, l2)        | sameNode (LIT l1, LIT l2) = Literal.same(l1, l2)
52        | sameNode (OP(rator1, args1), OP(rator2, args2)) =        | sameNode (OP(rator1, args1), OP(rator2, args2)) =
53              IL.Op.same(rator1, rator2) andalso ListPair.allEq sameNode (args1, args2)
54        | sameNode (APPLY(f1, args1), APPLY(f2, args2)) =        | sameNode (APPLY(f1, args1), APPLY(f2, args2)) =
55        | sameNode (CONS args1, CONS args2) =            ILBasis.same(f1, f2) andalso ListPair.allEq sameNode (args1, args2)
56          | sameNode (CONS(ty1, args1), CONS(ty2, args2)) =
57              IL.Ty.same(ty1, ty2) andalso ListPair.allEq sameNode (args1, args2)
58          | sameNode (PHI args1, PHI args2) = ListPair.allEq sameNode (args1, args2)
59    
60      structure Tbl = HashTableFn (      structure Tbl = HashTableFn (
61        struct        struct
# Line 116  Line 122 
122          }          }
123      in      in
124    (* map variables to their hash-consed definition *)    (* map variables to their hash-consed definition *)
125        val getVN = getVN
126      fun varToExp x = getExp(getVN x)      fun varToExp x = getExp(getVN x)
127      fun bindVarToExp (E{avail}, x, e) = (      fun bindVarToExp (E{avail}, x, e) = (
128            setVN(x, x); setExp(x, e);            setVN(x, x); setExp(x, e);
# Line 133  Line 140 
140            fun mkExp (env, rhs) = (case rhs            fun mkExp (env, rhs) = (case rhs
141                   of IL.VAR x => varToExp(env, x)                   of IL.VAR x => varToExp(env, x)
142                    | IL.LIT l => hashConsExp(LIT l)                    | IL.LIT l => hashConsExp(LIT l)
143                    | IL.OP(rator, args) => hashConsExp(OP(rator, varsToExp(env args)))                    | IL.OP(rator, args) => hashConsExp(OP(rator, varsToExp(env, args)))
144                    | IL.APPLY(f, args) => hashConsExp(APPLY(f, varsToExp(env args)))                    | IL.APPLY(f, args) => hashConsExp(APPLY(f, varsToExp(env, args)))
145                    | IL.CONS args => hashConsExp(CONS(varsToExp(env args)))                    | IL.CONS(ty, args) => hashConsExp(CONS(ty, varsToExp(env, args)))
146                  (* end case *))                  (* end case *))
147            fun vn (env, nd) = let            fun vn (env, nd) = let
148                  val env = (case IL.Node.kind nd                  val env = (case IL.Node.kind nd
149                         of IL.JOIN{succ, ...} =>                         of IL.JOIN{succ, phis, ...} => let
150                                fun doPhi ((y, xs), env) = let
151                                      val vn::vns = List.map getVN xs
152                                      in
153                                        if List.all (fn vn' => IL.Var.same(vn, vn')) vns
154                                          then (* a meaningless phi node; map y to vn *)
155                                          else let
156                                            val exp = hashConsExp(PHI(varsToExp(env, args)))
157                                            in
158                                              case expToVN(env, exp)
159                                               of SOME x => (* a redundant phi node *)
160                                                | NONE => bindVarToExp(env, y, exp)
161                                              (* end case *)
162                                            end
163                                      end
164                                in
165                                  List.foldl doPhi env (!phis)
166                                end
167                          | IL.ASSIGN{stm=(y, rhs), succ, ...} => let                          | IL.ASSIGN{stm=(y, rhs), succ, ...} => let
168                              val exp = mkExp(env, rhs)                              val exp = mkExp(env, rhs)
169                              in                              in

Legend:
Removed from v.740  
changed lines
  Added in v.741

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