/* * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef DFGAbstractValue_h #define DFGAbstractValue_h #include <wtf/Platform.h> #if ENABLE(DFG_JIT) #include "ArrayProfile.h" #include "DFGStructureAbstractValue.h" #include "JSCell.h" #include "SpeculatedType.h" #include "StructureSet.h" namespace JSC { namespace DFG { struct AbstractValue { AbstractValue() : m_type(SpecNone) , m_arrayModes(0) { } void clear() { m_type = SpecNone; m_arrayModes = 0; m_currentKnownStructure.clear(); m_futurePossibleStructure.clear(); m_value = JSValue(); checkConsistency(); } bool isClear() const { bool result = m_type == SpecNone && !m_arrayModes && m_currentKnownStructure.isClear() && m_futurePossibleStructure.isClear(); if (result) ASSERT(!m_value); return result; } void makeTop() { m_type |= SpecTop; // The state may have included SpecEmpty, in which case we want this to become SpecEmptyOrTop. m_arrayModes = ALL_ARRAY_MODES; m_currentKnownStructure.makeTop(); m_futurePossibleStructure.makeTop(); m_value = JSValue(); checkConsistency(); } void clobberStructures() { if (m_type & SpecCell) { m_currentKnownStructure.makeTop(); clobberArrayModes(); } else { ASSERT(m_currentKnownStructure.isClear()); ASSERT(!m_arrayModes); } checkConsistency(); } void clobberValue() { m_value = JSValue(); } bool isTop() const { return m_type == SpecTop && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop(); } bool valueIsTop() const { return !m_value && m_type; } JSValue value() const { return m_value; } static AbstractValue top() { AbstractValue result; result.makeTop(); return result; } void setMostSpecific(JSValue value) { if (!!value && value.isCell()) { Structure* structure = value.asCell()->structure(); m_currentKnownStructure = structure; setFuturePossibleStructure(structure); m_arrayModes = asArrayModes(structure->indexingType()); } else { m_currentKnownStructure.clear(); m_futurePossibleStructure.clear(); m_arrayModes = 0; } m_type = speculationFromValue(value); m_value = value; checkConsistency(); } void set(JSValue value) { if (!!value && value.isCell()) { m_currentKnownStructure.makeTop(); Structure* structure = value.asCell()->structure(); setFuturePossibleStructure(structure); m_arrayModes = asArrayModes(structure->indexingType()); clobberArrayModes(); } else { m_currentKnownStructure.clear(); m_futurePossibleStructure.clear(); m_arrayModes = 0; } m_type = speculationFromValue(value); m_value = value; checkConsistency(); } void set(Structure* structure) { m_currentKnownStructure = structure; setFuturePossibleStructure(structure); m_arrayModes = asArrayModes(structure->indexingType()); m_type = speculationFromStructure(structure); m_value = JSValue(); checkConsistency(); } void set(SpeculatedType type) { if (type & SpecCell) { m_currentKnownStructure.makeTop(); m_futurePossibleStructure.makeTop(); m_arrayModes = ALL_ARRAY_MODES; } else { m_currentKnownStructure.clear(); m_futurePossibleStructure.clear(); m_arrayModes = 0; } m_type = type; m_value = JSValue(); checkConsistency(); } bool operator==(const AbstractValue& other) const { return m_type == other.m_type && m_arrayModes == other.m_arrayModes && m_currentKnownStructure == other.m_currentKnownStructure && m_futurePossibleStructure == other.m_futurePossibleStructure && m_value == other.m_value; } bool operator!=(const AbstractValue& other) const { return !(*this == other); } bool merge(const AbstractValue& other) { if (other.isClear()) return false; #if !ASSERT_DISABLED AbstractValue oldMe = *this; #endif bool result = false; if (isClear()) { *this = other; result = !other.isClear(); } else { result |= mergeSpeculation(m_type, other.m_type); result |= mergeArrayModes(m_arrayModes, other.m_arrayModes); result |= m_currentKnownStructure.addAll(other.m_currentKnownStructure); result |= m_futurePossibleStructure.addAll(other.m_futurePossibleStructure); if (m_value != other.m_value) { result |= !!m_value; m_value = JSValue(); } } checkConsistency(); ASSERT(result == (*this != oldMe)); return result; } void merge(SpeculatedType type) { mergeSpeculation(m_type, type); if (type & SpecCell) { m_currentKnownStructure.makeTop(); m_futurePossibleStructure.makeTop(); m_arrayModes = ALL_ARRAY_MODES; } m_value = JSValue(); checkConsistency(); } void filter(const StructureSet& other) { // FIXME: This could be optimized for the common case of m_type not // having structures, array modes, or a specific value. // https://bugs.webkit.org/show_bug.cgi?id=109663 m_type &= other.speculationFromStructures(); m_arrayModes &= other.arrayModesFromStructures(); m_currentKnownStructure.filter(other); if (m_currentKnownStructure.isClear()) m_futurePossibleStructure.clear(); else if (m_currentKnownStructure.hasSingleton()) filterFuturePossibleStructure(m_currentKnownStructure.singleton()); // It's possible that prior to the above two statements we had (Foo, TOP), where // Foo is a SpeculatedType that is disjoint with the passed StructureSet. In that // case, we will now have (None, [someStructure]). In general, we need to make // sure that new information gleaned from the SpeculatedType needs to be fed back // into the information gleaned from the StructureSet. m_currentKnownStructure.filter(m_type); m_futurePossibleStructure.filter(m_type); filterArrayModesByType(); filterValueByType(); checkConsistency(); } void filterArrayModes(ArrayModes arrayModes) { ASSERT(arrayModes); m_type &= SpecCell; m_arrayModes &= arrayModes; // I could do more fancy filtering here. But it probably won't make any difference. checkConsistency(); } void filter(SpeculatedType type) { if (type == SpecTop) return; m_type &= type; // It's possible that prior to this filter() call we had, say, (Final, TOP), and // the passed type is Array. At this point we'll have (None, TOP). The best way // to ensure that the structure filtering does the right thing is to filter on // the new type (None) rather than the one passed (Array). m_currentKnownStructure.filter(m_type); m_futurePossibleStructure.filter(m_type); filterArrayModesByType(); filterValueByType(); checkConsistency(); } void filterByValue(JSValue value) { filter(speculationFromValue(value)); if (m_type) m_value = value; } bool validateType(JSValue value) const { if (isTop()) return true; if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type) return false; if (value.isEmpty()) { ASSERT(m_type & SpecEmpty); return true; } return true; } bool validate(JSValue value) const { if (isTop()) return true; if (!!m_value && m_value != value) return false; if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type) return false; if (value.isEmpty()) { ASSERT(m_type & SpecEmpty); return true; } if (!!value && value.isCell()) { ASSERT(m_type & SpecCell); Structure* structure = value.asCell()->structure(); return m_currentKnownStructure.contains(structure) && m_futurePossibleStructure.contains(structure) && (m_arrayModes & asArrayModes(structure->indexingType())); } return true; } Structure* bestProvenStructure() const { if (m_currentKnownStructure.hasSingleton()) return m_currentKnownStructure.singleton(); if (m_futurePossibleStructure.hasSingleton()) return m_futurePossibleStructure.singleton(); return 0; } void checkConsistency() const { if (!(m_type & SpecCell)) { ASSERT(m_currentKnownStructure.isClear()); ASSERT(m_futurePossibleStructure.isClear()); ASSERT(!m_arrayModes); } if (isClear()) ASSERT(!m_value); if (!!m_value) ASSERT(mergeSpeculations(m_type, speculationFromValue(m_value)) == m_type); // Note that it's possible for a prediction like (Final, []). This really means that // the value is bottom and that any code that uses the value is unreachable. But // we don't want to get pedantic about this as it would only increase the computational // complexity of the code. } void dump(PrintStream& out) const { out.print( "(", SpeculationDump(m_type), ", ", ArrayModesDump(m_arrayModes), ", ", m_currentKnownStructure, ", ", m_futurePossibleStructure); if (!!m_value) out.print(", ", m_value); out.print(")"); } // A great way to think about the difference between m_currentKnownStructure and // m_futurePossibleStructure is to consider these four examples: // // 1) x = foo(); // // In this case x's m_currentKnownStructure and m_futurePossibleStructure will // both be TOP, since we don't know anything about x for sure, yet. // // 2) x = foo(); // y = x.f; // // Where x will later have a new property added to it, 'g'. Because of the // known but not-yet-executed property addition, x's currently structure will // not be watchpointable; hence we have no way of statically bounding the set // of possible structures that x may have if a clobbering event happens. So, // x's m_currentKnownStructure will be whatever structure we check to get // property 'f', and m_futurePossibleStructure will be TOP. // // 3) x = foo(); // y = x.f; // // Where x has a terminal structure that is still watchpointable. In this case, // x's m_currentKnownStructure and m_futurePossibleStructure will both be // whatever structure we checked for when getting 'f'. // // 4) x = foo(); // y = x.f; // bar(); // // Where x has a terminal structure that is still watchpointable. In this // case, m_currentKnownStructure will be TOP because bar() may potentially // change x's structure and we have no way of proving otherwise, but // x's m_futurePossibleStructure will be whatever structure we had checked // when getting property 'f'. // NB. All fields in this struct must have trivial destructors. // This is a proven constraint on the structures that this value can have right // now. The structure of the current value must belong to this set. The set may // be TOP, indicating that it is the set of all possible structures, in which // case the current value can have any structure. The set may be BOTTOM (empty) // in which case this value cannot be a cell. This is all subject to change // anytime a new value is assigned to this one, anytime there is a control flow // merge, or most crucially, anytime a side-effect or structure check happens. // In case of a side-effect, we typically must assume that any value may have // had its structure changed, hence contravening our proof. We make the proof // valid again by switching this to TOP (i.e. claiming that we have proved that // this value may have any structure). Of note is that the proof represented by // this field is not subject to structure transition watchpoints - even if one // fires, we can be sure that this proof is still valid. StructureAbstractValue m_currentKnownStructure; // This is a proven constraint on the structures that this value can have now // or any time in the future subject to the structure transition watchpoints of // all members of this set not having fired. This set is impervious to side- // effects; even if one happens the side-effect can only cause the value to // change to at worst another structure that is also a member of this set. But, // the theorem being proved by this field is predicated upon there not being // any new structure transitions introduced into any members of this set. In // cases where there is no way for us to guard this happening, the set must be // TOP. But in cases where we can guard new structure transitions (all members // of the set have still-valid structure transition watchpoints) then this set // will be finite. Anytime that we make use of the finite nature of this set, // we must first issue a structure transition watchpoint, which will effectively // result in m_currentKnownStructure being filtered according to // m_futurePossibleStructure. StructureAbstractValue m_futurePossibleStructure; // This is a proven constraint on the possible types that this value can have // now or any time in the future, unless it is reassigned. This field is // impervious to side-effects unless the side-effect can reassign the value // (for example if we're talking about a captured variable). The relationship // between this field, and the structure fields above, is as follows. The // fields above constraint the structures that a cell may have, but they say // nothing about whether or not the value is known to be a cell. More formally, // the m_currentKnownStructure is itself an abstract value that consists of the // union of the set of all non-cell values and the set of cell values that have // the given structure. This abstract value is then the intersection of the // m_currentKnownStructure and the set of values whose type is m_type. So, for // example if m_type is SpecFinal|SpecInt32 and m_currentKnownStructure is // [0x12345] then this abstract value corresponds to the set of all integers // unified with the set of all objects with structure 0x12345. SpeculatedType m_type; // This is a proven constraint on the possible indexing types that this value // can have right now. It also implicitly constraints the set of structures // that the value may have right now, since a structure has an immutable // indexing type. This is subject to change upon reassignment, or any side // effect that makes non-obvious changes to the heap. ArrayModes m_arrayModes; // This is a proven constraint on the possible values that this value can // have now or any time in the future, unless it is reassigned. Note that this // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value) // means either BOTTOM or TOP depending on the state of m_type: if m_type is // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue() // means TOP. JSValue m_value; private: void clobberArrayModes() { // FIXME: We could make this try to predict the set of array modes that this object // could have in the future. For now, just do the simple thing. m_arrayModes = ALL_ARRAY_MODES; } void setFuturePossibleStructure(Structure* structure) { if (structure->transitionWatchpointSetIsStillValid()) m_futurePossibleStructure = structure; else m_futurePossibleStructure.makeTop(); } void filterFuturePossibleStructure(Structure* structure) { if (structure->transitionWatchpointSetIsStillValid()) m_futurePossibleStructure.filter(StructureAbstractValue(structure)); } // We could go further, and ensure that if the futurePossibleStructure contravenes // the value, then we could clear both of those things. But that's unlikely to help // in any realistic scenario, so we don't do it. Simpler is better. void filterValueByType() { if (!!m_type) { // The type is still non-empty. This implies that regardless of what filtering // was done, we either didn't have a value to begin with, or that value is still // valid. ASSERT(!m_value || validateType(m_value)); return; } // The type has been rendered empty. That means that the value must now be invalid, // as well. ASSERT(!m_value || !validateType(m_value)); m_value = JSValue(); } void filterArrayModesByType() { if (!(m_type & SpecCell)) m_arrayModes = 0; else if (!(m_type & ~SpecArray)) m_arrayModes &= ALL_ARRAY_ARRAY_MODES; // NOTE: If m_type doesn't have SpecArray set, that doesn't mean that the // array modes have to be a subset of ALL_NON_ARRAY_ARRAY_MODES, since // in the speculated type type-system, RegExpMatchesArry and ArrayPrototype // are Otherobj (since they are not *exactly* JSArray) but in the ArrayModes // type system they are arrays (since they expose the magical length // property and are otherwise allocated using array allocation). Hence the // following would be wrong: // // if (!(m_type & SpecArray)) // m_arrayModes &= ALL_NON_ARRAY_ARRAY_MODES; } }; } } // namespace JSC::DFG #endif // ENABLE(DFG_JIT) #endif // DFGAbstractValue_h