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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1685 - (download) (annotate)
Sun Jan 22 15:23:36 2012 UTC (7 years, 9 months ago) by jhr
File size: 2240 byte(s)
  Create a branch to implement things that we need for the Vis 2012 paper
(* 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 (
		    Stats.tick cntUnused;
		    case rhs
		     of IL.STATE _ => ()
                      | IL.VAR x => decUse x
		      | IL.LIT _ => ()
		      | IL.OP(_, xs) => List.app decUse xs
		      | IL.APPLY(_, xs) => List.app decUse xs
		      | IL.CONS(_, xs) => List.app decUse xs
		    (* end case *);
		    IL.CFG.deleteNode nd)
		  else ()
	    | IL.MASSIGN{stm=([], _, _), ...} => ()  (* executed for side effects *)
	    | IL.MASSIGN{stm=(ys, _, xs), ...} =>
                if 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