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