type-info.cc 19 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/type-info.h"
6

7 8 9
#include "src/ast.h"
#include "src/code-stubs.h"
#include "src/compiler.h"
10
#include "src/ic/ic.h"
11
#include "src/ic/stub-cache.h"
12
#include "src/objects-inl.h"
13

14 15 16 17
namespace v8 {
namespace internal {


18
TypeFeedbackOracle::TypeFeedbackOracle(
19 20 21
    Isolate* isolate, Zone* zone, Handle<Code> code,
    Handle<TypeFeedbackVector> feedback_vector, Handle<Context> native_context)
    : native_context_(native_context), isolate_(isolate), zone_(zone) {
22
  BuildDictionary(code);
23
  DCHECK(dictionary_->IsDictionary());
24 25 26 27
  // We make a copy of the feedback vector because a GC could clear
  // the type feedback info contained therein.
  // TODO(mvstanton): revisit the decision to copy when we weakly
  // traverse the feedback vector at GC time.
28
  feedback_vector_ = TypeFeedbackVector::Copy(isolate, feedback_vector);
29 30 31
}


32 33 34 35 36 37 38
static uint32_t IdToKey(TypeFeedbackId ast_id) {
  return static_cast<uint32_t>(ast_id.ToInt());
}


Handle<Object> TypeFeedbackOracle::GetInfo(TypeFeedbackId ast_id) {
  int entry = dictionary_->FindEntry(IdToKey(ast_id));
39 40
  if (entry != UnseededNumberDictionary::kNotFound) {
    Object* value = dictionary_->ValueAt(entry);
41 42
    if (value->IsCell()) {
      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 53
Handle<Object> TypeFeedbackOracle::GetInfo(FeedbackVectorSlot slot) {
  DCHECK(slot.ToInt() >= 0 && slot.ToInt() < feedback_vector_->length());
54 55
  Handle<Object> undefined =
      Handle<Object>::cast(isolate()->factory()->undefined_value());
56
  Object* obj = feedback_vector_->Get(slot);
57

58 59
  // Slots do not embed direct pointers to maps, functions. Instead
  // a WeakCell is always used.
60 61 62 63 64 65
  if (obj->IsWeakCell()) {
    WeakCell* cell = WeakCell::cast(obj);
    if (cell->cleared()) return undefined;
    obj = cell->value();
  }

66
  if (obj->IsJSFunction() || obj->IsAllocationSite() || obj->IsSymbol() ||
67
      obj->IsSimd128Value()) {
68 69
    return Handle<Object>(obj, isolate());
  }
70

71
  return undefined;
72 73 74
}


75
InlineCacheState TypeFeedbackOracle::LoadInlineCacheState(TypeFeedbackId id) {
76 77 78
  Handle<Object> maybe_code = GetInfo(id);
  if (maybe_code->IsCode()) {
    Handle<Code> code = Handle<Code>::cast(maybe_code);
79
    if (code->is_inline_cache_stub()) return code->ic_state();
80
  }
81 82 83 84

  // If we can't find an IC, assume we've seen *something*, but we don't know
  // what. PREMONOMORPHIC roughly encodes this meaning.
  return PREMONOMORPHIC;
85 86 87
}


88
InlineCacheState TypeFeedbackOracle::LoadInlineCacheState(
89
    FeedbackVectorSlot slot) {
90
  if (!slot.IsInvalid()) {
91 92
    FeedbackVectorSlotKind kind = feedback_vector_->GetKind(slot);
    if (kind == FeedbackVectorSlotKind::LOAD_IC) {
93 94
      LoadICNexus nexus(feedback_vector_, slot);
      return nexus.StateFromFeedback();
95
    } else if (kind == FeedbackVectorSlotKind::KEYED_LOAD_IC) {
96 97 98
      KeyedLoadICNexus nexus(feedback_vector_, slot);
      return nexus.StateFromFeedback();
    }
99 100
  }

101 102 103
  // If we can't find an IC, assume we've seen *something*, but we don't know
  // what. PREMONOMORPHIC roughly encodes this meaning.
  return PREMONOMORPHIC;
104 105 106
}


107
bool TypeFeedbackOracle::StoreIsUninitialized(TypeFeedbackId ast_id) {
108 109 110
  Handle<Object> maybe_code = GetInfo(ast_id);
  if (!maybe_code->IsCode()) return false;
  Handle<Code> code = Handle<Code>::cast(maybe_code);
111 112 113 114
  return code->ic_state() == UNINITIALIZED;
}


115
bool TypeFeedbackOracle::StoreIsUninitialized(FeedbackVectorSlot slot) {
116
  if (!slot.IsInvalid()) {
117 118
    FeedbackVectorSlotKind kind = feedback_vector_->GetKind(slot);
    if (kind == FeedbackVectorSlotKind::STORE_IC) {
119
      StoreICNexus nexus(feedback_vector_, slot);
120
      return nexus.StateFromFeedback() == UNINITIALIZED;
121
    } else if (kind == FeedbackVectorSlotKind::KEYED_STORE_IC) {
122
      KeyedStoreICNexus nexus(feedback_vector_, slot);
123
      return nexus.StateFromFeedback() == UNINITIALIZED;
124 125 126 127 128 129
    }
  }
  return true;
}


130
bool TypeFeedbackOracle::CallIsUninitialized(FeedbackVectorSlot slot) {
131 132 133 134 135 136 137
  Handle<Object> value = GetInfo(slot);
  return value->IsUndefined() ||
         value.is_identical_to(
             TypeFeedbackVector::UninitializedSentinel(isolate()));
}


138
bool TypeFeedbackOracle::CallIsMonomorphic(FeedbackVectorSlot slot) {
139
  Handle<Object> value = GetInfo(slot);
140
  return value->IsAllocationSite() || value->IsJSFunction();
141 142 143
}


144
bool TypeFeedbackOracle::CallNewIsMonomorphic(FeedbackVectorSlot slot) {
145
  Handle<Object> info = GetInfo(slot);
146
  return info->IsAllocationSite() || info->IsJSFunction();
147 148 149
}


150
byte TypeFeedbackOracle::ForInType(FeedbackVectorSlot feedback_vector_slot) {
151
  Handle<Object> value = GetInfo(feedback_vector_slot);
152
  return value.is_identical_to(
153 154 155
             TypeFeedbackVector::UninitializedSentinel(isolate()))
             ? ForInStatement::FAST_FOR_IN
             : ForInStatement::SLOW_FOR_IN;
156 157 158
}


159 160 161
void TypeFeedbackOracle::GetStoreModeAndKeyType(
    TypeFeedbackId ast_id, KeyedAccessStoreMode* store_mode,
    IcCheckType* key_type) {
162 163 164
  Handle<Object> maybe_code = GetInfo(ast_id);
  if (maybe_code->IsCode()) {
    Handle<Code> code = Handle<Code>::cast(maybe_code);
165
    if (code->kind() == Code::KEYED_STORE_IC) {
166 167 168 169
      ExtraICState extra_ic_state = code->extra_ic_state();
      *store_mode = KeyedStoreIC::GetKeyedAccessStoreMode(extra_ic_state);
      *key_type = KeyedStoreIC::GetKeyType(extra_ic_state);
      return;
170 171
    }
  }
172 173
  *store_mode = STANDARD_STORE;
  *key_type = ELEMENT;
174 175 176
}


177
void TypeFeedbackOracle::GetStoreModeAndKeyType(
178
    FeedbackVectorSlot slot, KeyedAccessStoreMode* store_mode,
179
    IcCheckType* key_type) {
180
  if (!slot.IsInvalid() &&
181 182
      feedback_vector_->GetKind(slot) ==
          FeedbackVectorSlotKind::KEYED_STORE_IC) {
183 184 185 186 187 188
    KeyedStoreICNexus nexus(feedback_vector_, slot);
    *store_mode = nexus.GetKeyedAccessStoreMode();
    *key_type = nexus.GetKeyType();
  } else {
    *store_mode = STANDARD_STORE;
    *key_type = ELEMENT;
189 190 191 192
  }
}


193
Handle<JSFunction> TypeFeedbackOracle::GetCallTarget(FeedbackVectorSlot slot) {
194
  Handle<Object> info = GetInfo(slot);
195 196
  if (info->IsAllocationSite()) {
    return Handle<JSFunction>(isolate()->native_context()->array_function());
197
  }
198

199
  return Handle<JSFunction>::cast(info);
200 201 202
}


203 204
Handle<JSFunction> TypeFeedbackOracle::GetCallNewTarget(
    FeedbackVectorSlot slot) {
205
  Handle<Object> info = GetInfo(slot);
206
  if (info->IsJSFunction()) {
207 208
    return Handle<JSFunction>::cast(info);
  }
209

210
  DCHECK(info->IsAllocationSite());
211
  return Handle<JSFunction>(isolate()->native_context()->array_function());
212 213 214
}


215
Handle<AllocationSite> TypeFeedbackOracle::GetCallAllocationSite(
216
    FeedbackVectorSlot slot) {
217 218 219 220 221 222 223 224
  Handle<Object> info = GetInfo(slot);
  if (info->IsAllocationSite()) {
    return Handle<AllocationSite>::cast(info);
  }
  return Handle<AllocationSite>::null();
}


225 226
Handle<AllocationSite> TypeFeedbackOracle::GetCallNewAllocationSite(
    FeedbackVectorSlot slot) {
227
  Handle<Object> info = GetInfo(slot);
228
  if (info->IsAllocationSite()) {
229 230 231
    return Handle<AllocationSite>::cast(info);
  }
  return Handle<AllocationSite>::null();
232 233
}

234

235 236
bool TypeFeedbackOracle::LoadIsBuiltin(
    TypeFeedbackId id, Builtins::Name builtin) {
237
  return *GetInfo(id) == isolate()->builtins()->builtin(builtin);
238 239 240
}


241
void TypeFeedbackOracle::CompareType(TypeFeedbackId id,
242 243 244
                                     Type** left_type,
                                     Type** right_type,
                                     Type** combined_type) {
245
  Handle<Object> info = GetInfo(id);
246 247
  if (!info->IsCode()) {
    // For some comparisons we don't have ICs, e.g. LiteralCompareTypeof.
248
    *left_type = *right_type = *combined_type = Type::None(zone());
249 250
    return;
  }
251 252 253 254
  Handle<Code> code = Handle<Code>::cast(info);

  Handle<Map> map;
  Map* raw_map = code->FindFirstMap();
255
  if (raw_map != NULL) Map::TryUpdate(handle(raw_map)).ToHandle(&map);
256

257
  if (code->is_compare_ic_stub()) {
258
    CompareICStub stub(code->stub_key(), isolate());
259 260 261
    *left_type = CompareICState::StateToType(zone(), stub.left());
    *right_type = CompareICState::StateToType(zone(), stub.right());
    *combined_type = CompareICState::StateToType(zone(), stub.state(), map);
262
  } else if (code->is_compare_nil_ic_stub()) {
263
    CompareNilICStub stub(isolate(), code->extra_ic_state());
264 265
    *combined_type = stub.GetType(zone(), map);
    *left_type = *right_type = stub.GetInputType(zone(), map);
266 267 268 269
  }
}


270
void TypeFeedbackOracle::BinaryType(TypeFeedbackId id,
271 272 273
                                    Type** left,
                                    Type** right,
                                    Type** result,
274
                                    Maybe<int>* fixed_right_arg,
275
                                    Handle<AllocationSite>* allocation_site,
276
                                    Token::Value op) {
277
  Handle<Object> object = GetInfo(id);
278
  if (!object->IsCode()) {
279
    // For some binary ops we don't have ICs, e.g. Token::COMMA, but for the
280
    // operations covered by the BinaryOpIC we should always have them.
281 282
    DCHECK(op < BinaryOpICState::FIRST_TOKEN ||
           op > BinaryOpICState::LAST_TOKEN);
283
    *left = *right = *result = Type::None(zone());
284
    *fixed_right_arg = Nothing<int>();
285
    *allocation_site = Handle<AllocationSite>::null();
286 287
    return;
  }
288
  Handle<Code> code = Handle<Code>::cast(object);
289
  DCHECK_EQ(Code::BINARY_OP_IC, code->kind());
290
  BinaryOpICState state(isolate(), code->extra_ic_state());
291
  DCHECK_EQ(op, state.op());
292

293 294 295
  *left = state.GetLeftType(zone());
  *right = state.GetRightType(zone());
  *result = state.GetResultType(zone());
296
  *fixed_right_arg = state.fixed_right_arg();
297 298 299 300 301 302 303

  AllocationSite* first_allocation_site = code->FindFirstAllocationSite();
  if (first_allocation_site != NULL) {
    *allocation_site = handle(first_allocation_site);
  } else {
    *allocation_site = Handle<AllocationSite>::null();
  }
304 305
}

306

307
Type* TypeFeedbackOracle::CountType(TypeFeedbackId id) {
308
  Handle<Object> object = GetInfo(id);
309
  if (!object->IsCode()) return Type::None(zone());
310
  Handle<Code> code = Handle<Code>::cast(object);
311
  DCHECK_EQ(Code::BINARY_OP_IC, code->kind());
312
  BinaryOpICState state(isolate(), code->extra_ic_state());
313
  return state.GetLeftType(zone());
314 315 316
}


317 318 319 320 321 322 323 324 325
bool TypeFeedbackOracle::HasOnlyStringMaps(SmallMapList* receiver_types) {
  bool all_strings = receiver_types->length() > 0;
  for (int i = 0; i < receiver_types->length(); i++) {
    all_strings &= receiver_types->at(i)->IsStringMap();
  }
  return all_strings;
}


326
void TypeFeedbackOracle::PropertyReceiverTypes(FeedbackVectorSlot slot,
327
                                               Handle<Name> name,
328 329
                                               SmallMapList* receiver_types) {
  receiver_types->Clear();
330 331 332 333 334
  if (!slot.IsInvalid()) {
    LoadICNexus nexus(feedback_vector_, slot);
    Code::Flags flags = Code::ComputeHandlerFlags(Code::LOAD_IC);
    CollectReceiverTypes(&nexus, name, flags, receiver_types);
  }
335 336 337 338
}


void TypeFeedbackOracle::KeyedPropertyReceiverTypes(
339
    FeedbackVectorSlot slot, SmallMapList* receiver_types, bool* is_string,
340
    IcCheckType* key_type) {
341
  receiver_types->Clear();
342 343 344 345 346 347 348 349 350
  if (slot.IsInvalid()) {
    *is_string = false;
    *key_type = ELEMENT;
  } else {
    KeyedLoadICNexus nexus(feedback_vector_, slot);
    CollectReceiverTypes<FeedbackNexus>(&nexus, receiver_types);
    *is_string = HasOnlyStringMaps(receiver_types);
    *key_type = nexus.FindFirstName() != NULL ? PROPERTY : ELEMENT;
  }
351 352 353
}


354 355 356
void TypeFeedbackOracle::AssignmentReceiverTypes(TypeFeedbackId id,
                                                 Handle<Name> name,
                                                 SmallMapList* receiver_types) {
357
  receiver_types->Clear();
358
  Code::Flags flags = Code::ComputeHandlerFlags(Code::STORE_IC);
359
  CollectReceiverTypes(id, name, flags, receiver_types);
360 361 362
}


363
void TypeFeedbackOracle::AssignmentReceiverTypes(FeedbackVectorSlot slot,
364 365 366 367 368 369 370 371
                                                 Handle<Name> name,
                                                 SmallMapList* receiver_types) {
  receiver_types->Clear();
  Code::Flags flags = Code::ComputeHandlerFlags(Code::STORE_IC);
  CollectReceiverTypes(slot, name, flags, receiver_types);
}


372 373
void TypeFeedbackOracle::KeyedAssignmentReceiverTypes(
    TypeFeedbackId id, SmallMapList* receiver_types,
374
    KeyedAccessStoreMode* store_mode, IcCheckType* key_type) {
375
  receiver_types->Clear();
376
  CollectReceiverTypes(id, receiver_types);
377
  GetStoreModeAndKeyType(id, store_mode, key_type);
378 379 380
}


381
void TypeFeedbackOracle::KeyedAssignmentReceiverTypes(
382
    FeedbackVectorSlot slot, SmallMapList* receiver_types,
383 384 385 386 387 388 389
    KeyedAccessStoreMode* store_mode, IcCheckType* key_type) {
  receiver_types->Clear();
  CollectReceiverTypes(slot, receiver_types);
  GetStoreModeAndKeyType(slot, store_mode, key_type);
}


390 391
void TypeFeedbackOracle::CountReceiverTypes(TypeFeedbackId id,
                                            SmallMapList* receiver_types) {
392
  receiver_types->Clear();
393
  CollectReceiverTypes(id, receiver_types);
394 395 396
}


397
void TypeFeedbackOracle::CountReceiverTypes(FeedbackVectorSlot slot,
398 399 400 401 402 403
                                            SmallMapList* receiver_types) {
  receiver_types->Clear();
  if (!slot.IsInvalid()) CollectReceiverTypes(slot, receiver_types);
}


404
void TypeFeedbackOracle::CollectReceiverTypes(FeedbackVectorSlot slot,
405 406 407 408 409 410 411 412
                                              Handle<Name> name,
                                              Code::Flags flags,
                                              SmallMapList* types) {
  StoreICNexus nexus(feedback_vector_, slot);
  CollectReceiverTypes<FeedbackNexus>(&nexus, name, flags, types);
}


413
void TypeFeedbackOracle::CollectReceiverTypes(TypeFeedbackId ast_id,
414
                                              Handle<Name> name,
415 416
                                              Code::Flags flags,
                                              SmallMapList* types) {
417
  Handle<Object> object = GetInfo(ast_id);
418
  if (object->IsUndefined() || object->IsSmi()) return;
419

420
  DCHECK(object->IsCode());
421
  Handle<Code> code(Handle<Code>::cast(object));
422 423
  CollectReceiverTypes<Code>(*code, name, flags, types);
}
424

425 426

template <class T>
427
void TypeFeedbackOracle::CollectReceiverTypes(T* obj, Handle<Name> name,
428 429
                                              Code::Flags flags,
                                              SmallMapList* types) {
430
  if (FLAG_collect_megamorphic_maps_from_stub_cache &&
431
      obj->ic_state() == MEGAMORPHIC) {
432
    types->Reserve(4, zone());
433
    isolate()->stub_cache()->CollectMatchingMaps(
434 435
        types, name, flags, native_context_, zone());
  } else {
436
    CollectReceiverTypes<T>(obj, types);
437 438 439 440
  }
}


441 442
void TypeFeedbackOracle::CollectReceiverTypes(TypeFeedbackId ast_id,
                                              SmallMapList* types) {
443 444 445
  Handle<Object> object = GetInfo(ast_id);
  if (!object->IsCode()) return;
  Handle<Code> code = Handle<Code>::cast(object);
446 447 448 449
  CollectReceiverTypes<Code>(*code, types);
}


450
void TypeFeedbackOracle::CollectReceiverTypes(FeedbackVectorSlot slot,
451
                                              SmallMapList* types) {
452 453
  FeedbackVectorSlotKind kind = feedback_vector_->GetKind(slot);
  if (kind == FeedbackVectorSlotKind::STORE_IC) {
454 455 456
    StoreICNexus nexus(feedback_vector_, slot);
    CollectReceiverTypes<FeedbackNexus>(&nexus, types);
  } else {
457
    DCHECK_EQ(FeedbackVectorSlotKind::KEYED_STORE_IC, kind);
458 459 460
    KeyedStoreICNexus nexus(feedback_vector_, slot);
    CollectReceiverTypes<FeedbackNexus>(&nexus, types);
  }
461 462 463
}


464 465
template <class T>
void TypeFeedbackOracle::CollectReceiverTypes(T* obj, SmallMapList* types) {
466
  MapHandleList maps;
467 468
  if (obj->ic_state() == MONOMORPHIC) {
    Map* map = obj->FindFirstMap();
469
    if (map != NULL) maps.Add(handle(map));
470 471
  } else if (obj->ic_state() == POLYMORPHIC) {
    obj->FindAllMaps(&maps);
472 473
  } else {
    return;
474
  }
475 476 477
  types->Reserve(maps.length(), zone());
  for (int i = 0; i < maps.length(); i++) {
    Handle<Map> map(maps.at(i));
478 479
    if (IsRelevantFeedback(*map, *native_context_)) {
      types->AddMapIfMissing(maps.at(i), zone());
480
    }
481 482 483 484
  }
}


485
uint16_t TypeFeedbackOracle::ToBooleanTypes(TypeFeedbackId id) {
486
  Handle<Object> object = GetInfo(id);
487 488 489 490
  return object->IsCode() ? Handle<Code>::cast(object)->to_boolean_state() : 0;
}


491 492 493 494 495
// Things are a bit tricky here: The iterator for the RelocInfos and the infos
// themselves are not GC-safe, so we first get all infos, then we create the
// dictionary (possibly triggering GC), and finally we relocate the collected
// infos before we process them.
void TypeFeedbackOracle::BuildDictionary(Handle<Code> code) {
496
  DisallowHeapAllocation no_allocation;
497
  ZoneList<RelocInfo> infos(16, zone());
498
  HandleScope scope(isolate());
499 500 501 502 503
  GetRelocInfos(code, &infos);
  CreateDictionary(code, &infos);
  ProcessRelocInfos(&infos);
  // Allocate handle in the parent scope.
  dictionary_ = scope.CloseAndEscape(dictionary_);
504 505 506
}


507 508 509 510
void TypeFeedbackOracle::GetRelocInfos(Handle<Code> code,
                                       ZoneList<RelocInfo>* infos) {
  int mask = RelocInfo::ModeMask(RelocInfo::CODE_TARGET_WITH_ID);
  for (RelocIterator it(*code, mask); !it.done(); it.next()) {
511
    infos->Add(*it.rinfo(), zone());
512 513
  }
}
514 515


516 517
void TypeFeedbackOracle::CreateDictionary(Handle<Code> code,
                                          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 527
                                            Code* old_code,
                                            Code* new_code) {
528 529
  for (int i = 0; i < infos->length(); i++) {
    RelocInfo* info = &(*infos)[i];
530 531 532
    info->set_host(new_code);
    info->set_pc(new_code->instruction_start() +
                 (info->pc() - old_code->instruction_start()));
533 534 535 536
  }
}


537 538
void TypeFeedbackOracle::ProcessRelocInfos(ZoneList<RelocInfo>* infos) {
  for (int i = 0; i < infos->length(); i++) {
539 540
    RelocInfo reloc_entry = (*infos)[i];
    Address target_address = reloc_entry.target_address();
541 542
    TypeFeedbackId ast_id =
        TypeFeedbackId(static_cast<unsigned>((*infos)[i].data()));
543 544
    Code* target = Code::GetCodeFromTargetAddress(target_address);
    switch (target->kind()) {
545 546
      case Code::LOAD_IC:
      case Code::STORE_IC:
547 548 549 550 551
      case Code::KEYED_LOAD_IC:
      case Code::KEYED_STORE_IC:
      case Code::BINARY_OP_IC:
      case Code::COMPARE_IC:
      case Code::TO_BOOLEAN_IC:
552
      case Code::COMPARE_NIL_IC:
553
        SetInfo(ast_id, target);
554 555 556 557 558
        break;

      default:
        break;
    }
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 568
  DisallowHeapAllocation no_need_to_resize_dictionary;
  HandleScope scope(isolate());
569 570
  USE(UnseededNumberDictionary::AtNumberPut(
      dictionary_, IdToKey(ast_id), handle(target, isolate())));
571 572
}

573

574 575
}  // namespace internal
}  // namespace v8