diff options
| -rw-r--r-- | pypy/doc/whatsnew-head.rst | 5 | ||||
| -rw-r--r-- | rpython/jit/metainterp/optimizeopt/intbounds.py | 107 | ||||
| -rw-r--r-- | rpython/jit/metainterp/optimizeopt/intutils.py | 91 | ||||
| -rw-r--r-- | rpython/jit/metainterp/optimizeopt/rewrite.py | 20 | ||||
| -rw-r--r-- | rpython/jit/metainterp/optimizeopt/test/test_intbound.py | 28 | ||||
| -rw-r--r-- | rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py | 78 | ||||
| -rw-r--r-- | rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py | 11 |
7 files changed, 256 insertions, 84 deletions
diff --git a/pypy/doc/whatsnew-head.rst b/pypy/doc/whatsnew-head.rst index 7a4e4c67bb..cf7632de21 100644 --- a/pypy/doc/whatsnew-head.rst +++ b/pypy/doc/whatsnew-head.rst @@ -80,3 +80,8 @@ Backport changes to ``_ctypes`` needed for maxos BigSur from py3.7 Updated the API to the latest cppyy_backend (1.14.2), made all types used consistent to avoid void*/long casting problems on Win64, and added several new "builtin" types (wide chars, complex, etc.). + + +.. branch: intbound-improvements-3 + +Refactor the intbound analysis in the JIT diff --git a/rpython/jit/metainterp/optimizeopt/intbounds.py b/rpython/jit/metainterp/optimizeopt/intbounds.py index a9445a5f8e..5e99a4999f 100644 --- a/rpython/jit/metainterp/optimizeopt/intbounds.py +++ b/rpython/jit/metainterp/optimizeopt/intbounds.py @@ -1,8 +1,7 @@ import sys from rpython.jit.metainterp.history import ConstInt from rpython.jit.metainterp.optimize import InvalidLoop -from rpython.jit.metainterp.optimizeopt.intutils import (IntBound, - IntLowerBound, IntUpperBound, ConstIntBound) +from rpython.jit.metainterp.optimizeopt.intutils import IntBound from rpython.jit.metainterp.optimizeopt.optimizer import (Optimization, CONST_1, CONST_0) from rpython.jit.metainterp.optimizeopt.util import ( @@ -43,8 +42,8 @@ class OptIntBounds(Optimization): # but the bounds produced by all instructions where box is # an argument might also be tighten b = self.getintbound(box) - if b.has_lower and b.has_upper and b.lower == b.upper: - self.make_constant_int(box, b.lower) + if b.is_constant(): + self.make_constant_int(box, b.getint()) box1 = self.optimizer.as_operation(box) if box1 is not None: @@ -214,7 +213,7 @@ class OptIntBounds(Optimization): # intbound.lshift_bound checks for an overflow and if the # lshift can be proven not to overflow sets b.has_upper and # b.has_lower - if b.has_lower and b.has_upper: + if b.bounded(): # Synthesize the reverse op for optimize_default to reuse self.pure_from_args(rop.INT_RSHIFT, [op, arg1], arg0) @@ -223,7 +222,7 @@ class OptIntBounds(Optimization): b1 = self.getintbound(op.getarg(0)) b2 = self.getintbound(op.getarg(1)) b = b1.rshift_bound(b2) - if b.has_lower and b.has_upper and b.lower == b.upper: + if b.is_constant(): # constant result (likely 0, for rshifts that kill all bits) self.make_constant_int(op, b.lower) return None @@ -489,7 +488,30 @@ class OptIntBounds(Optimization): numbits = op.getarg(1).getint() * 8 start = -(1 << (numbits - 1)) stop = 1 << (numbits - 1) - bounds = IntBound(start, stop - 1) + bres = self.getintbound(op) + bres.intersect_const(start, stop - 1) + + def postprocess_INT_INVERT(self, op): + b = self.getintbound(op.getarg(0)) + bounds = b.invert_bound() + bres = self.getintbound(op) + bres.intersect(bounds) + + def propagate_bounds_INT_INVERT(self, op): + b = self.getintbound(op.getarg(0)) + bres = self.getintbound(op) + bounds = bres.invert_bound() + b.intersect(bounds) + + def propagate_bounds_INT_NEG(self, op): + b = self.getintbound(op.getarg(0)) + bres = self.getintbound(op) + bounds = bres.neg_bound() + b.intersect(bounds) + + def postprocess_INT_NEG(self, op): + b = self.getintbound(op.getarg(0)) + bounds = b.neg_bound() bres = self.getintbound(op) bres.intersect(bounds) @@ -523,12 +545,11 @@ class OptIntBounds(Optimization): v1 = self.getintbound(op) v2 = getptrinfo(op.getarg(0)) intbound = self.getintbound(op.getarg(1)) - if (intbound.has_lower and v2 is not None and - v2.getlenbound(vstring.mode_string) is not None): - lb = IntLowerBound(intbound.lower + 1) - v2.getlenbound(vstring.mode_string).make_ge(lb) - v1.make_ge(IntLowerBound(0)) - v1.make_lt(IntUpperBound(256)) + if intbound.has_lower and v2 is not None: + lenbound = v2.getlenbound(vstring.mode_string) + if lenbound is not None: + lenbound.make_gt_const(intbound.lower) + v1.intersect_const(0, 255) def optimize_GETFIELD_RAW_I(self, op): return self.emit(op) @@ -537,8 +558,7 @@ class OptIntBounds(Optimization): descr = op.getdescr() if descr.is_integer_bounded(): b1 = self.getintbound(op) - b1.make_ge(IntLowerBound(descr.get_integer_min())) - b1.make_le(IntUpperBound(descr.get_integer_max())) + b1.intersect_const(descr.get_integer_min(), descr.get_integer_max()) optimize_GETFIELD_RAW_F = optimize_GETFIELD_RAW_I optimize_GETFIELD_RAW_R = optimize_GETFIELD_RAW_I @@ -567,8 +587,7 @@ class OptIntBounds(Optimization): descr = op.getdescr() if descr and descr.is_item_integer_bounded(): intbound = self.getintbound(op) - intbound.make_ge(IntLowerBound(descr.get_item_integer_min())) - intbound.make_le(IntUpperBound(descr.get_item_integer_max())) + intbound.intersect_const(descr.get_item_integer_min(), descr.get_item_integer_max()) optimize_GETARRAYITEM_RAW_F = optimize_GETARRAYITEM_RAW_I optimize_GETARRAYITEM_GC_I = optimize_GETARRAYITEM_RAW_I @@ -585,13 +604,13 @@ class OptIntBounds(Optimization): def postprocess_UNICODEGETITEM(self, op): b1 = self.getintbound(op) - b1.make_ge(IntLowerBound(0)) + b1.make_ge_const(0) v2 = getptrinfo(op.getarg(0)) intbound = self.getintbound(op.getarg(1)) - if (intbound.has_lower and v2 is not None and - v2.getlenbound(vstring.mode_unicode) is not None): - lb = IntLowerBound(intbound.lower + 1) - v2.getlenbound(vstring.mode_unicode).make_ge(lb) + if intbound.has_lower and v2 is not None: + lenbound = v2.getlenbound(vstring.mode_unicode) + if lenbound is not None: + lenbound.make_gt_const(intbound.lower) def make_int_lt(self, box1, box2): b1 = self.getintbound(box1) @@ -655,7 +674,7 @@ class OptIntBounds(Optimization): b2 = self.getintbound(box2) if b2.known_nonnegative: b1 = self.getintbound(box1) - if b1.make_lt(b2) | b1.make_ge(IntBound(0, 0)): + if b1.make_lt(b2) | b1.make_ge_const(0): self.propagate_bounds_backward(box1) #if b2.make_gt(b1): # ^^ probably correct but I fail to see a case where it is helpful @@ -666,7 +685,7 @@ class OptIntBounds(Optimization): b2 = self.getintbound(box2) if b2.known_nonnegative: b1 = self.getintbound(box1) - if b1.make_le(b2) | b1.make_ge(IntBound(0, 0)): + if b1.make_le(b2) | b1.make_ge_const(0): self.propagate_bounds_backward(box1) #if b2.make_ge(b1): # ^^ probably correct but I fail to see a case where it is helpful @@ -718,25 +737,23 @@ class OptIntBounds(Optimization): def propagate_bounds_INT_EQ(self, op): r = self.getintbound(op) - if r.is_constant(): - if r.equal(1): - b1 = self.getintbound(op.getarg(0)) - b2 = self.getintbound(op.getarg(1)) - if b1.intersect(b2): - self.propagate_bounds_backward(op.getarg(0)) - if b2.intersect(b1): - self.propagate_bounds_backward(op.getarg(1)) + if r.equal(1): + b1 = self.getintbound(op.getarg(0)) + b2 = self.getintbound(op.getarg(1)) + if b1.intersect(b2): + self.propagate_bounds_backward(op.getarg(0)) + if b2.intersect(b1): + self.propagate_bounds_backward(op.getarg(1)) def propagate_bounds_INT_NE(self, op): r = self.getintbound(op) - if r.is_constant(): - if r.equal(0): - b1 = self.getintbound(op.getarg(0)) - b2 = self.getintbound(op.getarg(1)) - if b1.intersect(b2): - self.propagate_bounds_backward(op.getarg(0)) - if b2.intersect(b1): - self.propagate_bounds_backward(op.getarg(1)) + if r.equal(0): + b1 = self.getintbound(op.getarg(0)) + b2 = self.getintbound(op.getarg(1)) + if b1.intersect(b2): + self.propagate_bounds_backward(op.getarg(0)) + if b2.intersect(b1): + self.propagate_bounds_backward(op.getarg(1)) def _propagate_int_is_true_or_zero(self, op, valnonzero, valzero): if self.is_raw_ptr(op.getarg(0)): @@ -746,16 +763,10 @@ class OptIntBounds(Optimization): if r.getint() == valnonzero: b1 = self.getintbound(op.getarg(0)) if b1.known_nonnegative(): - b1.make_gt(IntBound(0, 0)) + b1.make_gt_const(0) self.propagate_bounds_backward(op.getarg(0)) elif r.getint() == valzero: - b1 = self.getintbound(op.getarg(0)) - # XXX remove this hack maybe? - # Clever hack, we can't use self.make_constant_int yet because - # the args aren't in the values dictionary yet so it runs into - # an assert, this is a clever way of expressing the same thing. - b1.make_ge(IntBound(0, 0)) - b1.make_lt(IntBound(1, 1)) + self.make_constant_int(op.getarg(0), 0) self.propagate_bounds_backward(op.getarg(0)) def propagate_bounds_INT_IS_TRUE(self, op): diff --git a/rpython/jit/metainterp/optimizeopt/intutils.py b/rpython/jit/metainterp/optimizeopt/intutils.py index 2590aad376..9f2ced0f00 100644 --- a/rpython/jit/metainterp/optimizeopt/intutils.py +++ b/rpython/jit/metainterp/optimizeopt/intutils.py @@ -109,14 +109,34 @@ class IntBound(AbstractInfo): def bounded(self): return self.has_lower and self.has_upper + def known_lt_const(self, other): + if self.has_upper: + return self.upper < other + return False + + def known_le_const(self, other): + if self.has_upper: + return self.upper <= other + return False + + def known_gt_const(self, other): + if self.has_lower: + return self.lower > other + return False + + def known_ge_const(self, other): + if self.has_upper: + return self.upper >= other + return False + def known_lt(self, other): - if self.has_upper and other.has_lower and self.upper < other.lower: - return True + if other.has_lower: + return self.known_lt_const(other.lower) return False def known_le(self, other): - if self.has_upper and other.has_lower and self.upper <= other.lower: - return True + if other.has_lower: + return self.known_le_const(other.lower) return False def known_gt(self, other): @@ -130,19 +150,18 @@ class IntBound(AbstractInfo): def intersect(self, other): r = False - if other.has_lower: - if other.lower > self.lower or not self.has_lower: - self.lower = other.lower - self.has_lower = True + if self.make_ge_const(other.lower): r = True - if other.has_upper: - if other.upper < self.upper or not self.has_upper: - self.upper = other.upper - self.has_upper = True + if self.make_le_const(other.upper): r = True + return r + def intersect_const(self, lower, upper): + r = self.make_ge_const(lower) + if self.make_le_const(upper): + r = True return r def add(self, offset): @@ -241,10 +260,9 @@ class IntBound(AbstractInfo): return r def lshift_bound(self, other): - if self.has_upper and self.has_lower and \ - other.has_upper and other.has_lower and \ + if self.bounded() and other.bounded() and \ other.known_nonnegative() and \ - other.known_lt(IntBound(LONG_BIT, LONG_BIT)): + other.known_lt_const(LONG_BIT): try: vals = (ovfcheck(self.upper << other.upper), ovfcheck(self.upper << other.lower), @@ -257,10 +275,9 @@ class IntBound(AbstractInfo): return IntUnbounded() def rshift_bound(self, other): - if self.has_upper and self.has_lower and \ - other.has_upper and other.has_lower and \ + if self.bounded() and other.bounded() and \ other.known_nonnegative() and \ - other.known_lt(IntBound(LONG_BIT, LONG_BIT)): + other.known_lt_const(LONG_BIT): vals = (self.upper >> other.upper, self.upper >> other.lower, self.lower >> other.upper, @@ -292,6 +309,36 @@ class IntBound(AbstractInfo): r.make_ge_const(0) return r + def invert_bound(self): + res = self.clone() + res.has_upper = False + if self.has_lower: + res.upper = ~self.lower + res.has_upper = True + res.has_lower = False + if self.has_upper: + res.lower = ~self.upper + res.has_lower = True + return res + + def neg_bound(self): + res = self.clone() + res.has_upper = False + if self.has_lower: + try: + res.upper = ovfcheck(-self.lower) + res.has_upper = True + except OverflowError: + pass + res.has_lower = False + if self.has_upper: + try: + res.lower = ovfcheck(-self.upper) + res.has_lower = True + except OverflowError: + pass + return res + def contains(self, val): if not we_are_translated(): assert not isinstance(val, long) @@ -356,7 +403,7 @@ class IntBound(AbstractInfo): def is_bool(self): return (self.bounded() and self.known_nonnegative() and - self.known_le(ConstIntBound(1))) + self.known_le_const(1)) def make_bool(self): self.intersect(IntBound(0, 1)) @@ -367,11 +414,11 @@ class IntBound(AbstractInfo): return ConstInt(self.getint()) def getnullness(self): - if self.known_gt(IntBound(0, 0)) or \ - self.known_lt(IntBound(0, 0)): + if self.known_gt_const(0) or \ + self.known_lt_const(0): return INFO_NONNULL if self.known_nonnegative() and \ - self.known_le(IntBound(0, 0)): + self.known_le_const(0): return INFO_NULL return INFO_UNKNOWN diff --git a/rpython/jit/metainterp/optimizeopt/rewrite.py b/rpython/jit/metainterp/optimizeopt/rewrite.py index 47b88dbfdf..abb5766fd3 100644 --- a/rpython/jit/metainterp/optimizeopt/rewrite.py +++ b/rpython/jit/metainterp/optimizeopt/rewrite.py @@ -4,7 +4,6 @@ from rpython.jit.metainterp import compile from rpython.jit.metainterp.history import ( Const, ConstInt, make_hashable_int, ConstFloat, CONST_NULL) from rpython.jit.metainterp.optimize import InvalidLoop -from rpython.jit.metainterp.optimizeopt.intutils import IntBound from rpython.jit.metainterp.optimizeopt.optimizer import ( Optimization, OptimizationResult, REMOVED, CONST_0, CONST_1) from rpython.jit.metainterp.optimizeopt.info import ( @@ -239,9 +238,9 @@ class OptRewrite(Optimization): b1 = self.getintbound(op.getarg(0)) b2 = self.getintbound(op.getarg(1)) - if b2.is_constant() and b2.getint() == 0: + if b2.equal(0): self.make_equal_to(op, op.getarg(0)) - elif b1.is_constant() and b1.getint() == 0: + elif b1.equal(0): self.make_constant_int(op, 0) else: return self.emit(op) @@ -250,9 +249,9 @@ class OptRewrite(Optimization): b1 = self.getintbound(op.getarg(0)) b2 = self.getintbound(op.getarg(1)) - if b2.is_constant() and b2.getint() == 0: + if b2.equal(0): self.make_equal_to(op, op.getarg(0)) - elif b1.is_constant() and b1.getint() == 0: + elif b1.equal(0): self.make_constant_int(op, 0) else: return self.emit(op) @@ -268,6 +267,9 @@ class OptRewrite(Optimization): else: return self.emit(op) + def postprocess_INT_INVERT(self, op): + self.optimizer.pure_from_args(rop.INT_INVERT, [op], op.getarg(0)) + def optimize_FLOAT_MUL(self, op): arg1 = op.getarg(0) arg2 = op.getarg(1) @@ -837,7 +839,7 @@ class OptRewrite(Optimization): arg2 = op.getarg(2) b2 = self.getintbound(arg2) - if b1.is_constant() and b1.getint() == 0: + if b1.equal(0): self.make_constant_int(op, 0) self.last_emitted_operation = REMOVED return True @@ -859,7 +861,7 @@ class OptRewrite(Optimization): return True else: from rpython.jit.metainterp.optimizeopt import intdiv - known_nonneg = b1.known_ge(IntBound(0, 0)) + known_nonneg = b1.known_nonnegative() operations = intdiv.division_operations(arg1, val, known_nonneg) newop = None for newop in operations: @@ -873,7 +875,7 @@ class OptRewrite(Optimization): arg2 = op.getarg(2) b2 = self.getintbound(arg2) - if b1.is_constant() and b1.getint() == 0: + if b1.equal(0): self.make_constant_int(op, 0) self.last_emitted_operation = REMOVED return True @@ -899,7 +901,7 @@ class OptRewrite(Optimization): return True else: from rpython.jit.metainterp.optimizeopt import intdiv - known_nonneg = b1.known_ge(IntBound(0, 0)) + known_nonneg = b1.known_nonnegative() operations = intdiv.modulo_operations(arg1, val, known_nonneg) newop = None for newop in operations: diff --git a/rpython/jit/metainterp/optimizeopt/test/test_intbound.py b/rpython/jit/metainterp/optimizeopt/test/test_intbound.py index 45b1635136..0b782b4e60 100644 --- a/rpython/jit/metainterp/optimizeopt/test/test_intbound.py +++ b/rpython/jit/metainterp/optimizeopt/test/test_intbound.py @@ -371,6 +371,19 @@ def test_next_pow2_m1(): assert next_pow2_m1((1 << 32) - 5) == (1 << 32) - 1 assert next_pow2_m1((1 << 64) - 1) == (1 << 64) - 1 +def test_invert_bound(): + for _, _, b1 in some_bounds(): + b2 = b1.invert_bound() + for n1 in nbr: + if b1.contains(n1): + assert b2.contains(~n1) + +def test_neg_bound(): + for _, _, b1 in some_bounds(): + b2 = b1.neg_bound() + for n1 in nbr: + if b1.contains(n1): + assert b2.contains(-n1) @given(bound_with_contained_number, bound_with_contained_number) def test_make_random(t1, t2): @@ -464,3 +477,18 @@ def test_or_bound_random(t1, t2): assert b3.contains(r) r = n1 ^ n2 assert b3.contains(r) + +@given(bound_with_contained_number) +def test_invert_bound_random(t1): + b1, n1 = t1 + b2 = b1.invert_bound() + assert b2.contains(~n1) + +@given(bound_with_contained_number) +def test_neg_bound_random(t1): + b1, n1 = t1 + b2 = b1.neg_bound() + if n1 != -sys.maxint - 1: + assert b2.contains(-n1) + else: + assert not b2.has_lower diff --git a/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py b/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py index 4daf55065d..ac115639fc 100644 --- a/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py +++ b/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py @@ -6325,3 +6325,81 @@ class TestOptimizeBasic(BaseTestBasic): escape_i(i0) """ self.optimize_loop(ops, expected) + + def test_int_invert(self): + ops = """ + [p0] + i1 = arraylen_gc(p0, descr=arraydescr) # known >= 0 + i2 = int_invert(i1) + i3 = int_lt(i2, 0) + guard_true(i3) [] + """ + expected = """ + [p0] + i1 = arraylen_gc(p0, descr=arraydescr) # known >= 0 + i2 = int_invert(i1) + """ + self.optimize_loop(ops, expected) + + def test_int_invert_invert(self): + ops = """ + [i1] + i2 = int_invert(i1) + i3 = int_invert(i2) + escape_i(i3) + """ + expected = """ + [i1] + i2 = int_invert(i1) + escape_i(i1) + """ + self.optimize_loop(ops, expected) + + def test_int_invert_postprocess(self): + ops = """ + [i1] + i2 = int_invert(i1) + i3 = int_lt(i2, 0) + guard_true(i3) [] + i4 = int_ge(i1, 0) + guard_true(i4) [] + """ + expected = """ + [i1] + i2 = int_invert(i1) + i3 = int_lt(i2, 0) + guard_true(i3) [] + """ + self.optimize_loop(ops, expected) + + def test_int_neg(self): + ops = """ + [p0] + i1 = arraylen_gc(p0, descr=arraydescr) # known >= 0 + i2 = int_neg(i1) + i3 = int_le(i2, 0) + guard_true(i3) [] + """ + expected = """ + [p0] + i1 = arraylen_gc(p0, descr=arraydescr) # known >= 0 + i2 = int_neg(i1) + """ + self.optimize_loop(ops, expected) + + def test_int_neg_postprocess(self): + ops = """ + [i1] + i2 = int_neg(i1) + i3 = int_le(i2, 0) + guard_true(i3) [] + i4 = int_ge(i1, 0) + guard_true(i4) [] + """ + expected = """ + [i1] + i2 = int_neg(i1) + i3 = int_le(i2, 0) + guard_true(i3) [] + """ + 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 index 4de28a02ba..3e1a2e64fd 100644 --- a/rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py +++ b/rpython/jit/metainterp/optimizeopt/test/test_optimizeopt.py @@ -8327,7 +8327,7 @@ class TestOptimizeOpt(BaseTestWithUnroll): ops = """ [p1, p2] i1 = getfield_gc_i(p1, descr=valuedescr) - setfield_gc(p2, i1, descr=nextdescr) + setfield_gc(p2, i1, descr=valuedescr3) i2 = int_neg(i1) call_n(i2, descr=nonwritedescr) jump(p1, p2) @@ -8335,7 +8335,7 @@ class TestOptimizeOpt(BaseTestWithUnroll): expected = """ [p1, p2, i2, i1] call_n(i2, descr=nonwritedescr) - setfield_gc(p2, i1, descr=nextdescr) + setfield_gc(p2, i1, descr=valuedescr3) jump(p1, p2, i2, i1) """ self.optimize_loop(ops, expected) @@ -8346,17 +8346,18 @@ class TestOptimizeOpt(BaseTestWithUnroll): # potential short boxes during tests ops = """ [p1, p2] - i1 = getfield_gc_i(p1, descr=nextdescr) + i1 = getfield_gc_i(p1, descr=valuedescr3) setfield_gc(p2, i1, descr=valuedescr) i2 = int_neg(i1) call_n(i2, descr=nonwritedescr) jump(p1, p2) """ expected = """ - [p1, p2, i2, i1] + [p1, p2, i1] + i2 = int_neg(i1) call_n(i2, descr=nonwritedescr) setfield_gc(p2, i1, descr=valuedescr) - jump(p1, p2, i2, i1) + jump(p1, p2, i1) """ self.optimize_loop(ops, expected) |