Commits

Hakan Ardo committed 1806b0b

intbound support for shift operations

  • Participants
  • Parent commits 1529a34

Comments (0)

Files changed (6)

pypy/jit/metainterp/optimizeopt/intbounds.py

         r = self.getvalue(op.result)
         r.intbound.intersect(v1.intbound.div_bound(v2.intbound))
 
+    def optimize_INT_LSHIFT(self, op):
+        v1 = self.getvalue(op.getarg(0))
+        v2 = self.getvalue(op.getarg(1))
+        self.emit_operation(op)
+        r = self.getvalue(op.result)
+        r.intbound.intersect(v1.intbound.lshift_bound(v2.intbound))
+
+    def optimize_INT_RSHIFT(self, op):
+        v1 = self.getvalue(op.getarg(0))
+        v2 = self.getvalue(op.getarg(1))
+        self.emit_operation(op)
+        r = self.getvalue(op.result)
+        r.intbound.intersect(v1.intbound.rshift_bound(v2.intbound))
+
     def optimize_INT_ADD_OVF(self, op):
         v1 = self.getvalue(op.getarg(0))
         v2 = self.getvalue(op.getarg(1))
         if v2.intbound.intersect(b):
             self.propagate_bounds_backward(op.getarg(1))
 
+    def propagate_bounds_INT_LSHIFT(self, op):
+        v1 = self.getvalue(op.getarg(0))
+        v2 = self.getvalue(op.getarg(1))
+        r = self.getvalue(op.result)
+        b = r.intbound.rshift_bound(v2.intbound)
+        if v1.intbound.intersect(b):
+            self.propagate_bounds_backward(op.getarg(0))
+
     propagate_bounds_INT_ADD_OVF  = propagate_bounds_INT_ADD
     propagate_bounds_INT_SUB_OVF  = propagate_bounds_INT_SUB
     propagate_bounds_INT_MUL_OVF  = propagate_bounds_INT_MUL

pypy/jit/metainterp/optimizeopt/intutils.py

         else:
             return IntUnbounded()
 
+    def lshift_bound(self, other):
+        if self.has_upper and self.has_lower and \
+           other.has_upper and other.has_lower and \
+           other.known_ge(IntBound(0, 0)):
+            try:
+                vals = (ovfcheck(self.upper * pow2(other.upper)),
+                        ovfcheck(self.upper * pow2(other.lower)),
+                        ovfcheck(self.lower * pow2(other.upper)),
+                        ovfcheck(self.lower * pow2(other.lower)))
+                return IntBound(min4(vals), max4(vals))
+            except OverflowError:
+                return IntUnbounded()
+        else:
+            return IntUnbounded()
+
+    def rshift_bound(self, other):
+        if self.has_upper and self.has_lower and \
+           other.has_upper and other.has_lower and \
+           other.known_ge(IntBound(0, 0)):
+            try:
+                vals = (ovfcheck(self.upper / pow2(other.upper)),
+                        ovfcheck(self.upper / pow2(other.lower)),
+                        ovfcheck(self.lower / pow2(other.upper)),
+                        ovfcheck(self.lower / pow2(other.lower)))
+                return IntBound(min4(vals), max4(vals))
+            except OverflowError:
+                return IntUnbounded()
+        else:
+            return IntUnbounded()
+
+
     def contains(self, val):
         if self.has_lower and val < self.lower:
             return False
 
 def max4(t):
     return max(max(t[0], t[1]), max(t[2], t[3]))
+
+def pow2(x):
+    y = 1 << x
+    if y < 1:
+        raise OverflowError, "pow2 did overflow"
+    return y
+
+        

pypy/jit/metainterp/test/test_intbound.py

     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_div_bound():
     for _, _, b1 in some_bounds():
         for _, _, b2 in some_bounds():

