1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
(*
* Annotate GC safety-invariants before performing SSA optimizations
*
* -- Allen (leunga@cs.nyu.edu)
*)
functor SSAGCInvariants
(structure SSA : SSA
structure TypeSys : GC_TYPE_SYSTEM
sharing SSA.RTL = TypeSys.RTL
) : SSA_OPTIMIZATION =
struct
structure SSA = SSA
structure CFG = SSA.CFG
structure I = SSA.I
structure C = I.C
structure RTL = SSA.RTL
structure T = RTL.T
structure GCMap = TypeSys.GCMap
structure GC = GCMap.GC
structure G = Graph
structure A = Array
type flowgraph = SSA.ssa
val name = "GC Safety-Invariants"
val debug = MLRiscControl.getFlag "ssa-debug-gc"
fun error msg = MLRiscErrorMsg.error("SSAGCInvariants",msg)
fun run SSA =
let val CFG = SSA.cfg SSA
in case #get GCMap.GCMAP (!(CFG.annotations CFG)) of
NONE => SSA
| SOME gcmap => doTheWork(SSA, CFG, gcmap)
end
and doTheWork(SSA, CFG, gcmap) =
let val G.GRAPH ssa = SSA
val V = SSA.maxVar SSA (* maximum encoding of variables *)
val N = #capacity ssa ()
val const = SSA.const SSA (* constants map *)
val defSiteTbl = SSA.defSiteTbl SSA (* definition site *)
val cellKindMap = SSA.cellKindTbl SSA (* cellKind map *)
val defsTbl = SSA.defsTbl SSA
val usesTbl = SSA.usesTbl SSA
val rtlTbl = SSA.rtlTbl SSA
val cellKind = IntHashTable.find cellKindMap
val cellKind = fn r => case cellKind r of SOME k => k | NONE => C.GP
val updateTy = IntHashTable.insert gcmap
val zeroR = case C.zeroReg C.GP of
SOME z => z
| NONE => ~1
val gcTypes = A.array(V, GC.BOT)
val onQueue = BitSet.create N
val hasType = BitSet.create V
fun joins [] = GC.BOT
| joins [x] = x
| joins (x::xs) = GC.join(x, joins xs)
fun initializeTypes() =
(IntHashTable.appi (fn (r,t) =>
(BitSet.set(hasType,r); A.update(gcTypes, r, t))) gcmap;
if zeroR >= 0 then A.update(gcTypes, zeroR, GC.CONST 0) else ()
)
fun enqueueInsn(j, WL) =
if BitSet.markAndTest(onQueue, j) then WL
else j::WL
fun enqueue(r, WL) =
let val i = A.sub(defSiteTbl,r)
fun ins([], WL) = WL
| ins((_,j,_)::es, WL) = ins(es, enqueueInsn(j, WL))
in ins(#out_edges ssa i, WL) end
fun update(r, t, WL) =
if r = zeroR orelse BitSet.contains(hasType, r)
then WL
else let val t' = A.sub(gcTypes, r)
in if GC.==(t,t') then WL
else
((* print("r"^Int.toString r^":"^GC.toString t^"\n");*)
A.update(gcTypes, r, t);
enqueue(r, WL))
end
fun lookup r = A.sub(gcTypes, r)
val effectOf = TypeSys.effectOf {lookup=lookup, update=update}
fun iterate([]) = ()
| iterate(i::WL) =
let val _ = BitSet.reset(onQueue,i)
in iterate(process(i, WL)) end
and process(i,WL) =
let val rtl = A.sub(rtlTbl,i)
val defs = A.sub(defsTbl,i)
val uses = A.sub(usesTbl,i)
in case (rtl,defs,uses) of
(T.PHI _,[t],s) => phi(t,s,WL)
| (T.SOURCE _,t,_) =>
let fun init([],WL) = WL
| init(t::ts,WL) = init(ts,setTop(t,WL))
and setTop(t,WL) =
if BitSet.contains(hasType, t) then WL
else (update(t, GC.TOP, WL))
in init(t, WL) end
| (T.SINK _, _, _) => WL
| (e, t, s) =>
let fun lookupN n =
let val r = List.nth(s,n)
in if r < 0 then GC.INT else A.sub(gcTypes,r) end
fun updateN(n, ty, WL) = update(List.nth(t,n), ty, WL)
in TypeSys.effectOf{lookup=lookupN, update=updateN}
{action=e,src=s,dst=t,effect=WL}
handle e => (print("["^Int.toString i^"] "^
SSA.showOp SSA i^"\n"); raise e)
end
end
and phi(t, s, WL) =
if BitSet.contains(hasType, t) then WL
else let val tys = map lookup s
val ty = joins tys
in update(t, ty, WL) end
fun updateTypes() =
A.appi (fn (r,t) => if GC.==(t,GC.TOP) then ()
else if GC.==(t,GC.BOT) then ()
else updateTy(r,t)) (gcTypes, 0, NONE)
fun typeInference() =
let val WL = map #1 (#nodes ssa ())
in app (fn i => BitSet.set(onQueue,i)) WL;
iterate WL
end
fun markConstraints() =
let val G.GRAPH dom = SSA.dom SSA
val {ops, ...} = SSA.nodes SSA
val showOp = SSA.showOp SSA
fun walk b =
let fun markAsNonMovable i =
(if !debug then
print("Block "^Int.toString b^" can't move: "^
showOp i^"\n")
else ();
A.update(rtlTbl, i, RTL.pin(A.sub(rtlTbl, i)))
)
fun mark(i) =
let fun isRecoverable [] = true
| isRecoverable(t::ts) =
(cellKind t = C.MEM orelse
cellKind t = C.CTRL orelse
TypeSys.isRecoverable(A.sub(gcTypes,t))) andalso
isRecoverable ts
in case A.sub(rtlTbl,i) of
(T.PHI _ | T.SOURCE _ | T.SINK _) => ()
| _ =>
if isRecoverable (A.sub(defsTbl,i)) then () (* okay *)
else markAsNonMovable i
end
in app mark (A.sub(ops, b));
app walk (#succ dom b)
end
in walk(hd(#entries dom ()))
end
in print "GC type inference\n";
initializeTypes();
typeInference();
updateTypes();
print "GC type inference done\n";
markConstraints();
SSA
end
end
|
