Author: Armin Rigo <[email protected]>
Branch: remove-raisingops
Changeset: r84743:4d168a87ff26
Date: 2016-05-27 23:17 +0200
http://bitbucket.org/pypy/pypy/changeset/4d168a87ff26/
Log: Handle modulo-by-constant too
diff --git a/rpython/jit/metainterp/optimizeopt/intbounds.py
b/rpython/jit/metainterp/optimizeopt/intbounds.py
--- a/rpython/jit/metainterp/optimizeopt/intbounds.py
+++ b/rpython/jit/metainterp/optimizeopt/intbounds.py
@@ -196,17 +196,6 @@
def opt_call_INT_PY_MOD(self, op):
b1 = self.getintbound(op.getarg(1))
b2 = self.getintbound(op.getarg(2))
- if b2.is_constant():
- val = b2.getint()
- if val > 0 and (val & (val-1)) == 0:
- # x % power-of-two ==> x & (power-of-two - 1)
- # with Python's modulo, this is valid even if 'x' is negative.
- from rpython.jit.metainterp.history import DONT_CHANGE
- arg1 = op.getarg(1)
- arg2 = ConstInt(val-1)
- op = self.replace_op_with(op, rop.INT_AND,
- args=[arg1, arg2],
- descr=DONT_CHANGE) # <- xxx rename?
self.emit_operation(op)
if b2.is_constant():
val = b2.getint()
diff --git a/rpython/jit/metainterp/optimizeopt/intdiv.py
b/rpython/jit/metainterp/optimizeopt/intdiv.py
--- a/rpython/jit/metainterp/optimizeopt/intdiv.py
+++ b/rpython/jit/metainterp/optimizeopt/intdiv.py
@@ -90,6 +90,14 @@
return [mul_box, sh_box]
+def modulo_operations(n_box, m, known_nonneg=False):
+ operations = division_operations(n_box, m, known_nonneg)
+
+ mul_box = ResOperation(rop.INT_MUL, [operations[-1], ConstInt(m)])
+ diff_box = ResOperation(rop.INT_SUB, [n_box, mul_box])
+ return operations + [mul_box, diff_box]
+
+
def unsigned_mul_high(a, b):
DIGIT = LONG_BIT / 2
MASK = (1 << DIGIT) - 1
diff --git a/rpython/jit/metainterp/optimizeopt/rewrite.py
b/rpython/jit/metainterp/optimizeopt/rewrite.py
--- a/rpython/jit/metainterp/optimizeopt/rewrite.py
+++ b/rpython/jit/metainterp/optimizeopt/rewrite.py
@@ -673,6 +673,9 @@
elif oopspecindex == EffectInfo.OS_INT_PY_DIV:
if self._optimize_CALL_INT_PY_DIV(op):
return
+ elif oopspecindex == EffectInfo.OS_INT_PY_MOD:
+ if self._optimize_CALL_INT_PY_MOD(op):
+ return
self.emit_operation(op)
optimize_CALL_PURE_R = optimize_CALL_PURE_I
optimize_CALL_PURE_F = optimize_CALL_PURE_I
@@ -726,6 +729,46 @@
self.make_equal_to(op, newop)
return True
+ def _optimize_CALL_INT_PY_MOD(self, op):
+ arg1 = op.getarg(1)
+ b1 = self.getintbound(arg1)
+ arg2 = op.getarg(2)
+ b2 = self.getintbound(arg2)
+
+ if b1.is_constant() and b1.getint() == 0:
+ self.make_constant_int(op, 0)
+ self.last_emitted_operation = REMOVED
+ return True
+ # This is Python's integer division: 'x // (2**shift)' can always
+ # be replaced with 'x >> shift', even for negative values of x
+ if not b2.is_constant():
+ return False
+ val = b2.getint()
+ if val <= 0:
+ return False
+ if val == 1:
+ self.make_constant_int(op, 0)
+ self.last_emitted_operation = REMOVED
+ return True
+ elif val & (val - 1) == 0: # val == 2**shift
+ from rpython.jit.metainterp.history import DONT_CHANGE
+ # x % power-of-two ==> x & (power-of-two - 1)
+ # with Python's modulo, this is valid even if 'x' is negative.
+ op = self.replace_op_with(op, rop.INT_AND,
+ args=[arg1, ConstInt(val - 1)],
+ descr=DONT_CHANGE) # <- xxx rename? means "kill"
+ self.optimizer.send_extra_operation(op)
+ return True
+ else:
+ from rpython.jit.metainterp.optimizeopt import intdiv
+ known_nonneg = b1.known_ge(IntBound(0, 0))
+ operations = intdiv.modulo_operations(arg1, val, known_nonneg)
+ newop = None
+ for newop in operations:
+ self.optimizer.send_extra_operation(newop)
+ self.make_equal_to(op, newop)
+ return True
+
def optimize_CAST_PTR_TO_INT(self, op):
self.optimizer.pure_reverse(op)
self.emit_operation(op)
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
b/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
--- a/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
+++ b/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
@@ -4,6 +4,7 @@
from rpython.jit.metainterp.optimizeopt.intdiv import magic_numbers, LONG_BIT
from rpython.jit.metainterp.optimizeopt.intdiv import division_operations
+from rpython.jit.metainterp.optimizeopt.intdiv import modulo_operations
from rpython.jit.metainterp.optimizeopt.intdiv import unsigned_mul_high
from rpython.jit.metainterp.history import ConstInt
from rpython.jit.metainterp.resoperation import InputArgInt
@@ -46,3 +47,22 @@
constants[op] = ConstInt(res)
assert constants[op].getint() == n // m
+
+
+@given(strategies.integers(min_value=-sys.maxint-1, max_value=sys.maxint),
+ not_power_of_two,
+ strategies.booleans())
+def test_modulo_operations(n, m, known_nonneg):
+ if n < 0:
+ known_nonneg = False
+ n_box = InputArgInt()
+ ops = modulo_operations(n_box, m, known_nonneg)
+
+ constants = {n_box: ConstInt(n)}
+ for op in ops:
+ argboxes = op.getarglist()
+ constantboxes = [constants.get(box, box) for box in argboxes]
+ res = execute(None, None, op.getopnum(), None, *constantboxes)
+ constants[op] = ConstInt(res)
+
+ assert constants[op].getint() == n % m
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py
b/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py
--- a/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py
+++ b/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py
@@ -1,5 +1,6 @@
-import py
+import py, sys
from rpython.rlib.objectmodel import instantiate
+from rpython.rlib.rarithmetic import intmask
from rpython.jit.metainterp.optimizeopt.test.test_util import (
LLtypeMixin, BaseTest, FakeMetaInterpStaticData,
convert_old_style_to_targets)
from rpython.jit.metainterp.history import TargetToken, JitCellToken
@@ -4659,6 +4660,7 @@
self.optimize_loop(ops, expected)
def test_intmod_bounds(self):
+ from rpython.jit.metainterp.optimizeopt.intdiv import magic_numbers
ops = """
[i0, i1]
i2 = call_pure_i(321, i0, 12, descr=int_py_mod_descr)
@@ -4673,31 +4675,32 @@
guard_false(i7) []
jump(i2, i5)
"""
+ kk, ii = magic_numbers(12)
expected = """
[i0, i1]
- i2 = call_i(321, i0, 12, descr=int_py_mod_descr)
+ i4 = int_rshift(i0, %d)
+ i6 = int_xor(i0, i4)
+ i8 = uint_mul_high(i6, %d)
+ i9 = uint_rshift(i8, %d)
+ i10 = int_xor(i9, i4)
+ i11 = int_mul(i10, 12)
+ i2 = int_sub(i0, i11)
i5 = call_i(321, i1, -12, descr=int_py_mod_descr)
jump(i2, i5)
- """
- self.optimize_loop(ops, expected)
-
- # same as above, but all guards are shifted by one so that they
- # must stay
- ops = """
- [i8, i9]
- i0 = escape_i()
- i2 = call_pure_i(321, i0, 12, descr=int_py_mod_descr)
- i3 = int_ge(i2, 11)
- guard_false(i3) []
- i4 = int_lt(i2, 1)
- guard_false(i4) []
+ """ % (63 if sys.maxint > 2**32 else 31, intmask(kk), ii)
+ self.optimize_loop(ops, expected)
+
+ # same as above (2nd case), but all guards are shifted by one so
+ # that they must stay
+ ops = """
+ [i9]
i1 = escape_i()
i5 = call_pure_i(321, i1, -12, descr=int_py_mod_descr)
i6 = int_le(i5, -11)
guard_false(i6) []
i7 = int_gt(i5, -1)
guard_false(i7) []
- jump(i2, i5)
+ jump(i5)
"""
self.optimize_loop(ops, ops.replace('call_pure_i', 'call_i'))
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
