Commits

Carl Friedrich Bolz committed 5fcc432 Merge

merge improve-heap-caching-tracing:
- a much better heap cache during tracing, this makes the traces that are
produced before optimization much shorter, thus improving warmup time,
reducing GC pressure, etc.

- change the maximum trace length to half its original value. Now that the
traces are much shorted due to the better optimization, this seems to give
much better results for translation.

  • Participants
  • Parent commits 0fdfb1b, 7793d23

Comments (0)

Files changed (5)

File pypy/jit/metainterp/heapcache.py

+from pypy.jit.metainterp.history import ConstInt
+from pypy.jit.metainterp.resoperation import rop
+
+
+class HeapCache(object):
+    def __init__(self):
+        self.reset()
+
+    def reset(self):
+        # contains boxes where the class is already known
+        self.known_class_boxes = {}
+        # store the boxes that contain newly allocated objects:
+        self.new_boxes = {}
+        # contains frame boxes that are not virtualizables
+        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 = {}
+
+    def invalidate_caches(self, opnum, descr, argboxes):
+        if opnum == rop.SETFIELD_GC:
+            return
+        if opnum == rop.SETARRAYITEM_GC:
+            return
+        if opnum == rop.SETFIELD_RAW:
+            return
+        if opnum == rop.SETARRAYITEM_RAW:
+            return
+        if rop._OVF_FIRST <= opnum <= rop._OVF_LAST:
+            return
+        if rop._NOSIDEEFFECT_FIRST <= opnum <= rop._NOSIDEEFFECT_LAST:
+            return
+        if opnum == rop.CALL or opnum == rop.CALL_LOOPINVARIANT:
+            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:
+                # The destination box
+                if argboxes[2] in self.new_boxes:
+                    # XXX: no descr here so we invalidate any of them, not just
+                    # of the correct type
+                    # XXX: in theory the indices of the copy could be looked at
+                    # as well
+                    for descr, cache in self.heap_array_cache.iteritems():
+                        for idx, cache in cache.iteritems():
+                            for frombox in cache.keys():
+                                if frombox not in self.new_boxes:
+                                    del cache[frombox]
+                    return
+
+        self.heap_cache.clear()
+        self.heap_array_cache.clear()
+
+    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 new(self, box):
+        self.new_boxes[box] = None
+
+    def new_array(self, box, lengthbox):
+        self.new(box)
+        self.arraylen_now_known(box, lengthbox)
+
+    def getfield(self, box, descr):
+        d = self.heap_cache.get(descr, None)
+        if d:
+            tobox = d.get(box, None)
+            if tobox:
+                return tobox
+        return None
+
+    def getfield_now_known(self, box, descr, fieldbox):
+        self.heap_cache.setdefault(descr, {})[box] = fieldbox
+
+    def setfield(self, box, descr, fieldbox):
+        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):
+        # 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, descr, indexbox):
+        if not isinstance(indexbox, ConstInt):
+            return
+        index = indexbox.getint()
+        cache = self.heap_array_cache.get(descr, None)
+        if cache:
+            indexcache = cache.get(index, None)
+            if indexcache is not None:
+                return indexcache.get(box, None)
+
+    def getarrayitem_now_known(self, box, descr, indexbox, valuebox):
+        if not isinstance(indexbox, ConstInt):
+            return
+        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, descr, indexbox, valuebox):
+        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):
+        return self.length_cache.get(box, None)
+
+    def arraylen_now_known(self, box, lengthbox):
+        self.length_cache[box] = lengthbox
+
+    def _replace_box(self, d, oldbox, newbox):
+        new_d = {}
+        for frombox, tobox in d.iteritems():
+            if frombox is oldbox:
+                frombox = newbox
+            if tobox is oldbox:
+                tobox = newbox
+            new_d[frombox] = tobox
+        return new_d
+
+    def replace_box(self, oldbox, newbox):
+        for descr, d in self.heap_cache.iteritems():
+            self.heap_cache[descr] = self._replace_box(d, oldbox, newbox)
+        for descr, d in self.heap_array_cache.iteritems():
+            for index, cache in d.iteritems():
+                d[index] = self._replace_box(cache, oldbox, newbox)
+        self.length_cache = self._replace_box(self.length_cache, oldbox, newbox)

File pypy/jit/metainterp/pyjitpl.py

 from pypy.jit.metainterp.jitprof import ABORT_TOO_LONG, ABORT_BRIDGE, \
                                         ABORT_FORCE_QUASIIMMUT, ABORT_BAD_LOOP
 from pypy.jit.metainterp.jitexc import JitException, get_llexception
+from pypy.jit.metainterp.heapcache import HeapCache
 from pypy.rlib.objectmodel import specialize
 from pypy.jit.codewriter.jitcode import JitCode, SwitchDictDescr
 from pypy.jit.codewriter import heaptracker
     def _establish_nullity(self, box, orgpc):
         value = box.nonnull()
         if value:
-            if box not in self.metainterp.known_class_boxes:
+            if not self.metainterp.heapcache.is_class_known(box):
                 self.generate_guard(rop.GUARD_NONNULL, box, resumepc=orgpc)
         else:
             if not isinstance(box, Const):
 
     @arguments("descr")
     def opimpl_new(self, sizedescr):
-        return self.execute_with_descr(rop.NEW, sizedescr)
+        resbox = self.execute_with_descr(rop.NEW, sizedescr)
+        self.metainterp.heapcache.new(resbox)
+        return resbox
 
     @arguments("descr")
     def opimpl_new_with_vtable(self, sizedescr):
         cpu = self.metainterp.cpu
         cls = heaptracker.descr2vtable(cpu, sizedescr)
         resbox = self.execute(rop.NEW_WITH_VTABLE, ConstInt(cls))
-        self.metainterp.known_class_boxes[resbox] = None
+        self.metainterp.heapcache.new(resbox)
+        self.metainterp.heapcache.class_now_known(resbox)
         return resbox
 
 ##    @FixME  #arguments("box")
 ##        self.execute(rop.SUBCLASSOF, box1, box2)
 
     @arguments("descr", "box")
-    def opimpl_new_array(self, itemsizedescr, countbox):
-        return self.execute_with_descr(rop.NEW_ARRAY, itemsizedescr, countbox)
+    def opimpl_new_array(self, itemsizedescr, lengthbox):
+        resbox = self.execute_with_descr(rop.NEW_ARRAY, itemsizedescr, lengthbox)
+        self.metainterp.heapcache.new_array(resbox, lengthbox)
+        return resbox
 
     @arguments("box", "descr", "box")
     def _opimpl_getarrayitem_gc_any(self, arraybox, arraydescr, indexbox):
-        cache = self.metainterp.heap_array_cache.get(arraydescr, None)
-        if cache and isinstance(indexbox, ConstInt):
-            index = indexbox.getint()
-            frombox, tobox = cache.get(index, (None, None))
-            if frombox is arraybox:
-                return tobox
+        tobox = self.metainterp.heapcache.getarrayitem(
+                arraybox, arraydescr, indexbox)
+        if tobox:
+            # sanity check: see whether the current array value
+            # corresponds to what the cache thinks the value is
+            resbox = executor.execute(self.metainterp.cpu, self.metainterp,
+                                      rop.GETARRAYITEM_GC, arraydescr, arraybox, indexbox)
+            assert resbox.constbox().same_constant(tobox.constbox())
+            return tobox
         resbox = self.execute_with_descr(rop.GETARRAYITEM_GC,
                                          arraydescr, arraybox, indexbox)
-        if isinstance(indexbox, ConstInt):
-            if not cache:
-                cache = self.metainterp.heap_array_cache[arraydescr] = {}
-            index = indexbox.getint()
-            cache[index] = arraybox, resbox
+        self.metainterp.heapcache.getarrayitem_now_known(
+                arraybox, arraydescr, indexbox, resbox)
         return resbox
 
 
                                     indexbox, itembox):
         self.execute_with_descr(rop.SETARRAYITEM_GC, arraydescr, arraybox,
                                 indexbox, itembox)
-        if isinstance(indexbox, ConstInt):
-            cache = self.metainterp.heap_array_cache.setdefault(arraydescr, {})
-            cache[indexbox.getint()] = arraybox, itembox
-        else:
-            cache = self.metainterp.heap_array_cache.get(arraydescr, None)
-            if cache:
-                cache.clear()
+        self.metainterp.heapcache.setarrayitem(
+                arraybox, arraydescr, indexbox, itembox)
 
     opimpl_setarrayitem_gc_i = _opimpl_setarrayitem_gc_any
     opimpl_setarrayitem_gc_r = _opimpl_setarrayitem_gc_any
 
     @arguments("box", "descr")
     def opimpl_arraylen_gc(self, arraybox, arraydescr):
-        return self.execute_with_descr(rop.ARRAYLEN_GC, arraydescr, arraybox)
+        lengthbox = self.metainterp.heapcache.arraylen(arraybox)
+        if lengthbox is None:
+            lengthbox = self.execute_with_descr(
+                    rop.ARRAYLEN_GC, arraydescr, arraybox)
+            self.metainterp.heapcache.arraylen_now_known(arraybox, lengthbox)
+        return lengthbox
 
     @arguments("orgpc", "box", "descr", "box")
     def opimpl_check_neg_index(self, orgpc, arraybox, arraydescr, indexbox):
         negbox = self.implement_guard_value(orgpc, negbox)
         if negbox.getint():
             # the index is < 0; add the array length to it
