diff options
| -rw-r--r-- | src/passes/ReorderGlobals.cpp | 397 | ||||
| -rw-r--r-- | test/lit/merge/names.wat | 12 | ||||
| -rw-r--r-- | test/lit/merge/renamings.wat | 11 | ||||
| -rw-r--r-- | test/lit/passes/j2cl.wast | 25 | ||||
| -rw-r--r-- | test/lit/passes/reorder-globals-real.wast | 894 | ||||
| -rw-r--r-- | test/lit/passes/reorder-globals.wast | 547 |
6 files changed, 1774 insertions, 112 deletions
diff --git a/src/passes/ReorderGlobals.cpp b/src/passes/ReorderGlobals.cpp index 9b5940a21..4602f3284 100644 --- a/src/passes/ReorderGlobals.cpp +++ b/src/passes/ReorderGlobals.cpp @@ -19,6 +19,17 @@ // binaries because fewer bytes are needed to encode references to frequently // used globals. // +// This pass also sorts by dependencies, as each global can only appear after +// those it refers to. Other passes can use this internally to fix the ordering +// after they add new globals. +// +// The "always" variant of this pass will always sort globals, even if there are +// so few they all fit in a single LEB. In "always" mode we sort regardless and +// we measure size by considering each subsequent index to have a higher cost. +// That is, in reality the size of all globals up to 128 is a single byte, and +// then the LEB grows to 2, while in "always" mode we increase the size by 1/128 +// for each global in a smooth manner. "Always" is mainly useful for testing. +// #include "memory" @@ -29,14 +40,15 @@ namespace wasm { -using NameCountMap = std::unordered_map<Name, std::atomic<Index>>; +// We'll count uses in parallel. +using AtomicNameCountMap = std::unordered_map<Name, std::atomic<Index>>; struct UseCountScanner : public WalkerPass<PostWalker<UseCountScanner>> { bool isFunctionParallel() override { return true; } bool modifiesBinaryenIR() override { return false; } - UseCountScanner(NameCountMap& counts) : counts(counts) {} + UseCountScanner(AtomicNameCountMap& counts) : counts(counts) {} std::unique_ptr<Pass> create() override { return std::make_unique<UseCountScanner>(counts); @@ -53,112 +65,355 @@ struct UseCountScanner : public WalkerPass<PostWalker<UseCountScanner>> { } private: - NameCountMap& counts; + AtomicNameCountMap& counts; }; struct ReorderGlobals : public Pass { - // Whether to always reorder globals, even if there are very few and the - // benefit is minor. That is useful for testing, and also internally in passes - // that use us to reorder them so dependencies appear first (that is, if a - // pass ends up with an earlier global reading a later one, the sorting in - // this pass will reorder them properly; we need to take those dependencies - // into account anyhow here). bool always; ReorderGlobals(bool always) : always(always) {} + // For efficiency we will use global indices rather than names. That is, we + // use the index of the global in the original ordering to identify each + // global. A different ordering is then a vector of new indices, saying where + // each one moves, which is logically a mapping between indices. + using IndexIndexMap = std::vector<Index>; + + // We will also track counts of uses for each global. We use floating-point + // values here since while the initial counts are integers, we will be + // considering fractional sums of them later. + using IndexCountMap = std::vector<double>; + + // We must take into account dependencies, so that globals appear before + // their users in other globals: + // + // (global $a i32 (i32.const 10)) + // (global $b i32 (global.get $a)) ;; $b depends on $a; $a must be first + // + // To do so we construct a map from each global to those it depends on. We + // also build the reverse map, of those that it is depended upon by. + struct Dependencies { + std::unordered_map<Index, std::unordered_set<Index>> dependsOn; + std::unordered_map<Index, std::unordered_set<Index>> dependedUpon; + }; + void run(Module* module) override { - if (module->globals.size() < 128 && !always) { + auto& globals = module->globals; + + if (globals.size() < 128 && !always) { // The module has so few globals that they all fit in a single-byte U32LEB // value, so no reordering we can do can actually decrease code size. Note // that this is the common case with wasm MVP modules where the only // globals are typically the stack pointer and perhaps a handful of others // (however, features like wasm GC there may be a great many globals). + // TODO: we still need to sort here to fix dependencies sometimes return; } - NameCountMap counts; + AtomicNameCountMap atomicCounts; // Fill in info, as we'll operate on it in parallel. - for (auto& global : module->globals) { - counts[global->name]; + for (auto& global : globals) { + atomicCounts[global->name]; } // Count uses. - UseCountScanner scanner(counts); + UseCountScanner scanner(atomicCounts); scanner.run(getPassRunner(), module); scanner.runOnModuleCode(getPassRunner(), module); - // Do a toplogical sort to ensure we keep dependencies before the things - // that need them. For example, if $b's definition depends on $a then $b - // must appear later: - // - // (global $a i32 (i32.const 10)) - // (global $b i32 (global.get $a)) ;; $b depends on $a - // - struct DependencySort : TopologicalSort<Name, DependencySort> { - Module& wasm; - const NameCountMap& counts; - - std::unordered_map<Name, std::vector<Name>> deps; - - DependencySort(Module& wasm, const NameCountMap& counts) - : wasm(wasm), counts(counts) { - // Sort a list of global names by their counts. - auto sort = [&](std::vector<Name>& globals) { - std::stable_sort( - globals.begin(), globals.end(), [&](const Name& a, const Name& b) { - return counts.at(a) < counts.at(b); - }); - }; - - // Sort the globals. - std::vector<Name> sortedNames; - for (auto& global : wasm.globals) { - sortedNames.push_back(global->name); - } - sort(sortedNames); + // Switch to non-atomic for all further processing, and convert names to + // indices. + std::unordered_map<Name, Index> originalIndices; + for (Index i = 0; i < globals.size(); i++) { + originalIndices[globals[i]->name] = i; + } + IndexCountMap counts(globals.size()); + for (auto& [name, count] : atomicCounts) { + counts[originalIndices[name]] = count; + } - // Everything is a root (we need to emit all globals). - for (auto global : sortedNames) { - push(global); + // Compute dependencies. + Dependencies deps; + for (Index i = 0; i < globals.size(); i++) { + auto& global = globals[i]; + if (!global->imported()) { + for (auto* get : FindAll<GlobalGet>(global->init).list) { + auto getIndex = originalIndices[get->name]; + deps.dependsOn[i].insert(getIndex); + deps.dependedUpon[getIndex].insert(i); } + } + } + + // Compute various sorting options. All the options use a variation of the + // algorithm in doSort() below, see there for more details; the only + // difference between the sorts is in the use counts we provide it. + struct SortAndSize { + IndexIndexMap sort; + double size; + SortAndSize(IndexIndexMap&& sort, double size) + : sort(std::move(sort)), size(size) {} + }; + std::vector<SortAndSize> options; + auto addOption = [&](const IndexCountMap& customCounts) { + // Compute the sort using custom counts that guide us how to order. + auto sort = doSort(customCounts, deps, module); + // Compute the size using the true counts. + auto size = computeSize(sort, counts); + options.emplace_back(std::move(sort), size); + }; - // The dependencies are the globals referred to. - for (auto& global : wasm.globals) { - if (global->imported()) { - continue; - } - std::vector<Name> vec; - for (auto* get : FindAll<GlobalGet>(global->init).list) { - vec.push_back(get->name); - } - sort(vec); - deps[global->name] = std::move(vec); + // Compute the closest thing we can to the original, unoptimized sort, by + // setting all counts to 0 there, so it only takes into account dependencies + // and the original ordering and nothing else. + // + // We put this sort first because if they all end up with equal size we + // prefer it (as it avoids pointless changes). + IndexCountMap zeroes(globals.size()); + addOption(zeroes); + + // A simple sort that uses the counts. As the algorithm in doSort() is + // greedy (see below), this is a pure greedy sort (at each point it time it + // picks the global with the highest count that it can). + addOption(counts); + + // We can make the sort less greedy by adding to each global's count some of + // the count of its children. Then we'd still be picking in a greedy manner + // but our choices would be influenced by the bigger picture of what can be + // unlocked by emitting a particular global (it may have a low count itself, + // but allow emitting something that depends on it that has a high count). + // We try two variations of this, one which is a simple sum (add the + // dependent's counts to the global's) and one which exponentially decreases + // them (that is, we add a small multiple of the dependent's counts, which + // may help as the dependents also depend on other things potentially, so a + // simple sum may be too naive). + double const EXPONENTIAL_FACTOR = 0.095; + IndexCountMap sumCounts(globals.size()), exponentialCounts(globals.size()); + + struct Sort : public TopologicalSort<Index, Sort> { + const Dependencies& deps; + + Sort(Index numGlobals, const Dependencies& deps) : deps(deps) { + for (Index i = 0; i < numGlobals; i++) { + push(i); } } - void pushPredecessors(Name global) { - for (auto pred : deps[global]) { - push(pred); + void pushPredecessors(Index global) { + auto iter = deps.dependedUpon.find(global); + if (iter == deps.dependedUpon.end()) { + return; + } + for (auto dep : iter->second) { + push(dep); } } - }; + } sort(globals.size(), deps); - std::unordered_map<Name, Index> sortedIndexes; - for (auto global : DependencySort(*module, counts)) { - auto index = sortedIndexes.size(); - sortedIndexes[global] = index; + for (auto global : sort) { + // We can compute this global's count as in the sorted order all the + // values it cares about are resolved. Start with the self-count, then + // add the deps. + sumCounts[global] = exponentialCounts[global] = counts[global]; + for (auto dep : deps.dependedUpon[global]) { + sumCounts[global] += sumCounts[dep]; + exponentialCounts[global] += + EXPONENTIAL_FACTOR * exponentialCounts[dep]; + } } - std::sort( - module->globals.begin(), - module->globals.end(), - [&](const std::unique_ptr<Global>& a, const std::unique_ptr<Global>& b) { - return sortedIndexes[a->name] < sortedIndexes[b->name]; - }); + addOption(sumCounts); + addOption(exponentialCounts); + // Pick the best out of all the options we computed. + IndexIndexMap* best = nullptr; + double bestSize; + for (auto& [sort, size] : options) { + if (!best || size < bestSize) { + best = &sort; + bestSize = size; + } + } + + // Apply the indices we computed. + std::vector<std::unique_ptr<Global>> old(std::move(globals)); + globals.resize(old.size()); + for (Index i = 0; i < old.size(); i++) { + globals[(*best)[i]] = std::move(old[i]); + } module->updateMaps(); } + + IndexIndexMap doSort(const IndexCountMap& counts, + const Dependencies& originalDeps, + Module* module) { + auto& globals = module->globals; + + // Copy the deps as we will operate on them as we go. + auto deps = originalDeps; + + // To sort the globals we do a simple greedy approach of always picking the + // global with the highest count at every point in time, subject to the + // constraint that we can only emit globals that have all of their + // dependencies already emitted. To do so we keep a list of the "available" + // globals, which are those with no remaining dependencies. Then by keeping + // the list of available globals in heap form we can simply pop the largest + // from the heap each time, and add new available ones as they become so. + // + // Other approaches here could be to do a topological sort, but the optimal + // order may not require strict ordering by topological depth, e.g.: + /* + // $c - $a + // / + // $e + // \ + // $d - $b + */ + // Here $e depends on $c and $d, $c depends on $a, and $d on $b. This is a + // partial order, as $d can be before or after $a, for example. As a result, + // if we sorted topologically by sub-trees here then we'd keep $c and $a + // together, and $d and $b, but a better order might interleave them. A good + // order also may not keep topological depths separated, e.g. we may want to + // put $a in between $c and $d despite it having a greater depth. + // + // The greedy approach here may also be unoptimal, however. Consider that we + // might see that the best available global is $a, but if we popped $b + // instead that could unlock $c which depends on $b, and $c may have a much + // higher use count than $a. For that reason we try several variations of + // this with different counts, see earlier. + std::vector<Index> availableHeap; + + // Comparison function. Given a and b, returns if a should be before b. This + // is used in a heap, where "highest" means "popped first", so see the notes + // below on how we order. + auto cmp = [&](Index a, Index b) { + // Imports always go first. The binary writer takes care of this itself + // anyhow, but it is better to do it here in the IR so we can actually + // see what the final layout will be. + auto aImported = globals[a]->imported(); + auto bImported = globals[b]->imported(); + // The highest items will be popped first off the heap, so we want imports + // to be at higher indexes, that is, + // + // unimported, unimported, imported, imported. + // + // Then the imports are popped first. + if (aImported != bImported) { + return bImported; + } + + // Sort by the counts. We want higher counts at higher indexes so they are + // popped first, that is, + // + // 10, 20, 30, 40 + // + auto aCount = counts[a]; + auto bCount = counts[b]; + if (aCount != bCount) { + return aCount < bCount; + } + + // Break ties using the original order, which means just using the + // indices we have. We need lower indexes at the top so they are popped + // first, that is, + // + // 3, 2, 1, 0 + // + return a > b; + }; + + // Push an item that just became available to the available heap. + auto push = [&](Index global) { + availableHeap.push_back(global); + std::push_heap(availableHeap.begin(), availableHeap.end(), cmp); + }; + + // The initially available globals are those with no dependencies. + for (Index i = 0; i < globals.size(); i++) { + if (deps.dependsOn[i].empty()) { + push(i); + } + } + + // Pop off the heap: Emit the global and its final, sorted index. Keep + // doing that until we finish processing all the globals. + IndexIndexMap sortedindices(globals.size()); + Index numSortedindices = 0; + while (!availableHeap.empty()) { + std::pop_heap(availableHeap.begin(), availableHeap.end(), cmp); + auto global = availableHeap.back(); + sortedindices[global] = numSortedindices++; + availableHeap.pop_back(); + + // Each time we pop we emit the global, which means anything that only + // depended on it becomes available to be popped as well. + for (auto other : deps.dependedUpon[global]) { + assert(deps.dependsOn[other].count(global)); + deps.dependsOn[other].erase(global); + if (deps.dependsOn[other].empty()) { + push(other); + } + } + } + + // All globals must have been handled. Cycles would prevent this, but they + // cannot exist in valid IR. + assert(numSortedindices == globals.size()); + + return sortedindices; + } + + // Given an indexing of the globals and the counts of how many times each is + // used, estimate the size of relevant parts of the wasm binary (that is, of + // LEBs in global.gets). + double computeSize(IndexIndexMap& indices, IndexCountMap& counts) { + // |indices| maps each old index to its new position in the sort. We need + // the reverse map here, which at index 0 has the old index of the global + // that will be first, and so forth. + IndexIndexMap actualOrder(indices.size()); + for (Index i = 0; i < indices.size(); i++) { + // Each global has a unique index, so we only replace 0's here, and they + // must be in bounds. + assert(indices[i] < indices.size()); + assert(actualOrder[indices[i]] == 0); + + actualOrder[indices[i]] = i; + } + + if (always) { + // In this mode we gradually increase the cost of later globals, in an + // unrealistic but smooth manner. + double total = 0; + for (Index i = 0; i < actualOrder.size(); i++) { + // Multiply the count for this global by a smoothed LEB factor, which + // starts at 1 (for 1 byte) at index 0, and then increases linearly with + // i, so that after 128 globals we reach 2 (which is the true index at + // which the LEB size normally jumps from 1 to 2), and so forth. + total += counts[actualOrder[i]] * (1.0 + (i / 128.0)); + } + return total; + } + + // The total size we are computing. + double total = 0; + // Track the size in bits and the next index at which the size increases. At + // the first iteration we'll compute the size of the LEB for index 0, and so + // forth. + size_t sizeInBits = 0; + size_t nextSizeIncrease = 0; + for (Index i = 0; i < actualOrder.size(); i++) { + if (i == nextSizeIncrease) { + sizeInBits++; + // At the current size we have 7 * sizeInBits bits to use. For example, + // at index 0 the size is 1 and we'll compute 128 here, and indeed after + // emitting 128 globals (0,..,127) the 129th (at index 128) requires a + // larger LEB. + nextSizeIncrease = 1 << (7 * sizeInBits); + } + total += counts[actualOrder[i]] * sizeInBits; + } + return total; + } }; Pass* createReorderGlobalsPass() { return new ReorderGlobals(false); } diff --git a/test/lit/merge/names.wat b/test/lit/merge/names.wat index 4562af58b..c4e814649 100644 --- a/test/lit/merge/names.wat +++ b/test/lit/merge/names.wat @@ -12,13 +12,13 @@ ;; CHECK: (type $4 (func (param (ref $u)))) - ;; CHECK: (global $global$0 i32 (i32.const 0)) + ;; CHECK: (global $glob0 i32 (i32.const 0)) - ;; CHECK: (global $glob2 i32 (i32.const 0)) + ;; CHECK: (global $global$1 i32 (i32.const 0)) - ;; CHECK: (global $global$2 i32 (i32.const 0)) + ;; CHECK: (global $glob2 i32 (i32.const 0)) - ;; CHECK: (global $glob0 i32 (i32.const 0)) + ;; CHECK: (global $global$3 i32 (i32.const 0)) ;; CHECK: (memory $mem0 0) @@ -54,7 +54,7 @@ ;; CHECK: (export "g0" (global $glob0)) - ;; CHECK: (export "g1" (global $global$2)) + ;; CHECK: (export "g1" (global $global$1)) ;; CHECK: (export "m0" (memory $mem0)) @@ -80,7 +80,7 @@ ;; CHECK: (export "g2" (global $glob2)) - ;; CHECK: (export "g3" (global $global$0)) + ;; CHECK: (export "g3" (global $global$3)) ;; CHECK: (export "tag2" (tag $tag2)) diff --git a/test/lit/merge/renamings.wat b/test/lit/merge/renamings.wat index 4d1c32c5a..c6a22542a 100644 --- a/test/lit/merge/renamings.wat +++ b/test/lit/merge/renamings.wat @@ -23,21 +23,20 @@ ;; CHECK: (import "elsewhere" "some.tag" (tag $imported (param f64))) - ;; CHECK: (global $bar_2 i32 (i32.const 4)) - - ;; CHECK: (global $other i32 (i32.const 3)) - - ;; CHECK: (global $bar i32 (i32.const 2)) - ;; CHECK: (global $foo i32 (i32.const 1)) (global $foo i32 (i32.const 1)) ;; This global has a conflict in second.wat, and so second.wat's $bar ;; will be renamed. + ;; CHECK: (global $bar i32 (i32.const 2)) (global $bar i32 (i32.const 2)) ;; This memory has a conflict in second.wat, and so second.wat's $foo ;; will be renamed. + ;; CHECK: (global $other i32 (i32.const 3)) + + ;; CHECK: (global $bar_2 i32 (i32.const 4)) + ;; CHECK: (memory $foo 10 20) (memory $foo 10 20) diff --git a/test/lit/passes/j2cl.wast b/test/lit/passes/j2cl.wast index 1963203a8..b8081d8b2 100644 --- a/test/lit/passes/j2cl.wast +++ b/test/lit/passes/j2cl.wast @@ -6,10 +6,9 @@ (module ;; CHECK: (type $0 (func)) - ;; CHECK: (global $field-f64@Foo f64 (f64.const 1)) - ;; CHECK: (global $field-i32@Foo i32 (i32.const 1)) (global $field-i32@Foo (mut i32) (i32.const 0)) + ;; CHECK: (global $field-f64@Foo f64 (f64.const 1)) (global $field-f64@Foo (mut f64) (f64.const 0)) ;; CHECK: (func $clinit_<once>_@Foo (type $0) @@ -29,20 +28,18 @@ ;; CHECK: (type $1 (func)) - ;; CHECK: (global $field2@Foo (mut anyref) (ref.null none)) - ;; CHECK: (global $referredField@Foo i32 (i32.const 42)) (global $referredField@Foo i32 (i32.const 42)) - ;; CHECK: (global $field1@Foo anyref (struct.new $A - ;; CHECK-NEXT: (global.get $referredField@Foo) - ;; CHECK-NEXT: )) - ;; CHECK: (global $referredFieldMut@Foo (mut i32) (i32.const 42)) (global $referredFieldMut@Foo (mut i32) (i32.const 42)) + ;; CHECK: (global $field1@Foo anyref (struct.new $A + ;; CHECK-NEXT: (global.get $referredField@Foo) + ;; CHECK-NEXT: )) (global $field1@Foo (mut anyref) (ref.null none)) + ;; CHECK: (global $field2@Foo (mut anyref) (ref.null none)) (global $field2@Foo (mut anyref) (ref.null none)) ;; CHECK: (global $field3@Foo anyref (global.get $field1@Foo)) @@ -78,11 +75,10 @@ (type $A (struct)) ;; CHECK: (type $1 (func)) - ;; CHECK: (global $field-any@Foo (mut anyref) (struct.new_default $A)) - ;; CHECK: (global $field-i32@Foo (mut i32) (i32.const 2)) (global $field-i32@Foo (mut i32) (i32.const 2)) + ;; CHECK: (global $field-any@Foo (mut anyref) (struct.new_default $A)) (global $field-any@Foo (mut anyref) (struct.new $A)) ;; CHECK: (func $clinit_<once>_@Foo (type $1) @@ -156,13 +152,11 @@ (module ;; CHECK: (type $0 (func (result i32))) - ;; CHECK: (global $$var3@Zoo i32 (i32.const 2)) - - ;; CHECK: (global $$var2@Zoo i32 (i32.const 2)) - ;; CHECK: (global $$var1@Zoo i32 (i32.const 2)) (global $$var1@Zoo (mut i32) (i32.const 0)) + ;; CHECK: (global $$var2@Zoo i32 (i32.const 2)) (global $$var2@Zoo (mut i32) (i32.const 0)) + ;; CHECK: (global $$var3@Zoo i32 (i32.const 2)) (global $$var3@Zoo (mut i32) (i32.const 0)) ;; CHECK: (func $getVar1_<once>_@Zoo (type $0) (result i32) @@ -211,10 +205,9 @@ ;; CHECK: (type $1 (func (result i32))) - ;; CHECK: (global $$var2@Zoo (mut i32) (i32.const 3)) - ;; CHECK: (global $$var1@Zoo (mut i32) (i32.const 2)) (global $$var1@Zoo (mut i32) (i32.const 2)) + ;; CHECK: (global $$var2@Zoo (mut i32) (i32.const 3)) (global $$var2@Zoo (mut i32) (i32.const 3)) diff --git a/test/lit/passes/reorder-globals-real.wast b/test/lit/passes/reorder-globals-real.wast new file mode 100644 index 000000000..87ccc92c9 --- /dev/null +++ b/test/lit/passes/reorder-globals-real.wast @@ -0,0 +1,894 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited. + +;; Similar to reorder-globals, but this runs the "real" version, without +;; "-always". That is, this tests the production code. The downside is we need +;; 128+ globals to see any changes here, so we keep most testing in the other +;; file. + +;; RUN: foreach %s %t wasm-opt -all --reorder-globals -S -o - | filecheck %s + +;; A situation where the simple greedy sort fails to be optimal. We have 129 +;; globals, enough for the LEB size to grow by 1 for the last. One global, +;; |other|, is independent of the rest. The second is in a chain with all the +;; others: +;; +;; global1 <- global2 <- .. <- global128 +;; +;; other has a higher count than global1, so if we are greedy we pick it. But +;; global128 has the highest count by far, so it is actually worth emitting the +;; entire chain first, and only then other, which is the original order. +(module + ;; CHECK: (global $global1 i32 (i32.const 1)) + (global $global1 i32 (i32.const 1)) + ;; CHECK: (global $global2 i32 (global.get $global1)) + (global $global2 i32 (global.get $global1)) + ;; CHECK: (global $global3 i32 (global.get $global2)) + (global $global3 i32 (global.get $global2)) + ;; CHECK: (global $global4 i32 (global.get $global3)) + (global $global4 i32 (global.get $global3)) + ;; CHECK: (global $global5 i32 (global.get $global4)) + (global $global5 i32 (global.get $global4)) + ;; CHECK: (global $global6 i32 (global.get $global5)) + (global $global6 i32 (global.get $global5)) + ;; CHECK: (global $global7 i32 (global.get $global6)) + (global $global7 i32 (global.get $global6)) + ;; CHECK: (global $global8 i32 (global.get $global7)) + (global $global8 i32 (global.get $global7)) + ;; CHECK: (global $global9 i32 (global.get $global8)) + (global $global9 i32 (global.get $global8)) + ;; CHECK: (global $global10 i32 (global.get $global9)) + (global $global10 i32 (global.get $global9)) + ;; CHECK: (global $global11 i32 (global.get $global10)) + (global $global11 i32 (global.get $global10)) + ;; CHECK: (global $global12 i32 (global.get $global11)) + (global $global12 i32 (global.get $global11)) + ;; CHECK: (global $global13 i32 (global.get $global12)) + (global $global13 i32 (global.get $global12)) + ;; CHECK: (global $global14 i32 (global.get $global13)) + (global $global14 i32 (global.get $global13)) + ;; CHECK: (global $global15 i32 (global.get $global14)) + (global $global15 i32 (global.get $global14)) + ;; CHECK: (global $global16 i32 (global.get $global15)) + (global $global16 i32 (global.get $global15)) + ;; CHECK: (global $global17 i32 (global.get $global16)) + (global $global17 i32 (global.get $global16)) + ;; CHECK: (global $global18 i32 (global.get $global17)) + (global $global18 i32 (global.get $global17)) + ;; CHECK: (global $global19 i32 (global.get $global18)) + (global $global19 i32 (global.get $global18)) + ;; CHECK: (global $global20 i32 (global.get $global19)) + (global $global20 i32 (global.get $global19)) + ;; CHECK: (global $global21 i32 (global.get $global20)) + (global $global21 i32 (global.get $global20)) + ;; CHECK: (global $global22 i32 (global.get $global21)) + (global $global22 i32 (global.get $global21)) + ;; CHECK: (global $global23 i32 (global.get $global22)) + (global $global23 i32 (global.get $global22)) + ;; CHECK: (global $global24 i32 (global.get $global23)) + (global $global24 i32 (global.get $global23)) + ;; CHECK: (global $global25 i32 (global.get $global24)) + (global $global25 i32 (global.get $global24)) + ;; CHECK: (global $global26 i32 (global.get $global25)) + (global $global26 i32 (global.get $global25)) + ;; CHECK: (global $global27 i32 (global.get $global26)) + (global $global27 i32 (global.get $global26)) + ;; CHECK: (global $global28 i32 (global.get $global27)) + (global $global28 i32 (global.get $global27)) + ;; CHECK: (global $global29 i32 (global.get $global28)) + (global $global29 i32 (global.get $global28)) + ;; CHECK: (global $global30 i32 (global.get $global29)) + (global $global30 i32 (global.get $global29)) + ;; CHECK: (global $global31 i32 (global.get $global30)) + (global $global31 i32 (global.get $global30)) + ;; CHECK: (global $global32 i32 (global.get $global31)) + (global $global32 i32 (global.get $global31)) + ;; CHECK: (global $global33 i32 (global.get $global32)) + (global $global33 i32 (global.get $global32)) + ;; CHECK: (global $global34 i32 (global.get $global33)) + (global $global34 i32 (global.get $global33)) + ;; CHECK: (global $global35 i32 (global.get $global34)) + (global $global35 i32 (global.get $global34)) + ;; CHECK: (global $global36 i32 (global.get $global35)) + (global $global36 i32 (global.get $global35)) + ;; CHECK: (global $global37 i32 (global.get $global36)) + (global $global37 i32 (global.get $global36)) + ;; CHECK: (global $global38 i32 (global.get $global37)) + (global $global38 i32 (global.get $global37)) + ;; CHECK: (global $global39 i32 (global.get $global38)) + (global $global39 i32 (global.get $global38)) + ;; CHECK: (global $global40 i32 (global.get $global39)) + (global $global40 i32 (global.get $global39)) + ;; CHECK: (global $global41 i32 (global.get $global40)) + (global $global41 i32 (global.get $global40)) + ;; CHECK: (global $global42 i32 (global.get $global41)) + (global $global42 i32 (global.get $global41)) + ;; CHECK: (global $global43 i32 (global.get $global42)) + (global $global43 i32 (global.get $global42)) + ;; CHECK: (global $global44 i32 (global.get $global43)) + (global $global44 i32 (global.get $global43)) + ;; CHECK: (global $global45 i32 (global.get $global44)) + (global $global45 i32 (global.get $global44)) + ;; CHECK: (global $global46 i32 (global.get $global45)) + (global $global46 i32 (global.get $global45)) + ;; CHECK: (global $global47 i32 (global.get $global46)) + (global $global47 i32 (global.get $global46)) + ;; CHECK: (global $global48 i32 (global.get $global47)) + (global $global48 i32 (global.get $global47)) + ;; CHECK: (global $global49 i32 (global.get $global48)) + (global $global49 i32 (global.get $global48)) + ;; CHECK: (global $global50 i32 (global.get $global49)) + (global $global50 i32 (global.get $global49)) + ;; CHECK: (global $global51 i32 (global.get $global50)) + (global $global51 i32 (global.get $global50)) + ;; CHECK: (global $global52 i32 (global.get $global51)) + (global $global52 i32 (global.get $global51)) + ;; CHECK: (global $global53 i32 (global.get $global52)) + (global $global53 i32 (global.get $global52)) + ;; CHECK: (global $global54 i32 (global.get $global53)) + (global $global54 i32 (global.get $global53)) + ;; CHECK: (global $global55 i32 (global.get $global54)) + (global $global55 i32 (global.get $global54)) + ;; CHECK: (global $global56 i32 (global.get $global55)) + (global $global56 i32 (global.get $global55)) + ;; CHECK: (global $global57 i32 (global.get $global56)) + (global $global57 i32 (global.get $global56)) + ;; CHECK: (global $global58 i32 (global.get $global57)) + (global $global58 i32 (global.get $global57)) + ;; CHECK: (global $global59 i32 (global.get $global58)) + (global $global59 i32 (global.get $global58)) + ;; CHECK: (global $global60 i32 (global.get $global59)) + (global $global60 i32 (global.get $global59)) + ;; CHECK: (global $global61 i32 (global.get $global60)) + (global $global61 i32 (global.get $global60)) + ;; CHECK: (global $global62 i32 (global.get $global61)) + (global $global62 i32 (global.get $global61)) + ;; CHECK: (global $global63 i32 (global.get $global62)) + (global $global63 i32 (global.get $global62)) + ;; CHECK: (global $global64 i32 (global.get $global63)) + (global $global64 i32 (global.get $global63)) + ;; CHECK: (global $global65 i32 (global.get $global64)) + (global $global65 i32 (global.get $global64)) + ;; CHECK: (global $global66 i32 (global.get $global65)) + (global $global66 i32 (global.get $global65)) + ;; CHECK: (global $global67 i32 (global.get $global66)) + (global $global67 i32 (global.get $global66)) + ;; CHECK: (global $global68 i32 (global.get $global67)) + (global $global68 i32 (global.get $global67)) + ;; CHECK: (global $global69 i32 (global.get $global68)) + (global $global69 i32 (global.get $global68)) + ;; CHECK: (global $global70 i32 (global.get $global69)) + (global $global70 i32 (global.get $global69)) + ;; CHECK: (global $global71 i32 (global.get $global70)) + (global $global71 i32 (global.get $global70)) + ;; CHECK: (global $global72 i32 (global.get $global71)) + (global $global72 i32 (global.get $global71)) + ;; CHECK: (global $global73 i32 (global.get $global72)) + (global $global73 i32 (global.get $global72)) + ;; CHECK: (global $global74 i32 (global.get $global73)) + (global $global74 i32 (global.get $global73)) + ;; CHECK: (global $global75 i32 (global.get $global74)) + (global $global75 i32 (global.get $global74)) + ;; CHECK: (global $global76 i32 (global.get $global75)) + (global $global76 i32 (global.get $global75)) + ;; CHECK: (global $global77 i32 (global.get $global76)) + (global $global77 i32 (global.get $global76)) + ;; CHECK: (global $global78 i32 (global.get $global77)) + (global $global78 i32 (global.get $global77)) + ;; CHECK: (global $global79 i32 (global.get $global78)) + (global $global79 i32 (global.get $global78)) + ;; CHECK: (global $global80 i32 (global.get $global79)) + (global $global80 i32 (global.get $global79)) + ;; CHECK: (global $global81 i32 (global.get $global80)) + (global $global81 i32 (global.get $global80)) + ;; CHECK: (global $global82 i32 (global.get $global81)) + (global $global82 i32 (global.get $global81)) + ;; CHECK: (global $global83 i32 (global.get $global82)) + (global $global83 i32 (global.get $global82)) + ;; CHECK: (global $global84 i32 (global.get $global83)) + (global $global84 i32 (global.get $global83)) + ;; CHECK: (global $global85 i32 (global.get $global84)) + (global $global85 i32 (global.get $global84)) + ;; CHECK: (global $global86 i32 (global.get $global85)) + (global $global86 i32 (global.get $global85)) + ;; CHECK: (global $global87 i32 (global.get $global86)) + (global $global87 i32 (global.get $global86)) + ;; CHECK: (global $global88 i32 (global.get $global87)) + (global $global88 i32 (global.get $global87)) + ;; CHECK: (global $global89 i32 (global.get $global88)) + (global $global89 i32 (global.get $global88)) + ;; CHECK: (global $global90 i32 (global.get $global89)) + (global $global90 i32 (global.get $global89)) + ;; CHECK: (global $global91 i32 (global.get $global90)) + (global $global91 i32 (global.get $global90)) + ;; CHECK: (global $global92 i32 (global.get $global91)) + (global $global92 i32 (global.get $global91)) + ;; CHECK: (global $global93 i32 (global.get $global92)) + (global $global93 i32 (global.get $global92)) + ;; CHECK: (global $global94 i32 (global.get $global93)) + (global $global94 i32 (global.get $global93)) + ;; CHECK: (global $global95 i32 (global.get $global94)) + (global $global95 i32 (global.get $global94)) + ;; CHECK: (global $global96 i32 (global.get $global95)) + (global $global96 i32 (global.get $global95)) + ;; CHECK: (global $global97 i32 (global.get $global96)) + (global $global97 i32 (global.get $global96)) + ;; CHECK: (global $global98 i32 (global.get $global97)) + (global $global98 i32 (global.get $global97)) + ;; CHECK: (global $global99 i32 (global.get $global98)) + (global $global99 i32 (global.get $global98)) + ;; CHECK: (global $global100 i32 (global.get $global99)) + (global $global100 i32 (global.get $global99)) + ;; CHECK: (global $global101 i32 (global.get $global100)) + (global $global101 i32 (global.get $global100)) + ;; CHECK: (global $global102 i32 (global.get $global101)) + (global $global102 i32 (global.get $global101)) + ;; CHECK: (global $global103 i32 (global.get $global102)) + (global $global103 i32 (global.get $global102)) + ;; CHECK: (global $global104 i32 (global.get $global103)) + (global $global104 i32 (global.get $global103)) + ;; CHECK: (global $global105 i32 (global.get $global104)) + (global $global105 i32 (global.get $global104)) + ;; CHECK: (global $global106 i32 (global.get $global105)) + (global $global106 i32 (global.get $global105)) + ;; CHECK: (global $global107 i32 (global.get $global106)) + (global $global107 i32 (global.get $global106)) + ;; CHECK: (global $global108 i32 (global.get $global107)) + (global $global108 i32 (global.get $global107)) + ;; CHECK: (global $global109 i32 (global.get $global108)) + (global $global109 i32 (global.get $global108)) + ;; CHECK: (global $global110 i32 (global.get $global109)) + (global $global110 i32 (global.get $global109)) + ;; CHECK: (global $global111 i32 (global.get $global110)) + (global $global111 i32 (global.get $global110)) + ;; CHECK: (global $global112 i32 (global.get $global111)) + (global $global112 i32 (global.get $global111)) + ;; CHECK: (global $global113 i32 (global.get $global112)) + (global $global113 i32 (global.get $global112)) + ;; CHECK: (global $global114 i32 (global.get $global113)) + (global $global114 i32 (global.get $global113)) + ;; CHECK: (global $global115 i32 (global.get $global114)) + (global $global115 i32 (global.get $global114)) + ;; CHECK: (global $global116 i32 (global.get $global115)) + (global $global116 i32 (global.get $global115)) + ;; CHECK: (global $global117 i32 (global.get $global116)) + (global $global117 i32 (global.get $global116)) + ;; CHECK: (global $global118 i32 (global.get $global117)) + (global $global118 i32 (global.get $global117)) + ;; CHECK: (global $global119 i32 (global.get $global118)) + (global $global119 i32 (global.get $global118)) + ;; CHECK: (global $global120 i32 (global.get $global119)) + (global $global120 i32 (global.get $global119)) + ;; CHECK: (global $global121 i32 (global.get $global120)) + (global $global121 i32 (global.get $global120)) + ;; CHECK: (global $global122 i32 (global.get $global121)) + (global $global122 i32 (global.get $global121)) + ;; CHECK: (global $global123 i32 (global.get $global122)) + (global $global123 i32 (global.get $global122)) + ;; CHECK: (global $global124 i32 (global.get $global123)) + (global $global124 i32 (global.get $global123)) + ;; CHECK: (global $global125 i32 (global.get $global124)) + (global $global125 i32 (global.get $global124)) + ;; CHECK: (global $global126 i32 (global.get $global125)) + (global $global126 i32 (global.get $global125)) + ;; CHECK: (global $global127 i32 (global.get $global126)) + (global $global127 i32 (global.get $global126)) + ;; CHECK: (global $global128 i32 (global.get $global127)) + (global $global128 i32 (global.get $global127)) + + ;; CHECK: (global $other i32 (i32.const 0)) + (global $other i32 (i32.const 0)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $global128) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + ;; Aside from the uses in the globals themselves (which means one use for + ;; each of global1..global127), we add two uses of other, to make it + ;; have a higher count than global1, and 10 uses of global128, to make it + ;; have the highest count by far. + (drop (global.get $other)) + (drop (global.get $other)) + + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + (drop (global.get $global128)) + ) +) + +;; As above, but now the greedy sort is optimal. We remove all uses of +;; $global128, so $other has the highest count and there is no other factor that +;; matters here, so emitting $other first is best. +(module + ;; CHECK: (global $other i32 (i32.const 0)) + + ;; CHECK: (global $global1 i32 (i32.const 1)) + (global $global1 i32 (i32.const 1)) + ;; CHECK: (global $global2 i32 (global.get $global1)) + (global $global2 i32 (global.get $global1)) + ;; CHECK: (global $global3 i32 (global.get $global2)) + (global $global3 i32 (global.get $global2)) + ;; CHECK: (global $global4 i32 (global.get $global3)) + (global $global4 i32 (global.get $global3)) + ;; CHECK: (global $global5 i32 (global.get $global4)) + (global $global5 i32 (global.get $global4)) + ;; CHECK: (global $global6 i32 (global.get $global5)) + (global $global6 i32 (global.get $global5)) + ;; CHECK: (global $global7 i32 (global.get $global6)) + (global $global7 i32 (global.get $global6)) + ;; CHECK: (global $global8 i32 (global.get $global7)) + (global $global8 i32 (global.get $global7)) + ;; CHECK: (global $global9 i32 (global.get $global8)) + (global $global9 i32 (global.get $global8)) + ;; CHECK: (global $global10 i32 (global.get $global9)) + (global $global10 i32 (global.get $global9)) + ;; CHECK: (global $global11 i32 (global.get $global10)) + (global $global11 i32 (global.get $global10)) + ;; CHECK: (global $global12 i32 (global.get $global11)) + (global $global12 i32 (global.get $global11)) + ;; CHECK: (global $global13 i32 (global.get $global12)) + (global $global13 i32 (global.get $global12)) + ;; CHECK: (global $global14 i32 (global.get $global13)) + (global $global14 i32 (global.get $global13)) + ;; CHECK: (global $global15 i32 (global.get $global14)) + (global $global15 i32 (global.get $global14)) + ;; CHECK: (global $global16 i32 (global.get $global15)) + (global $global16 i32 (global.get $global15)) + ;; CHECK: (global $global17 i32 (global.get $global16)) + (global $global17 i32 (global.get $global16)) + ;; CHECK: (global $global18 i32 (global.get $global17)) + (global $global18 i32 (global.get $global17)) + ;; CHECK: (global $global19 i32 (global.get $global18)) + (global $global19 i32 (global.get $global18)) + ;; CHECK: (global $global20 i32 (global.get $global19)) + (global $global20 i32 (global.get $global19)) + ;; CHECK: (global $global21 i32 (global.get $global20)) + (global $global21 i32 (global.get $global20)) + ;; CHECK: (global $global22 i32 (global.get $global21)) + (global $global22 i32 (global.get $global21)) + ;; CHECK: (global $global23 i32 (global.get $global22)) + (global $global23 i32 (global.get $global22)) + ;; CHECK: (global $global24 i32 (global.get $global23)) + (global $global24 i32 (global.get $global23)) + ;; CHECK: (global $global25 i32 (global.get $global24)) + (global $global25 i32 (global.get $global24)) + ;; CHECK: (global $global26 i32 (global.get $global25)) + (global $global26 i32 (global.get $global25)) + ;; CHECK: (global $global27 i32 (global.get $global26)) + (global $global27 i32 (global.get $global26)) + ;; CHECK: (global $global28 i32 (global.get $global27)) + (global $global28 i32 (global.get $global27)) + ;; CHECK: (global $global29 i32 (global.get $global28)) + (global $global29 i32 (global.get $global28)) + ;; CHECK: (global $global30 i32 (global.get $global29)) + (global $global30 i32 (global.get $global29)) + ;; CHECK: (global $global31 i32 (global.get $global30)) + (global $global31 i32 (global.get $global30)) + ;; CHECK: (global $global32 i32 (global.get $global31)) + (global $global32 i32 (global.get $global31)) + ;; CHECK: (global $global33 i32 (global.get $global32)) + (global $global33 i32 (global.get $global32)) + ;; CHECK: (global $global34 i32 (global.get $global33)) + (global $global34 i32 (global.get $global33)) + ;; CHECK: (global $global35 i32 (global.get $global34)) + (global $global35 i32 (global.get $global34)) + ;; CHECK: (global $global36 i32 (global.get $global35)) + (global $global36 i32 (global.get $global35)) + ;; CHECK: (global $global37 i32 (global.get $global36)) + (global $global37 i32 (global.get $global36)) + ;; CHECK: (global $global38 i32 (global.get $global37)) + (global $global38 i32 (global.get $global37)) + ;; CHECK: (global $global39 i32 (global.get $global38)) + (global $global39 i32 (global.get $global38)) + ;; CHECK: (global $global40 i32 (global.get $global39)) + (global $global40 i32 (global.get $global39)) + ;; CHECK: (global $global41 i32 (global.get $global40)) + (global $global41 i32 (global.get $global40)) + ;; CHECK: (global $global42 i32 (global.get $global41)) + (global $global42 i32 (global.get $global41)) + ;; CHECK: (global $global43 i32 (global.get $global42)) + (global $global43 i32 (global.get $global42)) + ;; CHECK: (global $global44 i32 (global.get $global43)) + (global $global44 i32 (global.get $global43)) + ;; CHECK: (global $global45 i32 (global.get $global44)) + (global $global45 i32 (global.get $global44)) + ;; CHECK: (global $global46 i32 (global.get $global45)) + (global $global46 i32 (global.get $global45)) + ;; CHECK: (global $global47 i32 (global.get $global46)) + (global $global47 i32 (global.get $global46)) + ;; CHECK: (global $global48 i32 (global.get $global47)) + (global $global48 i32 (global.get $global47)) + ;; CHECK: (global $global49 i32 (global.get $global48)) + (global $global49 i32 (global.get $global48)) + ;; CHECK: (global $global50 i32 (global.get $global49)) + (global $global50 i32 (global.get $global49)) + ;; CHECK: (global $global51 i32 (global.get $global50)) + (global $global51 i32 (global.get $global50)) + ;; CHECK: (global $global52 i32 (global.get $global51)) + (global $global52 i32 (global.get $global51)) + ;; CHECK: (global $global53 i32 (global.get $global52)) + (global $global53 i32 (global.get $global52)) + ;; CHECK: (global $global54 i32 (global.get $global53)) + (global $global54 i32 (global.get $global53)) + ;; CHECK: (global $global55 i32 (global.get $global54)) + (global $global55 i32 (global.get $global54)) + ;; CHECK: (global $global56 i32 (global.get $global55)) + (global $global56 i32 (global.get $global55)) + ;; CHECK: (global $global57 i32 (global.get $global56)) + (global $global57 i32 (global.get $global56)) + ;; CHECK: (global $global58 i32 (global.get $global57)) + (global $global58 i32 (global.get $global57)) + ;; CHECK: (global $global59 i32 (global.get $global58)) + (global $global59 i32 (global.get $global58)) + ;; CHECK: (global $global60 i32 (global.get $global59)) + (global $global60 i32 (global.get $global59)) + ;; CHECK: (global $global61 i32 (global.get $global60)) + (global $global61 i32 (global.get $global60)) + ;; CHECK: (global $global62 i32 (global.get $global61)) + (global $global62 i32 (global.get $global61)) + ;; CHECK: (global $global63 i32 (global.get $global62)) + (global $global63 i32 (global.get $global62)) + ;; CHECK: (global $global64 i32 (global.get $global63)) + (global $global64 i32 (global.get $global63)) + ;; CHECK: (global $global65 i32 (global.get $global64)) + (global $global65 i32 (global.get $global64)) + ;; CHECK: (global $global66 i32 (global.get $global65)) + (global $global66 i32 (global.get $global65)) + ;; CHECK: (global $global67 i32 (global.get $global66)) + (global $global67 i32 (global.get $global66)) + ;; CHECK: (global $global68 i32 (global.get $global67)) + (global $global68 i32 (global.get $global67)) + ;; CHECK: (global $global69 i32 (global.get $global68)) + (global $global69 i32 (global.get $global68)) + ;; CHECK: (global $global70 i32 (global.get $global69)) + (global $global70 i32 (global.get $global69)) + ;; CHECK: (global $global71 i32 (global.get $global70)) + (global $global71 i32 (global.get $global70)) + ;; CHECK: (global $global72 i32 (global.get $global71)) + (global $global72 i32 (global.get $global71)) + ;; CHECK: (global $global73 i32 (global.get $global72)) + (global $global73 i32 (global.get $global72)) + ;; CHECK: (global $global74 i32 (global.get $global73)) + (global $global74 i32 (global.get $global73)) + ;; CHECK: (global $global75 i32 (global.get $global74)) + (global $global75 i32 (global.get $global74)) + ;; CHECK: (global $global76 i32 (global.get $global75)) + (global $global76 i32 (global.get $global75)) + ;; CHECK: (global $global77 i32 (global.get $global76)) + (global $global77 i32 (global.get $global76)) + ;; CHECK: (global $global78 i32 (global.get $global77)) + (global $global78 i32 (global.get $global77)) + ;; CHECK: (global $global79 i32 (global.get $global78)) + (global $global79 i32 (global.get $global78)) + ;; CHECK: (global $global80 i32 (global.get $global79)) + (global $global80 i32 (global.get $global79)) + ;; CHECK: (global $global81 i32 (global.get $global80)) + (global $global81 i32 (global.get $global80)) + ;; CHECK: (global $global82 i32 (global.get $global81)) + (global $global82 i32 (global.get $global81)) + ;; CHECK: (global $global83 i32 (global.get $global82)) + (global $global83 i32 (global.get $global82)) + ;; CHECK: (global $global84 i32 (global.get $global83)) + (global $global84 i32 (global.get $global83)) + ;; CHECK: (global $global85 i32 (global.get $global84)) + (global $global85 i32 (global.get $global84)) + ;; CHECK: (global $global86 i32 (global.get $global85)) + (global $global86 i32 (global.get $global85)) + ;; CHECK: (global $global87 i32 (global.get $global86)) + (global $global87 i32 (global.get $global86)) + ;; CHECK: (global $global88 i32 (global.get $global87)) + (global $global88 i32 (global.get $global87)) + ;; CHECK: (global $global89 i32 (global.get $global88)) + (global $global89 i32 (global.get $global88)) + ;; CHECK: (global $global90 i32 (global.get $global89)) + (global $global90 i32 (global.get $global89)) + ;; CHECK: (global $global91 i32 (global.get $global90)) + (global $global91 i32 (global.get $global90)) + ;; CHECK: (global $global92 i32 (global.get $global91)) + (global $global92 i32 (global.get $global91)) + ;; CHECK: (global $global93 i32 (global.get $global92)) + (global $global93 i32 (global.get $global92)) + ;; CHECK: (global $global94 i32 (global.get $global93)) + (global $global94 i32 (global.get $global93)) + ;; CHECK: (global $global95 i32 (global.get $global94)) + (global $global95 i32 (global.get $global94)) + ;; CHECK: (global $global96 i32 (global.get $global95)) + (global $global96 i32 (global.get $global95)) + ;; CHECK: (global $global97 i32 (global.get $global96)) + (global $global97 i32 (global.get $global96)) + ;; CHECK: (global $global98 i32 (global.get $global97)) + (global $global98 i32 (global.get $global97)) + ;; CHECK: (global $global99 i32 (global.get $global98)) + (global $global99 i32 (global.get $global98)) + ;; CHECK: (global $global100 i32 (global.get $global99)) + (global $global100 i32 (global.get $global99)) + ;; CHECK: (global $global101 i32 (global.get $global100)) + (global $global101 i32 (global.get $global100)) + ;; CHECK: (global $global102 i32 (global.get $global101)) + (global $global102 i32 (global.get $global101)) + ;; CHECK: (global $global103 i32 (global.get $global102)) + (global $global103 i32 (global.get $global102)) + ;; CHECK: (global $global104 i32 (global.get $global103)) + (global $global104 i32 (global.get $global103)) + ;; CHECK: (global $global105 i32 (global.get $global104)) + (global $global105 i32 (global.get $global104)) + ;; CHECK: (global $global106 i32 (global.get $global105)) + (global $global106 i32 (global.get $global105)) + ;; CHECK: (global $global107 i32 (global.get $global106)) + (global $global107 i32 (global.get $global106)) + ;; CHECK: (global $global108 i32 (global.get $global107)) + (global $global108 i32 (global.get $global107)) + ;; CHECK: (global $global109 i32 (global.get $global108)) + (global $global109 i32 (global.get $global108)) + ;; CHECK: (global $global110 i32 (global.get $global109)) + (global $global110 i32 (global.get $global109)) + ;; CHECK: (global $global111 i32 (global.get $global110)) + (global $global111 i32 (global.get $global110)) + ;; CHECK: (global $global112 i32 (global.get $global111)) + (global $global112 i32 (global.get $global111)) + ;; CHECK: (global $global113 i32 (global.get $global112)) + (global $global113 i32 (global.get $global112)) + ;; CHECK: (global $global114 i32 (global.get $global113)) + (global $global114 i32 (global.get $global113)) + ;; CHECK: (global $global115 i32 (global.get $global114)) + (global $global115 i32 (global.get $global114)) + ;; CHECK: (global $global116 i32 (global.get $global115)) + (global $global116 i32 (global.get $global115)) + ;; CHECK: (global $global117 i32 (global.get $global116)) + (global $global117 i32 (global.get $global116)) + ;; CHECK: (global $global118 i32 (global.get $global117)) + (global $global118 i32 (global.get $global117)) + ;; CHECK: (global $global119 i32 (global.get $global118)) + (global $global119 i32 (global.get $global118)) + ;; CHECK: (global $global120 i32 (global.get $global119)) + (global $global120 i32 (global.get $global119)) + ;; CHECK: (global $global121 i32 (global.get $global120)) + (global $global121 i32 (global.get $global120)) + ;; CHECK: (global $global122 i32 (global.get $global121)) + (global $global122 i32 (global.get $global121)) + ;; CHECK: (global $global123 i32 (global.get $global122)) + (global $global123 i32 (global.get $global122)) + ;; CHECK: (global $global124 i32 (global.get $global123)) + (global $global124 i32 (global.get $global123)) + ;; CHECK: (global $global125 i32 (global.get $global124)) + (global $global125 i32 (global.get $global124)) + ;; CHECK: (global $global126 i32 (global.get $global125)) + (global $global126 i32 (global.get $global125)) + ;; CHECK: (global $global127 i32 (global.get $global126)) + (global $global127 i32 (global.get $global126)) + ;; CHECK: (global $global128 i32 (global.get $global127)) + (global $global128 i32 (global.get $global127)) + + (global $other i32 (i32.const 0)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + (drop (global.get $other)) + (drop (global.get $other)) + ) +) + +;; As the last testcase, but one global fewer. As a result we only need a single +;; LEB byte for them all, and we do not bother changing the sort here. +(module + ;; CHECK: (global $global1 i32 (i32.const 1)) + (global $global1 i32 (i32.const 1)) + ;; CHECK: (global $global2 i32 (global.get $global1)) + (global $global2 i32 (global.get $global1)) + ;; CHECK: (global $global3 i32 (global.get $global2)) + (global $global3 i32 (global.get $global2)) + ;; CHECK: (global $global4 i32 (global.get $global3)) + (global $global4 i32 (global.get $global3)) + ;; CHECK: (global $global5 i32 (global.get $global4)) + (global $global5 i32 (global.get $global4)) + ;; CHECK: (global $global6 i32 (global.get $global5)) + (global $global6 i32 (global.get $global5)) + ;; CHECK: (global $global7 i32 (global.get $global6)) + (global $global7 i32 (global.get $global6)) + ;; CHECK: (global $global8 i32 (global.get $global7)) + (global $global8 i32 (global.get $global7)) + ;; CHECK: (global $global9 i32 (global.get $global8)) + (global $global9 i32 (global.get $global8)) + ;; CHECK: (global $global10 i32 (global.get $global9)) + (global $global10 i32 (global.get $global9)) + ;; CHECK: (global $global11 i32 (global.get $global10)) + (global $global11 i32 (global.get $global10)) + ;; CHECK: (global $global12 i32 (global.get $global11)) + (global $global12 i32 (global.get $global11)) + ;; CHECK: (global $global13 i32 (global.get $global12)) + (global $global13 i32 (global.get $global12)) + ;; CHECK: (global $global14 i32 (global.get $global13)) + (global $global14 i32 (global.get $global13)) + ;; CHECK: (global $global15 i32 (global.get $global14)) + (global $global15 i32 (global.get $global14)) + ;; CHECK: (global $global16 i32 (global.get $global15)) + (global $global16 i32 (global.get $global15)) + ;; CHECK: (global $global17 i32 (global.get $global16)) + (global $global17 i32 (global.get $global16)) + ;; CHECK: (global $global18 i32 (global.get $global17)) + (global $global18 i32 (global.get $global17)) + ;; CHECK: (global $global19 i32 (global.get $global18)) + (global $global19 i32 (global.get $global18)) + ;; CHECK: (global $global20 i32 (global.get $global19)) + (global $global20 i32 (global.get $global19)) + ;; CHECK: (global $global21 i32 (global.get $global20)) + (global $global21 i32 (global.get $global20)) + ;; CHECK: (global $global22 i32 (global.get $global21)) + (global $global22 i32 (global.get $global21)) + ;; CHECK: (global $global23 i32 (global.get $global22)) + (global $global23 i32 (global.get $global22)) + ;; CHECK: (global $global24 i32 (global.get $global23)) + (global $global24 i32 (global.get $global23)) + ;; CHECK: (global $global25 i32 (global.get $global24)) + (global $global25 i32 (global.get $global24)) + ;; CHECK: (global $global26 i32 (global.get $global25)) + (global $global26 i32 (global.get $global25)) + ;; CHECK: (global $global27 i32 (global.get $global26)) + (global $global27 i32 (global.get $global26)) + ;; CHECK: (global $global28 i32 (global.get $global27)) + (global $global28 i32 (global.get $global27)) + ;; CHECK: (global $global29 i32 (global.get $global28)) + (global $global29 i32 (global.get $global28)) + ;; CHECK: (global $global30 i32 (global.get $global29)) + (global $global30 i32 (global.get $global29)) + ;; CHECK: (global $global31 i32 (global.get $global30)) + (global $global31 i32 (global.get $global30)) + ;; CHECK: (global $global32 i32 (global.get $global31)) + (global $global32 i32 (global.get $global31)) + ;; CHECK: (global $global33 i32 (global.get $global32)) + (global $global33 i32 (global.get $global32)) + ;; CHECK: (global $global34 i32 (global.get $global33)) + (global $global34 i32 (global.get $global33)) + ;; CHECK: (global $global35 i32 (global.get $global34)) + (global $global35 i32 (global.get $global34)) + ;; CHECK: (global $global36 i32 (global.get $global35)) + (global $global36 i32 (global.get $global35)) + ;; CHECK: (global $global37 i32 (global.get $global36)) + (global $global37 i32 (global.get $global36)) + ;; CHECK: (global $global38 i32 (global.get $global37)) + (global $global38 i32 (global.get $global37)) + ;; CHECK: (global $global39 i32 (global.get $global38)) + (global $global39 i32 (global.get $global38)) + ;; CHECK: (global $global40 i32 (global.get $global39)) + (global $global40 i32 (global.get $global39)) + ;; CHECK: (global $global41 i32 (global.get $global40)) + (global $global41 i32 (global.get $global40)) + ;; CHECK: (global $global42 i32 (global.get $global41)) + (global $global42 i32 (global.get $global41)) + ;; CHECK: (global $global43 i32 (global.get $global42)) + (global $global43 i32 (global.get $global42)) + ;; CHECK: (global $global44 i32 (global.get $global43)) + (global $global44 i32 (global.get $global43)) + ;; CHECK: (global $global45 i32 (global.get $global44)) + (global $global45 i32 (global.get $global44)) + ;; CHECK: (global $global46 i32 (global.get $global45)) + (global $global46 i32 (global.get $global45)) + ;; CHECK: (global $global47 i32 (global.get $global46)) + (global $global47 i32 (global.get $global46)) + ;; CHECK: (global $global48 i32 (global.get $global47)) + (global $global48 i32 (global.get $global47)) + ;; CHECK: (global $global49 i32 (global.get $global48)) + (global $global49 i32 (global.get $global48)) + ;; CHECK: (global $global50 i32 (global.get $global49)) + (global $global50 i32 (global.get $global49)) + ;; CHECK: (global $global51 i32 (global.get $global50)) + (global $global51 i32 (global.get $global50)) + ;; CHECK: (global $global52 i32 (global.get $global51)) + (global $global52 i32 (global.get $global51)) + ;; CHECK: (global $global53 i32 (global.get $global52)) + (global $global53 i32 (global.get $global52)) + ;; CHECK: (global $global54 i32 (global.get $global53)) + (global $global54 i32 (global.get $global53)) + ;; CHECK: (global $global55 i32 (global.get $global54)) + (global $global55 i32 (global.get $global54)) + ;; CHECK: (global $global56 i32 (global.get $global55)) + (global $global56 i32 (global.get $global55)) + ;; CHECK: (global $global57 i32 (global.get $global56)) + (global $global57 i32 (global.get $global56)) + ;; CHECK: (global $global58 i32 (global.get $global57)) + (global $global58 i32 (global.get $global57)) + ;; CHECK: (global $global59 i32 (global.get $global58)) + (global $global59 i32 (global.get $global58)) + ;; CHECK: (global $global60 i32 (global.get $global59)) + (global $global60 i32 (global.get $global59)) + ;; CHECK: (global $global61 i32 (global.get $global60)) + (global $global61 i32 (global.get $global60)) + ;; CHECK: (global $global62 i32 (global.get $global61)) + (global $global62 i32 (global.get $global61)) + ;; CHECK: (global $global63 i32 (global.get $global62)) + (global $global63 i32 (global.get $global62)) + ;; CHECK: (global $global64 i32 (global.get $global63)) + (global $global64 i32 (global.get $global63)) + ;; CHECK: (global $global65 i32 (global.get $global64)) + (global $global65 i32 (global.get $global64)) + ;; CHECK: (global $global66 i32 (global.get $global65)) + (global $global66 i32 (global.get $global65)) + ;; CHECK: (global $global67 i32 (global.get $global66)) + (global $global67 i32 (global.get $global66)) + ;; CHECK: (global $global68 i32 (global.get $global67)) + (global $global68 i32 (global.get $global67)) + ;; CHECK: (global $global69 i32 (global.get $global68)) + (global $global69 i32 (global.get $global68)) + ;; CHECK: (global $global70 i32 (global.get $global69)) + (global $global70 i32 (global.get $global69)) + ;; CHECK: (global $global71 i32 (global.get $global70)) + (global $global71 i32 (global.get $global70)) + ;; CHECK: (global $global72 i32 (global.get $global71)) + (global $global72 i32 (global.get $global71)) + ;; CHECK: (global $global73 i32 (global.get $global72)) + (global $global73 i32 (global.get $global72)) + ;; CHECK: (global $global74 i32 (global.get $global73)) + (global $global74 i32 (global.get $global73)) + ;; CHECK: (global $global75 i32 (global.get $global74)) + (global $global75 i32 (global.get $global74)) + ;; CHECK: (global $global76 i32 (global.get $global75)) + (global $global76 i32 (global.get $global75)) + ;; CHECK: (global $global77 i32 (global.get $global76)) + (global $global77 i32 (global.get $global76)) + ;; CHECK: (global $global78 i32 (global.get $global77)) + (global $global78 i32 (global.get $global77)) + ;; CHECK: (global $global79 i32 (global.get $global78)) + (global $global79 i32 (global.get $global78)) + ;; CHECK: (global $global80 i32 (global.get $global79)) + (global $global80 i32 (global.get $global79)) + ;; CHECK: (global $global81 i32 (global.get $global80)) + (global $global81 i32 (global.get $global80)) + ;; CHECK: (global $global82 i32 (global.get $global81)) + (global $global82 i32 (global.get $global81)) + ;; CHECK: (global $global83 i32 (global.get $global82)) + (global $global83 i32 (global.get $global82)) + ;; CHECK: (global $global84 i32 (global.get $global83)) + (global $global84 i32 (global.get $global83)) + ;; CHECK: (global $global85 i32 (global.get $global84)) + (global $global85 i32 (global.get $global84)) + ;; CHECK: (global $global86 i32 (global.get $global85)) + (global $global86 i32 (global.get $global85)) + ;; CHECK: (global $global87 i32 (global.get $global86)) + (global $global87 i32 (global.get $global86)) + ;; CHECK: (global $global88 i32 (global.get $global87)) + (global $global88 i32 (global.get $global87)) + ;; CHECK: (global $global89 i32 (global.get $global88)) + (global $global89 i32 (global.get $global88)) + ;; CHECK: (global $global90 i32 (global.get $global89)) + (global $global90 i32 (global.get $global89)) + ;; CHECK: (global $global91 i32 (global.get $global90)) + (global $global91 i32 (global.get $global90)) + ;; CHECK: (global $global92 i32 (global.get $global91)) + (global $global92 i32 (global.get $global91)) + ;; CHECK: (global $global93 i32 (global.get $global92)) + (global $global93 i32 (global.get $global92)) + ;; CHECK: (global $global94 i32 (global.get $global93)) + (global $global94 i32 (global.get $global93)) + ;; CHECK: (global $global95 i32 (global.get $global94)) + (global $global95 i32 (global.get $global94)) + ;; CHECK: (global $global96 i32 (global.get $global95)) + (global $global96 i32 (global.get $global95)) + ;; CHECK: (global $global97 i32 (global.get $global96)) + (global $global97 i32 (global.get $global96)) + ;; CHECK: (global $global98 i32 (global.get $global97)) + (global $global98 i32 (global.get $global97)) + ;; CHECK: (global $global99 i32 (global.get $global98)) + (global $global99 i32 (global.get $global98)) + ;; CHECK: (global $global100 i32 (global.get $global99)) + (global $global100 i32 (global.get $global99)) + ;; CHECK: (global $global101 i32 (global.get $global100)) + (global $global101 i32 (global.get $global100)) + ;; CHECK: (global $global102 i32 (global.get $global101)) + (global $global102 i32 (global.get $global101)) + ;; CHECK: (global $global103 i32 (global.get $global102)) + (global $global103 i32 (global.get $global102)) + ;; CHECK: (global $global104 i32 (global.get $global103)) + (global $global104 i32 (global.get $global103)) + ;; CHECK: (global $global105 i32 (global.get $global104)) + (global $global105 i32 (global.get $global104)) + ;; CHECK: (global $global106 i32 (global.get $global105)) + (global $global106 i32 (global.get $global105)) + ;; CHECK: (global $global107 i32 (global.get $global106)) + (global $global107 i32 (global.get $global106)) + ;; CHECK: (global $global108 i32 (global.get $global107)) + (global $global108 i32 (global.get $global107)) + ;; CHECK: (global $global109 i32 (global.get $global108)) + (global $global109 i32 (global.get $global108)) + ;; CHECK: (global $global110 i32 (global.get $global109)) + (global $global110 i32 (global.get $global109)) + ;; CHECK: (global $global111 i32 (global.get $global110)) + (global $global111 i32 (global.get $global110)) + ;; CHECK: (global $global112 i32 (global.get $global111)) + (global $global112 i32 (global.get $global111)) + ;; CHECK: (global $global113 i32 (global.get $global112)) + (global $global113 i32 (global.get $global112)) + ;; CHECK: (global $global114 i32 (global.get $global113)) + (global $global114 i32 (global.get $global113)) + ;; CHECK: (global $global115 i32 (global.get $global114)) + (global $global115 i32 (global.get $global114)) + ;; CHECK: (global $global116 i32 (global.get $global115)) + (global $global116 i32 (global.get $global115)) + ;; CHECK: (global $global117 i32 (global.get $global116)) + (global $global117 i32 (global.get $global116)) + ;; CHECK: (global $global118 i32 (global.get $global117)) + (global $global118 i32 (global.get $global117)) + ;; CHECK: (global $global119 i32 (global.get $global118)) + (global $global119 i32 (global.get $global118)) + ;; CHECK: (global $global120 i32 (global.get $global119)) + (global $global120 i32 (global.get $global119)) + ;; CHECK: (global $global121 i32 (global.get $global120)) + (global $global121 i32 (global.get $global120)) + ;; CHECK: (global $global122 i32 (global.get $global121)) + (global $global122 i32 (global.get $global121)) + ;; CHECK: (global $global123 i32 (global.get $global122)) + (global $global123 i32 (global.get $global122)) + ;; CHECK: (global $global124 i32 (global.get $global123)) + (global $global124 i32 (global.get $global123)) + ;; CHECK: (global $global125 i32 (global.get $global124)) + (global $global125 i32 (global.get $global124)) + ;; CHECK: (global $global126 i32 (global.get $global125)) + (global $global126 i32 (global.get $global125)) + ;; CHECK: (global $global127 i32 (global.get $global126)) + (global $global127 i32 (global.get $global126)) + + ;; $global128 was removed + + ;; CHECK: (global $other i32 (i32.const 0)) + (global $other i32 (i32.const 0)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + (drop (global.get $other)) + (drop (global.get $other)) + ) +) diff --git a/test/lit/passes/reorder-globals.wast b/test/lit/passes/reorder-globals.wast index 6017f09ad..542311d59 100644 --- a/test/lit/passes/reorder-globals.wast +++ b/test/lit/passes/reorder-globals.wast @@ -145,8 +145,6 @@ ;; As above, but without dependencies, so now $c is first and then $b. (module - - ;; CHECK: (global $c i32 (i32.const 30)) ;; CHECK: (global $b i32 (i32.const 20)) @@ -180,10 +178,10 @@ ) ) -;; As above, but a mixed case: $b depends on $a but $c has no dependencies. $c -;; can be first. +;; As above, but a mixed case: $b depends on $a but $c has no dependencies, and +;; the counts are $c with the most, followed by $b, and then $a. $c can be +;; first here, but $b must follow $a. (module - ;; CHECK: (global $c i32 (i32.const 30)) ;; CHECK: (global $a i32 (i32.const 10)) @@ -197,6 +195,12 @@ ;; CHECK-NEXT: (global.get $b) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (global.get $c) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop @@ -204,6 +208,10 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $uses + ;; ($a already has one use in the global $b) + (drop + (global.get $b) + ) (drop (global.get $b) ) @@ -213,27 +221,111 @@ (drop (global.get $c) ) + (drop + (global.get $c) + ) ) ) -;; Another mixed case, now with $c depending on $b. $b can be before $a. +;; As above, but with the counts adjusted: before we had $c, $b, $a from most to +;; least uses, and now $b, $c, $a. +;; +;; A greedy sort would do $c, $a, $b (as the first choice is between $c and $a, +;; and $c wins), but that leaves $b, the highest count, for the end. The +;; smoothed-out LEB costs (1 byte at the start, +1/128 each index later) are: +;; +;; $c $a $b +;; 1 * 2 + 129/128 * 1 + 130/128 * 3 = 775/128 +;; +;; The original sort is +;; +;; $a $b $c +;; 1 * 1 + 129/128 * 3 + 130/128 * 2 = 775/128 +;; +;; As they are equal we prefer the original order. (module + ;; CHECK: (global $a i32 (i32.const 10)) + (global $a i32 (i32.const 10)) + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + ;; CHECK: (global $c i32 (i32.const 30)) + (global $c i32 (i32.const 30)) + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + (drop + (global.get $b) + ) + (drop + (global.get $b) + ) + (drop + (global.get $b) + ) + (drop + (global.get $c) + ) + (drop + (global.get $c) + ) + ) +) - ;; CHECK: (global $b i32 (i32.const 20)) - - ;; CHECK: (global $c i32 (global.get $b)) - +;; As above, but with the counts adjusted to $b, $a, $c. +(module ;; CHECK: (global $a i32 (i32.const 10)) (global $a i32 (i32.const 10)) - (global $b i32 (i32.const 20)) - (global $c i32 (global.get $b)) + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + ;; CHECK: (global $c i32 (i32.const 30)) + (global $c i32 (i32.const 30)) ;; CHECK: (func $uses (type $0) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (global.get $b) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + (drop + (global.get $b) + ) + (drop + (global.get $b) + ) + ) +) + +;; As above, but with the counts adjusted to $c, $a, $b. +(module + ;; CHECK: (global $c i32 (i32.const 30)) + + ;; CHECK: (global $a i32 (i32.const 10)) + (global $a i32 (i32.const 10)) + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + (global $c i32 (i32.const 30)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (global.get $c) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop @@ -242,11 +334,63 @@ ;; CHECK-NEXT: ) (func $uses (drop - (global.get $b) + (global.get $c) ) (drop (global.get $c) ) + ) +) + +;; As above, but with the counts adjusted to $a, $b, $c. +(module + ;; CHECK: (global $a i32 (i32.const 10)) + (global $a i32 (i32.const 10)) + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + ;; CHECK: (global $c i32 (i32.const 30)) + (global $c i32 (i32.const 30)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $a) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + (drop + (global.get $a) + ) + (drop + (global.get $b) + ) + ) +) + +;; As above, but with the counts adjusted to $a, $c, $b. +(module + ;; CHECK: (global $a i32 (i32.const 10)) + (global $a i32 (i32.const 10)) + ;; CHECK: (global $c i32 (i32.const 30)) + + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + (global $c i32 (i32.const 30)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $a) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + (drop + (global.get $a) + ) (drop (global.get $c) ) @@ -292,3 +436,380 @@ ) ) ) + +;; Lower letters have lower counts: $a has the least, and $e has the most. +;; +;; Dependency graph (left depends on right): +;; +;; $c - $a +;; / +;; $e +;; \ +;; $d - $b +;; +;; $e has the most uses, followed by $c and $d. $a and $b have a reverse +;; ordering from their dependers, so a naive topological sort will fail to +;; be optimal. There are multiple optimal orders however, including: +;; +;; $b, $a, $c, $d, $e +;; $b, $d, $a, $c, $e +;; +;; $b and $e must be at the edges, but there is no single way to sort the +;; others: the first sorting here puts $a before both $d (though $a has +;; lower count) while the second puts $d before $c. Our greedy algorithm +;; picks the second order here. +(module + ;; CHECK: (global $b i32 (i32.const 20)) + + ;; CHECK: (global $d i32 (global.get $b)) + + ;; CHECK: (global $a i32 (i32.const 10)) + (global $a i32 (i32.const 10)) + + (global $b i32 (i32.const 20)) + + ;; CHECK: (global $c i32 (global.get $a)) + (global $c i32 (global.get $a)) + + (global $d i32 (global.get $b)) + + ;; CHECK: (global $e i32 (i32.add + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: )) + (global $e i32 (i32.add + (global.get $c) + (global.get $d) + )) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + ;; $a, $b, $c, $d each have one already from the globals. Add more so that + ;; $a has the least, and $e has the most + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + + (drop (global.get $d)) + (drop (global.get $d)) + (drop (global.get $d)) + + (drop (global.get $c)) + (drop (global.get $c)) + + (drop (global.get $b)) + ) +) + +;; As above, but add a direct dep from $d to $a: +;; +;; $c - $a +;; / / +;; $e / <-- this was added +;; \ / +;; $d - $b +;; +;; This forces $a to appear before $d: the order goes from before, which was +;; $b, $d, $a, $c, $e +;; to +;; $b, $a, $d, $c, $e +(module + ;; CHECK: (global $b i32 (i32.const 20)) + + ;; CHECK: (global $a i32 (i32.const 10)) + (global $a i32 (i32.const 10)) + + (global $b i32 (i32.const 20)) + + ;; CHECK: (global $d i32 (i32.add + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: (global.get $a) + ;; CHECK-NEXT: )) + + ;; CHECK: (global $c i32 (global.get $a)) + (global $c i32 (global.get $a)) + + (global $d i32 (i32.add + (global.get $b) + (global.get $a) ;; this was added + )) + + ;; CHECK: (global $e i32 (i32.add + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: )) + (global $e i32 (i32.add + (global.get $c) + (global.get $d) + )) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $e) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $d) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + ;; $b, $c, $d each have one already from the globals, and $a has two. Add + ;; more so that $a has the least, and $e has the most. + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + (drop (global.get $e)) + + (drop (global.get $d)) + (drop (global.get $d)) + (drop (global.get $d)) + (drop (global.get $d)) + + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + + (drop (global.get $b)) + (drop (global.get $b)) + ) +) + +;; A situation where the simple greedy sort fails to be optimal. We have a +;; chain and one more independent global +;; +;; a <- b <- c +;; +;; other +;; +;; The candidates for the first global emitted are a and other, as they have no +;; dependencies, and other has a higher count so greedy sorting would pick it. +;; however, c has the highest count by far, so it is worth being less greedy and +;; doing a just in order to be able to do b and then c, and to emit other last. +;; In other words, the original order is best. +(module + ;; CHECK: (global $a i32 (i32.const 0)) + (global $a i32 (i32.const 0)) + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + ;; CHECK: (global $c i32 (global.get $b)) + (global $c i32 (global.get $b)) + + ;; CHECK: (global $other i32 (i32.const 1)) + (global $other i32 (i32.const 1)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + ;; Ten uses for $c, far more than all the rest combined. + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + + ;; Two uses for other, which is more than $a's single use. + (drop (global.get $other)) + (drop (global.get $other)) + ) +) + +;; As above, but with the original order a little different. This is again a +;; case where the greedy sort is unoptimal (see above), but now also the +;; original sort is unoptimal as well, and instead we use the "sum" sort, which +;; counts the sum of the uses of a global and all the things it depends on and +;; uses that as the count for that global (which in effect means that we take +;; into consideration not only its own size but the entire size that it may +;; unlock, which happens to work well here). +;; +;; The only change in the input compared to the previous test is that $other +;; was moved up to between $b and $c. Sum sort works well here because the +;; first comparison is $a and $other, and sum takes into account $b and $c in +;; $a's favor, so it wins. Likewise $b and $c win against $other as well, so +;; the order is $a, $b, $c, $other which is optimal here. +(module + ;; CHECK: (global $a i32 (i32.const 0)) + (global $a i32 (i32.const 0)) + ;; CHECK: (global $b i32 (global.get $a)) + (global $b i32 (global.get $a)) + + ;; CHECK: (global $c i32 (global.get $b)) + + ;; CHECK: (global $other i32 (i32.const 1)) + (global $other i32 (i32.const 1)) + + (global $c i32 (global.get $b)) + + ;; CHECK: (func $uses (type $0) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $c) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $other) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $uses + ;; Ten uses for $c, far more than all the rest combined. + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + (drop (global.get $c)) + + ;; Two uses for other, which is more than $a's single use. + (drop (global.get $other)) + (drop (global.get $other)) + ) +) + |