better reasoning about upper bounds of or and xor, and about lower bounds of or

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]