Reland 21774: Generate KeyedLoadGeneric with Hydrogen

src/hydrogen.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1210 matching lines @@
 
 HBasicBlock* HGraphBuilder::CreateLoopHeaderBlock() {
   HBasicBlock* header = graph()->CreateBasicBlock();
   HEnvironment* entry_env = environment()->CopyAsLoopHeader(header);
   header->SetInitialEnvironment(entry_env);
   header->AttachLoopInformation();
   return header;
 }
 
 
+HValue* HGraphBuilder::BuildGetElementsKind(HValue* object) {
+  HValue* map = Add<HLoadNamedField>(object, HObjectAccess::ForMap());
+
+  HValue* bit_field2 = Add<HLoadNamedField>(map,
+                                            HObjectAccess::ForMapBitField2());
+  HValue* unmasked_kind = AddUncasted<HShr>(
+      bit_field2, Add<HConstant>(Map::kElementsKindShift));

[Toon Verwaest, 2013/12/04 17:29:26]

It seems like ElementsKind should really be a BitField of bitfield2. And then
perhaps we should have a function to read a BitField from an HValue; rather than
manually shifting and masking.

[danno, 2014/06/06 15:43:51]

Done.

+  int mask = (1 << Map::kElementsKindBitCount) - 1;
+  HValue* mask_value = Add<HConstant>(mask);
+  return AddUncasted<HBitwise>(Token::BIT_AND, unmasked_kind, mask_value);
+}
+
+
 HValue* HGraphBuilder::BuildCheckHeapObject(HValue* obj) {
   if (obj->type().IsHeapObject()) return obj;
   return Add<HCheckHeapObject>(obj);
 }
 
 
 void HGraphBuilder::FinishExitWithHardDeoptimization(
     const char* reason, HBasicBlock* continuation) {
   PadEnvironmentForContinuation(current_block(), continuation);
   Add<HDeoptimize>(reason, Deoptimizer::EAGER);
@@ skipping 169 matching lines @@
     BuildGrowElementsCapacity(object, elements, from_kind, to_kind,
                               array_length, elements_length);
 
     if_builder.End();
   }
 
   Add<HStoreNamedField>(object, HObjectAccess::ForMap(), map);
 }
 
 