-            lenbox = self.metainterp.execute_and_record(
-                rop.ARRAYLEN_GC, arraydescr, arraybox)
+            lengthbox = self.opimpl_arraylen_gc(arraybox, arraydescr)
             indexbox = self.metainterp.execute_and_record(
-                rop.INT_ADD, None, indexbox, lenbox)
+                rop.INT_ADD, None, indexbox, lengthbox)
         return indexbox
 
     @arguments("descr", "descr", "descr", "descr", "box")
     def opimpl_newlist(self, structdescr, lengthdescr, itemsdescr, arraydescr,
                        sizebox):
-        sbox = self.metainterp.execute_and_record(rop.NEW, structdescr)
+        sbox = self.opimpl_new(structdescr)
         self._opimpl_setfield_gc_any(sbox, lengthdescr, sizebox)
-        abox = self.metainterp.execute_and_record(rop.NEW_ARRAY, arraydescr,
-                                                  sizebox)
+        abox = self.opimpl_new_array(arraydescr, sizebox)
         self._opimpl_setfield_gc_any(sbox, itemsdescr, abox)
         return sbox
 
 
     @specialize.arg(1)
     def _opimpl_getfield_gc_any_pureornot(self, opnum, box, fielddescr):
-        frombox, tobox = self.metainterp.heap_cache.get(fielddescr, (None, None))
-        if frombox is box:
+        tobox = self.metainterp.heapcache.getfield(box, fielddescr)
+        if tobox is not None:
+            # sanity check: see whether the current struct value
+            # corresponds to what the cache thinks the value is
+            resbox = executor.execute(self.metainterp.cpu, self.metainterp,
+                                      rop.GETFIELD_GC, fielddescr, box)
             return tobox
         resbox = self.execute_with_descr(opnum, fielddescr, box)
-        self.metainterp.heap_cache[fielddescr] = (box, resbox)
+        self.metainterp.heapcache.getfield_now_known(box, fielddescr, resbox)
         return resbox
 
     @arguments("orgpc", "box", "descr")
 
     @arguments("box", "descr", "box")
     def _opimpl_setfield_gc_any(self, box, fielddescr, valuebox):
-        frombox, tobox = self.metainterp.heap_cache.get(fielddescr, (None, None))
-        if frombox is box and tobox is valuebox:
+        tobox = self.metainterp.heapcache.getfield(box, fielddescr)
+        if tobox is valuebox:
             return
         self.execute_with_descr(rop.SETFIELD_GC, fielddescr, box, valuebox)
-        self.metainterp.heap_cache[fielddescr] = (box, valuebox)
+        self.metainterp.heapcache.setfield(box, fielddescr, valuebox)
     opimpl_setfield_gc_i = _opimpl_setfield_gc_any
     opimpl_setfield_gc_r = _opimpl_setfield_gc_any
     opimpl_setfield_gc_f = _opimpl_setfield_gc_any
         standard_box = self.metainterp.virtualizable_boxes[-1]
         if standard_box is box:
             return False
-        if box in self.metainterp.nonstandard_virtualizables:
+        if self.metainterp.heapcache.is_nonstandard_virtualizable(box):
             return True
         eqbox = self.metainterp.execute_and_record(rop.PTR_EQ, None,
                                                    box, standard_box)
         if isstandard:
             self.metainterp.replace_box(box, standard_box)
         else:
-            self.metainterp.nonstandard_virtualizables[box] = None
+            self.metainterp.heapcache.nonstandard_virtualizables_now_known(box)
         return not isstandard
 
     def _get_virtualizable_field_index(self, fielddescr):
     def opimpl_arraylen_vable(self, pc, box, fdescr, adescr):
         if self._nonstandard_virtualizable(pc, box):
             arraybox = self._opimpl_getfield_gc_any(box, fdescr)
-            return self.execute_with_descr(rop.ARRAYLEN_GC, adescr, arraybox)
+            return self.opimpl_arraylen_gc(arraybox, adescr)
         vinfo = self.metainterp.jitdriver_sd.virtualizable_info
         virtualizable_box = self.metainterp.virtualizable_boxes[-1]
         virtualizable = vinfo.unwrap_virtualizable_box(virtualizable_box)
     @arguments("orgpc", "box")
     def opimpl_guard_class(self, orgpc, box):
         clsbox = self.cls_of_box(box)
