summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/possible-contents.cpp303
-rw-r--r--src/ir/possible-contents.h55
-rw-r--r--src/passes/GUFA.cpp14
3 files changed, 296 insertions, 76 deletions
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index 6d75d65ca..8349939e1 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -89,39 +89,184 @@ void PossibleContents::combine(const PossibleContents& other) {
return;
}
+ auto lub = Type::getLeastUpperBound(type, otherType);
+ if (lub == Type::none) {
+ // The types are not in the same hierarchy.
+ value = Many();
+ return;
+ }
+
+ // From here we can assume there is a useful LUB.
+
// Nulls can be combined in by just adding nullability to a type.
if (isNull() || other.isNull()) {
// Only one of them can be null here, since we already handled the case
// where they were both null.
assert(!isNull() || !other.isNull());
- // If only one is a null, but the other's type is known exactly, then the
- // combination is to add nullability (if the type is *not* known exactly,
- // like for a global, then we cannot do anything useful here).
- if (!isNull() && hasExactType()) {
- value = ExactType(Type(type.getHeapType(), Nullable));
+ // If only one is a null then we can use the type info from the other, and
+ // just add in nullability. For example, a literal of type T and a null
+ // becomes an exact type of T that allows nulls, and so forth.
+ auto mixInNull = [](ConeType cone) {
+ cone.type = Type(cone.type.getHeapType(), Nullable);
+ return cone;
+ };
+ if (!isNull()) {
+ value = mixInNull(getCone());
return;
- } else if (!other.isNull() && other.hasExactType()) {
- value = ExactType(Type(otherType.getHeapType(), Nullable));
+ } else if (!other.isNull()) {
+ value = mixInNull(other.getCone());
return;
}
}
- if (hasExactType() && other.hasExactType() &&
- type.getHeapType() == otherType.getHeapType()) {
- // We know the types here exactly, and even the heap types match, but
- // there is some other difference that prevents them from being 100%
- // identical (for example, one might be an ExactType and the other a
- // Literal; or both might be ExactTypes and only one might be nullable).
- // In these cases we can emit a proper ExactType here, adding nullability
- // if we need to.
- value = ExactType(Type(
- type.getHeapType(),
- type.isNullable() || otherType.isNullable() ? Nullable : NonNullable));
+ // Find a ConeType that describes both inputs, using the shared ancestor which
+ // is the LUB. We need to find how big a cone we need: the cone must be big
+ // enough to contain both the inputs.
+ auto depth = getCone().depth;
+ auto otherDepth = other.getCone().depth;
+ Index newDepth;
+ if (depth == FullDepth || otherDepth == FullDepth) {
+ // At least one has full (infinite) depth, so we know the new depth must
+ // be the same.
+ newDepth = FullDepth;
+ } else {
+ // The depth we need under the lub is how far from the lub we are, plus
+ // the depth of our cone.
+ // TODO: we could make a single loop that also does the LUB, at the same
+ // time, and also avoids calling getDepth() which loops once more?
+ auto depthFromRoot = type.getHeapType().getDepth();
+ auto otherDepthFromRoot = otherType.getHeapType().getDepth();
+ auto lubDepthFromRoot = lub.getHeapType().getDepth();
+ assert(lubDepthFromRoot <= depthFromRoot);
+ assert(lubDepthFromRoot <= otherDepthFromRoot);
+ Index depthUnderLub = depthFromRoot - lubDepthFromRoot + depth;
+ Index otherDepthUnderLub =
+ otherDepthFromRoot - lubDepthFromRoot + otherDepth;
+
+ // The total cone must be big enough to contain all the above.
+ newDepth = std::max(depthUnderLub, otherDepthUnderLub);
+ }
+
+ value = ConeType{lub, newDepth};
+}
+
+void PossibleContents::intersectWithFullCone(const PossibleContents& other) {
+ assert(other.isFullConeType());
+
+ if (isSubContents(other, *this)) {
+ // The intersection is just |other|.
+ // Note that this code path handles |this| being Many.
+ value = other.value;
+ return;
+ }
+
+ if (!haveIntersection(*this, other)) {
+ // There is no intersection at all.
+ // Note that this code path handles |this| being None.
+ value = None();
+ return;
+ }
+
+ // There is an intersection here. Note that this implies |this| is a reference
+ // type, as it has an intersection with |other| which is a full cone type
+ // (which must be a reference type).
+ auto type = getType();
+ auto otherType = other.getType();
+ auto heapType = type.getHeapType();
+ auto otherHeapType = otherType.getHeapType();
+
+ // If both inputs are nullable then the intersection is nullable as well.
+ auto nullability =
+ type.isNullable() && otherType.isNullable() ? Nullable : NonNullable;
+
+ auto setNoneOrNull = [&]() {
+ if (nullability == Nullable) {
+ value = Literal::makeNull(otherHeapType);
+ } else {
+ value = None();
+ }
+ };
+
+ if (isNull()) {
+ // The intersection is either this null itself, or nothing if a null is not
+ // allowed.
+ setNoneOrNull();
+ return;
+ }
+
+ // If the heap types are not compatible then they are in separate hierarchies
+ // and there is no intersection.
+ auto isSubType = HeapType::isSubType(heapType, otherHeapType);
+ auto otherIsSubType = HeapType::isSubType(otherHeapType, heapType);
+ if (!isSubType && !otherIsSubType) {
+ value = None();
return;
}
- // Nothing else possible combines in an interesting way; emit a Many.
- value = Many();
+ if (isLiteral() || isGlobal()) {
+ // The information about the value being identical to a particular literal
+ // or immutable global is not removed by intersection, if the type is in the
+ // cone we are intersecting with.
+ if (isSubType) {
+ return;
+ }
+
+ // The type must change, so continue down to the generic code path.
+ // TODO: for globals we could perhaps refine the type here, but then the
+ // type on GlobalInfo would not match the module, so that needs some
+ // refactoring.
+ }
+
+ // Intersect the cones, as there is no more specific information we can use.
+ auto depthFromRoot = heapType.getDepth();
+ auto otherDepthFromRoot = otherHeapType.getDepth();
+
+ // To compute the new cone, find the new heap type for it, and to compute its
+ // depth, consider the adjustments to the existing depths that stem from the
+ // choice of new heap type.
+ HeapType newHeapType;
+
+ if (depthFromRoot < otherDepthFromRoot) {
+ newHeapType = otherHeapType;
+ } else {
+ newHeapType = heapType;
+ }
+
+ auto newType = Type(newHeapType, nullability);
+
+ // By assumption |other| has full depth. Consider the other cone in |this|.
+ if (hasFullCone()) {
+ // Both are full cones, so the result is as well.
+ value = FullConeType(newType);
+ } else {
+ // The result is a partial cone. If the cone starts in |otherHeapType| then
+ // we need to adjust the depth down, since it will be smaller than the
+ // original cone:
+ /*
+ // ..
+ // /
+ // otherHeapType
+ // / \
+ // heapType ..
+ // \
+ */
+ // E.g. if |this| is a cone of depth 10, and |otherHeapType| is an immediate
+ // subtype of |this|, then the new cone must be of depth 9.
+ auto newDepth = getCone().depth;
+ if (newHeapType == otherHeapType) {
+ assert(depthFromRoot <= otherDepthFromRoot);
+ auto reduction = otherDepthFromRoot - depthFromRoot;
+ if (reduction > newDepth) {
+ // The cone on heapType does not even reach the cone on otherHeapType,
+ // so the result is not a cone.
+ setNoneOrNull();
+ return;
+ }
+ newDepth -= reduction;
+ }
+
+ value = ConeType{newType, newDepth};
+ }
}
bool PossibleContents::haveIntersection(const PossibleContents& a,
@@ -148,43 +293,77 @@ bool PossibleContents::haveIntersection(const PossibleContents& a,
// From here on we focus on references.
- if (aType.isNullable() && bType.isNullable()) {
- // Null is possible on both sides. Assume that an intersection can exist,
- // but we could be more precise here and check if the types belong to
- // different hierarchies, in which case the nulls would differ TODO. For
- // now we only use this API from the RefEq logic, so this is fully precise.
+ auto aHeapType = aType.getHeapType();
+ auto bHeapType = bType.getHeapType();
+
+ if (aType.isNullable() && bType.isNullable() &&
+ aHeapType.getBottom() == bHeapType.getBottom()) {
+ // A compatible null is possible on both sides.
return true;
}
- // We ruled out a null on both sides, so at least one is non-nullable. If the
- // other is a null then no chance for an intersection remains.
+ // We ruled out having a compatible null on both sides. If one is simply a
+ // null then no chance for an intersection remains.
if (a.isNull() || b.isNull()) {
return false;
}
+ auto aSubB = HeapType::isSubType(aHeapType, bHeapType);
+ auto bSubA = HeapType::isSubType(bHeapType, aHeapType);
+ if (!aSubB && !bSubA) {
+ // No type can appear in both a and b, so the types differ, so the values
+ // do not overlap.
+ return false;
+ }
+
// From here on we focus on references and can ignore the case of null - any
// intersection must be of a non-null value, so we can focus on the heap
// types.
- auto aHeapType = aType.getHeapType();
- auto bHeapType = bType.getHeapType();
-
- if (a.hasExactType() && b.hasExactType() && aHeapType != bHeapType) {
- // The values must be different since their types are different.
- return false;
- }
- if (!HeapType::isSubType(aHeapType, bHeapType) &&
- !HeapType::isSubType(bHeapType, aHeapType)) {
- // No type can appear in both a and b, so the types differ, so the values
- // differ.
- return false;
+ auto aDepthFromRoot = aHeapType.getDepth();
+ auto bDepthFromRoot = bHeapType.getDepth();
+
+ if (aSubB) {
+ // A is a subtype of B. For there to be an intersection we need their cones
+ // to intersect, that is, to rule out the case where the cone from B is not
+ // deep enough to reach A.
+ assert(aDepthFromRoot >= bDepthFromRoot);
+ return aDepthFromRoot - bDepthFromRoot <= b.getCone().depth;
+ } else if (bSubA) {
+ assert(bDepthFromRoot >= aDepthFromRoot);
+ return bDepthFromRoot - aDepthFromRoot <= a.getCone().depth;
+ } else {
+ WASM_UNREACHABLE("we ruled out no subtyping before");
}
// TODO: we can also optimize things like different Literals, but existing
// passes do such things already so it is low priority.
+}
+
+bool PossibleContents::isSubContents(const PossibleContents& a,
+ const PossibleContents& b) {
+ // TODO: Everything else. For now we only call this when |a| or |b| is a full
+ // cone type.
+ if (b.isFullConeType()) {
+ if (a.isNone()) {
+ return true;
+ }
+ if (a.isMany()) {
+ return false;
+ }
+ if (a.isNull()) {
+ return b.getType().isNullable();
+ }
+ return Type::isSubType(a.getType(), b.getType());
+ }
+
+ if (a.isFullConeType()) {
+ // We've already ruled out b being a full cone type before, so the only way
+ // |a| can be contained in |b| is if |b| is everything.
+ return b.isMany();
+ }
- // It appears they can intersect.
- return true;
+ WASM_UNREACHABLE("a or b must be a full cone");
}
namespace {
@@ -1018,6 +1197,7 @@ struct InfoCollector
// verbose code).
void addRoot(Expression* curr,
PossibleContents contents = PossibleContents::many()) {
+ // TODO Use a cone type here when relevant
if (isRelevant(curr)) {
addRoot(ExpressionLocation{curr, 0}, contents);
}
@@ -1675,7 +1855,11 @@ void Flower::readFromData(HeapType declaredHeapType,
// 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());
+ assert(refContents.isMany() || refContents.isGlobal() ||
+ refContents.isConeType());
+
+ // TODO: Use the cone depth here for ConeType. Right now we do the
+ // pessimistic thing and assume a full cone of all subtypes.
// We create a ConeReadLocation for the canonical cone of this type, to
// avoid bloating the graph, see comment on ConeReadLocation().
@@ -1737,9 +1921,12 @@ void Flower::writeToData(Expression* ref, Expression* value, Index fieldIndex) {
DataLocation{refContents.getType().getHeapType(), fieldIndex};
updateContents(heapLoc, valueContents);
} else {
- assert(refContents.isMany() || refContents.isGlobal());
+ assert(refContents.isMany() || refContents.isGlobal() ||
+ refContents.isConeType());
// Update all possible subtypes here.
+ // TODO: Use the cone depth here for ConeType. Right now we do the
+ // pessimistic thing and assume a full cone of all subtypes.
auto type = ref->type.getHeapType();
for (auto subType : subTypes->getAllSubTypes(type)) {
auto heapLoc = DataLocation{subType, fieldIndex};
@@ -1751,32 +1938,10 @@ void Flower::writeToData(Expression* ref, Expression* value, Index fieldIndex) {
void Flower::flowRefCast(const PossibleContents& contents, RefCast* cast) {
// RefCast only allows valid values to go through: nulls and things of the
// cast type. Filter anything else out.
- PossibleContents filtered;
- if (contents.isMany()) {
- // Just pass the Many through.
- // TODO: we could emit a cone type here when we get one, instead of
- // emitting a Many in any of these code paths
- filtered = contents;
- } else {
- bool isSubType =
- HeapType::isSubType(contents.getType().getHeapType(), cast->intendedType);
- if (isSubType) {
- // The contents are not Many, but their heap type is a subtype of the
- // intended type, so we'll pass that through. Note that we pass the entire
- // contents here, which includes nullability, but that is fine, it would
- // just overlap with the code below that handles nulls (that is, the code
- // below only makes a difference when the heap type is *not* a subtype but
- // the type is nullable).
- // TODO: When we get cone types, we could filter the cone here.
- filtered.combine(contents);
- }
- bool mayBeNull = contents.getType().isNullable();
- if (mayBeNull) {
- // A null is possible, so pass that along.
- filtered.combine(
- PossibleContents::literal(Literal::makeNull(cast->intendedType)));
- }
- }
+ auto intendedCone =
+ PossibleContents::fullConeType(Type(cast->intendedType, Nullable));
+ PossibleContents filtered = contents;
+ filtered.intersectWithFullCone(intendedCone);
if (!filtered.isNone()) {
#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2
std::cout << " ref.cast passing through\n";
diff --git a/src/ir/possible-contents.h b/src/ir/possible-contents.h
index a6a27062a..ee817deae 100644
--- a/src/ir/possible-contents.h
+++ b/src/ir/possible-contents.h
@@ -50,6 +50,7 @@ namespace wasm {
// then only the exact type is possible; if the depth is 1
// then either that type or its immediate subtypes, and so
// forth.
+// A depth of -1 means unlimited: all subtypes are allowed.
// If the type here is nullable then null is also allowed.
// TODO: Add ConeTypePlusContents or such, which would be
// used on e.g. a struct.new with an immutable field
@@ -96,6 +97,12 @@ class PossibleContents {
// type.
static ConeType ExactType(Type type) { return ConeType{type, 0}; }
+ static constexpr Index FullDepth = -1;
+
+ // Internal convenience for creating a cone type of unbounded depth, i.e., the
+ // full cone of all subtypes for that type.
+ static ConeType FullConeType(Type type) { return ConeType{type, FullDepth}; }
+
public:
PossibleContents() : value(None()) {}
PossibleContents(const PossibleContents& other) = default;
@@ -114,8 +121,13 @@ public:
static PossibleContents exactType(Type type) {
return PossibleContents{ExactType(type)};
}
+ // Helper for a cone with unbounded depth, i.e., the full cone of all subtypes
+ // for that type.
+ static PossibleContents fullConeType(Type type) {
+ return PossibleContents{FullConeType(type)};
+ }
static PossibleContents coneType(Type type, Index depth) {
- WASM_UNREACHABLE("actual cones are not supported yet");
+ return PossibleContents{ConeType{type, depth}};
}
static PossibleContents many() { return PossibleContents{Many()}; }
@@ -133,6 +145,11 @@ public:
// contents here will then include whatever content was possible in |other|.
void combine(const PossibleContents& other);
+ // Removes anything not in |other| from this object, so that it ends up with
+ // only their intersection. Currently this only handles an intersection with a
+ // full cone.
+ void intersectWithFullCone(const PossibleContents& other);
+
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); }
@@ -174,6 +191,37 @@ public:
}
}
+ // Returns cone type info. This can be called on non-cone types as well, and
+ // it returns a cone that best describes them. That is, this is like getType()
+ // but it also provides an indication about the depth, if relevant. (If cone
+ // info is not relevant, like when getType() returns none or unreachable, the
+ // depth is set to 0.)
+ ConeType getCone() const {
+ if (auto* literal = std::get_if<Literal>(&value)) {
+ return ExactType(literal->type);
+ } else if (auto* global = std::get_if<GlobalInfo>(&value)) {
+ return FullConeType(global->type);
+ } else if (auto* coneType = std::get_if<ConeType>(&value)) {
+ return *coneType;
+ } else if (std::get_if<None>(&value)) {
+ return ExactType(Type::unreachable);
+ } else if (std::get_if<Many>(&value)) {
+ return ExactType(Type::none);
+ } else {
+ WASM_UNREACHABLE("bad value");
+ }
+ }
+
+ // Returns whether the relevant cone for this, as computed by getCone(), is of
+ // full size, that is, includes all subtypes.
+ bool hasFullCone() const { return getCone().depth == FullDepth; }
+
+ // Returns whether this is a cone type and also is of full size. This differs
+ // from hasFullCone() in that the former can return true for a global, for
+ // example, while this cannot (a global is not a cone type, but the
+ // information we have about its cone is that it is full).
+ bool isFullConeType() const { return isConeType() && hasFullCone(); }
+
// 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.
//
@@ -197,6 +245,11 @@ public:
static bool haveIntersection(const PossibleContents& a,
const PossibleContents& b);
+ // Returns whether |a| is a subset of |b|, that is, all possible contents of
+ // |a| are also possible in |b|.
+ static bool isSubContents(const PossibleContents& a,
+ const PossibleContents& b);
+
// Whether we can make an Expression* for this containing the proper contents.
// We can do that for a Literal (emitting a Const or RefFunc etc.) or a
// Global (emitting a GlobalGet), but not for anything else yet.
diff --git a/src/passes/GUFA.cpp b/src/passes/GUFA.cpp
index eedf5f20c..9774c1bb7 100644
--- a/src/passes/GUFA.cpp
+++ b/src/passes/GUFA.cpp
@@ -243,10 +243,11 @@ struct GUFAOptimizer
auto refType = refContents.getType();
if (refType.isRef()) {
// We have some knowledge of the type here. Use that to optimize: RefTest
- // returns 1 iff the input is not null and is also a subtype.
- bool isSubType =
- HeapType::isSubType(refType.getHeapType(), curr->intendedType);
- bool mayBeNull = refType.isNullable();
+ // returns 1 if the input is of a subtype of the intended type, that is,
+ // we are looking for a type in that cone of types. (Note that we use a
+ // non-nullable cone since only a non-null can pass the test.)
+ auto intendedContents =
+ PossibleContents::fullConeType(Type(curr->intendedType, NonNullable));
auto optimize = [&](int32_t result) {
auto* last = Builder(*getModule()).makeConst(Literal(int32_t(result)));
@@ -254,9 +255,10 @@ struct GUFAOptimizer
curr, *getModule(), getPassOptions(), last));
};
- if (!isSubType) {
+ if (!PossibleContents::haveIntersection(refContents, intendedContents)) {
optimize(0);
- } else if (!mayBeNull) {
+ } else if (PossibleContents::isSubContents(refContents,
+ intendedContents)) {
optimize(1);
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-05 12:26:50 +0000