summaryrefslogtreecommitdiff
path: root/src/ir/stack-utils.cpp
diff options
context:
space:
mode:
authorThomas Lively <7121787+tlively@users.noreply.github.com>2020-09-07 18:29:33 -0700
committerGitHub <noreply@github.com>2020-09-07 18:29:33 -0700
commita6816a287bd3f802cb6db51032e77145f036c8b7 (patch)
tree2b13779744aa126688055095bb1c747dc786f265 /src/ir/stack-utils.cpp
parent775363a98002a14c64bdc4f8d591c6f37b1e1604 (diff)
downloadbinaryen-a6816a287bd3f802cb6db51032e77145f036c8b7.tar.gz
binaryen-a6816a287bd3f802cb6db51032e77145f036c8b7.tar.bz2
binaryen-a6816a287bd3f802cb6db51032e77145f036c8b7.zip
Stack utils (#3083)
Implement and test utilities for manipulating and analyzing a new stacky form of Binaryen IR that is able to express arbitrary stack machine code. This new Poppy IR will eventually replace Stack IR, and new optimization passes will be built with these utilities. See #3059.
Diffstat (limited to 'src/ir/stack-utils.cpp')
-rw-r--r--src/ir/stack-utils.cpp292
1 files changed, 292 insertions, 0 deletions
diff --git a/src/ir/stack-utils.cpp b/src/ir/stack-utils.cpp
new file mode 100644
index 000000000..ef871040b
--- /dev/null
+++ b/src/ir/stack-utils.cpp
@@ -0,0 +1,292 @@
+/*
+ * Copyright 2020 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 "stack-utils.h"
+
+namespace wasm {
+
+namespace StackUtils {
+
+void removeNops(Block* block) {
+ size_t newIndex = 0;
+ for (size_t i = 0, size = block->list.size(); i < size; ++i) {
+ if (!block->list[i]->is<Nop>()) {
+ block->list[newIndex++] = block->list[i];
+ }
+ }
+ block->list.resize(newIndex);
+}
+
+} // namespace StackUtils
+
+StackSignature::StackSignature(Expression* expr) {
+ params = Type::none;
+ if (Properties::isControlFlowStructure(expr)) {
+ if (expr->is<If>()) {
+ params = Type::i32;
+ }
+ } else {
+ std::vector<Type> inputs;
+ for (auto* child : ChildIterator(expr)) {
+ assert(child->type.isConcrete());
+ // Children might be tuple pops, so expand their types
+ inputs.insert(inputs.end(), child->type.begin(), child->type.end());
+ }
+ params = Type(inputs);
+ }
+ if (expr->type == Type::unreachable) {
+ unreachable = true;
+ results = Type::none;
+ } else {
+ unreachable = false;
+ results = expr->type;
+ }
+}
+
+bool StackSignature::composes(const StackSignature& next) const {
+ auto checked = std::min(results.size(), next.params.size());
+ return std::equal(results.end() - checked,
+ results.end(),
+ next.params.end() - checked,
+ [](const Type& produced, const Type& consumed) {
+ return Type::isSubType(produced, consumed);
+ });
+}
+
+bool StackSignature::satisfies(Signature sig) const {
+ if (sig.params.size() < params.size() ||
+ sig.results.size() < results.size()) {
+ // Not enough values provided or too many produced
+ return false;
+ }
+ bool paramSuffixMatches =
+ std::equal(params.begin(),
+ params.end(),
+ sig.params.end() - params.size(),
+ [](const Type& consumed, const Type& provided) {
+ return Type::isSubType(provided, consumed);
+ });
+ if (!paramSuffixMatches) {
+ return false;
+ }
+ bool resultSuffixMatches =
+ std::equal(results.begin(),
+ results.end(),
+ sig.results.end() - results.size(),
+ [](const Type& produced, const Type& expected) {
+ return Type::isSubType(produced, expected);
+ });
+ if (!resultSuffixMatches) {
+ return false;
+ }
+ if (unreachable) {
+ // The unreachable can consume any additional provided params and produce
+ // any additional expected results, so we are done.
+ return true;
+ }
+ // Any additional provided params will pass through untouched, so they must be
+ // equivalent to the additional produced results.
+ return std::equal(sig.params.begin(),
+ sig.params.end() - params.size(),
+ sig.results.begin(),
+ sig.results.end() - results.size(),
+ [](const Type& produced, const Type& expected) {
+ return Type::isSubType(produced, expected);
+ });
+}
+
+StackSignature& StackSignature::operator+=(const StackSignature& next) {
+ assert(composes(next));
+ std::vector<Type> stack(results.begin(), results.end());
+ size_t required = next.params.size();
+ // Consume stack values according to next's parameters
+ if (stack.size() >= required) {
+ stack.resize(stack.size() - required);
+ } else {
+ if (!unreachable) {
+ // Prepend the unsatisfied params of `next` to the current params
+ size_t unsatisfied = required - stack.size();
+ std::vector<Type> newParams(next.params.begin(),
+ next.params.begin() + unsatisfied);
+ newParams.insert(newParams.end(), params.begin(), params.end());
+ params = Type(newParams);
+ }
+ stack.clear();
+ }
+ // Add stack values according to next's results
+ if (next.unreachable) {
+ results = next.results;
+ unreachable = true;
+ } else {
+ stack.insert(stack.end(), next.results.begin(), next.results.end());
+ results = Type(stack);
+ }
+ return *this;
+}
+
+StackSignature StackSignature::operator+(const StackSignature& next) const {
+ StackSignature sig = *this;
+ sig += next;
+ return sig;
+}
+
+StackFlow::StackFlow(Block* block) {
+ // Encapsulates the logic for treating the block and its children
+ // uniformly. The end of the block is treated as if it consumed values
+ // corresponding to the its result type and produced no values, which is why
+ // the block's result type is used as the params of its processed stack
+ // signature.
+ auto processBlock = [&block](auto process) {
+ // TODO: Once we support block parameters, set up the stack by calling
+ // `process` before iterating through the block.
+ for (auto* expr : block->list) {
+ process(expr, StackSignature(expr));
+ }
+ bool unreachable = block->type == Type::unreachable;
+ Type params = unreachable ? Type::none : block->type;
+ process(block, StackSignature(params, Type::none, unreachable));
+ };
+
+ // We need to make an initial pass through the block to figure out how many
+ // values each unreachable instruction produces.
+ std::unordered_map<Expression*, size_t> producedByUnreachable;
+ {
+ size_t stackSize = 0;
+ size_t produced = 0;
+ Expression* lastUnreachable = nullptr;
+ processBlock([&](Expression* expr, const StackSignature sig) {
+ // Consume params
+ if (sig.params.size() > stackSize) {
+ // We need more values than are available, so they must come from the
+ // last unreachable.
+ assert(lastUnreachable);
+ produced += sig.params.size() - stackSize;
+ stackSize = 0;
+ } else {
+ stackSize -= sig.params.size();
+ }
+
+ // Handle unreachable or produce results
+ if (sig.unreachable) {
+ if (lastUnreachable) {
+ producedByUnreachable[lastUnreachable] = produced;
+ produced = 0;
+ }
+ assert(produced == 0);
+ lastUnreachable = expr;
+ stackSize = 0;
+ } else {
+ stackSize += sig.results.size();
+ }
+ });
+
+ // Finish record for final unreachable
+ if (lastUnreachable) {
+ producedByUnreachable[lastUnreachable] = produced;
+ }
+ }
+
+ // Take another pass through the block, recording srcs and dests.
+ std::vector<Location> values;
+ Expression* lastUnreachable = nullptr;
+ processBlock([&](Expression* expr, const StackSignature sig) {
+ assert((sig.params.size() <= values.size() || lastUnreachable) &&
+ "Block inputs not yet supported");
+
+ // Unreachable instructions consume all available values
+ size_t consumed = sig.unreachable
+ ? std::max(values.size(), sig.params.size())
+ : sig.params.size();
+
+ // We previously calculated how many values unreachable instructions produce
+ size_t produced =
+ sig.unreachable ? producedByUnreachable[expr] : sig.results.size();
+
+ srcs[expr] = std::vector<Location>(consumed);
+ dests[expr] = std::vector<Location>(produced);
+
+ // Figure out what kind of unreachable values we have
+ assert(sig.params.size() <= consumed);
+ size_t unreachableBeyondStack = 0;
+ size_t unreachableFromStack = 0;
+ if (consumed > values.size()) {
+ assert(consumed == sig.params.size());
+ unreachableBeyondStack = consumed - values.size();
+ } else if (consumed > sig.params.size()) {
+ assert(consumed == values.size());
+ unreachableFromStack = consumed - sig.params.size();
+ }
+
+ // Consume values
+ for (Index i = 0; i < consumed; ++i) {
+ if (i < unreachableBeyondStack) {
+ // This value comes from the polymorphic stack of the last unreachable
+ // because the stack did not have enough values to satisfy this
+ // instruction.
+ assert(lastUnreachable);
+ assert(producedByUnreachable[lastUnreachable] >=
+ unreachableBeyondStack);
+ Index destIndex =
+ producedByUnreachable[lastUnreachable] - unreachableBeyondStack + i;
+ Type type = sig.params[i];
+ srcs[expr][i] = {lastUnreachable, destIndex, type, true};
+ dests[lastUnreachable][destIndex] = {expr, i, type, false};
+ } else {
+ // A normal value from the value stack
+ bool unreachable = i < unreachableFromStack;
+ auto& src = values[values.size() + i - consumed];
+ srcs[expr][i] = src;
+ dests[src.expr][src.index] = {expr, i, src.type, unreachable};
+ }
+ }
+
+ // Update available values
+ if (unreachableBeyondStack) {
+ producedByUnreachable[lastUnreachable] -= unreachableBeyondStack;
+ values.resize(0);
+ } else {
+ values.resize(values.size() - consumed);
+ }
+
+ // Produce values
+ for (Index i = 0; i < sig.results.size(); ++i) {
+ values.push_back({expr, i, sig.results[i], false});
+ }
+
+ // Update the last unreachable instruction
+ if (sig.unreachable) {
+ assert(producedByUnreachable[lastUnreachable] == 0);
+ lastUnreachable = expr;
+ }
+ });
+}
+
+StackSignature StackFlow::getSignature(Expression* expr) {
+ auto exprSrcs = srcs.find(expr);
+ auto exprDests = dests.find(expr);
+ assert(exprSrcs != srcs.end() && exprDests != dests.end());
+ std::vector<Type> params, results;
+ for (auto& src : exprSrcs->second) {
+ params.push_back(src.type);
+ }
+ for (auto& dest : exprDests->second) {
+ results.push_back(dest.type);
+ }
+ bool unreachable = expr->type == Type::unreachable;
+ return StackSignature(Type(params), Type(results), unreachable);
+}
+
+} // namespace wasm
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-09 09:44:49 +0000