-        if box not in self.metainterp.known_class_boxes:
+        if not self.metainterp.heapcache.is_class_known(box):
             self.generate_guard(rop.GUARD_CLASS, box, [clsbox], resumepc=orgpc)
-            self.metainterp.known_class_boxes[box] = None
+            self.metainterp.heapcache.class_now_known(box)
         return clsbox
 
     @arguments("int", "orgpc")
         self.last_exc_value_box = None
         self.retracing_loop_from = None
         self.call_pure_results = args_dict_box()
-        # contains boxes where the class is already known
-        self.known_class_boxes = {}
-        # contains frame boxes that are not virtualizables
-        self.nonstandard_virtualizables = {}
-        # heap cache
-        # maps descrs to (from_box, to_box) tuples
-        self.heap_cache = {}
-        # heap array cache
-        # maps descrs to {index: (from_box, to_box)} dicts
-        self.heap_array_cache = {}
+        self.heapcache = HeapCache()
 
     def perform_call(self, jitcode, boxes, greenkey=None):
         # causes the metainterp to enter the given subfunction
         # record the operation
         profiler = self.staticdata.profiler
         profiler.count_ops(opnum, RECORDED_OPS)
-        self._invalidate_caches(opnum, descr)
+        self.heapcache.invalidate_caches(opnum, descr, argboxes)
         op = self.history.record(opnum, argboxes, resbox, descr)
         self.attach_debug_info(op)
         return resbox
 
