[turbofan] Constant-fold certain JSOrdinaryHasInstance nodes.

src/compiler/js-native-context-specialization.cc

 // Copyright 2015 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/js-native-context-specialization.h"
 
 #include "src/accessors.h"
 #include "src/code-factory.h"
 #include "src/compilation-dependencies.h"
 #include "src/compiler/access-builder.h"
@@ skipping 248 matching lines @@
   }
 
   return NoChange();
 }
 
 Reduction JSNativeContextSpecialization::ReduceJSOrdinaryHasInstance(
     Node* node) {
   DCHECK_EQ(IrOpcode::kJSOrdinaryHasInstance, node->opcode());
   Node* constructor = NodeProperties::GetValueInput(node, 0);
   Node* object = NodeProperties::GetValueInput(node, 1);
+  Node* context = NodeProperties::GetContextInput(node);
+  Node* frame_state = NodeProperties::GetFrameStateInput(node);
+  Node* effect = NodeProperties::GetEffectInput(node);
+  Node* control = NodeProperties::GetControlInput(node);
+
+  // Check if the {constructor} is known at compile time.
+  HeapObjectMatcher m(constructor);
+  if (!m.HasValue()) return NoChange();
 
   // Check if the {constructor} is a JSBoundFunction.
-  HeapObjectMatcher m(constructor);
-  if (m.HasValue() && m.Value()->IsJSBoundFunction()) {
+  if (m.Value()->IsJSBoundFunction()) {
     // OrdinaryHasInstance on bound functions turns into a recursive
     // invocation of the instanceof operator again.
     // ES6 section 7.3.19 OrdinaryHasInstance (C, O) step 2.
     Handle<JSBoundFunction> function = Handle<JSBoundFunction>::cast(m.Value());
     Handle<JSReceiver> bound_target_function(function->bound_target_function());
     NodeProperties::ReplaceValueInput(node, object, 0);
     NodeProperties::ReplaceValueInput(
         node, jsgraph()->HeapConstant(bound_target_function), 1);
     NodeProperties::ChangeOp(node, javascript()->InstanceOf());
     Reduction const reduction = ReduceJSInstanceOf(node);
     return reduction.Changed() ? reduction : Changed(node);
   }
 
+  // Check if the {constructor} is a JSFunction.
+  if (m.Value()->IsJSFunction()) {
+    // Check if the {function} is a constructor and has an instance "prototype".
+    Handle<JSFunction> function = Handle<JSFunction>::cast(m.Value());
+    if (function->IsConstructor() && function->has_instance_prototype() &&
+        function->prototype()->IsJSReceiver()) {
+      // Ensure that the {function} has a valid initial map, so we can
+      // depend on that for the prototype constant-folding below.
+      JSFunction::EnsureHasInitialMap(function);
+
+      // Install a code dependency on the {function}s initial map.
+      Handle<Map> initial_map(function->initial_map(), isolate());
+      dependencies()->AssumeInitialMapCantChange(initial_map);
+      Handle<JSReceiver> function_prototype =
+          handle(JSReceiver::cast(initial_map->prototype()), isolate());
+
+      // Check if we can constant-fold the prototype chain walk
+      // for the given {object} and the {function_prototype}.
+      InferHasInPrototypeChainResult result =
+          InferHasInPrototypeChain(object, effect, function_prototype);
+      if (result != kMayBeInPrototypeChain) {
+        Node* value = jsgraph()->BooleanConstant(result == kIsInPrototypeChain);
+        ReplaceWithValue(node, value, effect, control);
+        return Replace(value);
+      }
+
+      Node* prototype = jsgraph()->Constant(function_prototype);
+
+      Node* check0 = graph()->NewNode(simplified()->ObjectIsSmi(), object);
+      Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kFalse),
+                                       check0, control);
+
+      Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
+      Node* etrue0 = effect;
+      Node* vtrue0 = jsgraph()->FalseConstant();
+
+      control = graph()->NewNode(common()->IfFalse(), branch0);
+
+      // Loop through the {object}s prototype chain looking for the {prototype}.
+      Node* loop = control =
+          graph()->NewNode(common()->Loop(2), control, control);
+      Node* eloop = effect =
+          graph()->NewNode(common()->EffectPhi(2), effect, effect, loop);
+      Node* vloop = object =
+          graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                           object, object, loop);
+
+      // Load the {object} map and instance type.
+      Node* object_map = effect =
+          graph()->NewNode(simplified()->LoadField(AccessBuilder::ForMap()),
+                           object, effect, control);
+      Node* object_instance_type = effect = graph()->NewNode(
+          simplified()->LoadField(AccessBuilder::ForMapInstanceType()),
+          object_map, effect, control);
+
+      // Check if the {object} is a special receiver, because for special
+      // receivers, i.e. proxies or API objects that need access checks,
+      // we have to use the %HasInPrototypeChain runtime function instead.
+      Node* check1 = graph()->NewNode(
+          simplified()->NumberLessThanOrEqual(), object_instance_type,
+          jsgraph()->Constant(LAST_SPECIAL_RECEIVER_TYPE));
+      Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kFalse),
+                                       check1, control);
+
+      control = graph()->NewNode(common()->IfFalse(), branch1);
+
+      Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
+      Node* etrue1 = effect;
+      Node* vtrue1;
+
+      // Check if the {object} is not a receiver at all.
+      Node* check10 =
+          graph()->NewNode(simplified()->NumberLessThan(), object_instance_type,
+                           jsgraph()->Constant(FIRST_JS_RECEIVER_TYPE));
+      Node* branch10 = graph()->NewNode(common()->Branch(BranchHint::kTrue),
+                                        check10, if_true1);
+
+      // A primitive value cannot match the {prototype} we're looking for.
+      if_true1 = graph()->NewNode(common()->IfTrue(), branch10);
+      vtrue1 = jsgraph()->FalseConstant();
+
+      Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch10);
+      Node* efalse1 = etrue1;
+      Node* vfalse1;
+      {
+        // Slow path, need to call the %HasInPrototypeChain runtime function.
+        vfalse1 = efalse1 = if_false1 = graph()->NewNode(
+            javascript()->CallRuntime(Runtime::kHasInPrototypeChain), object,
+            prototype, context, frame_state, efalse1, if_false1);
+
+        // Replace any potential {IfException} uses of {node} to catch
+        // exceptions from this %HasInPrototypeChain runtime call instead.
+        Node* on_exception = nullptr;
+        if (NodeProperties::IsExceptionalCall(node, &on_exception)) {
+          NodeProperties::ReplaceControlInput(on_exception, vfalse1);
+          NodeProperties::ReplaceEffectInput(on_exception, efalse1);
+          if_false1 = graph()->NewNode(common()->IfSuccess(), vfalse1);
+          Revisit(on_exception);
+        }
+      }
+
+      // Load the {object} prototype.
+      Node* object_prototype = effect = graph()->NewNode(
+          simplified()->LoadField(AccessBuilder::ForMapPrototype()), object_map,
+          effect, control);
+
+      // Check if we reached the end of {object}s prototype chain.
+      Node* check2 =
+          graph()->NewNode(simplified()->ReferenceEqual(), object_prototype,
+                           jsgraph()->NullConstant());
+      Node* branch2 = graph()->NewNode(common()->Branch(), check2, control);
+
+      Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
+      Node* etrue2 = effect;
+      Node* vtrue2 = jsgraph()->FalseConstant();
+
+      control = graph()->NewNode(common()->IfFalse(), branch2);
+
+      // Check if we reached the {prototype}.
+      Node* check3 = graph()->NewNode(simplified()->ReferenceEqual(),
+                                      object_prototype, prototype);
+      Node* branch3 = graph()->NewNode(common()->Branch(), check3, control);
+
+      Node* if_true3 = graph()->NewNode(common()->IfTrue(), branch3);
+      Node* etrue3 = effect;
+      Node* vtrue3 = jsgraph()->TrueConstant();
+
+      control = graph()->NewNode(common()->IfFalse(), branch3);
+
+      // Close the loop.
+      vloop->ReplaceInput(1, object_prototype);
+      eloop->ReplaceInput(1, effect);
+      loop->ReplaceInput(1, control);
+
+      control = graph()->NewNode(common()->Merge(5), if_true0, if_true1,
+                                 if_true2, if_true3, if_false1);
+      effect = graph()->NewNode(common()->EffectPhi(5), etrue0, etrue1, etrue2,
+                                etrue3, efalse1, control);
+
+      // Morph the {node} into an appropriate Phi.
+      ReplaceWithValue(node, node, effect, control);
+      node->ReplaceInput(0, vtrue0);
+      node->ReplaceInput(1, vtrue1);
+      node->ReplaceInput(2, vtrue2);
+      node->ReplaceInput(3, vtrue3);
+      node->ReplaceInput(4, vfalse1);
+      node->ReplaceInput(5, control);
+      node->TrimInputCount(6);
+      NodeProperties::ChangeOp(
+          node, common()->Phi(MachineRepresentation::kTagged, 5));
+      return Changed(node);
+    }
+  }
+
   return NoChange();
 }
 
 Reduction JSNativeContextSpecialization::ReduceJSLoadContext(Node* node) {
   DCHECK_EQ(IrOpcode::kJSLoadContext, node->opcode());
   ContextAccess const& access = ContextAccessOf(node->op());
   // Specialize JSLoadContext(NATIVE_CONTEXT_INDEX) to the known native
   // context (if any), so we can constant-fold those fields, which is
   // safe, since the NATIVE_CONTEXT_INDEX slot is always immutable.
   if (access.index() == Context::NATIVE_CONTEXT_INDEX) {
@@ skipping 1933 matching lines @@
   // Install code dependencies on the prototype maps.
   for (Handle<Map> map : receiver_maps) {
     dependencies()->AssumePrototypeMapsStable(map, initial_object_prototype);
   }
 
   // Install code dependency on the array protector cell.
   dependencies()->AssumePropertyCell(factory()->array_protector());
   return true;
 }
 
+JSNativeContextSpecialization::InferHasInPrototypeChainResult
+JSNativeContextSpecialization::InferHasInPrototypeChain(
+    Node* receiver, Node* effect, Handle<JSReceiver> prototype) {
+  ZoneHandleSet<Map> receiver_maps;
+  NodeProperties::InferReceiverMapsResult result =
+      NodeProperties::InferReceiverMaps(receiver, effect, &receiver_maps);
+  if (result == NodeProperties::kNoReceiverMaps) return kMayBeInPrototypeChain;
+
+  // Check if either all or none of the {receiver_maps} have the given
+  // {prototype} in their prototype chain.
+  bool all = true;
+  bool none = true;
+  for (size_t i = 0; i < receiver_maps.size(); ++i) {
+    Handle<Map> receiver_map = receiver_maps[i];
+    if (receiver_map->instance_type() <= LAST_SPECIAL_RECEIVER_TYPE) {
+      return kMayBeInPrototypeChain;
+    }
+    if (result == NodeProperties::kUnreliableReceiverMaps) {
+      // In case of an unreliable {result} we need to ensure that all
+      // {receiver_maps} are stable, because otherwise we cannot trust
+      // the {receiver_maps} information, since arbitrary side-effects
+      // may have happened.
+      if (!receiver_map->is_stable()) {
+        return kMayBeInPrototypeChain;
+      }
+    }
+    for (PrototypeIterator j(receiver_map);; j.Advance()) {
+      if (j.IsAtEnd()) {
+        all = false;
+        break;
+      }
+      Handle<JSReceiver> const current =
+          PrototypeIterator::GetCurrent<JSReceiver>(j);
+      if (current.is_identical_to(prototype)) {
+        none = false;
+        break;
+      }
+      if (!current->map()->is_stable() ||
+          current->map()->instance_type() <= LAST_SPECIAL_RECEIVER_TYPE) {
+        return kMayBeInPrototypeChain;
+      }
+    }
+  }
+  DCHECK_IMPLIES(all, !none);
+  DCHECK_IMPLIES(none, !all);
+
+  if (all) return kIsInPrototypeChain;
+  if (none) return kIsNotInPrototypeChain;
+  return kMayBeInPrototypeChain;
+}
+
 bool JSNativeContextSpecialization::ExtractReceiverMaps(
     Node* receiver, Node* effect, FeedbackNexus const& nexus,
     MapHandleList* receiver_maps) {
   DCHECK_EQ(0, receiver_maps->length());
   // See if we can infer a concrete type for the {receiver}.
   if (InferReceiverMaps(receiver, effect, receiver_maps)) {
     // We can assume that the {receiver} still has the infered {receiver_maps}.
     return true;
   }
   // Try to extract some maps from the {nexus}.
@@ skipping 101 matching lines @@
   return jsgraph()->javascript();
 }
 
 SimplifiedOperatorBuilder* JSNativeContextSpecialization::simplified() const {
   return jsgraph()->simplified();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8