deps/v8/src/type-feedback-vector.h

   1 // Copyright 2014 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 #ifndef V8_TYPE_FEEDBACK_VECTOR_H_
   6 #define V8_TYPE_FEEDBACK_VECTOR_H_
   7
   8 #include <vector>
   9
  10 #include "src/checks.h"
  11 #include "src/elements-kind.h"
  12 #include "src/heap/heap.h"
  13 #include "src/isolate.h"
  14 #include "src/objects.h"
  15 #include "src/zone-containers.h"
  16
  17 namespace v8 {
  18 namespace internal {
  19
  20 class FeedbackVectorSpec {
  21  public:
  22   FeedbackVectorSpec() : slots_(0), has_ic_slot_(false) {}
  23   explicit FeedbackVectorSpec(int slots) : slots_(slots), has_ic_slot_(false) {}
  24   FeedbackVectorSpec(int slots, Code::Kind ic_slot_kind)
  25       : slots_(slots), has_ic_slot_(true), ic_kind_(ic_slot_kind) {}
  26
  27   int slots() const { return slots_; }
  28
  29   int ic_slots() const { return has_ic_slot_ ? 1 : 0; }
  30
  31   Code::Kind GetKind(int ic_slot) const {
  32     DCHECK(FLAG_vector_ics && has_ic_slot_ && ic_slot == 0);
  33     return ic_kind_;
  34   }
  35
  36  private:
  37   int slots_;
  38   bool has_ic_slot_;
  39   Code::Kind ic_kind_;
  40 };
  41
  42
  43 class ZoneFeedbackVectorSpec {
  44  public:
  45   explicit ZoneFeedbackVectorSpec(Zone* zone)
  46       : slots_(0), ic_slots_(0), ic_slot_kinds_(zone) {}
  47
  48   ZoneFeedbackVectorSpec(Zone* zone, int slots, int ic_slots)
  49       : slots_(slots),
  50         ic_slots_(ic_slots),
  51         ic_slot_kinds_(FLAG_vector_ics ? ic_slots : 0, zone) {}
  52
  53   int slots() const { return slots_; }
  54   void increase_slots(int count) { slots_ += count; }
  55
  56   int ic_slots() const { return ic_slots_; }
  57   void increase_ic_slots(int count) {
  58     ic_slots_ += count;
  59     if (FLAG_vector_ics) ic_slot_kinds_.resize(ic_slots_);
  60   }
  61
  62   void SetKind(int ic_slot, Code::Kind kind) {
  63     DCHECK(FLAG_vector_ics);
  64     ic_slot_kinds_[ic_slot] = kind;
  65   }
  66
  67   Code::Kind GetKind(int ic_slot) const {
  68     DCHECK(FLAG_vector_ics);
  69     return static_cast<Code::Kind>(ic_slot_kinds_.at(ic_slot));
  70   }
  71
  72  private:
  73   int slots_;
  74   int ic_slots_;
  75   ZoneVector<unsigned char> ic_slot_kinds_;
  76 };
  77
  78
  79 // The shape of the TypeFeedbackVector is an array with:
  80 // 0: first_ic_slot_index (== length() if no ic slots are present)
  81 // 1: ics_with_types
  82 // 2: ics_with_generic_info
  83 // 3: type information for ic slots, if any
  84 // ...
  85 // N: first feedback slot (N >= 3)
  86 // ...
  87 // [<first_ic_slot_index>: feedback slot]
  88 // ...to length() - 1
  89 //
  90 class TypeFeedbackVector : public FixedArray {
  91  public:
  92   // Casting.
  93   static TypeFeedbackVector* cast(Object* obj) {
  94     DCHECK(obj->IsTypeFeedbackVector());
  95     return reinterpret_cast<TypeFeedbackVector*>(obj);
  96   }
  97
  98   static const int kReservedIndexCount = 3;
  99   static const int kFirstICSlotIndex = 0;
 100   static const int kWithTypesIndex = 1;
 101   static const int kGenericCountIndex = 2;
 102
 103   static int elements_per_ic_slot() { return FLAG_vector_ics ? 2 : 1; }
 104
 105   int first_ic_slot_index() const {
 106     DCHECK(length() >= kReservedIndexCount);
 107     return Smi::cast(get(kFirstICSlotIndex))->value();
 108   }
 109
 110   int ic_with_type_info_count() {
 111     return length() > 0 ? Smi::cast(get(kWithTypesIndex))->value() : 0;
 112   }
 113
 114   void change_ic_with_type_info_count(int delta) {
 115     if (delta == 0) return;
 116     int value = ic_with_type_info_count() + delta;
 117     // Could go negative because of the debugger.
 118     if (value >= 0) {
 119       set(kWithTypesIndex, Smi::FromInt(value));
 120     }
 121   }
 122
 123   int ic_generic_count() {
 124     return length() > 0 ? Smi::cast(get(kGenericCountIndex))->value() : 0;
 125   }
 126
 127   void change_ic_generic_count(int delta) {
 128     if (delta == 0) return;
 129     int value = ic_generic_count() + delta;
 130     if (value >= 0) {
 131       set(kGenericCountIndex, Smi::FromInt(value));
 132     }
 133   }
 134
 135   inline int ic_metadata_length() const;
 136
 137   int Slots() const {
 138     if (length() == 0) return 0;
 139     return Max(
 140         0, first_ic_slot_index() - ic_metadata_length() - kReservedIndexCount);
 141   }
 142
 143   int ICSlots() const {
 144     if (length() == 0) return 0;
 145     return (length() - first_ic_slot_index()) / elements_per_ic_slot();
 146   }
 147
 148   // Conversion from a slot or ic slot to an integer index to the underlying
 149   // array.
 150   int GetIndex(FeedbackVectorSlot slot) const {
 151     DCHECK(slot.ToInt() < first_ic_slot_index());
 152     return kReservedIndexCount + ic_metadata_length() + slot.ToInt();
 153   }
 154
 155   int GetIndex(FeedbackVectorICSlot slot) const {
 156     int first_ic_slot = first_ic_slot_index();
 157     DCHECK(slot.ToInt() < ICSlots());
 158     return first_ic_slot + slot.ToInt() * elements_per_ic_slot();
 159   }
 160
 161   // Conversion from an integer index to either a slot or an ic slot. The caller
 162   // should know what kind she expects.
 163   FeedbackVectorSlot ToSlot(int index) const {
 164     DCHECK(index >= kReservedIndexCount && index < first_ic_slot_index());
 165     return FeedbackVectorSlot(index - ic_metadata_length() -
 166                               kReservedIndexCount);
 167   }
 168
 169   FeedbackVectorICSlot ToICSlot(int index) const {
 170     DCHECK(index >= first_ic_slot_index() && index < length());
 171     int ic_slot = (index - first_ic_slot_index()) / elements_per_ic_slot();
 172     return FeedbackVectorICSlot(ic_slot);
 173   }
 174
 175   Object* Get(FeedbackVectorSlot slot) const { return get(GetIndex(slot)); }
 176   void Set(FeedbackVectorSlot slot, Object* value,
 177            WriteBarrierMode mode = UPDATE_WRITE_BARRIER) {
 178     set(GetIndex(slot), value, mode);
 179   }
 180
 181   Object* Get(FeedbackVectorICSlot slot) const { return get(GetIndex(slot)); }
 182   void Set(FeedbackVectorICSlot slot, Object* value,
 183            WriteBarrierMode mode = UPDATE_WRITE_BARRIER) {
 184     set(GetIndex(slot), value, mode);
 185   }
 186
 187   // IC slots need metadata to recognize the type of IC.
 188   Code::Kind GetKind(FeedbackVectorICSlot slot) const;
 189
 190   template <typename Spec>
 191   static Handle<TypeFeedbackVector> Allocate(Isolate* isolate,
 192                                              const Spec* spec);
 193
 194   static Handle<TypeFeedbackVector> Copy(Isolate* isolate,
 195                                          Handle<TypeFeedbackVector> vector);
 196
 197   // Clears the vector slots and the vector ic slots.
 198   void ClearSlots(SharedFunctionInfo* shared);
 199   void ClearICSlots(SharedFunctionInfo* shared) {
 200     ClearICSlotsImpl(shared, true);
 201   }
 202   void ClearICSlotsAtGCTime(SharedFunctionInfo* shared) {
 203     ClearICSlotsImpl(shared, false);
 204   }
 205
 206   // The object that indicates an uninitialized cache.
 207   static inline Handle<Object> UninitializedSentinel(Isolate* isolate);
 208
 209   // The object that indicates a megamorphic state.
 210   static inline Handle<Object> MegamorphicSentinel(Isolate* isolate);
 211
 212   // The object that indicates a premonomorphic state.
 213   static inline Handle<Object> PremonomorphicSentinel(Isolate* isolate);
 214
 215   // The object that indicates a monomorphic state of Array with
 216   // ElementsKind
 217   static inline Handle<Object> MonomorphicArraySentinel(
 218       Isolate* isolate, ElementsKind elements_kind);
 219
 220   // A raw version of the uninitialized sentinel that's safe to read during
 221   // garbage collection (e.g., for patching the cache).
 222   static inline Object* RawUninitializedSentinel(Heap* heap);
 223
 224  private:
 225   enum VectorICKind {
 226     KindUnused = 0x0,
 227     KindCallIC = 0x1,
 228     KindLoadIC = 0x2,
 229     KindKeyedLoadIC = 0x3
 230   };
 231
 232   static const int kVectorICKindBits = 2;
 233   static VectorICKind FromCodeKind(Code::Kind kind);
 234   static Code::Kind FromVectorICKind(VectorICKind kind);
 235   void SetKind(FeedbackVectorICSlot slot, Code::Kind kind);
 236
 237   typedef BitSetComputer<VectorICKind, kVectorICKindBits, kSmiValueSize,
 238                          uint32_t> VectorICComputer;
 239
 240   void ClearICSlotsImpl(SharedFunctionInfo* shared, bool force_clear);
 241
 242   DISALLOW_IMPLICIT_CONSTRUCTORS(TypeFeedbackVector);
 243 };
 244
 245
 246 // A FeedbackNexus is the combination of a TypeFeedbackVector and a slot.
 247 // Derived classes customize the update and retrieval of feedback.
 248 class FeedbackNexus {
 249  public:
 250   FeedbackNexus(Handle<TypeFeedbackVector> vector, FeedbackVectorICSlot slot)
 251       : vector_handle_(vector), vector_(NULL), slot_(slot) {}
 252   FeedbackNexus(TypeFeedbackVector* vector, FeedbackVectorICSlot slot)
 253       : vector_(vector), slot_(slot) {}
 254   virtual ~FeedbackNexus() {}
 255
 256   Handle<TypeFeedbackVector> vector_handle() const {
 257     DCHECK(vector_ == NULL);
 258     return vector_handle_;
 259   }
 260   TypeFeedbackVector* vector() const {
 261     return vector_handle_.is_null() ? vector_ : *vector_handle_;
 262   }
 263   FeedbackVectorICSlot slot() const { return slot_; }
 264
 265   InlineCacheState ic_state() const { return StateFromFeedback(); }
 266   Map* FindFirstMap() const {
 267     MapHandleList maps;
 268     ExtractMaps(&maps);
 269     if (maps.length() > 0) return *maps.at(0);
 270     return NULL;
 271   }
 272
 273   // TODO(mvstanton): remove FindAllMaps, it didn't survive a code review.
 274   void FindAllMaps(MapHandleList* maps) const { ExtractMaps(maps); }
 275
 276   virtual InlineCacheState StateFromFeedback() const = 0;
 277   virtual int ExtractMaps(MapHandleList* maps) const;
 278   virtual MaybeHandle<Code> FindHandlerForMap(Handle<Map> map) const;
 279   virtual bool FindHandlers(CodeHandleList* code_list, int length = -1) const;
 280   virtual Name* FindFirstName() const { return NULL; }
 281
 282   Object* GetFeedback() const { return vector()->Get(slot()); }
 283   Object* GetFeedbackExtra() const {
 284     DCHECK(TypeFeedbackVector::elements_per_ic_slot() > 1);
 285     int extra_index = vector()->GetIndex(slot()) + 1;
 286     return vector()->get(extra_index);
 287   }
 288
 289  protected:
 290   Isolate* GetIsolate() const { return vector()->GetIsolate(); }
 291
 292   void SetFeedback(Object* feedback,
 293                    WriteBarrierMode mode = UPDATE_WRITE_BARRIER) {
 294     vector()->Set(slot(), feedback, mode);
 295   }
 296
 297   void SetFeedbackExtra(Object* feedback_extra,
 298                         WriteBarrierMode mode = UPDATE_WRITE_BARRIER) {
 299     DCHECK(TypeFeedbackVector::elements_per_ic_slot() > 1);
 300     int index = vector()->GetIndex(slot()) + 1;
 301     vector()->set(index, feedback_extra, mode);
 302   }
 303
 304   Handle<FixedArray> EnsureArrayOfSize(int length);
 305   Handle<FixedArray> EnsureExtraArrayOfSize(int length);
 306   void InstallHandlers(Handle<FixedArray> array, MapHandleList* maps,
 307                        CodeHandleList* handlers);
 308
 309  private:
 310   // The reason for having a vector handle and a raw pointer is that we can and
 311   // should use handles during IC miss, but not during GC when we clear ICs. If
 312   // you have a handle to the vector that is better because more operations can
 313   // be done, like allocation.
 314   Handle<TypeFeedbackVector> vector_handle_;
 315   TypeFeedbackVector* vector_;
 316   FeedbackVectorICSlot slot_;
 317 };
 318
 319
 320 class CallICNexus : public FeedbackNexus {
 321  public:
 322   CallICNexus(Handle<TypeFeedbackVector> vector, FeedbackVectorICSlot slot)
 323       : FeedbackNexus(vector, slot) {
 324     DCHECK(vector->GetKind(slot) == Code::CALL_IC);
 325   }
 326   CallICNexus(TypeFeedbackVector* vector, FeedbackVectorICSlot slot)
 327       : FeedbackNexus(vector, slot) {
 328     DCHECK(vector->GetKind(slot) == Code::CALL_IC);
 329   }
 330
 331   void Clear(Code* host);
 332
 333   void ConfigureUninitialized();
 334   void ConfigureGeneric();
 335   void ConfigureMonomorphicArray();
 336   void ConfigureMonomorphic(Handle<JSFunction> function);
 337
 338   InlineCacheState StateFromFeedback() const OVERRIDE;
 339
 340   int ExtractMaps(MapHandleList* maps) const OVERRIDE {
 341     // CallICs don't record map feedback.
 342     return 0;
 343   }
 344   MaybeHandle<Code> FindHandlerForMap(Handle<Map> map) const OVERRIDE {
 345     return MaybeHandle<Code>();
 346   }
 347   virtual bool FindHandlers(CodeHandleList* code_list,
 348                             int length = -1) const OVERRIDE {
 349     return length == 0;
 350   }
 351 };
 352
 353
 354 class LoadICNexus : public FeedbackNexus {
 355  public:
 356   LoadICNexus(Handle<TypeFeedbackVector> vector, FeedbackVectorICSlot slot)
 357       : FeedbackNexus(vector, slot) {
 358     DCHECK(vector->GetKind(slot) == Code::LOAD_IC);
 359   }
 360   LoadICNexus(TypeFeedbackVector* vector, FeedbackVectorICSlot slot)
 361       : FeedbackNexus(vector, slot) {
 362     DCHECK(vector->GetKind(slot) == Code::LOAD_IC);
 363   }
 364
 365   void Clear(Code* host);
 366
 367   void ConfigureMegamorphic();
 368   void ConfigurePremonomorphic();
 369   void ConfigureMonomorphic(Handle<Map> receiver_map, Handle<Code> handler);
 370
 371   void ConfigurePolymorphic(MapHandleList* maps, CodeHandleList* handlers);
 372
 373   InlineCacheState StateFromFeedback() const OVERRIDE;
 374 };
 375
 376
 377 class KeyedLoadICNexus : public FeedbackNexus {
 378  public:
 379   KeyedLoadICNexus(Handle<TypeFeedbackVector> vector, FeedbackVectorICSlot slot)
 380       : FeedbackNexus(vector, slot) {
 381     DCHECK(vector->GetKind(slot) == Code::KEYED_LOAD_IC);
 382   }
 383   KeyedLoadICNexus(TypeFeedbackVector* vector, FeedbackVectorICSlot slot)
 384       : FeedbackNexus(vector, slot) {
 385     DCHECK(vector->GetKind(slot) == Code::KEYED_LOAD_IC);
 386   }
 387
 388   void Clear(Code* host);
 389
 390   void ConfigureMegamorphic();
 391   void ConfigurePremonomorphic();
 392   // name can be a null handle for element loads.
 393   void ConfigureMonomorphic(Handle<Name> name, Handle<Map> receiver_map,
 394                             Handle<Code> handler);
 395   // name can be null.
 396   void ConfigurePolymorphic(Handle<Name> name, MapHandleList* maps,
 397                             CodeHandleList* handlers);
 398
 399   InlineCacheState StateFromFeedback() const OVERRIDE;
 400   Name* FindFirstName() const OVERRIDE;
 401 };
 402 }
 403 }  // namespace v8::internal
 404
 405 #endif  // V8_TRANSITIONS_H_