From 73737fcdb63eafd4bd430079e437820b9407a7ad Mon Sep 17 00:00:00 2001 From: "fschneider@chromium.org" Date: Thu, 16 Dec 2010 18:01:36 +0000 Subject: [PATCH] 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 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@6055 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-instructions.cc | 101 ++++++++------------------- src/hydrogen-instructions.h | 6 +- src/hydrogen.cc | 4 +- test/mjsunit/compiler/regress-intoverflow.js | 62 ++++++++++++++++ 4 files changed, 98 insertions(+), 75 deletions(-) create mode 100644 test/mjsunit/compiler/regress-intoverflow.js diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index 670dad8..a96ee40 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -64,69 +64,34 @@ const char* Representation::Mnemonic() const { } -static int32_t AddAssertNoOverflow(int32_t a, int32_t b) { - ASSERT(static_cast(a + b) == (static_cast(a) + - static_cast(b))); - return a + b; -} - - -static int32_t SubAssertNoOverflow(int32_t a, int32_t b) { - ASSERT(static_cast(a - b) == (static_cast(a) - - static_cast(b))); - return a - b; -} - - -static int32_t MulAssertNoOverflow(int32_t a, int32_t b) { - ASSERT(static_cast(a * b) == (static_cast(a) * - static_cast(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(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(a) + static_cast(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; +static int32_t SubWithoutOverflow(int32_t a, int32_t b, bool* overflow) { + int64_t result = static_cast(a) - static_cast(b); + return ConvertAndSetOverflow(result, overflow); +} - 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 MulWithoutOverflow(int32_t a, int32_t b, bool* overflow) { + int64_t result = static_cast(a) * static_cast(b); + return ConvertAndSetOverflow(result, overflow); } @@ -143,39 +108,32 @@ int32_t Range::Mask() const { } -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 @@ void Range::Verify() const { } -// Returns whether the mul may overflow. bool Range::MulAndCheckOverflow(Range* other) { bool may_overflow = false; int v1 = MulWithoutOverflow(lower_, other->lower(), &may_overflow); diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index f3452e9..aafa7a8 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -334,6 +334,9 @@ class Range: public ZoneObject { 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); next_ = other; @@ -353,7 +356,8 @@ class Range: public ZoneObject { 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); diff --git a/src/hydrogen.cc b/src/hydrogen.cc index e818545..9ca26a6 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -1029,12 +1029,12 @@ void HRangeAnalysis::InferControlFlowRange(Token::Value op, } 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); } } diff --git a/test/mjsunit/compiler/regress-intoverflow.js b/test/mjsunit/compiler/regress-intoverflow.js new file mode 100644 index 0000000..5f82570 --- /dev/null +++ b/test/mjsunit/compiler/regress-intoverflow.js @@ -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)); -- 2.7.4