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

# SCM Repository

[smlnj] Diff of /sml/trunk/compiler/CodeGen/cpscompile/memAliasing.sml
 [smlnj] / sml / trunk / compiler / CodeGen / cpscompile / memAliasing.sml

# Diff of /sml/trunk/compiler/CodeGen/cpscompile/memAliasing.sml

revision 584, Mon Mar 27 09:55:55 2000 UTC revision 585, Wed Mar 29 23:55:35 2000 UTC
# Line 40  Line 40
40
41  signature MEM_ALIASING =  signature MEM_ALIASING =
42  sig  sig
43     val analyze : CPS.function list -> (CPS.lvar -> PointsTo.loc)     val analyze : CPS.function list -> (CPS.lvar -> CPSRegions.region)
44  end  end
45
46  functor MemAliasing(Cells : CELLS) : MEM_ALIASING =  functor MemAliasing(Cells : CELLS) : MEM_ALIASING =
# Line 57  Line 57
57      * how data structures are represented.      * how data structures are represented.
58      * IMPORTANT: we are assuming that the new array representation is used.      * IMPORTANT: we are assuming that the new array representation is used.
59      *)      *)
60     fun record(n,hp)  =  n * 4 + 4 + hp     fun recordSize(n,hp)  =  n * 4 + 4 + hp
61     fun frecord(n,hp) =     fun frecordSize(n,hp) =
62         let val hp = if Word.andb(Word.fromInt hp,0w4) <> 0w0 then hp+8 else hp+4         let val hp = if Word.andb(Word.fromInt hp,0w4) <> 0w0 then hp+8 else hp+4
63         in  8*n + hp end         in  8*n + hp end
64     fun vector(n,hp) = n * 4 + 16 + hp     fun vectorSize(n,hp) = n * 4 + 16 + hp
65
66     fun allocRecord(C.RK_FBLOCK,vs,hp) = frecord(length vs,hp)     fun allocRecord(C.RK_FBLOCK,vs,hp) = frecordSize(length vs,hp)
67       | allocRecord(C.RK_FCONT,vs,hp) = frecord(length vs,hp)       | allocRecord(C.RK_FCONT,vs,hp)  = frecordSize(length vs,hp)
68       | allocRecord(C.RK_VECTOR,vs,hp) = vector(length vs,hp)       | allocRecord(C.RK_VECTOR,vs,hp) = vectorSize(length vs,hp)
69       | allocRecord(_,vs,hp) = record(length vs,hp)       | allocRecord(_,vs,hp) = recordSize(length vs,hp)
70
71     val storeListSize = 8     val storeListSize = 8
72     val array0Size    = 20     val array0Size    = 20
# Line 85  Line 85
85           | sizeOf(C.SWITCH(v,x,ks),hp) = sizeOfs(ks,hp)           | sizeOf(C.SWITCH(v,x,ks),hp) = sizeOfs(ks,hp)
86           | sizeOf(C.BRANCH(p,_,x,k1,k2),hp) =           | sizeOf(C.BRANCH(p,_,x,k1,k2),hp) =
87               Int.max(sizeOf(k1,hp),sizeOf(k2,hp))               Int.max(sizeOf(k1,hp),sizeOf(k2,hp))
88             | sizeOf(C.SETTER(P.assign,vs,k),hp) = sizeOf(k,hp+storeListSize)
89           | sizeOf(C.SETTER(P.update,vs,k),hp) = sizeOf(k,hp+storeListSize)           | sizeOf(C.SETTER(P.update,vs,k),hp) = sizeOf(k,hp+storeListSize)
90           | sizeOf(C.SETTER(P.boxedupdate,vs,k),hp) = sizeOf(k,hp+storeListSize)           | sizeOf(C.SETTER(P.boxedupdate,vs,k),hp) = sizeOf(k,hp+storeListSize)
91           | sizeOf(C.SETTER(_,vs,k),hp) = sizeOf(k,hp)           | sizeOf(C.SETTER(_,vs,k),hp) = sizeOf(k,hp)
92           | sizeOf(C.PURE(P.fwrap,vs,x,cty,k),hp) = sizeOf(k,frecord(1,hp))           | sizeOf(C.PURE(P.fwrap,vs,x,cty,k),hp) = sizeOf(k,frecordSize(1,hp))
93           | sizeOf(C.PURE(P.mkspecial,vs,x,cty,k),hp) = sizeOf(k,hp+8)           | sizeOf(C.PURE(P.mkspecial,vs,x,cty,k),hp) = sizeOf(k,hp+8)
94           | sizeOf(C.PURE(P.makeref,vs,x,cty,k),hp) = sizeOf(k,hp+8)           | sizeOf(C.PURE(P.makeref,vs,x,cty,k),hp) = sizeOf(k,hp+8)
95           | sizeOf(C.PURE(P.i32wrap,vs,x,cty,k),hp) = sizeOf(k,hp+8)           | sizeOf(C.PURE(P.i32wrap,vs,x,cty,k),hp) = sizeOf(k,hp+8)
# Line 106  Line 107
107
108         val newMem = Cells.newCell Cells.MEM         val newMem = Cells.newCell Cells.MEM
109
110         fun newRef _ = ref(PT.REF(newMem(),ref []))         val _      = PT.reset newMem
111
112           fun newRef _ = ref(PT.SCELL(newMem(),ref []))
113
114           val exnptr = PT.newSRef() (* exception handler *)
115           val varptr = PT.newSRef() (* var ptr *)
116
117         fun lookup x =         fun lookup x =
118             look x handle _ =>             look x handle _ =>
119             let val l = newRef() in bind(x,l); l end             let val r = newRef() in bind(x,r); r end
120
fun process(fk, f, args, _, cexp) =
let (* process function f *)
val argLocs = map (fn x => let val l = newRef() in bind(x,l); l end)
args
val _ = PT.app(lookup f,argLocs)
121
122             (* create a table of allocation offset locations *)         fun defineFunction(fk, f, args, _, cexp) =
123               let val xs =
124                    map (fn x => let val r = newRef() in bind(x,r); r end) args
125               in  bind(f, PT.mkLambda xs) end
126
127           val off0 = C.OFFp 0
128
129           fun process(fk, f, args, _, cexp) =
130           let (* create a table of allocation offset locations *)
131             val table = Array.tabulate(sizeOf(cexp, 0) div 4, newRef)             val table = Array.tabulate(sizeOf(cexp, 0) div 4, newRef)
132
133             fun select(i,C.VAR v,x) = bind(x,PT.pi(lookup v,i))             fun select(i,C.VAR v,x) = bind(x,PT.pi(lookup v,i))
# Line 133  Line 142
142             fun apply(C.VAR f,args) = PT.app(lookup f,map value args)             fun apply(C.VAR f,args) = PT.app(lookup f,map value args)
143               | apply _             = ()               | apply _             = ()
144
145             fun mkrecord(x,vs,hp) =             fun getPath(v,C.OFFp 0) = value v
146             let fun g([],i)           = []               | getPath(v,C.OFFp n) = PT.offset(value v, n)
147                   | g((v,path)::vs,i) =               | getPath(v,C.SELp(n,path)) = PT.pi(getPath(v,path),n)
148                     let val l  = Array.sub(table,i)
149                         val l' = get(v,path)             fun getPaths([],hp) = []
150                     in  PT.unify(l,l'); l::g(vs,i+1) end               | getPaths((v,path)::vs,hp) =
151                   let val r  = Array.sub(table,hp)
152                 and get(v,C.OFFp 0) = value v                     val r' = getPath(v,path)
153                   | get(v,C.OFFp n) = PT.offset(value v,n)                 in  PT.unify(r,r'); r::getPaths(vs,hp+1) end
154                   | get(v,C.SELp(n,path)) = PT.pi(get(v,path),n)
155               fun getF64Paths([],hp) = []
156                 val i = Word.toInt(Word.>>(Word.fromInt hp,0w2))               | getF64Paths((v,path)::vs,hp) =
157                 val r = PT.record(Array.sub(table,i)::g(vs,i+1))                 let val r1  = Array.sub(table,hp)
158             in  bind(x,r)                     val r2  = Array.sub(table,hp+1)
159                       val r'  = getPath(v,path)
160                   in  PT.unify(r1,r'); PT.unify(r2,r');
161                       r'::getF64Paths(vs,hp+2)
162             end             end
163
164               (* How to make a record *)
165               fun mkRec(f,getPaths,x,vs,hp) =
166                   let val i = Word.toInt(Word.>>(Word.fromInt hp,0w2))
167                       val r = f(SOME(Array.sub(table,i)),getPaths(vs,i+1))
168                   in  bind(x,r) end
169               fun mkFRecord(x,vs,hp) = mkRec(PT.mkRecord,getF64Paths,x,vs,hp)
170               fun mkVector(x,vs,hp) = mkRec(PT.mkRecord,getPaths,x,vs,hp)
171               fun mkNormalRecord(x,vs,hp) = mkRec(PT.mkRecord,getPaths,x,vs,hp)
172
173               fun mkRecord(C.RK_FBLOCK,x,vs,hp) = mkFRecord(x,vs,hp)
174                 | mkRecord(C.RK_FCONT,x,vs,hp) = mkFRecord(x,vs,hp)
175                 | mkRecord(C.RK_VECTOR,x,vs,hp) = mkVector(x,vs,hp)
176                 | mkRecord(_,x,vs,hp) = mkNormalRecord(x,vs,hp)
177
178               (* CPS Pure Primitives *)
179               fun arrayptr v = PT.strongSubscript(value v, 0)
180
181               fun mkspecial(x,v,hp) = mkNormalRecord(x,[(v,off0)],hp)
182               fun fwrap(x,v,hp) = mkFRecord(x,[(v,off0)],hp)
183               fun i32wrap(x,v,hp) = mkNormalRecord(x,[(v,off0)],hp)
184               fun makeref(x,v,hp) = mkNormalRecord(x,[(v,off0)],hp)
185               fun newarray0(x,hp) =
186                   bind(x,PT.mkRecord(NONE,[PT.mkRecord(NONE,[])]))
187
188               fun objlength(x,v) = bind(x, PT.strongSubscript(value v, ~1))
189               fun length(x,v) = bind(x, PT.strongSubscript(value v, 1))
190               fun arraysub(x,a,i) = bind(x,PT.weakSubscript(arrayptr a))
191               fun subscriptv(x,a,i) = arraysub(x,a,i)
192               fun subscript(x,a,i) = arraysub(x,a,i)
193               fun pure_numsubscript(x,a,i) = arraysub(x,a,i)
194               fun gettag(x,v) = bind(x,PT.strongSubscript(value v, ~1))
195               fun numsubscript8(x,a,i) = arraysub(x,a,i)
196               fun numsubscriptf64(x,a,i) = arraysub(x,a,i)
197               fun getcon(x,v) = bind(x, PT.strongSubscript(value v,0))
198               fun getexn(x,v) = bind(x, PT.strongSubscript(value v,0))
199               fun recsubscript(x,a,i) = arraysub(x,a,i)
200               fun raw64subscript(x,a,i) = arraysub(x,a,i)
201
202               (* CPS Looker Primitives *)
203               fun deref(x,v) = bind(x, PT.strongSubscript(value v, 0))
204               fun gethdlr x = bind(x, PT.strongSubscript(exnptr, 0))
205               fun getvar x = bind(x, PT.strongSubscript(varptr, 0))
206
207               (* CPS Setter Primitives *)
208               fun supdate(a,x) = PT.strongUpdate(value a, 0, value x)
209               fun wupdate(a,x) = PT.weakUpdate(value a, value x)
210
211               fun assign(a,x) = supdate(a,x)
212               fun unboxedassign(a,x) = supdate(a,x)
213               fun update(a,i,x) = wupdate(a,x)
214               fun boxedupdate(a,i,x) = wupdate(a,x)
215               fun numupdate(a,i,x) = wupdate(a,x)
216               fun numupdateF64(a,i,x) = wupdate(a,x)
217               fun sethdlr x = PT.strongUpdate(exnptr, 0, value x)
218               fun setvar  x = PT.strongUpdate(varptr, 0, value x)
219
220             fun infer(C.RECORD(rk,vs,x,k),hp) =             fun infer(C.RECORD(rk,vs,x,k),hp) =
221                   (mkrecord(x,vs,hp); infer(k,allocRecord(rk,vs,hp)))                   (mkRecord(rk,x,vs,hp); infer(k,allocRecord(rk,vs,hp)))
222               | infer(C.SELECT(i,v,x,cty,k),hp) = (select(i,v,x); infer(k,hp))               | infer(C.SELECT(i,v,x,cty,k),hp) = (select(i,v,x); infer(k,hp))
223               | infer(C.OFFSET(i,v,x,k),hp) = (offset(i,v,x); infer(k,hp))               | infer(C.OFFSET(i,v,x,k),hp) = (offset(i,v,x); infer(k,hp))
224               | infer(C.APP(f,vs),hp) = apply(f,vs)               | infer(C.APP(f,vs),hp) = apply(f,vs)
225               | infer(C.FIX _,hp) = error "infer: FIX"               | infer(C.FIX _,hp) = error "infer: FIX"
226               | infer(C.SWITCH(v,x,ks),hp) = infers(ks,hp)               | infer(C.SWITCH(v,x,ks),hp) = infers(ks,hp)
227               | infer(C.BRANCH(p,_,x,k1,k2),hp) = (infer(k1,hp); infer(k2,hp))               | infer(C.BRANCH(p,_,x,k1,k2),hp) = (infer(k1,hp); infer(k2,hp))
228               | infer(C.SETTER(P.update,vs,k),hp) = infer(k,hp+storeListSize)
| infer(C.SETTER(P.boxedupdate,vs,k),hp) =
infer(k,hp+storeListSize)
| infer(C.SETTER(P.numupdate{kind=P.FLOAT 64}, [a,i,v], k),hp) =
infer(k,hp)
| infer(C.SETTER(_,vs,k),hp) = infer(k,hp)
229                 (*                 (*
230                  * These things are misnamed! There is nothing pure about them!                  * These things are misnamed! There is nothing pure about them!
231                  *)                  *)
232                 | infer(C.PURE(P.objlength, [v], x, _, k), hp) =
233                     (objlength(x, v); infer(k, hp))
234                 | infer(C.PURE(P.length, [v], x, _, k), hp) =
235                     (length(x, v); infer(k, hp))
236                 | infer(C.PURE(P.subscriptv,[a,i],x,_,k),hp) =
237                     (subscriptv(x, a, i); infer(k, hp))
238                 | infer(C.PURE(P.pure_numsubscript{kind=P.INT 8},[a,i],x,_,k),hp) =
239                     (pure_numsubscript(x, a, i); infer(k, hp))
240                 | infer(C.PURE(P.gettag, [v], x, _, k), hp) =
241                     (gettag(x, v); infer(k, hp))
242               | infer(C.PURE(P.mkspecial,[i,v],x,cty,k),hp) =               | infer(C.PURE(P.mkspecial,[i,v],x,cty,k),hp) =
243                   (bind(x,value v); infer(k,hp+8))                   (mkspecial(x,v,hp); infer(k,hp+8))
| infer(C.PURE(P.fwrap,[u],x,cty,k),hp) =
(bind(x,value u); infer(k,frecord(1,hp)))
| infer(C.PURE(P.i32wrap,[u],x,cty,k),hp) =
(bind(x,value u); infer(k,hp+8))
244               | infer(C.PURE(P.makeref,[v],x,cty,k),hp) =               | infer(C.PURE(P.makeref,[v],x,cty,k),hp) =
245                   (bind(x,value v); infer(k,hp+8))                   (makeref(x,v,hp); infer(k,hp+8))
246                 | infer(C.PURE(P.fwrap,[v],x,cty,k),hp) =
247                     (fwrap(x,v,hp); infer(k,frecordSize(1,hp)))
248                 | infer(C.PURE(P.i32wrap,[v],x,cty,k),hp) =
249                     (i32wrap(x,v,hp); infer(k,hp+8))
250                 | infer(C.PURE(P.getcon,[v],x,_,k), hp) =
251                     (getcon(x, v); infer(k, hp))
252                 | infer(C.PURE(P.getexn,[v],x,_,k), hp) =
253                     (getexn(x, v); infer(k, hp))
254                 | infer(C.PURE(P.recsubscript,[a,i],x,_,k), hp) =
255                     (recsubscript(x,a,i); infer(k, hp))
256                 | infer(C.PURE(P.raw64subscript,[a,i],x,_,k), hp) =
257                     (raw64subscript(x,a,i); infer(k, hp))
258               | infer(C.PURE(P.newarray0,_,x,cty,k),hp) =               | infer(C.PURE(P.newarray0,_,x,cty,k),hp) =
259                   (bind(x,newRef()); infer(k,hp+array0Size))                   (newarray0(x,hp); infer(k,hp+array0Size))
260               | infer(C.PURE(p,vs,x,cty,k),hp) = infer(k,hp)               | infer(C.PURE(p,vs,x,cty,k),hp) = infer(k,hp)
261
262               | infer(C.ARITH(a,vs,x,cty,k),hp) = infer(k,hp)               | infer(C.ARITH(a,vs,x,cty,k),hp) = infer(k,hp)
263               | infer(C.LOOKER(lk,vs,x,cty,k),hp) = infer(k,hp)
264                   (* Lookers *)
265                 | infer(C.LOOKER(P.!,[v],x,_,k),hp) = (deref(x,v); infer(k,hp))
266                 | infer(C.LOOKER(P.gethdlr,[],x,_,k),hp) = (gethdlr x; infer(k,hp))
267                 | infer(C.LOOKER(P.subscript,[a,i],x,_,k),hp) =
268                     (subscript(x,a,i); infer(k,hp))
269                 | infer(C.LOOKER(P.numsubscript{kind=P.INT 8},[a,i],x,_,k),hp) =
270                     (numsubscript8(x,a,i); infer(k,hp))
271                 | infer(C.LOOKER(P.numsubscript{kind=P.FLOAT 64},[a,i],x,_,k),hp) =
272                     (numsubscriptf64(x,a,i); infer(k,hp))
273
274                 | infer(C.LOOKER(P.getvar,[],x,_,k),hp) = (getvar x; infer(k,hp))
275
276                 | infer(C.LOOKER(P.deflvar,[],x,cty,k),hp) = infer(k,hp) (* nop! *)
277
278                   (* Setters *)
279                 | infer(C.SETTER(P.assign, [a,v], k),hp) =
280                     (assign(a,v); infer(k,hp+storeListSize))
281                 | infer(C.SETTER(P.unboxedassign, [a,v], k),hp) =
282                     (unboxedassign(a,v); infer(k,hp))
283                 | infer(C.SETTER(P.update, [a,i,v], k),hp) =
284                     (update(a,i,v); infer(k,hp+storeListSize))
285                 | infer(C.SETTER(P.boxedupdate, [a,i,v], k),hp) =
286                     (boxedupdate(a,i,v); infer(k,hp+storeListSize))
287                 | infer(C.SETTER(P.numupdate{kind=P.INT _}, [a,i,v], k),hp) =
288                     (numupdate(a,i,v); infer(k,hp))
289                 | infer(C.SETTER(P.numupdate{kind=P.FLOAT 64}, [a,i,v], k),hp) =
290                     (numupdateF64(a,i,v); infer(k,hp))
291
292                 | infer(C.SETTER(P.sethdlr, [x], k), hp) = (sethdlr x; infer(k,hp))
293                 | infer(C.SETTER(P.setvar, [x], k), hp) = (setvar x; infer(k,hp))
294
295                    (* Apparently these are nops (see MLRiscGen.sml) *)
296                 | infer(C.SETTER(P.uselvar, [x], k), hp) = infer(k, hp)
297                 | infer(C.SETTER(P.acclink, _, k), hp) = infer(k, hp)
298                 | infer(C.SETTER(P.setmark, _, k), hp) = infer(k, hp)
299                 | infer(C.SETTER(P.free, [x], k), hp) = infer(k, hp)
300
301                 | infer(C.SETTER(P.setpseudo, _, k), hp) =
302                     (print "setpseudo not implemented\n"; infer(k, hp))
303                 | infer(e, hp) =
304                     (PPCps.prcps e; print "\n"; error "infer")
305
306             and infers([],hp) = ()             and infers([],hp) = ()
307               | infers(k::ks,hp) = (infer(k,hp); infers(ks,hp))               | infers(k::ks,hp) = (infer(k,hp); infers(ks,hp))
308         in infer(cexp, 0)         in infer(cexp, 0)
309         end         end
310
311         val _   = PT.reset(Cells.newCell Cells.MEM)         val top = CPSRegions.memory
val top = ref(PT.NAMED("mem",PT.newTop()))
312     in  if !Control.CG.memDisambiguate then     in  if !Control.CG.memDisambiguate then
313         (app process cpsFunctions;         (CPSRegions.reset();
314            app defineFunction cpsFunctions;
315            app process cpsFunctions;
316          fn r => look r handle _ => top          fn r => look r handle _ => top
317         )         )
318         else         else

Legend:
 Removed from v.584 changed lines Added in v.585