summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/module-utils.h26
-rw-r--r--src/literal.h34
-rw-r--r--src/passes/Asyncify.cpp6
-rw-r--r--src/passes/ConstHoisting.cpp13
-rw-r--r--src/passes/GenerateDynCalls.cpp3
-rw-r--r--src/passes/RemoveNonJSOps.cpp3
-rw-r--r--src/support/insert_ordered.h56
-rw-r--r--src/tools/fuzzing.h7
-rw-r--r--src/wasm-stack.h3
-rw-r--r--src/wasm-type.h7
-rw-r--r--src/wasm/wasm-type.cpp154
-rw-r--r--src/wasm/wasm-validator.cpp2
12 files changed, 76 insertions, 238 deletions
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index ef6bc2bf6..486838aea 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -22,6 +22,7 @@
#include "ir/manipulation.h"
#include "ir/properties.h"
#include "pass.h"
+#include "support/insert_ordered.h"
#include "support/unique_deferring_queue.h"
#include "wasm.h"
@@ -306,10 +307,12 @@ template<typename T> inline void iterImports(Module& wasm, T visitor) {
// some computation that the operation performs.
// The operation performend should not modify the wasm module in any way.
// TODO: enforce this
-template<typename T> struct ParallelFunctionAnalysis {
+template<typename K, typename V> using DefaultMap = std::map<K, V>;
+template<typename T, template<typename, typename> class MapT = DefaultMap>
+struct ParallelFunctionAnalysis {
Module& wasm;
- typedef std::map<Function*, T> Map;
+ typedef MapT<Function*, T> Map;
Map map;
typedef std::function<void(Function*, T&)> Func;
@@ -467,7 +470,7 @@ template<typename T> struct CallGraphPropertyAnalysis {
inline void collectHeapTypes(Module& wasm,
std::vector<HeapType>& types,
std::unordered_map<HeapType, Index>& typeIndices) {
- struct Counts : public std::unordered_map<HeapType, size_t> {
+ struct Counts : public InsertOrderedMap<HeapType, size_t> {
void note(HeapType type) {
if (!type.isBasic()) {
(*this)[type]++;
@@ -522,7 +525,7 @@ inline void collectHeapTypes(Module& wasm,
}
// Collect info from functions in parallel.
- ModuleUtils::ParallelFunctionAnalysis<Counts> analysis(
+ ModuleUtils::ParallelFunctionAnalysis<Counts, InsertOrderedMap> analysis(
wasm, [&](Function* func, Counts& counts) {
counts.note(func->sig);
for (auto type : func->vars) {
@@ -534,9 +537,9 @@ inline void collectHeapTypes(Module& wasm,
});
// Combine the function info with the module info.
- for (auto& pair : analysis.map) {
- Counts& functionCounts = pair.second;
- for (auto& innerPair : functionCounts) {
+ for (const auto& pair : analysis.map) {
+ const Counts& functionCounts = pair.second;
+ for (const auto& innerPair : functionCounts) {
counts[innerPair.first] += innerPair.second;
}
}
@@ -547,7 +550,7 @@ inline void collectHeapTypes(Module& wasm,
// 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.
- std::unordered_set<HeapType> newTypes;
+ InsertOrderedSet<HeapType> newTypes;
for (auto& pair : counts) {
newTypes.insert(pair.first);
}
@@ -565,13 +568,10 @@ inline void collectHeapTypes(Module& wasm,
}
}
- // Sort by frequency and then simplicity.
+ // Sort by frequency and then original insertion order.
std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), counts.end());
std::stable_sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
- if (a.second != b.second) {
- return a.second > b.second;
- }
- return a.first < b.first;
+ return a.second > b.second;
});
for (Index i = 0; i < sorted.size(); ++i) {
typeIndices[sorted[i].first] = i;
diff --git a/src/literal.h b/src/literal.h
index a07e2597c..14281d66f 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -759,39 +759,7 @@ template<> struct hash<wasm::Literals> {
return digest;
}
};
-template<> struct less<wasm::Literal> {
- bool operator()(const wasm::Literal& a, const wasm::Literal& b) const {
- if (a.type < b.type) {
- return true;
- }
- if (b.type < a.type) {
- return false;
- }
- TODO_SINGLE_COMPOUND(a.type);
- switch (a.type.getBasic()) {
- case wasm::Type::i32:
- return a.geti32() < b.geti32();
- case wasm::Type::f32:
- return a.reinterpreti32() < b.reinterpreti32();
- case wasm::Type::i64:
- return a.geti64() < b.geti64();
- case wasm::Type::f64:
- return a.reinterpreti64() < b.reinterpreti64();
- case wasm::Type::v128:
- return memcmp(a.getv128Ptr(), b.getv128Ptr(), 16) < 0;
- case wasm::Type::funcref:
- case wasm::Type::externref:
- case wasm::Type::anyref:
- case wasm::Type::eqref:
- case wasm::Type::i31ref:
- case wasm::Type::dataref:
- case wasm::Type::none:
- case wasm::Type::unreachable:
- return false;
- }
- WASM_UNREACHABLE("unexpected type");
- }
-};
+
} // namespace std
#endif // wasm_literal_h
diff --git a/src/passes/Asyncify.cpp b/src/passes/Asyncify.cpp
index 1abfa9628..7ad3fab5d 100644
--- a/src/passes/Asyncify.cpp
+++ b/src/passes/Asyncify.cpp
@@ -380,8 +380,8 @@ public:
}
private:
- std::map<Type, Name> map;
- std::map<Name, Type> rev;
+ std::unordered_map<Type, Name> map;
+ std::unordered_map<Name, Type> rev;
// Collect the types returned from all calls for which call support globals
// may need to be generated.
@@ -1237,7 +1237,7 @@ private:
std::unique_ptr<AsyncifyBuilder> builder;
Index rewindIndex;
- std::map<Type, Index> fakeCallLocals;
+ std::unordered_map<Type, Index> fakeCallLocals;
std::set<Index> relevantLiveLocals;
void findRelevantLiveLocals(Function* func) {
diff --git a/src/passes/ConstHoisting.cpp b/src/passes/ConstHoisting.cpp
index 8349e7234..1caf0eb28 100644
--- a/src/passes/ConstHoisting.cpp
+++ b/src/passes/ConstHoisting.cpp
@@ -30,12 +30,11 @@
// <= 1 byte to declare the local and 2-3 to use it!
//
-#include <map>
-
-#include <pass.h>
-#include <wasm-binary.h>
-#include <wasm-builder.h>
-#include <wasm.h>
+#include "pass.h"
+#include "support/insert_ordered.h"
+#include "wasm-binary.h"
+#include "wasm-builder.h"
+#include "wasm.h"
namespace wasm {
@@ -47,7 +46,7 @@ struct ConstHoisting : public WalkerPass<PostWalker<ConstHoisting>> {
Pass* create() override { return new ConstHoisting; }
- std::map<Literal, std::vector<Expression**>> uses;
+ InsertOrderedMap<Literal, std::vector<Expression**>> uses;
void visitConst(Const* curr) {
uses[curr->value].push_back(getCurrentPointer());
diff --git a/src/passes/GenerateDynCalls.cpp b/src/passes/GenerateDynCalls.cpp
index 8ed9ce8b4..0f4934c06 100644
--- a/src/passes/GenerateDynCalls.cpp
+++ b/src/passes/GenerateDynCalls.cpp
@@ -28,6 +28,7 @@
#include "ir/import-utils.h"
#include "pass.h"
#include "support/debug.h"
+#include "support/insert_ordered.h"
#include "wasm-builder.h"
#define DEBUG_TYPE "generate-dyncalls"
@@ -81,7 +82,7 @@ struct GenerateDynCalls : public WalkerPass<PostWalker<GenerateDynCalls>> {
bool onlyI64;
// The set of all invokes' signatures
- std::set<Signature> invokeSigs;
+ InsertOrderedSet<Signature> invokeSigs;
};
static bool hasI64(Signature sig) {
diff --git a/src/passes/RemoveNonJSOps.cpp b/src/passes/RemoveNonJSOps.cpp
index 08e6e6482..7c0a0e2ce 100644
--- a/src/passes/RemoveNonJSOps.cpp
+++ b/src/passes/RemoveNonJSOps.cpp
@@ -43,6 +43,7 @@
#include "ir/memory-utils.h"
#include "ir/module-utils.h"
#include "passes/intrinsics-module.h"
+#include "support/insert_ordered.h"
#include "wasm-builder.h"
#include "wasm-s-parser.h"
@@ -51,7 +52,7 @@ namespace wasm {
struct RemoveNonJSOpsPass : public WalkerPass<PostWalker<RemoveNonJSOpsPass>> {
std::unique_ptr<Builder> builder;
std::unordered_set<Name> neededIntrinsics;
- std::set<std::pair<Name, Type>> neededImportedGlobals;
+ InsertOrderedSet<std::pair<Name, Type>> neededImportedGlobals;
bool isFunctionParallel() override { return false; }
diff --git a/src/support/insert_ordered.h b/src/support/insert_ordered.h
index 5e3dec96b..d4905b945 100644
--- a/src/support/insert_ordered.h
+++ b/src/support/insert_ordered.h
@@ -83,24 +83,43 @@ template<typename T> struct InsertOrderedSet {
// order that elements were added to the map (not in the order
// of operator<(Key, Key))
template<typename Key, typename T> struct InsertOrderedMap {
- std::unordered_map<Key, typename std::list<std::pair<Key, T>>::iterator> Map;
- std::list<std::pair<Key, T>> List;
+ std::unordered_map<Key, typename std::list<std::pair<const Key, T>>::iterator>
+ Map;
+ std::list<std::pair<const Key, T>> List;
+
+ typedef typename std::list<std::pair<const Key, T>>::iterator iterator;
+ iterator begin() { return List.begin(); }
+ iterator end() { return List.end(); }
+
+ typedef
+ typename std::list<std::pair<const Key, T>>::const_iterator const_iterator;
+ const_iterator begin() const { return List.begin(); }
+ const_iterator end() const { return List.end(); }
+
+ std::pair<iterator, bool> insert(std::pair<const Key, T>& kv) {
+ // Try inserting with a placeholder list iterator.
+ auto inserted = Map.insert({kv.first, List.end()});
+ if (inserted.second) {
+ // This is a new item; insert it in the list and update the iterator.
+ List.push_back(kv);
+ inserted.first->second = std::prev(List.end());
+ }
+ return {inserted.first->second, inserted.second};
+ }
T& operator[](const Key& k) {
+ std::pair<const Key, T> kv = {k, {}};
+ return insert(kv).first->second;
+ }
+
+ iterator find(const Key& k) {
auto it = Map.find(k);
if (it == Map.end()) {
- List.push_back(std::make_pair(k, T()));
- auto e = --List.end();
- Map.insert(std::make_pair(k, e));
- return e->second;
+ return end();
}
- return it->second->second;
+ return it->second;
}
- typedef typename std::list<std::pair<Key, T>>::iterator iterator;
- iterator begin() { return List.begin(); }
- iterator end() { return List.end(); }
-
void erase(const Key& k) {
auto it = Map.find(k);
if (it != Map.end()) {
@@ -126,14 +145,19 @@ template<typename Key, typename T> struct InsertOrderedMap {
size_t count(const Key& k) const { return Map.count(k); }
InsertOrderedMap() = default;
- InsertOrderedMap(InsertOrderedMap& other) {
- // TODO, watch out for iterators.
- WASM_UNREACHABLE("unimp");
+ InsertOrderedMap(const InsertOrderedMap& other) {
+ for (auto kv : other) {
+ insert(kv);
+ }
}
InsertOrderedMap& operator=(const InsertOrderedMap& other) {
- // TODO, watch out for iterators.
- WASM_UNREACHABLE("unimp");
+ if (this != &other) {
+ this->~InsertOrderedMap();
+ new (this) InsertOrderedMap<Key, T>(other);
+ }
+ return *this;
}
+
bool operator==(const InsertOrderedMap& other) {
return Map == other.Map && List == other.List;
}
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index 8dd083391..0635dc61d 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -29,6 +29,7 @@ high chance for set at start of loop
#include "ir/branch-utils.h"
#include "ir/memory-utils.h"
+#include "support/insert_ordered.h"
#include <ir/find_all.h>
#include <ir/literal-utils.h>
#include <ir/manipulation.h>
@@ -459,7 +460,7 @@ private:
}
}
- std::map<Type, std::vector<Name>> globalsByType;
+ std::unordered_map<Type, std::vector<Name>> globalsByType;
void setupGlobals() {
// If there were initial wasm contents, there may be imported globals. That
@@ -650,7 +651,7 @@ private:
std::vector<Expression*> hangStack;
// type => list of locals with that type
- std::map<Type, std::vector<Index>> typeLocals;
+ std::unordered_map<Type, std::vector<Index>> typeLocals;
FunctionCreationContext(TranslateToFuzzReader& parent, Function* func)
: parent(parent), func(func) {
@@ -782,7 +783,7 @@ private:
struct Scanner
: public PostWalker<Scanner, UnifiedExpressionVisitor<Scanner>> {
// A map of all expressions, categorized by type.
- std::map<Type, std::vector<Expression*>> exprsByType;
+ InsertOrderedMap<Type, std::vector<Expression*>> exprsByType;
void visitExpression(Expression* curr) {
exprsByType[curr->type].push_back(curr);
diff --git a/src/wasm-stack.h b/src/wasm-stack.h
index 38b64dff4..f114bf43e 100644
--- a/src/wasm-stack.h
+++ b/src/wasm-stack.h
@@ -20,6 +20,7 @@
#include "ir/branch-utils.h"
#include "ir/properties.h"
#include "pass.h"
+#include "support/insert_ordered.h"
#include "wasm-binary.h"
#include "wasm-traversal.h"
#include "wasm.h"
@@ -141,7 +142,7 @@ private:
// Keeps track of the binary index of the scratch locals used to lower
// tuple.extract.
- std::map<Type, Index> scratchLocals;
+ InsertOrderedMap<Type, Index> scratchLocals;
void countScratchLocals();
void setScratchLocals();
};
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 41a89d4fe..03e8c129f 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -173,9 +173,6 @@ public:
bool operator!=(const Type& other) const { return id != other.id; }
bool operator!=(const BasicType& other) const { return id != other; }
- // Order types by some notion of simplicity.
- bool operator<(const Type& other) const;
-
// Returns the type size in bytes. Only single types are supported.
unsigned getByteSize() const;
@@ -362,9 +359,6 @@ public:
bool operator!=(const HeapType& other) const { return id != other.id; }
bool operator!=(const BasicHeapType& other) const { return id != other; }
- // Order heap types by some notion of simplicity.
- bool operator<(const HeapType& other) const;
-
// Returns true if left is a subtype of right. Subtype includes itself.
static bool isSubType(HeapType left, HeapType right);
@@ -414,7 +408,6 @@ struct Signature {
return params == other.params && results == other.results;
}
bool operator!=(const Signature& other) const { return !(*this == other); }
- bool operator<(const Signature& other) const;
std::string toString() const;
};
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 9006eb9f8..d222d3a1a 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -128,24 +128,6 @@ struct HeapTypeInfo {
bool operator!=(const HeapTypeInfo& other) const { return !(*this == other); }
};
-// Helper for coinductively comparing Types and HeapTypes according to some
-// arbitrary notion of complexity.
-struct TypeComparator {
- // Set of HeapTypes we are assuming are equivalent as long as we cannot prove
- // otherwise.
- std::unordered_set<std::pair<HeapType, HeapType>> seen;
- bool lessThan(Type a, Type b);
- bool lessThan(HeapType a, HeapType b);
- bool lessThan(const TypeInfo& a, const TypeInfo& b);
- bool lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b);
- bool lessThan(const Tuple& a, const Tuple& b);
- bool lessThan(const Field& a, const Field& b);
- bool lessThan(const Signature& a, const Signature& b);
- bool lessThan(const Struct& a, const Struct& b);
- bool lessThan(const Array& a, const Array& b);
- bool lessThan(const Rtt& a, const Rtt& b);
-};
-
// Helper for coinductively checking whether a pair of Types or HeapTypes are in
// a subtype relation.
struct SubTyper {
@@ -833,10 +815,6 @@ Nullability Type::getNullability() const {
return isNullable() ? Nullable : NonNullable;
}
-bool Type::operator<(const Type& other) const {
- return TypeComparator().lessThan(*this, other);
-}
-
unsigned Type::getByteSize() const {
// TODO: alignment?
auto getSingleByteSize = [](Type t) {
@@ -1116,10 +1094,6 @@ bool HeapType::isArray() const {
}
}
-bool HeapType::operator<(const HeapType& other) const {
- return TypeComparator().lessThan(*this, other);
-}
-
Signature HeapType::getSignature() const {
assert(isSignature());
return getHeapTypeInfo(*this)->signature;
@@ -1145,10 +1119,6 @@ std::vector<HeapType> HeapType::getHeapTypeChildren() {
return collector.children;
}
-bool Signature::operator<(const Signature& other) const {
- return TypeComparator().lessThan(*this, other);
-}
-
template<typename T> static std::string genericToString(const T& t) {
std::ostringstream ss;
ss << t;
@@ -1203,127 +1173,6 @@ unsigned Field::getByteSize() const {
namespace {
-bool TypeComparator::lessThan(Type a, Type b) {
- if (a == b) {
- return false;
- }
- if (a.isBasic() && b.isBasic()) {
- return a.getBasic() < b.getBasic();
- }
- if (a.isBasic()) {
- return true;
- }
- if (b.isBasic()) {
- return false;
- }
- return lessThan(*getTypeInfo(a), *getTypeInfo(b));
-}
-
-bool TypeComparator::lessThan(HeapType a, HeapType b) {
- if (a == b) {
- return false;
- }
- if (seen.count({a, b})) {
- // We weren't able to disprove that a == b since we last saw them, so it
- // holds coinductively that a < b is false.
- return false;
- }
- if (a.isBasic() && b.isBasic()) {
- return a.getBasic() < b.getBasic();
- }
- if (a.isBasic()) {
- return true;
- }
- if (b.isBasic()) {
- return false;
- }
- // As we recurse, we will coinductively assume that a == b unless proven
- // otherwise.
- seen.insert({a, b});
- return lessThan(*getHeapTypeInfo(a), *getHeapTypeInfo(b));
-}
-
-bool TypeComparator::lessThan(const TypeInfo& a, const TypeInfo& b) {
- if (a.kind != b.kind) {
- return a.kind < b.kind;
- }
- switch (a.kind) {
- case TypeInfo::TupleKind:
- return lessThan(a.tuple, b.tuple);
- case TypeInfo::RefKind:
- if (a.ref.nullable != b.ref.nullable) {
- return a.ref.nullable < b.ref.nullable;
- }
- return lessThan(a.ref.heapType, b.ref.heapType);
- case TypeInfo::RttKind:
- return lessThan(a.rtt, b.rtt);
- }
- WASM_UNREACHABLE("unexpected kind");
-}
-
-bool TypeComparator::lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b) {
- if (a.kind != b.kind) {
- return a.kind < b.kind;
- }
- switch (a.kind) {
- case HeapTypeInfo::BasicKind:
- return a.basic < b.basic;
- case HeapTypeInfo::SignatureKind:
- return lessThan(a.signature, b.signature);
- case HeapTypeInfo::StructKind:
- return lessThan(a.struct_, b.struct_);
- case HeapTypeInfo::ArrayKind:
- return lessThan(a.array, b.array);
- }
- WASM_UNREACHABLE("unexpected kind");
-}
-
-bool TypeComparator::lessThan(const Tuple& a, const Tuple& b) {
- return std::lexicographical_compare(
- a.types.begin(),
- a.types.end(),
- b.types.begin(),
- b.types.end(),
- [&](Type ta, Type tb) { return lessThan(ta, tb); });
-}
-
-bool TypeComparator::lessThan(const Field& a, const Field& b) {
- if (a.mutable_ != b.mutable_) {
- return a.mutable_ < b.mutable_;
- }
- if (a.type == Type::i32 && b.type == Type::i32) {
- return a.packedType < b.packedType;
- }
- return lessThan(a.type, b.type);
-}
-
-bool TypeComparator::lessThan(const Signature& a, const Signature& b) {
- if (a.results != b.results) {
- return lessThan(a.results, b.results);
- }
- return lessThan(a.params, b.params);
-}
-
-bool TypeComparator::lessThan(const Struct& a, const Struct& b) {
- return std::lexicographical_compare(
- a.fields.begin(),
- a.fields.end(),
- b.fields.begin(),
- b.fields.end(),
- [&](const Field& fa, const Field& fb) { return lessThan(fa, fb); });
-}
-
-bool TypeComparator::lessThan(const Array& a, const Array& b) {
- return lessThan(a.element, b.element);
-}
-
-bool TypeComparator::lessThan(const Rtt& a, const Rtt& b) {
- if (a.depth != b.depth) {
- return a.depth < b.depth;
- }
- return lessThan(a.heapType, b.heapType);
-}
-
bool SubTyper::isSubType(Type a, Type b) {
if (a == b) {
return true;
@@ -1546,7 +1395,8 @@ HeapType TypeBounder::lub(HeapType a, HeapType b) {
// Allocate a new slot to construct the LUB of this pair if we have not
// already seen it before. Canonicalize the pair to have the element with the
// smaller ID first since order does not matter.
- auto pair = std::make_pair(std::min(a, b), std::max(a, b));
+ auto pair =
+ a.getID() < b.getID() ? std::make_pair(a, b) : std::make_pair(b, a);
size_t index = builder.size();
auto result = indices.insert({pair, index});
if (!result.second) {
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 3079ad0bb..d82542668 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -224,7 +224,7 @@ struct FunctionValidator : public WalkerPass<PostWalker<FunctionValidator>> {
std::unordered_set<Name> delegateTargetNames;
std::unordered_set<Name> rethrowTargetNames;
- std::set<Type> returnTypes; // types used in returns
+ std::unordered_set<Type> returnTypes; // types used in returns
// Binaryen IR requires that label names must be unique - IR generators must
// ensure that
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-22 09:45:01 +0000