[turbofan] Introduce new Select operator to improve bounds checking.

src/compiler/simplified-lowering.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/simplified-lowering.h"
 
 #include <limits>
 
 #include "src/base/bits.h"
 #include "src/code-factory.h"
@@ skipping 281 matching lines @@
   void VisitInt64Binop(Node* node) { VisitBinop(node, kMachInt64, kMachInt64); }
   void VisitUint64Binop(Node* node) {
     VisitBinop(node, kMachUint64, kMachUint64);
   }
   void VisitFloat64Cmp(Node* node) { VisitBinop(node, kMachFloat64, kRepBit); }
   void VisitInt32Cmp(Node* node) { VisitBinop(node, kMachInt32, kRepBit); }
   void VisitUint32Cmp(Node* node) { VisitBinop(node, kMachUint32, kRepBit); }
   void VisitInt64Cmp(Node* node) { VisitBinop(node, kMachInt64, kRepBit); }
   void VisitUint64Cmp(Node* node) { VisitBinop(node, kMachUint64, kRepBit); }
 
+  // Helper for handling selects.
+  // TODO(turbofan): Share some code with VisitPhi() below?
+  void VisitSelect(Node* node, MachineTypeUnion use,
+                   SimplifiedLowering* lowering) {
+    ProcessInput(node, 0, kRepBit);
+
+    // Selects adapt to the output representation their uses demand, pushing
+    // representation changes to their inputs.
+    Type* upper = NodeProperties::GetBounds(node).upper;
+    MachineType output = kMachNone;
+    MachineType propagate = kMachNone;
+
+    if (upper->Is(Type::Signed32()) || upper->Is(Type::Unsigned32())) {
+      // legal = kRepTagged | kRepFloat64 | kRepWord32;
+      if ((use & kRepMask) == kRepTagged) {
+        // only tagged uses.
+        output = kRepTagged;
+        propagate = kRepTagged;
+      } else if ((use & kRepMask) == kRepFloat64) {
+        // only float64 uses.
+        output = kRepFloat64;
+        propagate = kRepFloat64;
+      } else {
+        // multiple uses.
+        output = kRepWord32;
+        propagate = kRepWord32;
+      }
+    } else if (upper->Is(Type::Boolean())) {
+      // legal = kRepTagged | kRepBit;
+      if ((use & kRepMask) == kRepTagged) {
+        // only tagged uses.
+        output = kRepTagged;
+        propagate = kRepTagged;
+      } else {
+        // multiple uses.
+        output = kRepBit;
+        propagate = kRepBit;
+      }
+    } else if (upper->Is(Type::Number())) {
+      // legal = kRepTagged | kRepFloat64;
+      if ((use & kRepMask) == kRepTagged) {
+        // only tagged uses.
+        output = kRepTagged;
+        propagate = kRepTagged;
+      } else {
+        // multiple uses.
+        output = kRepFloat64;
+        propagate = kRepFloat64;
+      }
+    } else {
+      // legal = kRepTagged;
+      output = kRepTagged;
+      propagate = kRepTagged;
+    }
+
+    MachineType output_type =
+        static_cast<MachineType>(changer_->TypeFromUpperBound(upper) | output);
+    SetOutput(node, output_type);
+
+    if (lower()) {
+      // Update the select operator.
+      SelectParameters p = SelectParametersOf(node->op());
+      MachineType type = static_cast<MachineType>(output_type);
+      if (type != p.type()) {
+        node->set_op(lowering->common()->Select(type, p.hint()));
+      }
+
+      // Convert inputs to the output representation of this select.
+      ProcessInput(node, 1, output_type);
+      ProcessInput(node, 2, output_type);
+    } else {
+      // Propagate {use} of the select to value inputs.
+      MachineType use_type =
+          static_cast<MachineType>((use & kTypeMask) | propagate);
+      ProcessInput(node, 1, use_type);
+      ProcessInput(node, 2, use_type);
+    }
+  }
+
   // Helper for handling phis.
   void VisitPhi(Node* node, MachineTypeUnion use,
                 SimplifiedLowering* lowering) {
     // Phis adapt to the output representation their uses demand, pushing
     // representation changes to their inputs.
     Type* upper = NodeProperties::GetBounds(node).upper;
     MachineType output = kMachNone;
     MachineType propagate = kMachNone;
 
     if (upper->Is(Type::Signed32()) || upper->Is(Type::Unsigned32())) {
@@ skipping 162 matching lines @@
       case IrOpcode::kIfFalse:
       case IrOpcode::kReturn:
       case IrOpcode::kMerge:
       case IrOpcode::kThrow:
         return VisitInputs(node);  // default visit for all node inputs.
 
       case IrOpcode::kBranch:
         ProcessInput(node, 0, kRepBit);
         Enqueue(NodeProperties::GetControlInput(node, 0));
         break;
+      case IrOpcode::kSelect:
+        return VisitSelect(node, use, lowering);
       case IrOpcode::kPhi:
         return VisitPhi(node, use, lowering);
 
 //------------------------------------------------------------------
 // JavaScript operators.
 //------------------------------------------------------------------
 // For now, we assume that all JS operators were too complex to lower
 // to Simplified and that they will always require tagged value inputs
 // and produce tagged value outputs.
 // TODO(turbofan): it might be possible to lower some JSOperators here,
@@ skipping 556 matching lines @@
   WriteBarrierKind kind = ComputeWriteBarrierKind(
       access.base_is_tagged, access.machine_type, access.type);
   node->set_op(
       machine()->Store(StoreRepresentation(access.machine_type, kind)));
   Node* offset = jsgraph()->Int32Constant(access.offset - access.tag());
   node->InsertInput(zone(), 1, offset);
 }
 
 
 Node* SimplifiedLowering::ComputeIndex(const ElementAccess& access,
-                                       Node* index) {
-  int element_size = ElementSizeOf(access.machine_type);
+                                       Node* const key) {
+  Node* index = key;
+  const int element_size = ElementSizeOf(access.machine_type);
   if (element_size != 1) {
-    index = graph()->NewNode(machine()->Int32Mul(),
-                             jsgraph()->Int32Constant(element_size), index);
+    index = graph()->NewNode(machine()->Int32Mul(), index,
+                             jsgraph()->Int32Constant(element_size));
   }
-  int fixed_offset = access.header_size - access.tag();
-  if (fixed_offset == 0) return index;
-  return graph()->NewNode(machine()->Int32Add(), index,
-                          jsgraph()->Int32Constant(fixed_offset));
+  const int fixed_offset = access.header_size - access.tag();
+  if (fixed_offset != 0) {
+    index = graph()->NewNode(machine()->Int32Add(), index,
+                             jsgraph()->Int32Constant(fixed_offset));
+  }
+  // TODO(bmeurer): 64-Bit
+  // if (machine()->Is64()) {
+  //   index = graph()->NewNode(machine()->ChangeInt32ToInt64(), index);
+  // }
+  return index;
 }
 
 
+namespace {
+
+intptr_t AddressForOutOfBoundsLoad(MachineType type) {
+  switch (RepresentationOf(type)) {
+    case kRepFloat32: {
+      static const float dummy = std::numeric_limits<float>::quiet_NaN();
+      return bit_cast<intptr_t>(&dummy);
+    }
+    case kRepFloat64: {
+      static const double dummy = std::numeric_limits<double>::quiet_NaN();
+      return bit_cast<intptr_t>(&dummy);
+    }
+    case kRepBit:
+    case kRepWord8:
+    case kRepWord16:
+    case kRepWord32: {
+      static const int32_t dummy = 0;
+      return bit_cast<intptr_t>(&dummy);
+    }
+    default:
+      break;
+  }
+  UNREACHABLE();
+  return 0;
+}
+
+
+intptr_t AddressForOutOfBoundsStore() {
+  static volatile double dummy = 0;
+  return bit_cast<intptr_t>(&dummy);
+}
+
+}  // namespace
+
+
 void SimplifiedLowering::DoLoadElement(Node* node, MachineType output_type) {
   const ElementAccess& access = ElementAccessOf(node->op());
   const Operator* op = machine()->Load(access.machine_type);
   Node* key = node->InputAt(1);
+  Node* index = ComputeIndex(access, key);
   Node* effect = node->InputAt(3);
-  Node* index = ComputeIndex(access, key);
   if (access.bounds_check == kNoBoundsCheck) {
     DCHECK_EQ(access.machine_type, output_type);
     node->set_op(op);
     node->ReplaceInput(1, index);
     node->ReplaceInput(2, effect);
     node->ReplaceInput(3, graph()->start());
   } else {
     DCHECK_EQ(kTypedArrayBoundsCheck, access.bounds_check);
 
     Node* base = node->InputAt(0);
     Node* length = node->InputAt(2);
+    Node* check = graph()->NewNode(machine()->Uint32LessThan(), key, length);
 
-    Node* check = graph()->NewNode(machine()->Uint32LessThan(), key, length);
-    Node* branch = graph()->NewNode(common()->Branch(BranchHint::kTrue), check,
-                                    graph()->start());
+    IntPtrMatcher mbase(base);
+    if (mbase.HasValue() && (output_type & kRepTagged) == 0) {
+      Node* select = graph()->NewNode(
+          common()->Select(kMachIntPtr, BranchHint::kTrue), check, index,
+          jsgraph()->IntPtrConstant(AddressForOutOfBoundsLoad(output_type) -
+                                    mbase.Value()));
 
-    Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
-    Node* load = graph()->NewNode(op, base, index, effect, if_true);
-    Node* result = load;
-    if (output_type & kRepTagged) {
-      // TODO(turbofan): This is ugly as hell!
-      SimplifiedOperatorBuilder simplified(graph()->zone());
-      RepresentationChanger changer(jsgraph(), &simplified,
-                                    graph()->zone()->isolate());
-      result = changer.GetTaggedRepresentationFor(result, access.machine_type);
+      node->set_op(op);
+      node->ReplaceInput(1, select);
+      node->ReplaceInput(2, effect);
+      node->ReplaceInput(3, graph()->start());
+    } else {
+      Node* branch = graph()->NewNode(common()->Branch(BranchHint::kTrue),
+                                      check, graph()->start());
+
+      Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
+      Node* load = graph()->NewNode(op, base, index, effect, if_true);
+      Node* result = load;
+      if (output_type & kRepTagged) {
+        // TODO(turbofan): This is ugly as hell!
+        SimplifiedOperatorBuilder simplified(graph()->zone());
+        RepresentationChanger changer(jsgraph(), &simplified,
+                                      graph()->zone()->isolate());
+        result =
+            changer.GetTaggedRepresentationFor(result, access.machine_type);
+      }
+
+      Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
+      Node* undefined;
+      if (output_type & kRepTagged) {
+        DCHECK_EQ(0, access.machine_type & kRepTagged);
+        undefined = jsgraph()->UndefinedConstant();
+      } else if (output_type & kRepFloat32) {
+        undefined =
+            jsgraph()->Float32Constant(std::numeric_limits<float>::quiet_NaN());
+      } else if (output_type & kRepFloat64) {
+        undefined = jsgraph()->Float64Constant(
+            std::numeric_limits<double>::quiet_NaN());
+      } else {
+        undefined = jsgraph()->Int32Constant(0);
+      }
+
+      Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
+      Node* phi = graph()->NewNode(common()->EffectPhi(2), load, effect, merge);
+
+      // Replace effect uses of node with the effect phi.
+      for (UseIter i = node->uses().begin(); i != node->uses().end();) {
+        if (NodeProperties::IsEffectEdge(i.edge())) {
+          i = i.UpdateToAndIncrement(phi);
+        } else {
+          ++i;
+        }
+      }
+
+      node->set_op(common()->Phi(output_type, 2));
+      node->ReplaceInput(0, result);
+      node->ReplaceInput(1, undefined);
+      node->ReplaceInput(2, merge);
+      node->TrimInputCount(3);
     }
-
-    Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
-    Node* undefined;
-    if (output_type & kRepTagged) {
-      DCHECK(!(access.machine_type & kRepTagged));
-      undefined = jsgraph()->UndefinedConstant();
-    } else if (output_type & kRepFloat32) {
-      undefined =
-          jsgraph()->Float32Constant(std::numeric_limits<float>::quiet_NaN());
-    } else if (output_type & kRepFloat64) {
-      undefined =
-          jsgraph()->Float64Constant(std::numeric_limits<double>::quiet_NaN());
-    } else {
-      undefined = jsgraph()->Int32Constant(0);
-    }
-
-    Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
-    Node* phi = graph()->NewNode(common()->EffectPhi(2), load, effect, merge);
-
-    // Replace effect uses of node with the effect phi.
-    for (UseIter i = node->uses().begin(); i != node->uses().end();) {
-      if (NodeProperties::IsEffectEdge(i.edge())) {
-        i = i.UpdateToAndIncrement(phi);
-      } else {
-        ++i;
-      }
-    }
-
-    node->set_op(common()->Phi(output_type, 2));
-    node->ReplaceInput(0, result);
-    node->ReplaceInput(1, undefined);
-    node->ReplaceInput(2, merge);
-    node->TrimInputCount(3);
   }
 }
 
 
 void SimplifiedLowering::DoStoreElement(Node* node) {
   const ElementAccess& access = ElementAccessOf(node->op());
   const Operator* op = machine()->Store(StoreRepresentation(
       access.machine_type,
       ComputeWriteBarrierKind(access.base_is_tagged, access.machine_type,
                               access.type)));
   Node* key = node->InputAt(1);
   Node* index = ComputeIndex(access, key);
   if (access.bounds_check == kNoBoundsCheck) {
     node->set_op(op);
     node->ReplaceInput(1, index);
     node->RemoveInput(2);
   } else {
     DCHECK_EQ(kTypedArrayBoundsCheck, access.bounds_check);
 
     Node* base = node->InputAt(0);
     Node* length = node->InputAt(2);
     Node* value = node->InputAt(3);
     Node* effect = node->InputAt(4);
     Node* control = node->InputAt(5);
+    Node* check = graph()->NewNode(machine()->Uint32LessThan(), key, length);
 
-    Node* check = graph()->NewNode(machine()->Uint32LessThan(), key, length);
-    Node* branch =
-        graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control);
+    IntPtrMatcher mbase(base);
+    if (mbase.HasValue()) {
+      Node* select = graph()->NewNode(
+          common()->Select(kMachIntPtr, BranchHint::kTrue), check, index,
+          jsgraph()->IntPtrConstant(AddressForOutOfBoundsStore() -
+                                    mbase.Value()));
 
-    Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
-    Node* store = graph()->NewNode(op, base, index, value, effect, if_true);
+      node->set_op(op);
+      node->ReplaceInput(1, select);
+      node->RemoveInput(2);
+    } else {
+      Node* branch =
+          graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control);
 
-    Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
+      Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
+      Node* store = graph()->NewNode(op, base, index, value, effect, if_true);
 
-    Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
+      Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
 
-    node->set_op(common()->EffectPhi(2));
-    node->ReplaceInput(0, store);
-    node->ReplaceInput(1, effect);
-    node->ReplaceInput(2, merge);
-    node->TrimInputCount(3);
+      Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
+
+      node->set_op(common()->EffectPhi(2));
+      node->ReplaceInput(0, store);
+      node->ReplaceInput(1, effect);
+      node->ReplaceInput(2, merge);
+      node->TrimInputCount(3);
+    }
   }
 }
 
 
 void SimplifiedLowering::DoStringAdd(Node* node) {
   Callable callable = CodeFactory::StringAdd(
       zone()->isolate(), STRING_ADD_CHECK_NONE, NOT_TENURED);
   CallDescriptor::Flags flags = CallDescriptor::kNoFlags;
   CallDescriptor* desc =
       Linkage::GetStubCallDescriptor(callable.descriptor(), 0, flags, zone());
@@ skipping 179 matching lines @@
   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
 }
 
 
 void SimplifiedLowering::DoStringLessThanOrEqual(Node* node) {
   node->set_op(machine()->IntLessThanOrEqual());
   node->ReplaceInput(0, StringComparison(node, true));
   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
 }
 
-
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8