[turbofan] fold constants in compares

src/compiler/machine-operator-reducer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/machine-operator-reducer.h"
 
 #include "src/base/bits.h"
 #include "src/base/division-by-constant.h"
 #include "src/codegen.h"
 #include "src/compiler/generic-node-inl.h"
@@ skipping 224 matching lines @@
     }
     case IrOpcode::kWord32Ror: {
       Int32BinopMatcher m(node);
       if (m.right().Is(0)) return Replace(m.left().node());  // x ror 0 => x
       if (m.IsFoldable()) {                                  // K ror K => K
         return ReplaceInt32(
             base::bits::RotateRight32(m.left().Value(), m.right().Value()));
       }
       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
       if (m.IsFoldable()) {                                  // K + K => K
         return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) +
                             static_cast<uint32_t>(m.right().Value()));
       }
       break;
     }
     case IrOpcode::kInt32Sub: {
@@ skipping 27 matching lines @@
       break;
     }
     case IrOpcode::kInt32Div:
       return ReduceInt32Div(node);
     case IrOpcode::kUint32Div:
       return ReduceUint32Div(node);
     case IrOpcode::kInt32Mod:
       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
         return Replace(m.right().node());
       }
       if (m.IsFoldable()) {  // K + K => K
         return ReplaceFloat64(m.left().Value() + m.right().Value());
       }
       break;
     }
@@ skipping 125 matching lines @@
       }
       break;
     }
     default:
       break;
   }
   return NoChange();
 }
 
 
+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
   if (m.right().Is(0)) return Replace(m.right().node());  // x / 0 => 0
   if (m.right().Is(1)) return Replace(m.left().node());   // x / 1 => x
   if (m.IsFoldable()) {                                   // K / K => K
     return ReplaceInt32(
         base::bits::SignedDiv32(m.left().Value(), m.right().Value()));
   }
   if (m.LeftEqualsRight()) {  // x / x => x != 0
@@ skipping 167 matching lines @@
 MachineOperatorBuilder* MachineOperatorReducer::machine() const {
   return jsgraph()->machine();
 }
 
 
 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8