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

SCM Repository

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

Diff of /trunk/src/compiler/IL/value-numbering-fn.sml

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

revision 1232, Mon May 16 23:37:52 2011 UTC revision 1640, Wed Nov 16 02:19:51 2011 UTC
# Line 58  Line 58 
58      val setVN = setVN      val setVN = setVN
59      fun varToExp x = getExp(getVN x)      fun varToExp x = getExp(getVN x)
60      fun bindVarToExp (ENV{avail}, x, e) = (      fun bindVarToExp (ENV{avail}, x, e) = (
61    (*DEBUG**Log.msg(concat["** bindVarToExp: ", IL.Var.toString x, " --> ", E.toString e, "\n"]);*)
62            setVN(x, x); setExp(x, e);            setVN(x, x); setExp(x, e);
63            ENV{avail = ValueMap.insert(avail, e, x)})            ENV{avail = ValueMap.insert(avail, e, x)})
64      fun expToVN (ENV{avail}, e) = ValueMap.find(avail, e)      fun expToVN (ENV{avail}, e) = ValueMap.find(avail, e)
# Line 68  Line 69 
69              if IL.Var.same(x, x')              if IL.Var.same(x, x')
70                then x                then x
71                else (                else (
72  (*DEBUG Log.msg(concat["** rename ", IL.Var.toString x, " to ", IL.Var.toString x', "\n"]);*)  (*DEBUG**Log.msg(concat["** rename ", IL.Var.toString x, " to ", IL.Var.toString x', "\n"]);*)
73                  decUse x; incUse x';                  decUse x; incUse x';
74                  x')                  x')
75            end            end
# Line 106  Line 107 
107                        (* rewrite node to rename variables *)                        (* rewrite node to rename variables *)
108                          then IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(y, IL.RHS.map rename rhs))                          then IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(y, IL.RHS.map rename rhs))
109                          else ()                          else ()
110                      | IL.MASSIGN{stm=([], rator, xs), succ, ...} =>
111                          if (List.exists changed xs)
112                          (* rewrite node to rename variables *)
113                            then IL.CFG.replaceNode(nd, IL.Node.mkMASSIGN([], rator, List.map rename xs))
114                            else ()
115                      | IL.MASSIGN{stm=(ys, rator, xs), succ, ...} =>
116                          if List.all changed ys
117                            then IL.CFG.deleteNode nd (* deleting redundant assignment *)
118                          else if (List.exists changed xs)
119                          (* rewrite node to rename variables *)
120                            then IL.CFG.replaceNode(nd, IL.Node.mkMASSIGN(ys, rator, List.map rename xs))
121                            else ()
122                    | IL.NEW{strand, args, ...} =>                    | IL.NEW{strand, args, ...} =>
123                        if List.exists changed args                        if List.exists changed args
124                          then IL.CFG.replaceNode(nd, IL.Node.mkNEW{                          then IL.CFG.replaceNode(nd, IL.Node.mkNEW{
125                              strand=strand, args=List.map rename args                              strand=strand, args=List.map rename args
126                            })                            })
127                          else ()                          else ()
128                      | IL.SAVE{lhs, rhs, ...} =>
129                          if changed rhs
130                            then IL.CFG.replaceNode(nd, IL.Node.mkSAVE(lhs, rename rhs))
131                            else ()
132                    | IL.EXIT{kind, live, ...} =>                    | IL.EXIT{kind, live, ...} =>
133                        if List.exists changed live                        if List.exists changed live
134                          then let                          then let
# Line 134  Line 151 
151    
152      fun transformCFG (liveIn, renameIn, cfg) = let      fun transformCFG (liveIn, renameIn, cfg) = let
153            val tbl = E.new()            val tbl = E.new()
154              val mkSTATE = E.mkSTATE tbl
155            val mkVAR = E.mkVAR tbl            val mkVAR = E.mkVAR tbl
156            val mkLIT = E.mkLIT tbl            val mkLIT = E.mkLIT tbl
157            val mkOP = E.mkOP tbl            val mkOP = E.mkOP tbl
158              val mkMULTIOP = E.mkMULTIOP tbl
159            val mkAPPLY = E.mkAPPLY tbl            val mkAPPLY = E.mkAPPLY tbl
160            val mkCONS = E.mkCONS tbl            val mkCONS = E.mkCONS tbl
161            val mkPHI = E.mkPHI tbl            val mkPHI = E.mkPHI tbl
# Line 144  Line 163 
163            fun varsToExp (env, xs) = List.map varToExp xs            fun varsToExp (env, xs) = List.map varToExp xs
164          (* convert an SSA RHS into a hash-consed expression *)          (* convert an SSA RHS into a hash-consed expression *)
165            fun mkExp (env, rhs) = (case rhs            fun mkExp (env, rhs) = (case rhs
166                   of IL.VAR x => varToExp x                   of IL.STATE x => mkSTATE x
167                      | IL.VAR x => varToExp x
168                    | IL.LIT l => mkLIT l                    | IL.LIT l => mkLIT l
169                    | IL.OP(rator, args) => mkOP(rator, varsToExp(env, args))                    | IL.OP(rator, args) => mkOP(rator, varsToExp(env, args))
170                    | IL.APPLY(f, args) => mkAPPLY(f, varsToExp(env, args))                    | IL.APPLY(f, args) => mkAPPLY(f, varsToExp(env, args))
# Line 192  Line 212 
212                              in                              in
213                                case expToVN(env, exp)                                case expToVN(env, exp)
214                                 of SOME vn => ((* y is redundant, so map it to vn *)                                 of SOME vn => ((* y is redundant, so map it to vn *)
215  (* DEBUG Log.msg(concat["** redundant assignment: ", IL.assignToString (y, rhs),*)  (* DEBUG ** Log.msg(concat["** redundant multi-assignment: ", IL.assignToString (y, rhs),*)
216  (* DEBUG "; VN[", IL.Var.toString y, "] = ", IL.Var.toString vn, "\n"]);*)  (* DEBUG **"; VN[", IL.Var.toString y, "] = ", IL.Var.toString vn, "\n"]);*)
217                                      ST.tick cntRedundantAssign;                                      ST.tick cntRedundantAssign;
218                                      setVN(y, vn);                                      setVN(y, vn);
219                                      env)                                      env)
220                                  | NONE => (                                  | NONE => bindVarToExp(env, y, exp)
                                     bindVarToExp(env, y, exp))  
221                                (* end case *)                                (* end case *)
222                              end                              end
223                            | IL.MASSIGN{stm=(ys, rator, xs), succ, ...} => let
224                                val xs = varsToExp(env, xs)
225                                fun mkExps (env, _, []) = env
226                                  | mkExps (env, i, y::ys) = let
227                                      val exp = mkMULTIOP(i, rator, xs)
228                                      in
229                                        case expToVN(env, exp)
230                                         of SOME vn => ((* y is redundant, so map it to vn *)
231                                              ST.tick cntRedundantAssign;
232                                              setVN(y, vn);
233                                              mkExps (env, i+1, ys))
234                                          | NONE => mkExps (bindVarToExp(env, y, exp), i+1, ys)
235                                        (* end case *)
236                                      end
237                                in
238                                  mkExps (env, 0, ys)
239                                end
240                          | _ => env                          | _ => env
241                        (* end case *))                        (* end case *))
242                  in                  in
# Line 251  Line 287 
287            end            end
288    
289      fun transform prog = let      fun transform prog = let
290            val IL.Program{globalInit, initially, strands} = prog            val IL.Program{props, globalInit, initially, strands} = prog
291            val {cfg=globalInit, rename} = transformCFG' ([], [], globalInit)            val {cfg=globalInit, rename} = transformCFG' ([], [], globalInit)
292            val globals = IL.CFG.liveAtExit globalInit            val globals = IL.CFG.liveAtExit globalInit
293          (* transform the strand initialization code *)          (* transform the strand initialization code *)
# Line 293  Line 329 
329                  val liveIn = params @ globals                  val liveIn = params @ globals
330                  val stateInit = transformCFG (liveIn, rename, stateInit)                  val stateInit = transformCFG (liveIn, rename, stateInit)
331  (* FIXME: what if a state variable becomes redundant? *)  (* FIXME: what if a state variable becomes redundant? *)
332                  fun transformMeth (IL.Method{name, stateIn, body}) = let                  fun transformMeth (IL.Method{name, body}) = let
                       val liveIn = stateIn @ liveIn  
333                        val body = transformCFG (liveIn, rename, body)                        val body = transformCFG (liveIn, rename, body)
334                        in                        in
335                          IL.Method{name=name, stateIn=stateIn, body=body}                          IL.Method{name=name, body=body}
336                        end                        end
337                  in                  in
338                    IL.Strand{                    IL.Strand{
# Line 311  Line 346 
346            val strands = List.map transformStrand strands            val strands = List.map transformStrand strands
347            in            in
348              IL.Program{              IL.Program{
349                    props = props,
350                  globalInit = globalInit,                  globalInit = globalInit,
351                  initially = initially,                  initially = initially,
352                  strands = strands                  strands = strands

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

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