Commits

Hakan Ardo committed bb4e36f Merge

hg merge jit-int

Comments (0)

Files changed (7)

pypy/jit/backend/x86/regalloc.py

     def _compute_vars_longevity(self, inputargs, operations):
         # compute a dictionary that maps variables to index in
         # operations that is a "last-time-seen"
-        longevity = {}
-        start_live = {}
-        for inputarg in inputargs:
-            start_live[inputarg] = 0
-        for i in range(len(operations)):
+        produced = {}
+        last_used = {}
+        for i in range(len(operations)-1, -1, -1):
             op = operations[i]
-            if op.result is not None:
-                start_live[op.result] = i
+            if op.result:
+                if op.result not in last_used and op.has_no_side_effect():
+                    continue
+                assert op.result not in produced
+                produced[op.result] = i
             for j in range(op.numargs()):
                 arg = op.getarg(j)
-                if isinstance(arg, Box):
-                    if arg not in start_live:
-                        not_implemented("Bogus arg in operation %d at %d" %
-                                        (op.getopnum(), i))
-                    longevity[arg] = (start_live[arg], i)
+                if isinstance(arg, Box) and arg not in last_used:
+                    last_used[arg] = i
             if op.is_guard():
                 for arg in op.getfailargs():
                     if arg is None: # hole
                         continue
                     assert isinstance(arg, Box)
-                    if arg not in start_live:
-                        not_implemented("Bogus arg in guard %d at %d" %
-                                        (op.getopnum(), i))
-                    longevity[arg] = (start_live[arg], i)
+                    if arg not in last_used:
+                        last_used[arg] = i
+                        
+        longevity = {}
+        for arg in produced:
+            if arg in last_used:
+                assert isinstance(arg, Box)
+                assert produced[arg] < last_used[arg]
+                longevity[arg] = (produced[arg], last_used[arg])
+                del last_used[arg]
         for arg in inputargs:
-            if arg not in longevity:
+            assert isinstance(arg, Box)
+            if arg not in last_used:
                 longevity[arg] = (-1, -1)
-        for arg in longevity:
-            assert isinstance(arg, Box)
+            else:
+                longevity[arg] = (0, last_used[arg])
+                del last_used[arg]
+        assert len(last_used) == 0
         return longevity
 
     def loc(self, v):

pypy/jit/backend/x86/test/test_regalloc.py

         self.interpret(ops, [s, ord('a')])
         assert s[1] == 'a'
 