-    def _invalidate_caches(self, opnum, descr):
-        if opnum == rop.SETFIELD_GC:
-            return
-        if opnum == rop.SETARRAYITEM_GC:
-            return
-        if rop._NOSIDEEFFECT_FIRST <= opnum <= rop._NOSIDEEFFECT_LAST:
-            return
-        if opnum == rop.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
-        if self.heap_cache:
-            self.heap_cache.clear()
-        if self.heap_array_cache:
-            self.heap_array_cache.clear()
 
     def attach_debug_info(self, op):
         if (not we_are_translated() and op is not None
                 duplicates[box] = None
 
     def reached_loop_header(self, greenboxes, redboxes, resumedescr):
-        self.known_class_boxes = {}
-        self.nonstandard_virtualizables = {} # XXX maybe not needed?
-        self.heap_cache = {}
-        self.heap_array_cache = {}
+        self.heapcache.reset()
 
         duplicates = {}
         self.remove_consts_and_duplicates(redboxes, len(redboxes),
             for i in range(len(boxes)):
                 if boxes[i] is oldbox:
                     boxes[i] = newbox
-        for descr, (frombox, tobox) in self.heap_cache.iteritems():
-            change = False
-            if frombox is oldbox:
-                change = True
-                frombox = newbox
-            if tobox is oldbox:
-                change = True
-                tobox = newbox
-            if change:
-                self.heap_cache[descr] = frombox, tobox
-        # XXX what about self.heap_array_cache?
+        self.heapcache.replace_box(oldbox, newbox)
 
     def find_biggest_function(self):
         start_stack = []

File pypy/jit/metainterp/test/test_heapcache.py

+from pypy.jit.metainterp.heapcache import HeapCache
+from pypy.jit.metainterp.resoperation import rop
+from pypy.jit.metainterp.history import ConstInt
+
+box1 = object()
+box2 = object()
+box3 = object()
+box4 = object()
+lengthbox1 = object()
+lengthbox2 = object()
+descr1 = object()
+descr2 = object()
+descr3 = object()
+
+index1 = ConstInt(0)
+index2 = ConstInt(1)
+
+
+class FakeEffektinfo(object):
+    EF_ELIDABLE_CANNOT_RAISE           = 0 #elidable function (and cannot raise)
+    EF_LOOPINVARIANT                   = 1 #special: call it only once per loop
+    EF_CANNOT_RAISE                    = 2 #a function which cannot raise
+    EF_ELIDABLE_CAN_RAISE              = 3 #elidable function (but can raise)
+    EF_CAN_RAISE                       = 4 #normal function (can raise)
+    EF_FORCES_VIRTUAL_OR_VIRTUALIZABLE = 5 #can raise and force virtualizables
+    EF_RANDOM_EFFECTS                  = 6 #can do whatever
+
+    OS_ARRAYCOPY = 0
+
+    def __init__(self, extraeffect, oopspecindex):
+        self.extraeffect = extraeffect
+        self.oopspecindex = oopspecindex
+
+class FakeCallDescr(object):
+    def __init__(self, extraeffect, oopspecindex=None):
+        self.extraeffect = extraeffect
+        self.oopspecindex = oopspecindex
+
+    def get_extra_info(self):
+        return FakeEffektinfo(self.extraeffect, self.oopspecindex)
+
+class TestHeapCache(object):
+    def test_known_class_box(self):
+        h = HeapCache()
+        assert not h.is_class_known(1)
+        assert not h.is_class_known(2)
+        h.class_now_known(1)
+        assert h.is_class_known(1)
+        assert not h.is_class_known(2)
+
+        h.reset()
+        assert not h.is_class_known(1)
+        assert not h.is_class_known(2)
+
+    def test_nonstandard_virtualizable(self):
+        h = HeapCache()
+        assert not h.is_nonstandard_virtualizable(1)
+        assert not h.is_nonstandard_virtualizable(2)
+        h.nonstandard_virtualizables_now_known(1)
+        assert h.is_nonstandard_virtualizable(1)
+        assert not h.is_nonstandard_virtualizable(2)
+
+        h.reset()
+        assert not h.is_nonstandard_virtualizable(1)
+        assert not h.is_nonstandard_virtualizable(2)
+
+
+    def test_heapcache_fields(self):
+        h = HeapCache()
+        assert h.getfield(box1, descr1) is None
+        assert h.getfield(box1, descr2) is None
+        h.setfield(box1, descr1, box2)
+        assert h.getfield(box1, descr1) is box2
+        assert h.getfield(box1, descr2) is None
+        h.setfield(box1, descr2, box3)
+        assert h.getfield(box1, descr1) is box2
+        assert h.getfield(box1, descr2) is box3
+        h.setfield(box1, descr1, box3)
+        assert h.getfield(box1, descr1) is box3
+        assert h.getfield(box1, descr2) is box3
+        h.setfield(box3, descr1, box1)
+        assert h.getfield(box3, descr1) is box1
+        assert h.getfield(box1, descr1) is None
+        assert h.getfield(box1, descr2) is box3
+
+        h.reset()
+        assert h.getfield(box1, descr1) is None
+        assert h.getfield(box1, descr2) is None
+        assert h.getfield(box3, descr1) is None
+
+    def test_heapcache_read_fields_multiple(self):
+        h = HeapCache()
+        h.getfield_now_known(box1, descr1, box2)
+        h.getfield_now_known(box3, descr1, box4)
+        assert h.getfield(box1, descr1) is box2
+        assert h.getfield(box1, descr2) is None
+        assert h.getfield(box3, descr1) is box4
+        assert h.getfield(box3, descr2) is None
+
+        h.reset()
+        assert h.getfield(box1, descr1) is None
+        assert h.getfield(box1, descr2) is None
+        assert h.getfield(box3, descr1) is None
+        assert h.getfield(box3, descr2) is None
+
+    def test_heapcache_write_fields_multiple(self):
+        h = HeapCache()
+        h.setfield(box1, descr1, box2)
+        assert h.getfield(box1, descr1) is box2
+        h.setfield(box3, descr1, box4)
+        assert h.getfield(box3, descr1) is box4
+        assert h.getfield(box1, descr1) is None # box1 and box3 can alias
+
+        h = HeapCache()
+        h.new(box1)
+        h.setfield(box1, descr1, box2)
+        assert h.getfield(box1, descr1) is box2
+        h.setfield(box3, descr1, box4)
+        assert h.getfield(box3, descr1) is box4
+        assert h.getfield(box1, descr1) is None # box1 and box3 can alias
+
+        h = HeapCache()
+        h.new(box1)
+        h.new(box3)
+        h.setfield(box1, descr1, box2)
+        assert h.getfield(box1, descr1) is box2
+        h.setfield(box3, descr1, box4)
+        assert h.getfield(box3, descr1) is box4
+        assert h.getfield(box1, descr1) is box2 # box1 and box3 cannot alias
+        h.setfield(box1, descr1, box3)
+        assert h.getfield(box1, descr1) is box3
+
+
+    def test_heapcache_arrays(self):
+        h = HeapCache()
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.getarrayitem(box1, descr1, index2) is None
+        assert h.getarrayitem(box1, descr2, index2) is None
+
+        h.setarrayitem(box1, descr1, index1, box2)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.getarrayitem(box1, descr1, index2) is None
+        assert h.getarrayitem(box1, descr2, index2) is None
+        h.setarrayitem(box1, descr1, index2, box4)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.getarrayitem(box1, descr1, index2) is box4
+        assert h.getarrayitem(box1, descr2, index2) is None
+
+        h.setarrayitem(box1, descr2, index1, box3)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr2, index1) is box3
+        assert h.getarrayitem(box1, descr1, index2) is box4
+        assert h.getarrayitem(box1, descr2, index2) is None
+
+        h.setarrayitem(box1, descr1, index1, box3)
+        assert h.getarrayitem(box1, descr1, index1) is box3
+        assert h.getarrayitem(box1, descr2, index1) is box3
+        assert h.getarrayitem(box1, descr1, index2) is box4
+        assert h.getarrayitem(box1, descr2, index2) is None
+
+        h.setarrayitem(box3, descr1, index1, box1)
+        assert h.getarrayitem(box3, descr1, index1) is box1
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr2, index1) is box3
+        assert h.getarrayitem(box1, descr1, index2) is box4
+        assert h.getarrayitem(box1, descr2, index2) is None
+
+        h.reset()
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.getarrayitem(box3, descr1, index1) is None
+
+    def test_heapcache_array_nonconst_index(self):
+        h = HeapCache()
+        h.setarrayitem(box1, descr1, index1, box2)
+        h.setarrayitem(box1, descr1, index2, box4)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr1, index2) is box4
+        h.setarrayitem(box1, descr1, box2, box3)
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr1, index2) is None
+
+    def test_heapcache_read_fields_multiple_array(self):
+        h = HeapCache()
+        h.getarrayitem_now_known(box1, descr1, index1, box2)
+        h.getarrayitem_now_known(box3, descr1, index1, box4)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.getarrayitem(box3, descr1, index1) is box4
+        assert h.getarrayitem(box3, descr2, index1) is None
+
+        h.reset()
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.getarrayitem(box3, descr1, index1) is None
+        assert h.getarrayitem(box3, descr2, index1) is None
+
+    def test_heapcache_write_fields_multiple_array(self):
+        h = HeapCache()
+        h.setarrayitem(box1, descr1, index1, box2)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        h.setarrayitem(box3, descr1, index1, box4)
+        assert h.getarrayitem(box3, descr1, index1) is box4
+        assert h.getarrayitem(box1, descr1, index1) is None # box1 and box3 can alias
+
+        h = HeapCache()
+        h.new(box1)
+        h.setarrayitem(box1, descr1, index1, box2)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        h.setarrayitem(box3, descr1, index1, box4)
+        assert h.getarrayitem(box3, descr1, index1) is box4
+        assert h.getarrayitem(box1, descr1, index1) is None # box1 and box3 can alias
+
+        h = HeapCache()
+        h.new(box1)
+        h.new(box3)
+        h.setarrayitem(box1, descr1, index1, box2)
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        h.setarrayitem(box3, descr1, index1, box4)
+        assert h.getarrayitem(box3, descr1, index1) is box4
+        assert h.getarrayitem(box1, descr1, index1) is box2 # box1 and box3 cannot alias
+        h.setarrayitem(box1, descr1, index1, box3)
+        assert h.getarrayitem(box3, descr1, index1) is box4
+        assert h.getarrayitem(box1, descr1, index1) is box3 # box1 and box3 cannot alias
+
+    def test_length_cache(self):
+        h = HeapCache()
+        h.new_array(box1, lengthbox1)
+        assert h.arraylen(box1) is lengthbox1
+
+        assert h.arraylen(box2) is None
+        h.arraylen_now_known(box2, lengthbox2)
+        assert h.arraylen(box2) is lengthbox2
+
+
+    def test_invalidate_cache(self):
+        h = HeapCache()
+        h.setfield(box1, descr1, box2)
+        h.setarrayitem(box1, descr1, index1, box2)
+        h.setarrayitem(box1, descr1, index2, box4)
+        h.invalidate_caches(rop.INT_ADD, None, [])
+        h.invalidate_caches(rop.INT_ADD_OVF, None, [])
+        h.invalidate_caches(rop.SETFIELD_RAW, None, [])
+        h.invalidate_caches(rop.SETARRAYITEM_RAW, None, [])
+        assert h.getfield(box1, descr1) is box2
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr1, index2) is box4
+
+        h.invalidate_caches(
+            rop.CALL, FakeCallDescr(FakeEffektinfo.EF_ELIDABLE_CANNOT_RAISE), [])
+        assert h.getfield(box1, descr1) is box2
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        assert h.getarrayitem(box1, descr1, index2) is box4
+
+        h.invalidate_caches(
+            rop.CALL_LOOPINVARIANT, FakeCallDescr(FakeEffektinfo.EF_LOOPINVARIANT), [])
+
+        h.invalidate_caches(
+            rop.CALL, FakeCallDescr(FakeEffektinfo.EF_RANDOM_EFFECTS), [])
+        assert h.getfield(box1, descr1) is None
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr1, index2) is None
+
+
+    def test_replace_box(self):
+        h = HeapCache()
+        h.setfield(box1, descr1, box2)
+        h.setfield(box1, descr2, box3)
+        h.setfield(box2, descr3, box3)
+        h.replace_box(box1, box4)
+        assert h.getfield(box1, descr1) is None
+        assert h.getfield(box1, descr2) is None
+        assert h.getfield(box4, descr1) is box2
+        assert h.getfield(box4, descr2) is box3
+        assert h.getfield(box2, descr3) is box3
+
+    def test_replace_box_array(self):
+        h = HeapCache()
+        h.setarrayitem(box1, descr1, index1, box2)
+        h.setarrayitem(box1, descr2, index1, box3)
+        h.arraylen_now_known(box1, lengthbox1)
+        h.setarrayitem(box2, descr1, index2, box1)
+        h.setarrayitem(box3, descr2, index2, box1)
+        h.setarrayitem(box2, descr3, index2, box3)
+        h.replace_box(box1, box4)
+        assert h.getarrayitem(box1, descr1, index1) is None
+        assert h.getarrayitem(box1, descr2, index1) is None
+        assert h.arraylen(box1) is None
+        assert h.arraylen(box4) is lengthbox1
+        assert h.getarrayitem(box4, descr1, index1) is box2
+        assert h.getarrayitem(box4, descr2, index1) is box3
+        assert h.getarrayitem(box2, descr1, index2) is box4
+        assert h.getarrayitem(box3, descr2, index2) is box4
+        assert h.getarrayitem(box2, descr3, index2) is box3
+
+        h.replace_box(lengthbox1, lengthbox2)
+        assert h.arraylen(box4) is lengthbox2
+
+    def test_ll_arraycopy(self):
+        h = HeapCache()
+        h.new_array(box1, lengthbox1)
+        h.setarrayitem(box1, descr1, index1, box2)
+        h.new_array(box2, lengthbox1)
+        # Just need the destination box for this call
+        h.invalidate_caches(
+            rop.CALL,
+            FakeCallDescr(FakeEffektinfo.EF_CANNOT_RAISE, FakeEffektinfo.OS_ARRAYCOPY),
+            [None, None, box2, None, None]
+        )
+        assert h.getarrayitem(box1, descr1, index1) is box2
+        h.invalidate_caches(
+            rop.CALL,
+            FakeCallDescr(FakeEffektinfo.EF_CANNOT_RAISE, FakeEffektinfo.OS_ARRAYCOPY),
+            [None, None, box3, None, None]
+        )
+        assert h.getarrayitem(box1, descr1, index1) is None
+
+        h.setarrayitem(box4, descr1, index1, box2)
+        assert h.getarrayitem(box4, descr1, index1) is box2
+        h.invalidate_caches(
+            rop.CALL,
+            FakeCallDescr(FakeEffektinfo.EF_CANNOT_RAISE, FakeEffektinfo.OS_ARRAYCOPY),
+            [None, None, box2, None, None]
+        )
+        assert h.getarrayitem(box4, descr1, index1) is None

