deps/v8/src/type-info.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/v8.h"
   6
   7 #include "src/ast.h"
   8 #include "src/code-stubs.h"
   9 #include "src/compiler.h"
  10 #include "src/ic/ic.h"
  11 #include "src/ic/stub-cache.h"
  12 #include "src/type-info.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16
  17
  18 TypeFeedbackOracle::TypeFeedbackOracle(
  19     Isolate* isolate, Zone* zone, Handle<Code> code,
  20     Handle<TypeFeedbackVector> feedback_vector, Handle<Context> native_context)
  21     : native_context_(native_context), isolate_(isolate), zone_(zone) {
  22   BuildDictionary(code);
  23   DCHECK(dictionary_->IsDictionary());
  24   // We make a copy of the feedback vector because a GC could clear
  25   // the type feedback info contained therein.
  26   // TODO(mvstanton): revisit the decision to copy when we weakly
  27   // traverse the feedback vector at GC time.
  28   feedback_vector_ = TypeFeedbackVector::Copy(isolate, feedback_vector);
  29 }
  30
  31
  32 static uint32_t IdToKey(TypeFeedbackId ast_id) {
  33   return static_cast<uint32_t>(ast_id.ToInt());
  34 }
  35
  36
  37 Handle<Object> TypeFeedbackOracle::GetInfo(TypeFeedbackId ast_id) {
  38   int entry = dictionary_->FindEntry(IdToKey(ast_id));
  39   if (entry != UnseededNumberDictionary::kNotFound) {
  40     Object* value = dictionary_->ValueAt(entry);
  41     if (value->IsCell()) {
  42       Cell* cell = Cell::cast(value);
  43       return Handle<Object>(cell->value(), isolate());
  44     } else {
  45       return Handle<Object>(value, isolate());
  46     }
  47   }
  48   return Handle<Object>::cast(isolate()->factory()->undefined_value());
  49 }
  50
  51
  52 Handle<Object> TypeFeedbackOracle::GetInfo(FeedbackVectorSlot slot) {
  53   DCHECK(slot.ToInt() >= 0 && slot.ToInt() < feedback_vector_->length());
  54   Object* obj = feedback_vector_->Get(slot);
  55   if (!obj->IsJSFunction() ||
  56       !CanRetainOtherContext(JSFunction::cast(obj), *native_context_)) {
  57     return Handle<Object>(obj, isolate());
  58   }
  59   return Handle<Object>::cast(isolate()->factory()->undefined_value());
  60 }
  61
  62
  63 Handle<Object> TypeFeedbackOracle::GetInfo(FeedbackVectorICSlot slot) {
  64   DCHECK(slot.ToInt() >= 0 && slot.ToInt() < feedback_vector_->length());
  65   Handle<Object> undefined =
  66       Handle<Object>::cast(isolate()->factory()->undefined_value());
  67   Object* obj = feedback_vector_->Get(slot);
  68
  69   // Vector-based ICs do not embed direct pointers to maps, functions.
  70   // Instead a WeakCell is always used.
  71   if (obj->IsWeakCell()) {
  72     WeakCell* cell = WeakCell::cast(obj);
  73     if (cell->cleared()) return undefined;
  74     obj = cell->value();
  75   }
  76
  77   if (!obj->IsJSFunction() ||
  78       !CanRetainOtherContext(JSFunction::cast(obj), *native_context_)) {
  79     return Handle<Object>(obj, isolate());
  80   }
  81   return undefined;
  82 }
  83
  84
  85 bool TypeFeedbackOracle::LoadIsUninitialized(TypeFeedbackId id) {
  86   Handle<Object> maybe_code = GetInfo(id);
  87   if (maybe_code->IsCode()) {
  88     Handle<Code> code = Handle<Code>::cast(maybe_code);
  89     return code->is_inline_cache_stub() && code->ic_state() == UNINITIALIZED;
  90   }
  91   return false;
  92 }
  93
  94
  95 bool TypeFeedbackOracle::LoadIsUninitialized(FeedbackVectorICSlot slot) {
  96   Code::Kind kind = feedback_vector_->GetKind(slot);
  97   if (kind == Code::LOAD_IC) {
  98     LoadICNexus nexus(feedback_vector_, slot);
  99     return nexus.StateFromFeedback() == UNINITIALIZED;
 100   } else if (kind == Code::KEYED_LOAD_IC) {
 101     KeyedLoadICNexus nexus(feedback_vector_, slot);
 102     return nexus.StateFromFeedback() == UNINITIALIZED;
 103   } else if (kind == Code::NUMBER_OF_KINDS) {
 104     // Code::NUMBER_OF_KINDS indicates a slot that was never even compiled
 105     // in full code.
 106     return true;
 107   }
 108
 109   return false;
 110 }
 111
 112
 113 bool TypeFeedbackOracle::StoreIsUninitialized(TypeFeedbackId ast_id) {
 114   Handle<Object> maybe_code = GetInfo(ast_id);
 115   if (!maybe_code->IsCode()) return false;
 116   Handle<Code> code = Handle<Code>::cast(maybe_code);
 117   return code->ic_state() == UNINITIALIZED;
 118 }
 119
 120
 121 bool TypeFeedbackOracle::CallIsUninitialized(FeedbackVectorICSlot slot) {
 122   Handle<Object> value = GetInfo(slot);
 123   return value->IsUndefined() ||
 124          value.is_identical_to(
 125              TypeFeedbackVector::UninitializedSentinel(isolate()));
 126 }
 127
 128
 129 bool TypeFeedbackOracle::CallIsMonomorphic(FeedbackVectorICSlot slot) {
 130   Handle<Object> value = GetInfo(slot);
 131   return value->IsAllocationSite() || value->IsJSFunction();
 132 }
 133
 134
 135 bool TypeFeedbackOracle::CallNewIsMonomorphic(FeedbackVectorSlot slot) {
 136   Handle<Object> info = GetInfo(slot);
 137   return FLAG_pretenuring_call_new
 138       ? info->IsJSFunction()
 139       : info->IsAllocationSite() || info->IsJSFunction();
 140 }
 141
 142
 143 byte TypeFeedbackOracle::ForInType(FeedbackVectorSlot feedback_vector_slot) {
 144   Handle<Object> value = GetInfo(feedback_vector_slot);
 145   return value.is_identical_to(
 146              TypeFeedbackVector::UninitializedSentinel(isolate()))
 147              ? ForInStatement::FAST_FOR_IN
 148              : ForInStatement::SLOW_FOR_IN;
 149 }
 150
 151
 152 void TypeFeedbackOracle::GetStoreModeAndKeyType(
 153     TypeFeedbackId ast_id, KeyedAccessStoreMode* store_mode,
 154     IcCheckType* key_type) {
 155   Handle<Object> maybe_code = GetInfo(ast_id);
 156   if (maybe_code->IsCode()) {
 157     Handle<Code> code = Handle<Code>::cast(maybe_code);
 158     if (code->kind() == Code::KEYED_STORE_IC) {
 159       ExtraICState extra_ic_state = code->extra_ic_state();
 160       *store_mode = KeyedStoreIC::GetKeyedAccessStoreMode(extra_ic_state);
 161       *key_type = KeyedStoreIC::GetKeyType(extra_ic_state);
 162       return;
 163     }
 164   }
 165   *store_mode = STANDARD_STORE;
 166   *key_type = ELEMENT;
 167 }
 168
 169
 170 void TypeFeedbackOracle::GetLoadKeyType(
 171     TypeFeedbackId ast_id, IcCheckType* key_type) {
 172   Handle<Object> maybe_code = GetInfo(ast_id);
 173   if (maybe_code->IsCode()) {
 174     Handle<Code> code = Handle<Code>::cast(maybe_code);
 175     if (code->kind() == Code::KEYED_LOAD_IC) {
 176       ExtraICState extra_ic_state = code->extra_ic_state();
 177       *key_type = KeyedLoadIC::GetKeyType(extra_ic_state);
 178       return;
 179     }
 180   }
 181   *key_type = ELEMENT;
 182 }
 183
 184
 185 Handle<JSFunction> TypeFeedbackOracle::GetCallTarget(
 186     FeedbackVectorICSlot slot) {
 187   Handle<Object> info = GetInfo(slot);
 188   if (info->IsAllocationSite()) {
 189     return Handle<JSFunction>(isolate()->native_context()->array_function());
 190   }
 191
 192   return Handle<JSFunction>::cast(info);
 193 }
 194
 195
 196 Handle<JSFunction> TypeFeedbackOracle::GetCallNewTarget(
 197     FeedbackVectorSlot slot) {
 198   Handle<Object> info = GetInfo(slot);
 199   if (FLAG_pretenuring_call_new || info->IsJSFunction()) {
 200     return Handle<JSFunction>::cast(info);
 201   }
 202
 203   DCHECK(info->IsAllocationSite());
 204   return Handle<JSFunction>(isolate()->native_context()->array_function());
 205 }
 206
 207
 208 Handle<AllocationSite> TypeFeedbackOracle::GetCallAllocationSite(
 209     FeedbackVectorICSlot slot) {
 210   Handle<Object> info = GetInfo(slot);
 211   if (info->IsAllocationSite()) {
 212     return Handle<AllocationSite>::cast(info);
 213   }
 214   return Handle<AllocationSite>::null();
 215 }
 216
 217
 218 Handle<AllocationSite> TypeFeedbackOracle::GetCallNewAllocationSite(
 219     FeedbackVectorSlot slot) {
 220   Handle<Object> info = GetInfo(slot);
 221   if (FLAG_pretenuring_call_new || info->IsAllocationSite()) {
 222     return Handle<AllocationSite>::cast(info);
 223   }
 224   return Handle<AllocationSite>::null();
 225 }
 226
 227
 228 bool TypeFeedbackOracle::LoadIsBuiltin(
 229     TypeFeedbackId id, Builtins::Name builtin) {
 230   return *GetInfo(id) == isolate()->builtins()->builtin(builtin);
 231 }
 232
 233
 234 void TypeFeedbackOracle::CompareType(TypeFeedbackId id,
 235                                      Type** left_type,
 236                                      Type** right_type,
 237                                      Type** combined_type) {
 238   Handle<Object> info = GetInfo(id);
 239   if (!info->IsCode()) {
 240     // For some comparisons we don't have ICs, e.g. LiteralCompareTypeof.
 241     *left_type = *right_type = *combined_type = Type::None(zone());
 242     return;
 243   }
 244   Handle<Code> code = Handle<Code>::cast(info);
 245
 246   Handle<Map> map;
 247   Map* raw_map = code->FindFirstMap();
 248   if (raw_map != NULL) {
 249     if (Map::TryUpdate(handle(raw_map)).ToHandle(&map) &&
 250         CanRetainOtherContext(*map, *native_context_)) {
 251       map = Handle<Map>::null();
 252     }
 253   }
 254
 255   if (code->is_compare_ic_stub()) {
 256     CompareICStub stub(code->stub_key(), isolate());
 257     *left_type = CompareICState::StateToType(zone(), stub.left());
 258     *right_type = CompareICState::StateToType(zone(), stub.right());
 259     *combined_type = CompareICState::StateToType(zone(), stub.state(), map);
 260   } else if (code->is_compare_nil_ic_stub()) {
 261     CompareNilICStub stub(isolate(), code->extra_ic_state());
 262     *combined_type = stub.GetType(zone(), map);
 263     *left_type = *right_type = stub.GetInputType(zone(), map);
 264   }
 265 }
 266
 267
 268 void TypeFeedbackOracle::BinaryType(TypeFeedbackId id,
 269                                     Type** left,
 270                                     Type** right,
 271                                     Type** result,
 272                                     Maybe<int>* fixed_right_arg,
 273                                     Handle<AllocationSite>* allocation_site,
 274                                     Token::Value op) {
 275   Handle<Object> object = GetInfo(id);
 276   if (!object->IsCode()) {
 277     // For some binary ops we don't have ICs, e.g. Token::COMMA, but for the
 278     // operations covered by the BinaryOpIC we should always have them.
 279     DCHECK(op < BinaryOpICState::FIRST_TOKEN ||
 280            op > BinaryOpICState::LAST_TOKEN);
 281     *left = *right = *result = Type::None(zone());
 282     *fixed_right_arg = Maybe<int>();
 283     *allocation_site = Handle<AllocationSite>::null();
 284     return;
 285   }
 286   Handle<Code> code = Handle<Code>::cast(object);
 287   DCHECK_EQ(Code::BINARY_OP_IC, code->kind());
 288   BinaryOpICState state(isolate(), code->extra_ic_state());
 289   DCHECK_EQ(op, state.op());
 290
 291   *left = state.GetLeftType(zone());
 292   *right = state.GetRightType(zone());
 293   *result = state.GetResultType(zone());
 294   *fixed_right_arg = state.fixed_right_arg();
 295
 296   AllocationSite* first_allocation_site = code->FindFirstAllocationSite();
 297   if (first_allocation_site != NULL) {
 298     *allocation_site = handle(first_allocation_site);
 299   } else {
 300     *allocation_site = Handle<AllocationSite>::null();
 301   }
 302 }
 303
 304
 305 Type* TypeFeedbackOracle::CountType(TypeFeedbackId id) {
 306   Handle<Object> object = GetInfo(id);
 307   if (!object->IsCode()) return Type::None(zone());
 308   Handle<Code> code = Handle<Code>::cast(object);
 309   DCHECK_EQ(Code::BINARY_OP_IC, code->kind());
 310   BinaryOpICState state(isolate(), code->extra_ic_state());
 311   return state.GetLeftType(zone());
 312 }
 313
 314
 315 void TypeFeedbackOracle::PropertyReceiverTypes(TypeFeedbackId id,
 316                                                Handle<String> name,
 317                                                SmallMapList* receiver_types) {
 318   receiver_types->Clear();
 319   Code::Flags flags = Code::ComputeHandlerFlags(Code::LOAD_IC);
 320   CollectReceiverTypes(id, name, flags, receiver_types);
 321 }
 322
 323
 324 bool TypeFeedbackOracle::HasOnlyStringMaps(SmallMapList* receiver_types) {
 325   bool all_strings = receiver_types->length() > 0;
 326   for (int i = 0; i < receiver_types->length(); i++) {
 327     all_strings &= receiver_types->at(i)->IsStringMap();
 328   }
 329   return all_strings;
 330 }
 331
 332
 333 void TypeFeedbackOracle::KeyedPropertyReceiverTypes(
 334     TypeFeedbackId id,
 335     SmallMapList* receiver_types,
 336     bool* is_string,
 337     IcCheckType* key_type) {
 338   receiver_types->Clear();
 339   CollectReceiverTypes(id, receiver_types);
 340   *is_string = HasOnlyStringMaps(receiver_types);
 341   GetLoadKeyType(id, key_type);
 342 }
 343
 344
 345 void TypeFeedbackOracle::PropertyReceiverTypes(FeedbackVectorICSlot slot,
 346                                                Handle<String> name,
 347                                                SmallMapList* receiver_types) {
 348   receiver_types->Clear();
 349   LoadICNexus nexus(feedback_vector_, slot);
 350   Code::Flags flags = Code::ComputeHandlerFlags(Code::LOAD_IC);
 351   CollectReceiverTypes(&nexus, name, flags, receiver_types);
 352 }
 353
 354
 355 void TypeFeedbackOracle::KeyedPropertyReceiverTypes(
 356     FeedbackVectorICSlot slot, SmallMapList* receiver_types, bool* is_string,
 357     IcCheckType* key_type) {
 358   receiver_types->Clear();
 359   KeyedLoadICNexus nexus(feedback_vector_, slot);
 360   CollectReceiverTypes<FeedbackNexus>(&nexus, receiver_types);
 361   *is_string = HasOnlyStringMaps(receiver_types);
 362   *key_type = nexus.FindFirstName() != NULL ? PROPERTY : ELEMENT;
 363 }
 364
 365
 366 void TypeFeedbackOracle::AssignmentReceiverTypes(
 367     TypeFeedbackId id, Handle<String> name, SmallMapList* receiver_types) {
 368   receiver_types->Clear();
 369   Code::Flags flags = Code::ComputeHandlerFlags(Code::STORE_IC);
 370   CollectReceiverTypes(id, name, flags, receiver_types);
 371 }
 372
 373
 374 void TypeFeedbackOracle::KeyedAssignmentReceiverTypes(
 375     TypeFeedbackId id, SmallMapList* receiver_types,
 376     KeyedAccessStoreMode* store_mode, IcCheckType* key_type) {
 377   receiver_types->Clear();
 378   CollectReceiverTypes(id, receiver_types);
 379   GetStoreModeAndKeyType(id, store_mode, key_type);
 380 }
 381
 382
 383 void TypeFeedbackOracle::CountReceiverTypes(TypeFeedbackId id,
 384                                             SmallMapList* receiver_types) {
 385   receiver_types->Clear();
 386   CollectReceiverTypes(id, receiver_types);
 387 }
 388
 389
 390 void TypeFeedbackOracle::CollectReceiverTypes(TypeFeedbackId ast_id,
 391                                               Handle<String> name,
 392                                               Code::Flags flags,
 393                                               SmallMapList* types) {
 394   Handle<Object> object = GetInfo(ast_id);
 395   if (object->IsUndefined() || object->IsSmi()) return;
 396
 397   DCHECK(object->IsCode());
 398   Handle<Code> code(Handle<Code>::cast(object));
 399   CollectReceiverTypes<Code>(*code, name, flags, types);
 400 }
 401
 402
 403 template <class T>
 404 void TypeFeedbackOracle::CollectReceiverTypes(T* obj, Handle<String> name,
 405                                               Code::Flags flags,
 406                                               SmallMapList* types) {
 407   if (FLAG_collect_megamorphic_maps_from_stub_cache &&
 408       obj->ic_state() == MEGAMORPHIC) {
 409     types->Reserve(4, zone());
 410     isolate()->stub_cache()->CollectMatchingMaps(
 411         types, name, flags, native_context_, zone());
 412   } else {
 413     CollectReceiverTypes<T>(obj, types);
 414   }
 415 }
 416
 417
 418 // Check if a map originates from a given native context. We use this
 419 // information to filter out maps from different context to avoid
 420 // retaining objects from different tabs in Chrome via optimized code.
 421 bool TypeFeedbackOracle::CanRetainOtherContext(Map* map,
 422                                                Context* native_context) {
 423   Object* constructor = NULL;
 424   while (!map->prototype()->IsNull()) {
 425     constructor = map->constructor();
 426     if (!constructor->IsNull()) {
 427       // If the constructor is not null or a JSFunction, we have to
 428       // conservatively assume that it may retain a native context.
 429       if (!constructor->IsJSFunction()) return true;
 430       // Check if the constructor directly references a foreign context.
 431       if (CanRetainOtherContext(JSFunction::cast(constructor),
 432                                 native_context)) {
 433         return true;
 434       }
 435     }
 436     map = HeapObject::cast(map->prototype())->map();
 437   }
 438   constructor = map->constructor();
 439   if (constructor->IsNull()) return false;
 440   // If the constructor is not null or a JSFunction, we have to conservatively
 441   // assume that it may retain a native context.
 442   if (!constructor->IsJSFunction()) return true;
 443   JSFunction* function = JSFunction::cast(constructor);
 444   return CanRetainOtherContext(function, native_context);
 445 }
 446
 447
 448 bool TypeFeedbackOracle::CanRetainOtherContext(JSFunction* function,
 449                                                Context* native_context) {
 450   return function->context()->global_object() != native_context->global_object()
 451       && function->context()->global_object() != native_context->builtins();
 452 }
 453
 454
 455 void TypeFeedbackOracle::CollectReceiverTypes(TypeFeedbackId ast_id,
 456                                               SmallMapList* types) {
 457   Handle<Object> object = GetInfo(ast_id);
 458   if (!object->IsCode()) return;
 459   Handle<Code> code = Handle<Code>::cast(object);
 460   CollectReceiverTypes<Code>(*code, types);
 461 }
 462
 463
 464 template <class T>
 465 void TypeFeedbackOracle::CollectReceiverTypes(T* obj, SmallMapList* types) {
 466   MapHandleList maps;
 467   if (obj->ic_state() == MONOMORPHIC) {
 468     Map* map = obj->FindFirstMap();
 469     if (map != NULL) maps.Add(handle(map));
 470   } else if (obj->ic_state() == POLYMORPHIC) {
 471     obj->FindAllMaps(&maps);
 472   } else {
 473     return;
 474   }
 475   types->Reserve(maps.length(), zone());
 476   for (int i = 0; i < maps.length(); i++) {
 477     Handle<Map> map(maps.at(i));
 478     if (!CanRetainOtherContext(*map, *native_context_)) {
 479       types->AddMapIfMissing(map, zone());
 480     }
 481   }
 482 }
 483
 484
 485 byte TypeFeedbackOracle::ToBooleanTypes(TypeFeedbackId id) {
 486   Handle<Object> object = GetInfo(id);
 487   return object->IsCode() ? Handle<Code>::cast(object)->to_boolean_state() : 0;
 488 }
 489
 490
 491 // Things are a bit tricky here: The iterator for the RelocInfos and the infos
 492 // themselves are not GC-safe, so we first get all infos, then we create the
 493 // dictionary (possibly triggering GC), and finally we relocate the collected
 494 // infos before we process them.
 495 void TypeFeedbackOracle::BuildDictionary(Handle<Code> code) {
 496   DisallowHeapAllocation no_allocation;
 497   ZoneList<RelocInfo> infos(16, zone());
 498   HandleScope scope(isolate());
 499   GetRelocInfos(code, &infos);
 500   CreateDictionary(code, &infos);
 501   ProcessRelocInfos(&infos);
 502   // Allocate handle in the parent scope.
 503   dictionary_ = scope.CloseAndEscape(dictionary_);
 504 }
 505
 506
 507 void TypeFeedbackOracle::GetRelocInfos(Handle<Code> code,
 508                                        ZoneList<RelocInfo>* infos) {
 509   int mask = RelocInfo::ModeMask(RelocInfo::CODE_TARGET_WITH_ID);
 510   for (RelocIterator it(*code, mask); !it.done(); it.next()) {
 511     infos->Add(*it.rinfo(), zone());
 512   }
 513 }
 514
 515
 516 void TypeFeedbackOracle::CreateDictionary(Handle<Code> code,
 517                                           ZoneList<RelocInfo>* infos) {
 518   AllowHeapAllocation allocation_allowed;
 519   Code* old_code = *code;
 520   dictionary_ = UnseededNumberDictionary::New(isolate(), infos->length());
 521   RelocateRelocInfos(infos, old_code, *code);
 522 }
 523
 524
 525 void TypeFeedbackOracle::RelocateRelocInfos(ZoneList<RelocInfo>* infos,
 526                                             Code* old_code,
 527                                             Code* new_code) {
 528   for (int i = 0; i < infos->length(); i++) {
 529     RelocInfo* info = &(*infos)[i];
 530     info->set_host(new_code);
 531     info->set_pc(new_code->instruction_start() +
 532                  (info->pc() - old_code->instruction_start()));
 533   }
 534 }
 535
 536
 537 void TypeFeedbackOracle::ProcessRelocInfos(ZoneList<RelocInfo>* infos) {
 538   for (int i = 0; i < infos->length(); i++) {
 539     RelocInfo reloc_entry = (*infos)[i];
 540     Address target_address = reloc_entry.target_address();
 541     TypeFeedbackId ast_id =
 542         TypeFeedbackId(static_cast<unsigned>((*infos)[i].data()));
 543     Code* target = Code::GetCodeFromTargetAddress(target_address);
 544     switch (target->kind()) {
 545       case Code::LOAD_IC:
 546       case Code::STORE_IC:
 547       case Code::KEYED_LOAD_IC:
 548       case Code::KEYED_STORE_IC:
 549       case Code::BINARY_OP_IC:
 550       case Code::COMPARE_IC:
 551       case Code::TO_BOOLEAN_IC:
 552       case Code::COMPARE_NIL_IC:
 553         SetInfo(ast_id, target);
 554         break;
 555
 556       default:
 557         break;
 558     }
 559   }
 560 }
 561
 562
 563 void TypeFeedbackOracle::SetInfo(TypeFeedbackId ast_id, Object* target) {
 564   DCHECK(dictionary_->FindEntry(IdToKey(ast_id)) ==
 565          UnseededNumberDictionary::kNotFound);
 566   // Dictionary has been allocated with sufficient size for all elements.
 567   DisallowHeapAllocation no_need_to_resize_dictionary;
 568   HandleScope scope(isolate());
 569   USE(UnseededNumberDictionary::AtNumberPut(
 570       dictionary_, IdToKey(ast_id), handle(target, isolate())));
 571 }
 572
 573
 574 } }  // namespace v8::internal