Implement Object.prototype.hasOwnProperty in generated code.

src/ia32/code-stubs-ia32.cc

 // Copyright 2011 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 5507 matching lines @@
 void StringHelper::GenerateHashInit(MacroAssembler* masm,
                                     Register hash,
                                     Register character,
                                     Register scratch) {
   // hash = character + (character << 10);
   __ mov(hash, character);
   __ shl(hash, 10);
   __ add(hash, Operand(character));
   // hash ^= hash >> 6;
   __ mov(scratch, hash);
-  __ sar(scratch, 6);
+  __ shr(scratch, 6);

[Mads Ager (chromium), 2011/07/15 09:04:45]

This looks wrong? The >> operator in C++ is arithmetic so you might end up with
inconsistent hash values computed in C++ and in generated code which will be
bad. Same thing for the methods below. Maybe for some reason it is OK to use shr
here. I don't think we should - we should make sure that this matches the C++
code.

   __ xor_(hash, Operand(scratch));
 }
 
 
 void StringHelper::GenerateHashAddCharacter(MacroAssembler* masm,
                                             Register hash,
                                             Register character,
                                             Register scratch) {
   // hash += character;
   __ add(hash, Operand(character));
   // hash += hash << 10;
   __ mov(scratch, hash);
   __ shl(scratch, 10);
   __ add(hash, Operand(scratch));
   // hash ^= hash >> 6;
   __ mov(scratch, hash);
-  __ sar(scratch, 6);
+  __ shr(scratch, 6);
   __ xor_(hash, Operand(scratch));
 }
 
 
 void StringHelper::GenerateHashGetHash(MacroAssembler* masm,
                                        Register hash,
                                        Register scratch) {
   // hash += hash << 3;
   __ mov(scratch, hash);
   __ shl(scratch, 3);
   __ add(hash, Operand(scratch));
   // hash ^= hash >> 11;
   __ mov(scratch, hash);
-  __ sar(scratch, 11);
+  __ shr(scratch, 11);
   __ xor_(hash, Operand(scratch));
   // hash += hash << 15;
   __ mov(scratch, hash);
   __ shl(scratch, 15);
   __ add(hash, Operand(scratch));
 
   // if (hash == 0) hash = 27;
   Label hash_not_zero;
   __ test(hash, Operand(hash));
   __ j(not_zero, &hash_not_zero, Label::kNear);
@@ skipping 177 matching lines @@
   __ bind(&compare_chars);
   GenerateAsciiCharsCompareLoop(masm, left, right, length, scratch2,
                                 &strings_not_equal, Label::kNear);
 
   // Characters are equal.
   __ Set(eax, Immediate(Smi::FromInt(EQUAL)));
   __ ret(0);
 }
 
 
+void StringCompareStub::GenerateFlatAsciiStringEquals(
+    MacroAssembler* masm,
+    Register left,
+    Register right,
+    Register scratch1,
+    Register scratch2,
+    Label* strings_not_equal) {
+  Register length = scratch1;
+
+  // Compare lengths.
+  __ mov(length, FieldOperand(left, String::kLengthOffset));
+  __ cmp(length, FieldOperand(right, String::kLengthOffset));
+  __ j(not_equal, strings_not_equal);
+
+  // Check if the length is zero.
+  Label strings_equal;
+  STATIC_ASSERT(kSmiTag == 0);
+  __ test(length, Operand(length));
+  __ j(zero, &strings_equal, Label::kNear);
+
+  // Compare characters.
+  GenerateAsciiCharsCompareLoop(masm, left, right, length, scratch2,
+                                strings_not_equal, Label::kNear);
+
+  // Characters are equal.
+  __ bind(&strings_equal);
+}
+
+
 void StringCompareStub::GenerateCompareFlatAsciiStrings(MacroAssembler* masm,
                                                         Register left,
                                                         Register right,
                                                         Register scratch1,
                                                         Register scratch2,
                                                         Register scratch3) {
   Counters* counters = masm->isolate()->counters();
   __ IncrementCounter(counters->string_compare_native(), 1);
 
   // Find minimum length.
@@ skipping 484 matching lines @@
   __ shr(r0, String::kHashShift);
   __ push(r0);
   __ CallStub(&stub);
 
   __ test(r1, Operand(r1));
   __ j(zero, miss);
   __ jmp(done);
 }
 
 
