dfg/DFGAbstractHeap.h

   1 /*
   2  * Copyright (C) 2013 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 three-level type hierarchy:
  38 // - World is the supertype of all of the things.
  39 // - Kind with TOP payload is the direct subtype of World.
  40 // - Kind with non-TOP payload is the direct subtype of its corresponding TOP Kind.
  41
  42 #define FOR_EACH_ABSTRACT_HEAP_KIND(macro) \
  43     macro(InvalidAbstractHeap) \
  44     macro(World) \
  45     macro(Arguments_numArguments) \
  46     macro(Arguments_overrideLength) \
  47     macro(Arguments_registers) \
  48     macro(Arguments_slowArguments) \
  49     macro(ArrayBuffer_data) \
  50     macro(Butterfly_arrayBuffer) \
  51     macro(Butterfly_publicLength) \
  52     macro(Butterfly_vectorLength) \
  53     macro(JSArrayBufferView_length) \
  54     macro(JSArrayBufferView_mode) \
  55     macro(JSArrayBufferView_vector) \
  56     macro(JSCell_structureID) \
  57     macro(JSCell_indexingType) \
  58     macro(JSCell_typeInfoFlags) \
  59     macro(JSCell_typeInfoType) \
  60     macro(JSFunction_executable) \
  61     macro(JSFunction_scopeChain) \
  62     macro(JSObject_butterfly) \
  63     macro(JSVariableObject_registers) \
  64     macro(NamedProperties) \
  65     macro(IndexedInt32Properties) \
  66     macro(IndexedDoubleProperties) \
  67     macro(IndexedContiguousProperties) \
  68     macro(ArrayStorageProperties) \
  69     macro(Variables) \
  70     macro(TypedArrayProperties) \
  71     macro(GCState) \
  72     macro(BarrierState) \
  73     macro(RegExpState) \
  74     macro(InternalState) \
  75     macro(Absolute) \
  76     /* 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. */\
  77     macro(Watchpoint_fire) \
  78     /* Use this for reads only, just to indicate that if the world got clobbered, then this operation will not work. */\
  79     macro(MiscFields) \
  80     /* 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. */\
  81     macro(SideState)
  82
  83 enum AbstractHeapKind {
  84 #define ABSTRACT_HEAP_DECLARATION(name) name,
  85     FOR_EACH_ABSTRACT_HEAP_KIND(ABSTRACT_HEAP_DECLARATION)
  86 #undef ABSTRACT_HEAP_DECLARATION
  87 };
  88
  89 class AbstractHeap {
  90 public:
  91     class Payload {
  92     public:
  93         Payload()
  94             : m_isTop(false)
  95             , m_value(0)
  96         {
  97         }
  98
  99         Payload(bool isTop, int64_t value)
 100             : m_isTop(isTop)
 101             , m_value(value)
 102         {
 103             ASSERT(!(isTop && value));
 104         }
 105
 106         Payload(int64_t value)
 107             : m_isTop(false)
 108             , m_value(value)
 109         {
 110         }
 111
 112         Payload(const void* pointer)
 113             : m_isTop(false)
 114             , m_value(bitwise_cast<intptr_t>(pointer))
 115         {
 116         }
 117
 118         Payload(VirtualRegister operand)
 119             : m_isTop(false)
 120             , m_value(operand.offset())
 121         {
 122         }
 123
 124         static Payload top() { return Payload(true, 0); }
 125
 126         bool isTop() const { return m_isTop; }
 127         int64_t value() const
 128         {
 129             ASSERT(!isTop());
 130             return valueImpl();
 131         }
 132         int64_t valueImpl() const
 133         {
 134             return m_value;
 135         }
 136
 137         bool operator==(const Payload& other) const
 138         {
 139             return m_isTop == other.m_isTop
 140                 && m_value == other.m_value;
 141         }
 142
 143         bool operator!=(const Payload& other) const
 144         {
 145             return !(*this == other);
 146         }
 147
 148         bool operator<(const Payload& other) const
 149         {
 150             if (isTop())
 151                 return !other.isTop();
 152             if (other.isTop())
 153                 return false;
 154             return value() < other.value();
 155         }
 156
 157         bool isDisjoint(const Payload& other) const
 158         {
 159             if (isTop())
 160                 return false;
 161             if (other.isTop())
 162                 return false;
 163             return m_value != other.m_value;
 164         }
 165
 166         bool overlaps(const Payload& other) const
 167         {
 168             return !isDisjoint(other);
 169         }
 170
 171         void dump(PrintStream&) const;
 172
 173     private:
 174         bool m_isTop;
 175         int64_t m_value;
 176     };
 177
 178     AbstractHeap()
 179     {
 180         m_value = encode(InvalidAbstractHeap, Payload());
 181     }
 182
 183     AbstractHeap(AbstractHeapKind kind)
 184     {
 185         ASSERT(kind != InvalidAbstractHeap);
 186         m_value = encode(kind, Payload::top());
 187     }
 188
 189     AbstractHeap(AbstractHeapKind kind, Payload payload)
 190     {
 191         ASSERT(kind != InvalidAbstractHeap && kind != World);
 192         m_value = encode(kind, payload);
 193     }
 194
 195     AbstractHeap(WTF::HashTableDeletedValueType)
 196     {
 197         m_value = encode(InvalidAbstractHeap, Payload::top());
 198     }
 199
 200     bool operator!() const { return kind() == InvalidAbstractHeap && !payloadImpl().isTop(); }
 201
 202     AbstractHeapKind kind() const { return static_cast<AbstractHeapKind>(m_value & ((1 << topShift) - 1)); }
 203     Payload payload() const
 204     {
 205         ASSERT(kind() != World && kind() != InvalidAbstractHeap);
 206         return payloadImpl();
 207     }
 208
 209     bool isDisjoint(const AbstractHeap& other)
 210     {
 211         ASSERT(kind() != InvalidAbstractHeap);
 212         ASSERT(other.kind() != InvalidAbstractHeap);
 213         if (kind() == World)
 214             return false;
 215         if (other.kind() == World)
 216             return false;
 217         if (kind() != other.kind())
 218             return true;
 219         return payload().isDisjoint(other.payload());
 220     }
 221
 222     bool overlaps(const AbstractHeap& other)
 223     {
 224         return !isDisjoint(other);
 225     }
 226
 227     AbstractHeap supertype() const
 228     {
 229         ASSERT(kind() != InvalidAbstractHeap);
 230         if (kind() == World)
 231             return AbstractHeap();
 232         if (payload().isTop())
 233             return World;
 234         return AbstractHeap(kind());
 235     }
 236
 237     unsigned hash() const
 238     {
 239         return WTF::IntHash<int64_t>::hash(m_value);
 240     }
 241
 242     bool operator==(const AbstractHeap& other) const
 243     {
 244         return m_value == other.m_value;
 245     }
 246
 247     bool operator!=(const AbstractHeap& other) const
 248     {
 249         return !(*this == other);
 250     }
 251
 252     bool operator<(const AbstractHeap& other) const
 253     {
 254         if (kind() != other.kind())
 255             return kind() < other.kind();
 256         return payload() < other.payload();
 257     }
 258
 259     bool isHashTableDeletedValue() const
 260     {
 261         return kind() == InvalidAbstractHeap && payloadImpl().isTop();
 262     }
 263
 264     void dump(PrintStream& out) const;
 265
 266 private:
 267     static const unsigned valueShift = 15;
 268     static const unsigned topShift = 14;
 269
 270     Payload payloadImpl() const
 271     {
 272         return Payload((m_value >> topShift) & 1, m_value >> valueShift);
 273     }
 274
 275     static int64_t encode(AbstractHeapKind kind, Payload payload)
 276     {
 277         int64_t kindAsInt = static_cast<int64_t>(kind);
 278         ASSERT(kindAsInt < (1 << topShift));
 279         return kindAsInt | (payload.isTop() << topShift) | (payload.valueImpl() << valueShift);
 280     }
 281
 282     // The layout of the value is:
 283     // Low 14 bits: the Kind
 284     // 15th bit: whether or not the payload is TOP.
 285     // The upper bits: the payload.value().
 286     int64_t m_value;
 287 };
 288
 289 struct AbstractHeapHash {
 290     static unsigned hash(const AbstractHeap& key) { return key.hash(); }
 291     static bool equal(const AbstractHeap& a, const AbstractHeap& b) { return a == b; }
 292     static const bool safeToCompareToEmptyOrDeleted = true;
 293 };
 294
 295 } } // namespace JSC::DFG
 296
 297 namespace WTF {
 298
 299 void printInternal(PrintStream&, JSC::DFG::AbstractHeapKind);
 300
 301 template<typename T> struct DefaultHash;
 302 template<> struct DefaultHash<JSC::DFG::AbstractHeap> {
 303     typedef JSC::DFG::AbstractHeapHash Hash;
 304 };
 305
 306 template<typename T> struct HashTraits;
 307 template<> struct HashTraits<JSC::DFG::AbstractHeap> : SimpleClassHashTraits<JSC::DFG::AbstractHeap> { };
 308
 309 } // namespace WTF
 310
 311 #endif // ENABLE(DFG_JIT)
 312
 313 #endif // DFGAbstractHeap_h
 314