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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 3848, Thu May 12 14:30:19 2016 UTC revision 3849, Thu May 12 17:36:28 2016 UTC
# Line 9  Line 9 
9  structure ScopeVars : sig  structure ScopeVars : sig
10    
11    (* attach local variables to the innermost block that contains their scope *)    (* attach local variables to the innermost block that contains their scope *)
12      val assignScopes : TreeIR.block -> unit      val assignScopes : TreeIR.block -> TreeIR.block
13    
14    end = struct    end = struct
15    
16      val IR = TreeIR      structure IR = TreeIR
17      val S = TreeVar.Set      structure M = TreeVar.Map
18        structure S = TreeVar.Set
19    
20    (* a rose-tree representation of the nesting of blocks *)    (* a rose-tree representation of the nesting of blocks *)
21      datatype scope_nest = Scope of {      datatype scope_nest = Scope of {
22          blk : IR.block,                 (* the block in the IR *)          locals : IR.var list ref,       (* the block in the IR *)
23          used : S.set,                   (* the set of locals mentioned in the block, but not          used : S.set,                   (* the set of locals mentioned in the block, but not
24                                           * in sub-blocks)                                           * in sub-blocks
25                                           *)                                           *)
26          inner : scope_nest list         (* nested sub-blocks *)          inner : scope_nest list         (* nested sub-blocks *)
27        }        }
28    
29      fun assignScopes blk = let    (* build a scope_nest tree and comput a mapping from local variables to their minimum
30            fun doBlock (IR.Block{locals, stms}, def) = let     * binding depth.
31                  val     *)
32        fun buildScopeTree blk = let
33              fun recordDepth d (x, depthMap) = (case M.find(depthMap, x)
34                     of NONE => M.insert(depthMap, x, d)
35                      | SOME d' => if (d < d') then M.insert(depthMap, x, d) else depthMap
36                    (* end case *))
37              fun doBlock (IR.Block{locals, body}, depth, depthMap) = let
38                    fun doStms ([], used, depthMap, kids) = let
39                          val depthMap = S.foldl (recordDepth depth) depthMap used
40                          in
41                            (Scope{locals = locals, used = used, inner = kids}, depthMap)
42                          end
43                      | doStms (stm::stms, used, depthMap, kids) = (case stm
44                           of IR.S_Unpack(xs, e) =>
45                                doStms (stms, doExp(e, S.addList(used, xs)), depthMap, kids)
46                            | IR.S_Assign(x, e) =>
47                                doStms (stms, doExp(e, S.add(used, x)), depthMap, kids)
48                            | IR.S_MAssign(xs, e) =>
49                                doStms (stms, doExp(e, S.addList(used, xs)), depthMap, kids)
50                            | IR.S_GAssign(_, e) =>
51                                doStms (stms, doExp(e, used), depthMap, kids)
52                            | IR.S_IfThen(e, blk) => let
53                                val (scope, depthMap) = doBlock (blk, depth+1, depthMap)
54                  in                  in
55                                  doStms (stms, doExp(e, used), depthMap, scope::kids)
56                  end                  end
57                            | IR.S_IfThenElse(e, blk1, blk2) => let
58                                val (scope1, depthMap) = doBlock (blk1, depth+1, depthMap)
59                                val (scope2, depthMap) = doBlock (blk2, depth+1, depthMap)
60            in            in
61                                  doStms (stms, doExp(e, used), depthMap, scope2::scope1::kids)
62            end            end
63                            | IR.S_Foreach(x, e, blk) => let
64                              (* NOTE: we handle variables bound in for loops as a special case,
65                               * since they can be defined in the C++ for-loop syntax.
66                               *)
67                                val depthMap = M.insert(depthMap, x, depth)
68                                val (scope, depthMap) = doBlock (blk, depth+1, depthMap)
69                                in
70                                  doStms (stms, doExp(e, used), depthMap, scope::kids)
71                                end
72                            | IR.S_LoadNrrd(x, _) =>
73                                doStms (stms, S.add(used, x), depthMap, kids)
74                            | IR.S_Input(_, _, _, SOME e) =>
75                                doStms (stms, doExp(e, used), depthMap, kids)
76                            | IR.S_New(_, es) =>
77                                doStms (stms, List.foldl doExp used es, depthMap, kids)
78                            | IR.S_Save(_, e) =>
79                                doStms (stms, doExp(e, used), depthMap, kids)
80                            | IR.S_Print(_, es) =>
81                                doStms (stms, List.foldl doExp used es, depthMap, kids)
82                            | _ => doStms (stms, used, depthMap, kids)
83                          (* end case *))
84                    and doExp (e, used) = (case e
85                           of IR.E_State(SOME x, _) => S.add(used, x)
86                            | IR.E_Var x => S.add(used, x)
87                            | IR.E_Op(_, es) => List.foldl doExp used es
88                            | IR.E_Cons(es, _) => List.foldl doExp used es
89                            | IR.E_Seq(es, _) => List.foldl doExp used es
90                            | IR.E_Pack es => List.foldl doExp used es
91                            | IR.E_VLoad(_, e, _) => doExp (e, used)
92                            | _ => used
93                          (* end case *))
94                    in
95                      doStms (body, S.empty, depthMap, [])
96                    end
97              in
98                doBlock (blk, 0, M.empty)
99              end
100    
101      (* walk the scope_nest tree and assign variables to blocks based on their minimum
102       * reference depth.
103       *)
104        fun assignLocals (scope, depthMap) = let
105              fun assign (Scope{locals, used, inner}, depth) = let
106                    fun filter (x, xs) = (case M.find(depthMap, x)
107                           of SOME d => if (d = depth) then x::xs else xs
108                            | NONE => raise Fail("no depth for " ^ TreeVar.toString x)
109                          (* end case *))
110                    in
111                      locals := S.foldl filter [] used;
112                      List.app (fn s => assign(s, depth+1)) inner
113                    end
114              in
115                assign (scope, 0)
116              end
117    
118        fun assignScopes blk = (assignLocals (buildScopeTree blk); blk)
119    
120    end    end

Legend:
Removed from v.3848  
changed lines
  Added in v.3849

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