X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/a253471d7f8e4d91bf6ebabab00155c3b387d3d0..93a3786624b2768d89bfa27e46598dc64e2fb70a:/dfg/DFGAbstractValue.h diff --git a/dfg/DFGAbstractValue.h b/dfg/DFGAbstractValue.h index 682c7a9..25757b5 100644 --- a/dfg/DFGAbstractValue.h +++ b/dfg/DFGAbstractValue.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2011 Apple Inc. All rights reserved. + * 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 @@ -30,399 +30,250 @@ #if ENABLE(DFG_JIT) +#include "ArrayProfile.h" +#include "DFGStructureAbstractValue.h" #include "JSCell.h" -#include "PredictedType.h" +#include "SpeculatedType.h" #include "StructureSet.h" namespace JSC { namespace DFG { -class StructureAbstractValue { -public: - StructureAbstractValue() - : m_structure(0) - { - } - - StructureAbstractValue(Structure* structure) - : m_structure(structure) - { - } - - StructureAbstractValue(const StructureSet& set) +struct AbstractValue { + AbstractValue() + : m_type(SpecNone) + , m_arrayModes(0) { - switch (set.size()) { - case 0: - m_structure = 0; - break; - - case 1: - m_structure = set[0]; - break; - - default: - m_structure = topValue(); - break; - } } void clear() { - m_structure = 0; - } - - void makeTop() - { - m_structure = topValue(); - } - - static StructureAbstractValue top() - { - StructureAbstractValue value; - value.makeTop(); - return value; - } - - void add(Structure* structure) - { - ASSERT(!contains(structure) && !isTop()); - if (m_structure) - makeTop(); - else - m_structure = structure; - } - - bool addAll(const StructureSet& other) - { - if (isTop() || !other.size()) - return false; - if (other.size() > 1) { - makeTop(); - return true; - } - if (!m_structure) { - m_structure = other[0]; - return true; - } - if (m_structure == other[0]) - return false; - makeTop(); - return true; - } - - bool addAll(const StructureAbstractValue& other) - { - if (!other.m_structure) - return false; - if (isTop()) - return false; - if (other.isTop()) { - makeTop(); - return true; - } - if (m_structure) { - if (m_structure == other.m_structure) - return false; - makeTop(); - return true; - } - m_structure = other.m_structure; - return true; - } - - bool contains(Structure* structure) const - { - if (isTop()) - return true; - if (m_structure == structure) - return true; - return false; - } - - bool isSubsetOf(const StructureSet& other) const - { - if (isTop()) - return false; - if (!m_structure) - return true; - return other.contains(m_structure); - } - - bool doesNotContainAnyOtherThan(Structure* structure) const - { - if (isTop()) - return false; - if (!m_structure) - return true; - return m_structure == structure; - } - - bool isSupersetOf(const StructureSet& other) const - { - if (isTop()) - return true; - if (!other.size()) - return true; - if (other.size() > 1) - return false; - return m_structure == other[0]; - } - - bool isSubsetOf(const StructureAbstractValue& other) const - { - if (other.isTop()) - return true; - if (isTop()) - return false; - if (m_structure) { - if (other.m_structure) - return m_structure == other.m_structure; - return false; - } - return true; + m_type = SpecNone; + m_arrayModes = 0; + m_currentKnownStructure.clear(); + m_futurePossibleStructure.clear(); + m_value = JSValue(); + checkConsistency(); } - bool isSupersetOf(const StructureAbstractValue& other) const + bool isClear() const { - return other.isSubsetOf(*this); + bool result = m_type == SpecNone && !m_arrayModes && m_currentKnownStructure.isClear() && m_futurePossibleStructure.isClear(); + if (result) + ASSERT(!m_value); + return result; } - void filter(const StructureSet& other) + void makeTop() { - if (!m_structure) - return; - - if (isTop()) { - switch (other.size()) { - case 0: - m_structure = 0; - return; - - case 1: - m_structure = other[0]; - return; - - default: - return; - } - } - - if (other.contains(m_structure)) - return; - - m_structure = 0; + 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 filter(const StructureAbstractValue& other) + void clobberStructures() { - if (isTop()) { - m_structure = other.m_structure; - return; + if (m_type & SpecCell) { + m_currentKnownStructure.makeTop(); + clobberArrayModes(); + } else { + ASSERT(m_currentKnownStructure.isClear()); + ASSERT(!m_arrayModes); } - if (m_structure == other.m_structure) - return; - if (other.isTop()) - return; - m_structure = 0; + checkConsistency(); } - - void filter(PredictedType other) - { - if (!(other & PredictCell)) { - clear(); - return; - } - if (isClearOrTop()) - return; - - if (!(predictionFromStructure(m_structure) & other)) - m_structure = 0; - } - - bool isClear() const + void clobberValue() { - return !m_structure; + m_value = JSValue(); } - bool isTop() const { return m_structure == topValue(); } - - bool isClearOrTop() const { return m_structure <= topValue(); } - bool isNeitherClearNorTop() const { return !isClearOrTop(); } - - size_t size() const - { - ASSERT(!isTop()); - return !!m_structure; - } - - Structure* at(size_t i) const - { - ASSERT(!isTop()); - ASSERT(m_structure); - ASSERT_UNUSED(i, !i); - return m_structure; - } - - Structure* operator[](size_t i) const + bool isTop() const { - return at(i); + return m_type == SpecTop && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop(); } - Structure* last() const + bool valueIsTop() const { - return at(0); + return !m_value && m_type; } - PredictedType predictionFromStructures() const + JSValue value() const { - if (isTop()) - return PredictCell; - if (isClear()) - return PredictNone; - return predictionFromStructure(m_structure); + return m_value; } - bool operator==(const StructureAbstractValue& other) const + static AbstractValue top() { - return m_structure == other.m_structure; + AbstractValue result; + result.makeTop(); + return result; } - void dump(FILE* out) const + void setMostSpecific(JSValue value) { - if (isTop()) { - fprintf(out, "TOP"); - return; + 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; } - fprintf(out, "["); - if (m_structure) - fprintf(out, "%p", m_structure); - fprintf(out, "]"); - } - -private: - static Structure* topValue() { return reinterpret_cast(1); } - - // This can only remember one structure at a time. - Structure* m_structure; -}; - -struct AbstractValue { - AbstractValue() - : m_type(PredictNone) - { - } - - void clear() - { - m_type = PredictNone; - m_structure.clear(); - checkConsistency(); - } - - bool isClear() - { - return m_type == PredictNone && m_structure.isClear(); - } - - void makeTop() - { - m_type = PredictTop; - m_structure.makeTop(); - checkConsistency(); - } - - void clobberStructures() - { - if (m_type & PredictCell) - m_structure.makeTop(); - else - ASSERT(m_structure.isClear()); + m_type = speculationFromValue(value); + m_value = value; + checkConsistency(); } - bool isTop() const - { - return m_type == PredictTop && m_structure.isTop(); - } - - static AbstractValue top() - { - AbstractValue result; - result.makeTop(); - return result; - } - void set(JSValue value) { - m_structure.clear(); - if (value.isCell()) - m_structure.add(value.asCell()->structure()); + 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 = predictionFromValue(value); + m_type = speculationFromValue(value); + m_value = value; checkConsistency(); } void set(Structure* structure) { - m_structure.clear(); - m_structure.add(structure); - - m_type = predictionFromStructure(structure); + m_currentKnownStructure = structure; + setFuturePossibleStructure(structure); + m_arrayModes = asArrayModes(structure->indexingType()); + m_type = speculationFromStructure(structure); + m_value = JSValue(); checkConsistency(); } - void set(PredictedType type) + void set(SpeculatedType type) { - if (type & PredictCell) - m_structure.makeTop(); - else - m_structure.clear(); + 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_structure == other.m_structure; + 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) { - bool result = mergePrediction(m_type, other.m_type) | m_structure.addAll(other.m_structure); + 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(PredictedType type) + void merge(SpeculatedType type) { - mergePrediction(m_type, type); + mergeSpeculation(m_type, type); - if (type & PredictCell) - m_structure.makeTop(); + 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.predictionFromStructures(); - m_structure.filter(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 PredictedType that is disjoint with the passed StructureSet. In that + // 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 PredictedType needs to be fed back + // sure that new information gleaned from the SpeculatedType needs to be fed back // into the information gleaned from the StructureSet. - m_structure.filter(m_type); + 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(PredictedType type) + void filter(SpeculatedType type) { - if (type == PredictTop) + if (type == SpecTop) return; m_type &= type; @@ -430,38 +281,87 @@ struct AbstractValue { // 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_structure.filter(m_type); + m_currentKnownStructure.filter(m_type); + m_futurePossibleStructure.filter(m_type); + + filterArrayModesByType(); + filterValueByType(); + checkConsistency(); } - bool validate(JSValue value) const + void filterByValue(JSValue value) + { + filter(speculationFromValue(value)); + if (m_type) + m_value = value; + } + + bool validateType(JSValue value) const { if (isTop()) return true; - if (mergePredictions(m_type, predictionFromValue(value)) != m_type) + if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type) return false; if (value.isEmpty()) { - ASSERT(m_type & PredictEmpty); + ASSERT(m_type & SpecEmpty); return true; } - if (m_structure.isTop()) + return true; + } + + bool validate(JSValue value) const + { + if (isTop()) return true; - if (value.isCell()) { - ASSERT(m_type & PredictCell); - return m_structure.contains(value.asCell()->structure()); + 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 & PredictCell)) - ASSERT(m_structure.isClear()); + 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 @@ -469,15 +369,174 @@ struct AbstractValue { // complexity of the code. } - void dump(FILE* out) const + 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() { - fprintf(out, "(%s, ", predictionToString(m_type)); - m_structure.dump(out); - fprintf(out, ")"); + // 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)); } - StructureAbstractValue m_structure; - PredictedType m_type; + // 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