Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/compiler/CodeGen/cpscompile/memAliasing.sml
ViewVC logotype

Annotation of /sml/trunk/compiler/CodeGen/cpscompile/memAliasing.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5195 - (view) (download)

1 : jhr 4842 (* memAliasing.sml
2 :     *
3 :     * COPYRIGHT (c) 2018 The Fellowship of SML/NJ (http://www.smlnj.org)
4 :     * All rights reserved.
5 :     *
6 : monnier 409 * Perform memory aliasing analysis.
7 :     *
8 :     * The old memory disambiguation module discards aliasing information
9 :     * across CPS function boundaries, which made it not very useful for the
10 :     * optimizations I have in mind.
11 :     *
12 :     * This is an alternative module that (hopefully) does the right thing.
13 :     * The algorithm is inspired by Steensgaard's work on flow insensitive
14 :     * points-to analysis, but has been hacked to deal with target level issues.
15 :     *
16 :     * Some target level issues
17 :     * ------------------------
18 :     * In the source level two CPS allocations cannot be aliased by definition.
19 : jhr 4870 * When allocations are translated into target code, however, they become
20 : jhr 4446 * stores to fixed offsets from the heap pointer. Two allocation stores
21 : monnier 409 * that may write to the same offset are aliased. Allocation stores that are
22 :     * in disjoint program paths may be assigned the same heap allocation offset.
23 :     * We have to mark these as aliased since we want to allow speculative writes
24 :     * to the allocation space.
25 :     *
26 : jhr 4446 * Representing heap offsets
27 : monnier 409 * -------------------------
28 :     *
29 : jhr 4446 *
30 :     * Language
31 : monnier 409 * --------
32 :     * e ::= x <- v.i; k /* select */
33 :     * | x <- v+i; k /* offset */
34 :     * | x <- [v1,...vn]^hp; k /* record allocation at heap pointer hp */
35 :     * | x <- !v; k /* dereference */
36 :     * | v1 := v2; k /* update */
37 :     * | f(v1,...,vn) /* tail call */
38 :     *
39 : jhr 4446 * Since the analysis is flow insensitive, the branch constructs are
40 : monnier 409 * irrelevant.
41 :     *
42 :     * -- Allen
43 :     *)
44 :    
45 : jhr 5195 signature MEM_ALIASING = sig
46 : monnier 409
47 : jhr 5195 val analyze : CPS.function list -> (CPS.lvar -> CPSRegions.region)
48 : monnier 409
49 : jhr 5195 end
50 : monnier 409
51 : jhr 5195 functor MemAliasing (Cells : CELLS) : MEM_ALIASING =
52 :     struct
53 :     structure C = CPS
54 :     structure P = CPS.P
55 :     structure PT = PointsTo
56 : jhr 4316
57 : jhr 5195 fun error msg = MLRiscErrorMsg.error("MemAliasing",msg)
58 :    
59 :     val cellSz = Cells.cellSize
60 :     val cellShift = (case cellSz of 4 => 0w2 | 8 => 0w3)
61 :    
62 :     (*
63 :     * The following functions advance the heap pointer.
64 :     * These functions are highly dependent on the runtime system and
65 :     * how data structures are represented.
66 :     * IMPORTANT: we are assuming that the new array representation is used.
67 :     *)
68 :     fun recordSize (n, hp) = (n + 1) * cellSz + hp
69 :    
70 :     (* a record to hold n 64-bit floats; it needs to be 8-byte aligned on 32-bit systems. *)
71 : jhr 4842 (* REAL32: FIXME *)
72 : jhr 5195 val frecordSize = if (cellSz = 8)
73 :     then fn (n, hp) => hp + 8 * (n + 1)
74 :     else fn (n, hp) => (
75 :     if Word.andb(Word.fromInt hp, 0w4) <> 0w0
76 :     then hp + 8 * (n + 1)
77 :     else hp + 4 + 8 * n)
78 :    
79 :     (* vector is 3-word header object + data header + data *)
80 :     fun vectorSize (n, hp) = hp + cellSz * (n + 4)
81 :    
82 :     (* storage needed to wrap an integer or float *)
83 :     fun wrapSize (P.FLOAT 64, hp) = frecordSize(1, hp)
84 :     (* REAL32: FIXME *)
85 :     | wrapSize (P.INT sz, hp) =
86 :     if (sz <= Target.defaultIntSz)
87 :     then hp
88 : jhr 4842 (* NOTE: we might want padding for 64-bit ints on 32-bit machines in the future *)
89 : jhr 5195 else hp + cellSz * (1 + sz div Target.mlValueSz)
90 :     | wrapSize _ = error "wrapSize: bogus number kind"
91 : monnier 409
92 : jhr 5195 fun allocRecord (C.RK_RAW64BLOCK, vs, hp) = frecordSize(length vs, hp)
93 :     | allocRecord (C.RK_FCONT, vs, hp) = frecordSize(length vs, hp)
94 :     | allocRecord (C.RK_VECTOR, vs, hp) = vectorSize(length vs, hp)
95 :     | allocRecord (_, vs, hp) = recordSize(length vs, hp)
96 : monnier 409
97 : jhr 5195 val storeListSize = 2 * cellSz (* store-list elements *)
98 :     val array0Size = 5 * cellSz (* zero-length array *)
99 : monnier 409
100 : jhr 5195 exception NotFound
101 : monnier 409
102 : jhr 5195 val top = CPSRegions.memory
103 : leunga 590
104 : jhr 5195 (*
105 :     * Analyze a set of CPS functions
106 :     *)
107 :     fun analyze(cpsFunctions) = let
108 :     fun sizeOf (C.RECORD(rk,vs,x,k),hp) = sizeOf(k,allocRecord(rk,vs,hp))
109 :     | sizeOf (C.SELECT(off,v,x,cty,k),hp) = sizeOf(k,hp)
110 :     | sizeOf (C.OFFSET(off,v,x,k),hp) = sizeOf(k,hp)
111 :     | sizeOf (C.APP(f,vs),hp) = hp
112 :     | sizeOf (C.FIX _,hp) = error "sizeOf: FIX"
113 :     | sizeOf (C.SWITCH(v,x,ks),hp) = sizeOfs(ks,hp)
114 :     | sizeOf (C.BRANCH(p,_,x,k1,k2),hp) = Int.max(sizeOf(k1,hp),sizeOf(k2,hp))
115 :     | sizeOf (C.SETTER(P.ASSIGN,vs,k),hp) = sizeOf(k,hp+storeListSize)
116 :     | sizeOf (C.SETTER(P.UPDATE,vs,k),hp) = sizeOf(k,hp+storeListSize)
117 :     | sizeOf (C.SETTER(_,vs,k),hp) = sizeOf(k,hp)
118 :     | sizeOf (C.PURE(P.MKSPECIAL,vs,x,cty,k),hp) = sizeOf(k, hp + 2*cellSz)
119 :     | sizeOf (C.PURE(P.MAKEREF,vs,x,cty,k),hp) = sizeOf(k, hp + 2*cellSz)
120 :     | sizeOf (C.PURE(P.WRAP kind, _, _, _, k), hp) = sizeOf(k, wrapSize(kind, hp))
121 :     | sizeOf (C.PURE(P.NEWARRAY0,vs,x,cty,k),hp) = sizeOf(k,hp+array0Size)
122 :     | sizeOf (C.PURE(p,vs,x,cty,k),hp) = sizeOf(k,hp)
123 :     | sizeOf (C.ARITH(a,vs,x,cty,k),hp) = sizeOf(k,hp)
124 :     | sizeOf (C.LOOKER(lk,vs,x,cty,k),hp) = sizeOf(k,hp)
125 :     | sizeOf (C.RCC(_,_,_,_,_,k),hp) = sizeOf(k,hp)
126 : jhr 4446
127 : jhr 5195 and sizeOfs ([],hp) = hp
128 :     | sizeOfs (k::ks,hp) = Int.max(sizeOf(k,hp),sizeOfs(ks,hp))
129 : monnier 409
130 : jhr 5195 val locMap = IntHashTable.mkTable(37, NotFound) (* lvar -> loc *)
131 :     val look = IntHashTable.lookup locMap
132 :     val find = IntHashTable.find locMap
133 :     val bind = IntHashTable.insert locMap
134 : monnier 409
135 : jhr 5195 val newMem = Cells.newCell CellsBasis.MEM
136 : monnier 409
137 : jhr 5195 val _ = PT.reset newMem
138 : monnier 409
139 : jhr 5195 fun newRef _ = ref(PT.SCELL(newMem(),ref []))
140 : leunga 585
141 : jhr 5195 val exnptr = PT.newSRef() (* exception handler *)
142 :     val varptr = PT.newSRef() (* var ptr *)
143 : leunga 585
144 : jhr 5195 fun lookup x = (case find x
145 :     of SOME r => r
146 :     | NONE => let val r = newRef() in bind(x,r); r end
147 :     (* end case *))
148 : monnier 409
149 : jhr 5195 fun defineFunction (fk, f, args, _, cexp) = let
150 :     val xs = map (fn x => let val r = newRef() in bind(x,r); r end) args
151 :     in
152 :     bind(f, PT.mkLambda xs)
153 :     end
154 : jhr 4446
155 : jhr 5195 val off0 = C.OFFp 0
156 : leunga 585
157 : jhr 5195 fun process(fk, f, args, _, cexp) = let
158 :     (* create a table of allocation offset locations *)
159 :     val table = Array.tabulate(sizeOf(cexp, 0) div 4, newRef)
160 : leunga 585
161 : jhr 5195 fun select (i,C.VAR v,x) = bind(x,PT.pi(lookup v,i))
162 :     | select (i,_,x) = ()
163 : monnier 409
164 : jhr 5195 fun offset (i,C.VAR v,x) = bind(x,PT.offset(lookup v,i))
165 :     | offset (i,_,x) = ()
166 : monnier 409
167 : jhr 5195 fun value (C.VAR v) = lookup v
168 :     | value _ = newRef()
169 : monnier 409
170 : jhr 5195 fun apply (C.VAR f,args) = PT.app(lookup f,map value args)
171 :     | apply _ = ()
172 : monnier 409
173 : jhr 5195 fun getPath (v,C.OFFp 0) = value v
174 :     | getPath (v,C.OFFp n) = PT.offset(value v, n)
175 :     | getPath (v,C.SELp(n,path)) = PT.pi(getPath(v,path),n)
176 : monnier 409
177 : jhr 5195 fun getPaths ([],hp) = []
178 :     | getPaths ((v,path)::vs,hp) = let
179 :     val r = Array.sub(table,hp)
180 :     val r' = getPath(v,path)
181 :     in
182 :     PT.unify(r,r'); r::getPaths(vs,hp+1)
183 :     end
184 : monnier 409
185 : jhr 5195 fun getF64Paths ([],hp) = []
186 :     | getF64Paths ((v,path)::vs,hp) = let
187 :     val r1 = Array.sub(table,hp)
188 :     val r2 = Array.sub(table,hp+1)
189 :     val r' = getPath(v,path)
190 :     in
191 :     PT.unify(r1,r'); PT.unify(r2,r');
192 :     r'::getF64Paths(vs,hp+2)
193 :     end
194 : monnier 409
195 : jhr 5195 (* How to make a record *)
196 :     fun mkRec (f,getPaths,x,vs,hp) = let
197 :     val i = Word.toInt(Word.>>(Word.fromInt hp,cellShift))
198 :     val r = f(SOME(Array.sub(table,i)),getPaths(vs,i+1))
199 :     in
200 :     bind(x,r)
201 :     end
202 :     fun mkFRecord (x,vs,hp) = mkRec(PT.mkRecord,getF64Paths,x,vs,hp)
203 :     fun mkVector (x,vs,hp) = mkRec(PT.mkRecord,getPaths,x,vs,hp)
204 :     fun mkNormalRecord (x,vs,hp) = mkRec(PT.mkRecord,getPaths,x,vs,hp)
205 : monnier 409
206 : jhr 5195 fun mkRecord (C.RK_RAW64BLOCK,x,vs,hp) = mkFRecord(x,vs,hp)
207 :     | mkRecord (C.RK_FCONT,x,vs,hp) = mkFRecord(x,vs,hp)
208 :     | mkRecord (C.RK_VECTOR,x,vs,hp) = mkVector(x,vs,hp)
209 :     | mkRecord (_,x,vs,hp) = mkNormalRecord(x,vs,hp)
210 : leunga 585
211 : jhr 5195 fun makeTop m = (PT.unify(m, top); top)
212 : leunga 585
213 : jhr 5195 (* CPS Pure Primitives *)
214 :     fun arrayptr v = PT.pi(value v, 0)
215 : leunga 590
216 : jhr 5195 fun mkspecial (x,v,hp) = mkNormalRecord(x,[(v,off0)],hp)
217 :     fun mkWrap (P.FLOAT 64, x, v, hp) = mkFRecord(x, [(v, off0)], hp)
218 :     | mkWrap (P.INT sz, x, v, hp) = if (sz <= Target.defaultIntSz)
219 :     then ()
220 :     else mkNormalRecord(x, [(v, off0)], hp)
221 :     | mkWrap _ = error "mkWrap: bogus number kind"
222 :     fun makeref (x,v,hp) = mkNormalRecord(x,[(v,off0)],hp)
223 :     fun newarray0 (x,hp) =
224 :     bind(x,PT.mkRecord(NONE,[PT.mkRecord(NONE,[])]))
225 : leunga 585
226 : jhr 5195 fun objlength (x,v) = bind(x, PT.pi(value v, ~1))
227 :     fun length (x,v) = bind(x, PT.pi(value v, 1))
228 :     fun arraysub (x,a,i) = makeTop(PT.weakSubscript(arrayptr a))
229 :     fun subscriptv (x,a,i) = arraysub(x,a,i)
230 :     fun subscript (x,a,i) = arraysub(x,a,i)
231 :     fun pure_numsubscript (x,a,i) = arraysub(x,a,i)
232 :     fun gettag (x,v) = bind(x,PT.pi(value v, ~1))
233 :     fun numsubscript8 (x,a,i) = arraysub(x,a,i)
234 :     fun numsubscriptf64 (x,a,i) = arraysub(x,a,i)
235 :     fun getcon (x,v) = bind(x, PT.pi(value v,0))
236 :     fun getexn (x,v) = bind(x, PT.pi(value v,0))
237 :     fun recsubscript (x,a,i) = arraysub(x,a,i)
238 :     fun raw64subscript (x,a,i) = arraysub(x,a,i)
239 : leunga 585
240 : jhr 5195 (* CPS Looker Primitives *)
241 :     fun deref (x,v) = makeTop(PT.strongSubscript(value v, 0))
242 :     fun gethdlr x = bind(x, PT.strongSubscript(exnptr, 0))
243 :     fun getvar x = bind(x, PT.strongSubscript(varptr, 0))
244 : leunga 585
245 : jhr 5195 (* CPS Setter Primitives *)
246 :     fun supdate (a,x) = PT.strongUpdate(value a, 0, makeTop(value x))
247 :     fun wupdate (a,x) = PT.weakUpdate(value a, makeTop(value x))
248 : leunga 585
249 : jhr 5195 fun arrayupdate (a,i,x) = PT.weakUpdate(arrayptr a,value x)
250 : leunga 585
251 : jhr 5195 fun assign (a,x) = supdate(a,x)
252 :     fun unboxedassign (a,x) = supdate(a,x)
253 :     fun update (a,i,x) = arrayupdate(a,i,x)
254 :     fun unboxedupdate (a,i,x) = arrayupdate(a,i,x)
255 :     fun numupdate (a,i,x) = arrayupdate(a,i,x)
256 :     fun numupdateF64 (a,i,x) = arrayupdate(a,i,x)
257 :     fun sethdlr x = PT.strongUpdate(exnptr, 0, value x)
258 :     fun setvar x = PT.strongUpdate(varptr, 0, value x)
259 : leunga 590
260 : jhr 5195 (* I don't know whether the following makes any sense...
261 :     * Basically, I want to ignore this aliasing analysis
262 :     * as far as raw access is concerned. (The invariant is
263 :     * that raw access NEVER occurs to any memory location
264 :     * that ML "knows" about. -- Blume (2000/1/1) *)
265 :     fun rawstore (a, x) = ()
266 :     fun rawload (a, x) = top
267 : leunga 585
268 : jhr 5195 fun infer (C.RECORD(rk,vs,x,k),hp) =
269 :     (mkRecord(rk,x,vs,hp); infer(k,allocRecord(rk,vs,hp)))
270 :     | infer (C.SELECT(i,v,x,cty,k),hp) = (select(i,v,x); infer(k,hp))
271 :     | infer (C.OFFSET(i,v,x,k),hp) = (offset(i,v,x); infer(k,hp))
272 :     | infer (C.APP(f,vs),hp) = apply(f,vs)
273 :     | infer (C.FIX _,hp) = error "infer: FIX"
274 :     | infer (C.SWITCH(v,x,ks),hp) = infers(ks,hp)
275 :     | infer (C.BRANCH(p,_,x,k1,k2),hp) = (infer(k1,hp); infer(k2,hp))
276 :     (*
277 :     * These things are misnamed! There is nothing pure about them!
278 :     *)
279 :     | infer (C.PURE(P.OBJLENGTH, [v], x, _, k), hp) =
280 :     (objlength(x, v); infer(k, hp))
281 :     | infer (C.PURE(P.LENGTH, [v], x, _, k), hp) =
282 :     (length(x, v); infer(k, hp))
283 :     | infer (C.PURE(P.SUBSCRIPTV,[a,i],x,_,k),hp) =
284 :     (subscriptv(x, a, i); infer(k, hp))
285 :     | infer (C.PURE(P.PURE_NUMSUBSCRIPT{kind=P.INT 8},[a,i],x,_,k),hp) =
286 :     (pure_numsubscript(x, a, i); infer(k, hp))
287 :     | infer (C.PURE(P.GETTAG, [v], x, _, k), hp) =
288 :     (gettag(x, v); infer(k, hp))
289 :     | infer (C.PURE(P.MKSPECIAL,[i,v],x,cty,k),hp) =
290 :     (mkspecial(x,v,hp); infer(k,hp+8))
291 :     | infer (C.PURE(P.MAKEREF,[v],x,cty,k),hp) =
292 :     (makeref(x,v,hp); infer(k,hp+8))
293 :     | infer (C.PURE(P.WRAP kind, [v], x, cty, k), hp) = (
294 :     mkWrap(kind, x, v, hp);
295 :     infer(k, wrapSize(kind, hp)))
296 :     | infer (C.PURE(P.GETCON,[v],x,_,k), hp) =
297 :     (getcon(x, v); infer(k, hp))
298 :     | infer (C.PURE(P.GETEXN,[v],x,_,k), hp) =
299 :     (getexn(x, v); infer(k, hp))
300 :     | infer (C.PURE(P.RECSUBSCRIPT,[a,i],x,_,k), hp) =
301 :     (recsubscript(x,a,i); infer(k, hp))
302 :     | infer (C.PURE(P.RAW64SUBSCRIPT,[a,i],x,_,k), hp) =
303 :     (raw64subscript(x,a,i); infer(k, hp))
304 :     | infer (C.PURE(P.NEWARRAY0,_,x,cty,k),hp) =
305 :     (newarray0(x,hp); infer(k,hp+array0Size))
306 :     | infer (C.PURE(p,vs,x,cty,k),hp) = infer(k,hp)
307 : blume 772
308 : jhr 5195 | infer (C.ARITH(a,vs,x,cty,k),hp) = infer(k,hp)
309 : leunga 585
310 : jhr 5195 (* Lookers *)
311 :     | infer (C.LOOKER(P.DEREF,[v],x,_,k),hp) = (deref(x,v); infer(k,hp))
312 :     | infer (C.LOOKER(P.GETHDLR,[],x,_,k),hp) = (gethdlr x; infer(k,hp))
313 :     | infer (C.LOOKER(P.SUBSCRIPT,[a,i],x,_,k),hp) =
314 :     (subscript(x,a,i); infer(k,hp))
315 :     | infer (C.LOOKER(P.NUMSUBSCRIPT{kind=P.INT 8},[a,i],x,_,k),hp) =
316 :     (numsubscript8(x,a,i); infer(k,hp))
317 :     | infer (C.LOOKER(P.NUMSUBSCRIPT{kind=P.FLOAT 64},[a,i],x,_,k),hp) =
318 :     (numsubscriptf64(x,a,i); infer(k,hp))
319 : leunga 585
320 : jhr 5195 | infer (C.LOOKER(P.GETVAR,[],x,_,k),hp) = (getvar x; infer(k,hp))
321 : monnier 409
322 : jhr 5195 | infer (C.LOOKER (P.RAWLOAD _, [a], x, _, k), hp) =
323 :     (rawload (x, a); infer(k,hp))
324 : leunga 585
325 : jhr 5195 (* Setters *)
326 :     | infer (C.SETTER(P.ASSIGN, [a,v], k),hp) =
327 :     (assign(a,v); infer(k,hp+storeListSize))
328 :     | infer (C.SETTER(P.UNBOXEDASSIGN, [a,v], k),hp) =
329 :     (unboxedassign(a,v); infer(k,hp))
330 :     | infer (C.SETTER(P.UPDATE, [a,i,v], k),hp) =
331 :     (update(a,i,v); infer(k,hp+storeListSize))
332 :     | infer (C.SETTER(P.UNBOXEDUPDATE, [a,i,v], k), hp) =
333 :     (unboxedupdate(a,i,v); infer(k,hp))
334 :     | infer (C.SETTER(P.NUMUPDATE{kind=P.INT _}, [a,i,v], k),hp) =
335 :     (numupdate(a,i,v); infer(k,hp))
336 :     | infer (C.SETTER(P.NUMUPDATE{kind=P.FLOAT 64}, [a,i,v], k),hp) = (* REAL32: FIXME *)
337 :     (numupdateF64(a,i,v); infer(k,hp))
338 : leunga 585
339 : jhr 5195 | infer (C.SETTER(P.SETHDLR, [x], k), hp) = (sethdlr x; infer(k,hp))
340 :     | infer (C.SETTER(P.SETVAR, [x], k), hp) = (setvar x; infer(k,hp))
341 :     | infer (C.SETTER (P.RAWSTORE _, [a, x], k), hp) =
342 :     (rawstore (a, x); infer (k, hp))
343 : blume 772
344 : jhr 5195 | infer (e, hp) =
345 :     (PPCps.prcps e; print "\n"; error "infer")
346 : leunga 585
347 : jhr 5195 and infers ([],hp) = ()
348 :     | infers (k::ks,hp) = (infer(k,hp); infers(ks,hp))
349 :     in
350 :     infer (cexp, 0)
351 :     end (* process *)
352 : leunga 585
353 : jhr 5195 in
354 :     (* NOTE: the default for this flag is currently false *)
355 :     if !Control.CG.memDisambiguate
356 :     then (
357 :     CPSRegions.reset();
358 :     app defineFunction cpsFunctions;
359 :     app process cpsFunctions;
360 :     fn r => look r handle _ => top)
361 :     else (fn _ => top)
362 :     end
363 : jhr 4446
364 : jhr 5195 end

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