summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/abi/abi.h33
-rw-r--r--src/abi/stack.h124
-rw-r--r--src/cfg/liveness-traversal.h234
-rw-r--r--src/ir/find_all.h24
-rw-r--r--src/passes/CMakeLists.txt1
-rw-r--r--src/passes/CoalesceLocals.cpp287
-rw-r--r--src/passes/SpillPointers.cpp198
-rw-r--r--src/passes/pass.cpp1
-rw-r--r--src/passes/passes.h1
-rw-r--r--src/support/sorted_vector.h103
-rw-r--r--test/passes/spill-pointers.txt644
-rw-r--r--test/passes/spill-pointers.wast168
12 files changed, 1535 insertions, 283 deletions
diff --git a/src/abi/abi.h b/src/abi/abi.h
new file mode 100644
index 000000000..ff1864efa
--- /dev/null
+++ b/src/abi/abi.h
@@ -0,0 +1,33 @@
+/*
+ * Copyright 2017 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.
+ */
+
+#ifndef wasm_abi_abi_h
+#define wasm_abi_abi_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+namespace ABI {
+
+// The pointer type. Will need to update this for wasm64
+const static WasmType PointerType = WasmType::i32;
+
+} // namespace ABI
+
+} // namespace wasm
+
+#endif // wasm_abi_abi_h
diff --git a/src/abi/stack.h b/src/abi/stack.h
new file mode 100644
index 000000000..e43be07ec
--- /dev/null
+++ b/src/abi/stack.h
@@ -0,0 +1,124 @@
+/*
+ * Copyright 2017 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.
+ */
+
+#ifndef wasm_abi_stack_h
+#define wasm_abi_stack_h
+
+#include "wasm.h"
+#include "wasm-builder.h"
+#include "shared-constants.h"
+#include "asmjs/shared-constants.h"
+#include "ir/find_all.h"
+#include "ir/global-utils.h"
+#include "abi.h"
+
+namespace wasm {
+
+namespace ABI {
+
+enum {
+ StackAlign = 16
+};
+
+inline Index stackAlign(Index size) {
+ return (size + StackAlign - 1) & -StackAlign;
+}
+
+// Allocate some space on the stack, and assign it to a local.
+// The local will have the same constant value in all the function, so you can just
+// get_local it anywhere there.
+inline void getStackSpace(Index local, Function* func, Index size, Module& wasm) {
+ auto* stackPointer = GlobalUtils::getGlobalInitializedToImport(wasm, ENV, "STACKTOP");
+ if (!stackPointer) {
+ Fatal() << "getStackSpace: failed to find the stack pointer";
+ }
+ // align the size
+ size = stackAlign(size);
+ // TODO: find existing stack usage, and add on top of that - carefully
+ Builder builder(wasm);
+ auto* block = builder.makeBlock();
+ block->list.push_back(
+ builder.makeSetLocal(
+ local,
+ builder.makeGetGlobal(stackPointer->name, PointerType)
+ )
+ );
+ // TODO: add stack max check
+ Expression* added;
+ if (PointerType == i32) {
+ added = builder.makeBinary(
+ AddInt32,
+ builder.makeGetLocal(local, PointerType),
+ builder.makeConst(Literal(int32_t(size)))
+ );
+ } else {
+ WASM_UNREACHABLE();
+ }
+ block->list.push_back(
+ builder.makeSetGlobal(
+ stackPointer->name,
+ added
+ )
+ );
+ auto makeStackRestore = [&]() {
+ return builder.makeSetGlobal(
+ stackPointer->name,
+ builder.makeGetLocal(local, PointerType)
+ );
+ };
+ // add stack restores to the returns
+ FindAllPointers<Return> finder(func->body);
+ for (auto** ptr : finder.list) {
+ auto* ret = (*ptr)->cast<Return>();
+ if (ret->value && ret->value->type != unreachable) {
+ // handle the returned value
+ auto* block = builder.makeBlock();
+ auto temp = builder.addVar(func, ret->value->type);
+ block->list.push_back(builder.makeSetLocal(temp, ret->value));
+ block->list.push_back(makeStackRestore());
+ block->list.push_back(builder.makeReturn(
+ builder.makeGetLocal(temp, ret->value->type)
+ ));
+ block->finalize();
+ *ptr = block;
+ } else {
+ // restore, then return
+ *ptr = builder.makeSequence(makeStackRestore(), ret);
+ }
+ }
+ // add stack restores to the body
+ if (func->body->type == none) {
+ block->list.push_back(func->body);
+ block->list.push_back(makeStackRestore());
+ } else if (func->body->type == unreachable) {
+ block->list.push_back(func->body);
+ // no need to restore the old stack value, we're gone anyhow
+ } else {
+ // save the return value
+ auto temp = builder.addVar(func, func->result);
+ block->list.push_back(builder.makeSetLocal(temp, func->body));
+ block->list.push_back(makeStackRestore());
+ block->list.push_back(builder.makeGetLocal(temp, func->result));
+ }
+ block->finalize();
+ func->body = block;
+}
+
+} // namespace ABI
+
+} // namespace wasm
+
+#endif // wasm_abi_stack_h
diff --git a/src/cfg/liveness-traversal.h b/src/cfg/liveness-traversal.h
new file mode 100644
index 000000000..24578dcd7
--- /dev/null
+++ b/src/cfg/liveness-traversal.h
@@ -0,0 +1,234 @@
+#include <wasm-printing.h>
+/*
+ * Copyright 2017 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.
+ */
+
+//
+// Convert the AST to a CFG, while traversing it.
+//
+// Note that this is not the same as the relooper CFG. The relooper is
+// designed for compilation to an AST, this is for processing. There is
+// no built-in support for transforming this CFG into the AST back
+// again, it is just metadata on the side for computation purposes.
+//
+// Usage: As the traversal proceeds, you can note information and add it to
+// the current basic block using currBasicBlock, on the contents
+// property, whose type is user-defined.
+//
+
+#ifndef liveness_traversal_h
+#define liveness_traversal_h
+
+#include "support/sorted_vector.h"
+#include "wasm.h"
+#include "wasm-builder.h"
+#include "wasm-traversal.h"
+#include "cfg-traversal.h"
+
+namespace wasm {
+
+// A set of locals. This is optimized for comparisons,
+// mergings, and iteration on elements, assuming that there
+// may be a great many potential elements but actual sets
+// may be fairly small. Specifically, we use a sorted
+// vector.
+typedef SortedVector LocalSet;
+
+// A liveness-relevant action. Supports a get, a set, or an
+// "other" which can be used for other purposes, to mark
+// their position in a block
+struct Action {
+ enum What {
+ Get = 0,
+ Set = 1,
+ Other = 2
+ };
+ What what;
+ Index index; // the local index read or written
+ Expression** origin; // the origin
+ bool effective; // whether a store is actually effective, i.e., may be read
+
+ Action(What what, Index index, Expression** origin) : what(what), index(index), origin(origin), effective(false) {
+ assert(what != Other);
+ if (what == Get) assert((*origin)->is<GetLocal>());
+ if (what == Set) assert((*origin)->is<SetLocal>());
+ }
+ Action(Expression** origin) : what(Other), origin(origin) {}
+
+ bool isGet() { return what == Get; }
+ bool isSet() { return what == Set; }
+ bool isOther() { return what == Other; }
+};
+
+// information about liveness in a basic block
+struct Liveness {
+ LocalSet start, end; // live locals at the start and end
+ std::vector<Action> actions; // actions occurring in this block
+
+ void dump(Function* func) {
+ if (actions.empty()) return;
+ std::cout << " actions:\n";
+ for (auto& action : actions) {
+ std::cout << " " << (action.isGet() ? "get" : "set") << " " << func->getLocalName(action.index) << "\n";
+ }
+ }
+};
+
+template<typename SubType, typename VisitorType>
+struct LivenessWalker : public CFGWalker<SubType, VisitorType, Liveness> {
+ typedef typename CFGWalker<SubType, VisitorType, Liveness>::BasicBlock BasicBlock;
+
+ Index numLocals;
+ std::unordered_set<BasicBlock*> liveBlocks;
+ std::vector<uint8_t> copies; // canonicalized - accesses should check (low, high) TODO: use a map for high N, as this tends to be sparse? or don't look at copies at all for big N?
+ std::vector<Index> totalCopies; // total # of copies for each local, with all others
+
+ // cfg traversal work
+
+ static void doVisitGetLocal(SubType* self, Expression** currp) {
+ auto* curr = (*currp)->cast<GetLocal>();
+ // if in unreachable code, ignore
+ if (!self->currBasicBlock) {
+ *currp = Builder(*self->getModule()).replaceWithIdenticalType(curr);
+ return;
+ }
+ self->currBasicBlock->contents.actions.emplace_back(Action::Get, curr->index, currp);
+ }
+
+ static void doVisitSetLocal(SubType* self, Expression** currp) {
+ auto* curr = (*currp)->cast<SetLocal>();
+ // if in unreachable code, we don't need the tee (but might need the value, if it has side effects)
+ if (!self->currBasicBlock) {
+ if (curr->isTee()) {
+ *currp = curr->value;
+ } else {
+ *currp = Builder(*self->getModule()).makeDrop(curr->value);
+ }
+ return;
+ }
+ self->currBasicBlock->contents.actions.emplace_back(Action::Set, curr->index, currp);
+ // if this is a copy, note it
+ if (auto* get = self->getCopy(curr)) {
+ // add 2 units, so that backedge prioritization can decide ties, but not much more
+ self->addCopy(curr->index, get->index);
+ self->addCopy(curr->index, get->index);
+ }
+ }
+
+ // A simple copy is a set of a get. A more interesting copy
+ // is a set of an if with a value, where one side a get.
+ // That can happen when we create an if value in simplify-locals. TODO: recurse into
+ // nested ifs, and block return values? Those cases are trickier, need to
+ // count to see if worth it.
+ // TODO: an if can have two copies
+ GetLocal* getCopy(SetLocal* set) {
+ if (auto* get = set->value->dynCast<GetLocal>()) return get;
+ if (auto* iff = set->value->dynCast<If>()) {
+ if (auto* get = iff->ifTrue->dynCast<GetLocal>()) return get;
+ if (iff->ifFalse) {
+ if (auto* get = iff->ifFalse->dynCast<GetLocal>()) return get;
+ }
+ }
+ return nullptr;
+ }
+
+ // main entry point
+
+ void doWalkFunction(Function* func) {
+ numLocals = func->getNumLocals();
+ copies.resize(numLocals * numLocals);
+ std::fill(copies.begin(), copies.end(), 0);
+ totalCopies.resize(numLocals);
+ std::fill(totalCopies.begin(), totalCopies.end(), 0);
+ // create the CFG by walking the IR
+ CFGWalker<SubType, VisitorType, Liveness>::doWalkFunction(func);
+ // ignore links to dead blocks, so they don't confuse us and we can see their stores are all ineffective
+ liveBlocks = CFGWalker<SubType, VisitorType, Liveness>::findLiveBlocks();
+ CFGWalker<SubType, VisitorType, Liveness>::unlinkDeadBlocks(liveBlocks);
+ // flow liveness across blocks
+ flowLiveness();
+ }
+
+ void flowLiveness() {
+ // keep working while stuff is flowing
+ std::unordered_set<BasicBlock*> queue;
+ for (auto& curr : CFGWalker<SubType, VisitorType, Liveness>::basicBlocks) {
+ if (liveBlocks.count(curr.get()) == 0) continue; // ignore dead blocks
+ queue.insert(curr.get());
+ // do the first scan through the block, starting with nothing live at the end, and updating the liveness at the start
+ scanLivenessThroughActions(curr->contents.actions, curr->contents.start);
+ }
+ // at every point in time, we assume we already noted interferences between things already known alive at the end, and scanned back through the block using that
+ while (queue.size() > 0) {
+ auto iter = queue.begin();
+ auto* curr = *iter;
+ queue.erase(iter);
+ LocalSet live;
+ if (!mergeStartsAndCheckChange(curr->out, curr->contents.end, live)) continue;
+ assert(curr->contents.end.size() < live.size());
+ curr->contents.end = live;
+ scanLivenessThroughActions(curr->contents.actions, live);
+ // liveness is now calculated at the start. if something
+ // changed, all predecessor blocks need recomputation
+ if (curr->contents.start == live) continue;
+ assert(curr->contents.start.size() < live.size());
+ curr->contents.start = live;
+ for (auto* in : curr->in) {
+ queue.insert(in);
+ }
+ }
+ }
+
+ // merge starts of a list of blocks. return
+ // whether anything changed vs an old state (which indicates further processing is necessary).
+ bool mergeStartsAndCheckChange(std::vector<BasicBlock*>& blocks, LocalSet& old, LocalSet& ret) {
+ if (blocks.size() == 0) return false;
+ ret = blocks[0]->contents.start;
+ if (blocks.size() > 1) {
+ // more than one, so we must merge
+ for (Index i = 1; i < blocks.size(); i++) {
+ ret = ret.merge(blocks[i]->contents.start);
+ }
+ }
+ return old != ret;
+ }
+
+ void scanLivenessThroughActions(std::vector<Action>& actions, LocalSet& live) {
+ // move towards the front
+ for (int i = int(actions.size()) - 1; i >= 0; i--) {
+ auto& action = actions[i];
+ if (action.isGet()) {
+ live.insert(action.index);
+ } else {
+ live.erase(action.index);
+ }
+ }
+ }
+
+ void addCopy(Index i, Index j) {
+ auto k = std::min(i, j) * numLocals + std::max(i, j);
+ copies[k] = std::min(copies[k], uint8_t(254)) + 1;
+ totalCopies[i]++;
+ totalCopies[j]++;
+ }
+
+ uint8_t getCopies(Index i, Index j) {
+ return copies[std::min(i, j) * numLocals + std::max(i, j)];
+ }
+};
+
+} // namespace wasm
+
+#endif // liveness_traversal_h
diff --git a/src/ir/find_all.h b/src/ir/find_all.h
index 83c751666..44dc7a675 100644
--- a/src/ir/find_all.h
+++ b/src/ir/find_all.h
@@ -42,6 +42,30 @@ struct FindAll {
}
};
+// Find all pointers to instances of a certain node type
+
+struct PointerFinder : public PostWalker<PointerFinder, UnifiedExpressionVisitor<PointerFinder>> {
+ Expression::Id id;
+ std::vector<Expression**>* list;
+ void visitExpression(Expression* curr) {
+ if (curr->_id == id) {
+ (*list).push_back(getCurrentPointer());
+ }
+ }
+};
+
+template<typename T>
+struct FindAllPointers {
+ std::vector<Expression**> list;
+
+ FindAllPointers(Expression* ast) {
+ PointerFinder finder;
+ finder.id = T()._id;
+ finder.list = &list;
+ finder.walk(ast);
+ }
+};
+
} // namespace wasm
#endif // wasm_ir_find_all_h
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index e9a157499..1da9b57f7 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -38,6 +38,7 @@ SET(passes_SOURCES
TrapMode.cpp
SafeHeap.cpp
SimplifyLocals.cpp
+ SpillPointers.cpp
SSAify.cpp
Untee.cpp
Vacuum.cpp
diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp
index 36c963b08..ae9d9246e 100644
--- a/src/passes/CoalesceLocals.cpp
+++ b/src/passes/CoalesceLocals.cpp
@@ -29,7 +29,7 @@
#include "wasm.h"
#include "pass.h"
#include "ir/utils.h"
-#include "cfg/cfg-traversal.h"
+#include "cfg/liveness-traversal.h"
#include "wasm-builder.h"
#include "support/learning.h"
#include "support/permutations.h"
@@ -39,188 +39,21 @@
namespace wasm {
-// A set of locals. This is optimized for comparisons,
-// mergings, and iteration on elements, assuming that there
-// may be a great many potential elements but actual sets
-// may be fairly small. Specifically, we use a sorted
-// vector.
-struct LocalSet : std::vector<Index> {
- LocalSet() {}
-
- LocalSet merge(const LocalSet& other) const {
- LocalSet ret;
- ret.resize(size() + other.size());
- Index i = 0, j = 0, t = 0;
- while (i < size() && j < other.size()) {
- auto left = (*this)[i];
- auto right = other[j];
- if (left < right) {
- ret[t++] = left;
- i++;
- } else if (left > right) {
- ret[t++] = right;
- j++;
- } else {
- ret[t++] = left;
- i++;
- j++;
- }
- }
- while (i < size()) {
- ret[t++] = (*this)[i];
- i++;
- }
- while (j < other.size()) {
- ret[t++] = other[j];
- j++;
- }
- ret.resize(t);
- return ret;
- }
-
- void insert(Index x) {
- auto it = std::lower_bound(begin(), end(), x);
- if (it == end()) push_back(x);
- else if (*it > x) {
- Index i = it - begin();
- resize(size() + 1);
- std::move_backward(begin() + i, begin() + size() - 1, end());
- (*this)[i] = x;
- }
- }
-
- bool erase(Index x) {
- auto it = std::lower_bound(begin(), end(), x);
- if (it != end() && *it == x) {
- std::move(it + 1, end(), it);
- resize(size() - 1);
- return true;
- }
- return false;
- }
-
- bool has(Index x) {
- auto it = std::lower_bound(begin(), end(), x);
- return it != end() && *it == x;
- }
-
- void verify() const {
- for (Index i = 1; i < size(); i++) {
- assert((*this)[i - 1] < (*this)[i]);
- }
- }
-
- void dump(const char* str = nullptr) const {
- std::cout << "LocalSet " << (str ? str : "") << ": ";
- for (auto x : *this) std::cout << x << " ";
- std::cout << '\n';
- }
-};
-
-// a liveness-relevant action
-struct Action {
- enum What {
- Get, Set
- };
- What what;
- Index index; // the local index read or written
- Expression** origin; // the origin
- bool effective; // whether a store is actually effective, i.e., may be read
-
- Action(What what, Index index, Expression** origin) : what(what), index(index), origin(origin), effective(false) {}
-
- bool isGet() { return what == Get; }
- bool isSet() { return what == Set; }
-};
-
-// information about liveness in a basic block
-struct Liveness {
- LocalSet start, end; // live locals at the start and end
- std::vector<Action> actions; // actions occurring in this block
-
- void dump(Function* func) {
- if (actions.empty()) return;
- std::cout << " actions:\n";
- for (auto& action : actions) {
- std::cout << " " << (action.isGet() ? "get" : "set") << " " << func->getLocalName(action.index) << "\n";
- }
- }
-};
-
-struct CoalesceLocals : public WalkerPass<CFGWalker<CoalesceLocals, Visitor<CoalesceLocals>, Liveness>> {
+struct CoalesceLocals : public WalkerPass<LivenessWalker<CoalesceLocals, Visitor<CoalesceLocals>>> {
bool isFunctionParallel() override { return true; }
Pass* create() override { return new CoalesceLocals; }
- Index numLocals;
-
- // cfg traversal work
-
- static void doVisitGetLocal(CoalesceLocals* self, Expression** currp) {
- auto* curr = (*currp)->cast<GetLocal>();
- // if in unreachable code, ignore
- if (!self->currBasicBlock) {
- *currp = Builder(*self->getModule()).replaceWithIdenticalType(curr);
- return;
- }
- self->currBasicBlock->contents.actions.emplace_back(Action::Get, curr->index, currp);
- }
-
- static void doVisitSetLocal(CoalesceLocals* self, Expression** currp) {
- auto* curr = (*currp)->cast<SetLocal>();
- // if in unreachable code, we don't need the tee (but might need the value, if it has side effects)
- if (!self->currBasicBlock) {
- if (curr->isTee()) {
- *currp = curr->value;
- } else {
- *currp = Builder(*self->getModule()).makeDrop(curr->value);
- }
- return;
- }
- self->currBasicBlock->contents.actions.emplace_back(Action::Set, curr->index, currp);
- // if this is a copy, note it
- if (auto* get = self->getCopy(curr)) {
- // add 2 units, so that backedge prioritization can decide ties, but not much more
- self->addCopy(curr->index, get->index);
- self->addCopy(curr->index, get->index);
- }
- }
-
- // A simple copy is a set of a get. A more interesting copy
- // is a set of an if with a value, where one side a get.
- // That can happen when we create an if value in simplify-locals. TODO: recurse into
- // nested ifs, and block return values? Those cases are trickier, need to
- // count to see if worth it.
- // TODO: an if can have two copies
- GetLocal* getCopy(SetLocal* set) {
- if (auto* get = set->value->dynCast<GetLocal>()) return get;
- if (auto* iff = set->value->dynCast<If>()) {
- if (auto* get = iff->ifTrue->dynCast<GetLocal>()) return get;
- if (iff->ifFalse) {
- if (auto* get = iff->ifFalse->dynCast<GetLocal>()) return get;
- }
- }
- return nullptr;
- }
-
// main entry point
void doWalkFunction(Function* func);
void increaseBackEdgePriorities();
- void flowLiveness();
-
void calculateInterferences();
void calculateInterferences(const LocalSet& locals);
- // merge starts of a list of blocks, adding new interferences as necessary. return
- // whether anything changed vs an old state (which indicates further processing is necessary).
- bool mergeStartsAndCheckChange(std::vector<BasicBlock*>& blocks, LocalSet& old, LocalSet& ret);
-
- void scanLivenessThroughActions(std::vector<Action>& actions, LocalSet& live);
-
void pickIndicesFromOrder(std::vector<Index>& order, std::vector<Index>& indices);
void pickIndicesFromOrder(std::vector<Index>& order, std::vector<Index>& indices, Index& removedCopies);
@@ -231,7 +64,6 @@ struct CoalesceLocals : public WalkerPass<CFGWalker<CoalesceLocals, Visitor<Coal
// interference state
std::vector<bool> interferences; // canonicalized - accesses should check (low, high)
- std::unordered_set<BasicBlock*> liveBlocks;
void interfere(Index i, Index j) {
if (i == j) return;
@@ -246,50 +78,12 @@ struct CoalesceLocals : public WalkerPass<CFGWalker<CoalesceLocals, Visitor<Coal
bool interferes(Index i, Index j) {
return interferences[std::min(i, j) * numLocals + std::max(i, j)];
}
-
- // copying state
-
- std::vector<uint8_t> copies; // canonicalized - accesses should check (low, high) TODO: use a map for high N, as this tends to be sparse? or don't look at copies at all for big N?
- std::vector<Index> totalCopies; // total # of copies for each local, with all others
-
- void addCopy(Index i, Index j) {
- auto k = std::min(i, j) * numLocals + std::max(i, j);
- copies[k] = std::min(copies[k], uint8_t(254)) + 1;
- totalCopies[i]++;
- totalCopies[j]++;
- }
-
- uint8_t getCopies(Index i, Index j) {
- return copies[std::min(i, j) * numLocals + std::max(i, j)];
- }
};
void CoalesceLocals::doWalkFunction(Function* func) {
- numLocals = func->getNumLocals();
- copies.resize(numLocals * numLocals);
- std::fill(copies.begin(), copies.end(), 0);
- totalCopies.resize(numLocals);
- std::fill(totalCopies.begin(), totalCopies.end(), 0);
- // collect initial liveness info
super::doWalkFunction(func);
- // ignore links to dead blocks, so they don't confuse us and we can see their stores are all ineffective
- liveBlocks = findLiveBlocks();
- unlinkDeadBlocks(liveBlocks);
- // increase the cost of costly backedges
+ // prioritize back edges
increaseBackEdgePriorities();
-#ifdef CFG_DEBUG
- dumpCFG("the cfg");
-#endif
- // flow liveness across blocks
-#ifdef CFG_PROFILE
- static Timer timer("flow");
- timer.start();
-#endif
- flowLiveness();
-#ifdef CFG_PROFILE
- timer.stop();
- timer.dump();
-#endif
// use liveness to find interference
calculateInterferences();
// pick new indices
@@ -321,82 +115,9 @@ void CoalesceLocals::increaseBackEdgePriorities() {
}
}
-void CoalesceLocals::flowLiveness() {
+void CoalesceLocals::calculateInterferences() {
interferences.resize(numLocals * numLocals);
std::fill(interferences.begin(), interferences.end(), 0);
- // keep working while stuff is flowing
- std::unordered_set<BasicBlock*> queue;
- for (auto& curr : basicBlocks) {
- if (liveBlocks.count(curr.get()) == 0) continue; // ignore dead blocks
- queue.insert(curr.get());
- // do the first scan through the block, starting with nothing live at the end, and updating the liveness at the start
- scanLivenessThroughActions(curr->contents.actions, curr->contents.start);
- }
- // at every point in time, we assume we already noted interferences between things already known alive at the end, and scanned back through the block using that
- while (queue.size() > 0) {
- auto iter = queue.begin();
- auto* curr = *iter;
- queue.erase(iter);
- LocalSet live;
- if (!mergeStartsAndCheckChange(curr->out, curr->contents.end, live)) continue;
-#ifdef CFG_DEBUG
- std::cout << "change noticed at end of " << debugIds[curr] << " from " << curr->contents.end.size() << " to " << live.size() << " (out of " << numLocals << ")\n";
-#endif
- assert(curr->contents.end.size() < live.size());
- curr->contents.end = live;
- scanLivenessThroughActions(curr->contents.actions, live);
- // liveness is now calculated at the start. if something
- // changed, all predecessor blocks need recomputation
- if (curr->contents.start == live) continue;
-#ifdef CFG_DEBUG
- std::cout << "change noticed at start of " << debugIds[curr] << " from " << curr->contents.start.size() << " to " << live.size() << ", more work to do\n";
-#endif
- assert(curr->contents.start.size() < live.size());
- curr->contents.start = live;
- for (auto* in : curr->in) {
- queue.insert(in);
- }
- }
-#ifdef CFG_DEBUG
- std::hash<std::vector<bool>> hasher;
- std::cout << getFunction()->name << ": interference hash: " << hasher(*(std::vector<bool>*)&interferences) << "\n";
- for (Index i = 0; i < numLocals; i++) {
- std::cout << "int for " << getFunction()->getLocalName(i) << " [" << i << "]: ";
- for (Index j = 0; j < numLocals; j++) {
- if (interferes(i, j)) std::cout << getFunction()->getLocalName(j) << " ";
- }
- std::cout << "\n";
- }
-#endif
-}
-
-// merge starts of a list of blocks. return
-// whether anything changed vs an old state (which indicates further processing is necessary).
-bool CoalesceLocals::mergeStartsAndCheckChange(std::vector<BasicBlock*>& blocks, LocalSet& old, LocalSet& ret) {
- if (blocks.size() == 0) return false;
- ret = blocks[0]->contents.start;
- if (blocks.size() > 1) {
- // more than one, so we must merge
- for (Index i = 1; i < blocks.size(); i++) {
- ret = ret.merge(blocks[i]->contents.start);
- }
- }
- return old != ret;
-}
-
-void CoalesceLocals::scanLivenessThroughActions(std::vector<Action>& actions, LocalSet& live) {
- // move towards the front
- for (int i = int(actions.size()) - 1; i >= 0; i--) {
- auto& action = actions[i];
- if (action.isGet()) {
- live.insert(action.index);
- } else {
- live.erase(action.index);
- }
- }
-}
-
-void CoalesceLocals::calculateInterferences() {
for (auto& curr : basicBlocks) {
if (liveBlocks.count(curr.get()) == 0) continue; // ignore dead blocks
// everything coming in might interfere, as it might come from a different block
diff --git a/src/passes/SpillPointers.cpp b/src/passes/SpillPointers.cpp
new file mode 100644
index 000000000..492a90501
--- /dev/null
+++ b/src/passes/SpillPointers.cpp
@@ -0,0 +1,198 @@
+/*
+ * Copyright 2017 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.
+ */
+
+
+//
+// Spills values that might be pointers to the C stack. This allows
+// Boehm-style GC to see them properly.
+//
+// To reduce the overhead of the extra operations added here, you
+// should probably run optimizations after doing it.
+// TODO: add a dead store elimination pass, which would help here
+//
+// * There is currently no check that there is enough stack space.
+//
+
+#include "wasm.h"
+#include "pass.h"
+#include "cfg/liveness-traversal.h"
+#include "wasm-builder.h"
+#include "abi/abi.h"
+#include "abi/stack.h"
+
+namespace wasm {
+
+struct SpillPointers : public WalkerPass<LivenessWalker<SpillPointers, Visitor<SpillPointers>>> {
+ bool isFunctionParallel() override { return true; }
+
+ Pass* create() override { return new SpillPointers; }
+
+ // a mapping of the pointers to all the spillable things. We need to know
+ // how to replace them, and as we spill we may modify them. This map
+ // gives us, for an Expression** seen during the walk (and placed in the
+ // basic block, which is what we iterate on for efficiency) => the
+ // current actual pointer, which may have moded
+ std::unordered_map<Expression**, Expression**> actualPointers;
+
+ // note calls in basic blocks
+ template<typename T>
+ void visitSpillable(T* curr) {
+ // if in unreachable code, ignore
+ if (!currBasicBlock) return;
+ auto* pointer = getCurrentPointer();
+ currBasicBlock->contents.actions.emplace_back(pointer);
+ actualPointers[pointer] = pointer; // starts out as correct, may change later
+ }
+
+ void visitCall(Call* curr) {
+ visitSpillable(curr);
+ }
+ void visitCallImport(CallImport* curr) {
+ visitSpillable(curr);
+ }
+ void visitCallIndirect(CallIndirect* curr) {
+ visitSpillable(curr);
+ }
+
+ // main entry point
+
+ void doWalkFunction(Function* func) {
+ super::doWalkFunction(func);
+ spillPointers();
+ }
+
+ // map pointers to their offset in the spill area
+ typedef std::unordered_map<Index, Index> PointerMap;
+
+ void spillPointers() {
+ // we only care about possible pointers
+ auto* func = getFunction();
+ PointerMap pointerMap;
+ for (Index i = 0; i < func->getNumLocals(); i++) {
+ if (func->getLocalType(i) == ABI::PointerType) {
+ auto offset = pointerMap.size() * getWasmTypeSize(ABI::PointerType);
+ pointerMap[i] = offset;
+ }
+ }
+ // find calls and spill around them
+ bool spilled = false;
+ Index spillLocal = -1;
+ for (auto& curr : basicBlocks) {
+ if (liveBlocks.count(curr.get()) == 0) continue; // ignore dead blocks
+ auto& liveness = curr->contents;
+ auto& actions = liveness.actions;
+ Index lastCall = -1;
+ for (Index i = 0; i < actions.size(); i++) {
+ auto& action = liveness.actions[i];
+ if (action.isOther()) {
+ lastCall = i;
+ }
+ }
+ if (lastCall == Index(-1)) continue; // nothing to see here
+ // scan through the block, spilling around the calls
+ // TODO: we can filter on pointerMap everywhere
+ LocalSet live = liveness.end;
+ for (int i = int(actions.size()) - 1; i >= 0; i--) {
+ auto& action = actions[i];
+ if (action.isGet()) {
+ live.insert(action.index);
+ } else if (action.isSet()) {
+ live.erase(action.index);
+ } else if (action.isOther()) {
+ std::vector<Index> toSpill;
+ for (auto index : live) {
+ if (pointerMap.count(index) > 0) {
+ toSpill.push_back(index);
+ }
+ }
+ if (!toSpill.empty()) {
+ // we now have a call + the information about which locals
+ // should be spilled
+ if (!spilled) {
+ // prepare stack support: get a pointer to stack space big enough for all our data
+ spillLocal = Builder::addVar(func, ABI::PointerType);
+ spilled = true;
+ }
+ auto* pointer = actualPointers[action.origin]; // the origin was seen at walk, but the thing may have moved
+ spillPointersAroundCall(pointer, toSpill, spillLocal, pointerMap, func, getModule());
+ }
+ } else {
+ WASM_UNREACHABLE();
+ }
+ }
+ }
+ if (spilled) {
+ // get the stack space, and set the local to it
+ ABI::getStackSpace(spillLocal, func, getWasmTypeSize(ABI::PointerType) * pointerMap.size(), *getModule());
+ }
+ }
+
+ void spillPointersAroundCall(Expression** origin, std::vector<Index>& toSpill, Index spillLocal, PointerMap& pointerMap, Function* func, Module* module) {
+ auto* call = *origin;
+ if (call->type == unreachable) return; // the call is never reached anyhow, ignore
+ Builder builder(*module);
+ auto* block = builder.makeBlock();
+ // move the operands into locals, as we must spill after they are executed
+ auto handleOperand = [&](Expression*& operand) {
+ auto temp = builder.addVar(func, operand->type);
+ auto* set = builder.makeSetLocal(temp, operand);
+ block->list.push_back(set);
+ block->finalize();
+ if (actualPointers.count(&operand) > 0) {
+ // this is something we track, and it's moving - update
+ actualPointers[&operand] = &set->value;
+ }
+ operand = builder.makeGetLocal(temp, operand->type);
+ };
+ if (call->is<Call>()) {
+ for (auto*& operand : call->cast<Call>()->operands) {
+ handleOperand(operand);
+ }
+ } else if (call->is<CallImport>()) {
+ for (auto*& operand : call->cast<CallImport>()->operands) {
+ handleOperand(operand);
+ }
+ } else if (call->is<CallIndirect>()) {
+ for (auto*& operand : call->cast<CallIndirect>()->operands) {
+ handleOperand(operand);
+ }
+ handleOperand(call->cast<CallIndirect>()->target);
+ } else {
+ WASM_UNREACHABLE();
+ }
+ // add the spills
+ for (auto index : toSpill) {
+ block->list.push_back(builder.makeStore(
+ getWasmTypeSize(ABI::PointerType),
+ pointerMap[index],
+ getWasmTypeSize(ABI::PointerType),
+ builder.makeGetLocal(spillLocal, ABI::PointerType),
+ builder.makeGetLocal(index, ABI::PointerType),
+ ABI::PointerType
+ ));
+ }
+ // add the (modified) call
+ block->list.push_back(call);
+ block->finalize();
+ *origin = block;
+ }
+};
+
+Pass *createSpillPointersPass() {
+ return new SpillPointers();
+}
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 89467899c..339b1d1da 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -109,6 +109,7 @@ void PassRegistry::registerPasses() {
registerPass("simplify-locals-notee", "miscellaneous locals-related optimizations", createSimplifyLocalsNoTeePass);
registerPass("simplify-locals-nostructure", "miscellaneous locals-related optimizations", createSimplifyLocalsNoStructurePass);
registerPass("simplify-locals-notee-nostructure", "miscellaneous locals-related optimizations", createSimplifyLocalsNoTeeNoStructurePass);
+ registerPass("spill-pointers", "spill pointers to the C stack (useful for Boehm-style GC)", createSpillPointersPass);
registerPass("ssa", "ssa-ify variables so that they have a single assignment", createSSAifyPass);
registerPass("trap-mode-clamp", "replace trapping operations with clamping semantics", createTrapModeClamp);
registerPass("trap-mode-js", "replace trapping operations with js semantics", createTrapModeJS);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 5cefdea17..53198bf56 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -67,6 +67,7 @@ Pass* createSimplifyLocalsPass();
Pass* createSimplifyLocalsNoTeePass();
Pass* createSimplifyLocalsNoStructurePass();
Pass* createSimplifyLocalsNoTeeNoStructurePass();
+Pass* createSpillPointersPass();
Pass* createSSAifyPass();
Pass* createTrapModeClamp();
Pass* createTrapModeJS();
diff --git a/src/support/sorted_vector.h b/src/support/sorted_vector.h
new file mode 100644
index 000000000..607a30578
--- /dev/null
+++ b/src/support/sorted_vector.h
@@ -0,0 +1,103 @@
+/*
+ * Copyright 2017 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.
+ */
+
+//
+// Command line helpers.
+//
+
+#ifndef wasm_support_sorted_vector_h
+#define wasm_support_sorted_vector_h
+
+#include <vector>
+
+namespace wasm {
+
+struct SortedVector : std::vector<Index> {
+ SortedVector() {}
+
+ SortedVector merge(const SortedVector& other) const {
+ SortedVector ret;
+ ret.resize(size() + other.size());
+ Index i = 0, j = 0, t = 0;
+ while (i < size() && j < other.size()) {
+ auto left = (*this)[i];
+ auto right = other[j];
+ if (left < right) {
+ ret[t++] = left;
+ i++;
+ } else if (left > right) {
+ ret[t++] = right;
+ j++;
+ } else {
+ ret[t++] = left;
+ i++;
+ j++;
+ }
+ }
+ while (i < size()) {
+ ret[t++] = (*this)[i];
+ i++;
+ }
+ while (j < other.size()) {
+ ret[t++] = other[j];
+ j++;
+ }
+ ret.resize(t);
+ return ret;
+ }
+
+ void insert(Index x) {
+ auto it = std::lower_bound(begin(), end(), x);
+ if (it == end()) push_back(x);
+ else if (*it > x) {
+ Index i = it - begin();
+ resize(size() + 1);
+ std::move_backward(begin() + i, begin() + size() - 1, end());
+ (*this)[i] = x;
+ }
+ }
+
+ bool erase(Index x) {
+ auto it = std::lower_bound(begin(), end(), x);
+ if (it != end() && *it == x) {
+ std::move(it + 1, end(), it);
+ resize(size() - 1);
+ return true;
+ }
+ return false;
+ }
+
+ bool has(Index x) {
+ auto it = std::lower_bound(begin(), end(), x);
+ return it != end() && *it == x;
+ }
+
+ void verify() const {
+ for (Index i = 1; i < size(); i++) {
+ assert((*this)[i - 1] < (*this)[i]);
+ }
+ }
+
+ void dump(const char* str = nullptr) const {
+ std::cout << "SortedVector " << (str ? str : "") << ": ";
+ for (auto x : *this) std::cout << x << " ";
+ std::cout << '\n';
+ }
+};
+
+} // namespace wasm
+
+#endif // wasm_support_sorted_vector_h
diff --git a/test/passes/spill-pointers.txt b/test/passes/spill-pointers.txt
new file mode 100644
index 000000000..30febbec6
--- /dev/null
+++ b/test/passes/spill-pointers.txt
@@ -0,0 +1,644 @@
+(module
+ (type $ii (func (param i32 i32)))
+ (type $FUNCSIG$vi (func (param i32)))
+ (type $2 (func))
+ (type $3 (func (result i32)))
+ (type $4 (func (param i32) (result i32)))
+ (type $5 (func (param f64)))
+ (import "env" "STACKTOP" (global $STACKTOP$asm2wasm$import i32))
+ (import "env" "segfault" (func $segfault (param i32)))
+ (global $stack_ptr (mut i32) (get_global $STACKTOP$asm2wasm$import))
+ (table 1 1 anyfunc)
+ (memory $0 10)
+ (func $nothing (; 1 ;) (type $2)
+ (nop)
+ )
+ (func $not-alive (; 2 ;) (type $2)
+ (local $x i32)
+ (set_local $x
+ (i32.const 1)
+ )
+ (call $nothing)
+ )
+ (func $spill (; 3 ;) (type $2)
+ (local $x i32)
+ (local $1 i32)
+ (set_local $1
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $1)
+ (i32.const 16)
+ )
+ )
+ (block
+ (block
+ (i32.store
+ (get_local $1)
+ (get_local $x)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ )
+ (func $ignore-non-pointers (; 4 ;) (type $2)
+ (local $x i32)
+ (local $y i64)
+ (local $z f32)
+ (local $w f64)
+ (local $4 i32)
+ (set_local $4
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $4)
+ (i32.const 16)
+ )
+ )
+ (block
+ (set_local $x
+ (i32.const 1)
+ )
+ (set_local $y
+ (i64.const 1)
+ )
+ (set_local $z
+ (f32.const 1)
+ )
+ (set_local $w
+ (f64.const 1)
+ )
+ (block
+ (i32.store
+ (get_local $4)
+ (get_local $x)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ (drop
+ (get_local $y)
+ )
+ (drop
+ (get_local $z)
+ )
+ (drop
+ (get_local $w)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $4)
+ )
+ )
+ (func $spill4 (; 5 ;) (type $2)
+ (local $x i32)
+ (local $y i32)
+ (local $z i32)
+ (local $w i32)
+ (local $4 i32)
+ (set_local $4
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $4)
+ (i32.const 16)
+ )
+ )
+ (block
+ (set_local $x
+ (i32.const 1)
+ )
+ (set_local $y
+ (i32.const 1)
+ )
+ (set_local $z
+ (i32.const 1)
+ )
+ (set_local $w
+ (i32.const 1)
+ )
+ (block
+ (i32.store
+ (get_local $4)
+ (get_local $x)
+ )
+ (i32.store offset=4
+ (get_local $4)
+ (get_local $y)
+ )
+ (i32.store offset=8
+ (get_local $4)
+ (get_local $z)
+ )
+ (i32.store offset=12
+ (get_local $4)
+ (get_local $w)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ (drop
+ (get_local $y)
+ )
+ (drop
+ (get_local $z)
+ )
+ (drop
+ (get_local $w)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $4)
+ )
+ )
+ (func $spill5 (; 6 ;) (type $2)
+ (local $x i32)
+ (local $y i32)
+ (local $z i32)
+ (local $w i32)
+ (local $a i32)
+ (local $5 i32)
+ (set_local $5
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $5)
+ (i32.const 32)
+ )
+ )
+ (block
+ (set_local $x
+ (i32.const 1)
+ )
+ (set_local $y
+ (i32.const 1)
+ )
+ (set_local $z
+ (i32.const 1)
+ )
+ (set_local $w
+ (i32.const 1)
+ )
+ (set_local $a
+ (i32.const 1)
+ )
+ (block
+ (i32.store
+ (get_local $5)
+ (get_local $x)
+ )
+ (i32.store offset=4
+ (get_local $5)
+ (get_local $y)
+ )
+ (i32.store offset=8
+ (get_local $5)
+ (get_local $z)
+ )
+ (i32.store offset=12
+ (get_local $5)
+ (get_local $w)
+ )
+ (i32.store offset=16
+ (get_local $5)
+ (get_local $a)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ (drop
+ (get_local $y)
+ )
+ (drop
+ (get_local $z)
+ )
+ (drop
+ (get_local $w)
+ )
+ (drop
+ (get_local $a)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $5)
+ )
+ )
+ (func $some-alive (; 7 ;) (type $2)
+ (local $x i32)
+ (local $y i32)
+ (local $2 i32)
+ (set_local $2
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $2)
+ (i32.const 16)
+ )
+ )
+ (block
+ (block
+ (i32.store
+ (get_local $2)
+ (get_local $x)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $2)
+ )
+ )
+ (func $spill-args (; 8 ;) (type $ii) (param $p i32) (param $q i32)
+ (local $x i32)
+ (local $3 i32)
+ (local $4 i32)
+ (local $5 i32)
+ (set_local $3
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $3)
+ (i32.const 16)
+ )
+ )
+ (block
+ (block
+ (set_local $4
+ (i32.const 1)
+ )
+ (set_local $5
+ (i32.const 2)
+ )
+ (i32.store offset=8
+ (get_local $3)
+ (get_local $x)
+ )
+ (call $spill-args
+ (get_local $4)
+ (get_local $5)
+ )
+ )
+ (drop
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $3)
+ )
+ )
+ (func $spill-ret (; 9 ;) (type $3) (result i32)
+ (local $x i32)
+ (local $1 i32)
+ (local $2 i32)
+ (local $3 i32)
+ (local $4 i32)
+ (set_local $1
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $1)
+ (i32.const 16)
+ )
+ )
+ (set_local $4
+ (block (result i32)
+ (block
+ (i32.store
+ (get_local $1)
+ (get_local $x)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ (if
+ (i32.const 1)
+ (block
+ (set_local $2
+ (i32.const 2)
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (return
+ (get_local $2)
+ )
+ )
+ (block
+ (set_local $3
+ (i32.const 3)
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (return
+ (get_local $3)
+ )
+ )
+ )
+ (i32.const 4)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (get_local $4)
+ )
+ (func $spill-unreachable (; 10 ;) (type $3) (result i32)
+ (local $x i32)
+ (local $1 i32)
+ (local $2 i32)
+ (set_local $1
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $1)
+ (i32.const 16)
+ )
+ )
+ (set_local $2
+ (block (result i32)
+ (block
+ (i32.store
+ (get_local $1)
+ (get_local $x)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ (unreachable)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (get_local $2)
+ )
+ (func $spill-call-call0 (; 11 ;) (type $4) (param $p i32) (result i32)
+ (unreachable)
+ )
+ (func $spill-call-call1 (; 12 ;) (type $4) (param $p i32) (result i32)
+ (local $x i32)
+ (local $2 i32)
+ (local $3 i32)
+ (local $4 i32)
+ (local $5 i32)
+ (set_local $2
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $2)
+ (i32.const 16)
+ )
+ )
+ (set_local $5
+ (block (result i32)
+ (drop
+ (block (result i32)
+ (set_local $3
+ (block (result i32)
+ (set_local $4
+ (i32.const 1)
+ )
+ (i32.store offset=4
+ (get_local $2)
+ (get_local $x)
+ )
+ (call $spill-call-call1
+ (get_local $4)
+ )
+ )
+ )
+ (i32.store offset=4
+ (get_local $2)
+ (get_local $x)
+ )
+ (call $spill-call-call0
+ (get_local $3)
+ )
+ )
+ )
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $2)
+ )
+ (get_local $5)
+ )
+ (func $spill-call-ret (; 13 ;) (type $4) (param $p i32) (result i32)
+ (local $x i32)
+ (drop
+ (call $spill-call-call0
+ (return
+ (i32.const 1)
+ )
+ )
+ )
+ (i32.const 0)
+ )
+ (func $spill-ret-call (; 14 ;) (type $4) (param $p i32) (result i32)
+ (local $x i32)
+ (drop
+ (return
+ (call $spill-call-call0
+ (i32.const 1)
+ )
+ )
+ )
+ (i32.const 0)
+ )
+ (func $spill-ret-ret (; 15 ;) (type $3) (result i32)
+ (local $x i32)
+ (local $1 i32)
+ (local $2 i32)
+ (local $3 i32)
+ (set_local $1
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $1)
+ (i32.const 16)
+ )
+ )
+ (set_local $3
+ (block (result i32)
+ (block
+ (i32.store
+ (get_local $1)
+ (get_local $x)
+ )
+ (call $nothing)
+ )
+ (drop
+ (get_local $x)
+ )
+ (drop
+ (block
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (return
+ (block
+ (set_local $2
+ (i32.const 1)
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (return
+ (get_local $2)
+ )
+ )
+ )
+ )
+ )
+ (i32.const 0)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ (get_local $3)
+ )
+ (func $spill-call-othertype (; 16 ;) (type $5) (param $y f64)
+ (local $x i32)
+ (local $2 i32)
+ (local $3 f64)
+ (set_local $2
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $2)
+ (i32.const 16)
+ )
+ )
+ (block
+ (block
+ (set_local $3
+ (f64.const 1)
+ )
+ (i32.store
+ (get_local $2)
+ (get_local $x)
+ )
+ (call $spill-call-othertype
+ (get_local $3)
+ )
+ )
+ (drop
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $2)
+ )
+ )
+ (func $spill-call_indirect (; 17 ;) (type $2)
+ (local $x i32)
+ (local $1 i32)
+ (local $2 i32)
+ (local $3 i32)
+ (local $4 i32)
+ (set_local $1
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $1)
+ (i32.const 16)
+ )
+ )
+ (block
+ (block
+ (set_local $2
+ (i32.const 123)
+ )
+ (set_local $3
+ (i32.const 456)
+ )
+ (set_local $4
+ (i32.const 789)
+ )
+ (i32.store
+ (get_local $1)
+ (get_local $x)
+ )
+ (call_indirect (type $ii)
+ (get_local $2)
+ (get_local $3)
+ (get_local $4)
+ )
+ )
+ (drop
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ )
+ (func $spill-call_import (; 18 ;) (type $2)
+ (local $x i32)
+ (local $1 i32)
+ (local $2 i32)
+ (set_local $1
+ (get_global $stack_ptr)
+ )
+ (set_global $stack_ptr
+ (i32.add
+ (get_local $1)
+ (i32.const 16)
+ )
+ )
+ (block
+ (block
+ (set_local $2
+ (i32.const 200)
+ )
+ (i32.store
+ (get_local $1)
+ (get_local $x)
+ )
+ (call $segfault
+ (get_local $2)
+ )
+ )
+ (drop
+ (get_local $x)
+ )
+ )
+ (set_global $stack_ptr
+ (get_local $1)
+ )
+ )
+)
diff --git a/test/passes/spill-pointers.wast b/test/passes/spill-pointers.wast
new file mode 100644
index 000000000..c9bccd3b5
--- /dev/null
+++ b/test/passes/spill-pointers.wast
@@ -0,0 +1,168 @@
+(module
+ (memory 10)
+ (type $ii (func (param i32 i32)))
+ (table 1 1 anyfunc)
+ (elem (i32.const 0))
+ (import "env" "STACKTOP" (global $STACKTOP$asm2wasm$import i32))
+ (import "env" "segfault" (func $segfault (param i32)))
+ (global $stack_ptr (mut i32) (get_global $STACKTOP$asm2wasm$import))
+
+ (func $nothing
+ )
+ (func $not-alive
+ (local $x i32)
+ (set_local $x (i32.const 1))
+ (call $nothing)
+ )
+ (func $spill
+ (local $x i32)
+ (call $nothing)
+ (drop (get_local $x))
+ )
+ (func $ignore-non-pointers
+ (local $x i32)
+ (local $y i64)
+ (local $z f32)
+ (local $w f64)
+ (set_local $x (i32.const 1))
+ (set_local $y (i64.const 1))
+ (set_local $z (f32.const 1))
+ (set_local $w (f64.const 1))
+ (call $nothing)
+ (drop (get_local $x))
+ (drop (get_local $y))
+ (drop (get_local $z))
+ (drop (get_local $w))
+ )
+ (func $spill4
+ (local $x i32)
+ (local $y i32)
+ (local $z i32)
+ (local $w i32)
+ (set_local $x (i32.const 1))
+ (set_local $y (i32.const 1))
+ (set_local $z (i32.const 1))
+ (set_local $w (i32.const 1))
+ (call $nothing)
+ (drop (get_local $x))
+ (drop (get_local $y))
+ (drop (get_local $z))
+ (drop (get_local $w))
+ )
+ (func $spill5
+ (local $x i32)
+ (local $y i32)
+ (local $z i32)
+ (local $w i32)
+ (local $a i32)
+ (set_local $x (i32.const 1))
+ (set_local $y (i32.const 1))
+ (set_local $z (i32.const 1))
+ (set_local $w (i32.const 1))
+ (set_local $a (i32.const 1))
+ (call $nothing)
+ (drop (get_local $x))
+ (drop (get_local $y))
+ (drop (get_local $z))
+ (drop (get_local $w))
+ (drop (get_local $a))
+ )
+ (func $some-alive
+ (local $x i32)
+ (local $y i32)
+ (call $nothing)
+ (drop (get_local $x))
+ )
+ (func $spill-args (param $p i32) (param $q i32)
+ (local $x i32)
+ (call $spill-args (i32.const 1) (i32.const 2))
+ (drop (get_local $x))
+ )
+ (func $spill-ret (result i32)
+ (local $x i32)
+ (call $nothing)
+ (drop (get_local $x))
+ (if (i32.const 1)
+ (return (i32.const 2))
+ (return (i32.const 3))
+ )
+ (i32.const 4)
+ )
+ (func $spill-unreachable (result i32)
+ (local $x i32)
+ (call $nothing)
+ (drop (get_local $x))
+ (unreachable)
+ )
+ (func $spill-call-call0 (param $p i32) (result i32)
+ (unreachable)
+ )
+ (func $spill-call-call1 (param $p i32) (result i32)
+ (local $x i32)
+ (drop
+ (call $spill-call-call0
+ (call $spill-call-call1
+ (i32.const 1)
+ )
+ )
+ )
+ (get_local $x)
+ )
+ (func $spill-call-ret (param $p i32) (result i32)
+ (local $x i32)
+ (drop
+ (call $spill-call-call0
+ (return
+ (i32.const 1)
+ )
+ )
+ )
+ (get_local $x)
+ )
+ (func $spill-ret-call (param $p i32) (result i32)
+ (local $x i32)
+ (drop
+ (return
+ (call $spill-call-call0
+ (i32.const 1)
+ )
+ )
+ )
+ (get_local $x)
+ )
+ (func $spill-ret-ret (result i32)
+ (local $x i32)
+ (call $nothing)
+ (drop (get_local $x))
+ (drop
+ (return
+ (return
+ (i32.const 1)
+ )
+ )
+ )
+ (get_local $x)
+ )
+ (func $spill-call-othertype (param $y f64)
+ (local $x i32)
+ (call $spill-call-othertype (f64.const 1))
+ (drop (get_local $x))
+ )
+ (func $spill-call_indirect
+ (local $x i32)
+ (call_indirect (type $ii)
+ (i32.const 123)
+ (i32.const 456)
+ (i32.const 789)
+ )
+ (drop (get_local $x))
+ )
+ (func $spill-call_import
+ (local $x i32)
+ (call_import $segfault
+ (i32.const 200)
+ )
+ (drop (get_local $x))
+ )
+)
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-21 16:28:54 +0000