diff options
author | Alon Zakai <azakai@google.com> | 2021-08-09 13:25:09 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-08-09 13:25:09 -0700 |
commit | 329b3606b7f966f1ac3cbb1f9a46849ea4d5c785 (patch) | |
tree | 278cf2a6b2d82f18700d6c40f82acf549c1e59fb /src | |
parent | 832481af8af5ddefc3a3479701418f94a1a4921a (diff) | |
download | binaryen-329b3606b7f966f1ac3cbb1f9a46849ea4d5c785.tar.gz binaryen-329b3606b7f966f1ac3cbb1f9a46849ea4d5c785.tar.bz2 binaryen-329b3606b7f966f1ac3cbb1f9a46849ea4d5c785.zip |
[Wasm GC] Track struct.new and struct.set separately in ConstantFieldPropagation (#4064)
Previously we tracked them in the same way. That means that we did the same
when seeing if either a struct.new or a struct.set can write to the memory that
is read by a struct.get, where the rule is that if either type is a subtype of the
other then they might. But with struct.new we know the precise type, which
means we can do better.
Specifically, if we see a new of type B, then only a get of a supertype of B can
possibly read that data: it is not possible for our struct of type B to appear in
a location that requires a subtype of B. Conceptually:
A = type struct
B = type extends A
C = type extends B
x = struct.new<B>
struct.get<A>(y) // x might appear here, as it can be assigned to a
// variable y of a supertype
struct.get<C>(y) // x cannot appear here
This allows more devirtualization. It is a followup for #4052 that implements
a TODO from there.
The diff without whitespace is simpler.
Diffstat (limited to 'src')
-rw-r--r-- | src/passes/ConstantFieldPropagation.cpp | 139 |
1 files changed, 88 insertions, 51 deletions
diff --git a/src/passes/ConstantFieldPropagation.cpp b/src/passes/ConstantFieldPropagation.cpp index 621ceec2a..f73a9b380 100644 --- a/src/passes/ConstantFieldPropagation.cpp +++ b/src/passes/ConstantFieldPropagation.cpp @@ -169,6 +169,11 @@ struct StructValues : public std::vector<PossibleConstantValues> { assert(index < size()); return std::vector<PossibleConstantValues>::operator[](index); } + + const PossibleConstantValues& operator[](size_t index) const { + assert(index < size()); + return std::vector<PossibleConstantValues>::operator[](index); + } }; // Map of types to information about the values their fields can take. @@ -206,13 +211,21 @@ struct StructValuesMap : public std::unordered_map<HeapType, StructValues> { using FunctionStructValuesMap = std::unordered_map<Function*, StructValuesMap>; // Scan each function to note all its writes to struct fields. +// +// We track information from struct.new and struct.set separately, because in +// struct.new we know more about the type - we know the actual exact type being +// written to, and not just that it is of a subtype of the instruction's type, +// which helps later. struct Scanner : public WalkerPass<PostWalker<Scanner>> { bool isFunctionParallel() override { return true; } - Pass* create() override { return new Scanner(functionInfos); } + Pass* create() override { + return new Scanner(functionNewInfos, functionSetInfos); + } - Scanner(FunctionStructValuesMap& functionInfos) - : functionInfos(functionInfos) {} + Scanner(FunctionStructValuesMap& functionNewInfos, + FunctionStructValuesMap& functionSetInfos) + : functionNewInfos(functionNewInfos), functionSetInfos(functionSetInfos) {} void visitStructNew(StructNew* curr) { auto type = curr->type; @@ -222,7 +235,7 @@ struct Scanner : public WalkerPass<PostWalker<Scanner>> { // Note writes to all the fields of the struct. auto heapType = type.getHeapType(); - auto& values = getStructValues(heapType); + auto& values = functionNewInfos[getFunction()][heapType]; auto& fields = heapType.getStruct().fields; for (Index i = 0; i < fields.size(); i++) { auto& fieldValues = values[i]; @@ -242,15 +255,13 @@ struct Scanner : public WalkerPass<PostWalker<Scanner>> { // Note a write to this field of the struct. auto heapType = type.getHeapType(); - noteExpression(curr->value, getStructValues(heapType)[curr->index]); + auto& values = functionSetInfos[getFunction()][heapType]; + noteExpression(curr->value, values[curr->index]); } private: - FunctionStructValuesMap& functionInfos; - - StructValues& getStructValues(HeapType type) { - return functionInfos[getFunction()][type]; - } + FunctionStructValuesMap& functionNewInfos; + FunctionStructValuesMap& functionSetInfos; // Note a value, checking whether it is a constant or not. void noteExpression(Expression* expr, PossibleConstantValues& info) { @@ -348,28 +359,34 @@ struct ConstantFieldPropagation : public Pass { } // Find and analyze all writes inside each function. - FunctionStructValuesMap functionInfos; + FunctionStructValuesMap functionNewInfos, functionSetInfos; for (auto& func : module->functions) { // Initialize the data for each function, so that we can operate on this // structure in parallel without modifying it. - functionInfos[func.get()]; + functionNewInfos[func.get()]; + functionSetInfos[func.get()]; } - Scanner scanner(functionInfos); + Scanner scanner(functionNewInfos, functionSetInfos); scanner.run(runner, module); scanner.walkModuleCode(module); // Combine the data from the functions. - StructValuesMap combinedInfos; - for (auto& kv : functionInfos) { - StructValuesMap& infos = kv.second; - for (auto& kv : infos) { - auto type = kv.first; - auto& info = kv.second; - for (Index i = 0; i < info.size(); i++) { - combinedInfos[type][i].combine(info[i]); + auto combine = [](const FunctionStructValuesMap& functionInfos, + StructValuesMap& combinedInfos) { + for (auto& kv : functionInfos) { + const StructValuesMap& infos = kv.second; + for (auto& kv : infos) { + auto type = kv.first; + auto& info = kv.second; + for (Index i = 0; i < info.size(); i++) { + combinedInfos[type][i].combine(info[i]); + } } } - } + }; + StructValuesMap combinedNewInfos, combinedSetInfos; + combine(functionNewInfos, combinedNewInfos); + combine(functionSetInfos, combinedSetInfos); // Handle subtyping. |combinedInfo| so far contains data that represents // each struct.new and struct.set's operation on the struct type used in @@ -398,44 +415,64 @@ struct ConstantFieldPropagation : public Pass { // efficient, we therefore propagate information about the possible values // in each field to both subtypes and supertypes. // - // TODO: Model struct.new separately from struct.set. With new we actually - // do know the specific type being written to, which means a get is - // only relevant for a new if the get is of a subtype. That means we - // only need to propagate values from new to subtypes. + // struct.new on the other hand knows exactly what type is being written to, + // and so given a get of $A and a new of $B, the new is relevant for the get + // iff $A is a subtype of $B, so we only need to propagate in one direction + // there, to supertypes. // // TODO: A topological sort could avoid repeated work here perhaps. + SubTypes subTypes(*module); - UniqueDeferredQueue<HeapType> work; - for (auto& kv : combinedInfos) { - auto type = kv.first; - work.push(type); - } - while (!work.empty()) { - auto type = work.pop(); - auto& infos = combinedInfos[type]; - - // Propagate shared fields to the supertype. - HeapType superType; - if (type.getSuperType(superType)) { - auto& superInfos = combinedInfos[superType]; - auto& superFields = superType.getStruct().fields; - for (Index i = 0; i < superFields.size(); i++) { - if (superInfos[i].combine(infos[i])) { - work.push(superType); + + auto propagate = [&subTypes](StructValuesMap& combinedInfos, + bool toSubTypes) { + UniqueDeferredQueue<HeapType> work; + for (auto& kv : combinedInfos) { + auto type = kv.first; + work.push(type); + } + while (!work.empty()) { + auto type = work.pop(); + auto& infos = combinedInfos[type]; + + // Propagate shared fields to the supertype. + HeapType superType; + if (type.getSuperType(superType)) { + auto& superInfos = combinedInfos[superType]; + auto& superFields = superType.getStruct().fields; + for (Index i = 0; i < superFields.size(); i++) { + if (superInfos[i].combine(infos[i])) { + work.push(superType); + } } } - } - // Propagate shared fields to the subtypes. - auto numFields = type.getStruct().fields.size(); - for (auto subType : subTypes.getSubTypes(type)) { - auto& subInfos = combinedInfos[subType]; - for (Index i = 0; i < numFields; i++) { - if (subInfos[i].combine(infos[i])) { - work.push(subType); + if (toSubTypes) { + // Propagate shared fields to the subtypes. + auto numFields = type.getStruct().fields.size(); + for (auto subType : subTypes.getSubTypes(type)) { + auto& subInfos = combinedInfos[subType]; + for (Index i = 0; i < numFields; i++) { + if (subInfos[i].combine(infos[i])) { + work.push(subType); + } + } } } } + }; + propagate(combinedNewInfos, false); + propagate(combinedSetInfos, true); + + // Combine both sources of information to the final information that gets + // care about. + StructValuesMap combinedInfos = std::move(combinedNewInfos); + for (auto& kv : combinedSetInfos) { + auto type = kv.first; + auto& info = kv.second; + for (Index i = 0; i < info.size(); i++) { + combinedInfos[type][i].combine(info[i]); + } } // Optimize. |