Revision: 6055
Author: [email protected]
Date: Thu Dec 16 10:01:36 2010
Log: Fix bugs in the range analysis for integers.
The overflow conditions were not correctly detected for
certain add, sub and mul instructions.
I replaced the previous code by using 64-bit arithmetic
to correctly identify overflows for *, + and -.
Review URL: http://codereview.chromium.org/5860009
http://code.google.com/p/v8/source/detail?r=6055
Added:
/branches/bleeding_edge/test/mjsunit/compiler/regress-intoverflow.js
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/compiler/regress-intoverflow.js
Thu Dec 16 10:01:36 2010
@@ -0,0 +1,62 @@
+// Copyright 2010 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Test overflow checks in optimized code.
+function testMul(a, b) {
+ a *= 2;
+ b *= 2;
+ if (a < 1 && b < 1) {
+ return a * b;
+ }
+}
+
+for (var i=0; i<10000000; i++) testMul(0,0);
+assertEquals(4611686018427388000, testMul(-0x40000000, -0x40000000));
+
+function testAdd(a, b) {
+ a *= 2;
+ b *= 2;
+ if (a < 1 && b < 1) {
+ return a + b;
+ }
+}
+
+for (var i=0; i<10000000; i++) testAdd(0,0);
+assertEquals(-4294967296, testAdd(-0x40000000, -0x40000000));
+
+
+function testSub(a, b) {
+ a *= 2;
+ b *= 2;
+ if (b == 2) {print(a); print(b);}
+ if (a < 1 && b < 3) {
+ return a - b;
+ }
+}
+
+for (var i=0; i<10000000; i++) testSub(0,0);
+assertEquals(-2147483650, testSub(-0x40000000, 1));
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Tue Dec 7
03:31:57 2010
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Thu Dec 16
10:01:36 2010
@@ -64,69 +64,34 @@
}
-static int32_t AddAssertNoOverflow(int32_t a, int32_t b) {
- ASSERT(static_cast<int64_t>(a + b) == (static_cast<int64_t>(a) +
- static_cast<int64_t>(b)));
- return a + b;
-}
-
-
-static int32_t SubAssertNoOverflow(int32_t a, int32_t b) {
- ASSERT(static_cast<int64_t>(a - b) == (static_cast<int64_t>(a) -
- static_cast<int64_t>(b)));
- return a - b;
-}
-
-
-static int32_t MulAssertNoOverflow(int32_t a, int32_t b) {
- ASSERT(static_cast<int64_t>(a * b) == (static_cast<int64_t>(a) *
- static_cast<int64_t>(b)));
- return a * b;
-}
-
-
-static int32_t AddWithoutOverflow(int32_t a, int32_t b) {
- if (b > 0) {
- if (a <= kMaxInt - b) return AddAssertNoOverflow(a, b);
+static int32_t ConvertAndSetOverflow(int64_t result, bool* overflow) {
+ if (result > kMaxInt) {
+ *overflow = true;
return kMaxInt;
- } else {
- if (a >= kMinInt - b) return AddAssertNoOverflow(a, b);
+ }
+ if (result < kMinInt) {
+ *overflow = true;
return kMinInt;
}
+ return static_cast<int32_t>(result);
}
-static int32_t SubWithoutOverflow(int32_t a, int32_t b) {
- if (b < 0) {
- if (a <= kMaxInt + b) return SubAssertNoOverflow(a, b);
- return kMaxInt;
- } else {
- if (a >= kMinInt + b) return SubAssertNoOverflow(a, b);
- return kMinInt;
- }
+static int32_t AddWithoutOverflow(int32_t a, int32_t b, bool* overflow) {
+ int64_t result = static_cast<int64_t>(a) + static_cast<int64_t>(b);
+ return ConvertAndSetOverflow(result, overflow);
}
-static int32_t MulWithoutOverflow(int32_t a, int32_t b, bool* overflow) {
- if (b == 0 || a == 0) return 0;
- if (a == 1) return b;
- if (b == 1) return a;
-
- int sign = 1;
- if ((a < 0 && b > 0) || (a > 0 && b < 0)) sign = -1;
- if (a < 0) a = -a;
- if (b < 0) b = -b;
-
- if (kMaxInt / b > a && a != kMinInt && b != kMinInt) {
- return MulAssertNoOverflow(a, b) * sign;
- }
-
- *overflow = true;
- if (sign == 1) {
- return kMaxInt;
- } else {
- return kMinInt;
- }
+static int32_t SubWithoutOverflow(int32_t a, int32_t b, bool* overflow) {
+ int64_t result = static_cast<int64_t>(a) - static_cast<int64_t>(b);
+ return ConvertAndSetOverflow(result, overflow);
+}
+
+
+static int32_t MulWithoutOverflow(int32_t a, int32_t b, bool* overflow) {
+ int64_t result = static_cast<int64_t>(a) * static_cast<int64_t>(b);
+ return ConvertAndSetOverflow(result, overflow);
}
@@ -143,39 +108,32 @@
}
-void Range::Add(int32_t value) {
+void Range::AddConstant(int32_t value) {
if (value == 0) return;
- lower_ = AddWithoutOverflow(lower_, value);
- upper_ = AddWithoutOverflow(upper_, value);
+ bool may_overflow = false; // Overflow is ignored here.
+ lower_ = AddWithoutOverflow(lower_, value, &may_overflow);
+ upper_ = AddWithoutOverflow(upper_, value, &may_overflow);
Verify();
}
-// Returns whether the add may overflow.
bool Range::AddAndCheckOverflow(Range* other) {
- int old_lower = lower_;
- int old_upper = upper_;
- lower_ = AddWithoutOverflow(lower_, other->lower());
- upper_ = AddWithoutOverflow(upper_, other->upper());
- bool r = (old_lower + other->lower() != lower_ ||
- old_upper + other->upper() != upper_);
+ bool may_overflow = false;
+ lower_ = AddWithoutOverflow(lower_, other->lower(), &may_overflow);
+ upper_ = AddWithoutOverflow(upper_, other->upper(), &may_overflow);
KeepOrder();
Verify();
- return r;
+ return may_overflow;
}
-// Returns whether the sub may overflow.
bool Range::SubAndCheckOverflow(Range* other) {
- int old_lower = lower_;
- int old_upper = upper_;
- lower_ = SubWithoutOverflow(lower_, other->lower());
- upper_ = SubWithoutOverflow(upper_, other->upper());
- bool r = (old_lower - other->lower() != lower_ ||
- old_upper - other->upper() != upper_);
+ bool may_overflow = false;
+ lower_ = SubWithoutOverflow(lower_, other->upper(), &may_overflow);
+ upper_ = SubWithoutOverflow(upper_, other->lower(), &may_overflow);
KeepOrder();
Verify();
- return r;
+ return may_overflow;
}
@@ -193,7 +151,6 @@
}
-// Returns whether the mul may overflow.
bool Range::MulAndCheckOverflow(Range* other) {
bool may_overflow = false;
int v1 = MulWithoutOverflow(lower_, other->lower(), &may_overflow);
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Thu Dec 16 07:40:02
2010
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Thu Dec 16 10:01:36
2010
@@ -333,6 +333,9 @@
}
set_can_be_minus_zero(false);
}
+
+ // Adds a constant to the lower and upper bound of the range.
+ void AddConstant(int32_t value);
void StackUpon(Range* other) {
Intersect(other);
@@ -353,7 +356,8 @@
set_can_be_minus_zero(b);
}
- void Add(int32_t value);
+ // Compute a new result range and return true, if the operation
+ // can overflow.
bool AddAndCheckOverflow(Range* other);
bool SubAndCheckOverflow(Range* other);
bool MulAndCheckOverflow(Range* other);
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Thu Dec 16 06:18:41 2010
+++ /branches/bleeding_edge/src/hydrogen.cc Thu Dec 16 10:01:36 2010
@@ -1029,12 +1029,12 @@
} else if (op == Token::LT || op == Token::LTE) {
new_range = range->CopyClearLower();
if (op == Token::LT) {
- new_range->Add(-1);
+ new_range->AddConstant(-1);
}
} else if (op == Token::GT || op == Token::GTE) {
new_range = range->CopyClearUpper();
if (op == Token::GT) {
- new_range->Add(1);
+ new_range->AddConstant(1);
}
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
