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

SCM Repository

[diderot] View of /branches/vis15/src/compiler/low-to-tree/scope-vars.sml
ViewVC logotype

View of /branches/vis15/src/compiler/low-to-tree/scope-vars.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4088 - (download) (annotate)
Wed Jun 29 00:51:17 2016 UTC (3 years, 1 month ago) by jhr
File size: 5143 byte(s)
working on merge: bug fixing
(* scope-vars.sml
 *
 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
 *
 * COPYRIGHT (c) 2016 The University of Chicago
 * All rights reserved.
 *)

structure ScopeVars : sig

  (* attach local variables to the innermost block that contains their scope *)
    val assignScopes : TreeVar.t list * TreeIR.block -> TreeIR.block

  end = struct

    structure IR = TreeIR
    structure M = TreeVar.Map
    structure S = TreeVar.Set

  (* a rose-tree representation of the nesting of blocks *)
    datatype scope_nest = Scope of {
	locals : IR.var list ref,	(* the block in the IR *)
	used : S.set,			(* the set of locals mentioned in the block, but not
					 * in sub-blocks
					 *)
	inner : scope_nest list		(* nested sub-blocks *)
      }

  (* build a scope_nest tree and compute a mapping from local variables to their minimum
   * binding depth.
   *)
    fun buildScopeTree (def, blk) = let
	  fun recordDepth d (x, depthMap) = (case M.find(depthMap, x)
		 of NONE => M.insert(depthMap, x, d)
		  | SOME d' => if (d < d') then M.insert(depthMap, x, d) else depthMap
		(* end case *))
	  fun doBlock (IR.Block{locals, body}, def, depth, depthMap) = let
		fun doStms ([], def, used, depthMap, kids) = let
		      val depthMap = S.foldl (recordDepth depth) depthMap used
		      in
		        (Scope{locals = locals, used = used, inner = kids}, depthMap)
		      end
		  | doStms (stm::stms, def, used, depthMap, kids) = (case stm
		       of IR.S_Assign(true, x, e) =>
			    doStms (stms, S.add(def, x), doExp def (e, used), depthMap, kids)
			| IR.S_Assign(false, x, e) =>
			    doStms (stms, def, doExp def (e, S.add(used, x)), depthMap, kids)
			| IR.S_MAssign(xs, e) =>
			    doStms (stms, def, doExp def (e, S.addList(used, xs)), depthMap, kids)
			| IR.S_GAssign(_, e) =>
			    doStms (stms, def, doExp def (e, used), depthMap, kids)
			| IR.S_IfThen(e, blk) => let
			    val (scope, depthMap) = doBlock (blk, def, depth+1, depthMap)
			    in
			      doStms (stms, def, doExp def (e, used), depthMap, scope::kids)
			    end
			| IR.S_IfThenElse(e, blk1, blk2) => let
			    val (scope1, depthMap) = doBlock (blk1, def, depth+1, depthMap)
			    val (scope2, depthMap) = doBlock (blk2, def, depth+1, depthMap)
			    in
			      doStms (stms, def, doExp def (e, used), depthMap, scope2::scope1::kids)
			    end
			| IR.S_For(x, lo, hi, blk) => let
			  (* NOTE: we handle variables bound in for loops as a special case,
			   * since they can be defined in the C++ for-loop syntax.
			   *)
			    val def' = S.add(def, x)
			    val depthMap = M.insert(depthMap, x, depth)
			    val (scope, depthMap) = doBlock (blk, def', depth+1, depthMap)
			    val used = let
				  val doExp = doExp def
				  in
				    doExp (hi, doExp (lo, used))
				  end
			    in
			      doStms (stms, def, used, depthMap, scope::kids)
			    end
			| IR.S_Foreach(x, e, blk) => let
			  (* NOTE: we handle variables bound in foreach loops as a special case,
			   * since they can be defined in the C++ for-loop syntax.
			   *)
			    val def' = S.add(def, x)
			    val depthMap = M.insert(depthMap, x, depth)
			    val (scope, depthMap) = doBlock (blk, def', depth+1, depthMap)
			    in
			      doStms (stms, def, doExp def (e, used), depthMap, scope::kids)
			    end
			| IR.S_LoadNrrd(x, _, _) =>
			    doStms (stms, def, S.add(used, x), depthMap, kids)
			| IR.S_Input(_, _, _, SOME e) =>
			    doStms (stms, def, doExp def (e, used), depthMap, kids)
			| IR.S_New(_, es) =>
			    doStms (stms, def, List.foldl (doExp def) used es, depthMap, kids)
			| IR.S_Save(_, e) =>
			    doStms (stms, def, doExp def (e, used), depthMap, kids)
			| IR.S_Print(_, es) =>
			    doStms (stms, def, List.foldl (doExp def) used es, depthMap, kids)
			| _ => doStms (stms, def, used, depthMap, kids)
		      (* end case *))
		and doExp def (e, used) = (case e
		       of IR.E_State(SOME e, _) => doExp def (e, used)
			| IR.E_Var x => if S.member(def, x) then used else S.add(used, x)
			| IR.E_Op(_, es) => List.foldl (doExp def) used es
			| IR.E_Vec(_, _, es) => List.foldl (doExp def) used es
			| IR.E_Cons(es, _) => List.foldl (doExp def) used es
			| IR.E_Seq(es, _) => List.foldl (doExp def) used es
			| IR.E_Pack(_, es) => List.foldl (doExp def) used es
			| IR.E_VLoad(_, e, _) => doExp def (e, used)
			| _ => used
		      (* end case *))
		in
		  doStms (body, def, S.empty, depthMap, [])
		end
	  in
	    doBlock (blk, def, 0, M.empty)
	  end

  (* walk the scope_nest tree and assign variables to blocks based on their minimum
   * reference depth.
   *)
    fun assignLocals (scope, depthMap) = let
	  fun assign (Scope{locals, used, inner}, depth) = let
		fun filter (x, xs) = (case M.find(depthMap, x)
		       of SOME d => if (d = depth) then x::xs else xs
			| NONE => raise Fail("no depth for " ^ TreeVar.toString x)
		      (* end case *))
		in
		  locals := S.foldl filter [] used;
		  List.app (fn s => assign(s, depth+1)) inner
		end
	  in
	    assign (scope, 0)
	  end

    fun assignScopes (params, blk) = (
	  assignLocals (buildScopeTree (S.fromList params, blk));
	  blk)

  end

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