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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
|
from rpython.jit.metainterp.history import ConstInt
from rpython.jit.metainterp.resoperation import rop
class HeapCache(object):
def __init__(self):
self.reset()
def reset(self, reset_virtuals=True, trace_branch=True):
# contains boxes where the class is already known
self.known_class_boxes = {}
# store the boxes that contain newly allocated objects, this maps the
# boxes to a bool, the bool indicates whether or not the object has
# escaped the trace or not (True means the box never escaped, False
# means it did escape), its presences in the mapping shows that it was
# allocated inside the trace
if trace_branch:
self.new_boxes = {}
else:
for box in self.new_boxes:
self.new_boxes[box] = False
if reset_virtuals:
self.likely_virtuals = {} # only for jit.isvirtual()
# Tracks which boxes should be marked as escaped when the key box
# escapes.
self.dependencies = {}
# contains frame boxes that are not virtualizables
if trace_branch:
self.nonstandard_virtualizables = {}
# heap cache
# maps descrs to {from_box, to_box} dicts
self.heap_cache = {}
# heap array cache
# maps descrs to {index: {from_box: to_box}} dicts
self.heap_array_cache = {}
# cache the length of arrays
self.length_cache = {}
# replace_box is called surprisingly often, therefore it's not efficient
# to go over all the dicts and fix them.
# instead, these two dicts are kept, and a replace_box adds an entry to
# each of them.
# every time one of the dicts heap_cache, heap_array_cache, length_cache
# is accessed, suitable indirections need to be performed
# this looks all very subtle, but in practice the patterns of
# replacements should not be that complex. Usually a box is replaced by
# a const, once. Also, if something goes wrong, the effect is that less
# caching than possible is done, which is not a huge problem.
self.input_indirections = {}
self.output_indirections = {}
def _input_indirection(self, box):
return self.input_indirections.get(box, box)
def _output_indirection(self, box):
return self.output_indirections.get(box, box)
def invalidate_caches(self, opnum, descr, argboxes):
self.mark_escaped(opnum, descr, argboxes)
self.clear_caches(opnum, descr, argboxes)
def mark_escaped(self, opnum, descr, argboxes):
if opnum == rop.SETFIELD_GC:
assert len(argboxes) == 2
box, valuebox = argboxes
if self.is_unescaped(box) and self.is_unescaped(valuebox):
self.dependencies.setdefault(box, []).append(valuebox)
else:
self._escape(valuebox)
elif opnum == rop.SETARRAYITEM_GC:
assert len(argboxes) == 3
box, indexbox, valuebox = argboxes
if self.is_unescaped(box) and self.is_unescaped(valuebox):
self.dependencies.setdefault(box, []).append(valuebox)
else:
self._escape(valuebox)
elif (opnum == rop.CALL and
descr.get_extra_info().oopspecindex == descr.get_extra_info().OS_ARRAYCOPY and
isinstance(argboxes[3], ConstInt) and
isinstance(argboxes[4], ConstInt) and
isinstance(argboxes[5], ConstInt) and
len(descr.get_extra_info().write_descrs_arrays) == 1):
# ARRAYCOPY with constant starts and constant length doesn't escape
# its argument
pass
# GETFIELD_GC, MARK_OPAQUE_PTR, PTR_EQ, and PTR_NE don't escape their
# arguments
elif (opnum != rop.GETFIELD_GC and
opnum != rop.GETFIELD_GC_PURE and
opnum != rop.MARK_OPAQUE_PTR and
opnum != rop.PTR_EQ and
opnum != rop.PTR_NE and
opnum != rop.INSTANCE_PTR_EQ and
opnum != rop.INSTANCE_PTR_NE):
for box in argboxes:
self._escape(box)
def _escape(self, box):
try:
unescaped = self.new_boxes[box]
except KeyError:
pass
else:
if unescaped:
self.new_boxes[box] = False
try:
del self.likely_virtuals[box]
except KeyError:
pass
try:
deps = self.dependencies.pop(box)
except KeyError:
pass
else:
for dep in deps:
self._escape(dep)
def clear_caches(self, opnum, descr, argboxes):
if (opnum == rop.SETFIELD_GC or
opnum == rop.SETARRAYITEM_GC or
opnum == rop.SETFIELD_RAW or
opnum == rop.SETARRAYITEM_RAW or
opnum == rop.SETINTERIORFIELD_GC or
opnum == rop.COPYSTRCONTENT or
opnum == rop.COPYUNICODECONTENT or
opnum == rop.STRSETITEM or
opnum == rop.UNICODESETITEM or
opnum == rop.SETFIELD_RAW or
opnum == rop.SETARRAYITEM_RAW or
opnum == rop.SETINTERIORFIELD_RAW or
opnum == rop.RAW_STORE):
return
if (rop._OVF_FIRST <= opnum <= rop._OVF_LAST or
rop._NOSIDEEFFECT_FIRST <= opnum <= rop._NOSIDEEFFECT_LAST or
rop._GUARD_FIRST <= opnum <= rop._GUARD_LAST):
return
if opnum == rop.CALL or opnum == rop.CALL_LOOPINVARIANT or opnum == rop.COND_CALL:
effectinfo = descr.get_extra_info()
ef = effectinfo.extraeffect
if (ef == effectinfo.EF_LOOPINVARIANT or
ef == effectinfo.EF_ELIDABLE_CANNOT_RAISE or
ef == effectinfo.EF_ELIDABLE_CAN_RAISE):
return
# A special case for ll_arraycopy, because it is so common, and its
# effects are so well defined.
elif effectinfo.oopspecindex == effectinfo.OS_ARRAYCOPY:
if (
isinstance(argboxes[3], ConstInt) and
isinstance(argboxes[4], ConstInt) and
isinstance(argboxes[5], ConstInt) and
len(effectinfo.write_descrs_arrays) == 1
):
descr = effectinfo.write_descrs_arrays[0]
cache = self.heap_array_cache.get(descr, None)
srcstart = argboxes[3].getint()
dststart = argboxes[4].getint()
length = argboxes[5].getint()
for i in xrange(length):
value = self.getarrayitem(
argboxes[1],
ConstInt(srcstart + i),
descr,
)
if value is not None:
self.setarrayitem(
argboxes[2],
ConstInt(dststart + i),
value,
descr,
)
elif cache is not None:
try:
idx_cache = cache[dststart + i]
except KeyError:
pass
else:
if argboxes[2] in self.new_boxes:
for frombox in idx_cache.keys():
if not self.is_unescaped(frombox):
del idx_cache[frombox]
else:
idx_cache.clear()
return
elif (
argboxes[2] in self.new_boxes and
len(effectinfo.write_descrs_arrays) == 1
):
# Fish the descr out of the effectinfo
cache = self.heap_array_cache.get(effectinfo.write_descrs_arrays[0], None)
if cache is not None:
for idx, cache in cache.iteritems():
for frombox in cache.keys():
if not self.is_unescaped(frombox):
del cache[frombox]
return
else:
# Only invalidate things that are either escaped or arguments
for descr, boxes in self.heap_cache.iteritems():
for box in boxes.keys():
if not self.is_unescaped(box) or box in argboxes:
del boxes[box]
for descr, indices in self.heap_array_cache.iteritems():
for boxes in indices.itervalues():
for box in boxes.keys():
if not self.is_unescaped(box) or box in argboxes:
del boxes[box]
return
# XXX not completely sure, but I *think* it is needed to reset() the
# state at least in the 'CALL_*' operations that release the GIL. We
# tried to do only the kind of resetting done by the two loops just
# above, but hit an assertion in "pypy test_multiprocessing.py".
self.reset(reset_virtuals=False, trace_branch=False)
def is_class_known(self, box):
return box in self.known_class_boxes
def class_now_known(self, box):
self.known_class_boxes[box] = None
def is_nonstandard_virtualizable(self, box):
return box in self.nonstandard_virtualizables
def nonstandard_virtualizables_now_known(self, box):
self.nonstandard_virtualizables[box] = None
def is_unescaped(self, box):
return self.new_boxes.get(box, False)
def is_likely_virtual(self, box):
return box in self.likely_virtuals
def new(self, box):
self.new_boxes[box] = True
self.likely_virtuals[box] = None
def new_array(self, box, lengthbox):
self.new(box)
self.arraylen_now_known(box, lengthbox)
def getfield(self, box, descr):
box = self._input_indirection(box)
d = self.heap_cache.get(descr, None)
if d:
tobox = d.get(box, None)
return self._output_indirection(tobox)
return None
def getfield_now_known(self, box, descr, fieldbox):
box = self._input_indirection(box)
fieldbox = self._input_indirection(fieldbox)
self.heap_cache.setdefault(descr, {})[box] = fieldbox
def setfield(self, box, fieldbox, descr):
d = self.heap_cache.get(descr, None)
new_d = self._do_write_with_aliasing(d, box, fieldbox)
self.heap_cache[descr] = new_d
def _do_write_with_aliasing(self, d, box, fieldbox):
box = self._input_indirection(box)
fieldbox = self._input_indirection(fieldbox)
# slightly subtle logic here
# a write to an arbitrary box, all other boxes can alias this one
if not d or box not in self.new_boxes:
# therefore we throw away the cache
return {box: fieldbox}
# the object we are writing to is freshly allocated
# only remove some boxes from the cache
new_d = {}
for frombox, tobox in d.iteritems():
# the other box is *also* freshly allocated
# therefore frombox and box *must* contain different objects
# thus we can keep it in the cache
if frombox in self.new_boxes:
new_d[frombox] = tobox
new_d[box] = fieldbox
return new_d
def getarrayitem(self, box, indexbox, descr):
if not isinstance(indexbox, ConstInt):
return
box = self._input_indirection(box)
index = indexbox.getint()
cache = self.heap_array_cache.get(descr, None)
if cache:
indexcache = cache.get(index, None)
if indexcache is not None:
return self._output_indirection(indexcache.get(box, None))
def getarrayitem_now_known(self, box, indexbox, valuebox, descr):
if not isinstance(indexbox, ConstInt):
return
box = self._input_indirection(box)
valuebox = self._input_indirection(valuebox)
index = indexbox.getint()
cache = self.heap_array_cache.setdefault(descr, {})
indexcache = cache.get(index, None)
if indexcache is not None:
indexcache[box] = valuebox
else:
cache[index] = {box: valuebox}
def setarrayitem(self, box, indexbox, valuebox, descr):
if not isinstance(indexbox, ConstInt):
cache = self.heap_array_cache.get(descr, None)
if cache is not None:
cache.clear()
return
index = indexbox.getint()
cache = self.heap_array_cache.setdefault(descr, {})
indexcache = cache.get(index, None)
cache[index] = self._do_write_with_aliasing(indexcache, box, valuebox)
def arraylen(self, box):
box = self._input_indirection(box)
return self._output_indirection(self.length_cache.get(box, None))
def arraylen_now_known(self, box, lengthbox):
box = self._input_indirection(box)
self.length_cache[box] = self._input_indirection(lengthbox)
def replace_box(self, oldbox, newbox):
self.input_indirections[self._output_indirection(newbox)] = self._input_indirection(oldbox)
self.output_indirections[self._input_indirection(oldbox)] = self._output_indirection(newbox)
|
