summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/module-utils.h148
-rw-r--r--src/passes/Print.cpp42
-rw-r--r--src/wasm-binary.h4
-rw-r--r--src/wasm-type.h4
-rw-r--r--src/wasm/wasm-binary.cpp21
-rw-r--r--src/wasm/wasm-type.cpp35
6 files changed, 156 insertions, 98 deletions
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 008ec0714..de37e0875 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -392,29 +392,28 @@ template<typename T> struct CallGraphPropertyAnalysis {
}
};
-// Helper function for collecting the type signatures used in a module
+// Helper function for collecting all the types that are declared in a module,
+// which means the HeapTypes (that are non-basic, that is, not eqref etc., which
+// do not need to be defined).
//
-// Used when emitting or printing a module to give signatures canonical
-// indices. Signatures are sorted in order of decreasing frequency to minize the
+// Used when emitting or printing a module to give HeapTypes canonical
+// indices. HeapTypes are sorted in order of decreasing frequency to minize the
// size of their collective encoding. Both a vector mapping indices to
-// signatures and a map mapping signatures to indices are produced.
-inline void
-collectSignatures(Module& wasm,
- std::vector<Signature>& signatures,
- std::unordered_map<Signature, Index>& sigIndices) {
- struct Counts : public std::unordered_map<Signature, size_t> {
- void note(Signature sig) { (*this)[sig]++; }
+// HeapTypes and a map mapping HeapTypes to indices are produced.
+inline void collectHeapTypes(Module& wasm,
+ std::vector<HeapType>& types,
+ std::unordered_map<HeapType, Index>& typeIndices) {
+ struct Counts : public std::unordered_map<HeapType, size_t> {
+ bool isRelevant(Type type) { return !type.isBasic() && type.isRef(); }
+ void note(HeapType type) { (*this)[type]++; }
void maybeNote(Type type) {
- if (type.isRef()) {
- auto heapType = type.getHeapType();
- if (heapType.isSignature()) {
- note(heapType.getSignature());
- }
+ if (isRelevant(type)) {
+ note(type.getHeapType());
}
}
};
- // Collect the signature use counts for a single function
+ // Collect the type use counts for a single function
auto updateCounts = [&](Function* func, Counts& counts) {
if (func->imported()) {
return;
@@ -429,7 +428,7 @@ collectSignatures(Module& wasm,
if (curr->is<RefNull>()) {
counts.maybeNote(curr->type);
} else if (auto* call = curr->dynCast<CallIndirect>()) {
- counts[call->sig]++;
+ counts.note(call->sig);
} else if (Properties::isControlFlowStructure(curr)) {
counts.maybeNote(curr->type);
if (curr->type.isTuple()) {
@@ -437,6 +436,7 @@ collectSignatures(Module& wasm,
counts.note(Signature(Type::none, curr->type));
}
}
+ // TODO struct.get and others contain a type index
}
};
TypeCounter(counts).walk(func->body);
@@ -447,7 +447,7 @@ collectSignatures(Module& wasm,
// Collect all the counts.
Counts counts;
for (auto& curr : wasm.functions) {
- counts[curr->sig]++;
+ counts.note(curr->sig);
for (auto type : curr->vars) {
counts.maybeNote(type);
if (type.isTuple()) {
@@ -458,7 +458,7 @@ collectSignatures(Module& wasm,
}
}
for (auto& curr : wasm.events) {
- counts[curr->sig]++;
+ counts.note(curr->sig);
}
for (auto& pair : analysis.map) {
Counts& functionCounts = pair.second;
@@ -466,74 +466,83 @@ collectSignatures(Module& wasm,
counts[innerPair.first] += innerPair.second;
}
}
-
+ // A generic utility to traverse the child types of a type.
+ // TODO: work with tlively to refactor this to a shared place
+ auto walkRelevantChildren = [&](HeapType type,
+ std::function<void(HeapType)> callback) {
+ auto callIfRelevant = [&](Type type) {
+ if (counts.isRelevant(type)) {
+ callback(type.getHeapType());
+ }
+ };
+ if (type.isSignature()) {
+ auto sig = type.getSignature();
+ for (Type type : {sig.params, sig.results}) {
+ for (auto element : type) {
+ callIfRelevant(element);
+ }
+ }
+ } else if (type.isArray()) {
+ callIfRelevant(type.getArray().element.type);
+ } else if (type.isStruct()) {
+ auto fields = type.getStruct().fields;
+ for (auto field : fields) {
+ callIfRelevant(field.type);
+ }
+ }
+ };
// Recursively traverse each reference type, which may have a child type that
// is itself a reference type. This reflects an appearance in the binary
// format that is in the type section itself.
- // As we do this we may find more and more signatures, as nested children of
- // previous ones. Each such signature will appear in the type section once, so
+ // As we do this we may find more and more types, as nested children of
+ // previous ones. Each such type will appear in the type section once, so
// we just need to visit it once.
// TODO: handle struct and array fields
- std::unordered_set<Signature> newSigs;
+ std::unordered_set<HeapType> newTypes;
for (auto& pair : counts) {
- newSigs.insert(pair.first);
- }
- while (!newSigs.empty()) {
- auto iter = newSigs.begin();
- auto sig = *iter;
- newSigs.erase(iter);
- for (Type type : {sig.params, sig.results}) {
- for (auto element : type) {
- if (element.isRef()) {
- auto heapType = element.getHeapType();
- if (heapType.isSignature()) {
- auto sig = heapType.getSignature();
- if (!counts.count(sig)) {
- newSigs.insert(sig);
- }
- counts[sig]++;
- }
- }
+ newTypes.insert(pair.first);
+ }
+ while (!newTypes.empty()) {
+ auto iter = newTypes.begin();
+ auto type = *iter;
+ newTypes.erase(iter);
+ walkRelevantChildren(type, [&](HeapType type) {
+ if (!counts.count(type)) {
+ newTypes.insert(type);
}
- }
+ counts.note(type);
+ });
}
- // We must sort all the dependencies of a signature before it. For example,
+ // We must sort all the dependencies of a type before it. For example,
// (func (param (ref (func)))) must appear after (func). To do that, find the
- // depth of dependencies of each signature. For example, if A depends on B
+ // depth of dependencies of each type. For example, if A depends on B
// which depends on C, then A's depth is 2, B's is 1, and C's is 0 (assuming
// no other dependencies).
Counts depthOfDependencies;
- std::unordered_map<Signature, std::unordered_set<Signature>> isDependencyOf;
+ std::unordered_map<HeapType, std::unordered_set<HeapType>> isDependencyOf;
// To calculate the depth of dependencies, we'll do a flow analysis, visiting
- // each signature as we find out new things about it.
- std::set<Signature> toVisit;
+ // each type as we find out new things about it.
+ std::set<HeapType> toVisit;
for (auto& pair : counts) {
- auto sig = pair.first;
- depthOfDependencies[sig] = 0;
- toVisit.insert(sig);
- for (Type type : {sig.params, sig.results}) {
- for (auto element : type) {
- if (element.isRef()) {
- auto heapType = element.getHeapType();
- if (heapType.isSignature()) {
- isDependencyOf[heapType.getSignature()].insert(sig);
- }
- }
- }
- }
+ auto type = pair.first;
+ depthOfDependencies[type] = 0;
+ toVisit.insert(type);
+ walkRelevantChildren(type, [&](HeapType childType) {
+ isDependencyOf[childType].insert(type); // XXX flip?
+ });
}
while (!toVisit.empty()) {
auto iter = toVisit.begin();
- auto sig = *iter;
+ auto type = *iter;
toVisit.erase(iter);
// Anything that depends on this has a depth of dependencies equal to this
- // signature's, plus this signature itself.
- auto newDepth = depthOfDependencies[sig] + 1;
+ // type's, plus this type itself.
+ auto newDepth = depthOfDependencies[type] + 1;
if (newDepth > counts.size()) {
- Fatal() << "Cyclic signatures detected, cannot sort them.";
+ Fatal() << "Cyclic types detected, cannot sort them.";
}
- for (auto& other : isDependencyOf[sig]) {
+ for (auto& other : isDependencyOf[type]) {
if (depthOfDependencies[other] < newDepth) {
// We found something new to propagate.
depthOfDependencies[other] = newDepth;
@@ -541,10 +550,9 @@ collectSignatures(Module& wasm,
}
}
}
- // Sort by frequency and then simplicity, and also keeping every signature
+ // Sort by frequency and then simplicity, and also keeping every type
// before things that depend on it.
- std::vector<std::pair<Signature, size_t>> sorted(counts.begin(),
- counts.end());
+ std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), counts.end());
std::sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
if (depthOfDependencies[a.first] != depthOfDependencies[b.first]) {
return depthOfDependencies[a.first] < depthOfDependencies[b.first];
@@ -555,8 +563,8 @@ collectSignatures(Module& wasm,
return a.first < b.first;
});
for (Index i = 0; i < sorted.size(); ++i) {
- sigIndices[sorted[i].first] = i;
- signatures.push_back(sorted[i].first);
+ typeIndices[sorted[i].first] = i;
+ types.push_back(sorted[i].first);
}
}
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index c597028be..ba3981e21 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -141,6 +141,11 @@ struct TypeName {
TypeName(Type type) : type(type) {}
};
+struct HeapTypeName {
+ HeapType type;
+ HeapTypeName(HeapType type) : type(type) {}
+};
+
std::ostream& operator<<(std::ostream& os, TypeName typeName) {
auto type = typeName.type;
if (type.isRef() && !type.isBasic()) {
@@ -160,6 +165,16 @@ std::ostream& operator<<(std::ostream& os, TypeName typeName) {
return os << SExprType(typeName.type);
}
+std::ostream& operator<<(std::ostream& os, HeapTypeName typeName) {
+ auto type = typeName.type;
+ if (type.isSignature()) {
+ os << SigName(type.getSignature());
+ } else {
+ os << type;
+ }
+ return os;
+}
+
} // anonymous namespace
// Printing "unreachable" as a instruction prefix type is not valid in wasm text
@@ -2348,10 +2363,10 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
WASM_UNREACHABLE("TODO (gc): array.len");
}
// Module-level visitors
- void handleSignature(Signature curr, Name* funcName = nullptr) {
+ void handleSignature(Signature curr, Name name = Name()) {
o << "(func";
- if (funcName) {
- o << " $" << *funcName;
+ if (name.is()) {
+ o << " $" << name;
}
if (curr.params.size() > 0) {
o << maybeSpace;
@@ -2375,6 +2390,13 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
}
o << ")";
}
+ void handleHeapType(HeapType type) {
+ if (type.isSignature()) {
+ handleSignature(type.getSignature());
+ } else {
+ WASM_UNREACHABLE("unsupported heap type");
+ }
+ }
void visitExport(Export* curr) {
o << '(';
printMedium(o, "export ");
@@ -2453,7 +2475,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
lastPrintedLocation = {0, 0, 0};
o << '(';
emitImportHeader(curr);
- handleSignature(curr->sig, &curr->name);
+ handleSignature(curr->sig, curr->name);
o << ')';
o << maybeNewLine;
}
@@ -2702,15 +2724,15 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
printName(curr->name, o);
}
incIndent();
- std::vector<Signature> signatures;
- std::unordered_map<Signature, Index> indices;
- ModuleUtils::collectSignatures(*curr, signatures, indices);
- for (auto sig : signatures) {
+ std::vector<HeapType> types;
+ std::unordered_map<HeapType, Index> indices;
+ ModuleUtils::collectHeapTypes(*curr, types, indices);
+ for (auto type : types) {
doIndent(o, indent);
o << '(';
printMedium(o, "type") << ' ';
- o << SigName(sig) << ' ';
- handleSignature(sig);
+ o << HeapTypeName(type) << ' ';
+ handleHeapType(type);
o << ")" << maybeNewLine;
}
ModuleUtils::iterImportedMemories(
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 532cfb7ec..d7257f560 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1175,8 +1175,8 @@ private:
Module* wasm;
BufferWithRandomAccess& o;
BinaryIndexes indexes;
- std::unordered_map<Signature, Index> typeIndices;
- std::vector<Signature> types;
+ std::unordered_map<HeapType, Index> typeIndices;
+ std::vector<HeapType> types;
bool debugInfo = true;
std::ostream* sourceMap = nullptr;
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 77f7120bf..39ec1640e 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -304,6 +304,7 @@ struct Field {
mutable_ == other.mutable_;
}
bool operator!=(const Field& other) const { return !(*this == other); }
+ bool operator<(const Field& other) const;
std::string toString() const;
};
@@ -316,6 +317,7 @@ struct Struct {
Struct(FieldList&& fields) : fields(std::move(fields)) {}
bool operator==(const Struct& other) const { return fields == other.fields; }
bool operator!=(const Struct& other) const { return !(*this == other); }
+ bool operator<(const Struct& other) const { return fields < other.fields; }
std::string toString() const;
};
@@ -326,6 +328,7 @@ struct Array {
Array(Field&& element) : element(std::move(element)) {}
bool operator==(const Array& other) const { return element == other.element; }
bool operator!=(const Array& other) const { return !(*this == other); }
+ bool operator<(const Array& other) const { return element < other.element; }
std::string toString() const;
};
@@ -378,6 +381,7 @@ struct HeapType {
bool operator==(const HeapType& other) const;
bool operator!=(const HeapType& other) const { return !(*this == other); }
+ bool operator<(const HeapType& other) const;
HeapType& operator=(const HeapType& other);
std::string toString() const;
};
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 7a6d4d35d..54e417b8c 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -31,7 +31,7 @@ namespace wasm {
void WasmBinaryWriter::prepare() {
// Collect function types and their frequencies. Collect information in each
// function in parallel, then merge.
- ModuleUtils::collectSignatures(*wasm, types, typeIndices);
+ ModuleUtils::collectHeapTypes(*wasm, types, typeIndices);
importInfo = wasm::make_unique<ImportInfo>(*wasm);
}
@@ -215,14 +215,19 @@ void WasmBinaryWriter::writeTypes() {
auto start = startSection(BinaryConsts::Section::Type);
o << U32LEB(types.size());
for (Index i = 0; i < types.size(); ++i) {
- Signature& sig = types[i];
- BYN_TRACE("write " << sig.params << " -> " << sig.results << std::endl);
- o << S32LEB(BinaryConsts::EncodedType::Func);
- for (auto& sigType : {sig.params, sig.results}) {
- o << U32LEB(sigType.size());
- for (const auto& type : sigType) {
- writeType(type);
+ auto type = types[i];
+ BYN_TRACE("write " << type << std::endl);
+ if (type.isSignature()) {
+ o << S32LEB(BinaryConsts::EncodedType::Func);
+ auto sig = type.getSignature();
+ for (auto& sigType : {sig.params, sig.results}) {
+ o << U32LEB(sigType.size());
+ for (const auto& type : sigType) {
+ writeType(type);
+ }
}
+ } else {
+ WASM_UNREACHABLE("TODO GC type writing");
}
}
finishSection(start);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index be017140d..fd49c5b93 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -405,14 +405,7 @@ bool Type::operator<(const Type& other) const {
if (a.isNullable() != b.isNullable()) {
return a.isNullable();
}
- auto aHeap = a.getHeapType();
- auto bHeap = b.getHeapType();
- if (aHeap.isSignature() && bHeap.isSignature()) {
- return aHeap.getSignature() < bHeap.getSignature();
- }
- TODO_SINGLE_COMPOUND(a);
- TODO_SINGLE_COMPOUND(b);
- WASM_UNREACHABLE("unimplemented type comparison");
+ return a.getHeapType() < b.getHeapType();
};
return std::lexicographical_compare(
begin(), end(), other.begin(), other.end(), comp);
@@ -738,6 +731,22 @@ bool HeapType::operator==(const HeapType& other) const {
WASM_UNREACHABLE("unexpected kind");
}
+bool HeapType::operator<(const HeapType& other) const {
+ if (kind != other.kind) {
+ return kind < other.kind;
+ }
+ if (isSignature()) {
+ return getSignature() < other.getSignature();
+ }
+ if (isStruct()) {
+ return getStruct() < other.getStruct();
+ }
+ if (isArray()) {
+ return getArray() < other.getArray();
+ }
+ WASM_UNREACHABLE("unimplemented type comparison");
+}
+
HeapType& HeapType::operator=(const HeapType& other) {
if (&other != this) {
this->~HeapType();
@@ -746,6 +755,16 @@ HeapType& HeapType::operator=(const HeapType& other) {
return *this;
}
+bool Field::operator<(const Field& other) const {
+ if (mutable_ != other.mutable_) {
+ return mutable_ < other.mutable_;
+ }
+ if (type == Type::i32) {
+ return packedType < other.packedType;
+ }
+ return type < other.type;
+}
+
namespace {
std::ostream&
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-04 10:21:24 +0000