Hydrogen code stubs for vector-based ICs.

src/code-stubs-hydrogen.cc

 // Copyright 2012 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/v8.h"
 
 #include "src/bailout-reason.h"
 #include "src/code-stubs.h"
 #include "src/field-index.h"
 #include "src/hydrogen.h"
+#include "src/ic/ic.h"
 #include "src/lithium.h"
 
 namespace v8 {
 namespace internal {
 
 
 static LChunk* OptimizeGraph(HGraph* graph) {
   DisallowHeapAllocation no_allocation;
   DisallowHandleAllocation no_handles;
   DisallowHandleDereference no_deref;
@@ skipping 71 matching lines @@
                                          HValue* map_index);
   void BuildInstallCode(HValue* js_function, HValue* shared_info);
 
   HInstruction* LoadFromOptimizedCodeMap(HValue* optimized_map,
                                          HValue* iterator,
                                          int field_offset);
   void BuildInstallFromOptimizedCodeMap(HValue* js_function,
                                         HValue* shared_info,
                                         HValue* native_context);
 
+  // Tail calls handler found at array[index].
+  void TailCallHandler(HValue* receiver, HValue* name, HValue* array,
+                       HValue* index, HValue* slot, HValue* vector);
+
+  // Tail calls handler_code.
+  void TailCallHandler(HValue* receiver, HValue* name, HValue* slot,
+                       HValue* vector, HValue* handler_code);
+
+  void TailCallMiss(HValue* receiver, HValue* name, HValue* slot,
+                    HValue* vector, bool keyed_load);
+
+  // Handle MONOMORPHIC and POLYMORPHIC LoadIC and KeyedLoadIC cases.
+  void HandleArrayCases(HValue* array, HValue* receiver, HValue* name,
+                        HValue* slot, HValue* vector, bool keyed_load);
+
  private:
   HValue* BuildArraySingleArgumentConstructor(JSArrayBuilder* builder);
   HValue* BuildArrayNArgumentsConstructor(JSArrayBuilder* builder,
                                           ElementsKind kind);
 
   SmartArrayPointer<HParameter*> parameters_;
   HValue* arguments_length_;
   CompilationInfoWithZone info_;
   CodeStubDescriptor descriptor_;
   HContext* context_;
@@ skipping 1884 matching lines @@
 
   return Pop();
 }
 
 
 Handle<Code> KeyedLoadGenericStub::GenerateCode() {
   return DoGenerateCode(this);
 }
 
 
+void CodeStubGraphBuilderBase::TailCallHandler(HValue* receiver, HValue* name,
+                                               HValue* array, HValue* index,
+                                               HValue* slot, HValue* vector) {
+  HValue* handler_code =
+      Add<HLoadKeyed>(array, index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
+  TailCallHandler(receiver, name, slot, vector, handler_code);
+}
+
+
+void CodeStubGraphBuilderBase::TailCallHandler(HValue* receiver, HValue* name,
+                                               HValue* slot, HValue* vector,
+                                               HValue* handler_code) {
+  VectorLoadICDescriptor descriptor(isolate());
+  HValue* op_vals[] = {context(), receiver, name, slot, vector};
+  // We never return here, it is a tail call.

[Jakob Kummerow, 2014/12/02 08:43:06]

nit: I'd move this comment after the Add<...>.

If you feel you need to teach Hydrogen about the notion described in this
comment (e.g. because live ranges are an issue), the best approach is probably
modeled after HDeoptimize: end the block after the tail call instruction, emit a
goto to a new block, and update the HMarkUnreachableBlocksPhase to mark that
block as unreachable.

[mvstanton, 2014/12/03 11:48:30]

Thanks, sounds like a good idea. I tried approximating it by just adding Deopts
after these tail calls, but it didn't reduce spill slots or their usage. I'll
tackle this in a follow-on CL.

+  Add<HCallWithDescriptor>(handler_code, 0, descriptor,
+                           Vector<HValue*>(op_vals, 5), TAIL_CALL);
+}
+
+
+void CodeStubGraphBuilderBase::TailCallMiss(HValue* receiver, HValue* name,
+                                            HValue* slot, HValue* vector,
+                                            bool keyed_load) {
+  DCHECK(FLAG_vector_ics);
+  // We never return here, it is a tail call.

[Jakob Kummerow, 2014/12/02 08:43:06]

same here

[mvstanton, 2014/12/03 11:48:30]

Done.

+  Add<HTailCallThroughMegamorphicCache>(
+      receiver, name, slot, vector,
+      HTailCallThroughMegamorphicCache::ComputeFlags(keyed_load, true));
+}
+
+
+void CodeStubGraphBuilderBase::HandleArrayCases(HValue* array, HValue* receiver,
+                                                HValue* name, HValue* slot,
+                                                HValue* vector,
+                                                bool keyed_load) {
+  HValue* length = AddLoadFixedArrayLength(array, static_cast<HValue*>(NULL));
+  HValue* receiver_map = AddLoadMap(receiver, static_cast<HValue*>(NULL));
+  IfBuilder mono_checker(this);

[Jakob Kummerow, 2014/12/02 08:43:06]

Naming suggestion: if you name this guy "if_monomorphic", you'll get the very
natural "if_monomorphic.Then();" below. If you agree, consider similar namings
for other IfBuilders below.

[mvstanton, 2014/12/03 11:48:30]

Done.

+  HValue* mono_length =
+      Add<HConstant>(static_cast<int32_t>(keyed_load ? 3 : 2));
+  mono_checker.If<HCompareNumericAndBranch>(length, mono_length, Token::EQ);
+  mono_checker.Then();
+  {
+    // Compare map.
+    HValue* start =
+        keyed_load ? graph()->GetConstant1() : graph()->GetConstant0();
+    HValue* array_map = Add<HLoadKeyed>(
+        array, start, static_cast<HValue*>(NULL), FAST_ELEMENTS);
+    IfBuilder correct_map_checker(this);
+    correct_map_checker.If<HCompareObjectEqAndBranch>(receiver_map, array_map);
+    correct_map_checker.Then();
+    {
+      HValue* handler_index = keyed_load
+                                  ? Add<HConstant>(static_cast<int32_t>(2))

[Jakob Kummerow, 2014/12/02 08:43:06]

nit: Drop the static_cast, it's cleaner.

[mvstanton, 2014/12/03 11:48:29]

Done.

[mvstanton, 2014/12/03 11:48:30]

Done. I reformulated this code a bit too, noticing that I don't need to check
the array length in the monomorphic case, but only if we didn't find the map in
the first tuple of the array.

+                                  : graph()->GetConstant1();
+      TailCallHandler(receiver, name, array, handler_index, slot, vector);
+    }
+    correct_map_checker.Else();
+    { TailCallMiss(receiver, name, slot, vector, keyed_load); }
+    correct_map_checker.End();
+  }
+  mono_checker.Else();
+  {
+    // It is polymorphic.
+    HValue* increment_amount = Add<HConstant>(2);
+    LoopBuilder builder(this, context(), LoopBuilder::kPostIncrement,
+                        increment_amount);
+    HValue* start =
+        keyed_load ? graph()->GetConstant1() : graph()->GetConstant0();
+    HValue* key = builder.BeginBody(start, length, Token::LT);
+    {
+      HValue* array_map = Add<HLoadKeyed>(
+          array, key, static_cast<HValue*>(NULL), FAST_ELEMENTS);
+      IfBuilder correct_map_checker(this);
+      correct_map_checker.If<HCompareObjectEqAndBranch>(receiver_map,
+                                                        array_map);
+      correct_map_checker.Then();
+      {
+        HValue* one = graph()->GetConstant1();
+        HValue* index = AddUncasted<HAdd>(key, one);
+        TailCallHandler(receiver, name, array, index, slot, vector);
+      }
+    }
+    builder.EndBody();
+
+    TailCallMiss(receiver, name, slot, vector, keyed_load);
+  }
+  mono_checker.End();
+}
+
+
 template <>
 HValue* CodeStubGraphBuilder<VectorLoadStub>::BuildCodeStub() {
   HValue* receiver = GetParameter(VectorLoadICDescriptor::kReceiverIndex);
-  Add<HDeoptimize>("Always deopt", Deoptimizer::EAGER);
-  return receiver;
+  HValue* name = GetParameter(VectorLoadICDescriptor::kNameIndex);
+  HValue* slot = GetParameter(VectorLoadICDescriptor::kSlotIndex);
+  HValue* vector = GetParameter(VectorLoadICDescriptor::kVectorIndex);
+
+  // Are we monomorphic?

[Jakob Kummerow, 2014/12/02 08:43:06]

nit: s/Are we foo/Is the IC in foo state/, and please mention polymorphic as
well.

[mvstanton, 2014/12/03 11:48:30]

Done.

+  HValue* feedback =
+      Add<HLoadKeyed>(vector, slot, static_cast<HValue*>(NULL), FAST_ELEMENTS);
+  IfBuilder array_checker(this);
+  array_checker.If<HCompareMap>(feedback,

[Jakob Kummerow, 2014/12/02 08:43:06]

This map check bakes in the assumption that the feedback type sentinel is never
a Smi. Is that OK/intentional?

[mvstanton, 2014/12/03 11:48:30]

Yes indeed, that is why we have a pile of symbols to distinguish different
states. This convention was introduced for the CallIC last summer to improve
performance.

+                                isolate()->factory()->fixed_array_map());
+  array_checker.Then();
+  {
+    Add<HCheckHeapObject>(receiver);

[Jakob Kummerow, 2014/12/02 08:43:06]

Ugh. Hydrogen's ugly warts. HCheckHeapObject should be an iDef, and the
subsequent map load should have an explicit dependency on it. But that's not
this CL's business, and I guess by sheer luck the code just so happens to be
safe as it is...

[mvstanton, 2014/12/03 11:48:30]

Oh yeah, creepy. Okay, I've turned the HCheckHeapObject into a
HCheckSmiAndBranch, handling the MISS in the else case.

[Jakob Kummerow, 2014/12/03 13:22:17]

That's fine, but I didn't mean to imply you should do this. Using
HCheckHeapObject is fine. I was just ranting. Sorry if that confused you :-)

+    HandleArrayCases(feedback, receiver, name, slot, vector, false);
+  }
+  array_checker.Else();
+  {
+    // Are we megamorphic?
+    IfBuilder mega_checker(this);
+    HConstant* megamorphic_symbol =
+        Add<HConstant>(isolate()->factory()->megamorphic_symbol());
+    mega_checker.If<HCompareObjectEqAndBranch>(feedback, megamorphic_symbol);
+    mega_checker.Then();
+    {
+      // Probe the stub cache.
+      Add<HTailCallThroughMegamorphicCache>(
+          receiver, name, slot, vector,
+          HTailCallThroughMegamorphicCache::ComputeFlags(false, false));
+    }
+    mega_checker.End();
+
+    TailCallMiss(receiver, name, slot, vector, false);
+  }
+  array_checker.End();
+
+  // We never get here.
+  return graph()->GetConstant0();
 }
 
 
 Handle<Code> VectorLoadStub::GenerateCode() { return DoGenerateCode(this); }
 
 
 template <>
 HValue* CodeStubGraphBuilder<VectorKeyedLoadStub>::BuildCodeStub() {
   HValue* receiver = GetParameter(VectorLoadICDescriptor::kReceiverIndex);
-  Add<HDeoptimize>("Always deopt", Deoptimizer::EAGER);
-  return receiver;
+  HValue* name = GetParameter(VectorLoadICDescriptor::kNameIndex);
+  HValue* slot = GetParameter(VectorLoadICDescriptor::kSlotIndex);
+  HValue* vector = GetParameter(VectorLoadICDescriptor::kVectorIndex);
+  HConstant* zero = graph()->GetConstant0();
+
+  // Are we monomorphic?
+  HValue* feedback =
+      Add<HLoadKeyed>(vector, slot, static_cast<HValue*>(NULL), FAST_ELEMENTS);
+  IfBuilder array_checker(this);
+  array_checker.If<HCompareMap>(feedback,
+                                isolate()->factory()->fixed_array_map());
+  array_checker.Then();
+  {
+    // Deal with the key. If feedback[0] is 0, then we are dealing with element
+    // handlers. Otherwise, it's a string, verify that name matches.
+    HValue* recorded_name = Add<HLoadKeyed>(
+        feedback, zero, static_cast<HValue*>(NULL), FAST_ELEMENTS);
+
+    IfBuilder recorded_name_is_zero(this);
+    recorded_name_is_zero.If<HCompareNumericAndBranch>(recorded_name, zero,
+                                                       Token::EQ);
+    recorded_name_is_zero.Then();
+    {
+      // TODO(mvstanton): is this necessary? Anyway, I should call the
+      // miss handler directly and not let the bailout mechanism run.
+      Add<HCheckSmi>(name);
+    }
+    recorded_name_is_zero.Else();
+    {
+      IfBuilder strings_match(this);
+      strings_match.IfNot<HCompareObjectEqAndBranch>(name, recorded_name);
+      strings_match.Then();
+      TailCallMiss(receiver, name, slot, vector, true);
+      strings_match.End();
+    }
+    recorded_name_is_zero.End();
+
+    Add<HCheckHeapObject>(receiver);
+    HandleArrayCases(feedback, receiver, name, slot, vector, true);
+  }
+  array_checker.Else();
+  {
+    // Are we megamorphic?
+    IfBuilder mega_checker(this);
+    HConstant* megamorphic_symbol =
+        Add<HConstant>(isolate()->factory()->megamorphic_symbol());
+    mega_checker.If<HCompareObjectEqAndBranch>(feedback, megamorphic_symbol);
+    mega_checker.Then();
+    {
+      // HTailCallThroughMegamorphicCache expects name to be a string.
+      // TODO(mvstanton): I don't understand why I need this check. How does it
+      // work without --vector-ics on? Because there isn't a check on the name
+      // in that case right?

[Jakob Kummerow, 2014/12/02 08:43:06]

KeyedLoadIC currently doesn't support megamorphic state. For Smi keys, it can be
monomorphic, polymorphic, or generic. For non-Smi keys, it can be monomorphic or
generic. Yes, it's a mess. Future behavior TBD.

[mvstanton, 2014/12/03 11:48:30]

Wow...the overloaded megamorphic_stub() method in ic.h led me into this error -
I ended up providing megamorphic support for keyed loads :p. But I want simple
and basic correctness, so I'm withdrawing that support for now. If it comes in
handy I can bring it back in a follow-on CL.

[Jakob Kummerow, 2014/12/03 13:22:17]

Acknowledged.

+      Add<HCheckHeapObject>(name);
+      // Probe the stub cache.
+      Add<HTailCallThroughMegamorphicCache>(
+          receiver, name, slot, vector,
+          HTailCallThroughMegamorphicCache::ComputeFlags(true, false));
+    }
+    mega_checker.End();
+
+    // Are we generic?
+    IfBuilder generic_checker(this);
+    HConstant* generic_symbol =
+        Add<HConstant>(isolate()->factory()->generic_symbol());
+    generic_checker.If<HCompareObjectEqAndBranch>(feedback, generic_symbol);
+    generic_checker.Then();
+    {
+      // Tail-call to the generic KeyedLoadIC, treating it like a handler.
+      Handle<Code> stub = KeyedLoadIC::generic_stub(isolate());
+      HValue* constant_stub = Add<HConstant>(stub);
+      LoadDescriptor descriptor(isolate());
+      HValue* op_vals[] = {context(), receiver, name};
+      // We never return here, it is a tail call.
+      Add<HCallWithDescriptor>(constant_stub, 0, descriptor,
+                               Vector<HValue*>(op_vals, 3), TAIL_CALL);
+    }
+    generic_checker.End();
+
+    TailCallMiss(receiver, name, slot, vector, true);
+  }
+  array_checker.End();
+
+  // We never get here.
+  return zero;
 }
 
 
 Handle<Code> VectorKeyedLoadStub::GenerateCode() {
   return DoGenerateCode(this);
 }
 
 
 Handle<Code> MegamorphicLoadStub::GenerateCode() {
   return DoGenerateCode(this);
 }
 
 
 template <>
 HValue* CodeStubGraphBuilder<MegamorphicLoadStub>::BuildCodeStub() {
-  // The return address is on the stack.
   HValue* receiver = GetParameter(LoadDescriptor::kReceiverIndex);
   HValue* name = GetParameter(LoadDescriptor::kNameIndex);
 
+  // We shouldn't generate this when FLAG_vector_ics is true because the
+  // megamorphic case is handled as part of the default stub.
+  DCHECK(!FLAG_vector_ics);
+
   // Probe the stub cache.
-  Code::Flags flags = Code::RemoveTypeAndHolderFromFlags(
-      Code::ComputeHandlerFlags(Code::LOAD_IC));
-  Add<HTailCallThroughMegamorphicCache>(receiver, name, flags);
+  Add<HTailCallThroughMegamorphicCache>(receiver, name);
 
   // We never continue.
   return graph()->GetConstant0();
 }
 } }  // namespace v8::internal