Reviewers: titzer,
Description:
Precise shift right result type derivation for all int32 input ranges.
The typer can do better for the shift right operation, and can compute
the result range precisely and very simply in one line of code for
each limit. The patch also canonicalizes the shift range which gives a
precise result range for all int32 shift ranges.
BUG=
Please review this at https://codereview.chromium.org/1121573004/
Base URL: https://chromium.googlesource.com/v8/v8.git@master
Affected files (+60, -24 lines):
M src/compiler/typer.cc
M test/unittests/compiler/typer-unittest.cc
Index: src/compiler/typer.cc
diff --git a/src/compiler/typer.cc b/src/compiler/typer.cc
index
6fd609f2ab2ef6fad23189d1585ce6b7b181afcc..6d5f27e43d9d30d855936803a3fea13c6edaf46f
100644
--- a/src/compiler/typer.cc
+++ b/src/compiler/typer.cc
@@ -987,32 +987,29 @@ Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs,
Type* rhs, Typer* t) {
Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
lhs = NumberToInt32(ToNumber(lhs, t), t);
- rhs = NumberToUint32(ToNumber(rhs, t), t);
- double min = kMinInt;
- double max = kMaxInt;
- if (lhs->Min() >= 0) {
- // Right-shifting a non-negative value cannot make it negative, nor
larger.
- min = std::max(min, 0.0);
- max = std::min(max, lhs->Max());
- if (rhs->Min() > 0 && rhs->Max() <= 31) {
- max = static_cast<int>(max) >> static_cast<int>(rhs->Min());
- }
- }
- if (lhs->Max() < 0) {
- // Right-shifting a negative value cannot make it non-negative, nor
smaller.
- min = std::max(min, lhs->Min());
- max = std::min(max, -1.0);
- if (rhs->Min() > 0 && rhs->Max() <= 31) {
- min = static_cast<int>(min) >> static_cast<int>(rhs->Min());
+ rhs = NumberToInt32(ToNumber(rhs, t), t);
+
+ // Canonicalize the shift range to 0 to 31.
+ int32_t shift_min = rhs->Min();
+ int32_t shift_max = rhs->Max();
+ if ((int64_t(shift_max) - int64_t(shift_min)) >= 31) {
+ shift_min = 0;
+ shift_max = 31;
+ } else {
+ shift_min &= 0x1f;
+ shift_max &= 0x1f;
+ if (shift_min > shift_max) {
+ shift_min = 0;
+ shift_max = 31;
}
}
- if (rhs->Min() > 0 && rhs->Max() <= 31) {
- // Right-shifting by a positive value yields a small integer value.
- double shift_min = kMinInt >> static_cast<int>(rhs->Min());
- double shift_max = kMaxInt >> static_cast<int>(rhs->Min());
- min = std::max(min, shift_min);
- max = std::min(max, shift_max);
- }
+ DCHECK(shift_min >= 0 && shift_max <= 31);
+
+ int32_t lmin = lhs->Min();
+ int32_t min = std::min(std::max(lmin, 0) >> shift_max, lmin >>
shift_min);
+ int32_t lmax = lhs->Max();
+ int32_t max = std::max(lmax >> shift_min, std::min(lmax, -1) >>
shift_max);
+
// TODO(jarin) Ideally, the following micro-optimization should be
performed
// by the type constructor.
if (max != Type::Signed32()->Max() || min != Type::Signed32()->Min()) {
Index: test/unittests/compiler/typer-unittest.cc
diff --git a/test/unittests/compiler/typer-unittest.cc
b/test/unittests/compiler/typer-unittest.cc
index
f977c6fddd4d26a7d6928cee22ce734e5b9fb67e..a8398bb911c375b8892ccf1cb402c9bea197dd13
100644
--- a/test/unittests/compiler/typer-unittest.cc
+++ b/test/unittests/compiler/typer-unittest.cc
@@ -146,6 +146,37 @@ class TyperTest : public TypedGraphTest {
}
}
+ // Careful, this function scales poorly.
+ template <class BinaryFunction>
+ void TestPreciseBinaryArithOp(const Operator* op, BinaryFunction opfun,
+ int32_t llow, int32_t lhigh, int32_t linc,
+ int32_t rlow, int32_t rhigh, int32_t rinc)
{
+ for (int64_t lmin = llow; lmin <= lhigh; lmin += linc) {
+ for (int64_t lmax = lmin; lmax <= lhigh; lmax += linc) {
+ for (int64_t rmin = rlow; rmin <= rhigh; rmin += rinc) {
+ for (int64_t rmax = rmin; rmax <= rhigh; rmax += rinc) {
+ Type* r1 = NewRange(lmin, lmax);
+ Type* r2 = NewRange(rmin, rmax);
+ Type* derived_type = TypeBinaryOp(op, r1, r2);
+
+ double min = +V8_INFINITY, max = -V8_INFINITY;
+ for (int64_t x1 = lmin; x1 <= lmax; x1++) {
+ for (int64_t x2 = rmin; x2 <= rmax; x2++) {
+ double result_value = opfun(int32_t(x1), int32_t(x2));
+ if (result_value < min) min = result_value;
+ if (result_value > max) max = result_value;
+ }
+ }
+ Type* expected_type = NewRange(min, max);
+
+ EXPECT_TRUE(derived_type->Is(expected_type));
+ EXPECT_TRUE(expected_type->Is(derived_type));
+ }
+ }
+ }
+ }
+ }
+
template <class BinaryFunction>
void TestBinaryCompareOp(const Operator* op, BinaryFunction opfun) {
for (int i = 0; i < 100; ++i) {
@@ -287,6 +318,14 @@ TEST_F(TyperTest, TypeJSShiftLeft) {
TEST_F(TyperTest, TypeJSShiftRight) {
TestBinaryBitOp(javascript_.ShiftRight(LanguageMode::SLOPPY),
shift_right);
TestBinaryBitOp(javascript_.ShiftRight(LanguageMode::STRONG),
shift_right);
+ TestPreciseBinaryArithOp(javascript_.ShiftRight(LanguageMode::SLOPPY),
+ shift_right, -16, 15, 1, 0, 31, 1);
+ TestPreciseBinaryArithOp(javascript_.ShiftRight(LanguageMode::STRONG),
+ shift_right, -16, 15, 1, 0, 31, 1);
+ TestPreciseBinaryArithOp(javascript_.ShiftRight(LanguageMode::SLOPPY),
+ shift_right, -8, 7, 1, -64, 63, 1);
+ TestPreciseBinaryArithOp(javascript_.ShiftRight(LanguageMode::STRONG),
+ shift_right, -8, 7, 1, -64, 63, 1);
}
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
