diff options
-rw-r--r-- | src/passes/Outlining.cpp | 52 | ||||
-rw-r--r-- | src/passes/hash-stringify-walker.cpp | 6 | ||||
-rw-r--r-- | test/gtest/stringify.cpp | 2 | ||||
-rw-r--r-- | test/lit/passes/outlining.wast | 239 |
4 files changed, 234 insertions, 65 deletions
diff --git a/src/passes/Outlining.cpp b/src/passes/Outlining.cpp index 4bb883187..c7644c339 100644 --- a/src/passes/Outlining.cpp +++ b/src/passes/Outlining.cpp @@ -1,3 +1,19 @@ +/* + * Copyright 2023 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + #include "ir/names.h" #include "ir/utils.h" #include "pass.h" @@ -246,6 +262,9 @@ struct Outlining : public Pass { // relative to the entire program. auto sequences = makeSequences(module, substrings, stringify); outline(module, sequences); + // Position the outlined functions first in the functions vector to make + // the outlining lit tests far more readable. + moveOutlinedFunctions(module, substrings.size()); } Name addOutlinedFunction(Module* module, @@ -253,17 +272,16 @@ struct Outlining : public Pass { const std::vector<Expression*>& exprs) { auto startIdx = substring.StartIndices[0]; // The outlined functions can be named anything. - Name outlinedFunc = - Names::getValidFunctionName(*module, std::string("outline$")); + Name func = Names::getValidFunctionName(*module, std::string("outline$")); // Calculate the function signature for the outlined sequence. StackSignature sig; for (uint32_t exprIdx = startIdx; exprIdx < startIdx + substring.Length; exprIdx++) { sig += StackSignature(exprs[exprIdx]); } - module->addFunction(Builder::makeFunction( - outlinedFunc, Signature(sig.params, sig.results), {})); - return outlinedFunc; + module->addFunction( + Builder::makeFunction(func, Signature(sig.params, sig.results), {})); + return func; } using Sequences = @@ -278,15 +296,14 @@ struct Outlining : public Pass { const HashStringifyWalker& stringify) { Sequences seqByFunc; for (auto& substring : substrings) { - Name outlinedFunc = - addOutlinedFunction(module, substring, stringify.exprs); + auto func = addOutlinedFunction(module, substring, stringify.exprs); for (auto seqIdx : substring.StartIndices) { // seqIdx is relative to the entire program; making the idx of the // sequence relative to its function is better for outlining because we // walk functions. auto [relativeIdx, existingFunc] = stringify.makeRelative(seqIdx); - auto seq = OutliningSequence( - relativeIdx, relativeIdx + substring.Length, outlinedFunc); + auto seq = + OutliningSequence(relativeIdx, relativeIdx + substring.Length, func); seqByFunc[existingFunc].push_back(seq); } } @@ -307,6 +324,23 @@ struct Outlining : public Pass { } } + void moveOutlinedFunctions(Module* module, uint32_t outlinedCount) { + // Rearrange outlined functions to the beginning of the functions vector by + // using std::make_move_iterator to avoid making copies. A temp vector is + // created to avoid iterator invalidation. + auto count = module->functions.size(); + std::vector<std::unique_ptr<Function>> temp( + std::make_move_iterator(module->functions.end() - outlinedCount), + std::make_move_iterator(module->functions.end())); + module->functions.insert(module->functions.begin(), + std::make_move_iterator(temp.begin()), + std::make_move_iterator(temp.end())); + module->functions.resize(count); + // After the functions vector is directly manipulated, we need to call + // updateFunctionsMap(). + module->updateFunctionsMap(); + } + #if OUTLINING_DEBUG void printHashString(const std::vector<uint32_t>& hashString, const std::vector<Expression*>& exprs) { diff --git a/src/passes/hash-stringify-walker.cpp b/src/passes/hash-stringify-walker.cpp index 5afd50ef4..c9173c6a5 100644 --- a/src/passes/hash-stringify-walker.cpp +++ b/src/passes/hash-stringify-walker.cpp @@ -86,11 +86,9 @@ std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::repeatSubstrings(std::vector<uint32_t>& hashString) { SuffixTree st(hashString); std::vector<SuffixTree::RepeatedSubstring> substrings(st.begin(), st.end()); - for (auto substring : substrings) { + for (auto& substring : substrings) { // Sort by increasing start index to ensure determinism. - std::sort(substring.StartIndices.begin(), - substring.StartIndices.end(), - [](uint32_t a, uint32_t b) { return a < b; }); + std::sort(substring.StartIndices.begin(), substring.StartIndices.end()); } // Substrings are sorted so that the longest substring that repeats the most // times is ordered first. This is done so that we can assume the most diff --git a/test/gtest/stringify.cpp b/test/gtest/stringify.cpp index 59b7db6e1..3e50c6d4c 100644 --- a/test/gtest/stringify.cpp +++ b/test/gtest/stringify.cpp @@ -266,7 +266,7 @@ TEST_F(StringifyTest, Substrings) { // 10, 11, 6 appears at idx 18 and again at 27 SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{23, 34})}, // 11, 6 appears at idx 32, 19 and again at 28 - SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{40, 24, 35})}, + SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{24, 35, 40})}, // 7, 6 appears at idx 11 and again at 24 SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{14, 30})}})); } diff --git a/test/lit/passes/outlining.wast b/test/lit/passes/outlining.wast index d62570c11..ffd5eb081 100644 --- a/test/lit/passes/outlining.wast +++ b/test/lit/passes/outlining.wast @@ -2,9 +2,7 @@ ;; RUN: foreach %s %t wasm-opt --outlining -S -o - | filecheck %s -;; TODO: Add a test that creates an outlined function with a sequence at beginning ;; TODO: Add a test that creates an outlined function with one return value -;; TODO: Add a test that creates an outlined function that no arguments ;; TODO: Add a test that creates an outlined function that returns multiple values ;; TODO: Add a test that makes sure we filter localSets correctly ;; TODO: Add a test that makes sure we filter localGets correctly @@ -18,6 +16,18 @@ ;; CHECK: (type $1 (func (param i32))) + ;; CHECK: (func $outline$ (param $0 i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK: (func $a (result i32) ;; CHECK-NEXT: (call $outline$ ;; CHECK-NEXT: (i32.const 7) @@ -27,10 +37,18 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $a (result i32) - (drop (i32.const 7)) - (drop (i32.const 1)) - (drop (i32.const 2)) - (return (i32.const 4)) + (drop + (i32.const 7) + ) + (drop + (i32.const 1) + ) + (drop + (i32.const 2) + ) + (return + (i32.const 4) + ) ) ;; CHECK: (func $b (result i32) ;; CHECK-NEXT: (call $outline$ @@ -41,68 +59,187 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $b (result i32) - (drop (i32.const 0)) - (drop (i32.const 1)) - (drop (i32.const 2)) - (return (i32.const 5)) + (drop + (i32.const 0) + ) + (drop + (i32.const 1) + ) + (drop + (i32.const 2) + ) + (return + (i32.const 5) + ) ) ) ;; Tests that outlining occurs properly when the sequence is at the end of a function. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (func $outline$ + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + + ;; CHECK: (func $c + ;; CHECK-NEXT: (call $outline$) + ;; CHECK-NEXT: ) + (func $c + (drop + (i32.const 1) + ) + (drop + (i32.const 2) + ) + ) + ;; CHECK: (func $d + ;; CHECK-NEXT: (call $outline$) + ;; CHECK-NEXT: ) + (func $d + (drop + (i32.const 1) + ) + (drop + (i32.const 2) + ) + ) +) -;; CHECK: (func $outline$ (param $0 i32) -;; CHECK-NEXT: (drop -;; CHECK-NEXT: (local.get $0) -;; CHECK-NEXT: ) -;; CHECK-NEXT: (drop -;; CHECK-NEXT: (i32.const 1) -;; CHECK-NEXT: ) -;; CHECK-NEXT: (drop -;; CHECK-NEXT: (i32.const 2) -;; CHECK-NEXT: ) -;; CHECK-NEXT: ) +;; Tests that outlining occurs properly when the sequence is at the beginning of a function. +;; Also tests that the outlined function has no arguments. (module ;; CHECK: (type $0 (func)) - ;; CHECK: (type $1 (func (param i32))) + ;; CHECK: (func $outline$ + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) - ;; CHECK: (func $a + ;; CHECK: (func $e + ;; CHECK-NEXT: (call $outline$) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (i32.const 7) + ;; CHECK-NEXT: (i32.const 6) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (call $outline$ - ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: ) + (func $e + (drop + (i32.const 0) + ) + (drop + (i32.add + (i32.const 0) + (i32.const 1) + ) + ) + (drop + (i32.const 1) + ) + (drop + (i32.const 6) + ) + ) + ;; CHECK: (func $f + ;; CHECK-NEXT: (call $outline$) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 7) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) - (func $a - (drop (i32.const 7)) - (drop (i32.const 4)) - (drop (i32.const 1)) - (drop (i32.const 2)) + (func $f + (drop + (i32.const 0) + ) + (drop + (i32.add + (i32.const 0) + (i32.const 1) + ) + ) + (drop + (i32.const 1) + ) + (drop + (i32.const 7) + ) ) - ;; CHECK: (func $b +) + +;; Tests multiple sequences being outlined from the same source function into different +;; outlined functions. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (func $outline$ ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (call $outline$ - ;; CHECK-NEXT: (i32.const 5) + ;; CHECK-NEXT: ) + + ;; CHECK: (func $outline$_4 + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.sub + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) - (func $b - (drop (i32.const 0)) - (drop (i32.const 5)) - (drop (i32.const 1)) - (drop (i32.const 2)) + + ;; CHECK: (func $g + ;; CHECK-NEXT: (call $outline$) + ;; CHECK-NEXT: (call $outline$_4) + ;; CHECK-NEXT: ) + (func $g + (drop + (i32.add + (i32.const 0) + (i32.const 1) + ) + ) + (drop + (i32.sub + (i32.const 3) + (i32.const 4) + ) + ) + ) + ;; CHECK: (func $h + ;; CHECK-NEXT: (call $outline$_4) + ;; CHECK-NEXT: ) + (func $h + (drop + (i32.sub + (i32.const 3) + (i32.const 4) + ) + ) + ) + ;; CHECK: (func $i + ;; CHECK-NEXT: (call $outline$) + ;; CHECK-NEXT: ) + (func $i + (drop + (i32.add + (i32.const 0) + (i32.const 1) + ) + ) ) ) -;; CHECK: (func $outline$ (param $0 i32) -;; CHECK-NEXT: (drop -;; CHECK-NEXT: (local.get $0) -;; CHECK-NEXT: ) -;; CHECK-NEXT: (drop -;; CHECK-NEXT: (i32.const 1) -;; CHECK-NEXT: ) -;; CHECK-NEXT: (drop -;; CHECK-NEXT: (i32.const 2) -;; CHECK-NEXT: ) -;; CHECK-NEXT: ) |