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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5286 - (view) (download)

1 : jhr 3847 (* scope-vars.sml
2 :     *
3 :     * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     *
5 :     * COPYRIGHT (c) 2016 The University of Chicago
6 :     * All rights reserved.
7 :     *)
8 :    
9 :     structure ScopeVars : sig
10 :    
11 :     (* attach local variables to the innermost block that contains their scope *)
12 : jhr 3857 val assignScopes : TreeVar.t list * TreeIR.block -> TreeIR.block
13 : jhr 3847
14 :     end = struct
15 :    
16 : jhr 3849 structure IR = TreeIR
17 :     structure M = TreeVar.Map
18 :     structure S = TreeVar.Set
19 : jhr 3847
20 : jhr 4204 (* representation of a nesting depth: a pair of the depth and a path to the root.
21 :     * For D(d, p), we have d = length p.
22 :     *)
23 :     datatype depth_path = D of int * int list
24 :    
25 : jhr 3847 (* a rose-tree representation of the nesting of blocks *)
26 :     datatype scope_nest = Scope of {
27 : jhr 4317 depth : depth_path, (* depth path for the block *)
28 :     locals : IR.var list ref, (* the block in the IR *)
29 :     used : S.set, (* the set of locals mentioned in the block, but not
30 :     * in sub-blocks
31 :     *)
32 :     inner : scope_nest list (* nested sub-blocks *)
33 : jhr 3847 }
34 :    
35 : jhr 4204 fun mergeDepth (D(d1, p1), D(d2, p2)) = let
36 : jhr 4317 fun merge (_, [], []) = D(0, [])
37 :     | merge (d, p as n1::p1, n2::p2) = if (n1 = n2)
38 :     then D(d, p)
39 :     else merge (d-1, p1, p2)
40 :     in
41 :     case Int.compare(d1, d2)
42 :     of LESS => merge(d1, p1, List.drop(p2, d2-d1))
43 :     | EQUAL => merge(d1, p1, p2)
44 :     | GREATER => merge(d2, List.drop(p1, d1-d2), p2)
45 :     (* end case *)
46 :     end
47 : jhr 4204
48 : jhr 4088 (* build a scope_nest tree and compute a mapping from local variables to their minimum
49 : jhr 3849 * binding depth.
50 :     *)
51 : jhr 3857 fun buildScopeTree (def, blk) = let
52 : jhr 4317 val id = ref 0
53 :     fun pushScope (D(d, p)) = let
54 :     val n = !id
55 :     in
56 :     id := n+1; D(d+1, n::p)
57 :     end
58 :     fun recordDepth d (x, depthMap) = (case M.find(depthMap, x)
59 :     of NONE => M.insert(depthMap, x, d)
60 :     | SOME d' => M.insert(depthMap, x, mergeDepth(d, d'))
61 :     (* end case *))
62 :     fun doBlock (IR.Block{locals, body}, def, depth : depth_path, depthMap) = let
63 :     fun doStms ([], def, used, depthMap, kids) = let
64 :     val depthMap = S.foldl (recordDepth depth) depthMap used
65 :     in
66 :     (Scope{depth = depth, locals = locals, used = used, inner = kids}, depthMap)
67 :     end
68 :     | doStms (stm::stms, def, used, depthMap, kids) = (case stm
69 :     of IR.S_Assign(true, x, e) => let
70 :     val depthMap = recordDepth depth (x, depthMap)
71 :     in
72 :     doStms (stms, S.add(def, x), doExp def (e, used), depthMap, kids)
73 :     end
74 :     | IR.S_Assign(false, x, e) =>
75 :     doStms (stms, def, doExp def (e, S.add(used, x)), depthMap, kids)
76 :     | IR.S_MAssign(xs, e) => let
77 :     val depthMap = List.foldl (recordDepth depth) depthMap xs
78 :     in
79 :     doStms (stms, S.addList(def, xs),
80 :     doExp def (e, S.addList(used, xs)), depthMap, kids)
81 :     end
82 :     | IR.S_GAssign(_, e) =>
83 :     doStms (stms, def, doExp def (e, used), depthMap, kids)
84 :     | IR.S_IfThen(e, blk) => let
85 :     val (scope, depthMap) = doBlock (blk, def, pushScope depth, depthMap)
86 :     in
87 :     doStms (stms, def, doExp def (e, used), depthMap, scope::kids)
88 :     end
89 :     | IR.S_IfThenElse(e, blk1, blk2) => let
90 :     val (scope1, depthMap) = doBlock (blk1, def, pushScope depth, depthMap)
91 :     val (scope2, depthMap) = doBlock (blk2, def, pushScope depth, depthMap)
92 :     in
93 :     doStms (stms, def, doExp def (e, used), depthMap, scope2::scope1::kids)
94 :     end
95 :     | IR.S_For(x, lo, hi, blk) => let
96 :     (* NOTE: we handle variables bound in for loops as a special case,
97 :     * since they can be defined in the C++ for-loop syntax.
98 :     *)
99 :     val def' = S.add(def, x)
100 :     val depthMap = M.insert(depthMap, x, depth)
101 :     val (scope, depthMap) = doBlock (blk, def', pushScope depth, depthMap)
102 :     val used = let
103 :     val doExp = doExp def
104 :     in
105 :     doExp (hi, doExp (lo, used))
106 :     end
107 :     in
108 :     doStms (stms, def, used, depthMap, scope::kids)
109 :     end
110 :     | IR.S_Foreach(x, e, blk) => let
111 :     (* NOTE: we handle variables bound in foreach loops as a special case,
112 :     * since they can be defined in the C++ for-loop syntax.
113 :     *)
114 :     val def' = S.add(def, x)
115 :     val depthMap = M.insert(depthMap, x, depth)
116 :     val (scope, depthMap) = doBlock (blk, def', pushScope depth, depthMap)
117 :     in
118 :     doStms (stms, def, doExp def (e, used), depthMap, scope::kids)
119 :     end
120 : jhr 5215 | IR.S_MapReduce(mrs, src) => let
121 :     fun doMR ([], xs, used) = (xs, used)
122 :     | doMR (IR.MapReduce(x, _, _, es, _) :: mrr, xs, used) =
123 :     doMR (mrr, x::xs, List.foldl (doExp def) used es)
124 :     val (xs, used) = doMR (mrs, [], used)
125 :     val (def, depthMap) = List.foldl
126 :     (fn (x, (def, dm)) => (S.add(def, x), M.insert(dm, x, depth)))
127 :     (def, depthMap) xs
128 :     in
129 :     doStms (stms, def, S.add(used, src), depthMap, kids)
130 :     end
131 : jhr 5184 | IR.S_LoadNrrd(x, _, _, _) =>
132 : jhr 4317 doStms (stms, def, S.add(used, x), depthMap, kids)
133 :     | IR.S_Input(_, _, _, SOME e) =>
134 :     doStms (stms, def, doExp def (e, used), depthMap, kids)
135 :     | IR.S_New(_, es) =>
136 :     doStms (stms, def, List.foldl (doExp def) used es, depthMap, kids)
137 :     | IR.S_Save(_, e) =>
138 :     doStms (stms, def, doExp def (e, used), depthMap, kids)
139 :     | IR.S_Print(_, es) =>
140 :     doStms (stms, def, List.foldl (doExp def) used es, depthMap, kids)
141 : jhr 5286 | IR.S_Return(SOME e) =>
142 : jhr 4317 doStms (stms, def, doExp def (e, used), depthMap, kids)
143 :     | _ => doStms (stms, def, used, depthMap, kids)
144 :     (* end case *))
145 :     and doExp def (e, used) = (case e
146 :     of IR.E_State(SOME e, _) => doExp def (e, used)
147 :     | IR.E_Var x => if S.member(def, x) then used else S.add(used, x)
148 :     | IR.E_Op(_, es) => List.foldl (doExp def) used es
149 :     | IR.E_Apply(_, es) => List.foldl (doExp def) used es
150 :     | IR.E_Vec(_, _, es) => List.foldl (doExp def) used es
151 :     | IR.E_Cons(es, _) => List.foldl (doExp def) used es
152 :     | IR.E_Seq(es, _) => List.foldl (doExp def) used es
153 :     | IR.E_Pack(_, es) => List.foldl (doExp def) used es
154 :     | IR.E_VLoad(_, e, _) => doExp def (e, used)
155 :     | _ => used
156 :     (* end case *))
157 :     in
158 :     doStms (body, def, S.empty, depthMap, [])
159 :     end
160 :     in
161 :     doBlock (blk, def, D(0, []), M.empty)
162 :     end
163 : jhr 3847
164 : jhr 4204 fun matchDepth (D(0, _), D(0, _)) = true
165 :     | matchDepth (D(d1, p1), D(d2, p2)) = (d1 = d2) andalso (hd p1 = hd p2)
166 :    
167 : jhr 3849 (* walk the scope_nest tree and assign variables to blocks based on their minimum
168 :     * reference depth.
169 :     *)
170 :     fun assignLocals (scope, depthMap) = let
171 : jhr 4317 fun assign (Scope{depth, locals, used, inner}) = let
172 :     (* process a nested scope, which returns a list of the used variables that were
173 :     * not bound in the nested scope. We add these to the used variables in this
174 :     * scope.
175 :     *)
176 :     val used = let
177 :     fun doKid (kid, used) = S.union(used, assign kid)
178 :     in
179 :     List.foldl doKid used inner
180 :     end
181 :     (* partition the used variables into those that should be bound at this depth
182 :     * and those that should be bound at an outer scope.
183 :     *)
184 :     val (locs, notBound) = let
185 :     fun partition (x, (locs, nBnd)) = (case M.find(depthMap, x)
186 :     of SOME d => if matchDepth(d, depth)
187 :     then (x::locs, nBnd)
188 :     else (locs, S.add(nBnd, x))
189 :     | NONE => raise Fail("no depth for " ^ TreeVar.toString x)
190 :     (* end case *))
191 :     in
192 :     S.foldl partition ([], S.empty) used
193 :     end
194 :     in
195 :     locals := locs;
196 :     notBound
197 :     end
198 :     in
199 :     ignore (assign scope)
200 :     end
201 : jhr 3849
202 : jhr 3857 fun assignScopes (params, blk) = (
203 : jhr 4317 assignLocals (buildScopeTree (S.fromList params, blk));
204 :     blk)
205 : jhr 3849
206 : jhr 3847 end

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