/*
- * 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
#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<Structure*>(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;
// 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
// 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