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 4446 - (view) (download)

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

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