dfg/DFGAbstractValue.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 DFGAbstractValue_h
  27 #define DFGAbstractValue_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "ArrayProfile.h"
  32 #include "DFGFiltrationResult.h"
  33 #include "DFGFrozenValue.h"
  34 #include "DFGNodeFlags.h"
  35 #include "DFGStructureAbstractValue.h"
  36 #include "DFGStructureClobberState.h"
  37 #include "JSCell.h"
  38 #include "SpeculatedType.h"
  39 #include "DumpContext.h"
  40 #include "StructureSet.h"
  41
  42 namespace JSC {
  43
  44 class TrackedReferences;
  45
  46 namespace DFG {
  47
  48 class Graph;
  49 struct Node;
  50
  51 struct AbstractValue {
  52     AbstractValue()
  53         : m_type(SpecNone)
  54         , m_arrayModes(0)
  55     {
  56     }
  57
  58     void clear()
  59     {
  60         m_type = SpecNone;
  61         m_arrayModes = 0;
  62         m_structure.clear();
  63         m_value = JSValue();
  64         checkConsistency();
  65     }
  66
  67     bool isClear() const { return m_type == SpecNone; }
  68     bool operator!() const { return isClear(); }
  69
  70     void makeHeapTop()
  71     {
  72         makeTop(SpecHeapTop);
  73     }
  74
  75     void makeBytecodeTop()
  76     {
  77         makeTop(SpecBytecodeTop);
  78     }
  79
  80     void makeFullTop()
  81     {
  82         makeTop(SpecFullTop);
  83     }
  84
  85     void clobberStructures()
  86     {
  87         if (m_type & SpecCell) {
  88             m_structure.clobber();
  89             clobberArrayModes();
  90         } else {
  91             ASSERT(m_structure.isClear());
  92             ASSERT(!m_arrayModes);
  93         }
  94         checkConsistency();
  95     }
  96
  97     static void clobberStructuresFor(AbstractValue& value)
  98     {
  99         value.clobberStructures();
 100     }
 101
 102     void observeInvalidationPoint()
 103     {
 104         m_structure.observeInvalidationPoint();
 105         checkConsistency();
 106     }
 107
 108     static void observeInvalidationPointFor(AbstractValue& value)
 109     {
 110         value.observeInvalidationPoint();
 111     }
 112
 113     void observeTransition(Structure* from, Structure* to)
 114     {
 115         if (m_type & SpecCell) {
 116             m_structure.observeTransition(from, to);
 117             observeIndexingTypeTransition(from->indexingType(), to->indexingType());
 118         }
 119         checkConsistency();
 120     }
 121
 122     void observeTransitions(const TransitionVector& vector);
 123
 124     class TransitionObserver {
 125     public:
 126         TransitionObserver(Structure* from, Structure* to)
 127             : m_from(from)
 128             , m_to(to)
 129         {
 130         }
 131
 132         void operator()(AbstractValue& value)
 133         {
 134             value.observeTransition(m_from, m_to);
 135         }
 136     private:
 137         Structure* m_from;
 138         Structure* m_to;
 139     };
 140
 141     class TransitionsObserver {
 142     public:
 143         TransitionsObserver(const TransitionVector& vector)
 144             : m_vector(vector)
 145         {
 146         }
 147
 148         void operator()(AbstractValue& value)
 149         {
 150             value.observeTransitions(m_vector);
 151         }
 152     private:
 153         const TransitionVector& m_vector;
 154     };
 155
 156     void clobberValue()
 157     {
 158         m_value = JSValue();
 159     }
 160
 161     bool isHeapTop() const
 162     {
 163         return (m_type | SpecHeapTop) == m_type
 164             && m_structure.isTop()
 165             && m_arrayModes == ALL_ARRAY_MODES
 166             && !m_value;
 167     }
 168
 169     bool valueIsTop() const
 170     {
 171         return !m_value && m_type;
 172     }
 173
 174     JSValue value() const
 175     {
 176         return m_value;
 177     }
 178
 179     static AbstractValue heapTop()
 180     {
 181         AbstractValue result;
 182         result.makeHeapTop();
 183         return result;
 184     }
 185
 186     static AbstractValue bytecodeTop()
 187     {
 188         AbstractValue result;
 189         result.makeBytecodeTop();
 190         return result;
 191     }
 192
 193     static AbstractValue fullTop()
 194     {
 195         AbstractValue result;
 196         result.makeFullTop();
 197         return result;
 198     }
 199
 200     void set(Graph&, const FrozenValue&, StructureClobberState);
 201     void set(Graph&, Structure*);
 202     void set(Graph&, const StructureSet&);
 203
 204     // Set this value to represent the given set of types as precisely as possible.
 205     void setType(Graph&, SpeculatedType);
 206
 207     // As above, but only valid for non-cell types.
 208     void setType(SpeculatedType type)
 209     {
 210         RELEASE_ASSERT(!(type & SpecCell));
 211         m_structure.clear();
 212         m_arrayModes = 0;
 213         m_type = type;
 214         m_value = JSValue();
 215         checkConsistency();
 216     }
 217
 218     void fixTypeForRepresentation(Graph&, NodeFlags representation, Node* = nullptr);
 219     void fixTypeForRepresentation(Graph&, Node*);
 220
 221     bool operator==(const AbstractValue& other) const
 222     {
 223         return m_type == other.m_type
 224             && m_arrayModes == other.m_arrayModes
 225             && m_structure == other.m_structure
 226             && m_value == other.m_value;
 227     }
 228     bool operator!=(const AbstractValue& other) const
 229     {
 230         return !(*this == other);
 231     }
 232
 233     bool merge(const AbstractValue& other)
 234     {
 235         if (other.isClear())
 236             return false;
 237
 238 #if !ASSERT_DISABLED
 239         AbstractValue oldMe = *this;
 240 #endif
 241         bool result = false;
 242         if (isClear()) {
 243             *this = other;
 244             result = !other.isClear();
 245         } else {
 246             result |= mergeSpeculation(m_type, other.m_type);
 247             result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
 248             result |= m_structure.merge(other.m_structure);
 249             if (m_value != other.m_value) {
 250                 result |= !!m_value;
 251                 m_value = JSValue();
 252             }
 253         }
 254         checkConsistency();
 255         ASSERT(result == (*this != oldMe));
 256         return result;
 257     }
 258
 259     bool mergeOSREntryValue(Graph&, JSValue);
 260
 261     void merge(SpeculatedType type)
 262     {
 263         mergeSpeculation(m_type, type);
 264
 265         if (type & SpecCell) {
 266             m_structure.makeTop();
 267             m_arrayModes = ALL_ARRAY_MODES;
 268         }
 269         m_value = JSValue();
 270
 271         checkConsistency();
 272     }
 273
 274     bool couldBeType(SpeculatedType desiredType) const
 275     {
 276         return !!(m_type & desiredType);
 277     }
 278
 279     bool isType(SpeculatedType desiredType) const
 280     {
 281         return !(m_type & ~desiredType);
 282     }
 283
 284     FiltrationResult filter(Graph&, const StructureSet&);
 285     FiltrationResult filterArrayModes(ArrayModes);
 286     FiltrationResult filter(SpeculatedType);
 287     FiltrationResult filterByValue(const FrozenValue& value);
 288     FiltrationResult filter(const AbstractValue&);
 289
 290     FiltrationResult changeStructure(Graph&, const StructureSet&);
 291
 292     bool contains(Structure*) const;
 293
 294     bool validate(JSValue value) const
 295     {
 296         if (isHeapTop())
 297             return true;
 298
 299         if (!!m_value && m_value != value)
 300             return false;
 301
 302         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
 303             return false;
 304
 305         if (value.isEmpty()) {
 306             ASSERT(m_type & SpecEmpty);
 307             return true;
 308         }
 309
 310         if (!!value && value.isCell()) {
 311             ASSERT(m_type & SpecCell);
 312             Structure* structure = value.asCell()->structure();
 313             return m_structure.contains(structure)
 314                 && (m_arrayModes & asArrayModes(structure->indexingType()));
 315         }
 316
 317         return true;
 318     }
 319
 320     bool hasClobberableState() const
 321     {
 322         return m_structure.isNeitherClearNorTop()
 323             || !arrayModesAreClearOrTop(m_arrayModes);
 324     }
 325
 326 #if ASSERT_DISABLED
 327     void checkConsistency() const { }
 328     void assertIsRegistered(Graph&) const { }
 329 #else
 330     void checkConsistency() const;
 331     void assertIsRegistered(Graph&) const;
 332 #endif
 333
 334     void dumpInContext(PrintStream&, DumpContext*) const;
 335     void dump(PrintStream&) const;
 336
 337     void validateReferences(const TrackedReferences&);
 338
 339     // This is a proven constraint on the structures that this value can have right
 340     // now. The structure of the current value must belong to this set. The set may
 341     // be TOP, indicating that it is the set of all possible structures, in which
 342     // case the current value can have any structure. The set may be BOTTOM (empty)
 343     // in which case this value cannot be a cell. This is all subject to change
 344     // anytime a new value is assigned to this one, anytime there is a control flow
 345     // merge, or most crucially, anytime a side-effect or structure check happens.
 346     // In case of a side-effect, we must assume that any value with a structure that
 347     // isn't being watched may have had its structure changed, hence contravening
 348     // our proof. In such a case we make the proof valid again by switching this to
 349     // TOP (i.e. claiming that we have proved that this value may have any
 350     // structure).
 351     StructureAbstractValue m_structure;
 352
 353     // This is a proven constraint on the possible types that this value can have
 354     // now or any time in the future, unless it is reassigned. This field is
 355     // impervious to side-effects. The relationship between this field, and the
 356     // structure fields above, is as follows. The fields above constraint the
 357     // structures that a cell may have, but they say nothing about whether or not
 358     // the value is known to be a cell. More formally, the m_structure is itself an
 359     // abstract value that consists of the union of the set of all non-cell values
 360     // and the set of cell values that have the given structure. This abstract
 361     // value is then the intersection of the m_structure and the set of values
 362     // whose type is m_type. So, for example if m_type is SpecFinal|SpecInt32 and
 363     // m_structure is [0x12345] then this abstract value corresponds to the set of
 364     // all integers unified with the set of all objects with structure 0x12345.
 365     SpeculatedType m_type;
 366
 367     // This is a proven constraint on the possible indexing types that this value
 368     // can have right now. It also implicitly constraints the set of structures
 369     // that the value may have right now, since a structure has an immutable
 370     // indexing type. This is subject to change upon reassignment, or any side
 371     // effect that makes non-obvious changes to the heap.
 372     ArrayModes m_arrayModes;
 373
 374     // This is a proven constraint on the possible values that this value can
 375     // have now or any time in the future, unless it is reassigned. Note that this
 376     // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
 377     // means either BOTTOM or TOP depending on the state of m_type: if m_type is
 378     // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
 379     // means TOP. Also note that this value isn't necessarily known to the GC
 380     // (strongly or even weakly - it may be an "fragile" value, see
 381     // DFGValueStrength.h). If you perform any optimization based on a cell m_value
 382     // that requires that the value be kept alive, you must call freeze() on that
 383     // value, which will turn it into a weak value.
 384     JSValue m_value;
 385
 386 private:
 387     void clobberArrayModes()
 388     {
 389         // FIXME: We could make this try to predict the set of array modes that this object
 390         // could have in the future. For now, just do the simple thing.
 391         m_arrayModes = ALL_ARRAY_MODES;
 392     }
 393
 394     void observeIndexingTypeTransition(IndexingType from, IndexingType to)
 395     {
 396         if (m_arrayModes & asArrayModes(from))
 397             m_arrayModes |= asArrayModes(to);
 398     }
 399
 400     bool validateType(JSValue value) const
 401     {
 402         if (isHeapTop())
 403             return true;
 404
 405         // Constant folding always represents Int52's in a double (i.e. Int52AsDouble).
 406         // So speculationFromValue(value) for an Int52 value will return Int52AsDouble,
 407         // and that's fine - the type validates just fine.
 408         SpeculatedType type = m_type;
 409         if (type & SpecInt52)
 410             type |= SpecInt52AsDouble;
 411
 412         if (mergeSpeculations(type, speculationFromValue(value)) != type)
 413             return false;
 414
 415         if (value.isEmpty()) {
 416             ASSERT(m_type & SpecEmpty);
 417             return true;
 418         }
 419
 420         return true;
 421     }
 422
 423     void makeTop(SpeculatedType top)
 424     {
 425         m_type |= top;
 426         m_arrayModes = ALL_ARRAY_MODES;
 427         m_structure.makeTop();
 428         m_value = JSValue();
 429         checkConsistency();
 430     }
 431
 432     void filterValueByType();
 433     void filterArrayModesByType();
 434
 435     bool shouldBeClear() const;
 436     FiltrationResult normalizeClarity();
 437     FiltrationResult normalizeClarity(Graph&);
 438 };
 439
 440 } } // namespace JSC::DFG
 441
 442 #endif // ENABLE(DFG_JIT)
 443
 444 #endif // DFGAbstractValue_h
 445
 446