Author: Carl Friedrich Bolz-Tereick <cfb...@gmx.de>
Branch: intbound-improvements
Changeset: r93252:3485b3be23ea
Date: 2017-12-03 11:17 +0100
http://bitbucket.org/pypy/pypy/changeset/3485b3be23ea/
Log: separate implementations of or and xor, improve upper bounds on both
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
@@ -62,18 +62,22 @@
postprocess_GUARD_FALSE = _postprocess_guard_true_false_value
postprocess_GUARD_VALUE = _postprocess_guard_true_false_value
- def optimize_INT_OR_or_XOR(self, op):
+ def optimize_INT_OR(self, op):
v1 = self.get_box_replacement(op.getarg(0))
v2 = self.get_box_replacement(op.getarg(1))
if v1 is v2:
- if op.getopnum() == rop.INT_OR:
- self.make_equal_to(op, v1)
- else:
- self.make_constant_int(op, 0)
+ self.make_equal_to(op, v1)
return None
return self.emit(op)
- def postprocess_INT_OR_or_XOR(self, op):
+ def optimize_INT_XOR(self, op):
+ v1 = self.get_box_replacement(op.getarg(0))
+ v2 = self.get_box_replacement(op.getarg(1))
+ if v1 is v2:
+ self.make_constant_int(op, 0)
+ return self.emit(op)
+
+ def postprocess_INT_OR(self, op):
v1 = self.get_box_replacement(op.getarg(0))
b1 = self.getintbound(v1)
v2 = self.get_box_replacement(op.getarg(1))
@@ -81,11 +85,13 @@
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
-
- postprocess_INT_OR = postprocess_INT_OR_or_XOR
- postprocess_INT_XOR = postprocess_INT_OR_or_XOR
+ def postprocess_INT_XOR(self, op):
+ v1 = self.get_box_replacement(op.getarg(0))
+ b1 = self.getintbound(v1)
+ v2 = self.get_box_replacement(op.getarg(1))
+ b2 = self.getintbound(v2)
+ b = b1.xor_bound(b2)
+ self.getintbound(op).intersect(b)
def optimize_INT_AND(self, op):
return self.emit(op)
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
@@ -1,8 +1,6 @@
import sys
from rpython.rlib.rarithmetic import ovfcheck, LONG_BIT, maxint, is_valid_int
from rpython.rlib.objectmodel import we_are_translated
-from rpython.rtyper.lltypesystem import lltype
-from rpython.rtyper.lltypesystem.lloperation import llop
from rpython.jit.metainterp.resoperation import rop, ResOperation
from rpython.jit.metainterp.optimizeopt.info import AbstractInfo,
INFO_NONNULL,\
INFO_UNKNOWN, INFO_NULL
@@ -25,6 +23,15 @@
n |= n >> 32
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 ^
+ add = ovfcheck(upper1 + upper2)
+ except OverflowError:
+ return pow2
+ else:
+ return min(pow2, add)
class IntBound(AbstractInfo):
_attrs_ = ('has_upper', 'has_lower', 'upper', 'lower')
@@ -277,13 +284,27 @@
r = IntUnbounded()
if self.known_nonnegative() and \
other.known_nonnegative():
+ r.make_ge(IntBound(0, 0))
if self.has_upper and other.has_upper:
- mostsignificant = self.upper | other.upper
- r.intersect(IntBound(0, next_pow2_m1(mostsignificant)))
+ r.intersect(IntBound(0, 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(IntBound(lower, lower))
+ return r
+
+ def xor_bound(self, other):
+ r = IntUnbounded()
+ if self.known_nonnegative() and \
+ other.known_nonnegative():
+ if self.has_upper and other.has_upper:
+ r.intersect(IntBound(0, upper_bound_or_xor(self.upper,
other.upper)))
else:
r.make_ge(IntBound(0, 0))
return r
+
def contains(self, val):
if not we_are_translated():
assert not isinstance(val, long)
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
@@ -418,6 +418,15 @@
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():
@@ -426,7 +435,24 @@
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():
@@ -515,5 +541,11 @@
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)
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