File pypy/jit/metainterp/test/test_tracingopts.py

         self.check_operations_history(setarrayitem_gc=2, setfield_gc=2,
                                       getarrayitem_gc=0, getfield_gc=2)
 
+    def test_promote_changes_array_cache(self):
+        a1 = [0, 0]
+        a2 = [0, 0]
+        def fn(n):
+            if n > 0:
+                a = a1
+            else:
+                a = a2
+            a[0] = n
+            jit.hint(n, promote=True)
+            x1 = a[0]
+            jit.hint(x1, promote=True)
+            a[n - n] = n + 1
+            return a[0] + x1
+        res = self.interp_operations(fn, [7])
+        assert res == 7 + 7 + 1
+        self.check_operations_history(getarrayitem_gc=0, guard_value=1)
+        res = self.interp_operations(fn, [-7])
+        assert res == -7 - 7 + 1
+        self.check_operations_history(getarrayitem_gc=0, guard_value=1)
+
+
     def test_list_caching(self):
         a1 = [0, 0]
         a2 = [0, 0]
         assert res == f(10, 1, 1)
         self.check_history(getarrayitem_gc=0, getfield_gc=0)
 
-    def test_heap_caching_pure(self):
+    def test_heap_caching_array_pure(self):
         class A(object):
             pass
         p1 = A()
         assert res == -7 + 7
         self.check_operations_history(getfield_gc=0)
         return