pypy/jit/metainterp/test/test_optimizeopt.py

         """
         py.test.raises(InvalidLoop, self.optimize_loop, ops, ops)
 
+    def test_bound_lshift(self):
+        ops = """
+        [i0, i1, i1b, i2, i3]
+        i4 = int_lt(i1, 7)
+        guard_true(i4) []
+        i4b = int_lt(i1b, 7)
+        guard_true(i4b) []
+        i4c = int_ge(i1b, 0)
+        guard_true(i4c) []
+        i5 = int_lt(i3, 2)
+        guard_true(i5) []
+        i6 = int_ge(i3, 0)
+        guard_true(i6) []
+        i7 = int_lshift(i1, i3)
+        i8 = int_le(i7, 14)
+        guard_true(i8) []
+        i8b = int_lshift(i1, i2)
+        i9 = int_le(i8b, 14)
+        guard_true(i9) []
+        i10 = int_lshift(i0, i3)
+        i11 = int_le(i10, 14)
+        guard_true(i11) []
+        i12 = int_lt(i0, 15)
+        guard_true(i12) []
+        i13 = int_lshift(i1b, i3)
+        i14 = int_le(i13, 14)
+        guard_true(i14) []
+        i15 = int_lshift(i1b, i2)
+        i16 = int_le(i15, 14)
+        guard_true(i16) []
+        jump(i0, i1, i1b, i2, i3)
+        """
+        preamble = """
+        [i0, i1, i1b, i2, i3]        
+        i4 = int_lt(i1, 7)
+        guard_true(i4) []
+        i4b = int_lt(i1b, 7)
+        guard_true(i4b) []
+        i4c = int_ge(i1b, 0)
+        guard_true(i4c) []
+        i5 = int_lt(i3, 2)
+        guard_true(i5) []
+        i6 = int_ge(i3, 0)
+        guard_true(i6) []
+        i7 = int_lshift(i1, i3)
+        i8 = int_le(i7, 14)
+        guard_true(i8) []
+        i8b = int_lshift(i1, i2)
+        i9 = int_le(i8b, 14)
+        guard_true(i9) []
+        i10 = int_lshift(i0, i3)
+        i11 = int_le(i10, 14)
+        guard_true(i11) []
+        i13 = int_lshift(i1b, i3)
+        i15 = int_lshift(i1b, i2)
+        i16 = int_le(i15, 14)
+        guard_true(i16) []
+        jump(i0, i1, i1b, i2, i3)
+        """
+        expected = """
+        [i0, i1, i1b, i2, i3]
+        jump(i0, i1, i1b, i2, i3)        
+        """
+        self.optimize_loop(ops, expected, preamble)        
+
+    def test_bound_rshift(self):
+        ops = """
+        [i0, i1, i1b, i2, i3]
+        i4 = int_lt(i1, 7)
+        guard_true(i4) []
+        i4b = int_lt(i1b, 7)
+        guard_true(i4b) []
+        i4c = int_ge(i1b, 0)
+        guard_true(i4c) []
+        i5 = int_lt(i3, 2)
+        guard_true(i5) []
+        i6 = int_ge(i3, 0)
+        guard_true(i6) []
+        i7 = int_rshift(i1, i3)
+        i8 = int_le(i7, 14)
+        guard_true(i8) []
+        i8b = int_rshift(i1, i2)
+        i9 = int_le(i8b, 14)
+        guard_true(i9) []
+        i10 = int_rshift(i0, i3)
+        i11 = int_le(i10, 14)
+        guard_true(i11) []
+        i12 = int_lt(i0, 25)
+        guard_true(i12) []
+        i13 = int_rshift(i1b, i3)
+        i14 = int_le(i13, 14)
+        guard_true(i14) []
+        i15 = int_rshift(i1b, i2)
+        i16 = int_le(i15, 14)
+        guard_true(i16) []
+        jump(i0, i1, i1b, i2, i3)
+        """
+        preamble = """
+        [i0, i1, i1b, i2, i3]        
+        i4 = int_lt(i1, 7)
+        guard_true(i4) []
+        i4b = int_lt(i1b, 7)
+        guard_true(i4b) []
+        i4c = int_ge(i1b, 0)
+        guard_true(i4c) []
+        i5 = int_lt(i3, 2)
+        guard_true(i5) []
+        i6 = int_ge(i3, 0)
+        guard_true(i6) []
+        i7 = int_rshift(i1, i3)
+        i8b = int_rshift(i1, i2)
+        i9 = int_le(i8b, 14)
+        guard_true(i9) []
+        i10 = int_rshift(i0, i3)
+        i11 = int_le(i10, 14)
+        guard_true(i11) []
+        i12 = int_lt(i0, 25)
+        guard_true(i12) []
+        i13 = int_rshift(i1b, i3)
+        i15 = int_rshift(i1b, i2)
+        i16 = int_le(i15, 14)
+        guard_true(i16) []
+        jump(i0, i1, i1b, i2, i3)
+        """
+        expected = """
+        [i0, i1, i1b, i2, i3]
+        jump(i0, i1, i1b, i2, i3)        
+        """
+        self.optimize_loop(ops, expected, preamble)        
+
+    def test_bound_dont_backpropagate_rshift(self):
+        ops = """
+        [i0]
+        i3 = int_rshift(i0, 1)
+        i5 = int_eq(i3, 1)
+        guard_true(i5) []
+        i11 = int_add(i0, 1)
+        jump(i11)
+        """
+        self.optimize_loop(ops, ops, ops)
+
+        
     def test_mul_ovf(self):
         ops = """
         [i0, i1]

