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