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

SCM Repository

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

View of /trunk/src/compiler/IL/backward-dfa-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 258 - (download) (annotate)
Mon Aug 9 18:36:44 2010 UTC (9 years, 1 month ago) by jhr
File size: 1605 byte(s)
  Added BackwardDFAFn functor
(* backward-dfa-fn.sml
 *
 * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
 * All rights reserved.
 *
 * Backward data-flow analysis for IL code.
 *)

functor BackwardDFAFn (D : DOMAIN) :> sig

    structure D : DOMAIN

  (* abstract representation of analysis results *)
    type result

  (* given a function for defining out values for exis and the root statement, do the
   * backward DFA on the CFG
   *)
    val analyse : (D.IL.node -> D.t) * D.IL.stmt -> result

  (* get result for a node *)
    val inValue : result * D.IL.node -> D.t

  (* scrub results to reclaim space *)
    val scrub : result -> unit

  end = struct

    structure D = D
    structure IL = D.IL

    type result = IL.node list

    val {setFn, getFn, clrFn, ...} =
	  PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)

    fun analyse (exitVal, stm) = let
	(* use DFS order to get quicker convergence *)
	  val nodes = IL.sortNodes stm
	(* set initial values for exit nodes *)
	  val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setFn(nd, exitVal nd)) nodes
	  fun iterate () = let
		val anyChange = ref false
		fun doNode nd = let
		      val outValue = D.join (List.map getFn (IL.Node.succs nd))
		      val inValue = D.transfer (outValue, nd)
		      in
			if D.same(getFn nd, inValue)
			  then ()
			  else (setFn(nd, inValue); anyChange := true)
		      end
		in
		  List.app doNode nodes;
		  if !anyChange then iterate() else ()
		end
	  in
	    iterate (); nodes
	  end

    fun inValue (_, nd) = getFn nd

    fun scrub nodes = List.app clrFn nodes

  end

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