dfg/DFGAbstractValue.h

   1 /*
   2  * Copyright (C) 2011, 2012, 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 DFGAbstractValue_h
  27 #define DFGAbstractValue_h
  28
  29 #include <wtf/Platform.h>
  30
  31 #if ENABLE(DFG_JIT)
  32
  33 #include "ArrayProfile.h"
  34 #include "DFGStructureAbstractValue.h"
  35 #include "JSCell.h"
  36 #include "SpeculatedType.h"
  37 #include "StructureSet.h"
  38
  39 namespace JSC { namespace DFG {
  40
  41 struct AbstractValue {
  42     AbstractValue()
  43         : m_type(SpecNone)
  44         , m_arrayModes(0)
  45     {
  46     }
  47
  48     void clear()
  49     {
  50         m_type = SpecNone;
  51         m_arrayModes = 0;
  52         m_currentKnownStructure.clear();
  53         m_futurePossibleStructure.clear();
  54         m_value = JSValue();
  55         checkConsistency();
  56     }
  57
  58     bool isClear() const
  59     {
  60         bool result = m_type == SpecNone && !m_arrayModes && m_currentKnownStructure.isClear() && m_futurePossibleStructure.isClear();
  61         if (result)
  62             ASSERT(!m_value);
  63         return result;
  64     }
  65
  66     void makeTop()
  67     {
  68         m_type |= SpecTop; // The state may have included SpecEmpty, in which case we want this to become SpecEmptyOrTop.
  69         m_arrayModes = ALL_ARRAY_MODES;
  70         m_currentKnownStructure.makeTop();
  71         m_futurePossibleStructure.makeTop();
  72         m_value = JSValue();
  73         checkConsistency();
  74     }
  75
  76     void clobberStructures()
  77     {
  78         if (m_type & SpecCell) {
  79             m_currentKnownStructure.makeTop();
  80             clobberArrayModes();
  81         } else {
  82             ASSERT(m_currentKnownStructure.isClear());
  83             ASSERT(!m_arrayModes);
  84         }
  85         checkConsistency();
  86     }
  87
  88     void clobberValue()
  89     {
  90         m_value = JSValue();
  91     }
  92
  93     bool isTop() const
  94     {
  95         return m_type == SpecTop && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop();
  96     }
  97
  98     bool valueIsTop() const
  99     {
 100         return !m_value && m_type;
 101     }
 102
 103     JSValue value() const
 104     {
 105         return m_value;
 106     }
 107
 108     static AbstractValue top()
 109     {
 110         AbstractValue result;
 111         result.makeTop();
 112         return result;
 113     }
 114
 115     void setMostSpecific(JSValue value)
 116     {
 117         if (!!value && value.isCell()) {
 118             Structure* structure = value.asCell()->structure();
 119             m_currentKnownStructure = structure;
 120             setFuturePossibleStructure(structure);
 121             m_arrayModes = asArrayModes(structure->indexingType());
 122         } else {
 123             m_currentKnownStructure.clear();
 124             m_futurePossibleStructure.clear();
 125             m_arrayModes = 0;
 126         }
 127
 128         m_type = speculationFromValue(value);
 129         m_value = value;
 130
 131         checkConsistency();
 132     }
 133
 134     void set(JSValue value)
 135     {
 136         if (!!value && value.isCell()) {
 137             m_currentKnownStructure.makeTop();
 138             Structure* structure = value.asCell()->structure();
 139             setFuturePossibleStructure(structure);
 140             m_arrayModes = asArrayModes(structure->indexingType());
 141             clobberArrayModes();
 142         } else {
 143             m_currentKnownStructure.clear();
 144             m_futurePossibleStructure.clear();
 145             m_arrayModes = 0;
 146         }
 147
 148         m_type = speculationFromValue(value);
 149         m_value = value;
 150
 151         checkConsistency();
 152     }
 153
 154     void set(Structure* structure)
 155     {
 156         m_currentKnownStructure = structure;
 157         setFuturePossibleStructure(structure);
 158         m_arrayModes = asArrayModes(structure->indexingType());
 159         m_type = speculationFromStructure(structure);
 160         m_value = JSValue();
 161
 162         checkConsistency();
 163     }
 164
 165     void set(SpeculatedType type)
 166     {
 167         if (type & SpecCell) {
 168             m_currentKnownStructure.makeTop();
 169             m_futurePossibleStructure.makeTop();
 170             m_arrayModes = ALL_ARRAY_MODES;
 171         } else {
 172             m_currentKnownStructure.clear();
 173             m_futurePossibleStructure.clear();
 174             m_arrayModes = 0;
 175         }
 176         m_type = type;
 177         m_value = JSValue();
 178         checkConsistency();
 179     }
 180
 181     bool operator==(const AbstractValue& other) const
 182     {
 183         return m_type == other.m_type
 184             && m_arrayModes == other.m_arrayModes
 185             && m_currentKnownStructure == other.m_currentKnownStructure
 186             && m_futurePossibleStructure == other.m_futurePossibleStructure
 187             && m_value == other.m_value;
 188     }
 189     bool operator!=(const AbstractValue& other) const
 190     {
 191         return !(*this == other);
 192     }
 193
 194     bool merge(const AbstractValue& other)
 195     {
 196         if (other.isClear())
 197             return false;
 198
 199 #if !ASSERT_DISABLED
 200         AbstractValue oldMe = *this;
 201 #endif
 202         bool result = false;
 203         if (isClear()) {
 204             *this = other;
 205             result = !other.isClear();
 206         } else {
 207             result |= mergeSpeculation(m_type, other.m_type);
 208             result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
 209             result |= m_currentKnownStructure.addAll(other.m_currentKnownStructure);
 210             result |= m_futurePossibleStructure.addAll(other.m_futurePossibleStructure);
 211             if (m_value != other.m_value) {
 212                 result |= !!m_value;
 213                 m_value = JSValue();
 214             }
 215         }
 216         checkConsistency();
 217         ASSERT(result == (*this != oldMe));
 218         return result;
 219     }
 220
 221     void merge(SpeculatedType type)
 222     {
 223         mergeSpeculation(m_type, type);
 224
 225         if (type & SpecCell) {
 226             m_currentKnownStructure.makeTop();
 227             m_futurePossibleStructure.makeTop();
 228             m_arrayModes = ALL_ARRAY_MODES;
 229         }
 230         m_value = JSValue();
 231
 232         checkConsistency();
 233     }
 234
 235     void filter(const StructureSet& other)
 236     {
 237         // FIXME: This could be optimized for the common case of m_type not
 238         // having structures, array modes, or a specific value.
 239         // https://bugs.webkit.org/show_bug.cgi?id=109663
 240         m_type &= other.speculationFromStructures();
 241         m_arrayModes &= other.arrayModesFromStructures();
 242         m_currentKnownStructure.filter(other);
 243         if (m_currentKnownStructure.isClear())
 244             m_futurePossibleStructure.clear();
 245         else if (m_currentKnownStructure.hasSingleton())
 246             filterFuturePossibleStructure(m_currentKnownStructure.singleton());
 247
 248         // It's possible that prior to the above two statements we had (Foo, TOP), where
 249         // Foo is a SpeculatedType that is disjoint with the passed StructureSet. In that
 250         // case, we will now have (None, [someStructure]). In general, we need to make
 251         // sure that new information gleaned from the SpeculatedType needs to be fed back
 252         // into the information gleaned from the StructureSet.
 253         m_currentKnownStructure.filter(m_type);
 254         m_futurePossibleStructure.filter(m_type);
 255
 256         filterArrayModesByType();
 257         filterValueByType();
 258
 259         checkConsistency();
 260     }
 261
 262     void filterArrayModes(ArrayModes arrayModes)
 263     {
 264         ASSERT(arrayModes);
 265
 266         m_type &= SpecCell;
 267         m_arrayModes &= arrayModes;
 268
 269         // I could do more fancy filtering here. But it probably won't make any difference.
 270
 271         checkConsistency();
 272     }
 273
 274     void filter(SpeculatedType type)
 275     {
 276         if (type == SpecTop)
 277             return;
 278         m_type &= type;
 279
 280         // It's possible that prior to this filter() call we had, say, (Final, TOP), and
 281         // the passed type is Array. At this point we'll have (None, TOP). The best way
 282         // to ensure that the structure filtering does the right thing is to filter on
 283         // the new type (None) rather than the one passed (Array).
 284         m_currentKnownStructure.filter(m_type);
 285         m_futurePossibleStructure.filter(m_type);
 286
 287         filterArrayModesByType();
 288         filterValueByType();
 289
 290         checkConsistency();
 291     }
 292
 293     void filterByValue(JSValue value)
 294     {
 295         filter(speculationFromValue(value));
 296         if (m_type)
 297             m_value = value;
 298     }
 299
 300     bool validateType(JSValue value) const
 301     {
 302         if (isTop())
 303             return true;
 304
 305         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
 306             return false;
 307
 308         if (value.isEmpty()) {
 309             ASSERT(m_type & SpecEmpty);
 310             return true;
 311         }
 312
 313         return true;
 314     }
 315
 316     bool validate(JSValue value) const
 317     {
 318         if (isTop())
 319             return true;
 320
 321         if (!!m_value && m_value != value)
 322             return false;
 323
 324         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
 325             return false;
 326
 327         if (value.isEmpty()) {
 328             ASSERT(m_type & SpecEmpty);
 329             return true;
 330         }
 331
 332         if (!!value && value.isCell()) {
 333             ASSERT(m_type & SpecCell);
 334             Structure* structure = value.asCell()->structure();
 335             return m_currentKnownStructure.contains(structure)
 336                 && m_futurePossibleStructure.contains(structure)
 337                 && (m_arrayModes & asArrayModes(structure->indexingType()));
 338         }
 339
 340         return true;
 341     }
 342
 343     Structure* bestProvenStructure() const
 344     {
 345         if (m_currentKnownStructure.hasSingleton())
 346             return m_currentKnownStructure.singleton();
 347         if (m_futurePossibleStructure.hasSingleton())
 348             return m_futurePossibleStructure.singleton();
 349         return 0;
 350     }
 351
 352     void checkConsistency() const
 353     {
 354         if (!(m_type & SpecCell)) {
 355             ASSERT(m_currentKnownStructure.isClear());
 356             ASSERT(m_futurePossibleStructure.isClear());
 357             ASSERT(!m_arrayModes);
 358         }
 359
 360         if (isClear())
 361             ASSERT(!m_value);
 362
 363         if (!!m_value)
 364             ASSERT(mergeSpeculations(m_type, speculationFromValue(m_value)) == m_type);
 365
 366         // Note that it's possible for a prediction like (Final, []). This really means that
 367         // the value is bottom and that any code that uses the value is unreachable. But
 368         // we don't want to get pedantic about this as it would only increase the computational
 369         // complexity of the code.
 370     }
 371
 372     void dump(PrintStream& out) const
 373     {
 374         out.print(
 375             "(", SpeculationDump(m_type), ", ", ArrayModesDump(m_arrayModes), ", ",
 376             m_currentKnownStructure, ", ", m_futurePossibleStructure);
 377         if (!!m_value)
 378             out.print(", ", m_value);
 379         out.print(")");
 380     }
 381
 382     // A great way to think about the difference between m_currentKnownStructure and
 383     // m_futurePossibleStructure is to consider these four examples:
 384     //
 385     // 1) x = foo();
 386     //
 387     //    In this case x's m_currentKnownStructure and m_futurePossibleStructure will
 388     //    both be TOP, since we don't know anything about x for sure, yet.
 389     //
 390     // 2) x = foo();
 391     //    y = x.f;
 392     //
 393     //    Where x will later have a new property added to it, 'g'. Because of the
 394     //    known but not-yet-executed property addition, x's currently structure will
 395     //    not be watchpointable; hence we have no way of statically bounding the set
 396     //    of possible structures that x may have if a clobbering event happens. So,
 397     //    x's m_currentKnownStructure will be whatever structure we check to get
 398     //    property 'f', and m_futurePossibleStructure will be TOP.
 399     //
 400     // 3) x = foo();
 401     //    y = x.f;
 402     //
 403     //    Where x has a terminal structure that is still watchpointable. In this case,
 404     //    x's m_currentKnownStructure and m_futurePossibleStructure will both be
 405     //    whatever structure we checked for when getting 'f'.
 406     //
 407     // 4) x = foo();
 408     //    y = x.f;
 409     //    bar();
 410     //
 411     //    Where x has a terminal structure that is still watchpointable. In this
 412     //    case, m_currentKnownStructure will be TOP because bar() may potentially
 413     //    change x's structure and we have no way of proving otherwise, but
 414     //    x's m_futurePossibleStructure will be whatever structure we had checked
 415     //    when getting property 'f'.
 416
 417     // NB. All fields in this struct must have trivial destructors.
 418
 419     // This is a proven constraint on the structures that this value can have right
 420     // now. The structure of the current value must belong to this set. The set may
 421     // be TOP, indicating that it is the set of all possible structures, in which
 422     // case the current value can have any structure. The set may be BOTTOM (empty)
 423     // in which case this value cannot be a cell. This is all subject to change
 424     // anytime a new value is assigned to this one, anytime there is a control flow
 425     // merge, or most crucially, anytime a side-effect or structure check happens.
 426     // In case of a side-effect, we typically must assume that any value may have
 427     // had its structure changed, hence contravening our proof. We make the proof
 428     // valid again by switching this to TOP (i.e. claiming that we have proved that
 429     // this value may have any structure). Of note is that the proof represented by
 430     // this field is not subject to structure transition watchpoints - even if one
 431     // fires, we can be sure that this proof is still valid.
 432     StructureAbstractValue m_currentKnownStructure;
 433
 434     // This is a proven constraint on the structures that this value can have now
 435     // or any time in the future subject to the structure transition watchpoints of
 436     // all members of this set not having fired. This set is impervious to side-
 437     // effects; even if one happens the side-effect can only cause the value to
 438     // change to at worst another structure that is also a member of this set. But,
 439     // the theorem being proved by this field is predicated upon there not being
 440     // any new structure transitions introduced into any members of this set. In
 441     // cases where there is no way for us to guard this happening, the set must be
 442     // TOP. But in cases where we can guard new structure transitions (all members
 443     // of the set have still-valid structure transition watchpoints) then this set
 444     // will be finite. Anytime that we make use of the finite nature of this set,
 445     // we must first issue a structure transition watchpoint, which will effectively
 446     // result in m_currentKnownStructure being filtered according to
 447     // m_futurePossibleStructure.
 448     StructureAbstractValue m_futurePossibleStructure;
 449
 450     // This is a proven constraint on the possible types that this value can have
 451     // now or any time in the future, unless it is reassigned. This field is
 452     // impervious to side-effects unless the side-effect can reassign the value
 453     // (for example if we're talking about a captured variable). The relationship
 454     // between this field, and the structure fields above, is as follows. The
 455     // fields above constraint the structures that a cell may have, but they say
 456     // nothing about whether or not the value is known to be a cell. More formally,
 457     // the m_currentKnownStructure is itself an abstract value that consists of the
 458     // union of the set of all non-cell values and the set of cell values that have
 459     // the given structure. This abstract value is then the intersection of the
 460     // m_currentKnownStructure and the set of values whose type is m_type. So, for
 461     // example if m_type is SpecFinal|SpecInt32 and m_currentKnownStructure is
 462     // [0x12345] then this abstract value corresponds to the set of all integers
 463     // unified with the set of all objects with structure 0x12345.
 464     SpeculatedType m_type;
 465
 466     // This is a proven constraint on the possible indexing types that this value
 467     // can have right now. It also implicitly constraints the set of structures
 468     // that the value may have right now, since a structure has an immutable
 469     // indexing type. This is subject to change upon reassignment, or any side
 470     // effect that makes non-obvious changes to the heap.
 471     ArrayModes m_arrayModes;
 472
 473     // This is a proven constraint on the possible values that this value can
 474     // have now or any time in the future, unless it is reassigned. Note that this
 475     // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
 476     // means either BOTTOM or TOP depending on the state of m_type: if m_type is
 477     // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
 478     // means TOP.
 479     JSValue m_value;
 480
 481 private:
 482     void clobberArrayModes()
 483     {
 484         // FIXME: We could make this try to predict the set of array modes that this object
 485         // could have in the future. For now, just do the simple thing.
 486         m_arrayModes = ALL_ARRAY_MODES;
 487     }
 488
 489     void setFuturePossibleStructure(Structure* structure)
 490     {
 491         if (structure->transitionWatchpointSetIsStillValid())
 492             m_futurePossibleStructure = structure;
 493         else
 494             m_futurePossibleStructure.makeTop();
 495     }
 496
 497     void filterFuturePossibleStructure(Structure* structure)
 498     {
 499         if (structure->transitionWatchpointSetIsStillValid())
 500             m_futurePossibleStructure.filter(StructureAbstractValue(structure));
 501     }
 502
 503     // We could go further, and ensure that if the futurePossibleStructure contravenes
 504     // the value, then we could clear both of those things. But that's unlikely to help
 505     // in any realistic scenario, so we don't do it. Simpler is better.
 506     void filterValueByType()
 507     {
 508         if (!!m_type) {
 509             // The type is still non-empty. This implies that regardless of what filtering
 510             // was done, we either didn't have a value to begin with, or that value is still
 511             // valid.
 512             ASSERT(!m_value || validateType(m_value));
 513             return;
 514         }
 515
 516         // The type has been rendered empty. That means that the value must now be invalid,
 517         // as well.
 518         ASSERT(!m_value || !validateType(m_value));
 519         m_value = JSValue();
 520     }
 521
 522     void filterArrayModesByType()
 523     {
 524         if (!(m_type & SpecCell))
 525             m_arrayModes = 0;
 526         else if (!(m_type & ~SpecArray))
 527             m_arrayModes &= ALL_ARRAY_ARRAY_MODES;
 528
 529         // NOTE: If m_type doesn't have SpecArray set, that doesn't mean that the
 530         // array modes have to be a subset of ALL_NON_ARRAY_ARRAY_MODES, since
 531         // in the speculated type type-system, RegExpMatchesArry and ArrayPrototype
 532         // are Otherobj (since they are not *exactly* JSArray) but in the ArrayModes
 533         // type system they are arrays (since they expose the magical length
 534         // property and are otherwise allocated using array allocation). Hence the
 535         // following would be wrong:
 536         //
 537         // if (!(m_type & SpecArray))
 538         //    m_arrayModes &= ALL_NON_ARRAY_ARRAY_MODES;
 539     }
 540 };
 541
 542 } } // namespace JSC::DFG
 543
 544 #endif // ENABLE(DFG_JIT)
 545
 546 #endif // DFGAbstractValue_h
 547
 548