diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ir/possible-contents.cpp | 26 | ||||
| -rw-r--r-- | src/ir/possible-contents.h | 83 |
2 files changed, 69 insertions, 40 deletions
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp index 836f7570d..1b5c5ae0d 100644 --- a/src/ir/possible-contents.cpp +++ b/src/ir/possible-contents.cpp @@ -1411,12 +1411,12 @@ bool Flower::updateContents(LocationIndex locationIndex, // It is not worth sending any more to this location if we are now in the // worst possible case, as no future value could cause any change. // - // Many is always the worst possible case. An exact type of a non-reference is + // Many is always the worst possible case. A cone type of a non-reference is // also the worst case, since subtyping is not relevant there, and so if we - // know only the type then we already know nothing beyond what the type in the - // wasm tells us (and from there we can only go to Many). + // only know something about the type then we already know nothing beyond what + // the type in the wasm tells us (and from there we can only go to Many). bool worthSendingMore = !contents.isMany(); - if (!contents.getType().isRef() && contents.isExactType()) { + if (!contents.getType().isRef() && contents.isConeType()) { worthSendingMore = false; } @@ -1578,9 +1578,10 @@ void Flower::filterGlobalContents(PossibleContents& contents, // "Many", since in the worst case we can just use the immutable value. That // is, we can always replace this value with (global.get $name) which will // get the right value. Likewise, using the immutable global value is often - // better than an exact type, but TODO: we could note both an exact type - // *and* that something is equal to a global, in some cases. - if (contents.isMany() || contents.isExactType()) { + // better than a cone type (even an exact one), but TODO: we could note both + // a cone/exact type *and* that something is equal to a global, in some + // cases. See https://github.com/WebAssembly/binaryen/pull/5083 + if (contents.isMany() || contents.isConeType()) { contents = PossibleContents::global(global->name, global->type); // TODO: We could do better here, to set global->init->type instead of @@ -1603,7 +1604,7 @@ void Flower::readFromData(HeapType declaredHeapType, Expression* read) { // The data that a struct.get reads depends on two things: the reference that // we read from, and the relevant DataLocations. The reference determines - // which DataLocations are relevant: if it is an ExactType then we have a + // which DataLocations are relevant: if it is an exact type then we have a // single DataLocation to read from, the one type that can be read from there. // Otherwise, we might read from any subtype, and so all their DataLocations // are relevant. @@ -1645,22 +1646,21 @@ void Flower::readFromData(HeapType declaredHeapType, std::cout << " add special reads\n"; #endif - if (refContents.isExactType()) { + if (refContents.hasExactType()) { // Add a single link to the exact location the reference points to. connectDuringFlow( DataLocation{refContents.getType().getHeapType(), fieldIndex}, ExpressionLocation{read, 0}); } else { - // Otherwise, this is a cone: the declared type of the reference, or any - // subtype of that, regardless of whether the content is a Many or a Global - // or anything else. + // Otherwise, this is a true cone (i.e., it has a depth > 0): the declared + // type of the reference or some of its subtypes. // TODO: The Global case may have a different cone type than the heapType, // which we could use here. // TODO: A Global may refer to an immutable global, which we can read the // field from potentially (reading it from the struct.new/array.new // in the definition of it, if it is not imported; or, we could track // the contents of immutable fields of allocated objects, and not just - // represent them as ExactType). + // represent them as an exact type). // See the test TODO with text "We optimize some of this, but stop at // reading from the immutable global" assert(refContents.isMany() || refContents.isGlobal()); diff --git a/src/ir/possible-contents.h b/src/ir/possible-contents.h index f3ad37d92..f7c39e1f9 100644 --- a/src/ir/possible-contents.h +++ b/src/ir/possible-contents.h @@ -44,15 +44,16 @@ namespace wasm { // to that global. Typically we can only infer this for // immutable globals. // -// * ExactType: Any possible value of a specific exact type - *not* -// including subtypes. For example, (struct.new $Foo) has -// ExactType contents of type $Foo. +// * ConeType: Any possible value of a particular type, and a possible +// "cone" of a certain depth below it. If the depth is 0 +// then only the exact type is possible; if the depth is 1 +// then either that type or its immediate subtypes, and so +// forth. // If the type here is nullable then null is also allowed. -// TODO: Add ConeType, which would include subtypes. -// TODO: Add ExactTypePlusContents or such, which would be +// TODO: Add ConeTypePlusContents or such, which would be // used on e.g. a struct.new with an immutable field // to which we assign a constant: not only do we know -// the exact type, but also certain field's values. +// the type, but also certain field's values. // // * Many: Anything else. Many things are possible here, and we do // not track what they might be, so we must assume the worst @@ -73,17 +74,27 @@ class PossibleContents { } }; - using ExactType = Type; + struct ConeType { + Type type; + Index depth; + bool operator==(const ConeType& other) const { + return type == other.type && depth == other.depth; + } + }; struct Many : public std::monostate {}; // TODO: This is similar to the variant in PossibleConstantValues, and perhaps // we could share code, but extending a variant using template magic may // not be worthwhile. Another option might be to make PCV inherit from - // this and disallow ExactType etc., but PCV might get slower. - using Variant = std::variant<None, Literal, GlobalInfo, ExactType, Many>; + // this and disallow ConeType etc., but PCV might get slower. + using Variant = std::variant<None, Literal, GlobalInfo, ConeType, Many>; Variant value; + // Internal convenience for creating a cone type with depth 0, i.e,, an exact + // type. + static ConeType ExactType(Type type) { return ConeType{type, 0}; } + public: PossibleContents() : value(None()) {} PossibleContents(const PossibleContents& other) = default; @@ -98,9 +109,13 @@ public: static PossibleContents global(Name name, Type type) { return PossibleContents{GlobalInfo{name, type}}; } + // Helper for a cone type with depth 0, i.e., an exact type. static PossibleContents exactType(Type type) { return PossibleContents{ExactType(type)}; } + static PossibleContents coneType(Type type, Index depth) { + WASM_UNREACHABLE("actual cones are not supported yet"); + } static PossibleContents many() { return PossibleContents{Many()}; } PossibleContents& operator=(const PossibleContents& other) = default; @@ -120,7 +135,7 @@ public: bool isNone() const { return std::get_if<None>(&value); } bool isLiteral() const { return std::get_if<Literal>(&value); } bool isGlobal() const { return std::get_if<GlobalInfo>(&value); } - bool isExactType() const { return std::get_if<Type>(&value); } + bool isConeType() const { return std::get_if<ConeType>(&value); } bool isMany() const { return std::get_if<Many>(&value); } Literal getLiteral() const { @@ -137,8 +152,9 @@ public: // Return the relevant type here. Note that the *meaning* of the type varies // by the contents: type $foo of a global means that type or any subtype, as a - // subtype might be written to it, while type $foo of a Literal or an - // ExactType means that type and nothing else; see hasExactType(). + // subtype might be written to it, while type $foo of a Literal or a ConeType + // with depth zero means that type and nothing else, etc. (see also + // hasExactType). // // If no type is possible, return unreachable; if many types are, return none. Type getType() const { @@ -146,8 +162,8 @@ public: return literal->type; } else if (auto* global = std::get_if<GlobalInfo>(&value)) { return global->type; - } else if (auto* type = std::get_if<Type>(&value)) { - return *type; + } else if (auto* coneType = std::get_if<ConeType>(&value)) { + return coneType->type; } else if (std::get_if<None>(&value)) { return Type::unreachable; } else if (std::get_if<Many>(&value)) { @@ -160,17 +176,23 @@ public: // Returns whether the type we can report here is exact, that is, nothing of a // strict subtype might show up - the contents here have an exact type. // - // This is different from isExactType() which checks if all we know about the - // contents here is their exact type. Specifically, we may know both an exact - // type and also more than just that, which is the case with a Literal. - // // This returns false for None and Many, for whom it is not well-defined. - bool hasExactType() const { return isExactType() || isLiteral(); } + bool hasExactType() const { + if (isLiteral()) { + return true; + } + + if (auto* coneType = std::get_if<ConeType>(&value)) { + return coneType->depth == 0; + } + + return false; + } // Returns whether the given contents have any intersection, that is, whether // some value exists that can appear in both |a| and |b|. For example, if - // either is None, or if they are both ExactTypes but of different types, then - // they have no intersection. + // either is None, or if they are different literals, then they have no + // intersection. static bool haveIntersection(const PossibleContents& a, const PossibleContents& b); @@ -199,8 +221,10 @@ public: return size_t(1) | (std::hash<Literal>()(getLiteral()) << 3); } else if (isGlobal()) { return size_t(2) | (std::hash<Name>()(getGlobal()) << 3); - } else if (isExactType()) { - return size_t(3) | (std::hash<Type>()(getType()) << 3); + } else if (auto* coneType = std::get_if<ConeType>(&value)) { + return size_t(3) | ((std::hash<std::pair<Type, Index>>{}( + {coneType->type, coneType->depth})) + << 3); } else if (isMany()) { return 4; } else { @@ -221,9 +245,14 @@ public: } } else if (isGlobal()) { o << "GlobalInfo $" << getGlobal(); - } else if (isExactType()) { - o << "ExactType " << getType(); - auto t = getType(); + } else if (auto* coneType = std::get_if<ConeType>(&value)) { + auto t = coneType->type; + o << "ConeType " << t; + if (coneType->depth == 0) { + o << " exact"; + } else { + o << " depth=" << coneType->depth; + } if (t.isRef()) { auto h = t.getHeapType(); o << " HT: " << h; @@ -513,7 +542,7 @@ namespace wasm { // constant must be there (2, above), and so we do not make an effort to track // non-reference types here. This makes the internals of ContentOracle simpler // and faster. A noticeable outcome of that is that querying the contents of an -// i32 local will return Many and not ExactType{i32} (assuming we could not +// i32 local will return Many and not ConeType{i32, 0} (assuming we could not // infer either that there must be nothing there, or a constant). Again, the // caller is assumed to know the wasm IR type anyhow, and also other // optimization passes work on the types in the IR, so we do not focus on that |