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

SCM Repository

[diderot] View of /branches/charisee/src/compiler/IL/unused-elim-fn.sml
ViewVC logotype

View of /branches/charisee/src/compiler/IL/unused-elim-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2386 - (download) (annotate)
Sat Jun 15 18:34:05 2013 UTC (6 years, 4 months ago) by cchiw
File size: 3102 byte(s)
few changes 
(* unused-elim-fn.sml
 *
 * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
 * All rights reserved.
 *
 * This module implements a pass over a CFG that eliminates unused variables
 * (i.e., variables with use count = 0).
 *)

functor UnusedElimFn (
    structure IL : SSA
    val cntUnused : Stats.counter
  ) : sig

    val reduce : IL.cfg -> bool

  end = struct

    fun useCount (IL.V{useCnt, ...}) = !useCnt

  (* adjust a variable's use count *)
    fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)

  (* flag used to mark visited nodes in DFS walk of the CFG *)
    val {getFn, setFn} = PropList.newFlag (fn (IL.ND{props, ...}) => props)

    fun reduceNd (nd as IL.ND{kind, ...}) = (case kind
           of IL.JOIN{phis, ...} => let
                fun doVar (y, xs) = if (useCount y = 0)
                      then (
                        Stats.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)
                then (case rhs
                   of IL.STATE _ => IL.CFG.deleteNode nd
                    | IL.VAR x => (decUse x; IL.CFG.deleteNode nd)
                    | IL.LIT _ => IL.CFG.deleteNode nd
(* FIXME: we should distinguish between mutation effects and allocation effects! *)
                    | IL.OP(rator, xs) => if IL.Op.isPure rator
                        then (List.app decUse xs; IL.CFG.deleteNode nd)
                        else ()
                    | IL.APPLY(_, xs) => (List.app decUse xs; IL.CFG.deleteNode nd)
                    | IL.CONS(_, xs) => (List.app decUse xs; IL.CFG.deleteNode nd)
                    | IL.EINAPP(exp, xs)=> (List.app decUser xs; IL.CFG.deleteNodend)
                  (* end case *))
                else ()
            | IL.MASSIGN{stm=([], _, _), ...} => ()  (* executed for side effects *)
            | IL.MASSIGN{stm=(ys, rator, xs), ...} =>
(* FIXME: we should distinguish between mutation effects and allocation effects! *)
                if IL.Op.isPure rator andalso List.all (fn y => (useCount y = 0)) ys
                  then (
                    Stats.tick cntUnused;
                    List.app decUse xs;
                    IL.CFG.deleteNode nd)
                  else ()
            | _ => ()
          (* end case *))

  (* we apply the reduction in postorder, since eliminating a variable will
   * decrease the count.
   *)
    fun reduce (IL.CFG{entry, ...}) = let
          val n = Stats.count cntUnused
          fun dfs (nd, l) =
                if getFn nd
                  then l
                  else (
                    setFn (nd, true);
                    List.foldl dfs (nd :: l) (IL.Node.succs nd))
        (* nodes in reverse DFS order *)
          val nodes = dfs (entry, [])
          in
            List.app (fn nd => (reduceNd nd; setFn(nd, false))) nodes;
            Stats.count cntUnused > n
          end

  end

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