+
+    def test_heap_caching_multiple_objects(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        class A(object):
+            pass
+        a1 = A()
+        g.a1 = a1
+        a1.x = 7
+        a2 = A()
+        g.a2 = a2
+        a2.x = 7
+        def gn(a1, a2):
+            return a1.x + a2.x
+        def fn(n):
+            if n < 0:
+                a1 = A()
+                g.a1 = a1
+                a1.x = n
+                a2 = A()
+                g.a2 = a2
+                a2.x = n - 1
+            else:
+                a1 = g.a1
+                a2 = g.a2
+            return a1.x + a2.x + gn(a1, a2)
+        res = self.interp_operations(fn, [-7])
+        assert res == 2 * -7 + 2 * -8
+        self.check_operations_history(setfield_gc=4, getfield_gc=0)
+        res = self.interp_operations(fn, [7])
+        assert res == 4 * 7
+        self.check_operations_history(getfield_gc=4)
+
+    def test_heap_caching_multiple_tuples(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        def gn(a1, a2):
+            return a1[0] + a2[0]
+        def fn(n):
+            a1 = (n, )
+            g.a = a1
+            a2 = (n - 1, )
+            g.a = a2
+            jit.promote(n)
+            return a1[0] + a2[0] + gn(a1, a2)
+        res = self.interp_operations(fn, [7])
+        assert res == 2 * 7 + 2 * 6
+        self.check_operations_history(getfield_gc_pure=0)
+        res = self.interp_operations(fn, [-7])
+        assert res == 2 * -7 + 2 * -8
+        self.check_operations_history(getfield_gc_pure=0)
+
+    def test_heap_caching_multiple_arrays(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        def fn(n):
+            a1 = [n, n, n]
+            g.a = a1
+            a1[0] = n
+            a2 = [n, n, n]
+            g.a = a2
+            a2[0] = n - 1
+            return a1[0] + a2[0] + a1[0] + a2[0]
+        res = self.interp_operations(fn, [7])
+        assert res == 2 * 7 + 2 * 6
+        self.check_operations_history(getarrayitem_gc=0)
+        res = self.interp_operations(fn, [-7])
+        assert res == 2 * -7 + 2 * -8
+        self.check_operations_history(getarrayitem_gc=0)
+
+    def test_heap_caching_multiple_arrays_getarrayitem(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        g.a1 = [7, 8, 9]
+        g.a2 = [8, 9, 10, 11]
+
+        def fn(i):
+            if i < 0:
+                g.a1 = [7, 8, 9]
+                g.a2 = [7, 8, 9, 10]
+            jit.promote(i)
+            a1 = g.a1
+            a1[i + 1] = 15 # make lists mutable
+            a2 = g.a2
+            a2[i + 1] = 19
+            return a1[i] + a2[i] + a1[i] + a2[i]
+        res = self.interp_operations(fn, [0])
+        assert res == 2 * 7 + 2 * 8
+        self.check_operations_history(getarrayitem_gc=2)
+
+
+    def test_heap_caching_multiple_lists(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        g.l = []
+        def fn(n):
+            if n < -100:
+                g.l.append(1)
+            a1 = [n, n, n]
+            g.l = a1
+            a1[0] = n
+            a2 = [n, n, n]
+            g.l = a2
+            a2[0] = n - 1
+            return a1[0] + a2[0] + a1[0] + a2[0]
+        res = self.interp_operations(fn, [7])
+        assert res == 2 * 7 + 2 * 6
+        self.check_operations_history(getarrayitem_gc=0, getfield_gc=0)
+        res = self.interp_operations(fn, [-7])
+        assert res == 2 * -7 + 2 * -8
+        self.check_operations_history(getarrayitem_gc=0, getfield_gc=0)
+
+    def test_length_caching(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        g.a = [0] * 7
+        def fn(n):
+            a = g.a
+            res = len(a) + len(a)
+            a1 = [0] * n
+            g.a = a1
+            return len(a1) + res
+        res = self.interp_operations(fn, [7])
+        assert res == 7 * 3
+        self.check_operations_history(arraylen_gc=1)
+
+    def test_arraycopy(self):
+        class Gbl(object):
+            pass
+        g = Gbl()
+        g.a = [0] * 7
+        def fn(n):
+            assert n >= 0
+            a = g.a
+            x = [0] * n
+            x[2] = 21
+            return len(a[:n]) + x[2]
+        res = self.interp_operations(fn, [3])
+        assert res == 24
+        self.check_operations_history(getarrayitem_gc=0)

File pypy/rlib/jit.py

 PARAMETERS = {'threshold': 1032, # just above 1024
               'function_threshold': 1617, # slightly more than one above
               'trace_eagerness': 200,
-              'trace_limit': 12000,
+              'trace_limit': 6000,
               'inlining': 1,
               'loop_longevity': 1000,
               'retrace_limit': 5,