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