Revision: 17804
Author: [email protected]
Date: Fri Nov 15 17:53:35 2013 UTC
Log: Generate KeyedLoadDictionaryElementStub with Hydrogen
[email protected]
Review URL: https://codereview.chromium.org/19492007
http://code.google.com/p/v8/source/detail?r=17804
Modified:
/branches/bleeding_edge/src/arm/code-stubs-arm.cc
/branches/bleeding_edge/src/arm/macro-assembler-arm.cc
/branches/bleeding_edge/src/code-stubs-hydrogen.cc
/branches/bleeding_edge/src/code-stubs.cc
/branches/bleeding_edge/src/code-stubs.h
/branches/bleeding_edge/src/codegen.h
/branches/bleeding_edge/src/flag-definitions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/hydrogen.h
/branches/bleeding_edge/src/ia32/code-stubs-ia32.cc
/branches/bleeding_edge/src/ia32/macro-assembler-ia32.cc
/branches/bleeding_edge/src/stub-cache.cc
/branches/bleeding_edge/src/x64/code-stubs-x64.cc
/branches/bleeding_edge/src/x64/macro-assembler-x64.cc
=======================================
--- /branches/bleeding_edge/src/arm/code-stubs-arm.cc Fri Nov 15 10:52:05
2013 UTC
+++ /branches/bleeding_edge/src/arm/code-stubs-arm.cc Fri Nov 15 17:53:35
2013 UTC
@@ -111,6 +111,17 @@
descriptor->deoptimization_handler_ =
FUNCTION_ADDR(KeyedLoadIC_MissFromStubFailure);
}
+
+
+void KeyedLoadDictionaryElementStub::InitializeInterfaceDescriptor(
+ Isolate* isolate,
+ CodeStubInterfaceDescriptor* descriptor) {
+ static Register registers[] = { r1, r0 };
+ descriptor->register_param_count_ = 2;
+ descriptor->register_params_ = registers;
+ descriptor->deoptimization_handler_ =
+ FUNCTION_ADDR(KeyedLoadIC_MissFromStubFailure);
+}
void LoadFieldStub::InitializeInterfaceDescriptor(
=======================================
--- /branches/bleeding_edge/src/arm/macro-assembler-arm.cc Thu Nov 14
14:15:52 2013 UTC
+++ /branches/bleeding_edge/src/arm/macro-assembler-arm.cc Fri Nov 15
17:53:35 2013 UTC
@@ -1566,8 +1566,7 @@
sub(t1, t1, Operand(1));
// Generate an unrolled loop that performs a few probes before giving up.
- static const int kProbes = 4;
- for (int i = 0; i < kProbes; i++) {
+ for (int i = 0; i < kNumberDictionaryProbes; i++) {
// Use t2 for index calculations and keep the hash intact in t0.
mov(t2, t0);
// Compute the masked index: (hash + i + i * i) & mask.
@@ -1584,7 +1583,7 @@
add(t2, elements, Operand(t2, LSL, kPointerSizeLog2));
ldr(ip, FieldMemOperand(t2,
SeededNumberDictionary::kElementsStartOffset));
cmp(key, Operand(ip));
- if (i != kProbes - 1) {
+ if (i != kNumberDictionaryProbes - 1) {
b(eq, &done);
} else {
b(ne, miss);
=======================================
--- /branches/bleeding_edge/src/code-stubs-hydrogen.cc Fri Nov 15 10:52:05
2013 UTC
+++ /branches/bleeding_edge/src/code-stubs-hydrogen.cc Fri Nov 15 17:53:35
2013 UTC
@@ -1301,6 +1301,141 @@
Handle<Code> FastNewClosureStub::GenerateCode(Isolate* isolate) {
return DoGenerateCode(isolate, this);
}
+
+
+template <>
+class CodeStubGraphBuilder<KeyedLoadDictionaryElementStub>
+ : public CodeStubGraphBuilderBase {
+ public:
+ explicit CodeStubGraphBuilder(Isolate* isolate,
+ KeyedLoadDictionaryElementStub* stub)
+ : CodeStubGraphBuilderBase(isolate, stub) {}
+
+ protected:
+ HValue* BuildCodeStubHelper(HValue* dictionary,
+ HValue* key,
+ HValue* hash,
+ HValue* mask,
+ int current_probe);
+
+ virtual HValue* BuildCodeStub();
+
+ KeyedLoadDictionaryElementStub* casted_stub() {
+ return static_cast<KeyedLoadDictionaryElementStub*>(stub());
+ }
+};
+
+
+HValue* CodeStubGraphBuilder<KeyedLoadDictionaryElementStub>::
+ BuildCodeStubHelper(
+ HValue* elements,
+ HValue* key,
+ HValue* hash,
+ HValue* mask,
+ int current_probe) {
+ if (current_probe == kNumberDictionaryProbes) {
+ return NULL;
+ }
+
+ int32_t offset = SeededNumberDictionary::GetProbeOffset(current_probe);
+ HValue* raw_index = (current_probe == 0)
+ ? hash
+ : Add<HAdd>(hash, Add<HConstant>(offset));
+ raw_index = Add<HBitwise>(Token::BIT_AND, raw_index, mask);
+ int32_t entry_size = SeededNumberDictionary::kEntrySize;
+ raw_index = Add<HMul>(raw_index, Add<HConstant>(entry_size));
+ raw_index->ClearFlag(HValue::kCanOverflow);
+
+ int32_t base_offset = SeededNumberDictionary::kElementsStartIndex;
+ HValue* key_index = Add<HAdd>(raw_index, Add<HConstant>(base_offset));
+ key_index->ClearFlag(HValue::kCanOverflow);
+
+ HValue* candidate_key = Add<HLoadKeyed>(elements, key_index,
+ static_cast<HValue*>(NULL),
+ FAST_SMI_ELEMENTS);
+
+ IfBuilder key_compare(this);
+ key_compare.IfNot<HCompareObjectEqAndBranch>(key, candidate_key);
+ key_compare.Then();
+ {
+ // Key at the current probe doesn't match, try at the next probe.
+ HValue* result = BuildCodeStubHelper(elements, key, hash, mask,
+ current_probe + 1);
+ if (result == NULL) {
+ key_compare.Deopt("probes exhausted in keyed load dictionary
lookup");
+ result = graph()->GetConstantUndefined();
+ } else {
+ Push(result);
+ }
+ }
+ key_compare.Else();
+ {
+ // Key at current probe matches. Details must be zero, otherwise the
+ // dictionary element requires special handling.
+ HValue* details_index = Add<HAdd>(raw_index,
+ Add<HConstant>(base_offset + 2));
+ details_index->ClearFlag(HValue::kCanOverflow);
+
+ HValue* details = Add<HLoadKeyed>(elements, details_index,
+ static_cast<HValue*>(NULL),
+ FAST_SMI_ELEMENTS);
+ IfBuilder details_compare(this);
+ details_compare.If<HCompareNumericAndBranch>(details,
+ graph()->GetConstant0(),
+ Token::NE);
+ details_compare.ThenDeopt("keyed load dictionary element not fast
case");
+
+ details_compare.Else();
+ {
+ // Key matches and details are zero --> fast case. Load and return
the
+ // value.
+ HValue* result_index = Add<HAdd>(raw_index,
+ Add<HConstant>(base_offset + 1));
+ result_index->ClearFlag(HValue::kCanOverflow);
+
+ Push(Add<HLoadKeyed>(elements, result_index,
+ static_cast<HValue*>(NULL),
+ FAST_ELEMENTS));
+ }
+ details_compare.End();
+ }
+ key_compare.End();
+
+ return Pop();
+}
+
+
+HValue*
CodeStubGraphBuilder<KeyedLoadDictionaryElementStub>::BuildCodeStub() {
+ KeyedLoadDictionaryElementStub* stub = casted_stub();
+
+ HValue* dictionary = GetParameter(0);
+ HValue* key = GetParameter(1);
+ USE(stub);
+ USE(dictionary);
+
+ HValue* elements = AddLoadElements(dictionary);
+
+ Add<HCheckSmi>(key);
+
+ HValue* hash = BuildElementIndexHash(key);
+
+ HValue* capacity = Add<HLoadKeyed>(
+ elements,
+ Add<HConstant>(NameDictionary::kCapacityIndex),
+ static_cast<HValue*>(NULL),
+ FAST_SMI_ELEMENTS);
+
+ HValue* mask = Add<HSub>(capacity, graph()->GetConstant1());
+ mask->ChangeRepresentation(Representation::Integer32());
+ mask->ClearFlag(HValue::kCanOverflow);
+
+ return BuildCodeStubHelper(elements, key, hash, mask, 0);
+}
+
+
+Handle<Code> KeyedLoadDictionaryElementStub::GenerateCode(Isolate*
isolate) {
+ return DoGenerateCode(isolate, this);
+}
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/code-stubs.cc Fri Nov 15 10:52:05 2013 UTC
+++ /branches/bleeding_edge/src/code-stubs.cc Fri Nov 15 17:53:35 2013 UTC
@@ -964,7 +964,8 @@
}
-void KeyedLoadDictionaryElementStub::Generate(MacroAssembler* masm) {
+void KeyedLoadDictionaryElementPlatformStub::Generate(
+ MacroAssembler* masm) {
KeyedLoadStubCompiler::GenerateLoadDictionaryElement(masm);
}
=======================================
--- /branches/bleeding_edge/src/code-stubs.h Fri Nov 15 10:52:05 2013 UTC
+++ /branches/bleeding_edge/src/code-stubs.h Fri Nov 15 17:53:35 2013 UTC
@@ -1839,9 +1839,27 @@
};
-class KeyedLoadDictionaryElementStub : public PlatformCodeStub {
+class KeyedLoadDictionaryElementStub : public HydrogenCodeStub {
public:
KeyedLoadDictionaryElementStub() {}
+
+ virtual Handle<Code> GenerateCode(Isolate* isolate) V8_OVERRIDE;
+
+ virtual void InitializeInterfaceDescriptor(
+ Isolate* isolate,
+ CodeStubInterfaceDescriptor* descriptor) V8_OVERRIDE;
+
+ private:
+ Major MajorKey() { return KeyedLoadElement; }
+ int NotMissMinorKey() { return DICTIONARY_ELEMENTS; }
+
+ DISALLOW_COPY_AND_ASSIGN(KeyedLoadDictionaryElementStub);
+};
+
+
+class KeyedLoadDictionaryElementPlatformStub : public PlatformCodeStub {
+ public:
+ KeyedLoadDictionaryElementPlatformStub() {}
void Generate(MacroAssembler* masm);
@@ -1849,7 +1867,7 @@
Major MajorKey() { return KeyedLoadElement; }
int MinorKey() { return DICTIONARY_ELEMENTS; }
- DISALLOW_COPY_AND_ASSIGN(KeyedLoadDictionaryElementStub);
+ DISALLOW_COPY_AND_ASSIGN(KeyedLoadDictionaryElementPlatformStub);
};
=======================================
--- /branches/bleeding_edge/src/codegen.h Fri Jul 19 13:30:49 2013 UTC
+++ /branches/bleeding_edge/src/codegen.h Fri Nov 15 17:53:35 2013 UTC
@@ -112,6 +112,8 @@
DISALLOW_COPY_AND_ASSIGN(ElementsTransitionGenerator);
};
+static const int kNumberDictionaryProbes = 4;
+
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/flag-definitions.h Tue Nov 12 10:21:08 2013
UTC
+++ /branches/bleeding_edge/src/flag-definitions.h Fri Nov 15 17:53:35 2013
UTC
@@ -202,6 +202,8 @@
// Flags for experimental implementation features.
DEFINE_bool(packed_arrays, true, "optimizes arrays that have no holes")
DEFINE_bool(smi_only_arrays, true, "tracks arrays with only smi values")
+DEFINE_bool(compiled_keyed_dictionary_loads, false,
+ "use optimizing compiler to generate keyed dictionary load
stubs")
DEFINE_bool(clever_optimizations, true,
"Optimize object size, Array shift, DOM strings and string +")
DEFINE_bool(pretenuring, true, "allocate objects in old space")
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Fri Nov 15 12:10:59 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen.cc Fri Nov 15 17:53:35 2013 UTC
@@ -1403,6 +1403,138 @@
Add<HStoreNamedField>(object, HObjectAccess::ForMap(), map);
}
+
+
+HValue* HGraphBuilder::BuildUncheckedDictionaryElementLoadHelper(
+ HValue* elements,
+ HValue* key,
+ HValue* hash,
+ HValue* mask,
+ int current_probe) {
+ if (current_probe == kNumberDictionaryProbes) {
+ return NULL;
+ }
+
+ int32_t offset = SeededNumberDictionary::GetProbeOffset(current_probe);
+ HValue* raw_index = (current_probe == 0)
+ ? hash
+ : Add<HAdd>(hash, Add<HConstant>(offset));
+ raw_index = Add<HBitwise>(Token::BIT_AND, raw_index, mask);
+ int32_t entry_size = SeededNumberDictionary::kEntrySize;
+ raw_index = Add<HMul>(raw_index, Add<HConstant>(entry_size));
+ raw_index->ClearFlag(HValue::kCanOverflow);
+
+ int32_t base_offset = SeededNumberDictionary::kElementsStartIndex;
+ HValue* key_index = Add<HAdd>(raw_index, Add<HConstant>(base_offset));
+ key_index->ClearFlag(HValue::kCanOverflow);
+
+ HValue* candidate_key = Add<HLoadKeyed>(elements, key_index,
+ static_cast<HValue*>(NULL),
+ FAST_SMI_ELEMENTS);
+
+ IfBuilder key_compare(this);
+ key_compare.IfNot<HCompareObjectEqAndBranch>(key, candidate_key);
+ key_compare.Then();
+ {
+ // Key at the current probe doesn't match, try at the next probe.
+ HValue* result = BuildUncheckedDictionaryElementLoadHelper(
+ elements, key, hash, mask, current_probe + 1);
+ if (result == NULL) {
+ key_compare.Deopt("probes exhausted in keyed load dictionary
lookup");
+ result = graph()->GetConstantUndefined();
+ } else {
+ Push(result);
+ }
+ }
+ key_compare.Else();
+ {
+ // Key at current probe matches. Details must be zero, otherwise the
+ // dictionary element requires special handling.
+ HValue* details_index = Add<HAdd>(raw_index,
+ Add<HConstant>(base_offset + 2));
+ details_index->ClearFlag(HValue::kCanOverflow);
+
+ HValue* details = Add<HLoadKeyed>(elements, details_index,
+ static_cast<HValue*>(NULL),
+ FAST_SMI_ELEMENTS);
+ IfBuilder details_compare(this);
+ details_compare.If<HCompareNumericAndBranch>(details,
+ graph()->GetConstant0(),
+ Token::NE);
+ details_compare.ThenDeopt("keyed load dictionary element not fast
case");
+
+ details_compare.Else();
+ {
+ // Key matches and details are zero --> fast case. Load and return
the
+ // value.
+ HValue* result_index = Add<HAdd>(raw_index,
+ Add<HConstant>(base_offset + 1));
+ result_index->ClearFlag(HValue::kCanOverflow);
+
+ Push(Add<HLoadKeyed>(elements, result_index,
+ static_cast<HValue*>(NULL),
+ FAST_ELEMENTS));
+ }
+ details_compare.End();
+ }
+ key_compare.End();
+
+ return Pop();
+}
+
+
+HValue* HGraphBuilder::BuildElementIndexHash(HValue* index) {
+ int32_t seed_value =
static_cast<uint32_t>(isolate()->heap()->HashSeed());
+ HValue* seed = Add<HConstant>(seed_value);
+ HValue* hash = Add<HBitwise>(Token::BIT_XOR, index, seed);
+
+ // hash = ~hash + (hash << 15);
+ HValue* shifted_hash = Add<HShl>(hash, Add<HConstant>(15));
+ HValue* not_hash = Add<HBitwise>(Token::BIT_XOR, hash,
+ graph()->GetConstantMinus1());
+ hash = Add<HAdd>(shifted_hash, not_hash);
+
+ // hash = hash ^ (hash >> 12);
+ shifted_hash = Add<HShr>(hash, Add<HConstant>(12));
+ hash = Add<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
+
+ // hash = hash + (hash << 2);
+ shifted_hash = Add<HShl>(hash, Add<HConstant>(2));
+ hash = Add<HAdd>(hash, shifted_hash);
+
+ // hash = hash ^ (hash >> 4);
+ shifted_hash = Add<HShr>(hash, Add<HConstant>(4));
+ hash = Add<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
+
+ // hash = hash * 2057;
+ hash = Add<HMul>(hash, Add<HConstant>(2057));
+ hash->ClearFlag(HValue::kCanOverflow);
+
+ // hash = hash ^ (hash >> 16);
+ shifted_hash = Add<HShr>(hash, Add<HConstant>(16));
+ return Add<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
+}
+
+
+HValue* HGraphBuilder::BuildUncheckedDictionaryElementLoad(HValue*
receiver,
+ HValue* key) {
+ HValue* elements = AddLoadElements(receiver);
+
+ HValue* hash = BuildElementIndexHash(key);
+
+ HValue* capacity = Add<HLoadKeyed>(
+ elements,
+ Add<HConstant>(NameDictionary::kCapacityIndex),
+ static_cast<HValue*>(NULL),
+ FAST_SMI_ELEMENTS);
+
+ HValue* mask = Add<HSub>(capacity, graph()->GetConstant1());
+ mask->ChangeRepresentation(Representation::Integer32());
+ mask->ClearFlag(HValue::kCanOverflow);
+
+ return BuildUncheckedDictionaryElementLoadHelper(elements, key,
+ hash, mask, 0);
+}
HValue* HGraphBuilder::BuildNumberToString(HValue* object,
=======================================
--- /branches/bleeding_edge/src/hydrogen.h Fri Nov 15 10:52:05 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen.h Fri Nov 15 17:53:35 2013 UTC
@@ -1279,6 +1279,9 @@
HValue* BuildNumberToString(HValue* object, Handle<Type> type);
+ HValue* BuildUncheckedDictionaryElementLoad(HValue* receiver,
+ HValue* key);
+
// Computes the size for a sequential string of the given length and
encoding.
HValue* BuildSeqStringSizeFor(HValue* length,
String::Encoding encoding);
@@ -1701,6 +1704,8 @@
ElementsKind kind,
int length);
+ HValue* BuildElementIndexHash(HValue* index);
+
void BuildCompareNil(
HValue* value,
Handle<Type> type,
@@ -1727,6 +1732,13 @@
private:
HGraphBuilder();
+ HValue* BuildUncheckedDictionaryElementLoadHelper(
+ HValue* elements,
+ HValue* key,
+ HValue* hash,
+ HValue* mask,
+ int current_probe);
+
void PadEnvironmentForContinuation(HBasicBlock* from,
HBasicBlock* continuation);
=======================================
--- /branches/bleeding_edge/src/ia32/code-stubs-ia32.cc Fri Nov 15 10:52:05
2013 UTC
+++ /branches/bleeding_edge/src/ia32/code-stubs-ia32.cc Fri Nov 15 17:53:35
2013 UTC
@@ -116,6 +116,17 @@
descriptor->deoptimization_handler_ =
FUNCTION_ADDR(KeyedLoadIC_MissFromStubFailure);
}
+
+
+void KeyedLoadDictionaryElementStub::InitializeInterfaceDescriptor(
+ Isolate* isolate,
+ CodeStubInterfaceDescriptor* descriptor) {
+ static Register registers[] = { edx, ecx };
+ descriptor->register_param_count_ = 2;
+ descriptor->register_params_ = registers;
+ descriptor->deoptimization_handler_ =
+ FUNCTION_ADDR(KeyedLoadIC_MissFromStubFailure);
+}
void LoadFieldStub::InitializeInterfaceDescriptor(
=======================================
--- /branches/bleeding_edge/src/ia32/macro-assembler-ia32.cc Tue Nov 12
09:08:51 2013 UTC
+++ /branches/bleeding_edge/src/ia32/macro-assembler-ia32.cc Fri Nov 15
17:53:35 2013 UTC
@@ -1489,8 +1489,7 @@
dec(r1);
// Generate an unrolled loop that performs a few probes before giving up.
- const int kProbes = 4;
- for (int i = 0; i < kProbes; i++) {
+ for (int i = 0; i < kNumberDictionaryProbes; i++) {
// Use r2 for index calculations and keep the hash intact in r0.
mov(r2, r0);
// Compute the masked index: (hash + i + i * i) & mask.
@@ -1508,7 +1507,7 @@
r2,
times_pointer_size,
SeededNumberDictionary::kElementsStartOffset));
- if (i != (kProbes - 1)) {
+ if (i != (kNumberDictionaryProbes - 1)) {
j(equal, &done);
} else {
j(not_equal, miss);
=======================================
--- /branches/bleeding_edge/src/stub-cache.cc Fri Nov 15 09:34:44 2013 UTC
+++ /branches/bleeding_edge/src/stub-cache.cc Fri Nov 15 17:53:35 2013 UTC
@@ -1480,8 +1480,9 @@
elements_kind).GetCode(isolate());
__ DispatchMap(receiver(), scratch1(), receiver_map, stub,
DO_SMI_CHECK);
} else {
- Handle<Code> stub =
- KeyedLoadDictionaryElementStub().GetCode(isolate());
+ Handle<Code> stub = FLAG_compiled_keyed_dictionary_loads
+ ? KeyedLoadDictionaryElementStub().GetCode(isolate())
+ : KeyedLoadDictionaryElementPlatformStub().GetCode(isolate());
__ DispatchMap(receiver(), scratch1(), receiver_map, stub,
DO_SMI_CHECK);
}
=======================================
--- /branches/bleeding_edge/src/x64/code-stubs-x64.cc Fri Nov 15 10:52:05
2013 UTC
+++ /branches/bleeding_edge/src/x64/code-stubs-x64.cc Fri Nov 15 17:53:35
2013 UTC
@@ -112,6 +112,17 @@
descriptor->deoptimization_handler_ =
FUNCTION_ADDR(KeyedLoadIC_MissFromStubFailure);
}
+
+
+void KeyedLoadDictionaryElementStub::InitializeInterfaceDescriptor(
+ Isolate* isolate,
+ CodeStubInterfaceDescriptor* descriptor) {
+ static Register registers[] = { rdx, rcx };
+ descriptor->register_param_count_ = 2;
+ descriptor->register_params_ = registers;
+ descriptor->deoptimization_handler_ =
+ FUNCTION_ADDR(KeyedLoadIC_MissFromStubFailure);
+}
void LoadFieldStub::InitializeInterfaceDescriptor(
=======================================
--- /branches/bleeding_edge/src/x64/macro-assembler-x64.cc Thu Nov 14
15:14:37 2013 UTC
+++ /branches/bleeding_edge/src/x64/macro-assembler-x64.cc Fri Nov 15
17:53:35 2013 UTC
@@ -3980,8 +3980,7 @@
decl(r1);
// Generate an unrolled loop that performs a few probes before giving up.
- const int kProbes = 4;
- for (int i = 0; i < kProbes; i++) {
+ for (int i = 0; i < kNumberDictionaryProbes; i++) {
// Use r2 for index calculations and keep the hash intact in r0.
movq(r2, r0);
// Compute the masked index: (hash + i + i * i) & mask.
@@ -3999,7 +3998,7 @@
r2,
times_pointer_size,
SeededNumberDictionary::kElementsStartOffset));
- if (i != (kProbes - 1)) {
+ if (i != (kNumberDictionaryProbes - 1)) {
j(equal, &done);
} else {
j(not_equal, miss);
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
