1. Pypy
  2. Untitled project
  3. pypy

Commits

Carl Friedrich Bolz  committed 253569b

move optimizeopt tests from metainterp/tests to optimizeopt/test

  • Participants
  • Parent commits 14dc827
  • Branches default

Comments (0)

Files changed (4)

File rpython/jit/metainterp/optimizeopt/test/test_intbound.py

View file
+from rpython.jit.metainterp.optimizeopt.intutils import IntBound, IntUpperBound, \
+     IntLowerBound, IntUnbounded
+from copy import copy
+import sys
+from rpython.rlib.rarithmetic import LONG_BIT
+
+def bound(a,b):
+    if a is None and b is None:
+        return IntUnbounded()
+    elif a is None:
+        return IntUpperBound(b)
+    elif b is None:
+        return IntLowerBound(a)
+    else:
+        return IntBound(a,b)
+
+def const(a):
+    return bound(a,a)
+
+def some_bounds():
+    brd = [None] + range(-2, 3)
+    for lower in brd:
+        for upper in brd:
+            if lower is not None and upper is not None and lower > upper:
+                continue
+            yield (lower, upper, bound(lower, upper))
+
+nbr = range(-5, 6)
+
+def test_known():
+    for lower, upper, b in some_bounds():
+        inside = []
+        border = []
+        for n in nbr:
+            if (lower is None or n >= lower) and \
+               (upper is None or n <= upper):
+                if n == lower or n ==upper:
+                    border.append(n)
+                else:
+                    inside.append(n)
+                    
+        for n in nbr:
+            c = const(n)
+            if n in inside:
+                assert b.contains(n)
+                assert not b.known_lt(c)
+                assert not b.known_gt(c)
+                assert not b.known_le(c)
+                assert not b.known_ge(c)
+            elif n in border:
+                assert b.contains(n)
+                if n == upper:
+                    assert b.known_le(const(upper))
+                else:
+                    assert b.known_ge(const(lower))
+            else:
+                assert not b.contains(n)
+                some = (border + inside)[0]
+                if n < some:
+                    assert b.known_gt(c)
+                else:
+                    assert b.known_lt(c)
+
+
+def test_make():                            
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            lt = IntUnbounded()
+            lt.make_lt(b1)
+            lt.make_lt(b2)
+            for n in nbr:
+                c = const(n)
+                if b1.known_le(c) or b2.known_le(c):
+                    assert lt.known_lt(c)
+                else:
+                    assert not lt.known_lt(c)
+                assert not lt.known_gt(c)
+                assert not lt.known_ge(c)
+
+            gt = IntUnbounded()
+            gt.make_gt(b1)
+            gt.make_gt(b2)
+            for n in nbr:
+                c = const(n)
+                if b1.known_ge(c) or b2.known_ge(c):
+                    assert gt.known_gt(c)
+                else:
+                    assert not gt.known_gt(c)
+            assert not gt.known_lt(c)
+            assert not gt.known_le(c)
+
+            le = IntUnbounded()
+            le.make_le(b1)
+            le.make_le(b2)
+            for n in nbr:
+                c = const(n)
+                if b1.known_le(c) or b2.known_le(c):
+                    assert le.known_le(c)
+                else:
+                    assert not le.known_le(c)
+                assert not le.known_gt(c)
+                assert not le.known_ge(c)
+
+                
+            ge = IntUnbounded()
+            ge.make_ge(b1)
+            ge.make_ge(b2)
+            for n in nbr:
+                c = const(n)
+                if b1.known_ge(c) or b2.known_ge(c):
+                    assert ge.known_ge(c)
+                else:
+                    assert not ge.known_ge(c)
+                assert not ge.known_lt(c)
+                assert not ge.known_le(c)
+
+            gl = IntUnbounded()
+            gl.make_ge(b1)
+            gl.make_le(b2)
+            for n in nbr:
+                c = const(n)
+                if b1.known_ge(c):
+                    assert gl.known_ge(c)
+                else:
+                    assert not gl.known_ge(c)
+                    assert not gl.known_gt(c)
+                if  b2.known_le(c):
+                    assert gl.known_le(c)
+                else:
+                    assert not gl.known_le(c)
+                    assert not gl.known_lt(c)
+
+def test_intersect():                            
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            b = copy(b1)
+            b.intersect(b2)
+            for n in nbr:
+                if b1.contains(n) and b2.contains(n):
+                    assert b.contains(n)
+                else:
+                    assert not b.contains(n)
+                    
+def test_add():
+    for _, _, b1 in some_bounds():
+        for n1 in nbr:
+            b2 = b1.add(n1)
+            for n2 in nbr:
+                c1 = const(n2)
+                c2 = const(n2 + n1)
+                
+                if b1.known_le(c1):
+                    assert b2.known_le(c2)
+                else:
+                    assert not b2.known_le(c2)
+
+                if b1.known_ge(c1):
+                    assert b2.known_ge(c2)
+                else:
+                    assert not b2.known_ge(c2)
+
+                if b1.known_le(c1):
+                    assert b2.known_le(c2)
+                else:
+                    assert not b2.known_lt(c2)
+
+                if b1.known_lt(c1):
+                    assert b2.known_lt(c2)
+                else:
+                    assert not b2.known_lt(c2)
+
+                if b1.known_gt(c1):
+                    assert b2.known_gt(c2)
+                else:
+                    assert not b2.known_gt(c2)
+
+def test_add_bound():
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            b3 = b1.add_bound(b2)
+            for n1 in nbr:
+                for n2 in nbr:
+                    if b1.contains(n1) and b2.contains(n2):
+                        assert b3.contains(n1 + n2)
+
+    a=bound(2, 4).add_bound(bound(1, 2))
+    assert not a.contains(2)
+    assert not a.contains(7)
+
+def test_mul_bound():
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            b3 = b1.mul_bound(b2)
+            for n1 in nbr:
+                for n2 in nbr:
+                    if b1.contains(n1) and b2.contains(n2):
+                        assert b3.contains(n1 * n2)
+
+    a=bound(2, 4).mul_bound(bound(1, 2))
+    assert not a.contains(1)
+    assert not a.contains(9)
+
+    a=bound(-3, 2).mul_bound(bound(1, 2))
+    assert not a.contains(-7)
+    assert not a.contains(5)
+    assert a.contains(-6)
+    assert a.contains(4)
+
+    a=bound(-3, 2).mul(-1)
+    for i in range(-2,4):
+        assert a.contains(i)
+    assert not a.contains(4)
+    assert not a.contains(-3)
+
+def test_shift_bound():
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            bleft = b1.lshift_bound(b2)
+            bright = b1.rshift_bound(b2)
+            for n1 in nbr:
+                for n2 in range(10):
+                    if b1.contains(n1) and b2.contains(n2):
+                        assert bleft.contains(n1 << n2)
+                        assert bright.contains(n1 >> n2)
+
+def test_shift_overflow():
+    b10 = IntBound(0, 10)
+    b100 = IntBound(0, 100)
+    bmax = IntBound(0, sys.maxint/2)
+    assert not b10.lshift_bound(b100).has_upper
+    assert not bmax.lshift_bound(b10).has_upper
+    assert b10.lshift_bound(b10).has_upper
+
+    for b in (b10, b100, bmax, IntBound(0, 0)):
+        for shift_count_bound in (IntBound(7, LONG_BIT), IntBound(-7, 7)):
+            #assert not b.lshift_bound(shift_count_bound).has_upper
+            assert not b.rshift_bound(shift_count_bound).has_upper
+        
+    
+def test_div_bound():
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            b3 = b1.div_bound(b2)
+            for n1 in nbr:
+                for n2 in nbr:
+                    if b1.contains(n1) and b2.contains(n2):
+                        if n2 != 0:
+                            assert b3.contains(n1 / n2)
+
+    a=bound(2, 4).div_bound(bound(1, 2))
+    assert not a.contains(0)
+    assert not a.contains(5)
+
+    a=bound(-3, 2).div_bound(bound(1, 2))
+    assert not a.contains(-4)
+    assert not a.contains(3)
+    assert a.contains(-3)
+    assert a.contains(0)
+
+
+
+def test_sub_bound():
+    for _, _, b1 in some_bounds():
+        for _, _, b2 in some_bounds():
+            b3 = b1.sub_bound(b2)
+            for n1 in nbr:
+                for n2 in nbr:
+                    if b1.contains(n1) and b2.contains(n2):
+                        assert b3.contains(n1 - n2)
+
+    a=bound(2, 4).sub_bound(bound(1, 2))
+    assert not a.contains(-1)
+    assert not a.contains(4)

File rpython/jit/metainterp/optimizeopt/test/test_virtualstate.py

View file
+from __future__ import with_statement
+import py
+from rpython.jit.metainterp.optimize import InvalidLoop
+from rpython.jit.metainterp.optimizeopt.virtualstate import VirtualStateInfo, VStructStateInfo, \
+     VArrayStateInfo, NotVirtualStateInfo, VirtualState, ShortBoxes
+from rpython.jit.metainterp.optimizeopt.optimizer import OptValue
+from rpython.jit.metainterp.history import BoxInt, BoxFloat, BoxPtr, ConstInt, ConstPtr
+from rpython.rtyper.lltypesystem import lltype, llmemory
+from rpython.jit.metainterp.optimizeopt.test.test_util import LLtypeMixin, BaseTest, \
+                                                           equaloplists, FakeDescrWithSnapshot
+from rpython.jit.metainterp.optimizeopt.intutils import IntBound
+from rpython.jit.metainterp.history import TreeLoop, JitCellToken
+from rpython.jit.metainterp.optimizeopt.test.test_optimizeopt import FakeMetaInterpStaticData
+from rpython.jit.metainterp.resoperation import ResOperation, rop
+
+class TestBasic:
+    someptr1 = LLtypeMixin.myptr
+    someptr2 = LLtypeMixin.myptr2
+
+    def test_position_generalization(self):
+        def postest(info1, info2):
+            info1.position = 0
+            assert info1.generalization_of(info1, {}, {})
+            info2.position = 0
+            assert info1.generalization_of(info2, {}, {})
+            info2.position = 1
+            renum = {}
+            assert info1.generalization_of(info2, renum, {})
+            assert renum == {0:1}
+            assert info1.generalization_of(info2, {0:1}, {})
+            assert info1.generalization_of(info2, {1:1}, {})
+            bad = {}
+            assert not info1.generalization_of(info2, {0:0}, bad)
+            assert info1 in bad and info2 in bad
+
+        for BoxType in (BoxInt, BoxFloat, BoxPtr):
+            info1 = NotVirtualStateInfo(OptValue(BoxType()))
+            info2 = NotVirtualStateInfo(OptValue(BoxType()))
+            postest(info1, info2)
+            
+        info1, info2 = VArrayStateInfo(42), VArrayStateInfo(42)
+        info1.fieldstate = info2.fieldstate = []
+        postest(info1, info2)
+
+        info1, info2 = VStructStateInfo(42, []), VStructStateInfo(42, [])
+        info1.fieldstate = info2.fieldstate = []
+        postest(info1, info2)
+
+        info1, info2 = VirtualStateInfo(ConstInt(42), []), VirtualStateInfo(ConstInt(42), [])
+        info1.fieldstate = info2.fieldstate = []
+        postest(info1, info2)
+
+    def test_NotVirtualStateInfo_generalization(self):
+        def isgeneral(value1, value2):
+            info1 = NotVirtualStateInfo(value1)
+            info1.position = 0
+            info2 = NotVirtualStateInfo(value2)
+            info2.position = 0
+            return info1.generalization_of(info2, {}, {})
+
+        assert isgeneral(OptValue(BoxInt()), OptValue(ConstInt(7)))
+        assert not isgeneral(OptValue(ConstInt(7)), OptValue(BoxInt()))
+
+        ptr = OptValue(BoxPtr())
+        nonnull = OptValue(BoxPtr())
+        nonnull.make_nonnull(0)
+        knownclass = OptValue(BoxPtr())
+        knownclass.make_constant_class(ConstPtr(self.someptr1), 0)
+        const = OptValue(BoxPtr)
+        const.make_constant_class(ConstPtr(self.someptr1), 0)
+        const.make_constant(ConstPtr(self.someptr1))
+        inorder = [ptr, nonnull, knownclass, const]
+        for i in range(len(inorder)):
+            for j in range(i, len(inorder)):
+                assert isgeneral(inorder[i], inorder[j])
+                if i != j:
+                    assert not isgeneral(inorder[j], inorder[i])
+
+        value1 = OptValue(BoxInt())
+        value2 = OptValue(BoxInt())
+        value2.intbound.make_lt(IntBound(10, 10))
+        assert isgeneral(value1, value2)
+        assert not isgeneral(value2, value1)
+
+        assert isgeneral(OptValue(ConstInt(7)), OptValue(ConstInt(7)))
+        S = lltype.GcStruct('S')
+        foo = lltype.malloc(S)
+        fooref = lltype.cast_opaque_ptr(llmemory.GCREF, foo)
+        assert isgeneral(OptValue(ConstPtr(fooref)),
+                         OptValue(ConstPtr(fooref)))
+
+    def test_field_matching_generalization(self):
+        const1 = NotVirtualStateInfo(OptValue(ConstInt(1)))
+        const2 = NotVirtualStateInfo(OptValue(ConstInt(2)))
+        const1.position = const2.position = 1
+        assert not const1.generalization_of(const2, {}, {})
+        assert not const2.generalization_of(const1, {}, {})
+
+        def fldtst(info1, info2):
+            info1.position = info2.position = 0
+            info1.fieldstate = [const1]
+            info2.fieldstate = [const2]
+            assert not info1.generalization_of(info2, {}, {})
+            assert not info2.generalization_of(info1, {}, {})
+            assert info1.generalization_of(info1, {}, {})
+            assert info2.generalization_of(info2, {}, {})
+        fldtst(VArrayStateInfo(42), VArrayStateInfo(42))
+        fldtst(VStructStateInfo(42, [7]), VStructStateInfo(42, [7]))
+        fldtst(VirtualStateInfo(ConstInt(42), [7]), VirtualStateInfo(ConstInt(42), [7]))
+
+    def test_known_class_generalization(self):
+        knownclass1 = OptValue(BoxPtr())
+        knownclass1.make_constant_class(ConstPtr(self.someptr1), 0)
+        info1 = NotVirtualStateInfo(knownclass1)
+        info1.position = 0
+        knownclass2 = OptValue(BoxPtr())
+        knownclass2.make_constant_class(ConstPtr(self.someptr1), 0)
+        info2 = NotVirtualStateInfo(knownclass2)
+        info2.position = 0
+        assert info1.generalization_of(info2, {}, {})
+        assert info2.generalization_of(info1, {}, {})
+
+        knownclass3 = OptValue(BoxPtr())
+        knownclass3.make_constant_class(ConstPtr(self.someptr2), 0)
+        info3 = NotVirtualStateInfo(knownclass3)
+        info3.position = 0
+        assert not info1.generalization_of(info3, {}, {})
+        assert not info2.generalization_of(info3, {}, {})
+        assert not info3.generalization_of(info2, {}, {})
+        assert not info3.generalization_of(info1, {}, {})
+
+
+    def test_circular_generalization(self):
+        for info in (VArrayStateInfo(42), VStructStateInfo(42, [7]),
+                     VirtualStateInfo(ConstInt(42), [7])):
+            info.position = 0
+            info.fieldstate = [info]
+            assert info.generalization_of(info, {}, {})
+
+
+class BaseTestGenerateGuards(BaseTest):
+    def guards(self, info1, info2, box, expected):
+        info1.position = info2.position = 0
+        guards = []
+        info1.generate_guards(info2, box, self.cpu, guards, {})
+        self.compare(guards, expected, [box])
+
+    def compare(self, guards, expected, inputargs):
+        loop = self.parse(expected)
+        boxmap = {}
+        assert len(loop.inputargs) == len(inputargs)
+        for a, b in zip(loop.inputargs, inputargs):
+            boxmap[a] = b
+        for op in loop.operations:
+            if op.is_guard():
+                op.setdescr(None)
+        assert equaloplists(guards, loop.operations, False,
+                            boxmap)        
+    def test_intbounds(self):
+        value1 = OptValue(BoxInt())
+        value1.intbound.make_ge(IntBound(0, 10))
+        value1.intbound.make_le(IntBound(20, 30))
+        info1 = NotVirtualStateInfo(value1)
+        info2 = NotVirtualStateInfo(OptValue(BoxInt()))
+        expected = """
+        [i0]
+        i1 = int_ge(i0, 0)
+        guard_true(i1) []
+        i2 = int_le(i0, 30)
+        guard_true(i2) []
+        """
+        self.guards(info1, info2, BoxInt(15), expected)
+        py.test.raises(InvalidLoop, self.guards,
+                       info1, info2, BoxInt(50), expected)
+
+
+    def test_known_class(self):
+        value1 = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value1.make_constant_class(classbox, -1)
+        info1 = NotVirtualStateInfo(value1)
+        info2 = NotVirtualStateInfo(OptValue(self.nodebox))
+        expected = """
+        [p0]
+        guard_nonnull(p0) []        
+        guard_class(p0, ConstClass(node_vtable)) []
+        """
+        self.guards(info1, info2, self.nodebox, expected)
+        py.test.raises(InvalidLoop, self.guards,
+                       info1, info2, BoxPtr(), expected)
+
+    def test_known_class_value(self):
+        value1 = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value1.make_constant_class(classbox, -1)
+        box = self.nodebox
+        guards = value1.make_guards(box)
+        expected = """
+        [p0]
+        guard_nonnull(p0) []        
+        guard_class(p0, ConstClass(node_vtable)) []
+        """
+        self.compare(guards, expected, [box])
+
+    def test_equal_inputargs(self):
+        value = OptValue(self.nodebox)        
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        vstate1 = VirtualState([knownclass_info, knownclass_info])
+        assert vstate1.generalization_of(vstate1)
+
+        unknown_info1 = NotVirtualStateInfo(OptValue(self.nodebox))
+        vstate2 = VirtualState([unknown_info1, unknown_info1])
+        assert vstate2.generalization_of(vstate2)
+        assert not vstate1.generalization_of(vstate2)
+        assert vstate2.generalization_of(vstate1)
+
+        unknown_info1 = NotVirtualStateInfo(OptValue(self.nodebox))
+        unknown_info2 = NotVirtualStateInfo(OptValue(self.nodebox))
+        vstate3 = VirtualState([unknown_info1, unknown_info2])
+        assert vstate3.generalization_of(vstate2)
+        assert vstate3.generalization_of(vstate1)
+        assert not vstate2.generalization_of(vstate3)
+        assert not vstate1.generalization_of(vstate3)
+
+        expected = """
+        [p0]
+        guard_nonnull(p0) []        
+        guard_class(p0, ConstClass(node_vtable)) []
+        """
+        guards = []
+        vstate1.generate_guards(vstate2, [self.nodebox, self.nodebox], self.cpu, guards)
+        self.compare(guards, expected, [self.nodebox])
+
+        with py.test.raises(InvalidLoop):
+            guards = []
+            vstate1.generate_guards(vstate3, [self.nodebox, self.nodebox],
+                                    self.cpu, guards)
+        with py.test.raises(InvalidLoop):
+            guards = []
+            vstate2.generate_guards(vstate3, [self.nodebox, self.nodebox],
+                                    self.cpu, guards)
+        
+    def test_virtuals_with_equal_fields(self):
+        info1 = VirtualStateInfo(ConstInt(42), [1, 2])
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VirtualStateInfo(ConstInt(42), [1, 2])
+        unknown_info1 = NotVirtualStateInfo(OptValue(self.nodebox))
+        info2.fieldstate = [unknown_info1, unknown_info1]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+        assert not vstate1.generalization_of(vstate2)
+        assert vstate2.generalization_of(vstate1)
+
+        info3 = VirtualStateInfo(ConstInt(42), [1, 2])
+        unknown_info1 = NotVirtualStateInfo(OptValue(self.nodebox))
+        unknown_info2 = NotVirtualStateInfo(OptValue(self.nodebox))
+        info3.fieldstate = [unknown_info1, unknown_info2]
+        vstate3 = VirtualState([info3])        
+        assert vstate3.generalization_of(vstate2)
+        assert vstate3.generalization_of(vstate1)
+        assert not vstate2.generalization_of(vstate3)
+        assert not vstate1.generalization_of(vstate3)
+
+    def test_virtuals_with_nonmatching_fields(self):
+        info1 = VirtualStateInfo(ConstInt(42), [1, 2])
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VirtualStateInfo(ConstInt(42), [1, 2])
+        value = OptValue(self.nodebox2)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox2)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info2.fieldstate = [knownclass_info, knownclass_info]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+
+    def test_virtuals_with_nonmatching_descrs(self):
+        info1 = VirtualStateInfo(ConstInt(42), [10, 20])
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VirtualStateInfo(ConstInt(42), [1, 2])
+        value = OptValue(self.nodebox2)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox2)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info2.fieldstate = [knownclass_info, knownclass_info]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+        
+    def test_virtuals_with_nonmatching_classes(self):
+        info1 = VirtualStateInfo(ConstInt(42), [1, 2])
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VirtualStateInfo(ConstInt(7), [1, 2])
+        value = OptValue(self.nodebox2)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox2)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info2.fieldstate = [knownclass_info, knownclass_info]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+        
+    def test_nonvirtual_is_not_virtual(self):
+        info1 = VirtualStateInfo(ConstInt(42), [1, 2])
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = NotVirtualStateInfo(value)
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+
+    def test_arrays_with_nonmatching_fields(self):
+        info1 = VArrayStateInfo(42)
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VArrayStateInfo(42)
+        value = OptValue(self.nodebox2)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox2)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info2.fieldstate = [knownclass_info, knownclass_info]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+
+    def test_arrays_of_different_sizes(self):
+        info1 = VArrayStateInfo(42)
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VArrayStateInfo(42)
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info2.fieldstate = [knownclass_info]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+
+    def test_arrays_with_nonmatching_types(self):
+        info1 = VArrayStateInfo(42)
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = VArrayStateInfo(7)
+        value = OptValue(self.nodebox2)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox2)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info2.fieldstate = [knownclass_info, knownclass_info]
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+        
+    def test_nonvirtual_is_not_array(self):
+        info1 = VArrayStateInfo(42)
+        value = OptValue(self.nodebox)
+        classbox = self.cpu.ts.cls_of_box(self.nodebox)
+        value.make_constant_class(classbox, -1)
+        knownclass_info = NotVirtualStateInfo(value)
+        info1.fieldstate = [knownclass_info, knownclass_info]
+        vstate1 = VirtualState([info1])
+        assert vstate1.generalization_of(vstate1)
+
+        info2 = NotVirtualStateInfo(value)
+        vstate2 = VirtualState([info2])
+        assert vstate2.generalization_of(vstate2)
+
+        assert not vstate2.generalization_of(vstate1)
+        assert not vstate1.generalization_of(vstate2)
+        
+
+class BaseTestBridges(BaseTest):
+    enable_opts = "intbounds:rewrite:virtualize:string:pure:heap:unroll"
+
+    def _do_optimize_bridge(self, bridge, call_pure_results):
+        from rpython.jit.metainterp.optimizeopt import optimize_trace
+        from rpython.jit.metainterp.optimizeopt.util import args_dict
+
+        self.bridge = bridge
+        bridge.call_pure_results = args_dict()
+        if call_pure_results is not None:
+            for k, v in call_pure_results.items():
+                bridge.call_pure_results[list(k)] = v
+        metainterp_sd = FakeMetaInterpStaticData(self.cpu)
+        if hasattr(self, 'vrefinfo'):
+            metainterp_sd.virtualref_info = self.vrefinfo
+        if hasattr(self, 'callinfocollection'):
+            metainterp_sd.callinfocollection = self.callinfocollection
+        #
+        bridge.resume_at_jump_descr = FakeDescrWithSnapshot()
+        optimize_trace(metainterp_sd, bridge, self.enable_opts)
+
+        
+    def optimize_bridge(self, loops, bridge, expected, expected_target='Loop', **boxvalues):
+        if isinstance(loops, str):
+            loops = (loops, )
+        loops = [self.parse(loop) for loop in loops]
+        bridge = self.parse(bridge)
+        for loop in loops:
+            loop.preamble = self.unroll_and_optimize(loop)
+        preamble = loops[0].preamble
+        token = JitCellToken()
+        token.target_tokens = [l.operations[0].getdescr() for l in [preamble] + loops]
+
+        boxes = {}
+        for b in bridge.inputargs + [op.result for op in bridge.operations]:
+            boxes[str(b)] = b
+        for b, v in boxvalues.items():
+            boxes[b].value = v
+        bridge.operations[-1].setdescr(token)
+        self._do_optimize_bridge(bridge, None)
+        if bridge.operations[-1].getopnum() == rop.LABEL:
+            assert expected == 'RETRACE'
+            return
+
+        print '\n'.join([str(o) for o in bridge.operations])
+        expected = self.parse(expected)
+        self.assert_equal(bridge, expected)
+
+        if expected_target == 'Preamble':
+            assert bridge.operations[-1].getdescr() is preamble.operations[0].getdescr()
+        elif expected_target == 'Loop':
+            assert len(loops) == 1
+            assert bridge.operations[-1].getdescr() is loops[0].operations[0].getdescr()
+        elif expected_target.startswith('Loop'):
+            n = int(expected_target[4:])
+            assert bridge.operations[-1].getdescr() is loops[n].operations[0].getdescr()
+        else:
+            assert False
+
+    def test_nonnull(self):
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE', p0=self.nullptr)
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+        self.optimize_bridge(loop, expected, expected, p0=self.myptr)
+        self.optimize_bridge(loop, expected, expected, p0=self.nullptr)
+
+    def test_cached_nonnull(self):
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p1) []
+        call(p1, descr=nonwritedescr)
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p1) []
+        jump(p0, p1)
+        """
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+
+    def test_cached_unused_nonnull(self):        
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p1) []
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p1) []
+        jump(p0)
+        """        
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+
+    def test_cached_invalid_nonnull(self):        
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p1) []
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_value(p1, ConstPtr(nullptr)) []        
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, bridge, 'Preamble', p0=self.myptr)
+
+    def test_multiple_nonnull(self):
+        loops = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        jump(p0)
+        """, """
+        [p0]
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        jump(p0)
+        """
+        self.optimize_bridge(loops, bridge, expected, 'Loop1', p0=self.nullptr)
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        jump(p0)
+        """
+        self.optimize_bridge(loops, bridge, expected, 'Loop0', p0=self.myptr)
+
+    def test_constant(self):
+        loops = """
+        [p0]
+        p1 = same_as(ConstPtr(myptr))
+        jump(p1)
+        """, """
+        [p0]
+        p1 = same_as(ConstPtr(myptr2))
+        jump(p1)
+        """, """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        jump()
+        """
+        self.optimize_bridge(loops, loops[0], expected, 'Loop0')
+        self.optimize_bridge(loops, loops[1], expected, 'Loop1')
+        expected = """
+        [p0]
+        jump(p0)
+        """
+        self.optimize_bridge(loops, loops[2], expected, 'Loop2')
+
+    def test_cached_constant(self):
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_value(p1, ConstPtr(myptr)) []
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_value(p1, ConstPtr(myptr)) []       
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+
+    def test_virtual(self):
+        loops = """
+        [p0, p1]
+        p2 = new_with_vtable(ConstClass(node_vtable))
+        setfield_gc(p2, p1, descr=nextdescr)
+        setfield_gc(p2, 7, descr=adescr)
+        setfield_gc(p2, 42, descr=bdescr)
+        jump(p2, p1)
+        ""","""
+        [p0, p1]
+        p2 = new_with_vtable(ConstClass(node_vtable))
+        setfield_gc(p2, p1, descr=nextdescr)
+        setfield_gc(p2, 9, descr=adescr)
+        jump(p2, p1)
+        """
+        expected = """
+        [p0, p1]
+        jump(p1)
+        """
+        self.optimize_bridge(loops, loops[0], expected, 'Loop0')
+        self.optimize_bridge(loops, loops[1], expected, 'Loop1')
+        bridge = """
+        [p0, p1]
+        p2 = new_with_vtable(ConstClass(node_vtable))
+        setfield_gc(p2, p1, descr=nextdescr)
+        setfield_gc(p2, 42, descr=adescr)
+        setfield_gc(p2, 7, descr=bdescr)
+        jump(p2, p1)
+        """
+        self.optimize_bridge(loops, bridge, "RETRACE")
+        bridge = """
+        [p0, p1]
+        p2 = new_with_vtable(ConstClass(node_vtable))
+        setfield_gc(p2, p1, descr=nextdescr)
+        setfield_gc(p2, 7, descr=adescr)
+        jump(p2, p1)
+        """
+        self.optimize_bridge(loops, bridge, "RETRACE")
+
+    def test_known_class(self):
+        loops = """
+        [p0]
+        guard_nonnull_class(p0, ConstClass(node_vtable)) []
+        jump(p0)
+        ""","""
+        [p0]
+        guard_nonnull_class(p0, ConstClass(node_vtable2)) []
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        self.optimize_bridge(loops, bridge, loops[0], 'Loop0', p0=self.nodebox.value)
+        self.optimize_bridge(loops, bridge, loops[1], 'Loop1', p0=self.nodebox2.value)
+        self.optimize_bridge(loops[0], bridge, 'RETRACE', p0=self.nodebox2.value)
+        self.optimize_bridge(loops, loops[0], loops[0], 'Loop0', p0=self.nullptr)
+        self.optimize_bridge(loops, loops[1], loops[1], 'Loop1', p0=self.nullptr)
+
+    def test_cached_known_class(self):
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_class(p1, ConstClass(node_vtable)) []
+        jump(p0)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull_class(p1, ConstClass(node_vtable)) []
+        jump(p0)        
+        """
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+
+
+    def test_lenbound_array(self):
+        loop = """
+        [p0]
+        i2 = getarrayitem_gc(p0, 10, descr=arraydescr)
+        call(i2, descr=nonwritedescr)
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        i2 = getarrayitem_gc(p0, 10, descr=arraydescr)
+        call(i2, descr=nonwritedescr)
+        jump(p0, i2)
+        """
+        self.optimize_bridge(loop, loop, expected, 'Loop0')
+        bridge = """
+        [p0]
+        i2 = getarrayitem_gc(p0, 15, descr=arraydescr)
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        i2 = getarrayitem_gc(p0, 15, descr=arraydescr)
+        i3 = getarrayitem_gc(p0, 10, descr=arraydescr)
+        jump(p0, i3)
+        """        
+        self.optimize_bridge(loop, bridge, expected, 'Loop0')
+        bridge = """
+        [p0]
+        i2 = getarrayitem_gc(p0, 5, descr=arraydescr)
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE')
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE')
+
+    def test_cached_lenbound_array(self):
+        loop = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        i2 = getarrayitem_gc(p1, 10, descr=arraydescr)
+        call(i2, descr=nonwritedescr)
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        i2 = getarrayitem_gc(p1, 10, descr=arraydescr)
+        call(i2, descr=nonwritedescr)
+        i3 = arraylen_gc(p1, descr=arraydescr) # Should be killed by backend
+        jump(p0, i2, p1)
+        """
+        self.optimize_bridge(loop, loop, expected)
+        bridge = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        i2 = getarrayitem_gc(p1, 15, descr=arraydescr)
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        i2 = getarrayitem_gc(p1, 15, descr=arraydescr)
+        i3 = arraylen_gc(p1, descr=arraydescr) # Should be killed by backend        
+        i4 = getarrayitem_gc(p1, 10, descr=arraydescr)
+        jump(p0, i4, p1)
+        """        
+        self.optimize_bridge(loop, bridge, expected)
+        bridge = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        i2 = getarrayitem_gc(p1, 5, descr=arraydescr)
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        p1 = getfield_gc(p0, descr=nextdescr)
+        i2 = getarrayitem_gc(p1, 5, descr=arraydescr)
+        i3 = arraylen_gc(p1, descr=arraydescr) # Should be killed by backend
+        i4 = int_ge(i3, 11)
+        guard_true(i4) []
+        i5 = getarrayitem_gc(p1, 10, descr=arraydescr)
+        jump(p0, i5, p1)
+        """        
+        self.optimize_bridge(loop, bridge, expected)
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        p1 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p1) []
+        i3 = arraylen_gc(p1, descr=arraydescr) # Should be killed by backend
+        i4 = int_ge(i3, 11)
+        guard_true(i4) []
+        i5 = getarrayitem_gc(p1, 10, descr=arraydescr)
+        jump(p0, i5, p1)
+        """        
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+
+    def test_cached_setarrayitem_gc(self):
+        loop = """
+        [p0, p1]
+        p2 = getfield_gc(p0, descr=nextdescr)
+        pp = getarrayitem_gc(p2, 0, descr=arraydescr)
+        call(pp, descr=nonwritedescr)
+        p3 = getfield_gc(p1, descr=nextdescr)
+        setarrayitem_gc(p2, 0, p3, descr=arraydescr)
+        jump(p0, p3)
+        """
+        bridge = """
+        [p0, p1]
+        jump(p0, p1)
+        """
+        expected = """
+        [p0, p1]
+        guard_nonnull(p0) []
+        p2 = getfield_gc(p0, descr=nextdescr)
+        guard_nonnull(p2) []
+        i5 = arraylen_gc(p2, descr=arraydescr)
+        i6 = int_ge(i5, 1)
+        guard_true(i6) []
+        p3 = getarrayitem_gc(p2, 0, descr=arraydescr)
+        jump(p0, p1, p3, p2)
+        """
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)
+
+    def test_cache_constant_setfield(self):
+        loop = """
+        [p5]
+        i10 = getfield_gc(p5, descr=valuedescr)
+        call(i10, descr=nonwritedescr) 
+        setfield_gc(p5, 1, descr=valuedescr)
+        jump(p5)
+        """
+        bridge = """
+        [p0]
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        guard_nonnull(p0) []
+        i10 = getfield_gc(p0, descr=valuedescr)
+        guard_value(i10, 1) []
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, expected, p0=self.myptr)        
+        bridge = """
+        [p0]
+        setfield_gc(p0, 7, descr=valuedescr)
+        jump(p0)
+        """
+        expected = """
+        [p0]
+        setfield_gc(p0, 7, descr=valuedescr)
+        jump(p0)
+        """
+        self.optimize_bridge(loop, bridge, expected, 'Preamble', p0=self.myptr)
+
+    def test_cached_equal_fields(self):
+        loop = """
+        [p5, p6]
+        i10 = getfield_gc(p5, descr=valuedescr)
+        i11 = getfield_gc(p6, descr=nextdescr)
+        call(i10, i11, descr=nonwritedescr)
+        setfield_gc(p6, i10, descr=nextdescr)        
+        jump(p5, p6)
+        """
+        bridge = """
+        [p5, p6]
+        jump(p5, p6)
+        """
+        expected = """
+        [p5, p6]
+        guard_nonnull(p5) []
+        guard_nonnull(p6) []
+        i10 = getfield_gc(p5, descr=valuedescr)
+        i11 = getfield_gc(p6, descr=nextdescr)
+        jump(p5, p6, i10, i11)
+        """
+        self.optimize_bridge(loop, bridge, expected, p5=self.myptr, p6=self.myptr2)
+
+    def test_licm_boxed_opaque_getitem(self):
+        loop = """
+        [p1]
+        p2 = getfield_gc(p1, descr=nextdescr) 
+        mark_opaque_ptr(p2)        
+        guard_class(p2,  ConstClass(node_vtable)) []
+        i3 = getfield_gc(p2, descr=otherdescr)
+        i4 = call(i3, descr=nonwritedescr)
+        jump(p1)
+        """
+        bridge = """
+        [p1]
+        guard_nonnull(p1) []
+        jump(p1)
+        """
+        expected = """
+        [p1]
+        guard_nonnull(p1) []
+        p2 = getfield_gc(p1, descr=nextdescr)
+        jump(p1)
+        """        
+        self.optimize_bridge(loop, bridge, expected, 'Preamble')
+        
+        bridge = """
+        [p1]
+        p2 = getfield_gc(p1, descr=nextdescr) 
+        guard_class(p2,  ConstClass(node_vtable2)) []
+        jump(p1)
+        """
+        expected = """
+        [p1]
+        p2 = getfield_gc(p1, descr=nextdescr) 
+        guard_class(p2,  ConstClass(node_vtable2)) []
+        jump(p1)
+        """
+        self.optimize_bridge(loop, bridge, expected, 'Preamble')
+
+        bridge = """
+        [p1]
+        p2 = getfield_gc(p1, descr=nextdescr) 
+        guard_class(p2,  ConstClass(node_vtable)) []
+        jump(p1)
+        """
+        expected = """
+        [p1]
+        p2 = getfield_gc(p1, descr=nextdescr) 
+        guard_class(p2,  ConstClass(node_vtable)) []
+        i3 = getfield_gc(p2, descr=otherdescr)
+        jump(p1, i3)
+        """
+        self.optimize_bridge(loop, bridge, expected, 'Loop')
+
+    def test_licm_unboxed_opaque_getitem(self):
+        loop = """
+        [p2]
+        mark_opaque_ptr(p2)        
+        guard_class(p2,  ConstClass(node_vtable)) []
+        i3 = getfield_gc(p2, descr=otherdescr)
+        i4 = call(i3, descr=nonwritedescr)
+        jump(p2)
+        """
+        bridge = """
+        [p1]
+        guard_nonnull(p1) []
+        jump(p1)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE', p1=self.myptr)
+        self.optimize_bridge(loop, bridge, 'RETRACE', p1=self.myptr2)
+        
+        bridge = """
+        [p2]
+        guard_class(p2,  ConstClass(node_vtable2)) []
+        jump(p2)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE')
+
+        bridge = """
+        [p2]
+        guard_class(p2,  ConstClass(node_vtable)) []
+        jump(p2)
+        """
+        expected = """
+        [p2]
+        guard_class(p2,  ConstClass(node_vtable)) []
+        i3 = getfield_gc(p2, descr=otherdescr)
+        jump(p2, i3)
+        """
+        self.optimize_bridge(loop, bridge, expected, 'Loop')
+
+    def test_licm_virtual_opaque_getitem(self):
+        loop = """
+        [p1]
+        p2 = getfield_gc(p1, descr=nextdescr) 
+        mark_opaque_ptr(p2)        
+        guard_class(p2,  ConstClass(node_vtable)) []
+        i3 = getfield_gc(p2, descr=otherdescr)
+        i4 = call(i3, descr=nonwritedescr)
+        p3 = new_with_vtable(ConstClass(node_vtable))
+        setfield_gc(p3, p2, descr=nextdescr)
+        jump(p3)
+        """
+        bridge = """
+        [p1]
+        p3 = new_with_vtable(ConstClass(node_vtable))
+        setfield_gc(p3, p1, descr=nextdescr)
+        jump(p3)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE', p1=self.myptr)
+        self.optimize_bridge(loop, bridge, 'RETRACE', p1=self.myptr2)
+
+        bridge = """
+        [p1]
+        p3 = new_with_vtable(ConstClass(node_vtable))
+        guard_class(p1,  ConstClass(node_vtable2)) []
+        setfield_gc(p3, p1, descr=nextdescr)
+        jump(p3)
+        """
+        self.optimize_bridge(loop, bridge, 'RETRACE')
+
+        bridge = """
+        [p1]
+        p3 = new_with_vtable(ConstClass(node_vtable))
+        guard_class(p1,  ConstClass(node_vtable)) []
+        setfield_gc(p3, p1, descr=nextdescr)
+        jump(p3)
+        """
+        expected = """
+        [p1]
+        guard_class(p1,  ConstClass(node_vtable)) []
+        i3 = getfield_gc(p1, descr=otherdescr)
+        jump(p1, i3)
+        """
+        self.optimize_bridge(loop, bridge, expected)
+
+
+class TestLLtypeGuards(BaseTestGenerateGuards, LLtypeMixin):
+    pass
+
+class TestLLtypeBridges(BaseTestBridges, LLtypeMixin):
+    pass
+
+class FakeOptimizer:
+    def __init__(self):
+        self.opaque_pointers = {}
+        self.values = {}
+    def make_equal_to(*args):
+        pass
+    def getvalue(*args):
+        pass
+    def emit_operation(*args):
+        pass
+
+
+class TestShortBoxes:
+    p1 = BoxPtr()
+    p2 = BoxPtr()
+    p3 = BoxPtr()
+    p4 = BoxPtr()
+    i1 = BoxInt()
+    i2 = BoxInt()
+    i3 = BoxInt()
+    i4 = BoxInt()
+    
+    def test_short_box_duplication_direct(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1))
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes) == 4
+        assert self.i1 in sb.short_boxes
+        assert sum([op.result is self.i1 for op in sb.short_boxes.values() if op]) == 1
+
+    def test_dont_duplicate_potential_boxes(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1))
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [BoxPtr()], self.i1))
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+                sb.add_potential(ResOperation(rop.INT_ADD, [ConstInt(7), self.i2],
+                                              self.i3))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes) == 5
+
+    def test_prioritize1(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1))
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1))
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) in [self.p1, self.p2]
+
+    def test_prioritize1bis(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1),
+                                 synthetic=True)
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1),
+                                 synthetic=True)
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) in [self.p1, self.p2]
+        
+    def test_prioritize2(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1),
+                                 synthetic=True)
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1))
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) == self.p2
+        
+    def test_prioritize3(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1))
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1),
+                                 synthetic=True)
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) == self.p1

File rpython/jit/metainterp/test/test_intbound.py

-from rpython.jit.metainterp.optimizeopt.intutils import IntBound, IntUpperBound, \
-     IntLowerBound, IntUnbounded
-from copy import copy
-import sys
-from rpython.rlib.rarithmetic import LONG_BIT
-
-def bound(a,b):
-    if a is None and b is None:
-        return IntUnbounded()
-    elif a is None:
-        return IntUpperBound(b)
-    elif b is None:
-        return IntLowerBound(a)
-    else:
-        return IntBound(a,b)
-
-def const(a):
-    return bound(a,a)
-
-def some_bounds():
-    brd = [None] + range(-2, 3)
-    for lower in brd:
-        for upper in brd:
-            if lower is not None and upper is not None and lower > upper:
-                continue
-            yield (lower, upper, bound(lower, upper))
-
-nbr = range(-5, 6)
-
-def test_known():
-    for lower, upper, b in some_bounds():
-        inside = []
-        border = []
-        for n in nbr:
-            if (lower is None or n >= lower) and \
-               (upper is None or n <= upper):
-                if n == lower or n ==upper:
-                    border.append(n)
-                else:
-                    inside.append(n)
-                    
-        for n in nbr:
-            c = const(n)
-            if n in inside:
-                assert b.contains(n)
-                assert not b.known_lt(c)
-                assert not b.known_gt(c)
-                assert not b.known_le(c)
-                assert not b.known_ge(c)
-            elif n in border:
-                assert b.contains(n)
-                if n == upper:
-                    assert b.known_le(const(upper))
-                else:
-                    assert b.known_ge(const(lower))
-            else:
-                assert not b.contains(n)
-                some = (border + inside)[0]
-                if n < some:
-                    assert b.known_gt(c)
-                else:
-                    assert b.known_lt(c)
-
-
-def test_make():                            
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            lt = IntUnbounded()
-            lt.make_lt(b1)
-            lt.make_lt(b2)
-            for n in nbr:
-                c = const(n)
-                if b1.known_le(c) or b2.known_le(c):
-                    assert lt.known_lt(c)
-                else:
-                    assert not lt.known_lt(c)
-                assert not lt.known_gt(c)
-                assert not lt.known_ge(c)
-
-            gt = IntUnbounded()
-            gt.make_gt(b1)
-            gt.make_gt(b2)
-            for n in nbr:
-                c = const(n)
-                if b1.known_ge(c) or b2.known_ge(c):
-                    assert gt.known_gt(c)
-                else:
-                    assert not gt.known_gt(c)
-            assert not gt.known_lt(c)
-            assert not gt.known_le(c)
-
-            le = IntUnbounded()
-            le.make_le(b1)
-            le.make_le(b2)
-            for n in nbr:
-                c = const(n)
-                if b1.known_le(c) or b2.known_le(c):
-                    assert le.known_le(c)
-                else:
-                    assert not le.known_le(c)
-                assert not le.known_gt(c)
-                assert not le.known_ge(c)
-
-                
-            ge = IntUnbounded()
-            ge.make_ge(b1)
-            ge.make_ge(b2)
-            for n in nbr:
-                c = const(n)
-                if b1.known_ge(c) or b2.known_ge(c):
-                    assert ge.known_ge(c)
-                else:
-                    assert not ge.known_ge(c)
-                assert not ge.known_lt(c)
-                assert not ge.known_le(c)
-
-            gl = IntUnbounded()
-            gl.make_ge(b1)
-            gl.make_le(b2)
-            for n in nbr:
-                c = const(n)
-                if b1.known_ge(c):
-                    assert gl.known_ge(c)
-                else:
-                    assert not gl.known_ge(c)
-                    assert not gl.known_gt(c)
-                if  b2.known_le(c):
-                    assert gl.known_le(c)
-                else:
-                    assert not gl.known_le(c)
-                    assert not gl.known_lt(c)
-
-def test_intersect():                            
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            b = copy(b1)
-            b.intersect(b2)
-            for n in nbr:
-                if b1.contains(n) and b2.contains(n):
-                    assert b.contains(n)
-                else:
-                    assert not b.contains(n)
-                    
-def test_add():
-    for _, _, b1 in some_bounds():
-        for n1 in nbr:
-            b2 = b1.add(n1)
-            for n2 in nbr:
-                c1 = const(n2)
-                c2 = const(n2 + n1)
-                
-                if b1.known_le(c1):
-                    assert b2.known_le(c2)
-                else:
-                    assert not b2.known_le(c2)
-
-                if b1.known_ge(c1):
-                    assert b2.known_ge(c2)
-                else:
-                    assert not b2.known_ge(c2)
-
-                if b1.known_le(c1):
-                    assert b2.known_le(c2)
-                else:
-                    assert not b2.known_lt(c2)
-
-                if b1.known_lt(c1):
-                    assert b2.known_lt(c2)
-                else:
-                    assert not b2.known_lt(c2)
-
-                if b1.known_gt(c1):
-                    assert b2.known_gt(c2)
-                else:
-                    assert not b2.known_gt(c2)
-
-def test_add_bound():
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            b3 = b1.add_bound(b2)
-            for n1 in nbr:
-                for n2 in nbr:
-                    if b1.contains(n1) and b2.contains(n2):
-                        assert b3.contains(n1 + n2)
-
-    a=bound(2, 4).add_bound(bound(1, 2))
-    assert not a.contains(2)
-    assert not a.contains(7)
-
-def test_mul_bound():
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            b3 = b1.mul_bound(b2)
-            for n1 in nbr:
-                for n2 in nbr:
-                    if b1.contains(n1) and b2.contains(n2):
-                        assert b3.contains(n1 * n2)
-
-    a=bound(2, 4).mul_bound(bound(1, 2))
-    assert not a.contains(1)
-    assert not a.contains(9)
-
-    a=bound(-3, 2).mul_bound(bound(1, 2))
-    assert not a.contains(-7)
-    assert not a.contains(5)
-    assert a.contains(-6)
-    assert a.contains(4)
-
-    a=bound(-3, 2).mul(-1)
-    for i in range(-2,4):
-        assert a.contains(i)
-    assert not a.contains(4)
-    assert not a.contains(-3)
-
-def test_shift_bound():
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            bleft = b1.lshift_bound(b2)
-            bright = b1.rshift_bound(b2)
-            for n1 in nbr:
-                for n2 in range(10):
-                    if b1.contains(n1) and b2.contains(n2):
-                        assert bleft.contains(n1 << n2)
-                        assert bright.contains(n1 >> n2)
-
-def test_shift_overflow():
-    b10 = IntBound(0, 10)
-    b100 = IntBound(0, 100)
-    bmax = IntBound(0, sys.maxint/2)
-    assert not b10.lshift_bound(b100).has_upper
-    assert not bmax.lshift_bound(b10).has_upper
-    assert b10.lshift_bound(b10).has_upper
-
-    for b in (b10, b100, bmax, IntBound(0, 0)):
-        for shift_count_bound in (IntBound(7, LONG_BIT), IntBound(-7, 7)):
-            #assert not b.lshift_bound(shift_count_bound).has_upper
-            assert not b.rshift_bound(shift_count_bound).has_upper
-        
-    
-def test_div_bound():
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            b3 = b1.div_bound(b2)
-            for n1 in nbr:
-                for n2 in nbr:
-                    if b1.contains(n1) and b2.contains(n2):
-                        if n2 != 0:
-                            assert b3.contains(n1 / n2)
-
-    a=bound(2, 4).div_bound(bound(1, 2))
-    assert not a.contains(0)
-    assert not a.contains(5)
-
-    a=bound(-3, 2).div_bound(bound(1, 2))
-    assert not a.contains(-4)
-    assert not a.contains(3)
-    assert a.contains(-3)
-    assert a.contains(0)
-
-
-
-def test_sub_bound():
-    for _, _, b1 in some_bounds():
-        for _, _, b2 in some_bounds():
-            b3 = b1.sub_bound(b2)
-            for n1 in nbr:
-                for n2 in nbr:
-                    if b1.contains(n1) and b2.contains(n2):
-                        assert b3.contains(n1 - n2)
-
-    a=bound(2, 4).sub_bound(bound(1, 2))
-    assert not a.contains(-1)
-    assert not a.contains(4)

File rpython/jit/metainterp/test/test_virtualstate.py

-from __future__ import with_statement
-import py
-from rpython.jit.metainterp.optimize import InvalidLoop
-from rpython.jit.metainterp.optimizeopt.virtualstate import VirtualStateInfo, VStructStateInfo, \
-     VArrayStateInfo, NotVirtualStateInfo, VirtualState, ShortBoxes
-from rpython.jit.metainterp.optimizeopt.optimizer import OptValue
-from rpython.jit.metainterp.history import BoxInt, BoxFloat, BoxPtr, ConstInt, ConstPtr
-from rpython.rtyper.lltypesystem import lltype, llmemory
-from rpython.jit.metainterp.optimizeopt.test.test_util import LLtypeMixin, BaseTest, \
-                                                           equaloplists, FakeDescrWithSnapshot
-from rpython.jit.metainterp.optimizeopt.intutils import IntBound
-from rpython.jit.metainterp.history import TreeLoop, JitCellToken
-from rpython.jit.metainterp.optimizeopt.test.test_optimizeopt import FakeMetaInterpStaticData
-from rpython.jit.metainterp.resoperation import ResOperation, rop
-
-class TestBasic:
-    someptr1 = LLtypeMixin.myptr
-    someptr2 = LLtypeMixin.myptr2
-
-    def test_position_generalization(self):
-        def postest(info1, info2):
-            info1.position = 0
-            assert info1.generalization_of(info1, {}, {})
-            info2.position = 0
-            assert info1.generalization_of(info2, {}, {})
-            info2.position = 1
-            renum = {}
-            assert info1.generalization_of(info2, renum, {})
-            assert renum == {0:1}
-            assert info1.generalization_of(info2, {0:1}, {})
-            assert info1.generalization_of(info2, {1:1}, {})
-            bad = {}
-            assert not info1.generalization_of(info2, {0:0}, bad)
-            assert info1 in bad and info2 in bad
-
-        for BoxType in (BoxInt, BoxFloat, BoxPtr):
-            info1 = NotVirtualStateInfo(OptValue(BoxType()))
-            info2 = NotVirtualStateInfo(OptValue(BoxType()))
-            postest(info1, info2)
-            
-        info1, info2 = VArrayStateInfo(42), VArrayStateInfo(42)
-        info1.fieldstate = info2.fieldstate = []
-        postest(info1, info2)
-
-        info1, info2 = VStructStateInfo(42, []), VStructStateInfo(42, [])
-        info1.fieldstate = info2.fieldstate = []
-        postest(info1, info2)
-
-        info1, info2 = VirtualStateInfo(ConstInt(42), []), VirtualStateInfo(ConstInt(42), [])
-        info1.fieldstate = info2.fieldstate = []
-        postest(info1, info2)
-
-    def test_NotVirtualStateInfo_generalization(self):
-        def isgeneral(value1, value2):
-            info1 = NotVirtualStateInfo(value1)
-            info1.position = 0
-            info2 = NotVirtualStateInfo(value2)
-            info2.position = 0
-            return info1.generalization_of(info2, {}, {})
-
-        assert isgeneral(OptValue(BoxInt()), OptValue(ConstInt(7)))
-        assert not isgeneral(OptValue(ConstInt(7)), OptValue(BoxInt()))
-
-        ptr = OptValue(BoxPtr())
-        nonnull = OptValue(BoxPtr())
-        nonnull.make_nonnull(0)
-        knownclass = OptValue(BoxPtr())
-        knownclass.make_constant_class(ConstPtr(self.someptr1), 0)
-        const = OptValue(BoxPtr)
-        const.make_constant_class(ConstPtr(self.someptr1), 0)
-        const.make_constant(ConstPtr(self.someptr1))
-        inorder = [ptr, nonnull, knownclass, const]
-        for i in range(len(inorder)):
-            for j in range(i, len(inorder)):
-                assert isgeneral(inorder[i], inorder[j])
-                if i != j:
-                    assert not isgeneral(inorder[j], inorder[i])
-
-        value1 = OptValue(BoxInt())
-        value2 = OptValue(BoxInt())
-        value2.intbound.make_lt(IntBound(10, 10))
-        assert isgeneral(value1, value2)
-        assert not isgeneral(value2, value1)
-
-        assert isgeneral(OptValue(ConstInt(7)), OptValue(ConstInt(7)))
-        S = lltype.GcStruct('S')
-        foo = lltype.malloc(S)
-        fooref = lltype.cast_opaque_ptr(llmemory.GCREF, foo)
-        assert isgeneral(OptValue(ConstPtr(fooref)),
-                         OptValue(ConstPtr(fooref)))
-
-    def test_field_matching_generalization(self):
-        const1 = NotVirtualStateInfo(OptValue(ConstInt(1)))
-        const2 = NotVirtualStateInfo(OptValue(ConstInt(2)))
-        const1.position = const2.position = 1
-        assert not const1.generalization_of(const2, {}, {})
-        assert not const2.generalization_of(const1, {}, {})
-
-        def fldtst(info1, info2):
-            info1.position = info2.position = 0
-            info1.fieldstate = [const1]
-            info2.fieldstate = [const2]
-            assert not info1.generalization_of(info2, {}, {})
-            assert not info2.generalization_of(info1, {}, {})
-            assert info1.generalization_of(info1, {}, {})
-            assert info2.generalization_of(info2, {}, {})
-        fldtst(VArrayStateInfo(42), VArrayStateInfo(42))
-        fldtst(VStructStateInfo(42, [7]), VStructStateInfo(42, [7]))
-        fldtst(VirtualStateInfo(ConstInt(42), [7]), VirtualStateInfo(ConstInt(42), [7]))
-
-    def test_known_class_generalization(self):
-        knownclass1 = OptValue(BoxPtr())
-        knownclass1.make_constant_class(ConstPtr(self.someptr1), 0)
-        info1 = NotVirtualStateInfo(knownclass1)
-        info1.position = 0
-        knownclass2 = OptValue(BoxPtr())
-        knownclass2.make_constant_class(ConstPtr(self.someptr1), 0)
-        info2 = NotVirtualStateInfo(knownclass2)
-        info2.position = 0
-        assert info1.generalization_of(info2, {}, {})
-        assert info2.generalization_of(info1, {}, {})
-
-        knownclass3 = OptValue(BoxPtr())
-        knownclass3.make_constant_class(ConstPtr(self.someptr2), 0)
-        info3 = NotVirtualStateInfo(knownclass3)
-        info3.position = 0
-        assert not info1.generalization_of(info3, {}, {})
-        assert not info2.generalization_of(info3, {}, {})
-        assert not info3.generalization_of(info2, {}, {})
-        assert not info3.generalization_of(info1, {}, {})
-
-
-    def test_circular_generalization(self):
-        for info in (VArrayStateInfo(42), VStructStateInfo(42, [7]),
-                     VirtualStateInfo(ConstInt(42), [7])):
-            info.position = 0
-            info.fieldstate = [info]
-            assert info.generalization_of(info, {}, {})
-
-
-class BaseTestGenerateGuards(BaseTest):
-    def guards(self, info1, info2, box, expected):
-        info1.position = info2.position = 0
-        guards = []
-        info1.generate_guards(info2, box, self.cpu, guards, {})
-        self.compare(guards, expected, [box])
-
-    def compare(self, guards, expected, inputargs):
-        loop = self.parse(expected)
-        boxmap = {}
-        assert len(loop.inputargs) == len(inputargs)
-        for a, b in zip(loop.inputargs, inputargs):
-            boxmap[a] = b
-        for op in loop.operations:
-            if op.is_guard():
-                op.setdescr(None)
-        assert equaloplists(guards, loop.operations, False,
-                            boxmap)        
-    def test_intbounds(self):