Optimize non-mutation Map and Set operations for String keys

src/hydrogen.cc

 // Copyright 2013 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/hydrogen.h"
 
 #include <sstream>
 
 #include "src/v8.h"
 
@@ skipping 12086 matching lines @@
 
 void HOptimizedGraphBuilder::GenerateMathSqrtRT(CallRuntime* call) {
   DCHECK(call->arguments()->length() == 1);
   CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
   HValue* value = Pop();
   HInstruction* result = NewUncasted<HUnaryMathOperation>(value, kMathSqrt);
   return ast_context()->ReturnInstruction(result, call->id());
 }
 
 
+template <typename CollectionType>
+HValue* HOptimizedGraphBuilder::BuildOrderedHashTableFindEntry(HValue* table,
+                                                               HValue* key,
+                                                               HValue* hash) {
+  HValue* num_buckets = Add<HLoadKeyed>(
+      table, Add<HConstant>(CollectionType::kNumberOfBucketsIndex),

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

Why LoadKeyed here? Since the offset is constant, this should be LoadNamedField.
Ditto in other places below

[adamk, 2014/12/02 21:00:38]

Done.

In my defense, I was following the code in
HGraphBuilder::BuildUncheckedDictionaryElementLoad(). And now I have to
duplicate FixedArray indexing logic. But I agree it makes sense make this a
named load.

+      static_cast<HValue*>(NULL), FAST_ELEMENTS);
+  num_buckets->set_type(HType::Smi());
+
+  // Some things that won't change inside the loop
+  HValue* not_found = Add<HConstant>(CollectionType::kNotFound);
+  HValue* start_index = Add<HConstant>(CollectionType::kHashTableStartIndex);
+  HValue* entry_size = Add<HConstant>(CollectionType::kEntrySize);
+  HValue* chain_offset = Add<HConstant>(CollectionType::kChainOffset);
+  HValue* key_start = AddUncasted<HAdd>(start_index, num_buckets);
+  key_start->ClearFlag(HValue::kCanOverflow);
+
+  // BuildHashToBucket
+  HValue* mask = AddUncasted<HSub>(num_buckets, graph()->GetConstant1());
+  mask->ChangeRepresentation(Representation::Integer32());
+  mask->ClearFlag(HValue::kCanOverflow);
+
+  HValue* bucket = AddUncasted<HBitwise>(Token::BIT_AND, hash, mask);
+
+  // BuildHashToEntry
+  HValue* entry_index = AddUncasted<HAdd>(start_index, bucket);
+  entry_index->ClearFlag(HValue::kCanOverflow);
+  HValue* entry =
+      Add<HLoadKeyed>(table, entry_index, static_cast<HValue*>(NULL),
+                      FAST_ELEMENTS, ALLOW_RETURN_HOLE);
+  entry->set_type(HType::Smi());
+
+  Push(entry);
+
+  // LOOP
+  LoopBuilder loop(this);

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

Nit: use RAII for Loop/IfBuilders

[adamk, 2014/12/02 21:00:38]

Can you explain what you mean here? Do you mean you want more C++ blocks? Or
something else?

[Dmitry Lomov (no reviews), 2014/12/02 21:26:27]

Yes; sorry for being unclear; the pattern is:
{ IfBuilder if(..)
}

etc. You do not need to call End on IfBuilders then 

[adamk, 2014/12/02 21:37:57]

That works on IfBuilders, but LoopBuilder just has a DCHECK(finished_) in its
destructor. I've fixed up my ifs, but left the loop as-is. A followup patch
could change LoopBuilder's behavior, but I'd rather not touch it in this one.

+  loop.BeginBody(1);
+
+  entry = Pop();
+
+  IfBuilder if_not_found(this);
+  if_not_found.If<HCompareNumericAndBranch>(entry, not_found, Token::EQ);
+  if_not_found.Then();
+  Push(entry);
+  loop.Break();
+  if_not_found.End();
+
+  // BuildEntryToIndex
+  HValue* key_index = AddUncasted<HMul>(entry, entry_size);
+  key_index->ClearFlag(HValue::kCanOverflow);
+  key_index = AddUncasted<HAdd>(key_index, key_start);
+  key_index->ClearFlag(HValue::kCanOverflow);
+  // BuildKeyAt
+  HValue* candidate_key =
+      Add<HLoadKeyed>(table, key_index, static_cast<HValue*>(NULL),
+                      FAST_ELEMENTS, ALLOW_RETURN_HOLE);
+
+  IfBuilder if_keys_equal(this);
+  if_keys_equal.If<HIsStringAndBranch>(candidate_key);
+  if_keys_equal.AndIf<HStringCompareAndBranch>(candidate_key, key,
+                                               Token::EQ_STRICT);
+  if_keys_equal.Then();
+  Push(key_index);
+  loop.Break();
+  if_keys_equal.End();
+
+  // BuildChainAt
+  HValue* chain_index = AddUncasted<HMul>(entry, entry_size);
+  chain_index->ClearFlag(HValue::kCanOverflow);
+  chain_index = AddUncasted<HAdd>(chain_index, key_start);
+  chain_index->ClearFlag(HValue::kCanOverflow);
+  chain_index = AddUncasted<HAdd>(chain_index, chain_offset);
+  chain_index->ClearFlag(HValue::kCanOverflow);
+  entry = Add<HLoadKeyed>(table, chain_index, static_cast<HValue*>(NULL),
+                          FAST_ELEMENTS, ALLOW_RETURN_HOLE);
+  entry->set_type(HType::Smi());
+  Push(entry);
+
+  loop.EndBody();
+
+  return Pop();
+}
+
+
+void HOptimizedGraphBuilder::GenerateMapGet(CallRuntime* call) {
+  DCHECK(call->arguments()->length() == 2);
+  CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
+  CHECK_ALIVE(VisitForValue(call->arguments()->at(1)));
+  HValue* key = Pop();
+  HValue* receiver = Pop();
+
+  NoObservableSideEffectsScope no_effects(this);
+
+  HIfContinuation continuation;
+  HValue* hash =
+      BuildStringHashLoadIfIsStringAndHashComputed(key, &continuation);
+  IfBuilder string_checker(this, &continuation);
+  string_checker.Then();
+  {
+    HValue* table = Add<HLoadNamedField>(
+        receiver, static_cast<HValue*>(NULL),
+        HObjectAccess::ForObservableJSObjectOffset(JSCollection::kTableOffset));
+    HValue* key_index =
+        BuildOrderedHashTableFindEntry<OrderedHashMap>(table, key, hash);
+    IfBuilder if_found(this);
+    if_found.If<HCompareNumericAndBranch>(
+        key_index, Add<HConstant>(OrderedHashMap::kNotFound), Token::NE);
+    if_found.Then();
+    {
+      HValue* value_index = AddUncasted<HAdd>(
+          key_index, Add<HConstant>(OrderedHashMap::kValueOffset));
+      value_index->ClearFlag(HValue::kCanOverflow);
+      Push(Add<HLoadKeyed>(table, value_index, static_cast<HValue*>(NULL),
+                           FAST_ELEMENTS));
+    }
+    if_found.Else();
+    Push(graph()->GetConstantUndefined());
+    if_found.End();
+  }
+  string_checker.Else();
+  {
+    Add<HPushArguments>(receiver, key);
+    Push(Add<HCallRuntime>(isolate()->factory()->empty_string(),
+                           Runtime::FunctionForId(Runtime::kMapGet), 2));
+  }
+  string_checker.End();
+
+  return ast_context()->ReturnValue(Pop());
+}
+
+
+HValue* HOptimizedGraphBuilder::BuildStringHashLoadIfIsStringAndHashComputed(
+    HValue* object, HIfContinuation* continuation) {
+  IfBuilder string_checker(this);
+  string_checker.If<HIsStringAndBranch>(object);
+  string_checker.And();
+  HValue* hash = Add<HLoadNamedField>(object, static_cast<HValue*>(NULL),
+                                      HObjectAccess::ForStringHashField());
+  HValue* hash_not_computed_mask = Add<HConstant>(String::kHashNotComputedMask);
+  HValue* hash_computed_test =
+      AddUncasted<HBitwise>(Token::BIT_AND, hash, hash_not_computed_mask);
+  string_checker.If<HCompareNumericAndBranch>(
+      hash_computed_test, graph()->GetConstant0(), Token::EQ);
+  string_checker.Then();
+  HValue* shifted_hash =
+      AddUncasted<HShr>(hash, Add<HConstant>(String::kHashShift));
+  string_checker.CaptureContinuation(continuation);
+  return shifted_hash;
+}
+
+
+template <typename CollectionType>
+void HOptimizedGraphBuilder::BuildJSCollectionHas(
+    CallRuntime* call, const Runtime::Function* c_function) {
+  DCHECK(call->arguments()->length() == 2);
+  CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
+  CHECK_ALIVE(VisitForValue(call->arguments()->at(1)));
+  HValue* key = Pop();
+  HValue* receiver = Pop();
+
+  NoObservableSideEffectsScope no_effects(this);
+
+  HIfContinuation continuation;
+  HValue* hash =
+      BuildStringHashLoadIfIsStringAndHashComputed(key, &continuation);
+  IfBuilder string_checker(this, &continuation);
+  string_checker.Then();
+  {
+    HValue* table = Add<HLoadNamedField>(
+        receiver, static_cast<HValue*>(NULL),
+        HObjectAccess::ForObservableJSObjectOffset(JSCollection::kTableOffset));

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

Nit: Add HObjectAccess::ForJSCollectionTable()

[adamk, 2014/12/02 21:00:38]

Done.

+    HValue* key_index =
+        BuildOrderedHashTableFindEntry<CollectionType>(table, key, hash);
+    IfBuilder if_found(this);
+    if_found.If<HCompareNumericAndBranch>(
+        key_index, Add<HConstant>(CollectionType::kNotFound), Token::NE);
+    if_found.Then();
+    Push(graph()->GetConstantTrue());
+    if_found.Else();
+    Push(graph()->GetConstantFalse());
+    if_found.End();
+  }
+  string_checker.Else();
+  {
+    Add<HPushArguments>(receiver, key);
+    Push(
+        Add<HCallRuntime>(isolate()->factory()->empty_string(), c_function, 2));

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

nit: Please pass a name here.
I wonder why everyone just passes an empty string here...
In this case, it is easy: just plumb call->name() from callers.

[adamk, 2014/12/02 21:00:39]

Done.

+  }
+  string_checker.End();
+
+  return ast_context()->ReturnValue(Pop());
+}
+
+
+void HOptimizedGraphBuilder::GenerateMapHas(CallRuntime* call) {
+  BuildJSCollectionHas<OrderedHashMap>(
+      call, Runtime::FunctionForId(Runtime::kMapHas));
+}
+
+
+void HOptimizedGraphBuilder::GenerateSetHas(CallRuntime* call) {
+  BuildJSCollectionHas<OrderedHashSet>(
+      call, Runtime::FunctionForId(Runtime::kSetHas));
+}
+
+
+void HOptimizedGraphBuilder::GenerateSetGetSize(CallRuntime* call) {
+  DCHECK(call->arguments()->length() == 1);
+  CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
+  HValue* receiver = Pop();
+  HValue* table = Add<HLoadNamedField>(
+      receiver, static_cast<HValue*>(NULL),
+      HObjectAccess::ForObservableJSObjectOffset(JSSet::kTableOffset));

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

Nit: Add HObjectAccess::ForJSCollectionTable()

[adamk, 2014/12/02 21:00:38]

Done.

+  HInstruction* result = New<HLoadKeyed>(
+      table, Add<HConstant>(OrderedHashSet::kNumberOfElementsIndex),
+      static_cast<HValue*>(NULL), FAST_ELEMENTS);
+  return ast_context()->ReturnInstruction(result, call->id());
+}
+
+
+void HOptimizedGraphBuilder::GenerateMapGetSize(CallRuntime* call) {
+  DCHECK(call->arguments()->length() == 1);
+  CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
+  HValue* receiver = Pop();
+  HValue* table = Add<HLoadNamedField>(
+      receiver, static_cast<HValue*>(NULL),
+      HObjectAccess::ForObservableJSObjectOffset(JSMap::kTableOffset));

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

Nit: Add HObjectAccess::ForJSCollectionTable()

[adamk, 2014/12/02 21:00:38]

Done.

+  HInstruction* result = New<HLoadKeyed>(
+      table, Add<HConstant>(OrderedHashMap::kNumberOfElementsIndex),
+      static_cast<HValue*>(NULL), FAST_ELEMENTS);

[Dmitry Lomov (no reviews), 2014/11/27 18:18:26]

Why LoadKeyed here? Since the offset is constant, this should be LoadNamedField

[adamk, 2014/12/02 21:00:37]

Done.

+  return ast_context()->ReturnInstruction(result, call->id());
+}
+
+
 void HOptimizedGraphBuilder::GenerateGetCachedArrayIndex(CallRuntime* call) {
   DCHECK(call->arguments()->length() == 1);
   CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
   HValue* value = Pop();
   HGetCachedArrayIndex* result = New<HGetCachedArrayIndex>(value);
   return ast_context()->ReturnInstruction(result, call->id());
 }
 
 
 void HOptimizedGraphBuilder::GenerateFastOneByteArrayJoin(CallRuntime* call) {
@@ skipping 659 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal