Skip to content

Commit 92b0cbd

Browse files
tlivelytlively
authored
Remove Type ordering (WebAssembly#3793)
As found in WebAssembly#3682, the current implementation of type ordering is not correct, and although the immediate issue would be easy to fix, I don't think the current intended comparison algorithm is correct in the first place. Rather than try to switch to using a correct algorithm (which I am not sure I know how to implement, although I have an idea) this PR removes Type ordering entirely. In places that used Type ordering with std::set or std::map because they require deterministic iteration order, this PR uses InsertOrdered{Set,Map} instead.
1 parent f8bb9c2 commit 92b0cbd

162 files changed

Lines changed: 492 additions & 656 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎src/ir/module-utils.h‎

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
#include "ir/manipulation.h"
2323
#include "ir/properties.h"
2424
#include "pass.h"
25+
#include "support/insert_ordered.h"
2526
#include "support/unique_deferring_queue.h"
2627
#include "wasm.h"
2728

@@ -306,10 +307,12 @@ template<typename T> inline void iterImports(Module& wasm, T visitor) {
306307
// some computation that the operation performs.
307308
// The operation performend should not modify the wasm module in any way.
308309
// TODO: enforce this
309-
template<typename T> struct ParallelFunctionAnalysis {
310+
template<typename K, typename V> using DefaultMap = std::map<K, V>;
311+
template<typename T, template<typename, typename> class MapT = DefaultMap>
312+
struct ParallelFunctionAnalysis {
310313
Module& wasm;
311314

312-
typedef std::map<Function*, T> Map;
315+
typedef MapT<Function*, T> Map;
313316
Map map;
314317

315318
typedef std::function<void(Function*, T&)> Func;
@@ -467,7 +470,7 @@ template<typename T> struct CallGraphPropertyAnalysis {
467470
inline void collectHeapTypes(Module& wasm,
468471
std::vector<HeapType>& types,
469472
std::unordered_map<HeapType, Index>& typeIndices) {
470-
struct Counts : public std::unordered_map<HeapType, size_t> {
473+
struct Counts : public InsertOrderedMap<HeapType, size_t> {
471474
void note(HeapType type) {
472475
if (!type.isBasic()) {
473476
(*this)[type]++;
@@ -522,7 +525,7 @@ inline void collectHeapTypes(Module& wasm,
522525
}
523526

524527
// Collect info from functions in parallel.
525-
ModuleUtils::ParallelFunctionAnalysis<Counts> analysis(
528+
ModuleUtils::ParallelFunctionAnalysis<Counts, InsertOrderedMap> analysis(
526529
wasm, [&](Function* func, Counts& counts) {
527530
counts.note(func->sig);
528531
for (auto type : func->vars) {
@@ -534,9 +537,9 @@ inline void collectHeapTypes(Module& wasm,
534537
});
535538

536539
// Combine the function info with the module info.
537-
for (auto& pair : analysis.map) {
538-
Counts& functionCounts = pair.second;
539-
for (auto& innerPair : functionCounts) {
540+
for (const auto& pair : analysis.map) {
541+
const Counts& functionCounts = pair.second;
542+
for (const auto& innerPair : functionCounts) {
540543
counts[innerPair.first] += innerPair.second;
541544
}
542545
}
@@ -547,7 +550,7 @@ inline void collectHeapTypes(Module& wasm,
547550
// As we do this we may find more and more types, as nested children of
548551
// previous ones. Each such type will appear in the type section once, so
549552
// we just need to visit it once.
550-
std::unordered_set<HeapType> newTypes;
553+
InsertOrderedSet<HeapType> newTypes;
551554
for (auto& pair : counts) {
552555
newTypes.insert(pair.first);
553556
}
@@ -565,13 +568,10 @@ inline void collectHeapTypes(Module& wasm,
565568
}
566569
}
567570

568-
// Sort by frequency and then simplicity.
571+
// Sort by frequency and then original insertion order.
569572
std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), counts.end());
570573
std::stable_sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
571-
if (a.second != b.second) {
572-
return a.second > b.second;
573-
}
574-
return a.first < b.first;
574+
return a.second > b.second;
575575
});
576576
for (Index i = 0; i < sorted.size(); ++i) {
577577
typeIndices[sorted[i].first] = i;

‎src/literal.h‎

Lines changed: 1 addition & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -759,39 +759,7 @@ template<> struct hash<wasm::Literals> {
759759
return digest;
760760
}
761761
};
762-
template<> struct less<wasm::Literal> {
763-
bool operator()(const wasm::Literal& a, const wasm::Literal& b) const {
764-
if (a.type < b.type) {
765-
return true;
766-
}
767-
if (b.type < a.type) {
768-
return false;
769-
}
770-
TODO_SINGLE_COMPOUND(a.type);
771-
switch (a.type.getBasic()) {
772-
case wasm::Type::i32:
773-
return a.geti32() < b.geti32();
774-
case wasm::Type::f32:
775-
return a.reinterpreti32() < b.reinterpreti32();
776-
case wasm::Type::i64:
777-
return a.geti64() < b.geti64();
778-
case wasm::Type::f64:
779-
return a.reinterpreti64() < b.reinterpreti64();
780-
case wasm::Type::v128:
781-
return memcmp(a.getv128Ptr(), b.getv128Ptr(), 16) < 0;
782-
case wasm::Type::funcref:
783-
case wasm::Type::externref:
784-
case wasm::Type::anyref:
785-
case wasm::Type::eqref:
786-
case wasm::Type::i31ref:
787-
case wasm::Type::dataref:
788-
case wasm::Type::none:
789-
case wasm::Type::unreachable:
790-
return false;
791-
}
792-
WASM_UNREACHABLE("unexpected type");
793-
}
794-
};
762+
795763
} // namespace std
796764

797765
#endif // wasm_literal_h

‎src/passes/Asyncify.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -380,8 +380,8 @@ class FakeGlobalHelper {
380380
}
381381

382382
private:
383-
std::map<Type, Name> map;
384-
std::map<Name, Type> rev;
383+
std::unordered_map<Type, Name> map;
384+
std::unordered_map<Name, Type> rev;
385385

386386
// Collect the types returned from all calls for which call support globals
387387
// may need to be generated.
@@ -1237,7 +1237,7 @@ struct AsyncifyLocals : public WalkerPass<PostWalker<AsyncifyLocals>> {
12371237
std::unique_ptr<AsyncifyBuilder> builder;
12381238

12391239
Index rewindIndex;
1240-
std::map<Type, Index> fakeCallLocals;
1240+
std::unordered_map<Type, Index> fakeCallLocals;
12411241
std::set<Index> relevantLiveLocals;
12421242

12431243
void findRelevantLiveLocals(Function* func) {

‎src/passes/ConstHoisting.cpp‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -30,12 +30,11 @@
3030
// <= 1 byte to declare the local and 2-3 to use it!
3131
//
3232

33-
#include <map>
34-
35-
#include <pass.h>
36-
#include <wasm-binary.h>
37-
#include <wasm-builder.h>
38-
#include <wasm.h>
33+
#include "pass.h"
34+
#include "support/insert_ordered.h"
35+
#include "wasm-binary.h"
36+
#include "wasm-builder.h"
37+
#include "wasm.h"
3938

4039
namespace wasm {
4140

@@ -47,7 +46,7 @@ struct ConstHoisting : public WalkerPass<PostWalker<ConstHoisting>> {
4746

4847
Pass* create() override { return new ConstHoisting; }
4948

50-
std::map<Literal, std::vector<Expression**>> uses;
49+
InsertOrderedMap<Literal, std::vector<Expression**>> uses;
5150

5251
void visitConst(Const* curr) {
5352
uses[curr->value].push_back(getCurrentPointer());

‎src/passes/GenerateDynCalls.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@
2828
#include "ir/import-utils.h"
2929
#include "pass.h"
3030
#include "support/debug.h"
31+
#include "support/insert_ordered.h"
3132
#include "wasm-builder.h"
3233

3334
#define DEBUG_TYPE "generate-dyncalls"
@@ -81,7 +82,7 @@ struct GenerateDynCalls : public WalkerPass<PostWalker<GenerateDynCalls>> {
8182

8283
bool onlyI64;
8384
// The set of all invokes' signatures
84-
std::set<Signature> invokeSigs;
85+
InsertOrderedSet<Signature> invokeSigs;
8586
};
8687

8788
static bool hasI64(Signature sig) {

‎src/passes/RemoveNonJSOps.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@
4343
#include "ir/memory-utils.h"
4444
#include "ir/module-utils.h"
4545
#include "passes/intrinsics-module.h"
46+
#include "support/insert_ordered.h"
4647
#include "wasm-builder.h"
4748
#include "wasm-s-parser.h"
4849

@@ -51,7 +52,7 @@ namespace wasm {
5152
struct RemoveNonJSOpsPass : public WalkerPass<PostWalker<RemoveNonJSOpsPass>> {
5253
std::unique_ptr<Builder> builder;
5354
std::unordered_set<Name> neededIntrinsics;
54-
std::set<std::pair<Name, Type>> neededImportedGlobals;
55+
InsertOrderedSet<std::pair<Name, Type>> neededImportedGlobals;
5556

5657
bool isFunctionParallel() override { return false; }
5758

‎src/support/insert_ordered.h‎

Lines changed: 40 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -83,24 +83,43 @@ template<typename T> struct InsertOrderedSet {
8383
// order that elements were added to the map (not in the order
8484
// of operator<(Key, Key))
8585
template<typename Key, typename T> struct InsertOrderedMap {
86-
std::unordered_map<Key, typename std::list<std::pair<Key, T>>::iterator> Map;
87-
std::list<std::pair<Key, T>> List;
86+
std::unordered_map<Key, typename std::list<std::pair<const Key, T>>::iterator>
87+
Map;
88+
std::list<std::pair<const Key, T>> List;
89+
90+
typedef typename std::list<std::pair<const Key, T>>::iterator iterator;
91+
iterator begin() { return List.begin(); }
92+
iterator end() { return List.end(); }
93+
94+
typedef
95+
typename std::list<std::pair<const Key, T>>::const_iterator const_iterator;
96+
const_iterator begin() const { return List.begin(); }
97+
const_iterator end() const { return List.end(); }
98+
99+
std::pair<iterator, bool> insert(std::pair<const Key, T>& kv) {
100+
// Try inserting with a placeholder list iterator.
101+
auto inserted = Map.insert({kv.first, List.end()});
102+
if (inserted.second) {
103+
// This is a new item; insert it in the list and update the iterator.
104+
List.push_back(kv);
105+
inserted.first->second = std::prev(List.end());
106+
}
107+
return {inserted.first->second, inserted.second};
108+
}
88109

89110
T& operator[](const Key& k) {
111+
std::pair<const Key, T> kv = {k, {}};
112+
return insert(kv).first->second;
113+
}
114+
115+
iterator find(const Key& k) {
90116
auto it = Map.find(k);
91117
if (it == Map.end()) {
92-
List.push_back(std::make_pair(k, T()));
93-
auto e = --List.end();
94-
Map.insert(std::make_pair(k, e));
95-
return e->second;
118+
return end();
96119
}
97-
return it->second->second;
120+
return it->second;
98121
}
99122

100-
typedef typename std::list<std::pair<Key, T>>::iterator iterator;
101-
iterator begin() { return List.begin(); }
102-
iterator end() { return List.end(); }
103-
104123
void erase(const Key& k) {
105124
auto it = Map.find(k);
106125
if (it != Map.end()) {
@@ -126,14 +145,19 @@ template<typename Key, typename T> struct InsertOrderedMap {
126145
size_t count(const Key& k) const { return Map.count(k); }
127146

128147
InsertOrderedMap() = default;
129-
InsertOrderedMap(InsertOrderedMap& other) {
130-
// TODO, watch out for iterators.
131-
WASM_UNREACHABLE("unimp");
148+
InsertOrderedMap(const InsertOrderedMap& other) {
149+
for (auto kv : other) {
150+
insert(kv);
151+
}
132152
}
133153
InsertOrderedMap& operator=(const InsertOrderedMap& other) {
134-
// TODO, watch out for iterators.
135-
WASM_UNREACHABLE("unimp");
154+
if (this != &other) {
155+
this->~InsertOrderedMap();
156+
new (this) InsertOrderedMap<Key, T>(other);
157+
}
158+
return *this;
136159
}
160+
137161
bool operator==(const InsertOrderedMap& other) {
138162
return Map == other.Map && List == other.List;
139163
}

‎src/tools/fuzzing.h‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ high chance for set at start of loop
2929

3030
#include "ir/branch-utils.h"
3131
#include "ir/memory-utils.h"
32+
#include "support/insert_ordered.h"
3233
#include <ir/find_all.h>
3334
#include <ir/literal-utils.h>
3435
#include <ir/manipulation.h>
@@ -459,7 +460,7 @@ class TranslateToFuzzReader {
459460
}
460461
}
461462

462-
std::map<Type, std::vector<Name>> globalsByType;
463+
std::unordered_map<Type, std::vector<Name>> globalsByType;
463464

464465
void setupGlobals() {
465466
// If there were initial wasm contents, there may be imported globals. That
@@ -650,7 +651,7 @@ class TranslateToFuzzReader {
650651
std::vector<Expression*> hangStack;
651652

652653
// type => list of locals with that type
653-
std::map<Type, std::vector<Index>> typeLocals;
654+
std::unordered_map<Type, std::vector<Index>> typeLocals;
654655

655656
FunctionCreationContext(TranslateToFuzzReader& parent, Function* func)
656657
: parent(parent), func(func) {
@@ -782,7 +783,7 @@ class TranslateToFuzzReader {
782783
struct Scanner
783784
: public PostWalker<Scanner, UnifiedExpressionVisitor<Scanner>> {
784785
// A map of all expressions, categorized by type.
785-
std::map<Type, std::vector<Expression*>> exprsByType;
786+
InsertOrderedMap<Type, std::vector<Expression*>> exprsByType;
786787

787788
void visitExpression(Expression* curr) {
788789
exprsByType[curr->type].push_back(curr);

‎src/wasm-stack.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
#include "ir/branch-utils.h"
2121
#include "ir/properties.h"
2222
#include "pass.h"
23+
#include "support/insert_ordered.h"
2324
#include "wasm-binary.h"
2425
#include "wasm-traversal.h"
2526
#include "wasm.h"
@@ -141,7 +142,7 @@ class BinaryInstWriter : public OverriddenVisitor<BinaryInstWriter> {
141142

142143
// Keeps track of the binary index of the scratch locals used to lower
143144
// tuple.extract.
144-
std::map<Type, Index> scratchLocals;
145+
InsertOrderedMap<Type, Index> scratchLocals;
145146
void countScratchLocals();
146147
void setScratchLocals();
147148
};

‎src/wasm-type.h‎

Lines changed: 0 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -173,9 +173,6 @@ class Type {
173173
bool operator!=(const Type& other) const { return id != other.id; }
174174
bool operator!=(const BasicType& other) const { return id != other; }
175175

176-
// Order types by some notion of simplicity.
177-
bool operator<(const Type& other) const;
178-
179176
// Returns the type size in bytes. Only single types are supported.
180177
unsigned getByteSize() const;
181178

@@ -362,9 +359,6 @@ class HeapType {
362359
bool operator!=(const HeapType& other) const { return id != other.id; }
363360
bool operator!=(const BasicHeapType& other) const { return id != other; }
364361

365-
// Order heap types by some notion of simplicity.
366-
bool operator<(const HeapType& other) const;
367-
368362
// Returns true if left is a subtype of right. Subtype includes itself.
369363
static bool isSubType(HeapType left, HeapType right);
370364

@@ -414,7 +408,6 @@ struct Signature {
414408
return params == other.params && results == other.results;
415409
}
416410
bool operator!=(const Signature& other) const { return !(*this == other); }
417-
bool operator<(const Signature& other) const;
418411
std::string toString() const;
419412
};
420413

0 commit comments

Comments
 (0)