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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2801 - (download) (annotate)
Thu Nov 6 23:08:02 2014 UTC (4 years, 10 months ago) by jhr
File size: 6183 byte(s)
  fixed a bug in the global promotion code
(* promote-fn.sml
 *
 * COPYRIGHT (c) 2014 The Diderot Project (http://diderot-language.cs.uchicago.edu)
 * All rights reserved.
 *
 * Transformations, such as normalization, can create references to variables defined
 * in the global initialization section from nested scopes (e.g., inside strands).
 * This functor implements a pass that promotes such variables to be globals.
 *)

functor PromoteFn (IL : SSA) : sig

    val transform : IL.program -> IL.program

  end = struct

    structure V = IL.Var
    structure VTbl = V.Tbl
    structure VMap = V.Map

  (* adjust a variable's use count *)
    fun incUse (IL.V{useCnt, ...}) = (useCnt := !useCnt + 1)
    fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
    fun incGlobal (IL.GV{useCnt, ...}) = (useCnt := !useCnt + 1)

  (* variables in the global initialization section are either just used locally
   * or used to define a global (via GASSIGN).
   *)
    datatype info = LOCAL | GLOBAL of IL.global_var

    fun initTbl (inputInit, globalInit) = let
	  val tbl = VTbl.mkTable (64, Fail "promote")
	  val insert = VTbl.insert tbl
	  fun doNode nd = (case IL.Node.kind nd
		 of IL.GASSIGN{lhs, rhs, ...} => insert (rhs, GLOBAL lhs)
		  | _ => List.app (fn x => insert (x, LOCAL)) (IL.Node.defs nd)
		(* end case *))
	  in
	    IL.CFG.apply doNode inputInit;
	    IL.CFG.apply doNode globalInit;
	    tbl
	  end

    fun transform (prog as IL.Program{globals=[], ...}) = prog
      | transform (IL.Program{props, globals, inputInit, globalInit, initially, strands}) = let
	(* table mapping locals in the globalInit to info *)
	  val promoteTbl = initTbl (inputInit, globalInit)
	(* newly defined globals paired with their globalInit local definition *)
	  val newGlobs : (IL.global_var * IL.var) list ref = ref []
	(* update a CFG as necessary to references to globalInit locals with references to new
	 * globals.
	 *)
	  fun doCFG cfg = let
	      (* assignment statements to load local copies of the new globals; these get put
	       * at the beginning of the block.
	       *)
		val initStms = ref []
		fun doNode (nd as IL.ND{id, props, kind}, env) = let
		      fun doUse (false, [], _, env, _) = env
			| doUse (true, [], ys, env, mkNode) = (
			    IL.CFG.replaceNode (nd, mkNode(List.rev ys));
			    env)
			| doUse (changed, x::xs, ys, env, mkNode) = (case VTbl.find promoteTbl x
			     of SOME LOCAL => let
				  val x' = V.copy x
				  val gx = IL.GlobalVar.new(false, V.name x, V.ty x)
				  in
				    decUse x; incUse x'; incGlobal gx;
				    initStms := IL.ASSGN(x', IL.GLOBAL gx) :: !initStms;
				    newGlobs := (gx, x) :: !newGlobs;
				    VTbl.insert promoteTbl (x, GLOBAL gx);
				    doUse (true, xs, x'::ys, VMap.insert(env, x, x'), mkNode)
				  end
			      | SOME(GLOBAL gx) => (case VMap.find(env, x)
				   of SOME x' => (
					decUse x; incUse x';
					doUse (true, xs, x'::ys, env, mkNode))
				    | NONE => let (* no previous use of g in this CFG *)
					val x' = V.copy x
					in
					  decUse x; incUse x'; incGlobal gx;
					  initStms := IL.ASSGN(x', IL.GLOBAL gx) :: !initStms;
					  doUse (true, xs, x'::ys, VMap.insert(env, x, x'), mkNode)
					end
				  (* end case *))
			      | NONE => doUse (changed, xs, x::ys, env, mkNode)
			    (* end case *))
		      fun doArgs (args, mkNode) = doUse (false, args, [], env, mkNode)
		      in
			case kind
			 of IL.NULL => env
			  | IL.ENTRY _ => env
			  | IL.JOIN _ => env
			  | IL.COND _ => env
			  | IL.COM _ => env
			  | IL.ASSIGN{stm=(lhs, rhs), ...} => (case rhs
			       of IL.GLOBAL _ => env
				| IL.STATE _ => env
				| IL.VAR x => doArgs ([x], fn [x] => IL.Node.mkASSIGN(lhs, IL.VAR x))
				| IL.LIT _ => env
				| IL.OP(rator, args) =>
				    doArgs (args, fn args => IL.Node.mkASSIGN(lhs, IL.OP(rator, args)))
				| IL.APPLY(f, args) =>
				    doArgs (args, fn args => IL.Node.mkASSIGN(lhs, IL.APPLY(f, args)))
				| IL.CONS(ty, args) =>
				    doArgs (args, fn args => IL.Node.mkASSIGN(lhs, IL.CONS(ty, args)))
			      (* end case *))
			  | IL.MASSIGN{stm=(lhs, rator, rhs), ...} =>
			      doArgs (rhs, fn rhs => IL.Node.mkMASSIGN(lhs, rator, rhs))
			  | IL.GASSIGN _ => raise Fail "unexpected GASSIGN"
			  | IL.NEW{strand, args, ...} =>
			      doArgs (args, fn args => IL.Node.mkNEW{strand=strand, args=args})
			  | IL.SAVE{lhs, rhs, ...} =>
			      doArgs ([rhs], fn [rhs] => IL.Node.mkSAVE(lhs, rhs))
			  | IL.EXIT{live=[], ...} => env
			  | IL.EXIT{kind, live, ...} =>
			      doArgs (live, fn live => IL.Node.mkEXIT(kind, live))
			(* end case *)
		      end
		in
		  List.foldl doNode VMap.empty (IL.CFG.sort cfg);
		  case !initStms
		   of [] => cfg
		    | stms => IL.CFG.prependBlock(List.rev stms, cfg)
		  (* end case *)
		end
	(* process the initially code *)
	  val initially' = let
		val IL.Initially{isArray, rangeInit, iters, create=(cfg, strand, args)} = initially
		in
		  IL.Initially{
		      isArray = isArray,
		      rangeInit = doCFG rangeInit,
		      iters = iters,
		      create = (doCFG cfg, strand, args)
		    }
		end
	(* process a strand method *)
	  fun doMeth (IL.Method{name, body}) = IL.Method{name = name, body = doCFG body}
	(* process a strand *)
	  fun doStrand (IL.Strand{name, params, state, stateInit, methods}) = IL.Strand{
		  name = name, params = params, state = state,
		  stateInit = doCFG stateInit,
		  methods = List.map doMeth methods
		}
	  val strands' = List.map doStrand strands
	(* check to see if we have created new globals and thus need to update the globalInit block *)
	  val (globals', globalInit') = (case !newGlobs
		 of [] => (globals, globalInit)
		  | globs => let
		      fun f ([], globals, stms) = (globals, stms)
			| f ((gx, x)::globs, globals, stms) = (
			      incUse x;
			      IL.GlobalVar.setBinding(gx, x);
			      f (globs, gx::globals, IL.GASSGN(gx, x)::stms))
		      val (globals', stms) = f (globs, [], [])
		      in
			(globals @ globals', IL.CFG.appendBlock (globalInit, stms))
		      end
		(* end case *))
	  in
	    IL.Program{
		props = props,
		globals = globals',
		inputInit = inputInit,
		globalInit = globalInit',
		initially = initially',
		strands = strands'
	      }
	  end
	  
  end

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