(* forward-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.
 *
 * Forward data-flow analysis for IL code.
 *)

functor ForwardDFAFn (D : DOMAIN) :> sig

    structure D : DOMAIN = D

  (* given the entry value and root statement, do the forward DFA on the CFG and
   * return the list of nodes that were analysed.
   *)
    val analyse : 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

    type result = IL.node list

    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 (entryVal, cfg) = let
	(* use DFS order to get quicker convergence *)
	  val nodes as entry::rest = IL.CFG.sort cfg
	(* the first pass does not do change propagation, since we haven't computed anything yet *)
	  fun initNode nd = let
		val inValue = D.join (List.map getOut (IL.Node.preds nd))
		val outValue = D.transfer (inValue, nd)
		in
		  setIn (nd, inValue);
		  setOut (nd, outValue)
		end
	(* once nodes are initialized, we iterate until we reach a fixed point *)
	  fun iterate () = let
		val anyChange = ref false
		fun doNode nd = let
		      val inValue = D.join (List.map getOut (IL.Node.preds nd))
		      in
			if D.same(getIn nd, inValue)
			  then () (* input unchanged, so output will be unchanged *)
			  else let
			    val outValue = D.transfer (inValue, nd)
			    in
			      anyChange := true;
			      setIn (nd, inValue);
			      if D.same(getOut nd, outValue)
				then ()
				else setOut(nd, outValue)
			    end
		      end
		in
		  List.app doNode rest;
		  if !anyChange then iterate() else ()
		end
	  in
	  (* initialize the output of the CFG entry node *)
	    setOut (entry, entryVal);
	  (* initialize the rest of the nodes *)
	    List.app initNode rest;
	  (* iterate to a fixed point *)
	    iterate ();
	    nodes
	  end

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

    fun scrub nodes = List.app clear nodes

  end