+void StringDictionaryLookupStub::GenerateLookupWithComparisons(
+    MacroAssembler* masm,
+    Register dictionary,
+    Register name,
+    Register scratch1,
+    Register scratch2,
+    Register scratch3,
+    Label* found_in_dictionary,
+    Label* not_found_in_dictionary,
+    Label* call_runtime) {
+  // Check whether the name is an ASCII symbol or an ASCII string.
+  // Other types are not supported.
+  Label name_is_symbol;
+  __ mov(scratch1, FieldOperand(name, HeapObject::kMapOffset));
+  __ cmp(scratch1, masm->isolate()->factory()->ascii_symbol_map());
+  __ j(equal, &name_is_symbol);
+  __ cmp(scratch1, masm->isolate()->factory()->ascii_string_map());
+  __ j(not_equal, call_runtime);
+
+  // If the name is an ASCII string, it might not yet have its hash
+  // code computed.
+  Label name_has_hash_code;
+  __ cmp(FieldOperand(name, String::kHashFieldOffset),
+         Immediate(String::kEmptyHashField));
+  __ j(not_equal, &name_has_hash_code);
+
+  // Load the string length and check it's not zero and not too big.
+  __ mov(scratch1, FieldOperand(name, String::kLengthOffset));
+  __ SmiUntag(scratch1);
+  __ test(scratch1, Operand(scratch1));
+  __ j(zero, call_runtime);
+  __ cmp(scratch1, String::kMaxHashCalcLength);
+  __ j(greater, call_runtime);
+
+  // Load the first char and check it's not numeric. Numeric strings
+  // have a different hashing algorithm.
+  Label not_an_array_index;
+  Register character = scratch2;
+  __ movzx_b(character, FieldOperand(name, SeqAsciiString::kHeaderSize));
+  __ cmp(character, '9');
+  __ j(greater, &not_an_array_index, Label::kNear);
+  __ cmp(character, '0');
+  __ j(greater_equal, call_runtime);
+  __ bind(&not_an_array_index);
+
+  // Save the dictionary and the string length on the stack to free up
+  // registers.
+  __ push(dictionary);
+  Operand length = Operand(esp, 0);
+  __ push(scratch1);
+
+  // Hash the first (already loaded) char.
+  Register index = scratch1;
+  __ Set(index, Immediate(0));
+  Register hash = dictionary;
+  StringHelper::GenerateHashInit(masm, hash, character, scratch3);
+
+  // Hash the rest in a loop.
+  Label hash_loop, hash_loop_done;
+  __ bind(&hash_loop);
+  __ add(Operand(index), Immediate(1));
+  __ cmp(index, length);
+  __ j(above_equal, &hash_loop_done, Label::kNear);
+  __ movzx_b(character, FieldOperand(name,
+                                     index, times_1,
+                                     SeqAsciiString::kHeaderSize));
+  StringHelper::GenerateHashAddCharacter(masm, hash, character, scratch3);
+  __ jmp(&hash_loop, Label::kNear);
+  __ bind(&hash_loop_done);
+
+  // Store the computed hash code in the name string.
+  StringHelper::GenerateHashGetHash(masm, hash, scratch3);
+  __ shl(hash, String::kHashShift);
+  __ or_(hash, String::kIsNotArrayIndexMask);
+  __ mov(FieldOperand(name, String::kHashFieldOffset), hash);
+  // Restore the stack state.
+  __ pop(dictionary);  // Drop TOS.
+  __ pop(dictionary);
+
+  __ bind(&name_has_hash_code);
+  GenerateUnrolledComparisons(masm,
+                              NAME_IS_ASCII_STRING_WITH_HASH,
+                              dictionary,
+                              name,
+                              scratch1,
+                              scratch2,
+                              scratch3,
+                              found_in_dictionary,
+                              not_found_in_dictionary,
+                              call_runtime);
+
+  __ bind(&name_is_symbol);
+  GenerateUnrolledComparisons(masm,
+                              NAME_IS_ASCII_SYMBOL,
+                              dictionary,
+                              name,
+                              scratch1,
+                              scratch2,
+                              scratch3,
+                              found_in_dictionary,
+                              not_found_in_dictionary,
+                              call_runtime);
+}
+
+
+void StringDictionaryLookupStub::GenerateUnrolledComparisons(
+    MacroAssembler* masm,
+    NameType name_type,
+    Register dictionary,
+    Register name,
+    Register scratch1,
+    Register scratch2,
+    Register scratch3,
+    Label* found_in_dictionary,
+    Label* not_found_in_dictionary,
+    Label* call_runtime) {
+  // Compute the mask.
+  Register mask = scratch1;
+  __ mov(mask, FieldOperand(dictionary, kCapacityOffset));
+  __ SmiUntag(mask);
+  __ dec(mask);
+
+  // Generate an unrolled loop that performs a few probes before
+  // giving up. Measurements done on Gmail indicate that 2 probes
+  // cover ~93% of loads from dictionaries.
+  for (int i = 0; i < kInlinedProbes; i++) {
+    Register index = scratch2;
+    Register candidate = scratch3;
+
+    Label next_probe;
+    // Compute the masked index: (hash + i + i * i) & mask.
+    __ mov(index, FieldOperand(name, String::kHashFieldOffset));
+    __ shr(index, String::kHashShift);
+    if (i > 0) {
+      __ add(Operand(index), Immediate(StringDictionary::GetProbeOffset(i)));
+    }
+    __ and_(index, Operand(mask));
+
+    // Scale the index by multiplying by the entry size.
+    ASSERT(StringDictionary::kEntrySize == 3);
+    __ lea(index, Operand(index, index, times_2, 0));  // index *= 3
+
+    // Load the entry.
+    __ mov(candidate, FieldOperand(dictionary,
+                                   index,
+                                   times_pointer_size,
+                                   kElementsStartOffset));
+
+    // Fast identity check.
+    __ cmp(name, Operand(candidate));
+    __ j(equal, found_in_dictionary);
+
+    // Check for the end of the hash chain.
+    __ cmp(candidate, masm->isolate()->factory()->undefined_value());
+    __ j(equal, not_found_in_dictionary);
+
+    // Check for the deleted entry marker.
+    __ cmp(candidate, masm->isolate()->factory()->null_value());
+    __ j(equal, &next_probe);
+
+    // Load the instance type of the candidate.
+    __ mov(scratch2, FieldOperand(candidate, HeapObject::kMapOffset));
+    __ movzx_b(scratch2, FieldOperand(scratch2, Map::kInstanceTypeOffset));
+    if (name_type == NAME_IS_ASCII_SYMBOL) {
+      // If both name and candidate are symbols, we can go to the next
+      // probe.
+      __ test_b(Operand(scratch2), kIsSymbolMask);
+      __ j(not_zero, &next_probe);
+      // Check if the candidate is a sequential ASCII string.
+      __ cmp(scratch2, static_cast<int32_t>(ASCII_STRING_TYPE));
+      __ j(not_equal, call_runtime);
+    } else {
+      ASSERT(name_type == NAME_IS_ASCII_STRING_WITH_HASH);
+      // Check if the candidate is a sequential ASCII string or symbol.
+      uint32_t candidate_mask =
+          kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask;
+      uint32_t expected =
+          kStringTag | kAsciiStringTag | kSeqStringTag;
+      __ and_(scratch2, static_cast<int32_t>(candidate_mask));
+      __ cmp(scratch2, static_cast<int32_t>(expected));
+      __ j(not_equal, call_runtime);
+    }
+
+    // Compare sequential ASCII strings.
+    Label strings_not_equal;
+    __ push(dictionary);
+    __ push(name);
+    StringCompareStub::GenerateFlatAsciiStringEquals(masm,
+                                                     name,
+                                                     candidate,
+                                                     scratch2,
+                                                     dictionary,
+                                                     &strings_not_equal);
+    __ pop(name);
+    __ pop(dictionary);
+    __ jmp(found_in_dictionary);
+    __ bind(&strings_not_equal);
+    __ pop(name);
+    __ pop(dictionary);
+
+    __ bind(&next_probe);
+  }
+  __ jmp(call_runtime);
+}
+
+
 void StringDictionaryLookupStub::Generate(MacroAssembler* masm) {
   // Stack frame on entry:
   //  esp[0 * kPointerSize]: return address.
   //  esp[1 * kPointerSize]: key's hash.
   //  esp[2 * kPointerSize]: key.
   // Registers:
   //  dictionary_: StringDictionary to probe.
   //  result_: used as scratch.
   //  index_: will hold an index of entry if lookup is successful.
   //          might alias with result_.
@@ skipping 68 matching lines @@
   __ Drop(1);
   __ ret(2 * kPointerSize);
 
   __ bind(&not_in_dictionary);
   __ mov(result_, Immediate(0));
   __ Drop(1);
   __ ret(2 * kPointerSize);
 }
 
 
+void HasOwnPropertyStub::Generate(MacroAssembler* masm) {
+  Register object = eax;
+  Register map = ebx;
+  Register name = ecx;
+  Register scratch1 = edx;
+  Register scratch2 = edi;
+  Label call_runtime;
+
+  // Load the arguments.
+  __ mov(object, Operand(esp, 2 * kPointerSize));
+  __ mov(name, Operand(esp, 1 * kPointerSize));
+
+  if (FLAG_debug_code) {
+    Label not_smi;
+    __ JumpIfNotSmi(name, &not_smi, Label::kNear);
+    __ Abort("HasOwnPropertyStub: name is a smi");
+    __ bind(&not_smi);
+    __ mov(scratch1, FieldOperand(name, HeapObject::kMapOffset));
+    __ test_b(FieldOperand(scratch1, Map::kInstanceTypeOffset),
+              kIsNotStringMask);
+    __ Assert(not_zero, "HasOwnPropertyStub: name is not a string");
+  }
+
+  // Make sure the object is a non-special JS object with no elements,
+  // interceptors, or hidden prototypes.
+  // TODO(vitalyr): access check?

[Mads Ager (chromium), 2011/07/15 09:04:45]

Yes, I'm pretty sure you need to exclude objects that require access checks as
well. If you should not have access to the object you should not be able to ask
is about which properties it has.

+  __ JumpIfSmi(object, &call_runtime);
+  __ mov(map, FieldOperand(object, HeapObject::kMapOffset));
+  __ CmpInstanceType(map, JS_OBJECT_TYPE);

[Mads Ager (chromium), 2011/07/15 09:04:45]

Do you want to be that restrictive? You don't want this to work for arrays and
global objects?

+  __ j(not_equal, &call_runtime);
+  __ cmp(FieldOperand(object, JSObject::kElementsOffset),
+         masm->isolate()->factory()->empty_fixed_array());
+  __ j(not_equal, &call_runtime);
+  __ test_b(FieldOperand(map, Map::kBitFieldOffset),
+            (1 << Map::kHasNamedInterceptor) |
+            (1 << Map::kHasIndexedInterceptor));
+  __ j(not_zero, &call_runtime);
+  __ mov(scratch1, FieldOperand(map, Map::kPrototypeOffset));
+  __ mov(scratch1, FieldOperand(scratch1, HeapObject::kMapOffset));
+  __ test_b(FieldOperand(scratch1, Map::kBitFieldOffset),

[Mads Ager (chromium), 2011/07/15 09:04:45]

You are disregarding objects with hidden prototypes because the prototype in
that case is considered part of the object, right? Can you add a comment about
that?

+            (1 << Map::kIsHiddenPrototype));
+  __ j(not_zero, &call_runtime);
+
+  // Does the object have fast properties?
+  Label slow_properties;
+  __ mov(scratch1, FieldOperand(object, JSObject::kPropertiesOffset));
+  __ cmp(FieldOperand(scratch1, HeapObject::kMapOffset),
+         masm->isolate()->factory()->fixed_array_map());
+  __ j(not_equal, &slow_properties);
+
+  // Handle fast properties.
+  GenerateFastPropertiesCase(masm,
+                             map,
+                             name,
+                             object,
+                             scratch1,
+                             scratch2,
+                             &call_runtime);
+

[Mads Ager (chromium), 2011/07/15 09:04:45]

Add an abort here so it is clear that there is no fall-through?

+  // Handle slow properties.
+  __ bind(&slow_properties);
+  GenerateSlowPropertiesCase(masm,
+                             object,
+                             name,
+                             map,
+                             scratch1,
+                             scratch2,
+                             &call_runtime);
+

[Mads Ager (chromium), 2011/07/15 09:04:45]

Ditto, add an abort?

+  __ bind(&call_runtime);
+  __ TailCallRuntime(Runtime::kHasOwnProperty, 2, 1);
+}
+
+
+void HasOwnPropertyStub::GenerateFastPropertiesCase(MacroAssembler* masm,
+                                                    Register map,
+                                                    Register name,
+                                                    Register scratch1,
+                                                    Register scratch2,
+                                                    Register scratch3,
+                                                    Label* call_runtime) {
+  // Load the descritor array from the map.
+  Register descriptor_array = map;
+  Label not_found_in_descriptors;
+  __ mov(descriptor_array,
+         FieldOperand(map, Map::kInstanceDescriptorsOrBitField3Offset));
+  map = no_reg;
+  __ JumpIfSmi(descriptor_array, &not_found_in_descriptors);
+
+  // Check the name is a symbol or a sequential ASCII string. We don't
+  // support comparison of other string types here.
+  Label name_is_not_symbol;
+  __ mov(scratch1, FieldOperand(name, HeapObject::kMapOffset));
+  __ movzx_b(scratch1, FieldOperand(scratch1, Map::kInstanceTypeOffset));
+  __ test_b(Operand(scratch1), kIsSymbolMask);
+  __ j(zero, &name_is_not_symbol);
+  GenerateDescriptorArrayLookup(masm,
+                                NAME_IS_SYMBOL,
+                                descriptor_array,
+                                name,
+                                scratch1,
+                                scratch2,
+                                scratch3,
+                                &not_found_in_descriptors,
+                                call_runtime);
+  __ bind(&name_is_not_symbol);
+  uint32_t mask = kStringRepresentationMask | kStringEncodingMask;
+  uint32_t expected = kSeqStringTag | kAsciiStringTag;
+  __ and_(scratch1, static_cast<int32_t>(mask));
+  __ cmp(scratch1, static_cast<int32_t>(expected));
+  __ j(not_equal, call_runtime);
+  GenerateDescriptorArrayLookup(masm,
+                                NAME_IS_SEQUENTIAL_ASCII,
+                                descriptor_array,
+                                name,
+                                scratch1,
+                                scratch2,
+                                scratch3,
+                                &not_found_in_descriptors,
+                                call_runtime);
+
+  // Did not find a descriptor corresponding to the given property
+  // name.
+  __ bind(&not_found_in_descriptors);
+  __ mov(eax, masm->isolate()->factory()->false_value());
+  __ ret(2);
+}
+
+
+void HasOwnPropertyStub::GenerateDescriptorArrayLookup(
+    MacroAssembler* masm,
+    NameType name_type,
+    Register descriptor_array,
+    Register name,
+    Register scratch1,
+    Register scratch2,
+    Register scratch3,
+    Label* not_found_in_descriptors,
+    Label* call_runtime) {
+  // Setup the lookup loop.
+  Register index = scratch1;
+  __ Set(index, Immediate(Smi::FromInt(DescriptorArray::kFirstIndex - 1)));
+  Operand length = FieldOperand(descriptor_array, FixedArray::kLengthOffset);
+
+  // Loop over the descriptor array keys. Both index and length are
+  // smi tagged.
+  Register candidate = scratch2;
+  Label loop, found_in_descriptors;
+  __ bind(&loop);
+  __ add(Operand(index), Immediate(Smi::FromInt(1)));
+  __ cmp(index, length);
+  __ j(greater_equal, not_found_in_descriptors);
+  STATIC_ASSERT(kSmiTag == 0 && kSmiTagSize == 1);
+  Operand candidate_operand = FieldOperand(descriptor_array,
+                                           index, times_half_pointer_size,
+                                           FixedArray::kHeaderSize);
+  if (name_type == NAME_IS_SYMBOL) {
+    // If the property name is a symbol, we can do a fast identity
+    // check only, because descriptor arrays always contain symbols.
+    __ cmp(name, candidate_operand);
+    __ j(not_equal, &loop, Label::kNear);
+  } else {
+    ASSERT(name_type == NAME_IS_SEQUENTIAL_ASCII);
+    // If the property name is a sequential ASCII string, check that
+    // the descriptor name is a sequential ASCII symbol.
+    Label strings_not_equal;
+    __ mov(candidate, candidate_operand);
+    __ cmp(FieldOperand(candidate, HeapObject::kMapOffset),
+           masm->isolate()->factory()->ascii_symbol_map());
+    __ j(not_equal, call_runtime);
+
+    // Compare name and candidate strings. We have to temporarily save
+    // registers on the stack.
+    __ push(name);
+    __ push(descriptor_array);
+    StringCompareStub::GenerateFlatAsciiStringEquals(masm,
+                                                     name,
+                                                     candidate,
+                                                     scratch3,
+                                                     descriptor_array,
+                                                     &strings_not_equal);
+    __ pop(descriptor_array);
+    __ pop(name);
+    __ jmp(&found_in_descriptors);
+    __ bind(&strings_not_equal);
+    __ pop(descriptor_array);
+    __ pop(name);
+    __ jmp(&loop);
+  }
+
+  // Found a descriptor corresponding to the given property
+  // name. Check the descriptor details to determine whether the
+  // property exists or not.
+  Register details = descriptor_array;
+  Label do_return;
+  __ bind(&found_in_descriptors);
+  __ SmiUntag(index);
+  __ sub(Operand(index), Immediate(DescriptorArray::kFirstIndex));
+  __ mov(details, FieldOperand(descriptor_array,
+                               DescriptorArray::kContentArrayOffset));
+  __ mov(details, FieldOperand(details,
+                               index, times_twice_pointer_size,
+                               FixedArray::kHeaderSize + kPointerSize));
+  __ SmiUntag(details);
+  __ and_(details, PropertyDetails::TypeField::mask());
+  __ cmp(details,
+         PropertyDetails::TypeField::encode(FIRST_PHANTOM_PROPERTY_TYPE));
+  __ mov(eax, masm->isolate()->factory()->true_value());
+  __ j(less, &do_return, Label::kNear);
+  __ mov(eax, masm->isolate()->factory()->false_value());
+  __ bind(&do_return);
+  __ ret(2);
+}
+
+
+void HasOwnPropertyStub::GenerateSlowPropertiesCase(MacroAssembler* masm,
+                                                    Register object,
+                                                    Register name,
+                                                    Register scratch1,
+                                                    Register scratch2,
+                                                    Register scratch3,
+                                                    Label* call_runtime) {
+  Label found_in_dictionary, not_found_in_dictionary;
+  Register dictionary = object;
+  __ mov(dictionary, FieldOperand(object, JSObject::kPropertiesOffset));
+  StringDictionaryLookupStub::GenerateLookupWithComparisons(
+      masm,
+      dictionary,
+      name,
+      scratch1,
+      scratch2,
+      scratch3,
+      &found_in_dictionary,
+      &not_found_in_dictionary,
+      call_runtime);
+
+  // Found a property with the given name in the property dictionary.
+  __ bind(&found_in_dictionary);
+  __ mov(eax, masm->isolate()->factory()->true_value());
+  __ ret(2);
+
+  // Not found a property with the given name in the property dictionary.
+  __ bind(&not_found_in_dictionary);
+  __ mov(eax, masm->isolate()->factory()->false_value());
+  __ ret(2);
+}
+
 #undef __
 
 } }  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_IA32