+void HGraphBuilder::BuildReceiverCheck(HValue* receiver,
+                                       int bit_field_mask) {
+  // Check that the object isn't a smi.
+  Add<HCheckHeapObject>(receiver);
+
+  // Get the map of the receiver.
+  HValue* map = Add<HLoadNamedField>(receiver, HObjectAccess::ForMap());
+
+  if (V8_TARGET_LITTLE_ENDIAN) {
+    // Check the instance type and if an access check is needed, this can be
+    // done with a single load, since both bytes are adjacent in the map.
+    HObjectAccess access(HObjectAccess::ForMapInstanceTypeAndBitField());
+    HValue* instance_type_and_bit_field = Add<HLoadNamedField>(map, access);
+
+    HValue* mask = Add<HConstant>(0x00FF | (bit_field_mask << 8));
+    HValue* and_result = AddUncasted<HBitwise>(Token::BIT_AND,
+                                               instance_type_and_bit_field,
+                                               mask);
+    HValue* sub_result = AddUncasted<HSub>(and_result,
+                                           Add<HConstant>(JS_OBJECT_TYPE));
+    Add<HBoundsCheck>(sub_result, Add<HConstant>(0x100 - JS_OBJECT_TYPE));
+  } else {
+    HValue* instance_type =
+        Add<HLoadNamedField>(map, HObjectAccess::ForMapInstanceType());
+    IfBuilder type_check(this);
+    type_check.If<HCompareNumericAndBranch>(instance_type,
+                                            Add<HConstant>(JS_OBJECT_TYPE),
+                                            Token::LT);
+    type_check.ThenDeopt("receiver check: not JS_OBJECT_TYPE");
+    type_check.End();
+
+    HValue* bit_field2 =
+        Add<HLoadNamedField>(map, HObjectAccess::ForMapBitField());

[Toon Verwaest, 2013/12/04 17:29:26]

ForMapBitField2 I presume? Is this tested?
Seems to me like we should apply the same optimization here as above by swapping
the order of the bitfields. That would at least unify the code.

[danno, 2014/06/06 15:43:51]

Fields swapped, it makes this code much simpler.

+    HValue* and_result = AddUncasted<HBitwise>(
+        Token::BIT_AND,
+        bit_field2,
+        Add<HConstant>(bit_field_mask));
+    IfBuilder access_check(this);
+    access_check.If<HCompareNumericAndBranch>(and_result,

[Toon Verwaest, 2013/12/04 17:29:26]

Use DeoptimizeIf.

[danno, 2014/06/06 15:43:51]

Done.

+                                              graph()->GetConstant0(),
+                                              Token::NE);
+    access_check.ThenDeopt("receiver check: bit field check failed");
+    access_check.End();
+  }
+}
+
+
+HValue* HGraphBuilder::BuildHashToIndex(HValue *hash) {
+  // The assert checks that the constants for the maximum number of digits
+  // for an array index cached in the hash field and the number of bits
+  // reserved for it does not conflict.
+  ASSERT(TenToThe(String::kMaxCachedArrayIndexLength) <
+         (1 << String::kArrayIndexValueBits));
+  HValue* index = AddUncasted<HBitwise>(
+      Token::BIT_AND, hash, Add<HConstant>(String::kArrayIndexValueMask));
+  return AddUncasted<HShr>(index, Add<HConstant>(String::kHashShift));

[Toon Verwaest, 2013/12/04 17:29:26]

A bitfield decoding mechanism would be useful again.

[danno, 2014/06/06 15:43:51]

Done.

+}
+
+
+void HGraphBuilder::BuildKeyedIndexCheck(HValue* key,
+                                         HIfContinuation* join_continuation) {

[Toon Verwaest, 2013/12/04 17:29:26]

It took me a while to figure out why the branches below are ordered the way they
are. Please add a comment here indicating that join_continuation is basically
the continuation for if-true->smi, if-false->something-else; and that all
branches below need to match up to be able to join this continuation.
(Hence my confused comments below.)

[danno, 2014/06/06 15:43:51]

Done.

+  // Create a joinable continuation.
+  IfBuilder key_smi_if(this);
+  key_smi_if.If<HIsSmiAndBranch>(key);
+  key_smi_if.Then();
+  {
+    Push(key);  // Nothing to do, just continue to true of continuation.
+  }
+  key_smi_if.Else();
+  {
+    HValue* map = Add<HLoadNamedField>(key, HObjectAccess::ForMap());
+    HValue* instance_type =
+        Add<HLoadNamedField>(map, HObjectAccess::ForMapInstanceType());
+
+    // Non-unique string, check for a string with a hash code that is actually
+    // an index.
+    STATIC_ASSERT(LAST_UNIQUE_NAME_TYPE == FIRST_NONSTRING_TYPE);
+    IfBuilder not_string_or_name_if(this);

[Toon Verwaest, 2013/12/04 17:29:26]

I'd swap the condition (use string_or_name rather than not_string_or_name). The
double negation in the else branch is a bit confusing.

[danno, 2014/06/06 15:43:51]

Ordering needs to stay the same due to continuation join.

+    not_string_or_name_if.If<HCompareNumericAndBranch>(
+        instance_type,
+        Add<HConstant>(LAST_UNIQUE_NAME_TYPE),
+        Token::GT);
+
+    not_string_or_name_if.Then();
+    {
+      // Non-smi, non-Name, non-String: Try to convert to smi in case of
+      // HeapNumber.
+      Push(AddUncasted<HForceRepresentation>(key, Representation::Smi()));
+    }
+    not_string_or_name_if.Else();
+    {
+      // String or Name: check explicitly for Name, they can short-circuit
+      // directly to unique non-index key path.
+      IfBuilder name_if(this);
+      name_if.If<HCompareNumericAndBranch>(

[Toon Verwaest, 2013/12/04 17:29:26]

And here name_if means that it's not a name. That's also pretty confusing.

[danno, 2014/06/06 15:43:51]

Ordering needs to stay the same due to continuation join.

+          instance_type,
+          Add<HConstant>(LAST_UNIQUE_NAME_TYPE),
+          Token::NE);
+
+      name_if.Then();
+      {
+        // String: check whether the String is an String of an index. If it is,
+        // extract the index value from the hash.
+        HValue* hash =
+            Add<HLoadNamedField>(key, HObjectAccess::ForNameHashField());
+        HValue* cached_array_bit = AddUncasted<HBitwise>(
+            Token::BIT_AND,
+            hash,
+            Add<HConstant>(Name::kContainsCachedArrayIndexMask));

[Toon Verwaest, 2013/12/04 17:29:26]

Shouldn't kContainsCachedArrayIndex be on String rather than Name? Names can't
have cached array indices it seems to me.

[danno, 2014/06/06 15:43:51]

Done.

+
+        IfBuilder string_index_if(this);
+        string_index_if.If<HCompareNumericAndBranch>(cached_array_bit,
+                                                     graph()->GetConstant0(),
+                                                     Token::EQ);
+        string_index_if.Then();
+        {
+          // String with index in hash: extract string and merge to index path.
+          Push(BuildHashToIndex(hash));

[Toon Verwaest, 2013/12/04 17:29:26]

BuildHashToIndex could just be a bitfield decoder.

[danno, 2014/06/06 15:43:51]

Done.

+        }
+        string_index_if.Else();
+        {
+          // Key is a non-index String, check for uniqueness/internalization. If
+          // it's not, deopt.
+          HValue* not_internalized_bit = AddUncasted<HBitwise>(
+              Token::BIT_AND,
+              instance_type,
+              Add<HConstant>(static_cast<int>(kIsNotInternalizedMask)));
+          DeoptimizeIf<HCompareNumericAndBranch>(
+              not_internalized_bit,
+              graph()->GetConstant0(),
+              Token::NE,
+              "BuildKeyedIndexCheck: string isn't internalized");
+          // Key guaranteed to be a unqiue string
+          Push(key);
+        }
+        string_index_if.JoinContinuation(join_continuation);
+      }
+      name_if.Else();
+      {
+        Push(key);  // Key is name
+      }
+      name_if.JoinContinuation(join_continuation);
+    }
+    not_string_or_name_if.JoinContinuation(join_continuation);
+  }
+  key_smi_if.JoinContinuation(join_continuation);
+}
+
+
+void HGraphBuilder:: BuildGlobalInstanceTypeCheck(HValue* receiver) {
+  // Get the the instance type of the receiver, and make sure that it is
+  // not one of the global object types.

[Toon Verwaest, 2013/12/04 17:29:26]

This comment seems to say the opposite of the name of the method and the actual
body. The code (and name) guarantees that the receiver *is* a global object, not
that it isn't.

[danno, 2014/06/06 15:43:51]

Done.

+  HValue* map = Add<HLoadNamedField>(receiver, HObjectAccess::ForMap());
+  HValue* instance_type =
+      Add<HLoadNamedField>(map, HObjectAccess::ForMapInstanceType());
+  STATIC_ASSERT(JS_BUILTINS_OBJECT_TYPE == JS_GLOBAL_OBJECT_TYPE + 1);
+  STATIC_ASSERT(JS_GLOBAL_PROXY_TYPE == JS_BUILTINS_OBJECT_TYPE + 1);
+  HValue* smallest_global_type = Add<HConstant>(JS_GLOBAL_OBJECT_TYPE);
+  instance_type = AddUncasted<HSub>(instance_type, smallest_global_type);
+  int globla_type_count = JS_GLOBAL_PROXY_TYPE - JS_GLOBAL_OBJECT_TYPE;

[Toon Verwaest, 2013/12/04 17:29:26]

globAL

[danno, 2014/06/06 15:43:51]

Done.

+  Add<HBoundsCheck>(instance_type, Add<HConstant>(globla_type_count));
+}
+
+
+void HGraphBuilder::BuildCheckForDictionaryProperties(
+    HValue* object,
+    HIfContinuation* continuation) {
+  HValue* properties = Add<HLoadNamedField>(
+      object, HObjectAccess::ForPropertiesPointer());
+  HValue* properties_map = Add<HLoadNamedField>(
+      properties, HObjectAccess::ForMap());
+  HValue* hash_map = Add<HLoadRoot>(Heap::kHashTableMapRootIndex);
+  IfBuilder builder(this);
+  builder.If<HCompareObjectEqAndBranch>(properties_map, hash_map);
+  builder.CaptureContinuation(continuation);

[Toon Verwaest, 2013/12/04 17:29:26]

I wonder if the resulting code may be smaller / faster if you'd read out the
"is_dictionary_map" from the Map. That would avoid loading the HashTableMap.

[danno, 2014/06/06 15:43:51]

This is a copy of what the hand-written stub did IIRC. May I wait to try
optimizations in a separate CL?

+}
+
+
+HValue* HGraphBuilder::BuildKeyedLookupCacheHash(HValue* object,
+                                                 HValue* key) {
+  // Load the map of the receiver, compute the keyed lookup cache hash
+  // based on 32 bits of the map pointer and the string hash.
+  HValue* object_map = Add<HLoadNamedField>(
+      object, HObjectAccess::ForMapAsInteger32());
+  HValue* shifted_map = AddUncasted<HShr>(
+      object_map, Add<HConstant>(KeyedLookupCache::kMapHashShift));
+  HValue* string_hash = Add<HLoadNamedField>(
+      key, HObjectAccess::ForStringHashField());
+  HValue* shifted_hash = AddUncasted<HShr>(
+      string_hash, Add<HConstant>(String::kHashShift));
+  HValue* xor_result = AddUncasted<HBitwise>(Token::BIT_XOR, shifted_map,
+                                             shifted_hash);
+  int mask = (KeyedLookupCache::kCapacityMask & KeyedLookupCache::kHashMask);
+  return AddUncasted<HBitwise>(Token::BIT_AND, xor_result,
+                               Add<HConstant>(mask));
+}
+
+
 HValue* HGraphBuilder::BuildUncheckedDictionaryElementLoadHelper(
     HValue* elements,
     HValue* key,
     HValue* hash,
     HValue* mask,
     int current_probe) {
   if (current_probe == kNumberDictionaryProbes) {
     return NULL;
   }
 
@@ skipping 92 matching lines @@
   hash = AddUncasted<HMul>(hash, Add<HConstant>(2057));
   hash->ClearFlag(HValue::kCanOverflow);
 
   // hash = hash ^ (hash >> 16);
   shifted_hash = AddUncasted<HShr>(hash, Add<HConstant>(16));
   return AddUncasted<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
 }
 
 
 HValue* HGraphBuilder::BuildUncheckedDictionaryElementLoad(HValue* receiver,
-                                                           HValue* key) {
-  HValue* elements = AddLoadElements(receiver);
-
-  HValue* hash = BuildElementIndexHash(key);
-
+                                                           HValue* elements,
+                                                           HValue* key,
+                                                           HValue* hash) {
   HValue* capacity = Add<HLoadKeyed>(
       elements,
       Add<HConstant>(NameDictionary::kCapacityIndex),
       static_cast<HValue*>(NULL),
       FAST_SMI_ELEMENTS);
 
   HValue* mask = AddUncasted<HSub>(capacity, graph()->GetConstant1());
   mask->ChangeRepresentation(Representation::Integer32());
   mask->ClearFlag(HValue::kCanOverflow);
 
@@ skipping 9261 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal