diff options
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGAbstractValue.h')
| -rw-r--r-- | Source/JavaScriptCore/dfg/DFGAbstractValue.h | 536 |
1 files changed, 178 insertions, 358 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractValue.h b/Source/JavaScriptCore/dfg/DFGAbstractValue.h index 402fd0fcd..ff1c6d205 100644 --- a/Source/JavaScriptCore/dfg/DFGAbstractValue.h +++ b/Source/JavaScriptCore/dfg/DFGAbstractValue.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2011 Apple Inc. All rights reserved. + * 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 @@ -30,283 +30,13 @@ #if ENABLE(DFG_JIT) +#include "DFGStructureAbstractValue.h" #include "JSCell.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) - { - 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; - } - - bool isSupersetOf(const StructureAbstractValue& other) const - { - return other.isSubsetOf(*this); - } - - void filter(const StructureSet& other) - { - 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; - } - - void filter(const StructureAbstractValue& other) - { - if (isTop()) { - m_structure = other.m_structure; - return; - } - if (m_structure == other.m_structure) - return; - if (other.isTop()) - return; - m_structure = 0; - } - - void filter(SpeculatedType other) - { - if (!(other & SpecCell)) { - clear(); - return; - } - - if (isClearOrTop()) - return; - - if (!(speculationFromStructure(m_structure) & other)) - m_structure = 0; - } - - bool isClear() const - { - return !m_structure; - } - - 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 - { - return at(i); - } - - Structure* last() const - { - return at(0); - } - - SpeculatedType speculationFromStructures() const - { - if (isTop()) - return SpecCell; - if (isClear()) - return SpecNone; - return speculationFromStructure(m_structure); - } - - bool operator==(const StructureAbstractValue& other) const - { - return m_structure == other.m_structure; - } - - void dump(FILE* out) const - { - if (isTop()) { - fprintf(out, "TOP"); - return; - } - - 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(SpecNone) @@ -316,15 +46,15 @@ struct AbstractValue { void clear() { m_type = SpecNone; - m_structure.clear(); - m_unclobberedStructure.clear(); + m_currentKnownStructure.clear(); + m_futurePossibleStructure.clear(); m_value = JSValue(); checkConsistency(); } bool isClear() const { - bool result = m_type == SpecNone && m_structure.isClear() && m_unclobberedStructure.isClear(); + bool result = m_type == SpecNone && m_currentKnownStructure.isClear() && m_futurePossibleStructure.isClear(); if (result) ASSERT(!m_value); return result; @@ -333,8 +63,8 @@ struct AbstractValue { void makeTop() { m_type = SpecTop; - m_structure.makeTop(); - m_unclobberedStructure.makeTop(); + m_currentKnownStructure.makeTop(); + m_futurePossibleStructure.makeTop(); m_value = JSValue(); checkConsistency(); } @@ -342,9 +72,9 @@ struct AbstractValue { void clobberStructures() { if (m_type & SpecCell) - m_structure.makeTop(); + m_currentKnownStructure.makeTop(); else - ASSERT(m_structure.isClear()); + ASSERT(m_currentKnownStructure.isClear()); checkConsistency(); } @@ -355,7 +85,7 @@ struct AbstractValue { bool isTop() const { - return m_type == SpecTop && m_structure.isTop() && m_unclobberedStructure.isTop(); + return m_type == SpecTop && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop(); } bool valueIsTop() const @@ -375,20 +105,29 @@ struct AbstractValue { return result; } - void set(JSValue value) + 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)); + } + + void setMostSpecific(JSValue value) { if (!!value && value.isCell()) { - // Have to be careful here! It's tempting to set the structure to the - // value's structure, but that would be wrong, since that would - // constitute a proof that this value will always have the same - // structure. The whole point of a value having a structure is that - // it may change in the future - for example between when we compile - // the code and when we run it. - m_structure.makeTop(); - m_unclobberedStructure.makeTop(); // FIXME: Consider not clobbering this. + Structure* structure = value.asCell()->structure(); + m_currentKnownStructure = structure; + setFuturePossibleStructure(structure); } else { - m_structure.clear(); - m_unclobberedStructure.clear(); + m_currentKnownStructure.clear(); + m_futurePossibleStructure.clear(); } m_type = speculationFromValue(value); @@ -397,14 +136,26 @@ struct AbstractValue { checkConsistency(); } - void set(Structure* structure) + void set(JSValue value) { - m_structure.clear(); - m_structure.add(structure); + if (!!value && value.isCell()) { + m_currentKnownStructure.makeTop(); + setFuturePossibleStructure(value.asCell()->structure()); + } else { + m_currentKnownStructure.clear(); + m_futurePossibleStructure.clear(); + } - m_unclobberedStructure.clear(); - m_unclobberedStructure.add(structure); + m_type = speculationFromValue(value); + m_value = value; + checkConsistency(); + } + + void set(Structure* structure) + { + m_currentKnownStructure = structure; + setFuturePossibleStructure(structure); m_type = speculationFromStructure(structure); m_value = JSValue(); @@ -414,11 +165,11 @@ struct AbstractValue { void set(SpeculatedType type) { if (type & SpecCell) { - m_structure.makeTop(); - m_unclobberedStructure.makeTop(); + m_currentKnownStructure.makeTop(); + m_futurePossibleStructure.makeTop(); } else { - m_structure.clear(); - m_unclobberedStructure.clear(); + m_currentKnownStructure.clear(); + m_futurePossibleStructure.clear(); } m_type = type; m_value = JSValue(); @@ -428,8 +179,8 @@ struct AbstractValue { bool operator==(const AbstractValue& other) const { return m_type == other.m_type - && m_structure == other.m_structure - && m_unclobberedStructure == other.m_unclobberedStructure + && m_currentKnownStructure == other.m_currentKnownStructure + && m_futurePossibleStructure == other.m_futurePossibleStructure && m_value == other.m_value; } bool operator!=(const AbstractValue& other) const @@ -448,8 +199,8 @@ struct AbstractValue { result = !other.isClear(); } else { result |= mergeSpeculation(m_type, other.m_type); - result |= m_structure.addAll(other.m_structure); - result |= m_unclobberedStructure.addAll(other.m_unclobberedStructure); + 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(); @@ -465,8 +216,8 @@ struct AbstractValue { mergeSpeculation(m_type, type); if (type & SpecCell) { - m_structure.makeTop(); - m_unclobberedStructure.makeTop(); + m_currentKnownStructure.makeTop(); + m_futurePossibleStructure.makeTop(); } m_value = JSValue(); @@ -476,19 +227,21 @@ struct AbstractValue { void filter(const StructureSet& other) { m_type &= other.speculationFromStructures(); - m_structure.filter(other); - m_unclobberedStructure.filter(other); + 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_structure.filter(m_type); - m_unclobberedStructure.filter(m_type); + m_currentKnownStructure.filter(m_type); + m_futurePossibleStructure.filter(m_type); - if (!!m_value && !validateIgnoringValue(m_value)) - clear(); + filterValueByType(); checkConsistency(); } @@ -503,47 +256,38 @@ 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_unclobberedStructure.filter(m_type); + m_currentKnownStructure.filter(m_type); + m_futurePossibleStructure.filter(m_type); - if (!!m_value && !validateIgnoringValue(m_value)) - clear(); + filterValueByType(); checkConsistency(); } - bool validateIgnoringValue(JSValue value) const + // 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 (isTop()) - return true; - - if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type) - return false; - - if (value.isEmpty()) { - ASSERT(m_type & SpecEmpty); - return true; - } - - if (m_structure.isTop()) - return true; - - if (!!value && value.isCell()) { - ASSERT(m_type & SpecCell); - return m_structure.contains(value.asCell()->structure()); + 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; } - return true; + // 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(); } - bool validate(JSValue value) const + bool validateType(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; @@ -552,18 +296,10 @@ struct AbstractValue { return true; } - if (m_structure.isTop()) - return true; - - if (!!value && value.isCell()) { - ASSERT(m_type & SpecCell); - return m_structure.contains(value.asCell()->structure()); - } - return true; } - bool validateForEntry(JSValue value) const + bool validate(JSValue value) const { if (isTop()) return true; @@ -579,12 +315,11 @@ struct AbstractValue { return true; } - if (m_unclobberedStructure.isTop()) - return true; - if (!!value && value.isCell()) { ASSERT(m_type & SpecCell); - return m_unclobberedStructure.contains(value.asCell()->structure()); + Structure* structure = value.asCell()->structure(); + return m_currentKnownStructure.contains(structure) + && m_futurePossibleStructure.contains(structure); } return true; @@ -593,8 +328,8 @@ struct AbstractValue { void checkConsistency() const { if (!(m_type & SpecCell)) { - ASSERT(m_structure.isClear()); - ASSERT(m_unclobberedStructure.isClear()); + ASSERT(m_currentKnownStructure.isClear()); + ASSERT(m_futurePossibleStructure.isClear()); } if (isClear()) @@ -612,17 +347,102 @@ struct AbstractValue { void dump(FILE* out) const { fprintf(out, "(%s, ", speculationToString(m_type)); - m_structure.dump(out); + m_currentKnownStructure.dump(out); dataLog(", "); - m_unclobberedStructure.dump(out); + m_futurePossibleStructure.dump(out); if (!!m_value) fprintf(out, ", %s", m_value.description()); fprintf(out, ")"); } + + // 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'. - StructureAbstractValue m_structure; - StructureAbstractValue m_unclobberedStructure; + // 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 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; }; |