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 3349 - (download) (annotate)
Tue Oct 27 15:16:36 2015 UTC (5 years, 11 months ago) by jhr
File size: 2480 byte(s)
making copyrights consistent for all code in the repository
(* backward-dfa-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.
 * Backward data-flow analysis for IL code.

functor BackwardDFAFn (D : DOMAIN) :> sig

    structure D : DOMAIN

  (* given a function for defining out values for exits and the root node, do the
   * backward DFA on the CFG and return the list of nodes analysed.
    val analyse : (D.IL.node -> D.t) * D.IL.cfg -> D.IL.node list

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

  (* scrub results to reclaim space *)
    val scrub : D.IL.node list -> unit

  end = struct

    structure D = D
    structure IL = D.IL

    val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
	  PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
    val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
	  PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)

    fun clear node = (clrIn node; clrOut node)

    fun analyse (exitVal, cfg) = let
	(* use reverse DFS order to get quicker convergence *)
	  val nodes = List.rev (IL.CFG.sort cfg)
	(* the first pass does not do change propagation, since we haven't computed anything yet *)
	  fun initNode nd = if IL.Node.hasSucc nd
		then let
		  val outValue = D.join (List.map getIn (IL.Node.succs nd))
		  val inValue = D.transfer (outValue, nd)
		    setOut (nd, outValue);
		    setIn (nd, inValue)
		else setIn(nd, exitVal nd)  (* exit node *)
	(* once nodes are initialized, we iterate until we reach a fixed point *)
	  fun iterate () = let
		val anyChange = ref false
		fun doNode nd = let
		      val outValue = D.join (List.map getIn (IL.Node.succs nd))
			if D.same(getOut nd, outValue)
			  then ()(* output unchanged, so input will be unchanged *)
			  else let
			    val inValue = D.transfer (outValue, nd)
			      anyChange := true;
			      setOut (nd, outValue);
			      if D.same(getIn nd, inValue)
				then ()
				else setIn(nd, inValue)
		  List.app doNode nodes;
		  if !anyChange then iterate() else ()
	  (* initialize the rest of the nodes *)
	    List.app initNode nodes;
	  (* iterate to a fixed point *)
	    iterate ();

    fun inValue nd = getIn nd
    fun outValue nd = getOut nd

    fun scrub nodes = List.app clear nodes


ViewVC Help
Powered by ViewVC 1.0.0