dfg/DFGStructureAbstractValue.h

   1 /*
   2  * Copyright (C) 2011-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 DFGStructureAbstractValue_h
  27 #define DFGStructureAbstractValue_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGTransition.h"
  32 #include "JSCell.h"
  33 #include "SpeculatedType.h"
  34 #include "DumpContext.h"
  35 #include "StructureSet.h"
  36
  37 namespace JSC {
  38
  39 class TrackedReferences;
  40
  41 namespace DFG {
  42
  43 class StructureAbstractValue {
  44 public:
  45     StructureAbstractValue() { }
  46     StructureAbstractValue(Structure* structure)
  47         : m_set(StructureSet(structure))
  48     {
  49         setClobbered(false);
  50     }
  51     StructureAbstractValue(const StructureSet& other)
  52         : m_set(other)
  53     {
  54         setClobbered(false);
  55     }
  56     ALWAYS_INLINE StructureAbstractValue(const StructureAbstractValue& other)
  57         : m_set(other.m_set)
  58     {
  59         setClobbered(other.isClobbered());
  60     }
  61
  62     ALWAYS_INLINE StructureAbstractValue& operator=(Structure* structure)
  63     {
  64         m_set = StructureSet(structure);
  65         setClobbered(false);
  66         return *this;
  67     }
  68     ALWAYS_INLINE StructureAbstractValue& operator=(const StructureSet& other)
  69     {
  70         m_set = other;
  71         setClobbered(false);
  72         return *this;
  73     }
  74     ALWAYS_INLINE StructureAbstractValue& operator=(const StructureAbstractValue& other)
  75     {
  76         m_set = other.m_set;
  77         setClobbered(other.isClobbered());
  78         return *this;
  79     }
  80
  81     void clear()
  82     {
  83         m_set.clear();
  84         setClobbered(false);
  85     }
  86
  87     void makeTop()
  88     {
  89         m_set.deleteListIfNecessary();
  90         m_set.m_pointer = topValue;
  91     }
  92
  93 #if ASSERT_DISABLED
  94     void assertIsRegistered(Graph&) const { }
  95 #else
  96     void assertIsRegistered(Graph&) const;
  97 #endif
  98
  99     void clobber();
 100     void observeInvalidationPoint() { setClobbered(false); }
 101
 102     void observeTransition(Structure* from, Structure* to);
 103     void observeTransitions(const TransitionVector&);
 104
 105     static StructureAbstractValue top()
 106     {
 107         StructureAbstractValue result;
 108         result.m_set.m_pointer = topValue;
 109         return result;
 110     }
 111
 112     bool isClear() const { return m_set.isEmpty(); }
 113     bool isTop() const { return m_set.m_pointer == topValue; }
 114     bool isNeitherClearNorTop() const { return !isClear() && !isTop(); }
 115
 116     // A clobbered abstract value means that the set currently contains the m_set set of
 117     // structures plus TOP, except that the "plus TOP" will go away at the next invalidation
 118     // point. Note that it's tempting to think of this as "the set of structures in m_set plus
 119     // the set of structures transition-reachable from m_set" - but this isn't really correct,
 120     // since if we add an unwatchable structure after clobbering, the two definitions are not
 121     // equivalent. If we do this, the new unwatchable structure will be added to m_set.
 122     // Invalidation points do not try to "clip" the set of transition-reachable structures from
 123     // m_set by looking at reachability as this would mean that the new set is TOP. Instead they
 124     // literally assume that the set is just m_set rather than m_set plus TOP.
 125     bool isClobbered() const { return m_set.getReservedFlag(); }
 126
 127     bool add(Structure* structure);
 128
 129     bool merge(const StructureSet& other);
 130
 131     ALWAYS_INLINE bool merge(const StructureAbstractValue& other)
 132     {
 133         if (other.isClear())
 134             return false;
 135
 136         if (isTop())
 137             return false;
 138
 139         if (other.isTop()) {
 140             makeTop();
 141             return true;
 142         }
 143
 144         return mergeSlow(other);
 145     }
 146
 147     void filter(const StructureSet& other);
 148     void filter(const StructureAbstractValue& other);
 149
 150     ALWAYS_INLINE void filter(SpeculatedType type)
 151     {
 152         if (!(type & SpecCell)) {
 153             clear();
 154             return;
 155         }
 156         if (isNeitherClearNorTop())
 157             filterSlow(type);
 158     }
 159
 160     ALWAYS_INLINE bool operator==(const StructureAbstractValue& other) const
 161     {
 162         if ((m_set.isThin() && other.m_set.isThin()) || isTop() || other.isTop())
 163             return m_set.m_pointer == other.m_set.m_pointer;
 164
 165         return equalsSlow(other);
 166     }
 167
 168     const StructureSet& set() const
 169     {
 170         ASSERT(!isTop());
 171         return m_set;
 172     }
 173
 174     size_t size() const
 175     {
 176         ASSERT(!isTop());
 177         return m_set.size();
 178     }
 179
 180     Structure* at(size_t i) const
 181     {
 182         ASSERT(!isTop());
 183         return m_set.at(i);
 184     }
 185
 186     Structure* operator[](size_t i) const { return at(i); }
 187
 188     // In most cases, what you really want to do is verify whether the set is top or clobbered, and
 189     // if not, enumerate the set of structures. Use this only in cases where the singleton case is
 190     // meaningfully special, like for transitions.
 191     Structure* onlyStructure() const
 192     {
 193         if (isTop() || isClobbered())
 194             return nullptr;
 195         return m_set.onlyStructure();
 196     }
 197
 198     void dumpInContext(PrintStream&, DumpContext*) const;
 199     void dump(PrintStream&) const;
 200
 201     // The methods below are all conservative and err on the side of making 'this' appear bigger
 202     // than it is. For example, contains() may return true if the set is clobbered or TOP.
 203     // isSubsetOf() may return false in case of ambiguities. Therefore you should only perform
 204     // optimizations as a consequence of the "this is smaller" return value - so false for
 205     // contains(), true for isSubsetOf(), false for isSupersetOf(), and false for overlaps().
 206
 207     bool contains(Structure* structure) const;
 208
 209     bool isSubsetOf(const StructureSet& other) const;
 210     bool isSubsetOf(const StructureAbstractValue& other) const;
 211
 212     bool isSupersetOf(const StructureSet& other) const;
 213     bool isSupersetOf(const StructureAbstractValue& other) const
 214     {
 215         return other.isSubsetOf(*this);
 216     }
 217
 218     bool overlaps(const StructureSet& other) const;
 219     bool overlaps(const StructureAbstractValue& other) const;
 220
 221     void validateReferences(const TrackedReferences&) const;
 222
 223 private:
 224     static const uintptr_t clobberedFlag = StructureSet::reservedFlag;
 225     static const uintptr_t topValue = StructureSet::reservedValue;
 226     static const unsigned polymorphismLimit = 10;
 227     static const unsigned clobberedSupremacyThreshold = 2;
 228
 229     void filterSlow(SpeculatedType type);
 230     bool mergeSlow(const StructureAbstractValue& other);
 231
 232     bool equalsSlow(const StructureAbstractValue& other) const;
 233
 234     void makeTopWhenThin()
 235     {
 236         ASSERT(m_set.isThin());
 237         m_set.m_pointer = topValue;
 238     }
 239
 240     bool mergeNotTop(const StructureSet& other);
 241
 242     void setClobbered(bool clobbered)
 243     {
 244         ASSERT(!isTop() || !clobbered);
 245         m_set.setReservedFlag(clobbered);
 246     }
 247
 248     StructureSet m_set;
 249 };
 250
 251 } } // namespace JSC::DFG
 252
 253 #endif // ENABLE(DFG_JIT)
 254
 255 #endif // DFGStructureAbstractValue_h
 256
 257