dfg/DFGAbstractHeap.h

   1 /*
   2  * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef DFGAbstractHeap_h
  27 #define DFGAbstractHeap_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "VirtualRegister.h"
  32 #include <wtf/HashMap.h>
  33 #include <wtf/PrintStream.h>
  34
  35 namespace JSC { namespace DFG {
  36
  37 // Implements a four-level type hierarchy:
  38 // - World is the supertype of all of the things.
  39 // - Stack with a TOP payload is a direct subtype of World
  40 // - Stack with a non-TOP payload is a direct subtype of Stack with a TOP payload.
  41 // - Heap is a direct subtype of World.
  42 // - Any other kind with TOP payload is the direct subtype of Heap.
  43 // - Any other kind with non-TOP payload is the direct subtype of the same kind with a TOP payload.
  44
  45 #define FOR_EACH_ABSTRACT_HEAP_KIND(macro) \
  46     macro(InvalidAbstractHeap) \
  47     macro(World) \
  48     macro(Stack) \
  49     macro(Heap) \
  50     macro(Butterfly_publicLength) \
  51     macro(Butterfly_vectorLength) \
  52     macro(GetterSetter_getter) \
  53     macro(GetterSetter_setter) \
  54     macro(JSCell_structureID) \
  55     macro(JSCell_indexingType) \
  56     macro(JSCell_typeInfoFlags) \
  57     macro(JSCell_typeInfoType) \
  58     macro(JSObject_butterfly) \
  59     macro(JSPropertyNameEnumerator_cachedPropertyNames) \
  60     macro(NamedProperties) \
  61     macro(IndexedInt32Properties) \
  62     macro(IndexedDoubleProperties) \
  63     macro(IndexedContiguousProperties) \
  64     macro(IndexedArrayStorageProperties) \
  65     macro(ArrayStorageProperties) \
  66     macro(DirectArgumentsProperties) \
  67     macro(ScopeProperties) \
  68     macro(TypedArrayProperties) \
  69     macro(HeapObjectCount) /* Used to reflect the fact that some allocations reveal object identity */\
  70     macro(RegExpState) \
  71     macro(InternalState) \
  72     macro(Absolute) \
  73     /* Use this for writes only, to indicate that this may fire watchpoints. Usually this is never directly written but instead we test to see if a node clobbers this; it just so happens that you have to write world to clobber it. */\
  74     macro(Watchpoint_fire) \
  75     /* Use these for reads only, just to indicate that if the world got clobbered, then this operation will not work. */\
  76     macro(MiscFields) \
  77     /* Use this for writes only, just to indicate that hoisting the node is invalid. This works because we don't hoist anything that has any side effects at all. */\
  78     macro(SideState)
  79
  80 enum AbstractHeapKind {
  81 #define ABSTRACT_HEAP_DECLARATION(name) name,
  82     FOR_EACH_ABSTRACT_HEAP_KIND(ABSTRACT_HEAP_DECLARATION)
  83 #undef ABSTRACT_HEAP_DECLARATION
  84 };
  85
  86 class AbstractHeap {
  87 public:
  88     class Payload {
  89     public:
  90         Payload()
  91             : m_isTop(false)
  92             , m_value(0)
  93         {
  94         }
  95
  96         Payload(bool isTop, int64_t value)
  97             : m_isTop(isTop)
  98             , m_value(value)
  99         {
 100             ASSERT(!(isTop && value));
 101         }
 102
 103         Payload(int64_t value)
 104             : m_isTop(false)
 105             , m_value(value)
 106         {
 107         }
 108
 109         Payload(const void* pointer)
 110             : m_isTop(false)
 111             , m_value(bitwise_cast<intptr_t>(pointer))
 112         {
 113         }
 114
 115         Payload(VirtualRegister operand)
 116             : m_isTop(false)
 117             , m_value(operand.offset())
 118         {
 119         }
 120
 121         static Payload top() { return Payload(true, 0); }
 122
 123         bool isTop() const { return m_isTop; }
 124         int64_t value() const
 125         {
 126             ASSERT(!isTop());
 127             return valueImpl();
 128         }
 129         int64_t valueImpl() const
 130         {
 131             return m_value;
 132         }
 133
 134         int32_t value32() const
 135         {
 136             return static_cast<int32_t>(value());
 137         }
 138
 139         bool operator==(const Payload& other) const
 140         {
 141             return m_isTop == other.m_isTop
 142                 && m_value == other.m_value;
 143         }
 144
 145         bool operator!=(const Payload& other) const
 146         {
 147             return !(*this == other);
 148         }
 149
 150         bool operator<(const Payload& other) const
 151         {
 152             if (isTop())
 153                 return !other.isTop();
 154             if (other.isTop())
 155                 return false;
 156             return value() < other.value();
 157         }
 158
 159         bool isDisjoint(const Payload& other) const
 160         {
 161             if (isTop())
 162                 return false;
 163             if (other.isTop())
 164                 return false;
 165             return m_value != other.m_value;
 166         }
 167
 168         bool overlaps(const Payload& other) const
 169         {
 170             return !isDisjoint(other);
 171         }
 172
 173         void dump(PrintStream&) const;
 174
 175     private:
 176         bool m_isTop;
 177         int64_t m_value;
 178     };
 179
 180     AbstractHeap()
 181     {
 182         m_value = encode(InvalidAbstractHeap, Payload());
 183     }
 184
 185     AbstractHeap(AbstractHeapKind kind)
 186     {
 187         ASSERT(kind != InvalidAbstractHeap);
 188         m_value = encode(kind, Payload::top());
 189     }
 190
 191     AbstractHeap(AbstractHeapKind kind, Payload payload)
 192     {
 193         ASSERT(kind != InvalidAbstractHeap && kind != World && kind != Heap && kind != SideState);
 194         m_value = encode(kind, payload);
 195     }
 196
 197     AbstractHeap(WTF::HashTableDeletedValueType)
 198     {
 199         m_value = encode(InvalidAbstractHeap, Payload::top());
 200     }
 201
 202     bool operator!() const { return kind() == InvalidAbstractHeap && !payloadImpl().isTop(); }
 203
 204     AbstractHeapKind kind() const { return static_cast<AbstractHeapKind>(m_value & ((1 << topShift) - 1)); }
 205     Payload payload() const
 206     {
 207         ASSERT(kind() != World && kind() != InvalidAbstractHeap);
 208         return payloadImpl();
 209     }
 210
 211     AbstractHeap supertype() const
 212     {
 213         ASSERT(kind() != InvalidAbstractHeap);
 214         switch (kind()) {
 215         case World:
 216             return AbstractHeap();
 217         case Heap:
 218         case SideState:
 219             return World;
 220         default:
 221             if (payload().isTop()) {
 222                 if (kind() == Stack)
 223                     return World;
 224                 return Heap;
 225             }
 226             return AbstractHeap(kind());
 227         }
 228     }
 229
 230     bool isStrictSubtypeOf(const AbstractHeap& other) const
 231     {
 232         AbstractHeap current = *this;
 233         while (current.kind() != World) {
 234             current = current.supertype();
 235             if (current == other)
 236                 return true;
 237         }
 238         return false;
 239     }
 240
 241     bool isSubtypeOf(const AbstractHeap& other) const
 242     {
 243         return *this == other || isStrictSubtypeOf(other);
 244     }
 245
 246     bool overlaps(const AbstractHeap& other) const
 247     {
 248         return *this == other || isStrictSubtypeOf(other) || other.isStrictSubtypeOf(*this);
 249     }
 250
 251     bool isDisjoint(const AbstractHeap& other) const
 252     {
 253         return !overlaps(other);
 254     }
 255
 256     unsigned hash() const
 257     {
 258         return WTF::IntHash<int64_t>::hash(m_value);
 259     }
 260
 261     bool operator==(const AbstractHeap& other) const
 262     {
 263         return m_value == other.m_value;
 264     }
 265
 266     bool operator!=(const AbstractHeap& other) const
 267     {
 268         return !(*this == other);
 269     }
 270
 271     bool operator<(const AbstractHeap& other) const
 272     {
 273         if (kind() != other.kind())
 274             return kind() < other.kind();
 275         return payload() < other.payload();
 276     }
 277
 278     bool isHashTableDeletedValue() const
 279     {
 280         return kind() == InvalidAbstractHeap && payloadImpl().isTop();
 281     }
 282
 283     void dump(PrintStream& out) const;
 284
 285 private:
 286     static const unsigned valueShift = 15;
 287     static const unsigned topShift = 14;
 288
 289     Payload payloadImpl() const
 290     {
 291         return Payload((m_value >> topShift) & 1, m_value >> valueShift);
 292     }
 293
 294     static int64_t encode(AbstractHeapKind kind, Payload payload)
 295     {
 296         int64_t kindAsInt = static_cast<int64_t>(kind);
 297         ASSERT(kindAsInt < (1 << topShift));
 298         return kindAsInt | (payload.isTop() << topShift) | (payload.valueImpl() << valueShift);
 299     }
 300
 301     // The layout of the value is:
 302     // Low 14 bits: the Kind
 303     // 15th bit: whether or not the payload is TOP.
 304     // The upper bits: the payload.value().
 305     int64_t m_value;
 306 };
 307
 308 struct AbstractHeapHash {
 309     static unsigned hash(const AbstractHeap& key) { return key.hash(); }
 310     static bool equal(const AbstractHeap& a, const AbstractHeap& b) { return a == b; }
 311     static const bool safeToCompareToEmptyOrDeleted = true;
 312 };
 313
 314 } } // namespace JSC::DFG
 315
 316 namespace WTF {
 317
 318 void printInternal(PrintStream&, JSC::DFG::AbstractHeapKind);
 319
 320 template<typename T> struct DefaultHash;
 321 template<> struct DefaultHash<JSC::DFG::AbstractHeap> {
 322     typedef JSC::DFG::AbstractHeapHash Hash;
 323 };
 324
 325 template<typename T> struct HashTraits;
 326 template<> struct HashTraits<JSC::DFG::AbstractHeap> : SimpleClassHashTraits<JSC::DFG::AbstractHeap> { };
 327
 328 } // namespace WTF
 329
 330 #endif // ENABLE(DFG_JIT)
 331
 332 #endif // DFGAbstractHeap_h
 333