Author: fijal Branch: mmap-for-arenas Changeset: r93221:6fb9f1a724da Date: 2017-11-30 18:38 +0200 http://bitbucket.org/pypy/pypy/changeset/6fb9f1a724da/
Log: merge default 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,6 +25,19 @@ 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 @@ -37,7 +50,7 @@ return dispatch_postprocess(self, op) def propagate_bounds_backward(self, box): - # FIXME: This takes care of the instruction where box is the result + # FIXME: This takes care of the instruction where box is the reuslt # but the bounds produced by all instructions where box is # an argument might also be tighten b = self.getintbound(box) @@ -78,8 +91,14 @@ b1 = self.getintbound(v1) v2 = self.get_box_replacement(op.getarg(1)) b2 = self.getintbound(v2) - b = b1.or_bound(b2) - self.getintbound(op).intersect(b) + 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)) optimize_INT_OR = optimize_INT_OR_or_XOR optimize_INT_XOR = optimize_INT_OR_or_XOR @@ -93,8 +112,15 @@ def postprocess_INT_AND(self, op): b1 = self.getintbound(op.getarg(0)) b2 = self.getintbound(op.getarg(1)) - b = b1.and_bound(b2) - self.getintbound(op).intersect(b) + 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) def optimize_INT_SUB(self, op): return self.emit(op) @@ -185,10 +211,16 @@ 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)) - r = self.getintbound(op) - r.intersect(b1.mod_bound(b2)) + 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)) def optimize_INT_LSHIFT(self, op): return self.emit(op) @@ -404,7 +436,7 @@ def optimize_INT_FORCE_GE_ZERO(self, op): b = self.getintbound(op.getarg(0)) - if b.known_nonnegative(): + if b.known_ge(IntBound(0, 0)): self.make_equal_to(op, op.getarg(0)) else: return self.emit(op) @@ -615,7 +647,7 @@ if r.is_constant(): if r.getint() == valnonzero: b1 = self.getintbound(op.getarg(0)) - if b1.known_nonnegative(): + if b1.known_ge(IntBound(0, 0)): 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,19 +12,6 @@ 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') @@ -105,9 +92,6 @@ 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 @@ -208,22 +192,10 @@ 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_nonnegative() and \ + other.known_ge(IntBound(0, 0)) and \ other.known_lt(IntBound(LONG_BIT, LONG_BIT)): try: vals = (ovfcheck(self.upper << other.upper), @@ -239,7 +211,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_nonnegative() and \ + other.known_ge(IntBound(0, 0)) and \ other.known_lt(IntBound(LONG_BIT, LONG_BIT)): vals = (self.upper >> other.upper, self.upper >> other.lower, @@ -249,31 +221,7 @@ 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): - 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): @@ -334,7 +282,7 @@ guards.append(op) def is_bool(self): - return (self.bounded() and self.known_nonnegative() and + return (self.bounded() and self.known_ge(ConstIntBound(0)) and self.known_le(ConstIntBound(1))) def make_bool(self): @@ -349,7 +297,7 @@ if self.known_gt(IntBound(0, 0)) or \ self.known_lt(IntBound(0, 0)): return INFO_NONNULL - if self.known_nonnegative() and \ + if self.known_ge(IntBound(0, 0)) 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,34 +1,12 @@ from rpython.jit.metainterp.optimizeopt.intutils import IntBound, IntUpperBound, \ - IntLowerBound, IntUnbounded, next_pow2_m1 + IntLowerBound, IntUnbounded +from rpython.jit.metainterp.optimizeopt.intbounds import next_pow2_m1 from copy import copy import sys -from rpython.rlib.rarithmetic import LONG_BIT, ovfcheck +from rpython.rlib.rarithmetic import LONG_BIT -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): +def bound(a,b): if a is None and b is None: return IntUnbounded() elif a is None: @@ -36,55 +14,11 @@ 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: @@ -306,6 +240,8 @@ 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) @@ -325,15 +261,6 @@ 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(): @@ -348,25 +275,6 @@ 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 @@ -377,82 +285,3 @@ 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