Revision: 23809
Author: [email protected]
Date: Tue Sep 9 14:18:17 2014 UTC
Log: [turbofan] Add support for overflow add/sub to the
MachineOperatorReducer.
TEST=base-unittests,compiler-unittests,cctest
[email protected]
Review URL: https://codereview.chromium.org/555833002
https://code.google.com/p/v8/source/detail?r=23809
Modified:
/branches/bleeding_edge/include/v8config.h
/branches/bleeding_edge/src/base/bits-unittest.cc
/branches/bleeding_edge/src/base/bits.h
/branches/bleeding_edge/src/compiler/machine-operator-reducer-unittest.cc
/branches/bleeding_edge/src/compiler/machine-operator-reducer.cc
/branches/bleeding_edge/src/compiler/machine-operator-reducer.h
/branches/bleeding_edge/test/cctest/compiler/test-run-machops.cc
=======================================
--- /branches/bleeding_edge/include/v8config.h Tue Sep 2 07:07:52 2014 UTC
+++ /branches/bleeding_edge/include/v8config.h Tue Sep 9 14:18:17 2014 UTC
@@ -179,6 +179,8 @@
// V8_HAS_BUILTIN_CTZ - __builtin_ctz() supported
// V8_HAS_BUILTIN_EXPECT - __builtin_expect() supported
// V8_HAS_BUILTIN_POPCOUNT - __builtin_popcount() supported
+// V8_HAS_BUILTIN_SADD_OVERFLOW - __builtin_sadd_overflow()
supported
+// V8_HAS_BUILTIN_SSUB_OVERFLOW - __builtin_ssub_overflow()
supported
// V8_HAS_DECLSPEC_ALIGN - __declspec(align(n)) supported
// V8_HAS_DECLSPEC_DEPRECATED - __declspec(deprecated) supported
// V8_HAS_DECLSPEC_NOINLINE - __declspec(noinline) supported
@@ -213,6 +215,8 @@
# define V8_HAS_BUILTIN_CTZ (__has_builtin(__builtin_ctz))
# define V8_HAS_BUILTIN_EXPECT (__has_builtin(__builtin_expect))
# define V8_HAS_BUILTIN_POPCOUNT (__has_builtin(__builtin_popcount))
+# define V8_HAS_BUILTIN_SADD_OVERFLOW
(__has_builtin(__builtin_sadd_overflow))
+# define V8_HAS_BUILTIN_SSUB_OVERFLOW
(__has_builtin(__builtin_ssub_overflow))
# define V8_HAS_CXX11_ALIGNAS (__has_feature(cxx_alignas))
# define V8_HAS_CXX11_STATIC_ASSERT (__has_feature(cxx_static_assert))
=======================================
--- /branches/bleeding_edge/src/base/bits-unittest.cc Tue Sep 2 15:22:36
2014 UTC
+++ /branches/bleeding_edge/src/base/bits-unittest.cc Tue Sep 9 14:18:17
2014 UTC
@@ -2,6 +2,8 @@
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
+#include <limits>
+
#include "src/base/bits.h"
#include "src/base/macros.h"
#include "testing/gtest-support.h"
@@ -118,6 +120,47 @@
EXPECT_EQ(1u, RotateRight64(2, 1));
EXPECT_EQ(V8_UINT64_C(0x8000000000000000), RotateRight64(1, 1));
}
+
+
+TEST(Bits, SignedAddOverflow32) {
+ int32_t val = 0;
+ EXPECT_FALSE(SignedAddOverflow32(0, 0, &val));
+ EXPECT_EQ(0, val);
+ EXPECT_TRUE(
+ SignedAddOverflow32(std::numeric_limits<int32_t>::max(), 1, &val));
+ EXPECT_EQ(std::numeric_limits<int32_t>::min(), val);
+ EXPECT_TRUE(
+ SignedAddOverflow32(std::numeric_limits<int32_t>::min(), -1, &val));
+ EXPECT_EQ(std::numeric_limits<int32_t>::max(), val);
+ EXPECT_TRUE(SignedAddOverflow32(std::numeric_limits<int32_t>::max(),
+ std::numeric_limits<int32_t>::max(),
&val));
+ EXPECT_EQ(-2, val);
+ TRACED_FORRANGE(int32_t, i, 1, 50) {
+ TRACED_FORRANGE(int32_t, j, 1, i) {
+ EXPECT_FALSE(SignedAddOverflow32(i, j, &val));
+ EXPECT_EQ(i + j, val);
+ }
+ }
+}
+
+
+TEST(Bits, SignedSubOverflow32) {
+ int32_t val = 0;
+ EXPECT_FALSE(SignedSubOverflow32(0, 0, &val));
+ EXPECT_EQ(0, val);
+ EXPECT_TRUE(
+ SignedSubOverflow32(std::numeric_limits<int32_t>::min(), 1, &val));
+ EXPECT_EQ(std::numeric_limits<int32_t>::max(), val);
+ EXPECT_TRUE(
+ SignedSubOverflow32(std::numeric_limits<int32_t>::max(), -1, &val));
+ EXPECT_EQ(std::numeric_limits<int32_t>::min(), val);
+ TRACED_FORRANGE(int32_t, i, 1, 50) {
+ TRACED_FORRANGE(int32_t, j, 1, i) {
+ EXPECT_FALSE(SignedSubOverflow32(i, j, &val));
+ EXPECT_EQ(i - j, val);
+ }
+ }
+}
} // namespace bits
} // namespace base
=======================================
--- /branches/bleeding_edge/src/base/bits.h Tue Sep 2 13:36:35 2014 UTC
+++ /branches/bleeding_edge/src/base/bits.h Tue Sep 9 14:18:17 2014 UTC
@@ -6,6 +6,7 @@
#define V8_BASE_BITS_H_
#include "include/v8stdint.h"
+#include "src/base/macros.h"
#if V8_CC_MSVC
#include <intrin.h>
#endif
@@ -113,6 +114,34 @@
if (shift == 0) return value;
return (value >> shift) | (value << (64 - shift));
}
+
+
+// SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs|
and
+// |rhs| and stores the result into the variable pointed to by |val| and
+// returns true if the signed summation resulted in an overflow.
+inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
+#if V8_HAS_BUILTIN_SADD_OVERFLOW
+ return __builtin_sadd_overflow(lhs, rhs, val);
+#else
+ uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
+ *val = bit_cast<int32_t>(res);
+ return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
+#endif
+}
+
+
+// SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs|
and
+// |rhs| and stores the result into the variable pointed to by |val| and
+// returns true if the signed subtraction resulted in an overflow.
+inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
+#if V8_HAS_BUILTIN_SSUB_OVERFLOW
+ return __builtin_ssub_overflow(lhs, rhs, val);
+#else
+ uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
+ *val = bit_cast<int32_t>(res);
+ return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
+#endif
+}
} // namespace bits
} // namespace base
=======================================
---
/branches/bleeding_edge/src/compiler/machine-operator-reducer-unittest.cc
Tue Sep 9 13:20:09 2014 UTC
+++
/branches/bleeding_edge/src/compiler/machine-operator-reducer-unittest.cc
Tue Sep 9 14:18:17 2014 UTC
@@ -442,6 +442,98 @@
}
}
}
+
+
+//
-----------------------------------------------------------------------------
+// Int32AddWithOverflow
+
+
+TEST_F(MachineOperatorReducerTest, Int32AddWithOverflowWithZero) {
+ Node* p0 = Parameter(0);
+ {
+ Node* add = graph()->NewNode(machine()->Int32AddWithOverflow(),
+ Int32Constant(0), p0);
+
+ Reduction r = Reduce(graph()->NewNode(common()->Projection(1), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(), IsInt32Constant(0));
+
+ r = Reduce(graph()->NewNode(common()->Projection(0), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_EQ(p0, r.replacement());
+ }
+ {
+ Node* add = graph()->NewNode(machine()->Int32AddWithOverflow(), p0,
+ Int32Constant(0));
+
+ Reduction r = Reduce(graph()->NewNode(common()->Projection(1), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(), IsInt32Constant(0));
+
+ r = Reduce(graph()->NewNode(common()->Projection(0), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_EQ(p0, r.replacement());
+ }
+}
+
+
+TEST_F(MachineOperatorReducerTest, Int32AddWithOverflowWithConstant) {
+ TRACED_FOREACH(int32_t, x, kInt32Values) {
+ TRACED_FOREACH(int32_t, y, kInt32Values) {
+ int32_t z;
+ Node* add = graph()->NewNode(machine()->Int32AddWithOverflow(),
+ Int32Constant(x), Int32Constant(y));
+
+ Reduction r = Reduce(graph()->NewNode(common()->Projection(1), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(),
+ IsInt32Constant(base::bits::SignedAddOverflow32(x, y,
&z)));
+
+ r = Reduce(graph()->NewNode(common()->Projection(0), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(), IsInt32Constant(z));
+ }
+ }
+}
+
+
+//
-----------------------------------------------------------------------------
+// Int32SubWithOverflow
+
+
+TEST_F(MachineOperatorReducerTest, Int32SubWithOverflowWithZero) {
+ Node* p0 = Parameter(0);
+ Node* add =
+ graph()->NewNode(machine()->Int32SubWithOverflow(), p0,
Int32Constant(0));
+
+ Reduction r = Reduce(graph()->NewNode(common()->Projection(1), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(), IsInt32Constant(0));
+
+ r = Reduce(graph()->NewNode(common()->Projection(0), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_EQ(p0, r.replacement());
+}
+
+
+TEST_F(MachineOperatorReducerTest, Int32SubWithOverflowWithConstant) {
+ TRACED_FOREACH(int32_t, x, kInt32Values) {
+ TRACED_FOREACH(int32_t, y, kInt32Values) {
+ int32_t z;
+ Node* add = graph()->NewNode(machine()->Int32SubWithOverflow(),
+ Int32Constant(x), Int32Constant(y));
+
+ Reduction r = Reduce(graph()->NewNode(common()->Projection(1), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(),
+ IsInt32Constant(base::bits::SignedSubOverflow32(x, y,
&z)));
+
+ r = Reduce(graph()->NewNode(common()->Projection(0), add));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(), IsInt32Constant(z));
+ }
+ }
+}
} // namespace compiler
} // namespace internal
=======================================
--- /branches/bleeding_edge/src/compiler/machine-operator-reducer.cc Thu
Sep 4 10:55:58 2014 UTC
+++ /branches/bleeding_edge/src/compiler/machine-operator-reducer.cc Tue
Sep 9 14:18:17 2014 UTC
@@ -39,6 +39,8 @@
// Perform constant folding and strength reduction on machine operators.
Reduction MachineOperatorReducer::Reduce(Node* node) {
switch (node->opcode()) {
+ case IrOpcode::kProjection:
+ return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0));
case IrOpcode::kWord32And: {
Int32BinopMatcher m(node);
if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 =>
0
@@ -431,6 +433,43 @@
}
return NoChange();
}
+
+
+Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node*
node) {
+ switch (node->opcode()) {
+ case IrOpcode::kInt32AddWithOverflow: {
+ DCHECK(index == 0 || index == 1);
+ Int32BinopMatcher m(node);
+ if (m.IsFoldable()) {
+ int32_t val;
+ bool ovf = base::bits::SignedAddOverflow32(m.left().Value(),
+ m.right().Value(),
&val);
+ return ReplaceInt32((index == 0) ? val : ovf);
+ }
+ if (m.right().Is(0)) {
+ return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0);
+ }
+ break;
+ }
+ case IrOpcode::kInt32SubWithOverflow: {
+ DCHECK(index == 0 || index == 1);
+ Int32BinopMatcher m(node);
+ if (m.IsFoldable()) {
+ int32_t val;
+ bool ovf = base::bits::SignedSubOverflow32(m.left().Value(),
+ m.right().Value(),
&val);
+ return ReplaceInt32((index == 0) ? val : ovf);
+ }
+ if (m.right().Is(0)) {
+ return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0);
+ }
+ break;
+ }
+ default:
+ break;
+ }
+ return NoChange();
+}
CommonOperatorBuilder* MachineOperatorReducer::common() const {
=======================================
--- /branches/bleeding_edge/src/compiler/machine-operator-reducer.h Tue
Sep 2 07:07:52 2014 UTC
+++ /branches/bleeding_edge/src/compiler/machine-operator-reducer.h Tue
Sep 9 14:18:17 2014 UTC
@@ -41,6 +41,8 @@
Reduction ReplaceInt64(int64_t value) {
return Replace(Int64Constant(value));
}
+
+ Reduction ReduceProjection(size_t index, Node* node);
Graph* graph() const;
JSGraph* jsgraph() const { return jsgraph_; }
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-run-machops.cc Fri
Sep 5 11:44:31 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-run-machops.cc Tue
Sep 9 14:18:17 2014 UTC
@@ -4016,22 +4016,6 @@
#endif // MACHINE_ASSEMBLER_SUPPORTS_CALL_C
-static bool sadd_overflow(int32_t x, int32_t y, int32_t* val) {
- int32_t v =
- static_cast<int32_t>(static_cast<uint32_t>(x) +
static_cast<uint32_t>(y));
- *val = v;
- return (((v ^ x) & (v ^ y)) >> 31) & 1;
-}
-
-
-static bool ssub_overflow(int32_t x, int32_t y, int32_t* val) {
- int32_t v =
- static_cast<int32_t>(static_cast<uint32_t>(x) -
static_cast<uint32_t>(y));
- *val = v;
- return (((v ^ x) & (v ^ ~y)) >> 31) & 1;
-}
-
-
TEST(RunInt32AddWithOverflowP) {
int32_t actual_val = -1;
RawMachineAssemblerTester<int32_t> m;
@@ -4044,7 +4028,7 @@
FOR_INT32_INPUTS(i) {
FOR_INT32_INPUTS(j) {
int32_t expected_val;
- int expected_ovf = sadd_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedAddOverflow32(*i, *j, &expected_val);
CHECK_EQ(expected_ovf, bt.call(*i, *j));
CHECK_EQ(expected_val, actual_val);
}
@@ -4063,7 +4047,7 @@
m.StoreToPointer(&actual_val, kMachInt32, val);
m.Return(ovf);
FOR_INT32_INPUTS(j) {
- int expected_ovf = sadd_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedAddOverflow32(*i, *j,
&expected_val);
CHECK_EQ(expected_ovf, m.Call(*j));
CHECK_EQ(expected_val, actual_val);
}
@@ -4076,7 +4060,7 @@
m.StoreToPointer(&actual_val, kMachInt32, val);
m.Return(ovf);
FOR_INT32_INPUTS(j) {
- int expected_ovf = sadd_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedAddOverflow32(*i, *j,
&expected_val);
CHECK_EQ(expected_ovf, m.Call(*j));
CHECK_EQ(expected_val, actual_val);
}
@@ -4089,7 +4073,7 @@
Node* ovf = m.Projection(1, add);
m.StoreToPointer(&actual_val, kMachInt32, val);
m.Return(ovf);
- int expected_ovf = sadd_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedAddOverflow32(*i, *j, &expected_val);
CHECK_EQ(expected_ovf, m.Call());
CHECK_EQ(expected_val, actual_val);
}
@@ -4113,7 +4097,7 @@
FOR_INT32_INPUTS(i) {
FOR_INT32_INPUTS(j) {
int32_t expected;
- if (sadd_overflow(*i, *j, &expected)) expected = constant;
+ if (bits::SignedAddOverflow32(*i, *j, &expected)) expected =
constant;
CHECK_EQ(expected, bt.call(*i, *j));
}
}
@@ -4132,7 +4116,7 @@
FOR_INT32_INPUTS(i) {
FOR_INT32_INPUTS(j) {
int32_t expected_val;
- int expected_ovf = ssub_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedSubOverflow32(*i, *j, &expected_val);
CHECK_EQ(expected_ovf, bt.call(*i, *j));
CHECK_EQ(expected_val, actual_val);
}
@@ -4151,7 +4135,7 @@
m.StoreToPointer(&actual_val, kMachInt32, val);
m.Return(ovf);
FOR_INT32_INPUTS(j) {
- int expected_ovf = ssub_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedSubOverflow32(*i, *j,
&expected_val);
CHECK_EQ(expected_ovf, m.Call(*j));
CHECK_EQ(expected_val, actual_val);
}
@@ -4164,7 +4148,7 @@
m.StoreToPointer(&actual_val, kMachInt32, val);
m.Return(ovf);
FOR_INT32_INPUTS(j) {
- int expected_ovf = ssub_overflow(*j, *i, &expected_val);
+ int expected_ovf = bits::SignedSubOverflow32(*j, *i,
&expected_val);
CHECK_EQ(expected_ovf, m.Call(*j));
CHECK_EQ(expected_val, actual_val);
}
@@ -4177,7 +4161,7 @@
Node* ovf = m.Projection(1, add);
m.StoreToPointer(&actual_val, kMachInt32, val);
m.Return(ovf);
- int expected_ovf = ssub_overflow(*i, *j, &expected_val);
+ int expected_ovf = bits::SignedSubOverflow32(*i, *j, &expected_val);
CHECK_EQ(expected_ovf, m.Call());
CHECK_EQ(expected_val, actual_val);
}
@@ -4201,7 +4185,7 @@
FOR_INT32_INPUTS(i) {
FOR_INT32_INPUTS(j) {
int32_t expected;
- if (ssub_overflow(*i, *j, &expected)) expected = constant;
+ if (bits::SignedSubOverflow32(*i, *j, &expected)) expected =
constant;
CHECK_EQ(expected, bt.call(*i, *j));
}
}
--
--
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.