pypy/module/pypyjit/test/randomized.py

                ' ' + self.expression()
 
     def test(self):
-        return self.expression() + ' ' + self.sample(self.tests) + \
-               ' ' + self.expression()
+        tst = self.sample(self.tests)
+        if tst:
+            return self.expression() + ' ' + tst + \
+                   ' ' + self.expression()
+        else:
+            return self.expression()
 
     def constant(self):
         return str(self.sample(self.constants))
         
 
 class IntBounds(RandomCode):
-    opperators = ('+', '-', '*')
-    tests = ('<', '>', '<=', '>=', '==', '!=')
-    constants = range(-3,4)
+    opperators = ('+', '-', '*', '/', '>>', '<<')
+    tests = ('<', '>', '<=', '>=', '==', '!=', None)
+    constants = range(-3,4) 
     varnames = 'abcd'
 
     def function(self, name='f'):

pypy/module/pypyjit/test/test_pypy_c.py

     def run_source(self, source, expected_max_ops, *testcases, **kwds):
         assert isinstance(expected_max_ops, int)
         threshold = kwds.pop('threshold', 3)
+        self.count_debug_merge_point = \
+                                     kwds.pop('count_debug_merge_point', True)
         if kwds:
             raise TypeError, 'Unsupported keyword arguments: %s' % kwds.keys()
         source = py.code.Source(source)
         sliced_loops = [] # contains all bytecodes of all loops
         total_ops = 0
         for loop in loops:
-            total_ops += len(loop.operations)
             for op in loop.operations:
                 if op.getopname() == "debug_merge_point":
                     sliced_loop = BytecodeTrace()
                     sliced_loop.bytecode = op.getarg(0)._get_str().rsplit(" ", 1)[1]
                     sliced_loops.append(sliced_loop)
+                    if self.count_debug_merge_point:
+                        total_ops += 1
                 else:
                     sliced_loop.append(op)
+                    total_ops += 1
         return loops, sliced_loops, total_ops
 
     def check_0_op_bytecodes(self):
                     r = 2000
                 else:
                     r = 0
-                if a > 0 and b > 1:
-                    ops = 0
-                else:
-                    ops = 0
+                ops = 46
                 
                 self.run_source('''
                 def main(a, b):
                     return sa
                 ''', ops, ([a, b], r))
         
+    def test_shift(self):
+        from sys import maxint
+        maxvals = (-maxint-1, -maxint, maxint-1, maxint)
+        for a in (-4, -3, -2, -1, 0, 1, 2, 3, 4) + maxvals:
+            for b in (0, 1, 2, 31, 32, 33, 61, 62, 63):
+                r = 0
+                if (a >> b) >= 0:
+                    r += 2000
+                if (a << b) > 2:
+                    r += 20000000
+                if abs(a) < 10 and b < 5:
+                    ops = 13
+                else:
+                    ops = 29
+
+                self.run_source('''
+                def main(a, b):
+                    i = sa = 0
+                    while i < 2000:
+                        if a > 0: # Specialises the loop
+                            pass
+                        if b < 2 and b > 0:
+                            pass
+                        if (a >> b) >= 0:
+                            sa += 1
+                        if (a << b) > 2:
+                            sa += 10000
+                        i += 1
+                    return sa
+                ''', ops, ([a, b], r), count_debug_merge_point=False)
+        
 
 class AppTestJIT(PyPyCJITTests):
     def setup_class(cls):