Home | History | Annotate | Download | only in crankshaft 
      1 // Copyright 2013 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_CRANKSHAFT_UNIQUE_H_
      6 #define V8_CRANKSHAFT_UNIQUE_H_
      7 
      8 #include <ostream>  // NOLINT(readability/streams)
      9 
     10 #include "src/assert-scope.h"
     11 #include "src/base/functional.h"
     12 #include "src/handles.h"
     13 #include "src/utils.h"
     14 #include "src/zone/zone.h"
     15 
     16 namespace v8 {
     17 namespace internal {
     18 
     19 
     20 template <typename T>
     21 class UniqueSet;
     22 
     23 
     24 // Represents a handle to an object on the heap, but with the additional
     25 // ability of checking for equality and hashing without accessing the heap.
     26 //
     27 // Creating a Unique<T> requires first dereferencing the handle to obtain
     28 // the address of the object, which is used as the hashcode and the basis for
     29 // comparison. The object can be moved later by the GC, but comparison
     30 // and hashing use the old address of the object, without dereferencing it.
     31 //
     32 // Careful! Comparison of two Uniques is only correct if both were created
     33 // in the same "era" of GC or if at least one is a non-movable object.
     34 template <typename T>
     35 class Unique final {
     36  public:
     37   Unique<T>() : raw_address_(NULL) {}
     38 
     39   // TODO(titzer): make private and introduce a uniqueness scope.
     40   explicit Unique(Handle<T> handle) {
     41     if (handle.is_null()) {
     42       raw_address_ = NULL;
     43     } else {
     44       // This is a best-effort check to prevent comparing Unique<T>'s created
     45       // in different GC eras; we require heap allocation to be disallowed at
     46       // creation time.
     47       // NOTE: we currently consider maps to be non-movable, so no special
     48       // assurance is required for creating a Unique<Map>.
     49       // TODO(titzer): other immortable immovable objects are also fine.
     50       DCHECK(!AllowHeapAllocation::IsAllowed() || handle->IsMap());
     51       raw_address_ = reinterpret_cast<Address>(*handle);
     52       DCHECK_NOT_NULL(raw_address_);  // Non-null should imply non-zero address.
     53     }
     54     handle_ = handle;
     55   }
     56 
     57   // Constructor for handling automatic up casting.
     58   // Eg. Unique<JSFunction> can be passed when Unique<Object> is expected.
     59   template <class S> Unique(Unique<S> uniq) {
     60 #ifdef DEBUG
     61     T* a = NULL;
     62     S* b = NULL;
     63     a = b;  // Fake assignment to enforce type checks.
     64     USE(a);
     65 #endif
     66     raw_address_ = uniq.raw_address_;
     67     handle_ = uniq.handle_;
     68   }
     69 
     70   template <typename U>
     71   inline bool operator==(const Unique<U>& other) const {
     72     DCHECK(IsInitialized() && other.IsInitialized());
     73     return raw_address_ == other.raw_address_;
     74   }
     75 
     76   template <typename U>
     77   inline bool operator!=(const Unique<U>& other) const {
     78     DCHECK(IsInitialized() && other.IsInitialized());
     79     return raw_address_ != other.raw_address_;
     80   }
     81 
     82   friend inline size_t hash_value(Unique<T> const& unique) {
     83     DCHECK(unique.IsInitialized());
     84     return base::hash<void*>()(unique.raw_address_);
     85   }
     86 
     87   inline intptr_t Hashcode() const {
     88     DCHECK(IsInitialized());
     89     return reinterpret_cast<intptr_t>(raw_address_);
     90   }
     91 
     92   inline bool IsNull() const {
     93     DCHECK(IsInitialized());
     94     return raw_address_ == NULL;
     95   }
     96 
     97   inline bool IsKnownGlobal(void* global) const {
     98     DCHECK(IsInitialized());
     99     return raw_address_ == reinterpret_cast<Address>(global);
    100   }
    101 
    102   inline Handle<T> handle() const {
    103     return handle_;
    104   }
    105 
    106   template <class S> static Unique<T> cast(Unique<S> that) {
    107     // Allow fetching location() to unsafe-cast the handle. This is necessary
    108     // since we can't concurrently safe-cast. Safe-casting requires looking at
    109     // the heap which may be moving concurrently to the compiler thread.
    110     AllowHandleDereference allow_deref;
    111     return Unique<T>(that.raw_address_,
    112                      Handle<T>(reinterpret_cast<T**>(that.handle_.location())));
    113   }
    114 
    115   inline bool IsInitialized() const {
    116     return raw_address_ != NULL || handle_.is_null();
    117   }
    118 
    119   // TODO(titzer): this is a hack to migrate to Unique<T> incrementally.
    120   static Unique<T> CreateUninitialized(Handle<T> handle) {
    121     return Unique<T>(NULL, handle);
    122   }
    123 
    124   static Unique<T> CreateImmovable(Handle<T> handle) {
    125     return Unique<T>(reinterpret_cast<Address>(*handle), handle);
    126   }
    127 
    128  private:
    129   Unique(Address raw_address, Handle<T> handle)
    130       : raw_address_(raw_address), handle_(handle) {}
    131 
    132   Address raw_address_;
    133   Handle<T> handle_;
    134 
    135   friend class UniqueSet<T>;  // Uses internal details for speed.
    136   template <class U>
    137   friend class Unique;  // For comparing raw_address values.
    138 };
    139 
    140 template <typename T>
    141 inline std::ostream& operator<<(std::ostream& os, Unique<T> uniq) {
    142   return os << Brief(*uniq.handle());
    143 }
    144 
    145 
    146 template <typename T>
    147 class UniqueSet final : public ZoneObject {
    148  public:
    149   // Constructor. A new set will be empty.
    150   UniqueSet() : size_(0), capacity_(0), array_(NULL) { }
    151 
    152   // Capacity constructor. A new set will be empty.
    153   UniqueSet(int capacity, Zone* zone)
    154       : size_(0), capacity_(capacity),
    155         array_(zone->NewArray<Unique<T> >(capacity)) {
    156     DCHECK(capacity <= kMaxCapacity);
    157   }
    158 
    159   // Singleton constructor.
    160   UniqueSet(Unique<T> uniq, Zone* zone)
    161       : size_(1), capacity_(1), array_(zone->NewArray<Unique<T> >(1)) {
    162     array_[0] = uniq;
    163   }
    164 
    165   // Add a new element to this unique set. Mutates this set. O(|this|).
    166   void Add(Unique<T> uniq, Zone* zone) {
    167     DCHECK(uniq.IsInitialized());
    168     // Keep the set sorted by the {raw_address} of the unique elements.
    169     for (int i = 0; i < size_; i++) {
    170       if (array_[i] == uniq) return;
    171       if (array_[i].raw_address_ > uniq.raw_address_) {
    172         // Insert in the middle.
    173         Grow(size_ + 1, zone);
    174         for (int j = size_ - 1; j >= i; j--) array_[j + 1] = array_[j];
    175         array_[i] = uniq;
    176         size_++;
    177         return;
    178       }
    179     }
    180     // Append the element to the the end.
    181     Grow(size_ + 1, zone);
    182     array_[size_++] = uniq;
    183   }
    184 
    185   // Remove an element from this set. Mutates this set. O(|this|)
    186   void Remove(Unique<T> uniq) {
    187     for (int i = 0; i < size_; i++) {
    188       if (array_[i] == uniq) {
    189         while (++i < size_) array_[i - 1] = array_[i];
    190         size_--;
    191         return;
    192       }
    193     }
    194   }
    195 
    196   // Compare this set against another set. O(|this|).
    197   bool Equals(const UniqueSet<T>* that) const {
    198     if (that->size_ != this->size_) return false;
    199     for (int i = 0; i < this->size_; i++) {
    200       if (this->array_[i] != that->array_[i]) return false;
    201     }
    202     return true;
    203   }
    204 
    205   // Check whether this set contains the given element. O(|this|)
    206   // TODO(titzer): use binary search for large sets to make this O(log|this|)
    207   template <typename U>
    208   bool Contains(const Unique<U> elem) const {
    209     for (int i = 0; i < this->size_; ++i) {
    210       Unique<T> cand = this->array_[i];
    211       if (cand.raw_address_ >= elem.raw_address_) {
    212         return cand.raw_address_ == elem.raw_address_;
    213       }
    214     }
    215     return false;
    216   }
    217 
    218   // Check if this set is a subset of the given set. O(|this| + |that|).
    219   bool IsSubset(const UniqueSet<T>* that) const {
    220     if (that->size_ < this->size_) return false;
    221     int j = 0;
    222     for (int i = 0; i < this->size_; i++) {
    223       Unique<T> sought = this->array_[i];
    224       while (true) {
    225         if (sought == that->array_[j++]) break;
    226         // Fail whenever there are more elements in {this} than {that}.
    227         if ((this->size_ - i) > (that->size_ - j)) return false;
    228       }
    229     }
    230     return true;
    231   }
    232 
    233   // Returns a new set representing the intersection of this set and the other.
    234   // O(|this| + |that|).
    235   UniqueSet<T>* Intersect(const UniqueSet<T>* that, Zone* zone) const {
    236     if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>();
    237 
    238     UniqueSet<T>* out = new(zone) UniqueSet<T>(
    239         Min(this->size_, that->size_), zone);
    240 
    241     int i = 0, j = 0, k = 0;
    242     while (i < this->size_ && j < that->size_) {
    243       Unique<T> a = this->array_[i];
    244       Unique<T> b = that->array_[j];
    245       if (a == b) {
    246         out->array_[k++] = a;
    247         i++;
    248         j++;
    249       } else if (a.raw_address_ < b.raw_address_) {
    250         i++;
    251       } else {
    252         j++;
    253       }
    254     }
    255 
    256     out->size_ = k;
    257     return out;
    258   }
    259 
    260   // Returns a new set representing the union of this set and the other.
    261   // O(|this| + |that|).
    262   UniqueSet<T>* Union(const UniqueSet<T>* that, Zone* zone) const {
    263     if (that->size_ == 0) return this->Copy(zone);
    264     if (this->size_ == 0) return that->Copy(zone);
    265 
    266     UniqueSet<T>* out = new(zone) UniqueSet<T>(
    267         this->size_ + that->size_, zone);
    268 
    269     int i = 0, j = 0, k = 0;
    270     while (i < this->size_ && j < that->size_) {
    271       Unique<T> a = this->array_[i];
    272       Unique<T> b = that->array_[j];
    273       if (a == b) {
    274         out->array_[k++] = a;
    275         i++;
    276         j++;
    277       } else if (a.raw_address_ < b.raw_address_) {
    278         out->array_[k++] = a;
    279         i++;
    280       } else {
    281         out->array_[k++] = b;
    282         j++;
    283       }
    284     }
    285 
    286     while (i < this->size_) out->array_[k++] = this->array_[i++];
    287     while (j < that->size_) out->array_[k++] = that->array_[j++];
    288 
    289     out->size_ = k;
    290     return out;
    291   }
    292 
    293   // Returns a new set representing all elements from this set which are not in
    294   // that set. O(|this| * |that|).
    295   UniqueSet<T>* Subtract(const UniqueSet<T>* that, Zone* zone) const {
    296     if (that->size_ == 0) return this->Copy(zone);
    297 
    298     UniqueSet<T>* out = new(zone) UniqueSet<T>(this->size_, zone);
    299 
    300     int i = 0, j = 0;
    301     while (i < this->size_) {
    302       Unique<T> cand = this->array_[i];
    303       if (!that->Contains(cand)) {
    304         out->array_[j++] = cand;
    305       }
    306       i++;
    307     }
    308 
    309     out->size_ = j;
    310     return out;
    311   }
    312 
    313   // Makes an exact copy of this set. O(|this|).
    314   UniqueSet<T>* Copy(Zone* zone) const {
    315     UniqueSet<T>* copy = new(zone) UniqueSet<T>(this->size_, zone);
    316     copy->size_ = this->size_;
    317     memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>));
    318     return copy;
    319   }
    320 
    321   void Clear() {
    322     size_ = 0;
    323   }
    324 
    325   inline int size() const {
    326     return size_;
    327   }
    328 
    329   inline Unique<T> at(int index) const {
    330     DCHECK(index >= 0 && index < size_);
    331     return array_[index];
    332   }
    333 
    334  private:
    335   // These sets should be small, since operations are implemented with simple
    336   // linear algorithms. Enforce a maximum size.
    337   static const int kMaxCapacity = 65535;
    338 
    339   uint16_t size_;
    340   uint16_t capacity_;
    341   Unique<T>* array_;
    342 
    343   // Grow the size of internal storage to be at least {size} elements.
    344   void Grow(int size, Zone* zone) {
    345     CHECK(size < kMaxCapacity);  // Enforce maximum size.
    346     if (capacity_ < size) {
    347       int new_capacity = 2 * capacity_ + size;
    348       if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity;
    349       Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity);
    350       if (size_ > 0) {
    351         memcpy(new_array, array_, size_ * sizeof(Unique<T>));
    352       }
    353       capacity_ = new_capacity;
    354       array_ = new_array;
    355     }
    356   }
    357 };
    358 
    359 }  // namespace internal
    360 }  // namespace v8
    361 
    362 #endif  // V8_CRANKSHAFT_UNIQUE_H_
    363