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

SCM Repository

[diderot] Annotation of /trunk/src/compiler/IL/unused-elim-fn.sml
ViewVC logotype

Annotation of /trunk/src/compiler/IL/unused-elim-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3349 - (view) (download)

1 : jhr 1115 (* unused-elim-fn.sml
2 :     *
3 : jhr 3349 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     *
5 :     * COPYRIGHT (c) 2015 The University of Chicago
6 : jhr 1115 * All rights reserved.
7 :     *
8 :     * This module implements a pass over a CFG that eliminates unused variables
9 :     * (i.e., variables with use count = 0).
10 :     *)
11 :    
12 :     functor UnusedElimFn (
13 :     structure IL : SSA
14 :     val cntUnused : Stats.counter
15 :     ) : sig
16 :    
17 :     val reduce : IL.cfg -> bool
18 :    
19 :     end = struct
20 :    
21 :     fun useCount (IL.V{useCnt, ...}) = !useCnt
22 :    
23 :     (* adjust a variable's use count *)
24 :     fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
25 :    
26 :     (* flag used to mark visited nodes in DFS walk of the CFG *)
27 :     val {getFn, setFn} = PropList.newFlag (fn (IL.ND{props, ...}) => props)
28 :    
29 :     fun reduceNd (nd as IL.ND{kind, ...}) = (case kind
30 : jhr 2356 of IL.JOIN{phis, ...} => let
31 :     fun doVar (y, xs) = if (useCount y = 0)
32 :     then (
33 :     Stats.tick cntUnused;
34 :     List.app decUse xs;
35 :     false)
36 :     else true
37 :     in
38 :     phis := List.filter doVar (!phis)
39 :     end
40 :     | IL.ASSIGN{stm=(y, rhs), ...} => if (useCount y = 0)
41 : jhr 2660 then (
42 :     case rhs
43 :     of IL.STATE _ => (Stats.tick cntUnused; IL.CFG.deleteNode nd)
44 :     | IL.VAR x => (Stats.tick cntUnused; decUse x; IL.CFG.deleteNode nd)
45 :     | IL.LIT _ => (Stats.tick cntUnused; IL.CFG.deleteNode nd)
46 : jhr 2356 (* FIXME: we should distinguish between mutation effects and allocation effects! *)
47 :     | IL.OP(rator, xs) => if IL.Op.isPure rator
48 : jhr 2660 then (Stats.tick cntUnused; List.app decUse xs; IL.CFG.deleteNode nd)
49 : jhr 2356 else ()
50 : jhr 2660 | IL.APPLY(_, xs) => (
51 :     Stats.tick cntUnused; List.app decUse xs; IL.CFG.deleteNode nd)
52 :     | IL.CONS(_, xs) => (
53 :     Stats.tick cntUnused; List.app decUse xs; IL.CFG.deleteNode nd)
54 : jhr 2356 (* end case *))
55 :     else ()
56 :     | IL.MASSIGN{stm=([], _, _), ...} => () (* executed for side effects *)
57 :     | IL.MASSIGN{stm=(ys, rator, xs), ...} =>
58 :     (* FIXME: we should distinguish between mutation effects and allocation effects! *)
59 :     if IL.Op.isPure rator andalso List.all (fn y => (useCount y = 0)) ys
60 : jhr 1640 then (
61 :     Stats.tick cntUnused;
62 :     List.app decUse xs;
63 :     IL.CFG.deleteNode nd)
64 : jhr 2356 else ()
65 :     | _ => ()
66 :     (* end case *))
67 : jhr 1115
68 :     (* we apply the reduction in postorder, since eliminating a variable will
69 :     * decrease the count.
70 :     *)
71 :     fun reduce (IL.CFG{entry, ...}) = let
72 : jhr 2356 val n = Stats.count cntUnused
73 :     fun dfs (nd, l) =
74 :     if getFn nd
75 :     then l
76 :     else (
77 :     setFn (nd, true);
78 :     List.foldl dfs (nd :: l) (IL.Node.succs nd))
79 :     (* nodes in reverse DFS order *)
80 :     val nodes = dfs (entry, [])
81 :     in
82 :     List.app (fn nd => (reduceNd nd; setFn(nd, false))) nodes;
83 :     Stats.count cntUnused > n
84 :     end
85 : jhr 1115
86 :     end

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