| /* |
| * Copyright (C) 2011, 2012 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; |
| 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 !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) |
| { |
| 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(); |
| } |
| |
| bool filterByValue(JSValue value) |
| { |
| if (!validate(value)) |
| return false; |
| |
| if (!!value && value.isCell()) |
| filter(StructureSet(value.asCell()->structure())); |
| else |
| filter(speculationFromValue(value)); |
| |
| m_value = value; |
| |
| return true; |
| } |
| |
| 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'. |
| |
| // 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; |
| else if (!(m_type & SpecArray)) |
| m_arrayModes &= ALL_NON_ARRAY_ARRAY_MODES; |
| } |
| }; |
| |
| } } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
| |
| #endif // DFGAbstractValue_h |
| |
| |
