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