Author: Armin Rigo <ar...@tunes.org> Branch: Changeset: r93223:e6c7a428f649 Date: 2017-11-30 17:48 +0100 http://bitbucket.org/pypy/pypy/changeset/e6c7a428f649/
Log: Re-revert 30c6fda0a499, and add the proper fix, hopefully 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 @@ -25,19 +25,6 @@ return (1 << ((byte_size << 3) - 1)) - 1 -IS_64_BIT = sys.maxint > 2**32 - -def next_pow2_m1(n): - """Calculate next power of 2 greater than n minus one.""" - n |= n >> 1 - n |= n >> 2 - n |= n >> 4 - n |= n >> 8 - n |= n >> 16 - if IS_64_BIT: - n |= n >> 32 - return n - class OptIntBounds(Optimization): """Keeps track of the bounds placed on integers by guards and remove @@ -50,7 +37,7 @@ return dispatch_postprocess(self, op) def propagate_bounds_backward(self, box): - # FIXME: This takes care of the instruction where box is the reuslt + # FIXME: This takes care of the instruction where box is the result # but the bounds produced by all instructions where box is # an argument might also be tighten b = self.getintbound(box) @@ -91,14 +78,8 @@ b1 = self.getintbound(v1) v2 = self.get_box_replacement(op.getarg(1)) b2 = self.getintbound(v2) - if b1.known_ge(IntBound(0, 0)) and \ - b2.known_ge(IntBound(0, 0)): - r = self.getintbound(op) - if b1.has_upper and b2.has_upper: - mostsignificant = b1.upper | b2.upper - r.intersect(IntBound(0, next_pow2_m1(mostsignificant))) - else: - r.make_ge(IntBound(0, 0)) + b = b1.or_bound(b2) + self.getintbound(op).intersect(b) optimize_INT_OR = optimize_INT_OR_or_XOR optimize_INT_XOR = optimize_INT_OR_or_XOR @@ -112,15 +93,8 @@ def postprocess_INT_AND(self, op): b1 = self.getintbound(op.getarg(0)) b2 = self.getintbound(op.getarg(1)) - r = self.getintbound(op) - pos1 = b1.known_ge(IntBound(0, 0)) - pos2 = b2.known_ge(IntBound(0, 0)) - if pos1 or pos2: - r.make_ge(IntBound(0, 0)) - if pos1: - r.make_le(b1) - if pos2: - r.make_le(b2) + b = b1.and_bound(b2) + self.getintbound(op).intersect(b) def optimize_INT_SUB(self, op): return self.emit(op) @@ -211,16 +185,10 @@ r.intersect(b1.py_div_bound(b2)) def post_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() - r = self.getintbound(op) - if val >= 0: # with Python's modulo: 0 <= (x % pos) < pos - r.make_ge(IntBound(0, 0)) - r.make_lt(IntBound(val, val)) - else: # with Python's modulo: neg < (x % neg) <= 0 - r.make_gt(IntBound(val, val)) - r.make_le(IntBound(0, 0)) + r = self.getintbound(op) + r.intersect(b1.mod_bound(b2)) def optimize_INT_LSHIFT(self, op): return self.emit(op) @@ -436,7 +404,7 @@ def optimize_INT_FORCE_GE_ZERO(self, op): b = self.getintbound(op.getarg(0)) - if b.known_ge(IntBound(0, 0)): + if b.known_nonnegative(): self.make_equal_to(op, op.getarg(0)) else: return self.emit(op) @@ -647,7 +615,7 @@ if r.is_constant(): if r.getint() == valnonzero: b1 = self.getintbound(op.getarg(0)) - if b1.known_ge(IntBound(0, 0)): + if b1.known_nonnegative(): b1.make_gt(IntBound(0, 0)) self.propagate_bounds_backward(op.getarg(0)) elif r.getint() == valzero: diff --git a/rpython/jit/metainterp/optimizeopt/intutils.py b/rpython/jit/metainterp/optimizeopt/intutils.py --- a/rpython/jit/metainterp/optimizeopt/intutils.py +++ b/rpython/jit/metainterp/optimizeopt/intutils.py @@ -12,6 +12,19 @@ MAXINT = maxint MININT = -maxint - 1 +IS_64_BIT = sys.maxint > 2**32 + +def next_pow2_m1(n): + """Calculate next power of 2 greater than n minus one.""" + n |= n >> 1 + n |= n >> 2 + n |= n >> 4 + n |= n >> 8 + n |= n >> 16 + if IS_64_BIT: + n |= n >> 32 + return n + class IntBound(AbstractInfo): _attrs_ = ('has_upper', 'has_lower', 'upper', 'lower') @@ -92,6 +105,9 @@ def known_ge(self, other): return other.known_le(self) + def known_nonnegative(self): + return self.has_lower and 0 <= self.lower + def intersect(self, other): r = False @@ -192,10 +208,22 @@ else: return IntUnbounded() + def mod_bound(self, other): + r = IntUnbounded() + if other.is_constant(): + val = other.getint() + if val >= 0: # with Python's modulo: 0 <= (x % pos) < pos + r.make_ge(IntBound(0, 0)) + r.make_lt(IntBound(val, val)) + else: # with Python's modulo: neg < (x % neg) <= 0 + r.make_gt(IntBound(val, val)) + r.make_le(IntBound(0, 0)) + return r + 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)) and \ + other.known_nonnegative() and \ other.known_lt(IntBound(LONG_BIT, LONG_BIT)): try: vals = (ovfcheck(self.upper << other.upper), @@ -211,7 +239,7 @@ 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)) and \ + other.known_nonnegative() and \ other.known_lt(IntBound(LONG_BIT, LONG_BIT)): vals = (self.upper >> other.upper, self.upper >> other.lower, @@ -221,7 +249,32 @@ else: return IntUnbounded() + def and_bound(self, other): + pos1 = self.known_nonnegative() + pos2 = other.known_nonnegative() + r = IntUnbounded() + if pos1 or pos2: + r.make_ge(IntBound(0, 0)) + if pos1: + r.make_le(self) + if pos2: + r.make_le(other) + return r + + def or_bound(self, other): + r = IntUnbounded() + if self.known_nonnegative() and \ + other.known_nonnegative(): + if self.has_upper and other.has_upper: + mostsignificant = self.upper | other.upper + r.intersect(IntBound(0, next_pow2_m1(mostsignificant))) + else: + r.make_ge(IntBound(0, 0)) + return r + def contains(self, val): + if not we_are_translated(): + assert not isinstance(val, long) if not isinstance(val, int): if ((not self.has_lower or self.lower == MININT) and not self.has_upper or self.upper == MAXINT): @@ -282,7 +335,7 @@ guards.append(op) def is_bool(self): - return (self.bounded() and self.known_ge(ConstIntBound(0)) and + return (self.bounded() and self.known_nonnegative() and self.known_le(ConstIntBound(1))) def make_bool(self): @@ -297,7 +350,7 @@ if self.known_gt(IntBound(0, 0)) or \ self.known_lt(IntBound(0, 0)): return INFO_NONNULL - if self.known_ge(IntBound(0, 0)) and \ + if self.known_nonnegative() and \ self.known_le(IntBound(0, 0)): return INFO_NULL return INFO_UNKNOWN diff --git a/rpython/jit/metainterp/optimizeopt/test/test_intbound.py b/rpython/jit/metainterp/optimizeopt/test/test_intbound.py --- a/rpython/jit/metainterp/optimizeopt/test/test_intbound.py +++ b/rpython/jit/metainterp/optimizeopt/test/test_intbound.py @@ -1,12 +1,34 @@ from rpython.jit.metainterp.optimizeopt.intutils import IntBound, IntUpperBound, \ - IntLowerBound, IntUnbounded -from rpython.jit.metainterp.optimizeopt.intbounds import next_pow2_m1 + IntLowerBound, IntUnbounded, next_pow2_m1 from copy import copy import sys -from rpython.rlib.rarithmetic import LONG_BIT +from rpython.rlib.rarithmetic import LONG_BIT, ovfcheck -def bound(a,b): +from hypothesis import given, strategies + +special_values = ( + range(-100, 100) + + [2 ** i for i in range(1, LONG_BIT)] + + [-2 ** i for i in range(1, LONG_BIT)] + + [2 ** i - 1 for i in range(1, LONG_BIT)] + + [-2 ** i - 1 for i in range(1, LONG_BIT)] + + [2 ** i + 1 for i in range(1, LONG_BIT)] + + [-2 ** i + 1 for i in range(1, LONG_BIT)] + + [sys.maxint, -sys.maxint-1]) + +special_values = strategies.sampled_from( + [int(v) for v in special_values if type(int(v)) is int]) + +ints = strategies.builds( + int, # strategies.integers sometimes returns a long? + special_values | strategies.integers( + min_value=int(-sys.maxint-1), max_value=sys.maxint)) + +ints_or_none = strategies.none() | ints + + +def bound(a, b): if a is None and b is None: return IntUnbounded() elif a is None: @@ -14,11 +36,55 @@ elif b is None: return IntLowerBound(a) else: - return IntBound(a,b) + return IntBound(a, b) def const(a): return bound(a,a) + +def build_bound_with_contained_number(a, b, c): + a, b, c = sorted([a, b, c]) + r = bound(a, c) + assert r.contains(b) + return r, b + +bound_with_contained_number = strategies.builds( + build_bound_with_contained_number, + ints_or_none, + ints_or_none, + ints +) + +unbounded = strategies.builds( + lambda x: (bound(None, None), int(x)), + ints +) + +lower_bounded = strategies.builds( + lambda x, y: (bound(min(x, y), None), max(x, y)), + ints, + ints +) + +upper_bounded = strategies.builds( + lambda x, y: (bound(None, max(x, y)), min(x, y)), + ints, + ints +) + +bounded = strategies.builds( + build_bound_with_contained_number, + ints, ints, ints +) + +constant = strategies.builds( + lambda x: (const(x), x), + ints +) + +bound_with_contained_number = strategies.one_of( + unbounded, lower_bounded, upper_bounded, constant, bounded) + def some_bounds(): brd = [None] + range(-2, 3) for lower in brd: @@ -240,8 +306,6 @@ def test_div_bound(): - from rpython.rtyper.lltypesystem import lltype - from rpython.rtyper.lltypesystem.lloperation import llop for _, _, b1 in some_bounds(): for _, _, b2 in some_bounds(): b3 = b1.py_div_bound(b2) @@ -261,6 +325,15 @@ assert a.contains(-3) assert a.contains(0) +def test_mod_bound(): + for _, _, b1 in some_bounds(): + for _, _, b2 in some_bounds(): + b3 = b1.mod_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) # Python-style div def test_sub_bound(): for _, _, b1 in some_bounds(): @@ -275,6 +348,25 @@ assert not a.contains(-1) assert not a.contains(4) +def test_and_bound(): + for _, _, b1 in some_bounds(): + for _, _, b2 in some_bounds(): + b3 = b1.and_bound(b2) + for n1 in nbr: + for n2 in nbr: + if b1.contains(n1) and b2.contains(n2): + assert b3.contains(n1 & n2) + +def test_or_bound(): + for _, _, b1 in some_bounds(): + for _, _, b2 in some_bounds(): + b3 = b1.or_bound(b2) + for n1 in nbr: + for n2 in nbr: + if b1.contains(n1) and b2.contains(n2): + assert b3.contains(n1 | n2) + assert b3.contains(n1 ^ n2) # we use it for xor too + def test_next_pow2_m1(): assert next_pow2_m1(0) == 0 @@ -285,3 +377,82 @@ assert next_pow2_m1(80) == 127 assert next_pow2_m1((1 << 32) - 5) == (1 << 32) - 1 assert next_pow2_m1((1 << 64) - 1) == (1 << 64) - 1 + + +@given(bound_with_contained_number, bound_with_contained_number) +def test_add_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + print b1, n1 + print b2, n2 + b3 = b1.add_bound(b2) + try: + r = ovfcheck(n1 + n2) + except OverflowError: + assert not b3.bounded() + else: + assert b3.contains(r) + +@given(bound_with_contained_number, bound_with_contained_number) +def test_sub_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + print b1, n1 + print b2, n2 + b3 = b1.sub_bound(b2) + try: + r = ovfcheck(n1 - n2) + except OverflowError: + assert not b3.bounded() + else: + assert b3.contains(r) + +@given(bound_with_contained_number, bound_with_contained_number) +def test_mul_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + b3 = b1.mul_bound(b2) + try: + r = ovfcheck(n1 * n2) + except OverflowError: + assert not b3.bounded() + else: + assert b3.contains(r) + +@given(bound_with_contained_number, bound_with_contained_number) +def test_div_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + b3 = b1.py_div_bound(b2) + if n1 == -sys.maxint-1 and n2 == -1: + return # overflow + if n2 != 0: + assert b3.contains(n1 / n2) # Python-style div + +@given(bound_with_contained_number, bound_with_contained_number) +def test_mod_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + b3 = b1.mod_bound(b2) + if n1 == -sys.maxint-1 and n2 == -1: + return # overflow + if n2 != 0: + assert b3.contains(n1 % n2) # Python-style mod + +@given(bound_with_contained_number, bound_with_contained_number) +def test_and_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + b3 = b1.and_bound(b2) + r = n1 & n2 + assert b3.contains(r) + +@given(bound_with_contained_number, bound_with_contained_number) +def test_or_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + b3 = b1.or_bound(b2) + r = n1 | n2 + assert b3.contains(r) + r = n1 ^ n2 + assert b3.contains(r) _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit