Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(119)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/compiler/machine-operator-reducer.cc

Issue 683793003: [turbofan] fold constants in compares (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: rebase Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/machine-operator-reducer.h ('k') | test/unittests/compiler/machine-operator-reducer-unittest.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/machine-operator-reducer.cc
diff --git a/src/compiler/machine-operator-reducer.cc b/src/compiler/machine-operator-reducer.cc
index a40da1360cfbfb3dc23f5ce05e75b2b1dbd4e4a4..0c574c2342e8244ff4bee85e3e8dfc39cfe199d8 100644
--- a/src/compiler/machine-operator-reducer.cc
+++ b/src/compiler/machine-operator-reducer.cc
@@ -242,36 +242,10 @@ Reduction MachineOperatorReducer::Reduce(Node* node) {
}
break;
}
- case IrOpcode::kWord32Equal: {
- Int32BinopMatcher m(node);
- if (m.IsFoldable()) { // K == K => K
- return ReplaceBool(m.left().Value() == m.right().Value());
- }
- if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y == 0 => x == y
- Int32BinopMatcher msub(m.left().node());
- node->ReplaceInput(0, msub.left().node());
- node->ReplaceInput(1, msub.right().node());
- return Changed(node);
- }
- // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
- if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
- break;
- }
- case IrOpcode::kWord64Equal: {
- Int64BinopMatcher m(node);
- if (m.IsFoldable()) { // K == K => K
- return ReplaceBool(m.left().Value() == m.right().Value());
- }
- if (m.left().IsInt64Sub() && m.right().Is(0)) { // x - y == 0 => x == y
- Int64BinopMatcher msub(m.left().node());
- node->ReplaceInput(0, msub.left().node());
- node->ReplaceInput(1, msub.right().node());
- return Changed(node);
- }
- // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
- if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
- break;
- }
+ case IrOpcode::kWord32Equal:
+ return ReduceWord32Equal(node);
+ case IrOpcode::kWord64Equal:
+ return ReduceWord64Equal(node);
case IrOpcode::kInt32Add: {
Int32BinopMatcher m(node);
if (m.right().Is(0)) return Replace(m.left().node()); // x + 0 => x
@@ -319,80 +293,14 @@ Reduction MachineOperatorReducer::Reduce(Node* node) {
return ReduceInt32Mod(node);
case IrOpcode::kUint32Mod:
return ReduceUint32Mod(node);
- case IrOpcode::kInt32LessThan: {
- Int32BinopMatcher m(node);
- if (m.IsFoldable()) { // K < K => K
- return ReplaceBool(m.left().Value() < m.right().Value());
- }
- if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y < 0 => x < y
- Int32BinopMatcher msub(m.left().node());
- node->ReplaceInput(0, msub.left().node());
- node->ReplaceInput(1, msub.right().node());
- return Changed(node);
- }
- if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 < x - y => y < x
- Int32BinopMatcher msub(m.right().node());
- node->ReplaceInput(0, msub.right().node());
- node->ReplaceInput(1, msub.left().node());
- return Changed(node);
- }
- if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
- break;
- }
- case IrOpcode::kInt32LessThanOrEqual: {
- Int32BinopMatcher m(node);
- if (m.IsFoldable()) { // K <= K => K
- return ReplaceBool(m.left().Value() <= m.right().Value());
- }
- if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y <= 0 => x <= y
- Int32BinopMatcher msub(m.left().node());
- node->ReplaceInput(0, msub.left().node());
- node->ReplaceInput(1, msub.right().node());
- return Changed(node);
- }
- if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 <= x - y => y <= x
- Int32BinopMatcher msub(m.right().node());
- node->ReplaceInput(0, msub.right().node());
- node->ReplaceInput(1, msub.left().node());
- return Changed(node);
- }
- if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
- break;
- }
- case IrOpcode::kUint32LessThan: {
- Uint32BinopMatcher m(node);
- if (m.left().Is(kMaxUInt32)) return ReplaceBool(false); // M < x => false
- if (m.right().Is(0)) return ReplaceBool(false); // x < 0 => false
- if (m.IsFoldable()) { // K < K => K
- return ReplaceBool(m.left().Value() < m.right().Value());
- }
- if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
- if (m.left().IsWord32Sar() && m.right().HasValue()) {
- Int32BinopMatcher mleft(m.left().node());
- if (mleft.right().HasValue()) {
- // (x >> K) < C => x < (C << K) | (2^K - 1)
- // when C < (M >> K)
- const uint32_t c = m.right().Value();
- const uint32_t k = mleft.right().Value() & 0x1f;
- if (c < static_cast<uint32_t>(kMaxInt >> k)) {
- node->ReplaceInput(0, mleft.left().node());
- node->ReplaceInput(1, Uint32Constant((c << k) | ((1 << k) - 1)));
- return Changed(node);
- }
- }
- }
- break;
- }
- case IrOpcode::kUint32LessThanOrEqual: {
- Uint32BinopMatcher m(node);
- if (m.left().Is(0)) return ReplaceBool(true); // 0 <= x => true
- if (m.right().Is(kMaxUInt32)) return ReplaceBool(true); // x <= M => true
- if (m.IsFoldable()) { // K <= K => K
- return ReplaceBool(m.left().Value() <= m.right().Value());
- }
- if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
- break;
- }
+ case IrOpcode::kInt32LessThan:
+ return ReduceInt32LessThan(node);
+ case IrOpcode::kInt32LessThanOrEqual:
+ return ReduceInt32LessThanOrEqual(node);
+ case IrOpcode::kUint32LessThan:
+ return ReduceUint32LessThan(node);
+ case IrOpcode::kUint32LessThanOrEqual:
+ return ReduceUint32LessThanOrEqual(node);
case IrOpcode::kFloat64Add: {
Float64BinopMatcher m(node);
if (m.right().IsNaN()) { // x + NaN => NaN
@@ -538,6 +446,185 @@ Reduction MachineOperatorReducer::Reduce(Node* node) {
}
+static bool MatchBinopConstant(Node** left, int32_t* right) {
+ Int32BinopMatcher m(*left);
+ if (!m.right().HasValue()) return false;
+ *right = m.right().Value();
+ *left = m.left().node();
+ return true;
+}
+
+
+Reduction MachineOperatorReducer::ReduceCompare32(Node* compare) {
+ Int32BinopMatcher m(compare);
+ bool is_left_constant = false;
+ Node* node = NULL;
+ int32_t value = 0;
+ if (m.left().HasValue()) {
+ value = m.left().Value();
+ node = m.right().node();
+ is_left_constant = true;
+ } else if (m.right().HasValue()) {
+ value = m.right().Value();
+ node = m.left().node();
+ is_left_constant = false;
+ } else {
+ // No constant to fold.
+ return NoChange();
+ }
+ bool done;
+ do {
+ done = true;
+ int32_t temp = 0;
+ switch (node->opcode()) {
+ case IrOpcode::kInt32Add:
+ if (MatchBinopConstant(&node, &temp)) {
+ value -= temp;
+ done = false;
+ }
+ break;
+ case IrOpcode::kInt32Sub:
+ if (MatchBinopConstant(&node, &temp)) {
+ value += temp;
+ done = false;
+ }
+ break;
+ default:
+ break;
+ }
+ } while (!done);
+ // No change occured.
+ if (node == m.right().node() || node == m.left().node()) {
+ return NoChange();
+ }
+ int node_input = 0;
+ int const_input = 1;
+ if (is_left_constant) {
+ std::swap(node_input, const_input);
+ }
+ compare->ReplaceInput(node_input, node);
+ compare->ReplaceInput(const_input, Int32Constant(value));
+ return Changed(compare);
+}
+
+
+Reduction MachineOperatorReducer::ReduceWord32Equal(Node* node) {
+ Int32BinopMatcher m(node);
+ if (m.IsFoldable()) { // K == K => K
+ return ReplaceBool(m.left().Value() == m.right().Value());
+ }
+ if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y == 0 => x == y
+ Int32BinopMatcher msub(m.left().node());
+ node->ReplaceInput(0, msub.left().node());
+ node->ReplaceInput(1, msub.right().node());
+ return Changed(node);
+ }
+ // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
+ if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
+ return ReduceCompare32(node);
+}
+
+
+Reduction MachineOperatorReducer::ReduceWord64Equal(Node* node) {
+ Int64BinopMatcher m(node);
+ if (m.IsFoldable()) { // K == K => K
+ return ReplaceBool(m.left().Value() == m.right().Value());
+ }
+ if (m.left().IsInt64Sub() && m.right().Is(0)) { // x - y == 0 => x == y
+ Int64BinopMatcher msub(m.left().node());
+ node->ReplaceInput(0, msub.left().node());
+ node->ReplaceInput(1, msub.right().node());
+ return Changed(node);
+ }
+ // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
+ if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
+ // TODO(turbofan): add ReduceComputableCompare64?
+ return NoChange();
+}
+
+
+Reduction MachineOperatorReducer::ReduceInt32LessThan(Node* node) {
+ Int32BinopMatcher m(node);
+ if (m.IsFoldable()) { // K < K => K
+ return ReplaceBool(m.left().Value() < m.right().Value());
+ }
+ if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y < 0 => x < y
+ Int32BinopMatcher msub(m.left().node());
+ node->ReplaceInput(0, msub.left().node());
+ node->ReplaceInput(1, msub.right().node());
+ return Changed(node);
+ }
+ if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 < x - y => y < x
+ Int32BinopMatcher msub(m.right().node());
+ node->ReplaceInput(0, msub.right().node());
+ node->ReplaceInput(1, msub.left().node());
+ return Changed(node);
+ }
+ if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
+ return ReduceCompare32(node);
+}
+
+
+Reduction MachineOperatorReducer::ReduceInt32LessThanOrEqual(Node* node) {
+ Int32BinopMatcher m(node);
+ if (m.IsFoldable()) { // K <= K => K
+ return ReplaceBool(m.left().Value() <= m.right().Value());
+ }
+ if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y <= 0 => x <= y
+ Int32BinopMatcher msub(m.left().node());
+ node->ReplaceInput(0, msub.left().node());
+ node->ReplaceInput(1, msub.right().node());
+ return Changed(node);
+ }
+ if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 <= x - y => y <= x
+ Int32BinopMatcher msub(m.right().node());
+ node->ReplaceInput(0, msub.right().node());
+ node->ReplaceInput(1, msub.left().node());
+ return Changed(node);
+ }
+ if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
+ return ReduceCompare32(node);
+}
+
+
+Reduction MachineOperatorReducer::ReduceUint32LessThan(Node* node) {
+ Uint32BinopMatcher m(node);
+ if (m.left().Is(kMaxUInt32)) return ReplaceBool(false); // M < x => false
+ if (m.right().Is(0)) return ReplaceBool(false); // x < 0 => false
+ if (m.IsFoldable()) { // K < K => K
+ return ReplaceBool(m.left().Value() < m.right().Value());
+ }
+ if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
+ if (m.left().IsWord32Sar() && m.right().HasValue()) {
+ Int32BinopMatcher mleft(m.left().node());
+ if (mleft.right().HasValue()) {
+ // (x >> K) < C => x < (C << K) | (2^K - 1)
+ // when C < (M >> K)
+ const uint32_t c = m.right().Value();
+ const uint32_t k = mleft.right().Value() & 0x1f;
+ if (c < static_cast<uint32_t>(kMaxInt >> k)) {
+ node->ReplaceInput(0, mleft.left().node());
+ node->ReplaceInput(1, Uint32Constant((c << k) | ((1 << k) - 1)));
+ return Changed(node);
+ }
+ }
+ }
+ return ReduceCompare32(node);
+}
+
+
+Reduction MachineOperatorReducer::ReduceUint32LessThanOrEqual(Node* node) {
+ Uint32BinopMatcher m(node);
+ if (m.left().Is(0)) return ReplaceBool(true); // 0 <= x => true
+ if (m.right().Is(kMaxUInt32)) return ReplaceBool(true); // x <= M => true
+ if (m.IsFoldable()) { // K <= K => K
+ return ReplaceBool(m.left().Value() <= m.right().Value());
+ }
+ if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
+ return ReduceCompare32(node);
+}
+
+
Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) {
Int32BinopMatcher m(node);
if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0
« no previous file with comments | « src/compiler/machine-operator-reducer.h ('k') | test/unittests/compiler/machine-operator-reducer-unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698