+    def test_division_optimized(self):
+        ops = '''
+        [i7, i6]
+        i18 = int_floordiv(i7, i6)
+        i19 = int_xor(i7, i6)
+        i21 = int_lt(i19, 0)
+        i22 = int_mod(i7, i6)
+        i23 = int_is_true(i22)
+        i24 = int_eq(i6, 4)
+        guard_false(i24) [i18]
+        jump(i18, i6)
+        '''
+        self.interpret(ops, [10, 4])
+        assert self.getint(0) == 2
+        # FIXME: Verify that i19 - i23 are removed
+
 class TestRegallocFloats(BaseTestRegalloc):
     def test_float_add(self):
         ops = '''

pypy/jit/metainterp/optimizeopt/intbounds.py

         v2 = self.getvalue(op.getarg(1))
         self.emit_operation(op)
         r = self.getvalue(op.result)
-        r.intbound.intersect(v1.intbound.lshift_bound(v2.intbound))
+        b = v1.intbound.lshift_bound(v2.intbound)
+        r.intbound.intersect(b)
+        if b.has_lower and b.has_upper:
+            # Synthesize the reverse op for optimize_default to reuse
+            self.pure(rop.INT_RSHIFT, [op.result, op.getarg(1)], op.getarg(0))
+
 
     def optimize_INT_RSHIFT(self, op):
         v1 = self.getvalue(op.getarg(0))
             self.make_constant_int(op.result, 0)
         elif v1.intbound.known_lt(v2.intbound):
             self.make_constant_int(op.result, 0)
+        elif v1 is v2:
+            self.make_constant_int(op.result, 1)
         else:
             self.emit_operation(op)
 
             self.make_constant_int(op.result, 1)
         elif v1.intbound.known_lt(v2.intbound):
             self.make_constant_int(op.result, 1)
+        elif v1 is v2:
+            self.make_constant_int(op.result, 0)
         else:
             self.emit_operation(op)
 

pypy/jit/metainterp/optimizeopt/rewrite.py

 from pypy.jit.metainterp.optimizeutil import _findall
 from pypy.jit.metainterp.resoperation import rop, ResOperation
 from pypy.jit.codewriter.effectinfo import EffectInfo
+from pypy.jit.metainterp.optimizeopt.intutils import IntBound
 
 class OptRewrite(Optimization):
     """Rewrite operations into equivalent, cheaper operations.
             return True # 0-length arraycopy
         return False
 
+    def optimize_INT_FLOORDIV(self, op):
+        v1 = self.getvalue(op.getarg(0))
+        v2 = self.getvalue(op.getarg(1))
+
+        if v1.intbound.known_ge(IntBound(0, 0)) and v2.is_constant():
+            val = v2.box.getint()
+            if val & (val - 1) == 0 and val > 0: # val == 2**shift
+                shift = 0
+                while (1 << shift) < val:
+                    shift += 1
+                op = op.copy_and_change(rop.INT_RSHIFT,
+                                        args = [op.getarg(0), ConstInt(shift)])
+        self.emit_operation(op)
+
+
 optimize_ops = _findall(OptRewrite, 'optimize_')
 optimize_guards = _findall(OptRewrite, 'optimize_', 'GUARD')

pypy/jit/metainterp/test/test_optimizeopt.py

         """
         self.optimize_loop(ops, expected, preamble)
 
-
-
+    def test_division_to_rshift(self):
+        ops = """
+        [i1, i2]
+        it = int_gt(i1, 0) 
+        guard_true(it)[]
+        i3 = int_floordiv(i1, i2)
+        i4 = int_floordiv(2, i2)
+        i5 = int_floordiv(i1, 2)
+        i6 = int_floordiv(3, i2)
+        i7 = int_floordiv(i1, 3)
+        i8 = int_floordiv(4, i2)
+        i9 = int_floordiv(i1, 4)
+        i10 = int_floordiv(i1, 0)
+        i11 = int_floordiv(i1, 1)
+        i12 = int_floordiv(i2, 2)
+        i13 = int_floordiv(i2, 3)
+        i14 = int_floordiv(i2, 4)
+        jump(i5, i14)
+        """
+        expected = """
+        [i1, i2]
+        it = int_gt(i1, 0) 
+        guard_true(it)[]        
+        i3 = int_floordiv(i1, i2)
+        i4 = int_floordiv(2, i2)
+        i5 = int_rshift(i1, 1)
+        i6 = int_floordiv(3, i2)
+        i7 = int_floordiv(i1, 3)
+        i8 = int_floordiv(4, i2)
+        i9 = int_rshift(i1, 2)        
+        i10 = int_floordiv(i1, 0)
+        i11 = int_rshift(i1, 0)
+        i12 = int_floordiv(i2, 2)
+        i13 = int_floordiv(i2, 3)
+        i14 = int_floordiv(i2, 4)
+        jump(i5, i14)
+        """
+        self.optimize_loop(ops, expected)
+
+    def test_lshift_rshift(self):
+        ops = """
+        [i1, i2, i2b, i1b]
+        i3 = int_lshift(i1, i2)
+        i4 = int_rshift(i3, i2)
+        i5 = int_lshift(i1, 2)
+        i6 = int_rshift(i5, 2)
+        i7 = int_lshift(i1, 100)
+        i8 = int_rshift(i7, 100)
+        i9 = int_lt(i1b, 100)
+        guard_true(i9) []
+        i10 = int_gt(i1b, -100)
+        guard_true(i10) []        
+        i13 = int_lshift(i1b, i2)
+        i14 = int_rshift(i13, i2)
+        i15 = int_lshift(i1b, 2)
+        i16 = int_rshift(i15, 2)
+        i17 = int_lshift(i1b, 100)
+        i18 = int_rshift(i17, 100)
+        i19 = int_eq(i1b, i16)
+        guard_true(i19) []
+        i20 = int_ne(i1b, i16)
+        guard_false(i20) []
+        jump(i2, i3, i1b, i2b)
+        """
+        expected = """
+        [i1, i2, i2b, i1b]
+        i3 = int_lshift(i1, i2)
+        i4 = int_rshift(i3, i2)
+        i5 = int_lshift(i1, 2)
+        i6 = int_rshift(i5, 2)
+        i7 = int_lshift(i1, 100)
+        i8 = int_rshift(i7, 100)
+        i9 = int_lt(i1b, 100)
+        guard_true(i9) []
+        i10 = int_gt(i1b, -100)
+        guard_true(i10) []        
+        i13 = int_lshift(i1b, i2)
+        i14 = int_rshift(i13, i2)
+        i15 = int_lshift(i1b, 2)
+        i17 = int_lshift(i1b, 100)
+        i18 = int_rshift(i17, 100)
+        jump(i2, i3, i1b, i2b)
+        """
+        self.optimize_loop(ops, expected)
+        
     def test_subsub_ovf(self):
         ops = """
         [i0]

pypy/module/pypyjit/test/test_pypy_c.py

                         i += 1
                     return sa
                 ''', ops, ([a, b], r), count_debug_merge_point=False)
+
+    def test_revert_shift(self):
+        from sys import maxint
+        tests = []
+        for a in (1, 4, 8, 100):
+            for b in (-10, 10, -201, 201, -maxint/3, maxint/3):
+                for c in (-10, 10, -maxint/3, maxint/3):
+                    tests.append(([a, b, c], long(4000*(a+b+c))))
+        self.run_source('''
+        def main(a, b, c):
+            from sys import maxint
+            i = sa = 0
+            while i < 2000:
+                if 0 < a < 10: pass
+                if -100 < b < 100: pass
+                if -maxint/2 < c < maxint/2: pass
+                sa += (a<<a)>>a
+                sa += (b<<a)>>a
+                sa += (c<<a)>>a
+                sa += (a<<100)>>100
+                sa += (b<<100)>>100
+                sa += (c<<100)>>100
+                i += 1
+            return long(sa)
+        ''', 93, count_debug_merge_point=False, *tests)
+        
+    def test_division_to_rshift(self):
+        avalues = ('a', 'b', 7, -42, 8)
+        bvalues = ['b'] + range(-10, 0) + range(1,10)
+        code = ''
+        a1, b1, res1 = 10, 20, 0
+        a2, b2, res2 = 10, -20, 0
+        a3, b3, res3 = -10, -20, 0
+        def dd(a, b, aval, bval):
+            m = {'a': aval, 'b': bval}
+            if not isinstance(a, int):
+                a=m[a]
+            if not isinstance(b, int):
+                b=m[b]
+            return a/b
+        for a in avalues:
+            for b in bvalues:
+                code += '                sa += %s / %s\n' % (a, b)
+                res1 += dd(a, b, a1, b1)
+                res2 += dd(a, b, a2, b2)
+                res3 += dd(a, b, a3, b3)
+        self.run_source('''
+        def main(a, b):
+            i = sa = 0
+            while i < 2000:
+%s                
+                i += 1
+            return sa
+        ''' % code, 179, ([a1, b1], 2000 * res1),
+                         ([a2, b2], 2000 * res2),
+                         ([a3, b3], 2000 * res3),
+                         count_debug_merge_point=False)
+        
+    def test_mod(self):
+        py.test.skip('Results are correct, but traces 1902 times (on trunk too).')
+        avalues = ('a', 'b', 7, -42, 8)
+        bvalues = ['b'] + range(-10, 0) + range(1,10)
+        code = ''
+        a1, b1, res1 = 10, 20, 0
+        a2, b2, res2 = 10, -20, 0
+        a3, b3, res3 = -10, -20, 0
+        def dd(a, b, aval, bval):
+            m = {'a': aval, 'b': bval}
+            if not isinstance(a, int):
+                a=m[a]
+            if not isinstance(b, int):
+                b=m[b]
+            return a % b
+        for a in avalues:
+            for b in bvalues:
+                code += '                sa += %s %% %s\n' % (a, b)
+                res1 += dd(a, b, a1, b1)
+                res2 += dd(a, b, a2, b2)
+                res3 += dd(a, b, a3, b3)
+        self.run_source('''
+        def main(a, b):
+            i = sa = 0
+            while i < 2000:
+                if a > 0: pass
+                if 1 < b < 2: pass
+%s
+                i += 1
+            return sa
+        ''' % code, 0, ([a1, b1], 2000 * res1),
+                         ([a2, b2], 2000 * res2),
+                         ([a3, b3], 2000 * res3),
+                         count_debug_merge_point=False)
         
 
 class AppTestJIT(PyPyCJITTests):
             # return r + y*(((x^y)<0)&(r!=0));
             v_xor = hop.genop(prefix + 'xor', vlist,
                             resulttype=repr)
-            v_xor_le = hop.genop(prefix + 'le', [v_xor, c_zero],
+            v_xor_le = hop.genop(prefix + 'lt', [v_xor, c_zero],
                                resulttype=Bool)
             v_xor_le = hop.llops.convertvar(v_xor_le, bool_repr, repr)
             v_mod_ne = hop.genop(prefix + 'ne', [v_res, c_zero],