/*
* 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.
*/
//
// Loads wasm plus a list of functions that are global ctors, i.e.,
// are to be executed. It then executes as many of them as it can,
// applying their changes to memory etc as needed, then writes it. In
// other words, this executes code at compile time to speed up
// startup later.
//
#include <memory>
#include "asmjs/shared-constants.h"
#include "ir/find_all.h"
#include "ir/gc-type-utils.h"
#include "ir/global-utils.h"
#include "ir/import-utils.h"
#include "ir/literal-utils.h"
#include "ir/memory-utils.h"
#include "ir/names.h"
#include "pass.h"
#include "support/colors.h"
#include "support/file.h"
#include "support/insert_ordered.h"
#include "support/small_set.h"
#include "support/string.h"
#include "support/topological_sort.h"
#include "tool-options.h"
#include "wasm-builder.h"
#include "wasm-interpreter.h"
#include "wasm-io.h"
#include "wasm-validator.h"
using namespace wasm;
namespace {
struct FailToEvalException {
std::string why;
FailToEvalException(std::string why) : why(why) {}
};
// Check whether a field is both nullable and mutable. This is a useful
// property for breaking cycles of GC data, see below.
bool isNullableAndMutable(Expression* ref, Index fieldIndex) {
// Find the field for the given reference, and check its properties.
auto field = GCTypeUtils::getField(ref->type, fieldIndex);
assert(field);
return field->type.isNullable() && field->mutable_ == Mutable;
}
// The prefix for a recommendation, so it is aligned properly with the rest of
// the output.
#define RECOMMENDATION "\n recommendation: "
class EvallingModuleRunner : public ModuleRunnerBase<EvallingModuleRunner> {
public:
EvallingModuleRunner(
Module& wasm,
ExternalInterface* externalInterface,
std::map<Name, std::shared_ptr<EvallingModuleRunner>> linkedInstances_ = {})
: ModuleRunnerBase(wasm, externalInterface, linkedInstances_) {}
Flow visitGlobalGet(GlobalGet* curr) {
// Error on reads of imported globals.
auto* global = wasm.getGlobal(curr->name);
if (global->imported()) {
throw FailToEvalException(std::string("read from imported global ") +
global->module.toString() + "." +
global->base.toString());
}
return ModuleRunnerBase<EvallingModuleRunner>::visitGlobalGet(curr);
}
};
// Build an artificial `env` module based on a module's imports, so that the
// interpreter can use correct object instances. It initializes usable global
// imports, and fills the rest with fake values since those are dangerous to
// use. we will fail if dangerous globals are used.
std::unique_ptr<Module> buildEnvModule(Module& wasm) {
auto env = std::make_unique<Module>();
env->name = "env";
// create empty functions with similar signature
ModuleUtils::iterImportedFunctions(wasm, [&](Function* func) {
if (func->module == env->name) {
Builder builder(*env);
auto* copied = ModuleUtils::copyFunction(func, *env);
copied->module = Name();
copied->base = Name();
copied->body = builder.makeUnreachable();
env->addExport(
builder.makeExport(func->base, copied->name, ExternalKind::Function));
}
});
// create tables with similar initial and max values
ModuleUtils::iterImportedTables(wasm, [&](Table* table) {
if (table->module == env->name) {
auto* copied = ModuleUtils::copyTable(table, *env);
copied->module = Name();
copied->base = Name();
env->addExport(Builder(*env).makeExport(
table->base, copied->name, ExternalKind::Table));
}
});
ModuleUtils::iterImportedGlobals(wasm, [&](Global* global) {
if (global->module == env->name) {
auto* copied = ModuleUtils::copyGlobal(global, *env);
copied->module = Name();
copied->base = Name();
Builder builder(*env);
copied->init = builder.makeConst(Literal::makeZero(global->type));
env->addExport(
builder.makeExport(global->base, copied->name, ExternalKind::Global));
}
});
// create an exported memory with the same initial and max size
ModuleUtils::iterImportedMemories(wasm, [&](Memory* memory) {
if (memory->module == env->name) {
auto* copied = ModuleUtils::copyMemory(memory, *env);
copied->module = Name();
copied->base = Name();
env->addExport(Builder(*env).makeExport(
memory->base, copied->name, ExternalKind::Memory));
}
});
return env;
}
// Whether to ignore external input to the program as it runs. If set, we will
// assume that stdin is empty, that any env vars we try to read are not set,
// that there are not arguments passed to main, etc.
static bool ignoreExternalInput = false;
struct CtorEvalExternalInterface : EvallingModuleRunner::ExternalInterface {
Module* wasm;
EvallingModuleRunner* instance;
std::map<Name, std::shared_ptr<EvallingModuleRunner>> linkedInstances;
// A representation of the contents of wasm memory as we execute.
std::unordered_map<Name, std::vector<char>> memories;
// All the names of globals we've seen in the module. We cannot reuse these.
// We must track these manually as we will be adding more, and as we do so we
// also reorder them, so we remove and re-add globals, which means the module
// itself is not aware of all the globals that belong to it (those that have
// not yet been re-added are a blind spot for it).
std::unordered_set<Name> usedGlobalNames;
// Set to true after we create the instance.
bool instanceInitialized = false;
CtorEvalExternalInterface(
std::map<Name, std::shared_ptr<EvallingModuleRunner>> linkedInstances_ =
{}) {
linkedInstances.swap(linkedInstances_);
}
// Called when we want to apply the current state of execution to the Module.
// Until this is called the Module is never changed.
void applyToModule() {
clearApplyState();
// If nothing was ever written to memories then there is nothing to update.
if (!memories.empty()) {
applyMemoryToModule();
}
applyGlobalsToModule();
}
void init(Module& wasm_, EvallingModuleRunner& instance_) override {
wasm = &wasm_;
instance = &instance_;
for (auto& memory : wasm->memories) {
if (!memory->imported()) {
std::vector<char> data;
memories[memory->name] = data;
}
}
for (auto& global : wasm->globals) {
usedGlobalNames.insert(global->name);
}
}
void importGlobals(GlobalValueSet& globals, Module& wasm_) override {
ModuleUtils::iterImportedGlobals(wasm_, [&](Global* global) {
auto it = linkedInstances.find(global->module);
if (it != linkedInstances.end()) {
auto* inst = it->second.get();
auto* globalExport = inst->wasm.getExportOrNull(global->base);
if (!globalExport) {
throw FailToEvalException(std::string("importGlobals: ") +
global->module.toString() + "." +
global->base.toString());
}
globals[global->name] = inst->globals[globalExport->value];
} else {
throw FailToEvalException(std::string("importGlobals: ") +
global->module.toString() + "." +
global->base.toString());
}
});
}
Literals callImport(Function* import, const Literals& arguments) override {
Name WASI("wasi_snapshot_preview1");
if (ignoreExternalInput) {
if (import->module == WASI) {
if (import->base == "environ_sizes_get") {
if (arguments.size() != 2 || arguments[0].type != Type::i32 ||
import->getResults() != Type::i32) {
throw FailToEvalException("wasi environ_sizes_get has wrong sig");
}
// Write out a count of i32(0) and return __WASI_ERRNO_SUCCESS (0).
store32(arguments[0].geti32(), 0, wasm->memories[0]->name);
return {Literal(int32_t(0))};
}
if (import->base == "environ_get") {
if (arguments.size() != 2 || arguments[0].type != Type::i32 ||
import->getResults() != Type::i32) {
throw FailToEvalException("wasi environ_get has wrong sig");
}
// Just return __WASI_ERRNO_SUCCESS (0).
return {Literal(int32_t(0))};
}
if (import->base == "args_sizes_get") {
if (arguments.size() != 2 || arguments[0].type != Type::i32 ||
import->getResults() != Type::i32) {
throw FailToEvalException("wasi args_sizes_get has wrong sig");
}
// Write out an argc of i32(0) and return a __WASI_ERRNO_SUCCESS (0).
store32(arguments[0].geti32(), 0, wasm->memories[0]->name);
return {Literal(int32_t(0))};
}
if (import->base == "args_get") {
if (arguments.size() != 2 || arguments[0].type != Type::i32 ||
import->getResults() != Type::i32) {
throw FailToEvalException("wasi args_get has wrong sig");
}
// Just return __WASI_ERRNO_SUCCESS (0).
return {Literal(int32_t(0))};
}
// Otherwise, we don't recognize this import; continue normally to
// error.
}
}
std::string extra;
if (import->module == ENV && import->base == "___cxa_atexit") {
extra = RECOMMENDATION "build with -s NO_EXIT_RUNTIME=1 so that calls "
"to atexit are not emitted";
} else if (import->module == WASI && !ignoreExternalInput) {
extra = RECOMMENDATION "consider --ignore-external-input";
}
throw FailToEvalException(std::string("call import: ") +
import->module.toString() + "." +
import->base.toString() + extra);
}
// We assume the table is not modified FIXME
Literals callTable(Name tableName,
Address index,
HeapType sig,
Literals& arguments,
Type result,
EvallingModuleRunner& instance) override {
std::unordered_map<wasm::Name, std::vector<wasm::Name>>::iterator it;
auto* table = wasm->getTableOrNull(tableName);
if (!table) {
throw FailToEvalException("callTable on non-existing table");
}
// Look through the segments and find the function. Segments can overlap,
// so we want the last one.
Name targetFunc;
for (auto& segment : wasm->elementSegments) {
if (segment->table != tableName) {
continue;
}
Index start;
// look for the index in this segment. if it has a constant offset, we
// look in the proper range. if it instead gets a global, we rely on the
// fact that when not dynamically linking then the table is loaded at
// offset 0.
if (auto* c = segment->offset->dynCast<Const>()) {
start = c->value.getInteger();
} else if (segment->offset->is<GlobalGet>()) {
start = 0;
} else {
// wasm spec only allows const and global.get there
WASM_UNREACHABLE("invalid expr type");
}
auto end = start + segment->data.size();
if (start <= index && index < end) {
auto entry = segment->data[index - start];
if (auto* get = entry->dynCast<RefFunc>()) {
targetFunc = get->func;
} else {
throw FailToEvalException(
std::string("callTable on uninitialized entry"));
}
}
}
if (!targetFunc.is()) {
throw FailToEvalException(
std::string("callTable on index not found in static segments: ") +
std::to_string(index));
}
// If this is one of our functions, we can call it; if it was
// imported, fail.
auto* func = wasm->getFunction(targetFunc);
if (func->type != sig) {
throw FailToEvalException(std::string("callTable signature mismatch: ") +
targetFunc.toString());
}
if (!func->imported()) {
return instance.callFunction(targetFunc, arguments);
} else {
throw FailToEvalException(
std::string("callTable on imported function: ") +
targetFunc.toString());
}
}
Index tableSize(Name tableName) override {
// See callTable above, we assume the table is not modified FIXME
return wasm->getTableOrNull(tableName)->initial;
}
Literal tableLoad(Name tableName, Address index) override {
throw FailToEvalException("table.get: TODO");
}
// called during initialization
void
tableStore(Name tableName, Address index, const Literal& value) override {
// We allow stores to the table during initialization, but not after, as we
// assume the table does not change at runtime.
// TODO: Allow table changes by updating the table later like we do with the
// memory, by tracking and serializing them.
if (instanceInitialized) {
throw FailToEvalException("tableStore after init: TODO");
}
}
int8_t load8s(Address addr, Name memoryName) override {
return doLoad<int8_t>(addr, memoryName);
}
uint8_t load8u(Address addr, Name memoryName) override {
return doLoad<uint8_t>(addr, memoryName);
}
int16_t load16s(Address addr, Name memoryName) override {
return doLoad<int16_t>(addr, memoryName);
}
uint16_t load16u(Address addr, Name memoryName) override {
return doLoad<uint16_t>(addr, memoryName);
}
int32_t load32s(Address addr, Name memoryName) override {
return doLoad<int32_t>(addr, memoryName);
}
uint32_t load32u(Address addr, Name memoryName) override {
return doLoad<uint32_t>(addr, memoryName);
}
int64_t load64s(Address addr, Name memoryName) override {
return doLoad<int64_t>(addr, memoryName);
}
uint64_t load64u(Address addr, Name memoryName) override {
return doLoad<uint64_t>(addr, memoryName);
}
std::array<uint8_t, 16> load128(Address addr, Name memoryName) override {
return doLoad<std::array<uint8_t, 16>>(addr, memoryName);
}
void store8(Address addr, int8_t value, Name memoryName) override {
doStore<int8_t>(addr, value, memoryName);
}
void store16(Address addr, int16_t value, Name memoryName) override {
doStore<int16_t>(addr, value, memoryName);
}
void store32(Address addr, int32_t value, Name memoryName) override {
doStore<int32_t>(addr, value, memoryName);
}
void store64(Address addr, int64_t value, Name memoryName) override {
doStore<int64_t>(addr, value, memoryName);
}
void store128(Address addr,
const std::array<uint8_t, 16>& value,
Name memoryName) override {
doStore<std::array<uint8_t, 16>>(addr, value, memoryName);
}
bool growMemory(Name memoryName,
Address /*oldSize*/,
Address /*newSize*/) override {
throw FailToEvalException("grow memory");
}
bool growTable(Name /*name*/,
const Literal& /*value*/,
Index /*oldSize*/,
Index /*newSize*/) override {
throw FailToEvalException("grow table");
}
void trap(const char* why) override {
throw FailToEvalException(std::string("trap: ") + why);
}
void hostLimit(const char* why) override {
throw FailToEvalException(std::string("trap: ") + why);
}
void throwException(const WasmException& exn) override {
std::stringstream ss;
ss << "exception thrown: " << exn;
throw FailToEvalException(ss.str());
}
private:
// We limit the size of memory to some reasonable amount. We handle memory in
// a linear/dense manner, so when we see a write to address X we allocate X
// memory to represent that, and so very high addresses can lead to OOM. In
// practice, ctor-eval should only run on low addresses anyhow, since static
// memory tends to be reasonably-sized and mallocs start at the start of the
// heap, so it's simpler to add an arbitrary limit here to avoid OOMs for now.
const size_t MaximumMemory = 100 * 1024 * 1024;
// TODO: handle unaligned too, see shell-interface
template<typename T> T* getMemory(Address address, Name memoryName) {
auto it = memories.find(memoryName);
assert(it != memories.end());
auto& memory = it->second;
// resize the memory buffer as needed.
auto max = address + sizeof(T);
if (max > memory.size()) {
if (max > MaximumMemory) {
throw FailToEvalException("excessively high memory address accessed");
}
memory.resize(max);
}
return (T*)(&memory[address]);
}
template<typename T> void doStore(Address address, T value, Name memoryName) {
// do a memcpy to avoid undefined behavior if unaligned
memcpy(getMemory<T>(address, memoryName), &value, sizeof(T));
}
template<typename T> T doLoad(Address address, Name memoryName) {
// do a memcpy to avoid undefined behavior if unaligned
T ret;
memcpy(&ret, getMemory<T>(address, memoryName), sizeof(T));
return ret;
}
// Clear the state of the operation of applying the interpreter's runtime
// information into the module.
//
// This happens each time we apply contents to the module, which is basically
// once per ctor function, but can be more fine-grained also if we execute a
// line at a time.
void clearApplyState() {
// The process of allocating "defining globals" begins here, from scratch
// each time (things live before may no longer be).
definingGlobals.clear();
// Clear any startup operations as well (which may apply to globals that
// become no longer live; we'll create new start operations as we need
// them).
clearStartBlock();
}
void applyMemoryToModule() {
// Memory must have already been flattened into the standard form: one
// segment at offset 0, or none.
auto& memory = wasm->memories[0];
if (wasm->dataSegments.empty()) {
Builder builder(*wasm);
auto curr = builder.makeDataSegment();
curr->offset =
builder.makeConst(Literal::makeFromInt32(0, memory->addressType));
curr->setName(Name::fromInt(0), false);
curr->memory = memory->name;
wasm->addDataSegment(std::move(curr));
}
auto& segment = wasm->dataSegments[0];
assert(segment->offset->cast<Const>()->value.getInteger() == 0);
// Copy the current memory contents after execution into the Module's
// memory.
segment->data = memories[memory->name];
}
// Serializing GC data requires more work than linear memory, because
// allocations have an identity, and they are created using struct.new /
// array.new, which we must emit in a proper location in the wasm. This
// affects how we serialize globals, which can contain GC data, and also, we
// use globals to store GC data, so overall the process of computing the
// globals is where most of the GC logic ends up.
//
// The general idea for handling GC data is as follows: After evaluating the
// code, we end up with some live allocations in the interpreter, which we
// need to somehow serialize into the wasm module. We will put each such live
// GC data item into its own "defining global", a global whose purpose is to
// create and store that data. Each such global is immutable, and has the
// exact type of the data, for simplicity. Every other reference to that GC
// data in the interpreter's memory can then be serialized by simply emitting
// a global.get of that defining global.
void applyGlobalsToModule() {
if (!wasm->features.hasGC()) {
// Without GC, we can simply serialize the globals in place as they are.
for (const auto& [name, values] : instance->globals) {
wasm->getGlobal(name)->init = getSerialization(values);
}
return;
}
// We need to emit the "defining globals" of GC data before the existing
// globals, as the normal ones may refer to them. We do this by removing all
// the existing globals, and then adding them one by one, during which time
// we call getSerialization() for their init expressions. If their init
// refes to GC data, then we will allocate a defining global for that data,
// and refer to it. Put another way, we place the existing globals back into
// the module one at a time, adding their dependencies as we go.
auto oldGlobals = std::move(wasm->globals);
// After clearing the globals vector, clear the map as well.
wasm->updateMaps();
for (auto& oldGlobal : oldGlobals) {
// Serialize the global's value. While doing so, pass in the name of this
// global, as we may be able to reuse the global as the defining global
// for the value. See getSerialization() for more details.
Name name;
if (!oldGlobal->mutable_ && oldGlobal->type == oldGlobal->init->type) {
// This has the properties we need of a defining global - immutable and
// of the precise type - so use it as such.
name = oldGlobal->name;
}
// If the instance has an evalled value here, compute the serialization
// for it. (If there is no value, then this is a new global we've added
// during execution, for whom we've already set up a proper serialized
// value when we created it.)
auto iter = instance->globals.find(oldGlobal->name);
if (iter != instance->globals.end()) {
oldGlobal->init = getSerialization(iter->second, name);
}
// Add the global back to the module.
wasm->addGlobal(std::move(oldGlobal));
}
// Finally, we need to fix up cycles. The serialization we just emitted
// ignores them, so we can end up with things like this:
//
// (global $a (struct.new $A (global.get $a)))
//
// That global refers to an object that should have a self-reference, and
// the serialization logic simply emits global.gets for all references, so
// we end up with a situation like this where a global.get refers to a
// global before it is valid to do so. To fix this up, we can reorder
// globals as needed, and break up cycles by writing a null in the initial
// struct.new in the global's definition, and later in the start function we
// can perform additional struct.sets that cause cycles to form.
//
// The existing algorithm here is rather simple: we find things that
// definitely force a certain order and sort according to them. Then in that
// order we break forward references with fixups as described above. This is
// not always the best, as there may be a more optimal order, and we may end
// up doing more fixups than are absolutely necessary, but this algorithm is
// simple and works in linear time (or nlogn including the sort). The
// general problem here is NP-hard (the maximum acyclic subgraph problem),
// but there are probably greedy algorithms we could consider if we need to
// do better.
Builder builder(*wasm);
// First, find what constraints we have on the ordering of the globals. We
// will build up a map of each global to the globals it must be before.
using MustBeBefore = InsertOrderedMap<Name, InsertOrderedSet<Name>>;
MustBeBefore mustBeBefore;
for (auto& global : wasm->globals) {
if (!global->init) {
continue;
}
struct InitScanner : PostWalker<InitScanner> {
// All the global.gets that we can't fix up by replacing the value with
// a null and adding a set in the start function. These will be hard
// constraints on our sorting (if we could fix things up with a null +
// set then we would not need to reorder).
InsertOrderedSet<GlobalGet*> unfixableGets;
void visitGlobalGet(GlobalGet* curr) {
// Assume this is unfixable, unless we reach the parent and see that
// it is.
unfixableGets.insert(curr);
}
// Checks if a child is a global.get that we need to handle, and if we
// can fix it if so. The index is the position of the child in the
// parent (which is 0 for all array children, as their position does not
// matter, they all have the same field info).
void handleChild(Expression* child,
Expression* parent,
Index fieldIndex = 0) {
if (!child) {
return;
}
if (auto* get = child->dynCast<GlobalGet>()) {
if (isNullableAndMutable(parent, fieldIndex)) {
// We can replace the child with a null, and set the value later
// (in the start function), so this is not a constraint on our
// sorting - we'll just fix it up later, and the order won't be
// an issue.
unfixableGets.erase(get);
}
}
}
void visitStructNew(StructNew* curr) {
Index i = 0;
for (auto* child : curr->operands) {
handleChild(child, curr, i++);
}
}
void visitArrayNew(ArrayNew* curr) { handleChild(curr->init, curr); }
void visitArrayNewFixed(ArrayNewFixed* curr) {
for (auto* child : curr->values) {
handleChild(child, curr);
}
}
};
InitScanner scanner;
scanner.walk(global->init);
// Any global.gets that cannot be fixed up are constraints.
for (auto* get : scanner.unfixableGets) {
mustBeBefore[global->name];
mustBeBefore[get->name].insert(global->name);
}
}
if (!mustBeBefore.empty()) {
auto oldGlobals = std::move(wasm->globals);
// After clearing the globals vector, clear the map as well.
wasm->updateMaps();
std::unordered_map<Name, Index> globalIndexes;
for (Index i = 0; i < oldGlobals.size(); i++) {
globalIndexes[oldGlobals[i]->name] = i;
}
// Add the globals that had an important ordering, in the right order.
for (auto global :
TopologicalSort::sortOf(mustBeBefore.begin(), mustBeBefore.end())) {
wasm->addGlobal(std::move(oldGlobals[globalIndexes[global]]));
}
// Add all other globals after them.
for (auto& global : oldGlobals) {
if (global) {
wasm->addGlobal(std::move(global));
}
}
}
// After sorting (*), perform the fixups that we need, that is, replace the
// relevant fields in cycles with a null and prepare a set in the start
// function.
//
// We'll track the set of readable globals as we go (which are the globals
// we've seen already, and fully finished processing).
//
// (*) Note that we may need these fixups even if we didn't need to do any
// sorting. There may be a single global with a cycle in it, for
// example.
std::unordered_set<Name> readableGlobals;
for (auto& global : wasm->globals) {
if (!global->init) {
continue;
}
struct InitFixer : PostWalker<InitFixer> {
CtorEvalExternalInterface& evaller;
std::unique_ptr<Global>& global;
std::unordered_set<Name>& readableGlobals;
InitFixer(CtorEvalExternalInterface& evaller,
std::unique_ptr<Global>& global,
std::unordered_set<Name>& readableGlobals)
: evaller(evaller), global(global), readableGlobals(readableGlobals) {
}
// Handles a child by fixing things up if needed. Returns true if we
// did in fact fix things up.
bool handleChild(Expression*& child,
Expression* parent,
Index fieldIndex = 0) {
if (!child) {
return false;
}
if (auto* get = child->dynCast<GlobalGet>()) {
if (!readableGlobals.count(get->name)) {
// This get cannot be read - it is a global that appears after
// us - and so we must fix it up, using the method mentioned
// before (setting it to null now, and later in the start
// function writing to it).
assert(isNullableAndMutable(parent, fieldIndex));
evaller.addStartFixup(
{global->name, global->type}, fieldIndex, get);
child =
Builder(*getModule()).makeRefNull(get->type.getHeapType());
return true;
}
}
return false;
}
// This code will need to be updated for all new GC-creating
// instructions that we use when serializing GC data, that is, things we
// put in defining globals. (All other instructions, even constant ones
// in globals, will simply end up referring to them using a global.get,
// but will not be referred to. That is, cycles will only appear in
// defining globals.)
void visitStructNew(StructNew* curr) {
Index i = 0;
for (auto*& child : curr->operands) {
handleChild(child, curr, i++);
}
}
void visitArrayNew(ArrayNew* curr) {
if (handleChild(curr->init, curr)) {
// Handling array.new is tricky as the number of items may be
// unknown at compile time, so we'd need to loop at runtime. But,
// in practice we emit an array.new_fixed anyhow, so this should
// not be needed for now.
WASM_UNREACHABLE("TODO: ArrayNew in ctor-eval cycles");
}
}
void visitArrayNewFixed(ArrayNewFixed* curr) {
Index i = 0;
for (auto*& child : curr->values) {
handleChild(child, curr, i++);
}
}
};
InitFixer fixer(*this, global, readableGlobals);
fixer.setModule(wasm);
fixer.walk(global->init);
// Only after we've fully processed this global is it ok to be read from
// by later globals.
readableGlobals.insert(global->name);
}
}
public:
// Maps each GC data in the interpreter to its defining global: the global in
// which it is created, and then all other users of it can just global.get
// that. For each such global we track its name and type.
struct DefiningGlobalInfo {
Name name;
Type type;
};
std::unordered_map<GCData*, DefiningGlobalInfo> definingGlobals;
// If |possibleDefiningGlobal| is provided, it is the name of a global that we
// are in the init expression of, and which can be reused as defining global,
// if the other conditions are suitable.
Expression* getSerialization(Literal value,
Name possibleDefiningGlobal = Name()) {
Builder builder(*wasm);
// If this is externalized then we want to inspect the inner data, handle
// that, and emit a ref.externalize around it as needed. To simplify the
// logic here, we save the original (possible externalized) value, and then
// look at the internals from here on out.
Literal original = value;
if (value.type.isRef() &&
value.type.getHeapType().isMaybeShared(HeapType::ext)) {
value = value.internalize();
// We cannot serialize truly external things, only data and i31s.
assert(value.isData() ||
value.type.getHeapType().isMaybeShared(HeapType::i31));
}
// GC data (structs and arrays) must be handled with the special global-
// creating logic later down. But MVP types as well as i31s (even
// externalized i31s) can be handled by the general makeConstantExpression
// logic (which knows how to handle externalization, for i31s; and it also
// can handle string constants).
if (!value.isData() || value.isString()) {
return builder.makeConstantExpression(original);
}
// This is GC data, which we must handle in a more careful way.
auto* data = value.getGCData().get();
assert(data);
auto type = value.type;
Name definingGlobalName;
if (auto it = definingGlobals.find(data); it != definingGlobals.end()) {
// Use the existing defining global.
definingGlobalName = it->second.name;
} else {
// This is the first usage of this data. Generate a struct.new /
// array.new for it.
auto& values = value.getGCData()->values;
std::vector<Expression*> args;
// The initial values for this allocation may themselves be GC
// allocations. Recurse and add globals as necessary. First, pick the
// global name (note that we must do so first, as we may need to read from
// definingGlobals to find where this global will be, in the case of a
// cycle; see below).
if (possibleDefiningGlobal.is()) {
// No need to allocate a new global, as we are in the definition of
// one, which will be the defining global.
definingGlobals[data] =
DefiningGlobalInfo{possibleDefiningGlobal, type};
definingGlobalName = possibleDefiningGlobal;
} else {
// Allocate a new defining global.
definingGlobalName =
Names::getValidNameGivenExisting("ctor-eval$global", usedGlobalNames);
usedGlobalNames.insert(definingGlobalName);
definingGlobals[data] = DefiningGlobalInfo{definingGlobalName, type};
}
for (auto& value : values) {
args.push_back(getSerialization(value));
}
Expression* init;
auto heapType = type.getHeapType();
if (heapType.isStruct()) {
init = builder.makeStructNew(heapType, args);
} else if (heapType.isArray()) {
// TODO: for repeated identical values, can use ArrayNew
init = builder.makeArrayNewFixed(heapType, args);
} else {
WASM_UNREACHABLE("bad gc type");
}
if (possibleDefiningGlobal.is()) {
// We didn't need to allocate a new global, as we are in the definition
// of one, so just return the initialization expression, which will be
// placed in that global's |init| field.
return init;
}
// There is no existing defining global, so we must allocate a new one.
//
// We set the global's init to null temporarily, and we'll fix it up
// later down after we create the init expression.
wasm->addGlobal(
builder.makeGlobal(definingGlobalName, type, init, Builder::Immutable));
}
// Refer to this GC allocation by reading from the global that is
// designated to contain it.
Expression* ret = builder.makeGlobalGet(definingGlobalName, value.type);
if (original != value) {
// The original is externalized.
assert(original.type.getHeapType().isMaybeShared(HeapType::ext));
ret = builder.makeRefAs(ExternConvertAny, ret);
}
return ret;
}
Expression* getSerialization(const Literals& values,
Name possibleDefiningGlobal = Name()) {
if (values.size() > 1) {
// We do not support multivalues in defining globals, which store GC refs.
assert(possibleDefiningGlobal.isNull());
std::vector<Expression*> children;
for (const auto& value : values) {
children.push_back(getSerialization(value));
}
return Builder(*wasm).makeTupleMake(children);
}
assert(values.size() == 1);
return getSerialization(values[0], possibleDefiningGlobal);
}
// This is called when we hit a cycle in setting up defining globals. For
// example, if the data we want to emit is
//
// global globalA = new A{ field = &A }; // A has a reference to itself
//
// then we'll emit
//
// global globalA = new A{ field = null };
//
// and put this in the start function:
//
// globalA.field = globalA;
//
// The parameters here are a global and a field index to that global, and the
// global we want to assign to it, that is, our goal is to have
//
// global[index] = valueGlobal
//
// run during the start function.
void addStartFixup(DefiningGlobalInfo global, Index index, GlobalGet* value) {
if (!startBlock) {
createStartBlock();
}
Builder builder(*wasm);
auto* getGlobal = builder.makeGlobalGet(global.name, global.type);
Expression* set;
if (global.type.isStruct()) {
set = builder.makeStructSet(index, getGlobal, value);
} else {
set = builder.makeArraySet(
getGlobal, builder.makeConst(int32_t(index)), value);
}
(*startBlock)->list.push_back(set);
}
// A block in the start function where we put the operations we need to occur
// during startup.
std::optional<Block*> startBlock;
void createStartBlock() {
Builder builder(*wasm);
startBlock = builder.makeBlock();
if (wasm->start.is()) {
// Put our block before any user start code.
auto* existingStart = wasm->getFunction(wasm->start);
existingStart->body =
builder.makeSequence(*startBlock, existingStart->body);
} else {
// Make a new start function.
wasm->start = Names::getValidFunctionName(*wasm, "start");
wasm->addFunction(builder.makeFunction(
wasm->start, Signature{Type::none, Type::none}, {}, *startBlock));
}
}
void clearStartBlock() {
if (startBlock) {
(*startBlock)->list.clear();
}
}
};
// Whether to emit informative logging to stdout about the eval process.
static bool quiet = false;
// The outcome of evalling a ctor is one of three states:
//
// 1. We failed to eval it completely (but perhaps we succeeded partially). In
// that case the std::optional here contains nothing.
// 2. We evalled it completely, and it is a function with no return value, so
// it contains an empty Literals.
// 3. We evalled it completely, and it is a function with a return value, so
// it contains Literals with those results.
using EvalCtorOutcome = std::optional<Literals>;
// Eval a single ctor function. Returns whether we succeeded to completely
// evaluate the ctor (which means that the caller can proceed to try to eval
// further ctors if there are any), and if we did, the results if the function
// returns any.
EvalCtorOutcome evalCtor(EvallingModuleRunner& instance,
CtorEvalExternalInterface& interface,
Name funcName,
Name exportName) {
auto& wasm = instance.wasm;
auto* func = wasm.getFunction(funcName);
if (func->imported()) {
// We cannot evaluate an import.
if (!quiet) {
std::cout << " ...stopping since could not eval: call import: "
<< func->module.toString() << "." << func->base.toString()
<< '\n';
}
return EvalCtorOutcome();
}
// We don't know the values of parameters, so give up if there are any, unless
// we are ignoring them.
if (func->getNumParams() > 0 && !ignoreExternalInput) {
if (!quiet) {
std::cout << " ...stopping due to params\n";
std::cout << RECOMMENDATION "consider --ignore-external-input";
}
return EvalCtorOutcome();
}
// If there are params, we are ignoring them (or we would have quit earlier);
// set those up with zeros.
// TODO: Have a safer option here, either
// 1. Statically or dynamically stop evalling when a param is actually
// used, or
// 2. Split out --ignore-external-input into separate flags.
Literals params;
for (Index i = 0; i < func->getNumParams(); i++) {
auto type = func->getLocalType(i);
if (!LiteralUtils::canMakeZero(type)) {
if (!quiet) {
std::cout << " ...stopping due to non-zeroable param\n";
}
return EvalCtorOutcome();
}
params.push_back(Literal::makeZero(type));
}
// After we successfully eval a line we will store the operations to set up
// the locals here. That is, we need to save the local state in the function,
// which we do by setting up at the entry. We update this list of expressions
// at the same time as applyToModule() - we must only do it after an entire
// atomic "chunk" has been processed succesfully, we do not want partial
// updates from an item in the block that we only partially evalled. When we
// construct the (partially) evalled function, we will create local.sets of
// these expressions at the beginning.
std::vector<Expression*> localExprs;
// We might have to evaluate multiple functions due to return calls.
start_eval:
while (true) {
// We want to handle the form of the global constructor function in LLVM.
// That looks like this:
//
// (func $__wasm_call_ctors
// (call $ctor.1)
// (call $ctor.2)
// (call $ctor.3)
// )
//
// Some of those ctors may be inlined, however, which would mean that the
// function could have locals, control flow, etc. However, we assume for now
// that it does not have parameters at least (whose values we can't tell).
// And for now we look for a toplevel block and process its children one at
// a time. This allows us to eval some of the $ctor.* functions (or their
// inlined contents) even if not all.
//
// TODO: Support complete partial evalling, that is, evaluate parts of an
// arbitrary function, and not just a sequence in a single toplevel
// block.
Builder builder(wasm);
auto* block = builder.blockify(func->body);
// Go through the items in the block and try to execute them. We do all this
// in a single function scope for all the executions.
EvallingModuleRunner::FunctionScope scope(func, params, instance);
Literals results;
Index successes = 0;
for (auto* curr : block->list) {
Flow flow;
try {
flow = instance.visit(curr);
} catch (FailToEvalException& fail) {
if (!quiet) {
if (successes == 0) {
std::cout << " ...stopping (in block) since could not eval: "
<< fail.why << "\n";
} else {
std::cout << " ...partial evalling successful, but stopping since "
"could not eval: "
<< fail.why << "\n";
}
}
break;
}
if (flow.breakTo == RETURN_CALL_FLOW) {
// The return-called function is stored in the last value.
func = wasm.getFunction(flow.values.back().getFunc());
flow.values.pop_back();
params = std::move(flow.values);
// Serialize the arguments for the new function and save the module
// state in case we fail to eval the new function.
localExprs.clear();
for (auto& param : params) {
localExprs.push_back(interface.getSerialization(param));
}
interface.applyToModule();
goto start_eval;
}
// So far so good! Serialize the values of locals, and apply to the
// module. Note that we must serialize the locals now as doing so may
// cause changes that must be applied to the module (e.g. GC data may
// cause globals to be added). And we must apply to the module now, and
// not later, as we must do so right after a successfull partial eval
// (after any failure to eval, the global state is no long valid to be
// applied to the module, as incomplete changes may have occurred).
//
// Note that we make no effort to optimize locals: we just write out all
// of them, and leave it to the optimizer to remove redundant or
// unnecessary operations. We just recompute the entire local
// serialization sets from scratch each time here, for all locals.
localExprs.clear();
for (Index i = 0; i < func->getNumLocals(); i++) {
localExprs.push_back(interface.getSerialization(scope.locals[i]));
}
interface.applyToModule();
successes++;
// Note the values here, if any. If we are exiting the function now then
// these will be returned.
results = flow.values;
if (flow.breaking()) {
// We are returning out of the function (either via a return, or via a
// break to |block|, which has the same outcome. That means we don't
// need to execute any more lines, and can consider them to be
// executed.
if (!quiet) {
std::cout << " ...stopping in block due to break\n";
}
// Mark us as having succeeded on the entire block, since we have: we
// are skipping the rest, which means there is no problem there. We
// must set this here so that lower down we realize that we've evalled
// everything.
successes = block->list.size();
break;
}
}
// If we have not fully evaluated the current function, but we have
// evaluated part of it, have return-called to a different function, or have
// precomputed values for the current return-called function, then we can
// replace the export with a new function that does less work than the
// original.
if ((func->imported() || successes < block->list.size()) &&
(successes > 0 || func->name != funcName ||
(localExprs.size() && func->getParams() != Type::none))) {
auto originalFuncType = wasm.getFunction(funcName)->type;
auto copyName = Names::getValidFunctionName(wasm, funcName);
wasm.getExport(exportName)->value = copyName;
if (func->imported()) {
// We must have return-called this imported function. Generate a new
// function that return-calls the import with the arguments we have
// evalled.
auto copyFunc = builder.makeFunction(
copyName,
originalFuncType,
{},
builder.makeCall(func->name, localExprs, func->getResults(), true));
wasm.addFunction(std::move(copyFunc));
return EvalCtorOutcome();
}
// We may have managed to eval some but not all. That means we can't just
// remove the entire function, but need to keep parts of it - the parts we
// have not evalled - around. To do so, we create a copy of the function
// with the partially-evalled contents and make the export use that (as
// the function may be used in other places than the export, which we do
// not want to affect).
auto* copyBody =
builder.blockify(ExpressionManipulator::copy(func->body, wasm));
// Remove the items we've evalled.
for (Index i = 0; i < successes; i++) {
copyBody->list[i] = builder.makeNop();
}
// Put the local sets at the front of the function body.
auto* setsBlock = builder.makeBlock();
for (Index i = 0; i < localExprs.size(); ++i) {
setsBlock->list.push_back(builder.makeLocalSet(i, localExprs[i]));
}
copyBody = builder.makeSequence(setsBlock, copyBody, copyBody->type);
// We may have return-called into a function with different parameter
// types, but we ultimately need to export a function with the original
// signature. If there is a mismatch, shift the local indices to make room
// for the unused parameters.
std::vector<Type> localTypes;
auto originalParams = originalFuncType.getSignature().params;
if (originalParams != func->getParams()) {
// Add locals for the body to use instead of using the params.
for (auto type : func->getParams()) {
localTypes.push_back(type);
}
// Shift indices in the body so they will refer to the new locals.
auto localShift = originalParams.size();
if (localShift != 0) {
for (auto* get : FindAll<LocalGet>(copyBody).list) {
get->index += localShift;
}
for (auto* set : FindAll<LocalSet>(copyBody).list) {
set->index += localShift;
}
}
}
// Add vars from current function.
localTypes.insert(localTypes.end(), func->vars.begin(), func->vars.end());
// Create and add the new function.
auto* copyFunc = wasm.addFunction(builder.makeFunction(
copyName, originalFuncType, std::move(localTypes), copyBody));
// Interesting optimizations may be possible both due to removing some but
// not all of the code, and due to the locals we just added.
PassRunner passRunner(&wasm,
PassOptions::getWithDefaultOptimizationOptions());
passRunner.addDefaultFunctionOptimizationPasses();
passRunner.runOnFunction(copyFunc);
}
// Return true if we evalled the entire block. Otherwise, even if we evalled
// some of it, the caller must stop trying to eval further things.
if (successes == block->list.size()) {
return EvalCtorOutcome(results);
} else {
return EvalCtorOutcome();
}
}
}
// Eval all ctors in a module.
void evalCtors(Module& wasm,
std::vector<std::string>& ctors,
std::vector<std::string>& keptExports) {
std::unordered_set<std::string> keptExportsSet(keptExports.begin(),
keptExports.end());
std::map<Name, std::shared_ptr<EvallingModuleRunner>> linkedInstances;
// build and link the env module
auto envModule = buildEnvModule(wasm);
CtorEvalExternalInterface envInterface;
auto envInstance =
std::make_shared<EvallingModuleRunner>(*envModule, &envInterface);
linkedInstances[envModule->name] = envInstance;
CtorEvalExternalInterface interface(linkedInstances);
try {
// create an instance for evalling
EvallingModuleRunner instance(wasm, &interface, linkedInstances);
interface.instanceInitialized = true;
// go one by one, in order, until we fail
// TODO: if we knew priorities, we could reorder?
for (auto& ctor : ctors) {
if (!quiet) {
std::cout << "trying to eval " << ctor << '\n';
}
Export* ex = wasm.getExportOrNull(ctor);
if (!ex) {
Fatal() << "export not found: " << ctor;
}
auto funcName = ex->value;
auto outcome = evalCtor(instance, interface, funcName, ctor);
if (!outcome) {
if (!quiet) {
std::cout << " ...stopping\n";
}
return;
}
// Success! And we can continue to try more.
if (!quiet) {
std::cout << " ...success on " << ctor << ".\n";
}
// Remove the export if we should.
auto* exp = wasm.getExport(ctor);
if (!keptExportsSet.count(ctor)) {
wasm.removeExport(exp->name);
} else {
// We are keeping around the export, which should now refer to an
// empty function since calling the export should do nothing.
auto* func = wasm.getFunction(exp->value);
auto copyName = Names::getValidFunctionName(wasm, func->name);
auto* copyFunc = ModuleUtils::copyFunction(func, wasm, copyName);
if (func->getResults() == Type::none) {
copyFunc->body = Builder(wasm).makeNop();
} else {
copyFunc->body = interface.getSerialization(*outcome);
}
wasm.getExport(exp->name)->value = copyName;
}
}
} catch (FailToEvalException& fail) {
// that's it, we failed to even create the instance
if (!quiet) {
std::cout << " ...stopping since could not create module instance: "
<< fail.why << "\n";
}
return;
}
}
static bool canEval(Module& wasm) {
// Check if we can flatten memory. We need to do so currently because of how
// we assume memory is simple and flat. TODO
if (!MemoryUtils::flatten(wasm)) {
if (!quiet) {
std::cout << " ...stopping since could not flatten memory\n";
}
return false;
}
return true;
}
} // anonymous namespace
//
// main
//
int main(int argc, const char* argv[]) {
Name entry;
std::vector<std::string> passes;
bool emitBinary = true;
bool debugInfo = false;
String::Split ctors;
String::Split keptExports;
const std::string WasmCtorEvalOption = "wasm-ctor-eval options";
ToolOptions options("wasm-ctor-eval", "Execute code at compile time");
options
.add("--output",
"-o",
"Output file (stdout if not specified)",
WasmCtorEvalOption,
Options::Arguments::One,
[](Options* o, const std::string& argument) {
o->extra["output"] = argument;
Colors::setEnabled(false);
})
.add("--emit-text",
"-S",
"Emit text instead of binary for the output file",
WasmCtorEvalOption,
Options::Arguments::Zero,
[&](Options* o, const std::string& argument) { emitBinary = false; })
.add("--debuginfo",
"-g",
"Emit names section and debug info",
WasmCtorEvalOption,
Options::Arguments::Zero,
[&](Options* o, const std::string& arguments) { debugInfo = true; })
.add("--ctors",
"-c",
"Comma-separated list of global constructor functions to evaluate",
WasmCtorEvalOption,
Options::Arguments::One,
[&](Options* o, const std::string& argument) {
ctors = String::Split(argument, ",");
})
.add(
"--kept-exports",
"-ke",
"Comma-separated list of ctors whose exports we keep around even if we "
"eval those ctors",
WasmCtorEvalOption,
Options::Arguments::One,
[&](Options* o, const std::string& argument) {
keptExports = String::Split(argument, ",");
})
.add("--ignore-external-input",
"-ipi",
"Assumes no env vars are to be read, stdin is empty, etc.",
WasmCtorEvalOption,
Options::Arguments::Zero,
[&](Options* o, const std::string& argument) {
ignoreExternalInput = true;
})
.add("--quiet",
"-q",
"Do not emit verbose logging about the eval process",
WasmCtorEvalOption,
Options::Arguments::Zero,
[&](Options* o, const std::string& argument) { quiet = true; })
.add_positional("INFILE",
Options::Arguments::One,
[](Options* o, const std::string& argument) {
o->extra["infile"] = argument;
});
options.parse(argc, argv);
Module wasm;
options.applyOptionsBeforeParse(wasm);
{
if (options.debug) {
std::cout << "reading...\n";
}
ModuleReader reader;
try {
reader.read(options.extra["infile"], wasm);
} catch (ParseException& p) {
p.dump(std::cout);
Fatal() << "error in parsing input";
}
}
options.applyOptionsAfterParse(wasm);
if (!WasmValidator().validate(wasm)) {
std::cout << wasm << '\n';
Fatal() << "error in validating input";
}
if (canEval(wasm)) {
evalCtors(wasm, ctors, keptExports);
if (!WasmValidator().validate(wasm)) {
std::cout << wasm << '\n';
Fatal() << "error in validating output";
}
// Do some useful optimizations after the evalling
{
PassRunner passRunner(&wasm);
passRunner.add("memory-packing"); // we flattened it, so re-optimize
// TODO: just do -Os for the one function
passRunner.add("remove-unused-names");
passRunner.add("dce");
passRunner.add("merge-blocks");
passRunner.add("vacuum");
passRunner.add("remove-unused-module-elements");
passRunner.run();
}
}
if (options.extra.count("output") > 0) {
if (options.debug) {
std::cout << "writing..." << std::endl;
}
ModuleWriter writer(options.passOptions);
writer.setBinary(emitBinary);
writer.setDebugInfo(debugInfo);
writer.write(wasm, options.extra["output"]);
}
}