(* 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
Click to toggle
does not end with </html> tag
does not end with </body> tag
The output has ended thus: > (reduceNd nd; setFn(nd, false))) nodes; Stats.count cntUnused > n end end