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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3349 - (download) (annotate)
Tue Oct 27 15:16:36 2015 UTC (5 years, 4 months ago) by jhr
File size: 3274 byte(s)
making copyrights consistent for all code in the repository
(* unused-elim-fn.sml
 *
 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
 *
 * COPYRIGHT (c) 2015 The University of Chicago
 * 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 _ => (Stats.tick cntUnused; IL.CFG.deleteNode nd)
                    | IL.VAR x => (Stats.tick cntUnused; decUse x; IL.CFG.deleteNode nd)
                    | IL.LIT _ => (Stats.tick cntUnused; IL.CFG.deleteNode nd)
(* FIXME: we should distinguish between mutation effects and allocation effects! *)
                    | IL.OP(rator, xs) => if IL.Op.isPure rator
                        then (Stats.tick cntUnused; List.app decUse xs; IL.CFG.deleteNode nd)
                        else ()
                    | IL.APPLY(_, xs) => (
                        Stats.tick cntUnused; List.app decUse xs; IL.CFG.deleteNode nd)
                    | IL.CONS(_, xs) => (
                        Stats.tick cntUnused; List.app decUse xs; IL.CFG.deleteNode nd)
                  (* 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