Author: Carl Friedrich Bolz <[email protected]>
Branch: nonquadratic-heapcache
Changeset: r75933:33600f2c12d8
Date: 2015-02-17 11:36 +0100
http://bitbucket.org/pypy/pypy/changeset/33600f2c12d8/
Log: refactor heap cache to use HeapCacheValues everywhere
diff --git a/rpython/jit/metainterp/heapcache.py
b/rpython/jit/metainterp/heapcache.py
--- a/rpython/jit/metainterp/heapcache.py
+++ b/rpython/jit/metainterp/heapcache.py
@@ -5,13 +5,22 @@
def __init__(self, box):
self.box = box
self.known_class = False
+ # did we see the allocation during tracing?
+ self.seen_allocation = False
+ self.is_unescaped = False
+ self.likely_virtual = False
self.nonstandard_virtualizable = False
+ self.lengthvalue = None
+ self.dependencies = None
+
+ def __repr__(self):
+ return 'HeapCacheValue(%s)' % (self.box, )
class HeapCache(object):
def __init__(self):
self.reset()
- def reset(self, reset_virtuals=True, trace_branch=True):
+ def reset(self):
# maps boxes to values
self.values = {}
# store the boxes that contain newly allocated objects, this maps the
@@ -19,54 +28,48 @@
# 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()
+ #if trace_branch:
+ #self.new_boxes = {}
+ # pass
+ #else:
+ #for box in self.new_boxes:
+ # self.new_boxes[box] = False
+ # pass
+ #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 = {}
+ #self.dependencies = {}
# heap cache
- # maps descrs to {from_box, to_box} dicts
+ # maps descrs to {from_value, to_value} dicts
self.heap_cache = {}
# heap array cache
- # maps descrs to {index: {from_box: to_box}} dicts
+ # maps descrs to {index: {from_value: to_value}} 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
+ def reset_keep_likely_virtuals(self):
+ for value in self.values.itervalues():
+ value.is_unescaped = False
+ self.heap_cache = {}
+ self.heap_array_cache = {}
- # 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 get_value(self, box):
+ def getvalue(self, box):
value = self.values.get(box, None)
if not value:
value = self.values[box] = HeapCacheValue(box)
return value
+ def getvalues(self, boxes):
+ return [self.getvalue(box) for box in boxes]
+
def _input_indirection(self, box):
- return self.input_indirections.get(box, box)
+ value = self.values.get(box, None)
+ if value is None:
+ return box
+ return value.box
- def _output_indirection(self, box):
- return self.output_indirections.get(box, box)
+ _output_indirection = _input_indirection
def invalidate_caches(self, opnum, descr, argboxes):
self.mark_escaped(opnum, descr, argboxes)
@@ -75,18 +78,22 @@
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)
+ value, fieldvalue = self.getvalues(argboxes)
+ if value.is_unescaped and fieldvalue.is_unescaped:
+ if value.dependencies is None:
+ value.dependencies = []
+ value.dependencies.append(fieldvalue)
else:
- self._escape(valuebox)
+ self._escape(fieldvalue)
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)
+ value, indexvalue, fieldvalue = self.getvalues(argboxes)
+ if value.is_unescaped and fieldvalue.is_unescaped:
+ if value.dependencies is None:
+ value.dependencies = []
+ value.dependencies.append(fieldvalue)
else:
- self._escape(valuebox)
+ self._escape(fieldvalue)
elif (opnum == rop.CALL and
descr.get_extra_info().oopspecindex ==
descr.get_extra_info().OS_ARRAYCOPY and
isinstance(argboxes[3], ConstInt) and
@@ -106,25 +113,20 @@
opnum != rop.INSTANCE_PTR_EQ and
opnum != rop.INSTANCE_PTR_NE):
for box in argboxes:
- self._escape(box)
+ self._escape_box(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:
+ def _escape_box(self, box):
+ value = self.values.get(box, None)
+ if not value:
+ return
+ self._escape(value)
+
+ def _escape(self, value):
+ value.is_unescaped = False
+ value.likely_virtual = False
+ deps = value.dependencies
+ value.dependencies = None
+ if deps is not None:
for dep in deps:
self._escape(dep)
@@ -157,6 +159,7 @@
# A special case for ll_arraycopy, because it is so common, and its
# effects are so well defined.
elif effectinfo.oopspecindex == effectinfo.OS_ARRAYCOPY:
+ seen_allocation_of_target =
self.getvalue(argboxes[2]).seen_allocation
if (
isinstance(argboxes[3], ConstInt) and
isinstance(argboxes[4], ConstInt) and
@@ -187,43 +190,43 @@
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]
+ if seen_allocation_of_target:
+ for fromvalue in idx_cache.keys():
+ if not fromvalue.seen_allocation:
+ del idx_cache[fromvalue]
else:
idx_cache.clear()
return
elif (
- argboxes[2] in self.new_boxes and
+ seen_allocation_of_target 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]
+ for fromvalue in cache.keys():
+ if not fromvalue.seen_allocation:
+ del cache[fromvalue]
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, values in self.heap_cache.iteritems():
+ for value in values.keys():
+ if not self.is_unescaped(value.box) or value.box in
argboxes:
+ del values[value]
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]
+ for values in indices.itervalues():
+ for value in values.keys():
+ if not self.is_unescaped(value.box) or value.box
in argboxes:
+ del values[value]
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)
+ self.reset_keep_likely_virtuals()
def is_class_known(self, box):
value = self.values.get(box, None)
@@ -232,7 +235,7 @@
return False
def class_now_known(self, box):
- self.get_value(box).known_class = True
+ self.getvalue(box).known_class = True
def is_nonstandard_virtualizable(self, box):
value = self.values.get(box, None)
@@ -241,34 +244,44 @@
return False
def nonstandard_virtualizables_now_known(self, box):
- self.get_value(box).nonstandard_virtualizable = True
+ self.getvalue(box).nonstandard_virtualizable = True
def is_unescaped(self, box):
- return self.new_boxes.get(box, False)
+ value = self.values.get(box, None)
+ if value:
+ return value.is_unescaped
+ return False
def is_likely_virtual(self, box):
- return box in self.likely_virtuals
+ value = self.values.get(box, None)
+ if value:
+ return value.likely_virtual
+ return False
def new(self, box):
- self.new_boxes[box] = True
- self.likely_virtuals[box] = None
+ value = self.getvalue(box)
+ value.is_unescaped = True
+ value.likely_virtual = True
+ value.seen_allocation = True
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)
+ value = self.values.get(box, None)
+ if value:
+ d = self.heap_cache.get(descr, None)
+ if d:
+ tovalue = d.get(value, None)
+ if tovalue:
+ return tovalue.box
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
+ value = self.getvalue(box)
+ fieldvalue = self.getvalue(fieldbox)
+ self.heap_cache.setdefault(descr, {})[value] = fieldvalue
def setfield(self, box, fieldbox, descr):
d = self.heap_cache.get(descr, None)
@@ -276,51 +289,55 @@
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)
+ value = self.getvalue(box)
+ fieldvalue = self.getvalue(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:
+ # a write to an arbitrary value, all other valuees can alias this one
+ if not d or not value.seen_allocation:
# therefore we throw away the cache
- return {box: fieldbox}
+ return {value: fieldvalue}
# the object we are writing to is freshly allocated
- # only remove some boxes from the cache
+ # only remove some valuees 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
+ for fromvalue, tovalue in d.iteritems():
+ # the other value is *also* one where we saw the allocation
+ # therefore fromvalue and value *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
- print len(self.new_boxes), len(d), len(new_d)
+ if fromvalue.seen_allocation:
+ new_d[fromvalue] = tovalue
+ new_d[value] = fieldvalue
return new_d
def getarrayitem(self, box, indexbox, descr):
if not isinstance(indexbox, ConstInt):
- return
- box = self._input_indirection(box)
+ return None
+ value = self.values.get(box, None)
+ if value is None:
+ return None
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))
+ resvalue = indexcache.get(value, None)
+ if resvalue:
+ return resvalue.box
+ return None
- def getarrayitem_now_known(self, box, indexbox, valuebox, descr):
+ def getarrayitem_now_known(self, box, indexbox, fieldbox, descr):
if not isinstance(indexbox, ConstInt):
return
- box = self._input_indirection(box)
- valuebox = self._input_indirection(valuebox)
+ value = self.getvalue(box)
+ fieldvalue = self.getvalue(fieldbox)
index = indexbox.getint()
cache = self.heap_array_cache.setdefault(descr, {})
indexcache = cache.get(index, None)
if indexcache is not None:
- indexcache[box] = valuebox
+ indexcache[value] = fieldvalue
else:
- cache[index] = {box: valuebox}
+ cache[index] = {value: fieldvalue}
- def setarrayitem(self, box, indexbox, valuebox, descr):
+ def setarrayitem(self, box, indexbox, fieldbox, descr):
if not isinstance(indexbox, ConstInt):
cache = self.heap_array_cache.get(descr, None)
if cache is not None:
@@ -329,16 +346,21 @@
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)
+ cache[index] = self._do_write_with_aliasing(indexcache, box, fieldbox)
def arraylen(self, box):
- box = self._input_indirection(box)
- return self._output_indirection(self.length_cache.get(box, None))
+ value = self.values.get(box, None)
+ if value and value.length:
+ return value.length.box
+ return None
def arraylen_now_known(self, box, lengthbox):
- box = self._input_indirection(box)
- self.length_cache[box] = self._input_indirection(lengthbox)
+ value = self.getvalue(box)
+ value.length = self.getvalue(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)
+ value = self.values.get(oldbox, None)
+ if value is None:
+ return
+ value.box = newbox
+ self.values[newbox] = value
diff --git a/rpython/jit/metainterp/pyjitpl.py
b/rpython/jit/metainterp/pyjitpl.py
--- a/rpython/jit/metainterp/pyjitpl.py
+++ b/rpython/jit/metainterp/pyjitpl.py
@@ -2192,7 +2192,8 @@
duplicates[box] = None
def reached_loop_header(self, greenboxes, redboxes):
- self.heapcache.reset(reset_virtuals=False)
+ #self.heapcache.reset(reset_virtuals=False)
+ self.heapcache.reset_keep_likely_virtuals()
duplicates = {}
self.remove_consts_and_duplicates(redboxes, len(redboxes),
diff --git a/rpython/jit/metainterp/test/test_heapcache.py
b/rpython/jit/metainterp/test/test_heapcache.py
--- a/rpython/jit/metainterp/test/test_heapcache.py
+++ b/rpython/jit/metainterp/test/test_heapcache.py
@@ -594,9 +594,9 @@
h.new(box1)
assert h.is_unescaped(box1)
assert h.is_likely_virtual(box1)
- h.reset(reset_virtuals=False)
+ h.reset_keep_likely_virtuals()
assert not h.is_unescaped(box1)
assert h.is_likely_virtual(box1)
- h._escape(box1)
+ h._escape_box(box1)
assert not h.is_unescaped(box1)
assert not h.is_likely_virtual(box1)
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
