OLD | NEW |
---|---|
1 // Copyright 2017 the V8 project authors. All rights reserved. | 1 // Copyright 2017 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/builtins/builtins-constructor-gen.h" | 5 #include "src/builtins/builtins-constructor-gen.h" |
6 #include "src/builtins/builtins-iterator-gen.h" | 6 #include "src/builtins/builtins-iterator-gen.h" |
7 #include "src/builtins/builtins-utils-gen.h" | 7 #include "src/builtins/builtins-utils-gen.h" |
8 #include "src/code-stub-assembler.h" | 8 #include "src/code-stub-assembler.h" |
9 #include "src/objects/hash-table.h" | 9 #include "src/objects/hash-table.h" |
10 | 10 |
(...skipping 11 matching lines...) Expand all Loading... | |
22 Node* AllocateJSMap(Node* js_map_function); | 22 Node* AllocateJSMap(Node* js_map_function); |
23 | 23 |
24 template <typename CollectionType> | 24 template <typename CollectionType> |
25 Node* AllocateOrderedHashTable(); | 25 Node* AllocateOrderedHashTable(); |
26 Node* AllocateJSCollection(Node* js_map_function); | 26 Node* AllocateJSCollection(Node* js_map_function); |
27 | 27 |
28 Node* CallGetRaw(Node* const table, Node* const key); | 28 Node* CallGetRaw(Node* const table, Node* const key); |
29 template <typename CollectionType, int entrysize> | 29 template <typename CollectionType, int entrysize> |
30 Node* CallHasRaw(Node* const table, Node* const key); | 30 Node* CallHasRaw(Node* const table, Node* const key); |
31 | 31 |
32 // Tries to find OrderedHashMap entry for given Smi key, jumps | 32 // Builds code that finds OrderedHashMap entry for given key with hash code |
33 // to {entry_found} if the key is found, or to {not_found} if the | 33 // {hash} with using the comparison code generated by {key_compare}. The code |
34 // key was not found. Returns the node with the entry index (relative to | 34 // jumps to {entry_found} if the key is found, or to {not_found} if the key |
35 // OrderedHashMap::kHashTableStartIndex). The node can only be used in the | 35 // was not found. In the {entry_found} branch, the variable |
36 // {entry_found} branch. | 36 // entry_start_position will be bound to the index of the entry (relative to |
37 Node* FindOrderedHashMapEntryForSmiKey(Node* table, Node* key_tagged, | 37 // OrderedHashMap::kHashTableStartIndex). |
38 Label* entry_found, Label* not_found); | 38 void FindOrderedHashMapEntry( |
39 Node* table, Node* key_tagged, Node* hash, | |
40 std::function<void(Node* other, Label* if_same, Label* if_not_same)> | |
41 key_compare, | |
42 Label* entry_found, Variable* entry_start_position, Label* not_found); | |
Camillo Bruni
2017/07/03 14:51:29
nit: I think it would be nice to have the entry_fo
Jarin
2017/07/04 04:24:47
Well, the idea behind this order was that entry_st
| |
43 | |
44 // Specialization for Smi. | |
45 void FindOrderedHashMapEntryForSmiKey(Node* table, Node* key_tagged, | |
46 Label* entry_found, | |
47 Variable* entry_start_position, | |
48 Label* not_found); | |
49 void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same, | |
50 Label* if_not_same); | |
51 | |
52 // Specialization for String. | |
53 void FindOrderedHashMapEntryForStringKey(Node* context, Node* table, | |
54 Node* key_tagged, Label* entry_found, | |
55 Variable* entry_start_position, | |
56 Label* not_found); | |
57 Node* ComputeIntegerHashForString(Node* context, Node* string_key); | |
58 void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key, | |
59 Label* if_same, Label* if_not_same); | |
39 }; | 60 }; |
40 | 61 |
41 template <typename CollectionType> | 62 template <typename CollectionType> |
42 Node* CollectionsBuiltinsAssembler::AllocateOrderedHashTable() { | 63 Node* CollectionsBuiltinsAssembler::AllocateOrderedHashTable() { |
43 static const int kCapacity = CollectionType::kMinCapacity; | 64 static const int kCapacity = CollectionType::kMinCapacity; |
44 static const int kBucketCount = kCapacity / CollectionType::kLoadFactor; | 65 static const int kBucketCount = kCapacity / CollectionType::kLoadFactor; |
45 static const int kDataTableLength = kCapacity * CollectionType::kEntrySize; | 66 static const int kDataTableLength = kCapacity * CollectionType::kEntrySize; |
46 static const int kFixedArrayLength = | 67 static const int kFixedArrayLength = |
47 CollectionType::kHashTableStartIndex + kBucketCount + kDataTableLength; | 68 CollectionType::kHashTableStartIndex + kBucketCount + kDataTableLength; |
48 static const int kDataTableStartIndex = | 69 static const int kDataTableStartIndex = |
(...skipping 324 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
373 MachineType type_tagged = MachineType::AnyTagged(); | 394 MachineType type_tagged = MachineType::AnyTagged(); |
374 | 395 |
375 Node* const result = | 396 Node* const result = |
376 CallCFunction3(type_uint8, type_ptr, type_tagged, type_tagged, | 397 CallCFunction3(type_uint8, type_ptr, type_tagged, type_tagged, |
377 function_addr, isolate_ptr, table, key); | 398 function_addr, isolate_ptr, table, key); |
378 | 399 |
379 return SelectBooleanConstant( | 400 return SelectBooleanConstant( |
380 Word32NotEqual(Word32And(result, Int32Constant(0xFF)), Int32Constant(0))); | 401 Word32NotEqual(Word32And(result, Int32Constant(0xFF)), Int32Constant(0))); |
381 } | 402 } |
382 | 403 |
383 Node* CollectionsBuiltinsAssembler::FindOrderedHashMapEntryForSmiKey( | 404 void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi, |
384 Node* table, Node* key_tagged, Label* entry_found, Label* not_found) { | 405 Node* candidate_key, |
385 // Compute the hash. | 406 Label* if_same, |
386 Node* const key = SmiUntag(key_tagged); | 407 Label* if_not_same) { |
408 // If the key is the same, we are done. | |
409 GotoIf(WordEqual(candidate_key, key_smi), if_same); | |
410 | |
411 // If the candidate key is smi, then it must be different (because | |
412 // we already checked for equality above). | |
413 GotoIf(TaggedIsSmi(candidate_key), if_not_same); | |
414 | |
415 // If the candidate key is not smi, we still have to check if it is a | |
416 // heap number with the same value. | |
417 GotoIfNot(IsHeapNumber(candidate_key), if_not_same); | |
418 | |
419 Node* const candidate_key_number = LoadHeapNumberValue(candidate_key); | |
420 Node* const key_number = SmiToFloat64(key_smi); | |
421 | |
422 GotoIf(Float64Equal(candidate_key_number, key_number), if_same); | |
423 | |
424 Goto(if_not_same); | |
425 } | |
426 | |
427 void CollectionsBuiltinsAssembler::FindOrderedHashMapEntryForSmiKey( | |
428 Node* table, Node* smi_key, Label* entry_found, | |
429 Variable* entry_start_position, Label* not_found) { | |
430 Node* const key = SmiUntag(smi_key); | |
387 Node* const hash = | 431 Node* const hash = |
388 ChangeInt32ToIntPtr(ComputeIntegerHash(key, Int32Constant(0))); | 432 ChangeInt32ToIntPtr(ComputeIntegerHash(key, Int32Constant(0))); |
433 FindOrderedHashMapEntry( | |
434 table, smi_key, hash, | |
435 [&](Node* other_key, Label* if_same, Label* if_not_same) { | |
436 SameValueZeroSmi(smi_key, other_key, if_same, if_not_same); | |
437 }, | |
438 entry_found, entry_start_position, not_found); | |
439 } | |
389 | 440 |
441 void CollectionsBuiltinsAssembler::FindOrderedHashMapEntryForStringKey( | |
442 Node* context, Node* table, Node* key_tagged, Label* entry_found, | |
443 Variable* entry_start_position, Label* not_found) { | |
444 Node* const hash = ComputeIntegerHashForString(context, key_tagged); | |
445 FindOrderedHashMapEntry( | |
446 table, key_tagged, hash, | |
447 [&](Node* other_key, Label* if_same, Label* if_not_same) { | |
448 SameValueZeroString(context, key_tagged, other_key, if_same, | |
449 if_not_same); | |
450 }, | |
451 entry_found, entry_start_position, not_found); | |
452 } | |
453 | |
454 Node* CollectionsBuiltinsAssembler::ComputeIntegerHashForString( | |
455 Node* context, Node* string_key) { | |
456 VARIABLE(var_result, MachineType::PointerRepresentation()); | |
457 | |
458 Label hash_not_computed(this), done(this, &var_result); | |
459 Node* hash = | |
460 ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed)); | |
461 var_result.Bind(hash); | |
462 Goto(&done); | |
463 | |
464 BIND(&hash_not_computed); | |
465 Node* tagged_hash = CallRuntime(Runtime::kGenericHash, context, string_key); | |
Camillo Bruni
2017/07/03 14:51:29
For me this RT-call is OK.
I remembered jkummerow
Jarin
2017/07/04 04:24:47
Acknowledged.
| |
466 CSA_ASSERT(this, TaggedIsSmi(tagged_hash)); | |
467 var_result.Bind(SmiUntag(tagged_hash)); | |
468 Goto(&done); | |
469 | |
470 BIND(&done); | |
471 return var_result.value(); | |
472 } | |
473 | |
474 void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context, | |
475 Node* key_string, | |
476 Node* candidate_key, | |
477 Label* if_same, | |
478 Label* if_not_same) { | |
479 // If the candidate is not a string, the keys are not equal. | |
480 GotoIf(TaggedIsSmi(candidate_key), if_not_same); | |
481 GotoIfNot(IsString(candidate_key), if_not_same); | |
482 | |
483 Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string, | |
484 candidate_key), | |
485 TrueConstant()), | |
486 if_same, if_not_same); | |
487 } | |
488 | |
489 void CollectionsBuiltinsAssembler::FindOrderedHashMapEntry( | |
490 Node* table, Node* key_tagged, Node* hash, | |
491 std::function<void(Node*, Label*, Label*)> key_compare, Label* entry_found, | |
492 Variable* entry_start_position, Label* not_found) { | |
390 // Get the index of the bucket. | 493 // Get the index of the bucket. |
391 Node* const number_of_buckets = SmiUntag( | 494 Node* const number_of_buckets = SmiUntag( |
392 LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex)); | 495 LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex)); |
393 Node* const bucket = | 496 Node* const bucket = |
394 WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1))); | 497 WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1))); |
395 Node* const first_entry = SmiUntag(LoadFixedArrayElement( | 498 Node* const first_entry = SmiUntag(LoadFixedArrayElement( |
396 table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize)); | 499 table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize)); |
397 | 500 |
398 Node* entry_start_position; | |
399 // Walk the bucket chain. | 501 // Walk the bucket chain. |
400 { | 502 { |
401 VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry); | 503 VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry); |
402 Label loop(this, &var_entry), continue_next_entry(this); | 504 Label loop(this, {&var_entry, entry_start_position}), |
505 continue_next_entry(this); | |
403 Goto(&loop); | 506 Goto(&loop); |
404 BIND(&loop); | 507 BIND(&loop); |
405 | 508 |
406 // If the entry index is the not-found sentinel, we are done. | 509 // If the entry index is the not-found sentinel, we are done. |
407 GotoIf( | 510 GotoIf( |
408 WordEqual(var_entry.value(), IntPtrConstant(OrderedHashMap::kNotFound)), | 511 WordEqual(var_entry.value(), IntPtrConstant(OrderedHashMap::kNotFound)), |
409 not_found); | 512 not_found); |
410 | 513 |
411 // Make sure the entry index is within range. | 514 // Make sure the entry index is within range. |
412 CSA_ASSERT( | 515 CSA_ASSERT( |
413 this, | 516 this, |
414 UintPtrLessThan( | 517 UintPtrLessThan( |
415 var_entry.value(), | 518 var_entry.value(), |
416 SmiUntag(SmiAdd( | 519 SmiUntag(SmiAdd( |
417 LoadFixedArrayElement(table, | 520 LoadFixedArrayElement(table, |
418 OrderedHashMap::kNumberOfElementsIndex), | 521 OrderedHashMap::kNumberOfElementsIndex), |
419 LoadFixedArrayElement( | 522 LoadFixedArrayElement( |
420 table, OrderedHashMap::kNumberOfDeletedElementsIndex))))); | 523 table, OrderedHashMap::kNumberOfDeletedElementsIndex))))); |
421 | 524 |
422 // Compute the index of the entry relative to kHashTableStartIndex. | 525 // Compute the index of the entry relative to kHashTableStartIndex. |
423 entry_start_position = | 526 Node* entry_start = |
424 IntPtrAdd(IntPtrMul(var_entry.value(), | 527 IntPtrAdd(IntPtrMul(var_entry.value(), |
425 IntPtrConstant(OrderedHashMap::kEntrySize)), | 528 IntPtrConstant(OrderedHashMap::kEntrySize)), |
426 number_of_buckets); | 529 number_of_buckets); |
530 entry_start_position->Bind(entry_start); | |
427 | 531 |
428 // Load the key from the entry. | 532 // Load the key from the entry. |
429 Node* const candidate_key = LoadFixedArrayElement( | 533 Node* const candidate_key = LoadFixedArrayElement( |
430 table, entry_start_position, | 534 table, entry_start, |
431 OrderedHashMap::kHashTableStartIndex * kPointerSize); | 535 OrderedHashMap::kHashTableStartIndex * kPointerSize); |
432 | 536 |
433 // If the key is the same, we are done. | 537 key_compare(candidate_key, entry_found, &continue_next_entry); |
434 GotoIf(WordEqual(candidate_key, key_tagged), entry_found); | |
435 | |
436 // If the candidate key is smi, then it must be different (because | |
437 // we already checked for equality above). | |
438 GotoIf(TaggedIsSmi(candidate_key), &continue_next_entry); | |
439 | |
440 // If the candidate key is not smi, we still have to check if it is a heap | |
441 // number with the same value. | |
442 GotoIfNot(IsHeapNumber(candidate_key), &continue_next_entry); | |
443 | |
444 Node* const candidate_key_number = LoadHeapNumberValue(candidate_key); | |
445 Node* const key_number = SmiToFloat64(key_tagged); | |
446 | |
447 GotoIf(Float64Equal(candidate_key_number, key_number), entry_found); | |
448 | |
449 Goto(&continue_next_entry); | |
450 | 538 |
451 BIND(&continue_next_entry); | 539 BIND(&continue_next_entry); |
452 // Load the index of the next entry in the bucket chain. | 540 // Load the index of the next entry in the bucket chain. |
453 var_entry.Bind(SmiUntag(LoadFixedArrayElement( | 541 var_entry.Bind(SmiUntag(LoadFixedArrayElement( |
454 table, entry_start_position, | 542 table, entry_start, |
455 (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kChainOffset) * | 543 (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kChainOffset) * |
456 kPointerSize))); | 544 kPointerSize))); |
457 | 545 |
458 Goto(&loop); | 546 Goto(&loop); |
459 } | 547 } |
460 return entry_start_position; | |
461 } | 548 } |
462 | 549 |
463 TF_BUILTIN(MapGet, CollectionsBuiltinsAssembler) { | 550 TF_BUILTIN(MapGet, CollectionsBuiltinsAssembler) { |
464 Node* const receiver = Parameter(Descriptor::kReceiver); | 551 Node* const receiver = Parameter(Descriptor::kReceiver); |
465 Node* const key_tagged = Parameter(Descriptor::kKey); | 552 Node* const key_tagged = Parameter(Descriptor::kKey); |
466 Node* const context = Parameter(Descriptor::kContext); | 553 Node* const context = Parameter(Descriptor::kContext); |
467 | 554 |
468 ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get"); | 555 ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get"); |
469 | 556 |
470 Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); | 557 Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); |
471 | 558 |
472 Label if_key_smi(this); | 559 VARIABLE(entry_start_position, MachineType::PointerRepresentation(), |
560 IntPtrConstant(0)); | |
561 Label if_key_smi(this), if_key_string(this); | |
473 GotoIf(TaggedIsSmi(key_tagged), &if_key_smi); | 562 GotoIf(TaggedIsSmi(key_tagged), &if_key_smi); |
563 GotoIf(IsString(key_tagged), &if_key_string); | |
474 | 564 |
475 Return(CallGetRaw(table, key_tagged)); | 565 Return(CallGetRaw(table, key_tagged)); |
476 | 566 |
477 BIND(&if_key_smi); | 567 BIND(&if_key_smi); |
478 Label entry_found(this), not_found(this); | 568 Label entry_found(this, &entry_start_position), not_found(this); |
479 Node* entry_start_position = FindOrderedHashMapEntryForSmiKey( | 569 FindOrderedHashMapEntryForSmiKey(table, key_tagged, &entry_found, |
480 table, key_tagged, &entry_found, ¬_found); | 570 &entry_start_position, ¬_found); |
571 | |
572 BIND(&if_key_string); | |
573 FindOrderedHashMapEntryForStringKey(context, table, key_tagged, &entry_found, | |
574 &entry_start_position, ¬_found); | |
481 | 575 |
482 BIND(&entry_found); | 576 BIND(&entry_found); |
483 Return(LoadFixedArrayElement( | 577 Return(LoadFixedArrayElement( |
484 table, entry_start_position, | 578 table, entry_start_position.value(), |
485 (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) * | 579 (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) * |
486 kPointerSize)); | 580 kPointerSize)); |
487 | 581 |
488 BIND(¬_found); | 582 BIND(¬_found); |
489 Return(UndefinedConstant()); | 583 Return(UndefinedConstant()); |
490 } | 584 } |
491 | 585 |
492 TF_BUILTIN(MapHas, CollectionsBuiltinsAssembler) { | 586 TF_BUILTIN(MapHas, CollectionsBuiltinsAssembler) { |
493 Node* const receiver = Parameter(Descriptor::kReceiver); | 587 Node* const receiver = Parameter(Descriptor::kReceiver); |
494 Node* const key_tagged = Parameter(Descriptor::kKey); | 588 Node* const key_tagged = Parameter(Descriptor::kKey); |
495 Node* const context = Parameter(Descriptor::kContext); | 589 Node* const context = Parameter(Descriptor::kContext); |
496 | 590 |
497 ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has"); | 591 ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has"); |
498 | 592 |
499 Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); | 593 Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); |
500 | 594 |
501 Label if_key_smi(this); | 595 VARIABLE(entry_start_position, MachineType::PointerRepresentation(), |
596 IntPtrConstant(0)); | |
597 Label if_key_smi(this), if_key_string(this); | |
502 GotoIf(TaggedIsSmi(key_tagged), &if_key_smi); | 598 GotoIf(TaggedIsSmi(key_tagged), &if_key_smi); |
599 GotoIf(IsString(key_tagged), &if_key_string); | |
503 | 600 |
504 Return(CallHasRaw<OrderedHashMap, 2>(table, key_tagged)); | 601 Return(CallHasRaw<OrderedHashMap, 2>(table, key_tagged)); |
505 | 602 |
506 BIND(&if_key_smi); | 603 BIND(&if_key_smi); |
507 Label entry_found(this), not_found(this); | 604 Label entry_found(this), not_found(this); |
508 FindOrderedHashMapEntryForSmiKey(table, key_tagged, &entry_found, ¬_found); | 605 FindOrderedHashMapEntryForSmiKey(table, key_tagged, &entry_found, |
606 &entry_start_position, ¬_found); | |
607 | |
608 BIND(&if_key_string); | |
609 FindOrderedHashMapEntryForStringKey(context, table, key_tagged, &entry_found, | |
610 &entry_start_position, ¬_found); | |
509 | 611 |
510 BIND(&entry_found); | 612 BIND(&entry_found); |
511 Return(TrueConstant()); | 613 Return(TrueConstant()); |
512 | 614 |
513 BIND(¬_found); | 615 BIND(¬_found); |
514 Return(FalseConstant()); | 616 Return(FalseConstant()); |
515 } | 617 } |
516 | 618 |
517 TF_BUILTIN(SetHas, CollectionsBuiltinsAssembler) { | 619 TF_BUILTIN(SetHas, CollectionsBuiltinsAssembler) { |
518 Node* const receiver = Parameter(Descriptor::kReceiver); | 620 Node* const receiver = Parameter(Descriptor::kReceiver); |
519 Node* const key = Parameter(Descriptor::kKey); | 621 Node* const key = Parameter(Descriptor::kKey); |
520 Node* const context = Parameter(Descriptor::kContext); | 622 Node* const context = Parameter(Descriptor::kContext); |
521 | 623 |
522 ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has"); | 624 ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has"); |
523 | 625 |
524 Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); | 626 Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); |
525 Return(CallHasRaw<OrderedHashSet, 1>(table, key)); | 627 Return(CallHasRaw<OrderedHashSet, 1>(table, key)); |
526 } | 628 } |
527 | 629 |
528 } // namespace internal | 630 } // namespace internal |
529 } // namespace v8 | 631 } // namespace v8 |
OLD | NEW |