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