From bfca40151ca0d6f97a8ae8a220cd2f6f95efc5d4 Mon Sep 17 00:00:00 2001 From: Carl Friedrich Bolz-Tereick Date: Wed, 29 Apr 2020 11:06:35 +0200 Subject: better reasoning about upper bounds of or and xor, and about lower bounds of or --- rpython/jit/metainterp/optimizeopt/intutils.py | 32 +++++++-- .../metainterp/optimizeopt/test/test_intbound.py | 34 ++++++++- .../optimizeopt/test/test_optimizebasic.py | 80 ++++++++++++++++++++++ 3 files changed, 141 insertions(+), 5 deletions(-) diff --git a/rpython/jit/metainterp/optimizeopt/intutils.py b/rpython/jit/metainterp/optimizeopt/intutils.py index 9f2ced0f00..49e2b3498e 100644 --- a/rpython/jit/metainterp/optimizeopt/intutils.py +++ b/rpython/jit/metainterp/optimizeopt/intutils.py @@ -26,6 +26,18 @@ def next_pow2_m1(n): return n +def upper_bound_or_xor(upper1, upper2): + pow2 = next_pow2_m1(upper1 | upper2) + try: + # addition gives an ok (but not tight) upper bound of | and ^ (for + # known non-negative numbers) + add = ovfcheck(upper1 + upper2) + except OverflowError: + return pow2 + else: + return min(pow2, add) + + class IntBound(AbstractInfo): _attrs_ = ('has_upper', 'has_lower', 'upper', 'lower') @@ -302,11 +314,23 @@ class IntBound(AbstractInfo): r = IntUnbounded() if self.known_nonnegative() and \ other.known_nonnegative(): + r.make_ge_const(0) 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_const(0) + r.make_le_const(upper_bound_or_xor(self.upper, other.upper)) + if self.has_lower and other.has_lower: + # max of the two lower bounds gives an ok (but not tight) lower + # bound of or + lower = max(self.lower, other.lower) + r.make_ge_const(lower) + return r + + def xor_bound(self, other): + r = IntUnbounded() + if self.known_nonnegative() and \ + other.known_nonnegative(): + r.make_ge_const(0) + if self.has_upper and other.has_upper: + r.make_le_const(upper_bound_or_xor(self.upper, other.upper)) return r def invert_bound(self): diff --git a/rpython/jit/metainterp/optimizeopt/test/test_intbound.py b/rpython/jit/metainterp/optimizeopt/test/test_intbound.py index 0b782b4e60..6231baa03e 100644 --- a/rpython/jit/metainterp/optimizeopt/test/test_intbound.py +++ b/rpython/jit/metainterp/optimizeopt/test/test_intbound.py @@ -350,6 +350,15 @@ def test_and_bound(): if b1.contains(n1) and b2.contains(n2): assert b3.contains(n1 & n2) +def test_or_bound_explicit(): + a = bound(0b10, 0b100) + b = bound(0, 0b10) + c = a.or_bound(b) + assert c.contains(0b10) + assert c.contains(0b100 | 0b10) + assert not c.contains(1) + assert not c.contains(0b111) + def test_or_bound(): for _, _, b1 in some_bounds(): for _, _, b2 in some_bounds(): @@ -358,7 +367,24 @@ def test_or_bound(): 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_xor_bound_explicit(): + a = bound(0b10, 0b100) + b = bound(0, 0b10) + c = a.or_bound(b) + assert c.contains(0b10) + assert c.contains(0b100 | 0b10) + assert not c.contains(-1) + assert not c.contains(0b111) + +def test_xor_bound(): + for _, _, b1 in some_bounds(): + for _, _, b2 in some_bounds(): + b3 = b1.xor_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_next_pow2_m1(): @@ -475,6 +501,12 @@ def test_or_bound_random(t1, t2): b3 = b1.or_bound(b2) r = n1 | n2 assert b3.contains(r) + +@given(bound_with_contained_number, bound_with_contained_number) +def test_xor_bound_random(t1, t2): + b1, n1 = t1 + b2, n2 = t2 + b3 = b1.xor_bound(b2) r = n1 ^ n2 assert b3.contains(r) diff --git a/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py b/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py index ac115639fc..44189ad6af 100644 --- a/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py +++ b/rpython/jit/metainterp/optimizeopt/test/test_optimizebasic.py @@ -5955,6 +5955,18 @@ class TestOptimizeBasic(BaseTestBasic): """ self.optimize_loop(ops, expected) + def test_int_xor_same_arg(self): + ops = """ + [i0] + i1 = int_xor(i0, i0) + jump(i1) + """ + expected = """ + [i0] + jump(0) + """ + self.optimize_loop(ops, expected) + def test_consecutive_getinteriorfields(self): py.test.skip("we want this to pass") ops = """ @@ -6304,6 +6316,74 @@ class TestOptimizeBasic(BaseTestBasic): """ self.optimize_loop(ops, expected) + def test_int_or_xor_upper(self): + ops = """ + [p0, p1] + i0 = arraylen_gc(p0, descr=arraydescr) + i2 = int_lt(i0, 17) + guard_true(i2) [] + i1 = arraylen_gc(p1, descr=arraydescr) + i3 = int_lt(i1, 17) + guard_true(i3) [] + i57 = int_or(i1, i0) + i62 = int_lt(i57, 40) + guard_true(i62) [] + """ + expected = """ + [p0, p1] + i0 = arraylen_gc(p0, descr=arraydescr) + i2 = int_lt(i0, 17) + guard_true(i2) [] + i1 = arraylen_gc(p1, descr=arraydescr) + i3 = int_lt(i1, 17) + guard_true(i3) [] + i57 = int_or(i1, i0) + """ + self.optimize_loop(ops, expected) + self.optimize_loop(ops.replace("int_or", "int_xor"), expected.replace("int_or", "int_xor")) + + def test_int_or_lower(self): + ops = """ + [i0, i1] + i2 = int_ge(i0, 17) + guard_true(i2) [] + i3 = int_ge(i1, 100) + guard_true(i3) [] + i57 = int_or(i1, i0) + i62 = int_ge(i57, 100) + guard_true(i62) [] + """ + expected = """ + [i0, i1] + i2 = int_ge(i0, 17) + guard_true(i2) [] + i3 = int_ge(i1, 100) + guard_true(i3) [] + i57 = int_or(i1, i0) + """ + self.optimize_loop(ops, expected) + + def test_int_xor_lower(self): + ops = """ + [i0, i1] + i2 = int_ge(i0, 17) + guard_true(i2) [] + i3 = int_ge(i1, 100) + guard_true(i3) [] + i57 = int_xor(i1, i0) + i62 = int_ge(i57, 0) + guard_true(i62) [] + """ + expected = """ + [i0, i1] + i2 = int_ge(i0, 17) + guard_true(i2) [] + i3 = int_ge(i1, 100) + guard_true(i3) [] + i57 = int_xor(i1, i0) + """ + self.optimize_loop(ops, expected) + def test_convert_float_bytes_to_longlong(self): ops = """ [f0, i0] -- cgit v1.2.3-65-gdbad