Author: Armin Rigo <[email protected]>
Branch: remove-raisingops
Changeset: r84730:8ca81269b110
Date: 2016-05-27 18:53 +0200
http://bitbucket.org/pypy/pypy/changeset/8ca81269b110/
Log: Division by a constant: can be replaced with some carefully-computed
multiplication-and-keep-the-high-word.
diff --git a/rpython/jit/metainterp/blackhole.py
b/rpython/jit/metainterp/blackhole.py
--- a/rpython/jit/metainterp/blackhole.py
+++ b/rpython/jit/metainterp/blackhole.py
@@ -408,6 +408,14 @@
def bhimpl_int_mul(a, b):
return intmask(a * b)
+ @arguments("i", "i", returns="i")
+ def bhimpl_uint_mul_high(a, b):
+ from rpython.jit.metainterp.optimizeopt import intdiv
+ a = r_uint(a)
+ b = r_uint(b)
+ c = intdiv.unsigned_mul_high(a, b)
+ return intmask(c)
+
@arguments("L", "i", "i", returns="iL")
def bhimpl_int_add_jump_if_ovf(label, a, b):
try:
diff --git a/rpython/jit/metainterp/optimizeopt/intdiv.py
b/rpython/jit/metainterp/optimizeopt/intdiv.py
new file mode 100644
--- /dev/null
+++ b/rpython/jit/metainterp/optimizeopt/intdiv.py
@@ -0,0 +1,116 @@
+from rpython.rlib.rarithmetic import LONG_BIT, intmask, r_uint
+from rpython.rlib.rbigint import rbigint, ONERBIGINT
+
+from rpython.jit.metainterp.history import ConstInt
+from rpython.jit.metainterp.resoperation import ResOperation, rop
+
+
+# Logic to replace the signed integer division by a constant
+# by a few operations involving a UINT_MUL_HIGH.
+
+
+def magic_numbers(m):
+ assert m == intmask(m)
+ assert m & (m-1) != 0 # not a power of two
+ assert m >= 3
+ i = 1
+ while (r_uint(1) << (i+1)) < r_uint(m):
+ i += 1
+
+ # k = 2**(64+i) // m + 1, computed manually using rbigint
+ # because that's the easiest
+ k1 = ONERBIGINT.lshift(LONG_BIT + i).floordiv(rbigint.fromint(m))
+ k = k1.touint() + r_uint(1)
+
+ assert k != r_uint(0)
+ # Proof that k < 2**64 holds in all cases, even with the "+1":
+ #
+ # starting point: 2**i < m < 2**(i+1) with i <= 63
+ # 2**i < m
+ # 2**i <= m - (2.0**(i-63)) as real number, because (2.0**(i-63))<=1.0
+ # 2**(64+i) <= 2**64 * m - 2**(i+1) as integers again
+ # 2**(64+i) < 2**64 * m - m
+ # 2**(64+i) / float(m) < 2**64-1 real numbers division
+ # 2**(64+i) // m < 2**64-1 with the integer division
+ # k < 2**64
+
+ assert k > (r_uint(1) << (LONG_BIT-1))
+
+ return (k, i)
+
+
+def division_operations(n_box, m, known_nonneg=False):
+ kk, ii = magic_numbers(m)
+
+ # Turn the division into:
+ # t = n >> 63 # t == 0 or t == -1
+ # return (((n^t) * k) >> (64 + i)) ^ t
+
+ # Proof that this gives exactly a = n // m = floor(q), where q
+ # is the real number quotient:
+ #
+ # case t == 0, i.e. 0 <= n < 2**63
+ #
+ # a <= q <= a + (m-1)/m (we use '/' for the real quotient here)
+ #
+ # n * k == n * (2**(64+i) // m + 1)
+ # == n * ceil(2**(64+i) / m)
+ # == n * (2**(64+i) / m + ferr) for 0 < ferr < 1
+ # == q * 2**(64+i) + err for 0 < err < n
+ # < q * 2**(64+i) + n
+ # <= (a + (m-1)/m) * 2**(64+i) + n
+ # == 2**(64+i) * (a + extra) for 0 <= extra < ?
+ #
+ # extra == (m-1)/m + (n / 2**(64+i))
+ #
+ # but n < 2**63 < 2**(64+i)/m because m < 2**(i+1)
+ #
+ # extra < (m-1)/m + 1/m
+ # extra < 1.
+ #
+ # case t == -1, i.e. -2**63 <= n <= -1
+ #
+ # (note that n^(-1) == ~n)
+ # 0 <= ~n < 2**63
+ # by the previous case we get an answer a == (~n) // m
+ # ~a == n // m because it's a division truncating towards -inf.
+
+ if not known_nonneg:
+ t_box = ResOperation(rop.INT_RSHIFT, [n_box, ConstInt(LONG_BIT - 1)])
+ nt_box = ResOperation(rop.INT_XOR, [n_box, t_box])
+ else:
+ t_box = None
+ nt_box = n_box
+ mul_box = ResOperation(rop.UINT_MUL_HIGH, [nt_box, ConstInt(intmask(kk))])
+ sh_box = ResOperation(rop.UINT_RSHIFT, [mul_box, ConstInt(ii)])
+ if not known_nonneg:
+ final_box = ResOperation(rop.INT_XOR, [sh_box, t_box])
+ return [t_box, nt_box, mul_box, sh_box, final_box]
+ else:
+ return [mul_box, sh_box]
+
+
+def unsigned_mul_high(a, b):
+ DIGIT = LONG_BIT / 2
+ MASK = (1 << DIGIT) - 1
+
+ ah = a >> DIGIT
+ al = a & MASK
+ bh = b >> DIGIT
+ bl = b & MASK
+
+ rll = al * bl; assert rll == r_uint(rll)
+ rlh = al * bh; assert rlh == r_uint(rlh)
+ rhl = ah * bl; assert rhl == r_uint(rhl)
+ rhh = ah * bh; assert rhh == r_uint(rhh)
+
+ r1 = (rll >> DIGIT) + rhl
+ assert r1 == r_uint(r1)
+
+ r1 = r_uint(r1)
+ r2 = r_uint(r1 + rlh)
+ borrow = (r2 < r1) << DIGIT
+
+ r3 = (r2 >> DIGIT) + borrow + rhh
+ assert r3 == r_uint(r3)
+ return r3
diff --git a/rpython/jit/metainterp/optimizeopt/optimizer.py
b/rpython/jit/metainterp/optimizeopt/optimizer.py
--- a/rpython/jit/metainterp/optimizeopt/optimizer.py
+++ b/rpython/jit/metainterp/optimizeopt/optimizer.py
@@ -5,7 +5,7 @@
ConstIntBound, MININT, MAXINT, IntUnbounded
from rpython.jit.metainterp.optimizeopt.util import make_dispatcher_method
from rpython.jit.metainterp.resoperation import rop, AbstractResOp,
GuardResOp,\
- OpHelpers, ResOperation
+ OpHelpers
from rpython.jit.metainterp.optimizeopt import info
from rpython.jit.metainterp.optimize import InvalidLoop
from rpython.jit.metainterp.typesystem import llhelper
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
@@ -700,19 +700,31 @@
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 b2.is_constant():
- val = b2.getint()
- if val == 1:
- self.make_equal_to(op, arg1)
- self.last_emitted_operation = REMOVED
- return True
- elif val > 0 and val & (val - 1) == 0: # val == 2**shift
- from rpython.jit.metainterp.history import DONT_CHANGE
- op = self.replace_op_with(op, rop.INT_RSHIFT,
- args=[arg1, ConstInt(highest_bit(val))],
- descr=DONT_CHANGE) # <- xxx rename? means "kill"
- self.emit_operation(op)
- return True
+ if not b2.is_constant():
+ return False
+ val = b2.getint()
+ if val <= 0:
+ return False
+ if val == 1:
+ self.make_equal_to(op, arg1)
+ self.last_emitted_operation = REMOVED
+ return True
+ elif val & (val - 1) == 0: # val == 2**shift
+ from rpython.jit.metainterp.history import DONT_CHANGE
+ op = self.replace_op_with(op, rop.INT_RSHIFT,
+ args=[arg1, ConstInt(highest_bit(val))],
+ 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.division_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)
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
b/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
new file mode 100644
--- /dev/null
+++ b/rpython/jit/metainterp/optimizeopt/test/test_intdiv.py
@@ -0,0 +1,48 @@
+import sys
+import py
+from hypothesis import given, strategies
+
+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 unsigned_mul_high
+from rpython.jit.metainterp.history import ConstInt
+from rpython.jit.metainterp.resoperation import InputArgInt
+from rpython.jit.metainterp.executor import execute
+
+not_power_of_two = (strategies.integers(min_value=3, max_value=sys.maxint)
+ .filter(lambda m: (m & (m - 1)) != 0))
+
+
+@given(strategies.integers(min_value=0, max_value=sys.maxint),
+ not_power_of_two)
+def test_magic_numbers(n, m):
+ k, i = magic_numbers(m)
+ k = int(k) # and no longer r_uint, with wrap-around semantics
+ a = (n * k) >> (LONG_BIT + i)
+ assert a == n // m
+
+
+@given(strategies.integers(min_value=0, max_value=2*sys.maxint+1),
+ strategies.integers(min_value=0, max_value=2*sys.maxint+1))
+def test_unsigned_mul_high(a, b):
+ c = unsigned_mul_high(a, b)
+ assert c == ((a * b) >> LONG_BIT)
+
+
+@given(strategies.integers(min_value=-sys.maxint-1, max_value=sys.maxint),
+ not_power_of_two,
+ strategies.booleans())
+def test_division_operations(n, m, known_nonneg):
+ if n < 0:
+ known_nonneg = False
+ n_box = InputArgInt()
+ ops = division_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
@@ -4640,17 +4640,21 @@
def test_intdiv_bounds(self):
ops = """
- [i0]
- i2 = call_pure_i(321, i0, 3, descr=int_py_div_descr)
+ [i0, i1]
+ i4 = int_ge(i1, 3)
+ guard_true(i4) []
+ i2 = call_pure_i(321, i0, i1, descr=int_py_div_descr)
i3 = int_add_ovf(i2, 50)
guard_no_overflow() []
- jump(i3)
- """
- expected = """
- [i0]
- i2 = call_i(321, i0, 3, descr=int_py_div_descr)
+ jump(i3, i1)
+ """
+ expected = """
+ [i0, i1]
+ i4 = int_ge(i1, 3)
+ guard_true(i4) []
+ i2 = call_i(321, i0, i1, descr=int_py_div_descr)
i3 = int_add(i2, 50)
- jump(i3)
+ jump(i3, i1)
"""
self.optimize_loop(ops, expected)
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py
b/rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py
--- a/rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py
+++ b/rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py
@@ -1,5 +1,6 @@
import py, sys
from rpython.rlib.objectmodel import instantiate
+from rpython.rlib.rarithmetic import intmask
from rpython.rtyper.lltypesystem import lltype
from rpython.jit.metainterp import compile, resume
from rpython.jit.metainterp.history import AbstractDescr, ConstInt, TreeLoop
@@ -5327,9 +5328,7 @@
i10 = call_pure_i(327, i1, 0, descr=int_py_div_descr)
i11 = call_pure_i(328, i1, 1, descr=int_py_div_descr)
i5 = call_pure_i(329, i1, 2, descr=int_py_div_descr)
- i7 = call_pure_i(330, i1, 3, descr=int_py_div_descr)
i9 = call_pure_i(331, i1, 4, descr=int_py_div_descr)
- i9d = call_pure_i(332, i1, 6, descr=int_py_div_descr)
jump(i5, i9)
"""
expected = """
@@ -5343,13 +5342,50 @@
i10 = call_i(327, i1, 0, descr=int_py_div_descr)
# i11 = i1
i5 = int_rshift(i1, 1)
- i7 = call_i(330, i1, 3, descr=int_py_div_descr)
i9 = int_rshift(i1, 2)
- i9d = call_i(332, i1, 6, descr=int_py_div_descr)
jump(i5, i9)
"""
self.optimize_loop(ops, expected)
+ def test_division_to_mul_high_nonneg(self):
+ from rpython.jit.metainterp.optimizeopt.intdiv import magic_numbers
+ for divisor in [3, 5, 12]:
+ kk, ii = magic_numbers(divisor)
+ ops = """
+ [i1]
+ i3 = int_ge(i1, 0)
+ guard_true(i3) []
+ i2 = call_pure_i(321, i1, %d, descr=int_py_div_descr)
+ jump(i2)
+ """ % divisor
+ expected = """
+ [i1]
+ i4 = uint_mul_high(i1, %d)
+ i2 = uint_rshift(i4, %d)
+ jump(i2)
+ """ % (intmask(kk), ii)
+ self.optimize_loop(ops, expected)
+
+ def test_division_to_mul_high(self):
+ from rpython.jit.metainterp.optimizeopt.intdiv import magic_numbers
+ for divisor in [3, 5, 12]:
+ kk, ii = magic_numbers(divisor)
+ ops = """
+ [i1]
+ i2 = call_pure_i(321, i1, %d, descr=int_py_div_descr)
+ jump(i2)
+ """ % divisor
+ expected = """
+ [i1]
+ i3 = int_rshift(i1, %d)
+ i4 = int_xor(i1, i3)
+ i5 = uint_mul_high(i4, %d)
+ i6 = uint_rshift(i5, %d)
+ i2 = int_xor(i6, i3)
+ jump(i2)
+ """ % (63 if sys.maxint > 2**32 else 31, intmask(kk), ii)
+ self.optimize_loop(ops, expected)
+
def test_mul_to_lshift(self):
ops = """
[i1, i2]
diff --git a/rpython/jit/metainterp/resoperation.py
b/rpython/jit/metainterp/resoperation.py
--- a/rpython/jit/metainterp/resoperation.py
+++ b/rpython/jit/metainterp/resoperation.py
@@ -955,6 +955,7 @@
'INT_ADD/2/i',
'INT_SUB/2/i',
'INT_MUL/2/i',
+ 'UINT_MUL_HIGH/2/i', # a * b as a double-word, keep the high word
'INT_AND/2/i',
'INT_OR/2/i',
'INT_XOR/2/i',
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
