diff options
| -rw-r--r-- | src/ir/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/ir/possible-contents.cpp | 1656 | ||||
| -rw-r--r-- | src/ir/possible-contents.h | 538 | ||||
| -rw-r--r-- | src/ir/subtypes.h | 5 | ||||
| -rw-r--r-- | test/gtest/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | test/gtest/possible-contents.cpp | 262 |
6 files changed, 2461 insertions, 2 deletions
diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt index bdf75bb69..ed95c5d7d 100644 --- a/src/ir/CMakeLists.txt +++ b/src/ir/CMakeLists.txt @@ -8,6 +8,7 @@ set(ir_SOURCES memory-utils.cpp module-utils.cpp names.cpp + possible-contents.cpp properties.cpp LocalGraph.cpp ReFinalize.cpp diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp new file mode 100644 index 000000000..94c22aacc --- /dev/null +++ b/src/ir/possible-contents.cpp @@ -0,0 +1,1656 @@ +/* + * Copyright 2022 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <optional> +#include <variant> + +#include "ir/branch-utils.h" +#include "ir/eh-utils.h" +#include "ir/module-utils.h" +#include "ir/possible-contents.h" +#include "wasm.h" + +#ifdef POSSIBLE_CONTENTS_INSERT_ORDERED +// Use an insert-ordered set for easier debugging with deterministic queue +// ordering. +#include "support/insert_ordered.h" +#endif + +namespace std { + +std::ostream& operator<<(std::ostream& stream, + const wasm::PossibleContents& contents) { + contents.dump(stream); + return stream; +} + +} // namespace std + +namespace wasm { + +void PossibleContents::combine(const PossibleContents& other) { + // First handle the trivial cases of them being equal, or one of them is + // None or Many. + if (*this == other) { + return; + } + if (other.isNone()) { + return; + } + if (isNone()) { + value = other.value; + return; + } + if (isMany()) { + return; + } + if (other.isMany()) { + value = Many(); + return; + } + + auto type = getType(); + auto otherType = other.getType(); + + if (!type.isRef() || !otherType.isRef()) { + // At least one is not a reference. The only possibility left for a useful + // combination here is if they have the same type (since we've already ruled + // out the case of them being equal). If they have the same type then + // neither is a reference and we can emit an exact type (since subtyping is + // not relevant for non-references. + if (type == otherType) { + value = ExactType(type); + } else { + value = Many(); + } + return; + } + + // Special handling for references from here. + + // Nulls are always equal to each other, even if their types differ. + if (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)); + return; + } else if (!other.isNull() && other.hasExactType()) { + value = ExactType(Type(otherType.getHeapType(), Nullable)); + return; + } else if (isNull() && other.isNull()) { + // Both are null. The result is a null, of the LUB. + auto lub = HeapType::getLeastUpperBound(type.getHeapType(), + otherType.getHeapType()); + value = Literal::makeNull(lub); + 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)); + return; + } + + // Nothing else possible combines in an interesting way; emit a Many. + value = Many(); +} + +namespace { + +// We are going to do a very large flow operation, potentially, as we create +// a Location for every interesting part in the entire wasm, and some of those +// places will have lots of links (like a struct field may link out to every +// single struct.get of that type), so we must make the data structures here +// as efficient as possible. Towards that goal, we work with location +// *indexes* where possible, which are small (32 bits) and do not require any +// complex hashing when we use them in sets or maps. +// +// Note that we do not use indexes everywhere, since the initial analysis is +// done in parallel, and we do not have a fixed indexing of locations yet. When +// we merge the parallel data we create that indexing, and use indexes from then +// on. +using LocationIndex = uint32_t; + +#ifndef NDEBUG +// Assert on not having duplicates in a vector. +template<typename T> void disallowDuplicates(const T& targets) { +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::unordered_set<LocationIndex> uniqueTargets; + for (const auto& target : targets) { + uniqueTargets.insert(target); + } + assert(uniqueTargets.size() == targets.size()); +#endif +} +#endif + +// A link indicates a flow of content from one location to another. For +// example, if we do a local.get and return that value from a function, then +// we have a link from a LocalLocation to a ResultLocation. +template<typename T> struct Link { + T from; + T to; + + bool operator==(const Link<T>& other) const { + return from == other.from && to == other.to; + } +}; + +using LocationLink = Link<Location>; +using IndexLink = Link<LocationIndex>; + +} // anonymous namespace + +} // namespace wasm + +namespace std { + +template<> struct hash<wasm::LocationLink> { + size_t operator()(const wasm::LocationLink& loc) const { + return std::hash<std::pair<wasm::Location, wasm::Location>>{}( + {loc.from, loc.to}); + } +}; + +template<> struct hash<wasm::IndexLink> { + size_t operator()(const wasm::IndexLink& loc) const { + return std::hash<std::pair<wasm::LocationIndex, wasm::LocationIndex>>{}( + {loc.from, loc.to}); + } +}; + +} // namespace std + +namespace wasm { + +namespace { + +// The data we gather from each function, as we process them in parallel. Later +// this will be merged into a single big graph. +struct CollectedFuncInfo { + // All the links we found in this function. Rarely are there duplicates + // in this list (say when writing to the same global location from another + // global location), and we do not try to deduplicate here, just store them in + // a plain array for now, which is faster (later, when we merge all the info + // from the functions, we need to deduplicate anyhow). + std::vector<LocationLink> links; + + // All the roots of the graph, that is, places that begin by containing some + // particular content. That includes i32.const, ref.func, struct.new, etc. All + // possible contents in the rest of the graph flow from such places. + // + // The vector here is of the location of the root and then its contents. + std::vector<std::pair<Location, PossibleContents>> roots; + + // In some cases we need to know the parent of the expression. Consider this: + // + // (struct.set $A k + // (local.get $ref) + // (local.get $value) + // ) + // + // Imagine that the first local.get, for $ref, receives a new value. That can + // affect where the struct.set sends values: if previously that local.get had + // no possible contents, and now it does, then we have DataLocations to + // update. Likewise, when the second local.get is updated we must do the same, + // but again which DataLocations we update depends on the ref passed to the + // struct.set. To handle such things, we set add a childParent link, and then + // when we update the child we can find the parent and handle any special + // behavior we need there. + std::unordered_map<Expression*, Expression*> childParents; +}; + +// Walk the wasm and find all the links we need to care about, and the locations +// and roots related to them. This builds up a CollectedFuncInfo data structure. +// After all InfoCollectors run, those data structures will be merged and the +// main flow will begin. +struct InfoCollector + : public PostWalker<InfoCollector, OverriddenVisitor<InfoCollector>> { + CollectedFuncInfo& info; + + InfoCollector(CollectedFuncInfo& info) : info(info) {} + + // Check if a type is relevant for us. If not, we can ignore it entirely. + bool isRelevant(Type type) { + if (type == Type::unreachable || type == Type::none) { + return false; + } + if (type.isTuple()) { + for (auto t : type) { + if (isRelevant(t)) { + return true; + } + } + } + if (type.isRef() && getTypeSystem() != TypeSystem::Nominal && + getTypeSystem() != TypeSystem::Isorecursive) { + // We need explicit supers in the SubTyping helper class. Without that, + // cannot handle refs, and consider them irrelevant. + return false; + } + return true; + } + + bool isRelevant(Signature sig) { + return isRelevant(sig.params) || isRelevant(sig.results); + } + + bool isRelevant(Expression* curr) { return curr && isRelevant(curr->type); } + + template<typename T> bool isRelevant(const T& vec) { + for (auto* expr : vec) { + if (isRelevant(expr->type)) { + return true; + } + } + return false; + } + + // Each visit*() call is responsible for connecting the children of a node to + // that node. Responsibility for connecting the node's output to anywhere + // else (another expression or the function itself, if we are at the top + // level) is the responsibility of the outside. + + void visitBlock(Block* curr) { + if (curr->list.empty()) { + return; + } + + // Values sent to breaks to this block must be received here. + handleBreakTarget(curr); + + // The final item in the block can flow a value to here as well. + receiveChildValue(curr->list.back(), curr); + } + void visitIf(If* curr) { + // Each arm may flow out a value. + receiveChildValue(curr->ifTrue, curr); + receiveChildValue(curr->ifFalse, curr); + } + void visitLoop(Loop* curr) { receiveChildValue(curr->body, curr); } + void visitBreak(Break* curr) { + // Connect the value (if present) to the break target. + handleBreakValue(curr); + + // The value may also flow through in a br_if (the type will indicate that, + // which receiveChildValue will notice). + receiveChildValue(curr->value, curr); + } + void visitSwitch(Switch* curr) { handleBreakValue(curr); } + void visitLoad(Load* curr) { + // We could infer the exact type here, but as no subtyping is possible, it + // would have no benefit, so just add a generic root (which will be "Many"). + // See the comment on the ContentOracle class. + addRoot(curr); + } + void visitStore(Store* curr) {} + void visitAtomicRMW(AtomicRMW* curr) { addRoot(curr); } + void visitAtomicCmpxchg(AtomicCmpxchg* curr) { addRoot(curr); } + void visitAtomicWait(AtomicWait* curr) { addRoot(curr); } + void visitAtomicNotify(AtomicNotify* curr) { addRoot(curr); } + void visitAtomicFence(AtomicFence* curr) {} + void visitSIMDExtract(SIMDExtract* curr) { addRoot(curr); } + void visitSIMDReplace(SIMDReplace* curr) { addRoot(curr); } + void visitSIMDShuffle(SIMDShuffle* curr) { addRoot(curr); } + void visitSIMDTernary(SIMDTernary* curr) { addRoot(curr); } + void visitSIMDShift(SIMDShift* curr) { addRoot(curr); } + void visitSIMDLoad(SIMDLoad* curr) { addRoot(curr); } + void visitSIMDLoadStoreLane(SIMDLoadStoreLane* curr) { addRoot(curr); } + void visitMemoryInit(MemoryInit* curr) {} + void visitDataDrop(DataDrop* curr) {} + void visitMemoryCopy(MemoryCopy* curr) {} + void visitMemoryFill(MemoryFill* curr) {} + void visitConst(Const* curr) { + addRoot(curr, PossibleContents::literal(curr->value)); + } + void visitUnary(Unary* curr) { + // TODO: Optimize cases like this using interpreter integration: if the + // input is a Literal, we could interpret the Literal result. + addRoot(curr); + } + void visitBinary(Binary* curr) { addRoot(curr); } + void visitSelect(Select* curr) { + // TODO: We could use the fact that both sides are executed unconditionally + // while optimizing (if one arm must trap, then the Select will trap, + // which is not the same as with an If). + receiveChildValue(curr->ifTrue, curr); + receiveChildValue(curr->ifFalse, curr); + } + void visitDrop(Drop* curr) {} + void visitMemorySize(MemorySize* curr) { addRoot(curr); } + void visitMemoryGrow(MemoryGrow* curr) { addRoot(curr); } + void visitRefNull(RefNull* curr) { + addRoot( + curr, + PossibleContents::literal(Literal::makeNull(curr->type.getHeapType()))); + } + void visitRefIs(RefIs* curr) { + // TODO: optimize when possible + addRoot(curr); + } + void visitRefFunc(RefFunc* curr) { + addRoot(curr, PossibleContents::literal(Literal(curr->func, curr->type))); + } + void visitRefEq(RefEq* curr) { + // TODO: optimize when possible (e.g. when both sides must contain the same + // global) + addRoot(curr); + } + void visitTableGet(TableGet* curr) { + // TODO: optimize when possible + addRoot(curr); + } + void visitTableSet(TableSet* curr) {} + void visitTableSize(TableSize* curr) { addRoot(curr); } + void visitTableGrow(TableGrow* curr) { addRoot(curr); } + + void visitNop(Nop* curr) {} + void visitUnreachable(Unreachable* curr) {} + +#ifndef NDEBUG + // For now we only handle pops in a catch body, see visitTry(). To check for + // errors, use counter of the pops we handled and all the pops; those sums + // must agree at the end, or else we've seen something we can't handle. + Index totalPops = 0; + Index handledPops = 0; +#endif + + void visitPop(Pop* curr) { +#ifndef NDEBUG + totalPops++; +#endif + } + void visitI31New(I31New* curr) { + // TODO: optimize like struct references + addRoot(curr); + } + void visitI31Get(I31Get* curr) { + // TODO: optimize like struct references + addRoot(curr); + } + + void visitRefTest(RefTest* curr) { + // TODO: optimize when possible + addRoot(curr); + } + void visitRefCast(RefCast* curr) { + // We will handle this in a special way later during the flow, as ref.cast + // only allows valid values to flow through. + addChildParentLink(curr->ref, curr); + } + void visitBrOn(BrOn* curr) { + // TODO: optimize when possible + handleBreakValue(curr); + receiveChildValue(curr->ref, curr); + } + void visitRttCanon(RttCanon* curr) { addRoot(curr); } + void visitRttSub(RttSub* curr) { addRoot(curr); } + void visitRefAs(RefAs* curr) { + // TODO: optimize when possible: like RefCast, not all values flow through. + receiveChildValue(curr->value, curr); + } + + // Locals read and write to their index. + // TODO: we could use a LocalGraph for SSA-like precision + void visitLocalGet(LocalGet* curr) { + if (isRelevant(curr->type)) { + for (Index i = 0; i < curr->type.size(); i++) { + info.links.push_back({LocalLocation{getFunction(), curr->index, i}, + ExpressionLocation{curr, i}}); + } + } + } + void visitLocalSet(LocalSet* curr) { + if (!isRelevant(curr->value->type)) { + return; + } + for (Index i = 0; i < curr->value->type.size(); i++) { + info.links.push_back({ExpressionLocation{curr->value, i}, + LocalLocation{getFunction(), curr->index, i}}); + } + + // Tees also flow out the value (receiveChildValue will see if this is a tee + // based on the type, automatically). + receiveChildValue(curr->value, curr); + } + + // Globals read and write from their location. + void visitGlobalGet(GlobalGet* curr) { + if (isRelevant(curr->type)) { + // FIXME: we allow tuples in globals, so GlobalLocation needs a tupleIndex + // and we should loop here. + assert(!curr->type.isTuple()); + info.links.push_back( + {GlobalLocation{curr->name}, ExpressionLocation{curr, 0}}); + } + } + void visitGlobalSet(GlobalSet* curr) { + if (isRelevant(curr->value->type)) { + info.links.push_back( + {ExpressionLocation{curr->value, 0}, GlobalLocation{curr->name}}); + } + } + + // Iterates over a list of children and adds links to parameters and results + // as needed. The param/result functions receive the index and create the + // proper location for it. + template<typename T> + void handleCall(T* curr, + std::function<Location(Index)> makeParamLocation, + std::function<Location(Index)> makeResultLocation) { + Index i = 0; + for (auto* operand : curr->operands) { + if (isRelevant(operand->type)) { + info.links.push_back( + {ExpressionLocation{operand, 0}, makeParamLocation(i)}); + } + i++; + } + + // Add results, if anything flows out. + for (Index i = 0; i < curr->type.size(); i++) { + if (isRelevant(curr->type[i])) { + info.links.push_back( + {makeResultLocation(i), ExpressionLocation{curr, i}}); + } + } + + // If this is a return call then send the result to the function return as + // well. + if (curr->isReturn) { + auto results = getFunction()->getResults(); + for (Index i = 0; i < results.size(); i++) { + auto result = results[i]; + if (isRelevant(result)) { + info.links.push_back( + {makeResultLocation(i), ResultLocation{getFunction(), i}}); + } + } + } + } + + // Calls send values to params in their possible targets, and receive + // results. + void visitCall(Call* curr) { + auto* target = getModule()->getFunction(curr->target); + handleCall( + curr, + [&](Index i) { + return LocalLocation{target, i, 0}; + }, + [&](Index i) { + return ResultLocation{target, i}; + }); + } + void visitCallIndirect(CallIndirect* curr) { + // TODO: the table identity could also be used here + auto targetType = curr->heapType; + handleCall( + curr, + [&](Index i) { + return SignatureParamLocation{targetType, i}; + }, + [&](Index i) { + return SignatureResultLocation{targetType, i}; + }); + } + void visitCallRef(CallRef* curr) { + auto targetType = curr->target->type; + if (targetType != Type::unreachable) { + auto heapType = targetType.getHeapType(); + handleCall( + curr, + [&](Index i) { + return SignatureParamLocation{heapType, i}; + }, + [&](Index i) { + return SignatureResultLocation{heapType, i}; + }); + } + } + + // Creates a location for a null of a particular type and adds a root for it. + // Such roots are where the default value of an i32 local comes from, or the + // value in a ref.null. + Location getNullLocation(Type type) { + auto location = NullLocation{type}; + addRoot(location, PossibleContents::literal(Literal::makeZero(type))); + return location; + } + + // Iterates over a list of children and adds links from them. The target of + // those link is created using a function that is passed in, which receives + // the index of the child. + void linkChildList(ExpressionList& operands, + std::function<Location(Index)> makeTarget) { + Index i = 0; + for (auto* operand : operands) { + // This helper is not used from places that allow a tuple (hence we can + // hardcode the index 0 a few lines down). + assert(!operand->type.isTuple()); + + if (isRelevant(operand->type)) { + info.links.push_back({ExpressionLocation{operand, 0}, makeTarget(i)}); + } + i++; + } + } + + void visitStructNew(StructNew* curr) { + if (curr->type == Type::unreachable) { + return; + } + auto type = curr->type.getHeapType(); + if (curr->isWithDefault()) { + // Link the default values to the struct's fields. + auto& fields = type.getStruct().fields; + for (Index i = 0; i < fields.size(); i++) { + info.links.push_back( + {getNullLocation(fields[i].type), DataLocation{type, i}}); + } + } else { + // Link the operands to the struct's fields. + linkChildList(curr->operands, [&](Index i) { + return DataLocation{type, i}; + }); + } + addRoot(curr, PossibleContents::exactType(curr->type)); + } + void visitArrayNew(ArrayNew* curr) { + if (curr->type == Type::unreachable) { + return; + } + auto type = curr->type.getHeapType(); + if (curr->init) { + info.links.push_back( + {ExpressionLocation{curr->init, 0}, DataLocation{type, 0}}); + } else { + info.links.push_back( + {getNullLocation(type.getArray().element.type), DataLocation{type, 0}}); + } + addRoot(curr, PossibleContents::exactType(curr->type)); + } + void visitArrayInit(ArrayInit* curr) { + if (curr->type == Type::unreachable) { + return; + } + if (!curr->values.empty()) { + auto type = curr->type.getHeapType(); + linkChildList(curr->values, [&](Index i) { + // The index i is ignored, as we do not track indexes in Arrays - + // everything is modeled as if at index 0. + return DataLocation{type, 0}; + }); + } + addRoot(curr, PossibleContents::exactType(curr->type)); + } + + // Struct operations access the struct fields' locations. + void visitStructGet(StructGet* curr) { + if (!isRelevant(curr->ref)) { + // If references are irrelevant then we will ignore them, and we won't + // have information about this struct.get's reference, which means we + // won't have information to compute relevant values for this struct.get. + // Instead, just mark this as an unknown value (root). + addRoot(curr); + return; + } + // The struct.get will receive different values depending on the contents + // in the reference, so mark us as the parent of the ref, and we will + // handle all of this in a special way during the flow. Note that we do + // not even create a DataLocation here; anything that we need will be + // added during the flow. + addChildParentLink(curr->ref, curr); + } + void visitStructSet(StructSet* curr) { + if (curr->ref->type == Type::unreachable) { + return; + } + // See comment on visitStructGet. Here we also connect the value. + addChildParentLink(curr->ref, curr); + addChildParentLink(curr->value, curr); + } + // Array operations access the array's location, parallel to how structs work. + void visitArrayGet(ArrayGet* curr) { + if (!isRelevant(curr->ref)) { + addRoot(curr); + return; + } + addChildParentLink(curr->ref, curr); + } + void visitArraySet(ArraySet* curr) { + if (curr->ref->type == Type::unreachable) { + return; + } + addChildParentLink(curr->ref, curr); + addChildParentLink(curr->value, curr); + } + + void visitArrayLen(ArrayLen* curr) { + // TODO: optimize when possible (perhaps we can infer a Literal for the + // length) + addRoot(curr); + } + void visitArrayCopy(ArrayCopy* curr) { + if (curr->type == Type::unreachable) { + return; + } + // Our flow handling of GC data is not simple: we have special code for each + // read and write instruction. Therefore, to avoid adding special code for + // ArrayCopy, model it as a combination of an ArrayRead and ArrayWrite, by + // just emitting fake expressions for those. The fake expressions are not + // part of the main IR, which is potentially confusing during debugging, + // however, which is a downside. + Builder builder(*getModule()); + auto* get = builder.makeArrayGet(curr->srcRef, curr->srcIndex); + visitArrayGet(get); + auto* set = builder.makeArraySet(curr->destRef, curr->destIndex, get); + visitArraySet(set); + } + + // TODO: Model which throws can go to which catches. For now, anything thrown + // is sent to the location of that tag, and any catch of that tag can + // read them. + void visitTry(Try* curr) { + receiveChildValue(curr->body, curr); + for (auto* catchBody : curr->catchBodies) { + receiveChildValue(catchBody, curr); + } + + auto numTags = curr->catchTags.size(); + for (Index tagIndex = 0; tagIndex < numTags; tagIndex++) { + auto tag = curr->catchTags[tagIndex]; + auto* body = curr->catchBodies[tagIndex]; + + auto params = getModule()->getTag(tag)->sig.params; + if (params.size() == 0) { + continue; + } + + // Find the pop of the tag's contents. The body must start with such a + // pop, which might be of a tuple. + auto* pop = EHUtils::findPop(body); + // There must be a pop since we checked earlier if it was an empty tag, + // and would not reach here. + assert(pop); + assert(pop->type.size() == params.size()); + for (Index i = 0; i < params.size(); i++) { + if (isRelevant(params[i])) { + info.links.push_back( + {TagLocation{tag, i}, ExpressionLocation{pop, i}}); + } + } + +#ifndef NDEBUG + // This pop was in the position we can handle, note that (see visitPop + // for details). + handledPops++; +#endif + } + } + void visitThrow(Throw* curr) { + auto& operands = curr->operands; + if (!isRelevant(operands)) { + return; + } + + auto tag = curr->tag; + for (Index i = 0; i < curr->operands.size(); i++) { + info.links.push_back( + {ExpressionLocation{operands[i], 0}, TagLocation{tag, i}}); + } + } + void visitRethrow(Rethrow* curr) {} + + void visitTupleMake(TupleMake* curr) { + if (isRelevant(curr->type)) { + for (Index i = 0; i < curr->operands.size(); i++) { + info.links.push_back({ExpressionLocation{curr->operands[i], 0}, + ExpressionLocation{curr, i}}); + } + } + } + void visitTupleExtract(TupleExtract* curr) { + if (isRelevant(curr->type)) { + info.links.push_back({ExpressionLocation{curr->tuple, curr->index}, + ExpressionLocation{curr, 0}}); + } + } + + // Adds a result to the current function, such as from a return or the value + // that flows out. + void addResult(Expression* value) { + if (value && isRelevant(value->type)) { + for (Index i = 0; i < value->type.size(); i++) { + info.links.push_back( + {ExpressionLocation{value, i}, ResultLocation{getFunction(), i}}); + } + } + } + + void visitReturn(Return* curr) { addResult(curr->value); } + + void visitFunction(Function* curr) { + // Vars have an initial value. + for (Index i = 0; i < curr->getNumLocals(); i++) { + if (curr->isVar(i)) { + Index j = 0; + for (auto t : curr->getLocalType(i)) { + if (t.isDefaultable()) { + info.links.push_back( + {getNullLocation(t), LocalLocation{curr, i, j}}); + } + j++; + } + } + } + + // Functions with a result can flow a value out from their body. + addResult(curr->body); + + // See visitPop(). + assert(handledPops == totalPops); + } + + // Helpers + + // Handles the value sent in a break instruction. Does not handle anything + // else like the condition etc. + void handleBreakValue(Expression* curr) { + BranchUtils::operateOnScopeNameUsesAndSentValues( + curr, [&](Name target, Expression* value) { + if (value && isRelevant(value->type)) { + for (Index i = 0; i < value->type.size(); i++) { + // Breaks send the contents of the break value to the branch target + // that the break goes to. + info.links.push_back( + {ExpressionLocation{value, i}, + BreakTargetLocation{getFunction(), target, i}}); + } + } + }); + } + + // Handles receiving values from breaks at the target (as in a block). + void handleBreakTarget(Expression* curr) { + if (isRelevant(curr->type)) { + BranchUtils::operateOnScopeNameDefs(curr, [&](Name target) { + for (Index i = 0; i < curr->type.size(); i++) { + info.links.push_back({BreakTargetLocation{getFunction(), target, i}, + ExpressionLocation{curr, i}}); + } + }); + } + } + + // Connect a child's value to the parent, that is, all content in the child is + // now considered possible in the parent as well. + void receiveChildValue(Expression* child, Expression* parent) { + if (isRelevant(parent) && isRelevant(child)) { + // The tuple sizes must match (or, if not a tuple, the size should be 1 in + // both cases). + assert(child->type.size() == parent->type.size()); + for (Index i = 0; i < child->type.size(); i++) { + info.links.push_back( + {ExpressionLocation{child, i}, ExpressionLocation{parent, i}}); + } + } + } + + // See the comment on CollectedFuncInfo::childParents. + void addChildParentLink(Expression* child, Expression* parent) { + if (isRelevant(child->type)) { + info.childParents[child] = parent; + } + } + + // Adds a root, if the expression is relevant. If the value is not specified, + // mark the root as containing Many (which is the common case, so avoid + // verbose code). + void addRoot(Expression* curr, + PossibleContents contents = PossibleContents::many()) { + if (isRelevant(curr)) { + addRoot(ExpressionLocation{curr, 0}, contents); + } + } + + // As above, but given an arbitrary location and not just an expression. + void addRoot(Location loc, + PossibleContents contents = PossibleContents::many()) { + info.roots.emplace_back(loc, contents); + } +}; + +// Main logic for building data for the flow analysis and then performing that +// analysis. +struct Flower { + Module& wasm; + + Flower(Module& wasm); + + // Each LocationIndex will have one LocationInfo that contains the relevant + // information we need for each location. + struct LocationInfo { + // The location at this index. + Location location; + + // The possible contents in that location. + PossibleContents contents; + + // A list of the target locations to which this location sends content. + // TODO: benchmark SmallVector<1> here, as commonly there may be a single + // target (an expression has one parent) + std::vector<LocationIndex> targets; + + LocationInfo(Location location) : location(location) {} + }; + + // Maps location indexes to the info stored there, as just described above. + std::vector<LocationInfo> locations; + + // Reverse mapping of locations to their indexes. + std::unordered_map<Location, LocationIndex> locationIndexes; + + const Location& getLocation(LocationIndex index) { + assert(index < locations.size()); + return locations[index].location; + } + + PossibleContents& getContents(LocationIndex index) { + assert(index < locations.size()); + return locations[index].contents; + } + +private: + std::vector<LocationIndex>& getTargets(LocationIndex index) { + assert(index < locations.size()); + return locations[index].targets; + } + + // Convert the data into the efficient LocationIndex form we will use during + // the flow analysis. This method returns the index of a location, allocating + // one if this is the first time we see it. + LocationIndex getIndex(const Location& location) { + auto iter = locationIndexes.find(location); + if (iter != locationIndexes.end()) { + return iter->second; + } + + // Allocate a new index here. + size_t index = locations.size(); +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " new index " << index << " for "; + dump(location); +#endif + if (index >= std::numeric_limits<LocationIndex>::max()) { + // 32 bits should be enough since each location takes at least one byte + // in the binary, and we don't have 4GB wasm binaries yet... do we? + Fatal() << "Too many locations for 32 bits"; + } + locations.emplace_back(location); + locationIndexes[location] = index; + + return index; + } + + bool hasIndex(const Location& location) { + return locationIndexes.find(location) != locationIndexes.end(); + } + + IndexLink getIndexes(const LocationLink& link) { + return {getIndex(link.from), getIndex(link.to)}; + } + + // See the comment on CollectedFuncInfo::childParents. This is the merged info + // from all the functions and the global scope. + std::unordered_map<LocationIndex, LocationIndex> childParents; + + // The work remaining to do during the flow: locations that we need to flow + // content from, after new content reached them. + // + // Using a set here is efficient as multiple updates may arrive to a location + // before we get to processing it. + // + // The items here could be {location, newContents}, but it is more efficient + // to have already written the new contents to the main data structure. That + // avoids larger data here, and also, updating the contents as early as + // possible is helpful as anything reading them meanwhile (before we get to + // their work item in the queue) will see the newer value, possibly avoiding + // flowing an old value that would later be overwritten. +#ifdef POSSIBLE_CONTENTS_INSERT_ORDERED + InsertOrderedSet<LocationIndex> workQueue; +#else + std::unordered_set<LocationIndex> workQueue; +#endif + + // All existing links in the graph. We keep this to know when a link we want + // to add is new or not. + std::unordered_set<IndexLink> links; + + // Update a location with new contents that are added to everything already + // present there. If the update changes the contents at that location (if + // there was anything new) then we also need to flow from there, which we will + // do by adding the location to the work queue, and eventually flowAfterUpdate + // will be called on this location. + // + // Returns whether it is worth sending new contents to this location in the + // future. If we return false, the sending location never needs to do that + // ever again. + bool updateContents(LocationIndex locationIndex, + PossibleContents newContents); + + // Slow helper that converts a Location to a LocationIndex. This should be + // avoided. TODO: remove the remaining uses of this. + bool updateContents(const Location& location, + const PossibleContents& newContents) { + return updateContents(getIndex(location), newContents); + } + + // Flow contents from a location where a change occurred. This sends the new + // contents to all the normal targets of this location (using + // flowToTargetsAfterUpdate), and also handles special cases of flow after. + void flowAfterUpdate(LocationIndex locationIndex); + + // Internal part of flowAfterUpdate that handles sending new values to the + // given location index's normal targets (that is, the ones listed in the + // |targets| vector). + void flowToTargetsAfterUpdate(LocationIndex locationIndex, + const PossibleContents& contents); + + // Add a new connection while the flow is happening. If the link already + // exists it is not added. + void connectDuringFlow(Location from, Location to); + + // Contents sent to a global location can be filtered in a special way during + // the flow, which is handled in this helper. + void filterGlobalContents(PossibleContents& contents, + const GlobalLocation& globalLoc); + + // Reads from GC data: a struct.get or array.get. This is given the type of + // the read operation, the field that is read on that type, the known contents + // in the reference the read receives, and the read instruction itself. We + // compute where we need to read from based on the type and the ref contents + // and get that data, adding new links in the graph as needed. + void readFromData(HeapType declaredHeapType, + Index fieldIndex, + const PossibleContents& refContents, + Expression* read); + + // Similar to readFromData, but does a write for a struct.set or array.set. + void writeToData(Expression* ref, Expression* value, Index fieldIndex); + + // Special handling for RefCast during the flow: RefCast only admits valid + // values to flow through it. + void flowRefCast(const PossibleContents& contents, RefCast* cast); + + // We will need subtypes during the flow, so compute them once ahead of time. + std::unique_ptr<SubTypes> subTypes; + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + // Dump out a location for debug purposes. + void dump(Location location); +#endif +}; + +Flower::Flower(Module& wasm) : wasm(wasm) { +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "parallel phase\n"; +#endif + + // First, collect information from each function. + ModuleUtils::ParallelFunctionAnalysis<CollectedFuncInfo> analysis( + wasm, [&](Function* func, CollectedFuncInfo& info) { + InfoCollector finder(info); + + if (func->imported()) { + // Imports return unknown values. + for (Index i = 0; i < func->getResults().size(); i++) { + finder.addRoot(ResultLocation{func, i}, PossibleContents::many()); + } + return; + } + + finder.walkFunctionInModule(func, &wasm); + }); + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "single phase\n"; +#endif + + // Also walk the global module code (for simplicity, also add it to the + // function map, using a "function" key of nullptr). + auto& globalInfo = analysis.map[nullptr]; + InfoCollector finder(globalInfo); + finder.walkModuleCode(&wasm); + + // Connect global init values (which we've just processed, as part of the + // module code) to the globals they initialize. + for (auto& global : wasm.globals) { + if (global->imported()) { + // Imports are unknown values. + finder.addRoot(GlobalLocation{global->name}, PossibleContents::many()); + continue; + } + auto* init = global->init; + if (finder.isRelevant(init->type)) { + globalInfo.links.push_back( + {ExpressionLocation{init, 0}, GlobalLocation{global->name}}); + } + } + + // Merge the function information into a single large graph that represents + // the entire program all at once, indexing and deduplicating everything as we + // go. + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "merging+indexing phase\n"; +#endif + + // The merged roots. (Note that all other forms of merged data are declared at + // the class level, since we need them during the flow, but the roots are only + // needed to start the flow, so we can declare them here.) + std::unordered_map<Location, PossibleContents> roots; + + for (auto& [func, info] : analysis.map) { + for (auto& link : info.links) { + links.insert(getIndexes(link)); + } + for (auto& [root, value] : info.roots) { + roots[root] = value; + + // Ensure an index even for a root with no links to it - everything needs + // an index. + getIndex(root); + } + for (auto [child, parent] : info.childParents) { + // In practice we do not have any childParent connections with a tuple; + // assert on that just to be safe. + assert(!child->type.isTuple()); + childParents[getIndex(ExpressionLocation{child, 0})] = + getIndex(ExpressionLocation{parent, 0}); + } + } + + // We no longer need the function-level info. + analysis.map.clear(); + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "external phase\n"; +#endif + + // Parameters of exported functions are roots, since exports can have callers + // that we can't see, so anything might arrive there. + auto calledFromOutside = [&](Name funcName) { + auto* func = wasm.getFunction(funcName); + for (Index i = 0; i < func->getParams().size(); i++) { + roots[LocalLocation{func, i, 0}] = PossibleContents::many(); + } + }; + + for (auto& ex : wasm.exports) { + if (ex->kind == ExternalKind::Function) { + calledFromOutside(ex->value); + } else if (ex->kind == ExternalKind::Table) { + // If any table is exported, assume any function in any table (including + // other tables) can be called from the outside. + // TODO: This could be more precise about which tables are exported and + // which are not: perhaps one table is exported but we can optimize + // the functions in another table, which is not exported. However, + // it is simpler to treat them all the same, and this handles the + // common case of no tables being exported at all. + // TODO: This does not handle table.get/table.set, or call_ref, for which + // we'd need to see which references are used and which escape etc. + // For now, assume a closed world for such such advanced use cases / + // assume this pass won't be run in them anyhow. + // TODO: do this only once if multiple tables are exported + for (auto& elementSegment : wasm.elementSegments) { + for (auto* curr : elementSegment->data) { + if (auto* refFunc = curr->dynCast<RefFunc>()) { + calledFromOutside(refFunc->func); + } + } + } + } + } + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "func phase\n"; +#endif + + // Connect function parameters to their signature, so that any indirect call + // of that signature will reach them. + // TODO: find which functions are even taken by reference + for (auto& func : wasm.functions) { + for (Index i = 0; i < func->getParams().size(); i++) { + links.insert(getIndexes({SignatureParamLocation{func->type, i}, + LocalLocation{func.get(), i, 0}})); + } + for (Index i = 0; i < func->getResults().size(); i++) { + links.insert(getIndexes({ResultLocation{func.get(), i}, + SignatureResultLocation{func->type, i}})); + } + } + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "struct phase\n"; +#endif + + if (getTypeSystem() == TypeSystem::Nominal || + getTypeSystem() == TypeSystem::Isorecursive) { + subTypes = std::make_unique<SubTypes>(wasm); + } + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "Link-targets phase\n"; +#endif + + // Add all links to the targets vectors of the source locations, which we will + // use during the flow. + for (auto& link : links) { + getTargets(link.from).push_back(link.to); + } + +#ifndef NDEBUG + // Each vector of targets (which is a vector for efficiency) must have no + // duplicates. + for (auto& info : locations) { + disallowDuplicates(info.targets); + } +#endif + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "roots phase\n"; +#endif + + // Set up the roots, which are the starting state for the flow analysis: send + // their initial content to them to start the flow. + for (const auto& [location, value] : roots) { +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " init root\n"; + dump(location); + value.dump(std::cout, &wasm); + std::cout << '\n'; +#endif + + updateContents(location, value); + } + +#ifdef POSSIBLE_CONTENTS_DEBUG + std::cout << "flow phase\n"; + size_t iters = 0; +#endif + + // Flow the data while there is still stuff flowing. + while (!workQueue.empty()) { +#ifdef POSSIBLE_CONTENTS_DEBUG + iters++; + if ((iters & 255) == 0) { + std::cout << iters++ << " iters, work left: " << workQueue.size() << '\n'; + } +#endif + + auto iter = workQueue.begin(); + auto locationIndex = *iter; + workQueue.erase(iter); + + flowAfterUpdate(locationIndex); + } + + // TODO: Add analysis and retrieval logic for fields of immutable globals, + // including multiple levels of depth (necessary for itables in j2wasm). +} + +bool Flower::updateContents(LocationIndex locationIndex, + PossibleContents newContents) { + auto& contents = getContents(locationIndex); + auto oldContents = contents; + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << "updateContents\n"; + dump(getLocation(locationIndex)); + contents.dump(std::cout, &wasm); + std::cout << "\n with new contents \n"; + newContents.dump(std::cout, &wasm); + std::cout << '\n'; +#endif + + contents.combine(newContents); + + if (contents.isNone()) { + // There is still nothing here. There is nothing more to do here but to + // return that it is worth sending more. + return true; + } + + // 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 + // 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). + bool worthSendingMore = !contents.isMany(); + if (!contents.getType().isRef() && contents.isExactType()) { + worthSendingMore = false; + } + + if (contents == oldContents) { + // Nothing actually changed, so just return. + return worthSendingMore; + } + + // Handle special cases: Some locations can only contain certain contents, so + // filter accordingly. + if (auto* globalLoc = + std::get_if<GlobalLocation>(&getLocation(locationIndex))) { + filterGlobalContents(contents, *globalLoc); + if (contents == oldContents) { + // Nothing actually changed after filtering, so just return. + return worthSendingMore; + } + } + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " updateContents has something new\n"; + contents.dump(std::cout, &wasm); + std::cout << '\n'; +#endif + + // Add a work item if there isn't already. + workQueue.insert(locationIndex); + + return worthSendingMore; +} + +void Flower::flowAfterUpdate(LocationIndex locationIndex) { + const auto location = getLocation(locationIndex); + auto& contents = getContents(locationIndex); + + // We are called after a change at a location. A change means that some + // content has arrived, since we never send empty values around. Assert on + // that. + assert(!contents.isNone()); + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << "\nflowAfterUpdate to:\n"; + dump(location); + std::cout << " arriving:\n"; + contents.dump(std::cout, &wasm); + std::cout << '\n'; +#endif + + // Flow the contents to the normal targets of this location. + flowToTargetsAfterUpdate(locationIndex, contents); + + // We are mostly done, except for handling interesting/special cases in the + // flow, additional operations that we need to do aside from sending the new + // contents to the normal (statically linked) targets. + + if (auto* exprLoc = std::get_if<ExpressionLocation>(&location)) { + auto iter = childParents.find(locationIndex); + if (iter == childParents.end()) { + return; + } + + // This is indeed one of the special cases where it is the child of a + // parent, and we need to do some special handling because of that child- + // parent connection. + auto* child = exprLoc->expr; + auto parentIndex = iter->second; + auto* parent = std::get<ExpressionLocation>(getLocation(parentIndex)).expr; + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " special, parent:\n" << *parent << '\n'; +#endif + + if (auto* get = parent->dynCast<StructGet>()) { + // |child| is the reference child of a struct.get. + assert(get->ref == child); + readFromData(get->ref->type.getHeapType(), get->index, contents, get); + } else if (auto* set = parent->dynCast<StructSet>()) { + // |child| is either the reference or the value child of a struct.set. + assert(set->ref == child || set->value == child); + writeToData(set->ref, set->value, set->index); + } else if (auto* get = parent->dynCast<ArrayGet>()) { + assert(get->ref == child); + readFromData(get->ref->type.getHeapType(), 0, contents, get); + } else if (auto* set = parent->dynCast<ArraySet>()) { + assert(set->ref == child || set->value == child); + writeToData(set->ref, set->value, 0); + } else if (auto* cast = parent->dynCast<RefCast>()) { + assert(cast->ref == child); + flowRefCast(contents, cast); + } else { + // TODO: ref.test and all other casts can be optimized (see the cast + // helper code used in OptimizeInstructions and RemoveUnusedBrs) + WASM_UNREACHABLE("bad childParents content"); + } + } +} + +void Flower::flowToTargetsAfterUpdate(LocationIndex locationIndex, + const PossibleContents& contents) { + // Send the new contents to all the targets of this location. As we do so, + // prune any targets that we do not need to bother sending content to in the + // future, to save space and work later. + auto& targets = getTargets(locationIndex); + targets.erase(std::remove_if(targets.begin(), + targets.end(), + [&](LocationIndex targetIndex) { +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " send to target\n"; + dump(getLocation(targetIndex)); +#endif + return !updateContents(targetIndex, contents); + }), + targets.end()); + + if (contents.isMany()) { + // We contain Many, and just called updateContents on our targets to send + // that value to them. We'll never need to send anything from here ever + // again, since we sent the worst case possible already, so we can just + // clear our targets vector. But we should have already removed all the + // targets in the above remove_if operation, since they should have all + // notified us that we do not need to send them any more updates. + assert(targets.empty()); + } +} + +void Flower::connectDuringFlow(Location from, Location to) { + auto newLink = LocationLink{from, to}; + auto newIndexLink = getIndexes(newLink); + if (links.count(newIndexLink) == 0) { + // This is a new link. Add it to the known links. + links.insert(newIndexLink); + + // Add it to the |targets| vector. + auto& targets = getTargets(newIndexLink.from); + targets.push_back(newIndexLink.to); +#ifndef NDEBUG + disallowDuplicates(targets); +#endif + + // In addition to adding the link, which will ensure new contents appearing + // later will be sent along, we also update with the current contents. + updateContents(to, getContents(getIndex(from))); + } +} + +void Flower::filterGlobalContents(PossibleContents& contents, + const GlobalLocation& globalLoc) { + auto* global = wasm.getGlobal(globalLoc.name); + if (global->mutable_ == Immutable) { + // This is an immutable global. We never need to consider this value as + // "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()) { + contents = PossibleContents::global(global->name, global->type); + + // TODO: We could do better here, to set global->init->type instead of + // global->type, or even the contents.getType() - either of those + // may be more refined. But other passes will handle that in + // general (by refining the global's type). + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " setting immglobal to ImmutableGlobal\n"; + contents.dump(std::cout, &wasm); + std::cout << '\n'; +#endif + } + } +} + +void Flower::readFromData(HeapType declaredHeapType, + Index fieldIndex, + const PossibleContents& refContents, + 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 + // 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. + // + // What can be confusing is that the information about the reference is also + // inferred during the flow. That is, we use our current information about the + // reference to decide what to do here. But the flow is not finished yet! + // To keep things valid, we must therefore react to changes in either the + // reference - when we see that more types might be read from here - or the + // DataLocations - when new things are written to the data we can read from. + // Specifically, at every point in time we want to preserve the property that + // we've read from all relevant types based on the current reference, and + // we've read the very latest possible contents from those types. And then + // since we preserve that property til the end of the flow, it is also valid + // then. At the end of the flow, the current reference's contents are the + // final and correct contents for that location, which means we've ended up + // with the proper result: the struct.get reads everything it should. + // + // To implement what was just described, we call this function when the + // reference is updated. This function will then set up connections in the + // graph so that updates to the relevant DataLocations will reach us in the + // future. + + if (refContents.isNull() || refContents.isNone()) { + // Nothing is read here. + return; + } + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " add special reads\n"; +#endif + + if (refContents.isExactType()) { + // 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. + // 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). + // See the test TODO with text "We optimize some of this, but stop at + // reading from the immutable global" + // Note that this cannot be a Literal, since this is a reference, and the + // only reference literals we have are nulls (handled above) and ref.func. + // ref.func is not valid in struct|array.get, so the code would trap at + // runtime, and also it would never reach here as because of wasm validation + // it would be cast to a struct/array type, and our special ref.cast code + // would filter it out. + assert(refContents.isMany() || refContents.isGlobal()); + + // We create a ConeReadLocation for the canonical cone of this type, to + // avoid bloating the graph, see comment on ConeReadLocation(). + // TODO: A cone with no subtypes needs no canonical location, just + // add one direct link here. + auto coneReadLocation = ConeReadLocation{declaredHeapType, fieldIndex}; + if (!hasIndex(coneReadLocation)) { + // This is the first time we use this location, so create the links for it + // in the graph. + for (auto type : subTypes->getAllSubTypes(declaredHeapType)) { + connectDuringFlow(DataLocation{type, fieldIndex}, coneReadLocation); + } + + // TODO: if the old contents here were an exact type then we have an old + // link here that we could remove as it is redundant (the cone + // contains the exact type among the others). But removing links + // is not efficient, so maybe not worth it. + } + + // Link to the canonical location. + connectDuringFlow(coneReadLocation, ExpressionLocation{read, 0}); + } +} + +void Flower::writeToData(Expression* ref, Expression* value, Index fieldIndex) { +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " add special writes\n"; +#endif + + // We could set up links here as we do for reads, but as we get to this code + // in any case, we can just flow the values forward directly. This avoids + // adding any links (edges) to the graph (and edges are what we want to avoid + // adding, as there can be a quadratic number of them). In other words, we'll + // loop over the places we need to send info to, which we can figure out in a + // simple way, and by doing so we avoid materializing edges into the graph. + // + // Note that this is different from readFromData, above, which does add edges + // to the graph (and works hard to add as few as possible, see the "canonical + // cone reads" logic). The difference is because readFromData must "subscribe" + // to get notifications from the relevant DataLocations. But when writing that + // is not a problem: whenever a change happens in the reference or the value + // of a struct.set then this function will get called, and those are the only + // things we care about. And we can then just compute the values we are + // sending (based on the current contents of the reference and the value), and + // where we should send them to, and do that right here. (And as commented in + // readFromData, that is guaranteed to give us the right result in the end: at + // every point in time we send the right data, so when the flow is finished + // we've sent information based on the final and correct information about our + // reference and value.) + + auto refContents = getContents(getIndex(ExpressionLocation{ref, 0})); + auto valueContents = getContents(getIndex(ExpressionLocation{value, 0})); + if (refContents.isNone() || refContents.isNull()) { + return; + } + if (refContents.hasExactType()) { + // Update the one possible type here. + auto heapLoc = + DataLocation{refContents.getType().getHeapType(), fieldIndex}; + updateContents(heapLoc, valueContents); + } else { + assert(refContents.isMany() || refContents.isGlobal()); + + // Update all possible subtypes here. + auto type = ref->type.getHeapType(); + for (auto subType : subTypes->getAllSubTypes(type)) { + auto heapLoc = DataLocation{subType, fieldIndex}; + updateContents(heapLoc, valueContents); + } + } +} + +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 { + auto intendedType = cast->getIntendedType(); + bool isSubType = + HeapType::isSubType(contents.getType().getHeapType(), 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(intendedType))); + } + } + if (!filtered.isNone()) { +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 + std::cout << " ref.cast passing through\n"; + filtered.dump(std::cout); + std::cout << '\n'; +#endif + updateContents(ExpressionLocation{cast, 0}, filtered); + } +} + +#if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 +void Flower::dump(Location location) { + if (auto* loc = std::get_if<ExpressionLocation>(&location)) { + std::cout << " exprloc \n" << *loc->expr << '\n'; + } else if (auto* loc = std::get_if<DataLocation>(&location)) { + std::cout << " dataloc "; + if (wasm.typeNames.count(loc->type)) { + std::cout << '$' << wasm.typeNames[loc->type].name; + } else { + std::cout << loc->type << '\n'; + } + std::cout << " : " << loc->index << '\n'; + } else if (auto* loc = std::get_if<TagLocation>(&location)) { + std::cout << " tagloc " << loc->tag << '\n'; + } else if (auto* loc = std::get_if<LocalLocation>(&location)) { + std::cout << " localloc " << loc->func->name << " : " << loc->index + << " tupleIndex " << loc->tupleIndex << '\n'; + } else if (auto* loc = std::get_if<ResultLocation>(&location)) { + std::cout << " resultloc " << loc->func->name << " : " << loc->index + << '\n'; + } else if (auto* loc = std::get_if<GlobalLocation>(&location)) { + std::cout << " globalloc " << loc->name << '\n'; + } else if (auto* loc = std::get_if<BreakTargetLocation>(&location)) { + std::cout << " branchloc " << loc->func->name << " : " << loc->target + << " tupleIndex " << loc->tupleIndex << '\n'; + } else if (auto* loc = std::get_if<SignatureParamLocation>(&location)) { + WASM_UNUSED(loc); + std::cout << " sigparamloc " << '\n'; + } else if (auto* loc = std::get_if<SignatureResultLocation>(&location)) { + WASM_UNUSED(loc); + std::cout << " sigresultloc " << '\n'; + } else if (auto* loc = std::get_if<NullLocation>(&location)) { + std::cout << " Nullloc " << loc->type << '\n'; + } else if (auto* loc = std::get_if<UniqueLocation>(&location)) { + std::cout << " Specialloc " << loc->index << '\n'; + } else { + std::cout << " (other)\n"; + } +} +#endif + +} // anonymous namespace + +void ContentOracle::analyze() { + Flower flower(wasm); + for (LocationIndex i = 0; i < flower.locations.size(); i++) { + locationContents[flower.getLocation(i)] = flower.getContents(i); + } +} + +} // namespace wasm diff --git a/src/ir/possible-contents.h b/src/ir/possible-contents.h new file mode 100644 index 000000000..38bc263e9 --- /dev/null +++ b/src/ir/possible-contents.h @@ -0,0 +1,538 @@ +/* + * Copyright 2022 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef wasm_ir_possible_contents_h +#define wasm_ir_possible_contents_h + +#include <variant> + +#include "ir/possible-constant.h" +#include "ir/subtypes.h" +#include "support/small_vector.h" +#include "wasm-builder.h" +#include "wasm.h" + +namespace wasm { + +// +// PossibleContents represents the possible contents at a particular location +// (such as in a local or in a function parameter). This is a little similar to +// PossibleConstantValues, but considers more types of contents than constant +// values - in particular, it can track types to some extent. +// +// The specific contents this can vary over are: +// +// * None: No possible value. +// +// * Literal: One possible constant value like an i32 of 42. +// +// * Global: The name of a global whose value is here. We do not know +// the actual value at compile time, but we know it is equal +// 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. +// 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 +// 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. +// +// * Many: Anything else. Many things are possible here, and we do +// not track what they might be, so we must assume the worst +// in the calling code. +// +class PossibleContents { + struct None : public std::monostate {}; + + struct GlobalInfo { + Name name; + // The type of the global in the module. We stash this here so that we do + // not need to pass around a module all the time. + // TODO: could we save size in this variant if we did pass around the + // module? + Type type; + bool operator==(const GlobalInfo& other) const { + return name == other.name && type == other.type; + } + }; + + using ExactType = Type; + + 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>; + Variant value; + +public: + PossibleContents() : value(None()) {} + PossibleContents(const PossibleContents& other) = default; + + template<typename T> explicit PossibleContents(T val) : value(val) {} + + // Most users will use one of the following static functions to construct a + // new instance: + + static PossibleContents none() { return PossibleContents{None()}; } + static PossibleContents literal(Literal c) { return PossibleContents{c}; } + static PossibleContents global(Name name, Type type) { + return PossibleContents{GlobalInfo{name, type}}; + } + static PossibleContents exactType(Type type) { + return PossibleContents{ExactType(type)}; + } + static PossibleContents many() { return PossibleContents{Many()}; } + + PossibleContents& operator=(const PossibleContents& other) = default; + + bool operator==(const PossibleContents& other) const { + return value == other.value; + } + + bool operator!=(const PossibleContents& other) const { + return !(*this == other); + } + + // Combine the information in a given PossibleContents to this one. The + // contents here will then include whatever content was possible in |other|. + void combine(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); } + bool isExactType() const { return std::get_if<Type>(&value); } + bool isMany() const { return std::get_if<Many>(&value); } + + Literal getLiteral() const { + assert(isLiteral()); + return std::get<Literal>(value); + } + + Name getGlobal() const { + assert(isGlobal()); + return std::get<GlobalInfo>(value).name; + } + + bool isNull() const { return isLiteral() && getLiteral().isNull(); } + + // 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(). + // + // If no type is possible, return unreachable; if many types are, return none. + Type getType() const { + if (auto* literal = std::get_if<Literal>(&value)) { + 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 (std::get_if<None>(&value)) { + return Type::unreachable; + } else if (std::get_if<Many>(&value)) { + return Type::none; + } else { + WASM_UNREACHABLE("bad value"); + } + } + + // 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(); } + + // 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. + bool canMakeExpression() const { return isLiteral() || isGlobal(); } + + Expression* makeExpression(Module& wasm) { + assert(canMakeExpression()); + Builder builder(wasm); + if (isLiteral()) { + return builder.makeConstantExpression(getLiteral()); + } else { + auto name = getGlobal(); + return builder.makeGlobalGet(name, wasm.getGlobal(name)->type); + } + } + + size_t hash() const { + // Encode this using three bits for the variant type, then the rest of the + // contents. + if (isNone()) { + return 0; + } else if (isLiteral()) { + 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 (isMany()) { + return 4; + } else { + WASM_UNREACHABLE("bad variant"); + } + } + + void dump(std::ostream& o, Module* wasm = nullptr) const { + o << '['; + if (isNone()) { + o << "None"; + } else if (isLiteral()) { + o << "Literal " << getLiteral(); + auto t = getType(); + if (t.isRef()) { + auto h = t.getHeapType(); + o << " HT: " << h; + } + } else if (isGlobal()) { + o << "GlobalInfo $" << getGlobal(); + } else if (isExactType()) { + o << "ExactType " << getType(); + auto t = getType(); + if (t.isRef()) { + auto h = t.getHeapType(); + o << " HT: " << h; + if (wasm && wasm->typeNames.count(h)) { + o << " $" << wasm->typeNames[h].name; + } + if (t.isNullable()) { + o << " null"; + } + } + } else if (isMany()) { + o << "Many"; + } else { + WASM_UNREACHABLE("bad variant"); + } + o << ']'; + } +}; + +// The various *Location structs (ExpressionLocation, ResultLocation, etc.) +// describe particular locations where content can appear. + +// The location of a specific IR expression. +struct ExpressionLocation { + Expression* expr; + // If this expression contains a tuple then each index in the tuple will have + // its own location with a corresponding tupleIndex. If this is not a tuple + // then we only use tupleIndex 0. + Index tupleIndex; + bool operator==(const ExpressionLocation& other) const { + return expr == other.expr && tupleIndex == other.tupleIndex; + } +}; + +// The location of one of the results of a function. +struct ResultLocation { + Function* func; + Index index; + bool operator==(const ResultLocation& other) const { + return func == other.func && index == other.index; + } +}; + +// The location of one of the locals in a function (either a param or a var). +// TODO: would separating params from vars help? (SSA might be enough) +struct LocalLocation { + Function* func; + // The index of the local. + Index index; + // As in ExpressionLocation, the index inside the tuple, or 0 if not a tuple. + Index tupleIndex; + bool operator==(const LocalLocation& other) const { + return func == other.func && index == other.index && + tupleIndex == other.tupleIndex; + } +}; + +// The location of a break target in a function, identified by its name. +struct BreakTargetLocation { + Function* func; + Name target; + // As in ExpressionLocation, the index inside the tuple, or 0 if not a tuple. + // That is, if the branch target has a tuple type, then each branch to that + // location sends a tuple, and we'll have a separate BreakTargetLocation for + // each, indexed by the index in the tuple that the branch sends. + Index tupleIndex; + bool operator==(const BreakTargetLocation& other) const { + return func == other.func && target == other.target && + tupleIndex == other.tupleIndex; + } +}; + +// The location of a global in the module. +struct GlobalLocation { + Name name; + bool operator==(const GlobalLocation& other) const { + return name == other.name; + } +}; + +// The location of one of the parameters in a function signature. +struct SignatureParamLocation { + HeapType type; + Index index; + bool operator==(const SignatureParamLocation& other) const { + return type == other.type && index == other.index; + } +}; + +// The location of one of the results in a function signature. +struct SignatureResultLocation { + HeapType type; + Index index; + bool operator==(const SignatureResultLocation& other) const { + return type == other.type && index == other.index; + } +}; + +// The location of contents in a struct or array (i.e., things that can fit in a +// dataref). Note that this is specific to this type - it does not include data +// about subtypes or supertypes. +struct DataLocation { + HeapType type; + // The index of the field in a struct, or 0 for an array (where we do not + // attempt to differentiate by index). + Index index; + bool operator==(const DataLocation& other) const { + return type == other.type && index == other.index; + } +}; + +// The location of anything written to a particular tag. +struct TagLocation { + Name tag; + // If the tag has more than one element, we'll have a separate TagLocation for + // each, with corresponding indexes. If the tag has just one element we'll + // only have one TagLocation with index 0. + Index tupleIndex; + bool operator==(const TagLocation& other) const { + return tag == other.tag && tupleIndex == other.tupleIndex; + } +}; + +// A null value. This is used as the location of the default value of a var in a +// function, a null written to a struct field in struct.new_with_default, etc. +struct NullLocation { + Type type; + bool operator==(const NullLocation& other) const { + return type == other.type; + } +}; + +// A special type of location that does not refer to something concrete in the +// wasm, but is used to optimize the graph. A "cone read" is a struct.get or +// array.get of a type that is not exact, so it can read the "cone" of all the +// subtypes. In general a read of a cone type (as opposed to an exact type) will +// require N incoming links, from each of the N subtypes - and we need that +// for each struct.get of a cone. If there are M such gets then we have N * M +// edges for this. Instead, we make a single canonical "cone read" location, and +// add a single link to it from each get, which is only N + M (plus the cost +// of adding "latency" in requiring an additional step along the way for the +// data to flow along). +struct ConeReadLocation { + HeapType type; + // The index of the field in a struct, or 0 for an array (where we do not + // attempt to differentiate by index). + Index index; + bool operator==(const ConeReadLocation& other) const { + return type == other.type && index == other.index; + } +}; + +// A location is a variant over all the possible flavors of locations that we +// have. +using Location = std::variant<ExpressionLocation, + ResultLocation, + LocalLocation, + BreakTargetLocation, + GlobalLocation, + SignatureParamLocation, + SignatureResultLocation, + DataLocation, + TagLocation, + NullLocation, + ConeReadLocation>; + +} // namespace wasm + +namespace std { + +std::ostream& operator<<(std::ostream& stream, + const wasm::PossibleContents& contents); + +template<> struct hash<wasm::PossibleContents> { + size_t operator()(const wasm::PossibleContents& contents) const { + return contents.hash(); + } +}; + +// Define hashes of all the *Location flavors so that Location itself is +// hashable and we can use it in unordered maps and sets. + +template<> struct hash<wasm::ExpressionLocation> { + size_t operator()(const wasm::ExpressionLocation& loc) const { + return std::hash<std::pair<size_t, wasm::Index>>{}( + {size_t(loc.expr), loc.tupleIndex}); + } +}; + +template<> struct hash<wasm::ResultLocation> { + size_t operator()(const wasm::ResultLocation& loc) const { + return std::hash<std::pair<size_t, wasm::Index>>{}( + {size_t(loc.func), loc.index}); + } +}; + +template<> struct hash<wasm::LocalLocation> { + size_t operator()(const wasm::LocalLocation& loc) const { + return std::hash<std::pair<size_t, std::pair<wasm::Index, wasm::Index>>>{}( + {size_t(loc.func), {loc.index, loc.tupleIndex}}); + } +}; + +template<> struct hash<wasm::BreakTargetLocation> { + size_t operator()(const wasm::BreakTargetLocation& loc) const { + return std::hash<std::pair<size_t, std::pair<wasm::Name, wasm::Index>>>{}( + {size_t(loc.func), {loc.target, loc.tupleIndex}}); + } +}; + +template<> struct hash<wasm::GlobalLocation> { + size_t operator()(const wasm::GlobalLocation& loc) const { + return std::hash<wasm::Name>{}(loc.name); + } +}; + +template<> struct hash<wasm::SignatureParamLocation> { + size_t operator()(const wasm::SignatureParamLocation& loc) const { + return std::hash<std::pair<wasm::HeapType, wasm::Index>>{}( + {loc.type, loc.index}); + } +}; + +template<> struct hash<wasm::SignatureResultLocation> { + size_t operator()(const wasm::SignatureResultLocation& loc) const { + return std::hash<std::pair<wasm::HeapType, wasm::Index>>{}( + {loc.type, loc.index}); + } +}; + +template<> struct hash<wasm::DataLocation> { + size_t operator()(const wasm::DataLocation& loc) const { + return std::hash<std::pair<wasm::HeapType, wasm::Index>>{}( + {loc.type, loc.index}); + } +}; + +template<> struct hash<wasm::TagLocation> { + size_t operator()(const wasm::TagLocation& loc) const { + return std::hash<std::pair<wasm::Name, wasm::Index>>{}( + {loc.tag, loc.tupleIndex}); + } +}; + +template<> struct hash<wasm::NullLocation> { + size_t operator()(const wasm::NullLocation& loc) const { + return std::hash<wasm::Type>{}(loc.type); + } +}; + +template<> struct hash<wasm::ConeReadLocation> { + size_t operator()(const wasm::ConeReadLocation& loc) const { + return std::hash<std::pair<wasm::HeapType, wasm::Index>>{}( + {loc.type, loc.index}); + } +}; + +} // namespace std + +namespace wasm { + +// Analyze the entire wasm file to find which contents are possible in which +// locations. This assumes a closed world and starts from roots - newly created +// values - and propagates them to the locations they reach. After the +// analysis the user of this class can ask which contents are possible at any +// location. +// +// This focuses on useful information for the typical user of this API. +// Specifically, we find out: +// +// 1. What locations have no content reaching them at all. That means the code +// is unreachable. (Other passes may handle this, but ContentOracle does it +// for all things, so it might catch situations other passes do not cover; +// and, it takes no effort to support this here). +// 2. For all locations, we try to find when they must contain a constant value +// like i32(42) or ref.func(foo). +// 3. For locations that contain references, information about the subtypes +// possible there. For example, if something has wasm type anyref in the IR, +// we might find it must contain an exact type of something specific. +// +// Note that there is not much use in providing type info for locations that are +// *not* references. If a local is i32, for example, then it cannot contain any +// subtype anyhow, since i32 is not a reference and has no subtypes. And we know +// the type i32 from the wasm anyhow, that is, the caller will know it. +// Therefore the only useful information we can provide on top of the info +// already in the wasm is either that nothing can be there (1, above), or that a +// 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 +// 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 +// here. +class ContentOracle { + Module& wasm; + + void analyze(); + +public: + ContentOracle(Module& wasm) : wasm(wasm) { analyze(); } + + // Get the contents possible at a location. + PossibleContents getContents(Location location) { + auto iter = locationContents.find(location); + if (iter == locationContents.end()) { + // We know of no possible contents here. + return PossibleContents::none(); + } + return iter->second; + } + +private: + std::unordered_map<Location, PossibleContents> locationContents; +}; + +} // namespace wasm + +#endif // wasm_ir_possible_contents_h diff --git a/src/ir/subtypes.h b/src/ir/subtypes.h index 9064d5ed0..74c95032d 100644 --- a/src/ir/subtypes.h +++ b/src/ir/subtypes.h @@ -26,8 +26,9 @@ namespace wasm { // them. struct SubTypes { SubTypes(Module& wasm) { - if (getTypeSystem() != TypeSystem::Nominal) { - Fatal() << "SubTypes requires nominal typing to find supers"; + if (getTypeSystem() != TypeSystem::Nominal && + getTypeSystem() != TypeSystem::Isorecursive) { + Fatal() << "SubTypes requires explicit supers"; } types = ModuleUtils::collectHeapTypes(wasm); for (auto type : types) { diff --git a/test/gtest/CMakeLists.txt b/test/gtest/CMakeLists.txt index 1c30cdb10..548f01ff6 100644 --- a/test/gtest/CMakeLists.txt +++ b/test/gtest/CMakeLists.txt @@ -2,6 +2,7 @@ include_directories(../../third_party/googletest/googletest/include) include_directories(../../src/wasm) set(unittest_SOURCES + possible-contents.cpp type-builder.cpp wat-lexer.cpp ) diff --git a/test/gtest/possible-contents.cpp b/test/gtest/possible-contents.cpp new file mode 100644 index 000000000..2994a6221 --- /dev/null +++ b/test/gtest/possible-contents.cpp @@ -0,0 +1,262 @@ +#include "ir/possible-contents.h" +#include "wasm-s-parser.h" +#include "wasm.h" +#include "gtest/gtest.h" + +using namespace wasm; + +// Asserts a == b, in any order. +template<typename T> void assertEqualSymmetric(const T& a, const T& b) { + EXPECT_EQ(a, b); + EXPECT_EQ(b, a); + EXPECT_PRED2([](const T& a, const T& b) { return !(a != b); }, a, b); + EXPECT_PRED2([](const T& a, const T& b) { return !(b != a); }, a, b); +} + +// Asserts a != b, in any order. +template<typename T> void assertNotEqualSymmetric(const T& a, const T& b) { + EXPECT_NE(a, b); + EXPECT_NE(b, a); + EXPECT_PRED2([](const T& a, const T& b) { return !(a == b); }, a, b); + EXPECT_PRED2([](const T& a, const T& b) { return !(b == a); }, a, b); +} + +// Asserts a combined with b (in any order) is equal to c. +template<typename T> +void assertCombination(const T& a, const T& b, const T& c) { + T temp1 = a; + temp1.combine(b); + assertEqualSymmetric(temp1, c); + + T temp2 = b; + temp2.combine(a); + assertEqualSymmetric(temp2, c); +} + +// Parse a module from text and return it. +static std::unique_ptr<Module> parse(std::string module) { + auto wasm = std::make_unique<Module>(); + wasm->features = FeatureSet::All; + try { + SExpressionParser parser(&module.front()); + Element& root = *parser.root; + SExpressionWasmBuilder builder(*wasm, *root[0], IRProfile::Normal); + } catch (ParseException& p) { + p.dump(std::cerr); + Fatal() << "error in parsing wasm text"; + } + return wasm; +}; + +// We want to declare a bunch of globals that are used in various tests. Doing +// so in the global scope is risky, as their constructors use types, and the +// type system itself uses global constructors. Instead, we use a fixture for +// that. +class PossibleContentsTest : public testing::Test { +protected: + void SetUp() override { + // Use nominal typing to test struct types. + wasm::setTypeSystem(TypeSystem::Nominal); + } + + PossibleContents none = PossibleContents::none(); + + PossibleContents i32Zero = PossibleContents::literal(Literal(int32_t(0))); + PossibleContents i32One = PossibleContents::literal(Literal(int32_t(1))); + PossibleContents f64One = PossibleContents::literal(Literal(double(1))); + PossibleContents anyNull = + PossibleContents::literal(Literal::makeNull(HeapType::any)); + PossibleContents funcNull = + PossibleContents::literal(Literal::makeNull(HeapType::func)); + + PossibleContents i32Global1 = + PossibleContents::global("i32Global1", Type::i32); + PossibleContents i32Global2 = + PossibleContents::global("i32Global2", Type::i32); + PossibleContents f64Global = PossibleContents::global("f64Global", Type::f64); + PossibleContents anyGlobal = + PossibleContents::global("anyGlobal", Type::anyref); + + PossibleContents nonNullFunc = PossibleContents::literal( + Literal("func", Type(Signature(Type::none, Type::none), NonNullable))); + + PossibleContents exactI32 = PossibleContents::exactType(Type::i32); + PossibleContents exactAnyref = PossibleContents::exactType(Type::anyref); + PossibleContents exactFuncref = PossibleContents::exactType(Type::funcref); + PossibleContents exactNonNullAnyref = + PossibleContents::exactType(Type(HeapType::any, NonNullable)); + PossibleContents exactNonNullFuncref = + PossibleContents::exactType(Type(HeapType::func, NonNullable)); + + PossibleContents exactFuncSignatureType = PossibleContents::exactType( + Type(Signature(Type::none, Type::none), Nullable)); + PossibleContents exactNonNullFuncSignatureType = PossibleContents::exactType( + Type(Signature(Type::none, Type::none), NonNullable)); + + PossibleContents many = PossibleContents::many(); +}; + +TEST_F(PossibleContentsTest, TestComparisons) { + assertEqualSymmetric(none, none); + assertNotEqualSymmetric(none, i32Zero); + assertNotEqualSymmetric(none, i32Global1); + assertNotEqualSymmetric(none, exactI32); + assertNotEqualSymmetric(none, many); + + assertEqualSymmetric(i32Zero, i32Zero); + assertNotEqualSymmetric(i32Zero, i32One); + assertNotEqualSymmetric(i32Zero, f64One); + assertNotEqualSymmetric(i32Zero, i32Global1); + assertNotEqualSymmetric(i32Zero, exactI32); + assertNotEqualSymmetric(i32Zero, many); + + assertEqualSymmetric(i32Global1, i32Global1); + assertNotEqualSymmetric(i32Global1, i32Global2); + assertNotEqualSymmetric(i32Global1, exactI32); + assertNotEqualSymmetric(i32Global1, many); + + assertEqualSymmetric(exactI32, exactI32); + assertNotEqualSymmetric(exactI32, exactAnyref); + assertNotEqualSymmetric(exactI32, many); + + assertEqualSymmetric(many, many); + + // Nulls + + assertNotEqualSymmetric(i32Zero, anyNull); + assertEqualSymmetric(anyNull, anyNull); + assertEqualSymmetric(anyNull, funcNull); // All nulls compare equal. + + assertEqualSymmetric(exactNonNullAnyref, exactNonNullAnyref); + assertNotEqualSymmetric(exactNonNullAnyref, exactAnyref); +} + +TEST_F(PossibleContentsTest, TestCombinations) { + // None with anything else becomes the other thing. + assertCombination(none, none, none); + assertCombination(none, i32Zero, i32Zero); + assertCombination(none, i32Global1, i32Global1); + assertCombination(none, exactI32, exactI32); + assertCombination(none, many, many); + + // i32(0) will become Many, unless the value or the type is identical. + assertCombination(i32Zero, i32Zero, i32Zero); + assertCombination(i32Zero, i32One, exactI32); + assertCombination(i32Zero, f64One, many); + assertCombination(i32Zero, i32Global1, exactI32); + assertCombination(i32Zero, f64Global, many); + assertCombination(i32Zero, exactI32, exactI32); + assertCombination(i32Zero, exactAnyref, many); + assertCombination(i32Zero, many, many); + + assertCombination(i32Global1, i32Global1, i32Global1); + assertCombination(i32Global1, i32Global2, exactI32); + assertCombination(i32Global1, f64Global, many); + assertCombination(i32Global1, exactI32, exactI32); + assertCombination(i32Global1, exactAnyref, many); + assertCombination(i32Global1, many, many); + + assertCombination(exactI32, exactI32, exactI32); + assertCombination(exactI32, exactAnyref, many); + assertCombination(exactI32, many, many); + + assertCombination(many, many, many); + + // Exact references: An exact reference only stays exact when combined with + // the same heap type (nullability may be added, but nothing else). + assertCombination(exactFuncref, exactAnyref, many); + assertCombination(exactFuncref, anyGlobal, many); + assertCombination(exactFuncref, nonNullFunc, many); + assertCombination(exactFuncref, exactFuncref, exactFuncref); + assertCombination(exactFuncref, exactNonNullFuncref, exactFuncref); + + // Nulls. + + assertCombination(anyNull, i32Zero, many); + assertCombination(anyNull, anyNull, anyNull); + assertCombination(anyNull, exactAnyref, exactAnyref); + + // Two nulls go to the lub. + assertCombination(anyNull, funcNull, anyNull); + + assertCombination(exactNonNullAnyref, exactNonNullAnyref, exactNonNullAnyref); + + // If one is a null and the other is not, it makes the one that is not a + // null be a nullable type - but keeps the heap type of the other (since the + // type of the null does not matter, all nulls compare equal). + assertCombination(anyNull, exactNonNullAnyref, exactAnyref); + assertCombination(anyNull, exactNonNullFuncref, exactFuncref); + + // Funcrefs + + // A function reference + a null becomes an exact type (of that sig), plus + // nullability. + assertCombination(nonNullFunc, anyNull, exactFuncSignatureType); + assertCombination(nonNullFunc, funcNull, exactFuncSignatureType); + assertCombination(exactFuncSignatureType, funcNull, exactFuncSignatureType); + assertCombination( + exactNonNullFuncSignatureType, funcNull, exactFuncSignatureType); + assertCombination( + nonNullFunc, exactFuncSignatureType, exactFuncSignatureType); + assertCombination( + nonNullFunc, exactNonNullFuncSignatureType, exactNonNullFuncSignatureType); + assertCombination(nonNullFunc, exactI32, many); + + // Globals vs nulls. + + assertCombination(anyGlobal, anyNull, many); + assertCombination(anyGlobal, funcNull, many); +} + +TEST_F(PossibleContentsTest, TestOracleMinimal) { + // A minimal test of the public API of PossibleTypesOracle. See the lit test + // for coverage of all the internals (using lit makes the result more + // fuzzable). + auto wasm = parse(R"( + (module + (global $null (ref null any) (ref.null any)) + (global $something i32 (i32.const 42)) + ) + )"); + ContentOracle oracle(*wasm); + + // This will be a null constant. + EXPECT_TRUE(oracle.getContents(GlobalLocation{"null"}).isNull()); + + // This will be 42. + EXPECT_EQ(oracle.getContents(GlobalLocation{"something"}).getLiteral(), + Literal(int32_t(42))); +} + +TEST_F(PossibleContentsTest, TestOracleManyTypes) { + // Test for a node with many possible types. The pass limits how many it + // notices to not use excessive memory, so even though 4 are possible here, + // we'll just report that more than one is possible ("many"). + auto wasm = parse(R"( + (module + (type $A (struct_subtype (field i32) data)) + (type $B (struct_subtype (field i64) data)) + (type $C (struct_subtype (field f32) data)) + (type $D (struct_subtype (field f64) data)) + (func $foo (result (ref any)) + (select (result (ref any)) + (select (result (ref any)) + (struct.new $A) + (struct.new $B) + (i32.const 0) + ) + (select (result (ref any)) + (struct.new $C) + (struct.new $D) + (i32.const 0) + ) + (i32.const 0) + ) + ) + ) + )"); + ContentOracle oracle(*wasm); + // The function's body should be Many. + EXPECT_TRUE( + oracle.getContents(ResultLocation{wasm->getFunction("foo"), 0}).isMany()); +} |