summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/passes/Outlining.cpp52
-rw-r--r--src/passes/hash-stringify-walker.cpp6
-rw-r--r--test/gtest/stringify.cpp2
-rw-r--r--test/lit/passes/outlining.wast239
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: )
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-07 23:14:55 +0000