diff options
Diffstat (limited to 'src/tools/fuzzing.h')
-rw-r--r-- | src/tools/fuzzing.h | 3218 |
1 files changed, 138 insertions, 3080 deletions
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h index dcdfd391f..e58b0f51b 100644 --- a/src/tools/fuzzing.h +++ b/src/tools/fuzzing.h @@ -65,158 +65,14 @@ struct BinaryArgs { class TranslateToFuzzReader { public: - TranslateToFuzzReader(Module& wasm, std::string& filename) - : wasm(wasm), builder(wasm) { - auto input(read_file<std::vector<char>>(filename, Flags::Binary)); - readData(input); - } - - TranslateToFuzzReader(Module& wasm, std::vector<char> input) - : wasm(wasm), builder(wasm) { - readData(input); - } - - void pickPasses(OptimizationOptions& options) { - while (options.passes.size() < 20 && !finishedInput && !oneIn(3)) { - switch (upTo(32)) { - case 0: - case 1: - case 2: - case 3: - case 4: { - options.passes.push_back("O"); - options.passOptions.optimizeLevel = upTo(4); - options.passOptions.shrinkLevel = upTo(4); - break; - } - case 5: - options.passes.push_back("coalesce-locals"); - break; - case 6: - options.passes.push_back("code-pushing"); - break; - case 7: - options.passes.push_back("code-folding"); - break; - case 8: - options.passes.push_back("dce"); - break; - case 9: - options.passes.push_back("duplicate-function-elimination"); - break; - case 10: - options.passes.push_back("flatten"); - break; - case 11: - options.passes.push_back("inlining"); - break; - case 12: - options.passes.push_back("inlining-optimizing"); - break; - case 13: - options.passes.push_back("local-cse"); - break; - case 14: - options.passes.push_back("memory-packing"); - break; - case 15: - options.passes.push_back("merge-blocks"); - break; - case 16: - options.passes.push_back("optimize-instructions"); - break; - case 17: - options.passes.push_back("pick-load-signs"); - break; - case 18: - options.passes.push_back("precompute"); - break; - case 19: - options.passes.push_back("precompute-propagate"); - break; - case 20: - options.passes.push_back("remove-unused-brs"); - break; - case 21: - options.passes.push_back("remove-unused-module-elements"); - break; - case 22: - options.passes.push_back("remove-unused-names"); - break; - case 23: - options.passes.push_back("reorder-functions"); - break; - case 24: - options.passes.push_back("reorder-locals"); - break; - case 25: { - options.passes.push_back("flatten"); - options.passes.push_back("rereloop"); - break; - } - case 26: - options.passes.push_back("simplify-locals"); - break; - case 27: - options.passes.push_back("simplify-locals-notee"); - break; - case 28: - options.passes.push_back("simplify-locals-nostructure"); - break; - case 29: - options.passes.push_back("simplify-locals-notee-nostructure"); - break; - case 30: - options.passes.push_back("ssa"); - break; - case 31: - options.passes.push_back("vacuum"); - break; - default: - WASM_UNREACHABLE("unexpected value"); - } - } - if (oneIn(2)) { - options.passOptions.optimizeLevel = upTo(4); - } - if (oneIn(2)) { - options.passOptions.shrinkLevel = upTo(4); - } - std::cout << "opt level: " << options.passOptions.optimizeLevel << '\n'; - std::cout << "shrink level: " << options.passOptions.shrinkLevel << '\n'; - } + TranslateToFuzzReader(Module& wasm, std::vector<char> input); + TranslateToFuzzReader(Module& wasm, std::string& filename); + void pickPasses(OptimizationOptions& options); void setAllowMemory(bool allowMemory_) { allowMemory = allowMemory_; } - void setAllowOOB(bool allowOOB_) { allowOOB = allowOOB_; } - void build() { - if (HANG_LIMIT > 0) { - prepareHangLimitSupport(); - } - if (allowMemory) { - setupMemory(); - } - setupTables(); - setupGlobals(); - if (wasm.features.hasExceptionHandling()) { - setupTags(); - } - modifyInitialFunctions(); - addImportLoggingSupport(); - // keep adding functions until we run out of input - while (!finishedInput) { - auto* func = addFunction(); - addInvocations(func); - } - if (HANG_LIMIT > 0) { - addHangLimitSupport(); - } - if (allowMemory) { - finalizeMemory(); - } - finalizeTable(); - } + void build(); private: Module& wasm; @@ -225,38 +81,7 @@ private: size_t pos; // the position in the input // whether we already cycled through all the input (if so, we should try to // finish things off) - bool finishedInput; - - // The maximum amount of params to each function. - static const int MAX_PARAMS = 10; - - // The maximum amount of vars in each function. - static const int MAX_VARS = 20; - - // The maximum number of globals in a module. - static const int MAX_GLOBALS = 20; - - // The maximum number of tuple elements. - static const int MAX_TUPLE_SIZE = 6; - - // some things require luck, try them a few times - static const int TRIES = 10; - - // beyond a nesting limit, greatly decrease the chance to continue to nest - static const int NESTING_LIMIT = 11; - - // the maximum size of a block - static const int BLOCK_FACTOR = 5; - - // the memory that we use, a small portion so that we have a good chance of - // looking at writes (we also look outside of this region with small - // probability) this should be a power of 2 - const Address USABLE_MEMORY = 16; - - // the number of runtime iterations (function calls, loop backbranches) we - // allow before we stop execution with a trap, to prevent hangs. 0 means - // no hang protection. - static const int HANG_LIMIT = 10; + bool finishedInput = false; // Whether to emit memory operations like loads and stores. bool allowMemory = true; @@ -276,371 +101,20 @@ private: // randomize this in each function. unsigned LOGGING_PERCENT = 0; - void readData(std::vector<char> input) { - bytes.swap(input); - pos = 0; - finishedInput = false; - // ensure *some* input to be read - if (bytes.size() == 0) { - bytes.push_back(0); - } - } - - int8_t get() { - if (pos == bytes.size()) { - // we ran out of input, go to the start for more stuff - finishedInput = true; - pos = 0; - xorFactor++; - } - return bytes[pos++] ^ xorFactor; - } - - int16_t get16() { - auto temp = uint16_t(get()) << 8; - return temp | uint16_t(get()); - } - - int32_t get32() { - auto temp = uint32_t(get16()) << 16; - return temp | uint32_t(get16()); - } - - int64_t get64() { - auto temp = uint64_t(get32()) << 32; - return temp | uint64_t(get32()); - } - - float getFloat() { return Literal(get32()).reinterpretf32(); } - - double getDouble() { return Literal(get64()).reinterpretf64(); } - - Type getSubType(Type type) { - if (type.isTuple()) { - std::vector<Type> types; - for (const auto& t : type) { - types.push_back(getSubType(t)); - } - return Type(types); - } - if (type.isFunction() && type != Type::funcref) { - // TODO: specific typed function references types. - return type; - } - SmallVector<Type, 2> options; - options.push_back(type); // includes itself - // TODO: interesting uses of typed function types - // TODO: interesting subtypes of compound types - if (type.isBasic()) { - switch (type.getBasic()) { - case Type::anyref: - if (wasm.features.hasReferenceTypes()) { - options.push_back(Type::funcref); - options.push_back(Type::externref); - if (wasm.features.hasGC()) { - options.push_back(Type::eqref); - // TODO: i31ref, dataref, etc. - } - } - break; - case Type::eqref: - if (wasm.features.hasGC()) { - // TODO: i31ref, dataref, etc. - } - break; - default: - break; - } - } - return pick(options); - } - - void setupMemory() { - // Add memory itself - MemoryUtils::ensureExists(wasm.memory); - if (wasm.features.hasBulkMemory()) { - size_t memCovered = 0; - // need at least one segment for memory.inits - size_t numSegments = upTo(8) + 1; - for (size_t i = 0; i < numSegments; i++) { - Memory::Segment segment; - segment.isPassive = bool(upTo(2)); - size_t segSize = upTo(USABLE_MEMORY * 2); - segment.data.resize(segSize); - for (size_t j = 0; j < segSize; j++) { - segment.data[j] = upTo(512); - } - if (!segment.isPassive) { - segment.offset = builder.makeConst(int32_t(memCovered)); - memCovered += segSize; - } - wasm.memory.segments.push_back(segment); - } - } else { - // init some data - wasm.memory.segments.emplace_back(builder.makeConst(int32_t(0))); - auto num = upTo(USABLE_MEMORY * 2); - for (size_t i = 0; i < num; i++) { - auto value = upTo(512); - wasm.memory.segments[0].data.push_back(value >= 256 ? 0 - : (value & 0xff)); - } - } - // Add memory hasher helper (for the hash, see hash.h). The function looks - // like: - // function hashMemory() { - // hash = 5381; - // hash = ((hash << 5) + hash) ^ mem[0]; - // hash = ((hash << 5) + hash) ^ mem[1]; - // .. - // return hash; - // } - std::vector<Expression*> contents; - contents.push_back( - builder.makeLocalSet(0, builder.makeConst(uint32_t(5381)))); - auto zero = Literal::makeFromInt32(0, wasm.memory.indexType); - for (Index i = 0; i < USABLE_MEMORY; i++) { - contents.push_back(builder.makeLocalSet( - 0, - builder.makeBinary( - XorInt32, - builder.makeBinary( - AddInt32, - builder.makeBinary(ShlInt32, - builder.makeLocalGet(0, Type::i32), - builder.makeConst(uint32_t(5))), - builder.makeLocalGet(0, Type::i32)), - builder.makeLoad( - 1, false, i, 1, builder.makeConst(zero), Type::i32)))); - } - contents.push_back(builder.makeLocalGet(0, Type::i32)); - auto* body = builder.makeBlock(contents); - auto* hasher = wasm.addFunction(builder.makeFunction( - "hashMemory", Signature(Type::none, Type::i32), {Type::i32}, body)); - wasm.addExport( - builder.makeExport(hasher->name, hasher->name, ExternalKind::Function)); - // Export memory so JS fuzzing can use it - if (!wasm.getExportOrNull("memory")) { - wasm.addExport(builder.makeExport("memory", "0", ExternalKind::Memory)); - } - } + Name HANG_LIMIT_GLOBAL; Name funcrefTableName; - // TODO(reference-types): allow the fuzzer to create multiple tables - void setupTables() { - // Ensure a funcref element segment and table exist. Segments with more - // specific function types may have a smaller chance of getting functions. - Table* table = nullptr; - auto iter = - std::find_if(wasm.tables.begin(), wasm.tables.end(), [&](auto& table) { - return table->type == Type::funcref; - }); - if (iter != wasm.tables.end()) { - table = iter->get(); - } else { - auto tablePtr = builder.makeTable( - Names::getValidTableName(wasm, "fuzzing_table"), Type::funcref, 0, 0); - tablePtr->hasExplicitName = true; - table = wasm.addTable(std::move(tablePtr)); - } - funcrefTableName = table->name; - bool hasFuncrefElemSegment = std::any_of( - wasm.elementSegments.begin(), - wasm.elementSegments.end(), - [&](auto& segment) { - return segment->table.is() && segment->type == Type::funcref; - }); - if (!hasFuncrefElemSegment) { - // TODO: use a random table - auto segment = std::make_unique<ElementSegment>( - table->name, builder.makeConst(int32_t(0))); - segment->setName(Names::getValidElementSegmentName(wasm, "elem$"), false); - wasm.addElementSegment(std::move(segment)); - } - } - std::unordered_map<Type, std::vector<Name>> globalsByType; - void setupGlobals() { - // If there were initial wasm contents, there may be imported globals. That - // would be a problem in the fuzzer harness as we'd error if we do not - // provide them (and provide the proper type, etc.). - // Avoid that, so that all the standard fuzzing infrastructure can always - // run the wasm. - for (auto& global : wasm.globals) { - if (global->imported()) { - // Remove import info from imported globals, and give them a simple - // initializer. - global->module = global->base = Name(); - global->init = makeConst(global->type); - } else { - // If the initialization referred to an imported global, it no longer - // can point to the same global after we make it a non-imported global - // (as wasm doesn't allow that - you can only use an imported one). - if (global->init->is<GlobalGet>()) { - global->init = makeConst(global->type); - } - } - } - for (size_t index = upTo(MAX_GLOBALS); index > 0; --index) { - auto type = getConcreteType(); - auto global = - builder.makeGlobal(Names::getValidGlobalName(wasm, "global$"), - type, - makeConst(type), - Builder::Mutable); - globalsByType[type].push_back(global->name); - wasm.addGlobal(std::move(global)); - } - } - - void setupTags() { - Index num = upTo(3); - for (size_t i = 0; i < num; i++) { - auto tag = builder.makeTag(Names::getValidTagName(wasm, "tag$"), - Signature(getControlFlowType(), Type::none)); - wasm.addTag(std::move(tag)); - } - } - - void finalizeMemory() { - for (auto& segment : wasm.memory.segments) { - Address maxOffset = segment.data.size(); - if (!segment.isPassive) { - if (auto* offset = segment.offset->dynCast<GlobalGet>()) { - // Using a non-imported global in a segment offset is not valid in - // wasm. This can occur due to us making what used to be an imported - // global, in initial contents, be not imported any more. To fix that, - // replace such invalid things with a constant. - // Note that it is still possible in theory to have imported globals - // here, as we only do the above for initial contents. While the - // fuzzer doesn't do so as of the time of this comment, do a check - // for full generality, so that this code essentially does "if this - // is invalid wasm, fix it up." - if (!wasm.getGlobal(offset->name)->imported()) { - // TODO: It would be better to avoid segment overlap so that - // MemoryPacking can run. - segment.offset = - builder.makeConst(Literal::makeFromInt32(0, Type::i32)); - } - } - if (auto* offset = segment.offset->dynCast<Const>()) { - maxOffset = maxOffset + offset->value.getInteger(); - } - } - wasm.memory.initial = std::max( - wasm.memory.initial, - Address((maxOffset + Memory::kPageSize - 1) / Memory::kPageSize)); - } - wasm.memory.initial = std::max(wasm.memory.initial, USABLE_MEMORY); - // Avoid an unlimited memory size, which would make fuzzing very difficult - // as different VMs will run out of system memory in different ways. - if (wasm.memory.max == Memory::kUnlimitedSize) { - wasm.memory.max = wasm.memory.initial; - } - if (wasm.memory.max <= wasm.memory.initial) { - // To allow growth to work (which a testcase may assume), try to make the - // maximum larger than the initial. - // TODO: scan the wasm for grow instructions? - wasm.memory.max = - std::min(Address(wasm.memory.initial + 1), Address(Memory::kMaxSize32)); - } - // Avoid an imported memory (which the fuzz harness would need to handle). - wasm.memory.module = wasm.memory.base = Name(); - } - - void finalizeTable() { - for (auto& table : wasm.tables) { - ModuleUtils::iterTableSegments( - wasm, table->name, [&](ElementSegment* segment) { - // If the offset is a global that was imported (which is ok) but no - // longer is (not ok) we need to change that. - if (auto* offset = segment->offset->dynCast<GlobalGet>()) { - if (!wasm.getGlobal(offset->name)->imported()) { - // TODO: the segments must not overlap... - segment->offset = - builder.makeConst(Literal::makeFromInt32(0, Type::i32)); - } - } - Address maxOffset = segment->data.size(); - if (auto* offset = segment->offset->dynCast<Const>()) { - maxOffset = maxOffset + offset->value.getInteger(); - } - table->initial = std::max(table->initial, maxOffset); - }); - table->max = oneIn(2) ? Address(Table::kUnlimitedSize) : table->initial; - // Avoid an imported table (which the fuzz harness would need to handle). - table->module = table->base = Name(); - } - } - - Name HANG_LIMIT_GLOBAL; - - void prepareHangLimitSupport() { - HANG_LIMIT_GLOBAL = Names::getValidGlobalName(wasm, "hangLimit"); - } - - void addHangLimitSupport() { - auto glob = builder.makeGlobal(HANG_LIMIT_GLOBAL, - Type::i32, - builder.makeConst(int32_t(HANG_LIMIT)), - Builder::Mutable); - wasm.addGlobal(std::move(glob)); - - Name exportName = "hangLimitInitializer"; - auto funcName = Names::getValidFunctionName(wasm, exportName); - auto* func = new Function; - func->name = funcName; - func->type = Signature(Type::none, Type::none); - func->body = builder.makeGlobalSet(HANG_LIMIT_GLOBAL, - builder.makeConst(int32_t(HANG_LIMIT))); - wasm.addFunction(func); - - if (wasm.getExportOrNull(exportName)) { - // We must export our actual hang limit function - remove anything - // previously existing. - wasm.removeExport(exportName); - } - auto* export_ = new Export; - export_->name = exportName; - export_->value = func->name; - export_->kind = ExternalKind::Function; - wasm.addExport(export_); - } - - void addImportLoggingSupport() { - for (auto type : getLoggableTypes()) { - auto* func = new Function; - Name name = std::string("log-") + type.toString(); - func->name = name; - func->module = "fuzzing-support"; - func->base = name; - func->type = Signature(type, Type::none); - wasm.addFunction(func); - } - } - - Expression* makeHangLimitCheck() { - return builder.makeSequence( - builder.makeIf( - builder.makeUnary(UnaryOp::EqZInt32, - builder.makeGlobalGet(HANG_LIMIT_GLOBAL, Type::i32)), - makeTrivial(Type::unreachable)), - builder.makeGlobalSet( - HANG_LIMIT_GLOBAL, - builder.makeBinary(BinaryOp::SubInt32, - builder.makeGlobalGet(HANG_LIMIT_GLOBAL, Type::i32), - builder.makeConst(int32_t(1))))); - } + std::vector<Type> loggableTypes; - // function generation state + Index numAddedFunctions = 0; + // RAII helper for managing the state used to create a single function. struct FunctionCreationContext { TranslateToFuzzReader& parent; - Function* func; - std::vector<Expression*> breakableStack; // things we can break to Index labelIndex = 0; @@ -656,113 +130,51 @@ private: parent.funcContext = this; } - ~FunctionCreationContext() { - if (parent.HANG_LIMIT > 0) { - parent.addHangLimitChecks(func); - } - assert(breakableStack.empty()); - assert(hangStack.empty()); - parent.funcContext = nullptr; - } + ~FunctionCreationContext(); }; FunctionCreationContext* funcContext = nullptr; - Index numAddedFunctions = 0; + int nesting = 0; - Function* addFunction() { - LOGGING_PERCENT = upToSquared(100); - auto* func = new Function; - func->name = Names::getValidFunctionName(wasm, "func"); - FunctionCreationContext context(*this, func); - assert(funcContext->typeLocals.empty()); - Index numParams = upToSquared(MAX_PARAMS); - std::vector<Type> params; - params.reserve(numParams); - for (Index i = 0; i < numParams; i++) { - auto type = getSingleConcreteType(); - funcContext->typeLocals[type].push_back(params.size()); - params.push_back(type); - } - func->type = Signature(Type(params), getControlFlowType()); - Index numVars = upToSquared(MAX_VARS); - for (Index i = 0; i < numVars; i++) { - auto type = getConcreteType(); - if (!type.isDefaultable()) { - // We can't use a nondefaultable type as a var, as those must be - // initialized to some default value. - continue; - } - funcContext->typeLocals[type].push_back(params.size() + - func->vars.size()); - func->vars.push_back(type); - } - // with small chance, make the body unreachable - auto bodyType = func->getResults(); - if (oneIn(10)) { - bodyType = Type::unreachable; - } - // with reasonable chance make the body a block - if (oneIn(2)) { - func->body = makeBlock(bodyType); - } else { - func->body = make(bodyType); - } - // Our OOB checks are already in the code, and if we recombine/mutate we - // may end up breaking them. TODO: do them after the fact, like with the - // hang limit checks. - if (allowOOB) { - // Recombinations create duplicate code patterns. - recombine(func); - // Mutations add random small changes, which can subtly break duplicate - // code patterns. - mutate(func); - // TODO: liveness operations on gets, with some prob alter a get to one - // with more possible sets. - // Recombination, mutation, etc. can break validation; fix things up - // after. - fixLabels(func); - } - // Add hang limit checks after all other operations on the function body. - wasm.addFunction(func); - // export some, but not all (to allow inlining etc.). make sure to - // export at least one, though, to keep each testcase interesting - if ((numAddedFunctions == 0 || oneIn(2)) && - !wasm.getExportOrNull(func->name)) { - auto* export_ = new Export; - export_->name = func->name; - export_->value = func->name; - export_->kind = ExternalKind::Function; - wasm.addExport(export_); - } - // add some to an elem segment - while (oneIn(3) && !finishedInput) { - auto type = Type(func->type, NonNullable); - std::vector<ElementSegment*> compatibleSegments; - ModuleUtils::iterActiveElementSegments( - wasm, [&](ElementSegment* segment) { - if (Type::isSubType(type, segment->type)) { - compatibleSegments.push_back(segment); - } - }); - auto& randomElem = compatibleSegments[upTo(compatibleSegments.size())]; - randomElem->data.push_back(builder.makeRefFunc(func->name, func->type)); - } - numAddedFunctions++; - return func; - } + // Methods for getting random data. + int8_t get(); + int16_t get16(); + int32_t get32(); + int64_t get64(); + float getFloat() { return Literal(get32()).reinterpretf32(); } + double getDouble() { return Literal(get64()).reinterpretf64(); } - void addHangLimitChecks(Function* func) { - // loop limit - FindAll<Loop> loops(func->body); - for (auto* loop : loops.list) { - loop->body = - builder.makeSequence(makeHangLimitCheck(), loop->body, loop->type); - } - // recursion limit - func->body = builder.makeSequence( - makeHangLimitCheck(), func->body, func->getResults()); - } + // Choose an integer value in [0, x). This doesn't use a perfectly uniform + // distribution, but it's fast and reasonable. + Index upTo(Index x); + bool oneIn(Index x) { return upTo(x) == 0; } + + // Apply upTo twice, generating a skewed distribution towards + // low values. + Index upToSquared(Index x) { return upTo(upTo(x)); } + + // Setup methods + void setupMemory(); + void setupTables(); + void setupGlobals(); + void setupTags(); + void finalizeMemory(); + void finalizeTable(); + void prepareHangLimitSupport(); + void addHangLimitSupport(); + void addImportLoggingSupport(); + + // Special expression makers + Expression* makeHangLimitCheck(); + Expression* makeLogging(); + Expression* makeMemoryHashLogging(); + + // Function creation + Function* addFunction(); + void addHangLimitChecks(Function* func); + + // Recombination and mutation // Recombination and mutation can replace a node with another node of the same // type, but should not do so for certain types that are dangerous. For @@ -771,223 +183,12 @@ private: bool canBeArbitrarilyReplaced(Expression* curr) { return curr->type.isDefaultable(); } - - void recombine(Function* func) { - // Don't always do this. - if (oneIn(2)) { - return; - } - // First, scan and group all expressions by type. - struct Scanner - : public PostWalker<Scanner, UnifiedExpressionVisitor<Scanner>> { - // A map of all expressions, categorized by type. - InsertOrderedMap<Type, std::vector<Expression*>> exprsByType; - - void visitExpression(Expression* curr) { - exprsByType[curr->type].push_back(curr); - } - }; - Scanner scanner; - scanner.walk(func->body); - // Potentially trim the list of possible picks, so replacements are more - // likely to collide. - for (auto& pair : scanner.exprsByType) { - if (oneIn(2)) { - continue; - } - auto& list = pair.second; - std::vector<Expression*> trimmed; - size_t num = upToSquared(list.size()); - for (size_t i = 0; i < num; i++) { - trimmed.push_back(pick(list)); - } - if (trimmed.empty()) { - trimmed.push_back(pick(list)); - } - list.swap(trimmed); - } - // Replace them with copies, to avoid a copy into one altering another copy - for (auto& pair : scanner.exprsByType) { - for (auto*& item : pair.second) { - item = ExpressionManipulator::copy(item, wasm); - } - } - // Second, with some probability replace an item with another item having - // the same type. (This is not always valid due to nesting of labels, but - // we'll fix that up later.) - struct Modder - : public PostWalker<Modder, UnifiedExpressionVisitor<Modder>> { - Module& wasm; - Scanner& scanner; - TranslateToFuzzReader& parent; - - Modder(Module& wasm, Scanner& scanner, TranslateToFuzzReader& parent) - : wasm(wasm), scanner(scanner), parent(parent) {} - - void visitExpression(Expression* curr) { - if (parent.oneIn(10) && parent.canBeArbitrarilyReplaced(curr)) { - // Replace it! - auto& candidates = scanner.exprsByType[curr->type]; - assert(!candidates.empty()); // this expression itself must be there - replaceCurrent( - ExpressionManipulator::copy(parent.pick(candidates), wasm)); - } - } - }; - Modder modder(wasm, scanner, *this); - modder.walk(func->body); - } - - void mutate(Function* func) { - // Don't always do this. - if (oneIn(2)) { - return; - } - struct Modder - : public PostWalker<Modder, UnifiedExpressionVisitor<Modder>> { - Module& wasm; - TranslateToFuzzReader& parent; - - Modder(Module& wasm, TranslateToFuzzReader& parent) - : wasm(wasm), parent(parent) {} - - void visitExpression(Expression* curr) { - if (parent.oneIn(10) && parent.canBeArbitrarilyReplaced(curr)) { - // For constants, perform only a small tweaking in some cases. - if (auto* c = curr->dynCast<Const>()) { - if (parent.oneIn(2)) { - c->value = parent.tweak(c->value); - return; - } - } - // TODO: more minor tweaks to immediates, like making a load atomic or - // not, changing an offset, etc. - // Perform a general replacement. - // (This is not always valid due to nesting of labels, but - // we'll fix that up later.) - replaceCurrent(parent.make(curr->type)); - } - } - }; - Modder modder(wasm, *this); - modder.walk(func->body); - } - + void recombine(Function* func); + void mutate(Function* func); // Fix up changes that may have broken validation - types are correct in our // modding, but not necessarily labels. - void fixLabels(Function* func) { - struct Fixer - : public ControlFlowWalker<Fixer, UnifiedExpressionVisitor<Fixer>> { - Module& wasm; - TranslateToFuzzReader& parent; - - Fixer(Module& wasm, TranslateToFuzzReader& parent) - : wasm(wasm), parent(parent) {} - - // Track seen names to find duplication, which is invalid. - std::set<Name> seen; - - void visitExpression(Expression* curr) { - // Note all scope names, and fix up all uses. - BranchUtils::operateOnScopeNameDefs(curr, [&](Name& name) { - if (name.is()) { - if (seen.count(name)) { - replace(); - } else { - seen.insert(name); - } - } - }); - BranchUtils::operateOnScopeNameUses(curr, [&](Name& name) { - if (name.is()) { - replaceIfInvalid(name); - } - }); - } - - bool replaceIfInvalid(Name target) { - if (!hasBreakTarget(target)) { - // There is no valid parent, replace with something trivially safe. - replace(); - return true; - } - return false; - } - - void replace() { replaceCurrent(parent.makeTrivial(getCurrent()->type)); } - - bool hasBreakTarget(Name name) { - if (controlFlowStack.empty()) { - return false; - } - Index i = controlFlowStack.size() - 1; - while (1) { - auto* curr = controlFlowStack[i]; - if (auto* block = curr->dynCast<Block>()) { - if (name == block->name) { - return true; - } - } else if (auto* loop = curr->dynCast<Loop>()) { - if (name == loop->name) { - return true; - } - } else { - // an if or a try, ignorable - assert(curr->is<If>() || curr->is<Try>()); - } - if (i == 0) { - return false; - } - i--; - } - } - }; - Fixer fixer(wasm, *this); - fixer.walk(func->body); - ReFinalize().walkFunctionInModule(func, &wasm); - } - - void modifyInitialFunctions() { - if (wasm.functions.empty()) { - return; - } - // Pick a chance to fuzz the contents of a function. - const int RESOLUTION = 10; - auto chance = upTo(RESOLUTION + 1); - // Do not iterate directly on wasm.functions itself (that is, avoid - // for (x : wasm.functions) - // ) as we may add to it as we go through the functions - make() can add new - // functions to implement a RefFunc. Instead, use an index. This avoids an - // iterator invalidation, and also we will process those new functions at - // the end (currently that is not needed atm, but it might in the future). - for (Index i = 0; i < wasm.functions.size(); i++) { - auto* func = wasm.functions[i].get(); - FunctionCreationContext context(*this, func); - if (func->imported()) { - // We can't allow extra imports, as the fuzzing infrastructure wouldn't - // know what to provide. - func->module = func->base = Name(); - func->body = make(func->getResults()); - } - // Optionally, fuzz the function contents. - if (upTo(RESOLUTION) >= chance) { - dropToLog(func); - // TODO add some locals? and the rest of addFunction's operations? - // TODO: interposition, replace initial a(b) with a(RANDOM_THING(b)) - // TODO: if we add OOB checks after creation, then we can do it on - // initial contents too, and it may be nice to *not* run these - // passes, like we don't run them on new functions. But, we may - // still want to run them some of the time, at least, so that we - // check variations on initial testcases even at the risk of OOB. - recombine(func); - mutate(func); - fixLabels(func); - } - } - // Remove a start function - the fuzzing harness expects code to run only - // from exports. - wasm.start = Name(); - } + void fixLabels(Function* func); + void modifyInitialFunctions(); // Initial wasm contents may have come from a test that uses the drop pattern: // @@ -997,2194 +198,104 @@ private: // by a pass, and we verify it is the expected one. But this does not use the // value in a way the fuzzer can notice. Replace some drops with a logging // operation instead. - void dropToLog(Function* func) { - // Don't always do this. - if (oneIn(2)) { - return; - } - struct Modder : public PostWalker<Modder> { - Module& wasm; - TranslateToFuzzReader& parent; - - Modder(Module& wasm, TranslateToFuzzReader& parent) - : wasm(wasm), parent(parent) {} - - void visitDrop(Drop* curr) { - if (parent.isLoggableType(curr->value->type) && parent.oneIn(2)) { - replaceCurrent(parent.builder.makeCall(std::string("log-") + - curr->value->type.toString(), - {curr->value}, - Type::none)); - } - } - }; - Modder modder(wasm, *this); - modder.walk(func->body); - } + void dropToLog(Function* func); // the fuzzer external interface sends in zeros (simpler to compare // across invocations from JS or wasm-opt etc.). Add invocations in // the wasm, so they run everywhere - void addInvocations(Function* func) { - Name name = func->name.str + std::string("_invoker"); - if (wasm.getFunctionOrNull(name) || wasm.getExportOrNull(name)) { - return; - } - std::vector<Expression*> invocations; - while (oneIn(2) && !finishedInput) { - std::vector<Expression*> args; - for (const auto& type : func->getParams()) { - args.push_back(makeConst(type)); - } - Expression* invoke = - builder.makeCall(func->name, args, func->getResults()); - if (func->getResults().isConcrete()) { - invoke = builder.makeDrop(invoke); - } - invocations.push_back(invoke); - // log out memory in some cases - if (oneIn(2)) { - invocations.push_back(makeMemoryHashLogging()); - } - } - if (invocations.empty()) { - return; - } - auto* invoker = new Function; - invoker->name = name; - invoker->type = Signature(Type::none, Type::none); - invoker->body = builder.makeBlock(invocations); - wasm.addFunction(invoker); - auto* export_ = new Export; - export_->name = name; - export_->value = name; - export_->kind = ExternalKind::Function; - wasm.addExport(export_); - } + void addInvocations(Function* func); Name makeLabel() { return std::string("label$") + std::to_string(funcContext->labelIndex++); } - // Weighting for the core make* methods. Some nodes are important enough that - // we should do them quite often. - static const size_t VeryImportant = 4; - static const size_t Important = 2; - - // always call the toplevel make(type) command, not the internal specific ones - - int nesting = 0; - - Expression* make(Type type) { - // when we should stop, emit something small (but not necessarily trivial) - if (finishedInput || nesting >= 5 * NESTING_LIMIT || // hard limit - (nesting >= NESTING_LIMIT && !oneIn(3))) { - if (type.isConcrete()) { - if (oneIn(2)) { - return makeConst(type); - } else { - return makeLocalGet(type); - } - } else if (type == Type::none) { - if (oneIn(2)) { - return makeNop(type); - } else { - return makeLocalSet(type); - } - } - assert(type == Type::unreachable); - return makeTrivial(type); - } - nesting++; - Expression* ret = nullptr; - if (type.isConcrete()) { - ret = _makeConcrete(type); - } else if (type == Type::none) { - ret = _makenone(); - } else { - assert(type == Type::unreachable); - ret = _makeunreachable(); - } - // we should create the right type of thing - assert(Type::isSubType(ret->type, type)); - nesting--; - return ret; - } - - Expression* _makeConcrete(Type type) { - bool canMakeControlFlow = !type.isTuple() || wasm.features.hasMultivalue(); - using Self = TranslateToFuzzReader; - FeatureOptions<Expression* (Self::*)(Type)> options; - using WeightedOption = decltype(options)::WeightedOption; - options.add(FeatureSet::MVP, - WeightedOption{&Self::makeLocalGet, VeryImportant}, - WeightedOption{&Self::makeLocalSet, VeryImportant}, - WeightedOption{&Self::makeGlobalGet, Important}, - WeightedOption{&Self::makeConst, Important}); - if (canMakeControlFlow) { - options - .add(FeatureSet::MVP, - WeightedOption{&Self::makeBlock, Important}, - WeightedOption{&Self::makeIf, Important}, - WeightedOption{&Self::makeLoop, Important}, - WeightedOption{&Self::makeBreak, Important}, - &Self::makeCall, - &Self::makeCallIndirect) - .add(FeatureSet::TypedFunctionReferences | FeatureSet::ReferenceTypes, - &Self::makeCallRef); - } - if (type.isSingle()) { - options - .add(FeatureSet::MVP, - WeightedOption{&Self::makeUnary, Important}, - WeightedOption{&Self::makeBinary, Important}, - &Self::makeSelect) - .add(FeatureSet::Multivalue, &Self::makeTupleExtract); - } - if (type.isSingle() && !type.isRef() && !type.isRtt()) { - options.add(FeatureSet::MVP, {&Self::makeLoad, Important}); - options.add(FeatureSet::SIMD, &Self::makeSIMD); - } - if (type.isInteger()) { - options.add(FeatureSet::Atomics, &Self::makeAtomic); - } - if (type == Type::i32) { - options.add(FeatureSet::ReferenceTypes, &Self::makeRefIsNull); - options.add(FeatureSet::ReferenceTypes | FeatureSet::GC, - &Self::makeRefEq); - // TODO: makeI31Get - } - if (type.isTuple()) { - options.add(FeatureSet::Multivalue, &Self::makeTupleMake); - } - if (type == Type::i31ref) { - options.add(FeatureSet::ReferenceTypes | FeatureSet::GC, - &Self::makeI31New); - } - // TODO: struct.get and other GC things - return (this->*pick(options))(type); - } - - Expression* _makenone() { - auto choice = upTo(100); - if (choice < LOGGING_PERCENT) { - if (choice < LOGGING_PERCENT / 2) { - return makeLogging(); - } else { - return makeMemoryHashLogging(); - } - } - using Self = TranslateToFuzzReader; - auto options = FeatureOptions<Expression* (Self::*)(Type)>(); - using WeightedOption = decltype(options)::WeightedOption; - options - .add(FeatureSet::MVP, - WeightedOption{&Self::makeLocalSet, VeryImportant}, - WeightedOption{&Self::makeBlock, Important}, - WeightedOption{&Self::makeIf, Important}, - WeightedOption{&Self::makeLoop, Important}, - WeightedOption{&Self::makeBreak, Important}, - WeightedOption{&Self::makeStore, Important}, - &Self::makeCall, - &Self::makeCallIndirect, - &Self::makeDrop, - &Self::makeNop, - &Self::makeGlobalSet) - .add(FeatureSet::BulkMemory, &Self::makeBulkMemory) - .add(FeatureSet::Atomics, &Self::makeAtomic) - .add(FeatureSet::TypedFunctionReferences | FeatureSet::ReferenceTypes, - &Self::makeCallRef); - return (this->*pick(options))(Type::none); - } - - Expression* _makeunreachable() { - using Self = TranslateToFuzzReader; - auto options = FeatureOptions<Expression* (Self::*)(Type)>(); - using WeightedOption = decltype(options)::WeightedOption; - options - .add(FeatureSet::MVP, - WeightedOption{&Self::makeLocalSet, VeryImportant}, - WeightedOption{&Self::makeBlock, Important}, - WeightedOption{&Self::makeIf, Important}, - WeightedOption{&Self::makeLoop, Important}, - WeightedOption{&Self::makeBreak, Important}, - WeightedOption{&Self::makeStore, Important}, - WeightedOption{&Self::makeUnary, Important}, - WeightedOption{&Self::makeBinary, Important}, - WeightedOption{&Self::makeUnreachable, Important}, - &Self::makeCall, - &Self::makeCallIndirect, - &Self::makeSelect, - &Self::makeSwitch, - &Self::makeDrop, - &Self::makeReturn) - .add(FeatureSet::TypedFunctionReferences | FeatureSet::ReferenceTypes, - &Self::makeCallRef); - return (this->*pick(options))(Type::unreachable); - } - - // make something with no chance of infinite recursion - Expression* makeTrivial(Type type) { - if (type.isConcrete()) { - if (oneIn(2)) { - return makeLocalGet(type); - } else { - return makeConst(type); - } - } else if (type == Type::none) { - return makeNop(type); - } - assert(type == Type::unreachable); - Expression* ret = nullptr; - if (funcContext->func->getResults().isConcrete()) { - ret = makeTrivial(funcContext->func->getResults()); - } - return builder.makeReturn(ret); - } - - // specific expression creators - - Expression* makeBlock(Type type) { - auto* ret = builder.makeBlock(); - ret->type = type; // so we have it during child creation - ret->name = makeLabel(); - funcContext->breakableStack.push_back(ret); - Index num = upToSquared(BLOCK_FACTOR - 1); // we add another later - if (nesting >= NESTING_LIMIT / 2) { - // smaller blocks past the limit - num /= 2; - if (nesting >= NESTING_LIMIT && oneIn(2)) { - // smaller blocks past the limit - num /= 2; - } - } - // not likely to have a block of size 1 - if (num == 0 && !oneIn(10)) { - num++; - } - while (num > 0 && !finishedInput) { - ret->list.push_back(make(Type::none)); - num--; - } - // give a chance to make the final element an unreachable break, instead - // of concrete - a common pattern (branch to the top of a loop etc.) - if (!finishedInput && type.isConcrete() && oneIn(2)) { - ret->list.push_back(makeBreak(Type::unreachable)); - } else { - ret->list.push_back(make(type)); - } - funcContext->breakableStack.pop_back(); - if (type.isConcrete()) { - ret->finalize(type); - } else { - ret->finalize(); - } - if (ret->type != type) { - // e.g. we might want an unreachable block, but a child breaks to it - assert(type == Type::unreachable && ret->type == Type::none); - return builder.makeSequence(ret, make(Type::unreachable)); - } - return ret; - } - - Expression* makeLoop(Type type) { - auto* ret = wasm.allocator.alloc<Loop>(); - ret->type = type; // so we have it during child creation - ret->name = makeLabel(); - funcContext->breakableStack.push_back(ret); - funcContext->hangStack.push_back(ret); - // either create random content, or do something more targeted - if (oneIn(2)) { - ret->body = makeMaybeBlock(type); - } else { - // ensure a branch back. also optionally create some loop vars - std::vector<Expression*> list; - list.push_back(makeMaybeBlock(Type::none)); // primary contents - // possible branch back - list.push_back(builder.makeBreak(ret->name, nullptr, makeCondition())); - list.push_back(make(type)); // final element, so we have the right type - ret->body = builder.makeBlock(list, type); - } - funcContext->breakableStack.pop_back(); - funcContext->hangStack.pop_back(); - ret->finalize(type); - return ret; - } - - Expression* makeCondition() { - // we want a 50-50 chance for the condition to be taken, for interesting - // execution paths. by itself, there is bias (e.g. most consts are "yes") - // so even that out with noise - auto* ret = make(Type::i32); - if (oneIn(2)) { - ret = builder.makeUnary(UnaryOp::EqZInt32, ret); - } - return ret; - } - - // make something, with a good chance of it being a block - Expression* makeMaybeBlock(Type type) { - // if past the limit, prefer not to emit blocks - if (nesting >= NESTING_LIMIT || oneIn(3)) { - return make(type); - } else { - return makeBlock(type); - } - } - - Expression* buildIf(const struct ThreeArgs& args, Type type) { - return builder.makeIf(args.a, args.b, args.c, type); - } - - Expression* makeIf(Type type) { - auto* condition = makeCondition(); - funcContext->hangStack.push_back(nullptr); - auto* ret = - buildIf({condition, makeMaybeBlock(type), makeMaybeBlock(type)}, type); - funcContext->hangStack.pop_back(); - return ret; - } - - Expression* makeBreak(Type type) { - if (funcContext->breakableStack.empty()) { - return makeTrivial(type); - } - Expression* condition = nullptr; - if (type != Type::unreachable) { - funcContext->hangStack.push_back(nullptr); - condition = makeCondition(); - } - // we need to find a proper target to break to; try a few times - int tries = TRIES; - while (tries-- > 0) { - auto* target = pick(funcContext->breakableStack); - auto name = getTargetName(target); - auto valueType = getTargetType(target); - if (type.isConcrete()) { - // we are flowing out a value - if (valueType != type) { - // we need to break to a proper place - continue; - } - auto* ret = builder.makeBreak(name, make(type), condition); - funcContext->hangStack.pop_back(); - return ret; - } else if (type == Type::none) { - if (valueType != Type::none) { - // we need to break to a proper place - continue; - } - auto* ret = builder.makeBreak(name, nullptr, condition); - funcContext->hangStack.pop_back(); - return ret; - } else { - assert(type == Type::unreachable); - if (valueType != Type::none) { - // we need to break to a proper place - continue; - } - // we are about to make an *un*conditional break. if it is - // to a loop, we prefer there to be a condition along the - // way, to reduce the chance of infinite looping - size_t conditions = 0; - int i = funcContext->hangStack.size(); - while (--i >= 0) { - auto* item = funcContext->hangStack[i]; - if (item == nullptr) { - conditions++; - } else if (auto* loop = item->cast<Loop>()) { - if (loop->name == name) { - // we found the target, no more conditions matter - break; - } - } - } - switch (conditions) { - case 0: { - if (!oneIn(4)) { - continue; - } - break; - } - case 1: { - if (!oneIn(2)) { - continue; - } - break; - } - default: { - if (oneIn(conditions + 1)) { - continue; - } - } - } - return builder.makeBreak(name); - } - } - // we failed to find something - if (type != Type::unreachable) { - funcContext->hangStack.pop_back(); - } - return makeTrivial(type); - } - - Expression* makeCall(Type type) { - int tries = TRIES; - bool isReturn; - while (tries-- > 0) { - Function* target = funcContext->func; - if (!wasm.functions.empty() && !oneIn(wasm.functions.size())) { - target = pick(wasm.functions).get(); - } - isReturn = type == Type::unreachable && wasm.features.hasTailCall() && - funcContext->func->getResults() == target->getResults(); - if (target->getResults() != type && !isReturn) { - continue; - } - // we found one! - std::vector<Expression*> args; - for (const auto& argType : target->getParams()) { - args.push_back(make(argType)); - } - return builder.makeCall(target->name, args, type, isReturn); - } - // we failed to find something - return makeTrivial(type); - } - - Expression* makeCallIndirect(Type type) { - auto& randomElem = wasm.elementSegments[upTo(wasm.elementSegments.size())]; - auto& data = randomElem->data; - if (data.empty()) { - return make(type); - } - // look for a call target with the right type - Index start = upTo(data.size()); - Index i = start; - Function* targetFn; - bool isReturn; - while (1) { - // TODO: handle unreachable - if (auto* get = data[i]->dynCast<RefFunc>()) { - targetFn = wasm.getFunction(get->func); - isReturn = type == Type::unreachable && wasm.features.hasTailCall() && - funcContext->func->getResults() == targetFn->getResults(); - if (targetFn->getResults() == type || isReturn) { - break; - } - } - i++; - if (i == data.size()) { - i = 0; - } - if (i == start) { - return makeTrivial(type); - } - } - // with high probability, make sure the type is valid otherwise, most are - // going to trap - Expression* target; - if (!allowOOB || !oneIn(10)) { - target = builder.makeConst(int32_t(i)); - } else { - target = make(Type::i32); - } - std::vector<Expression*> args; - for (const auto& type : targetFn->getParams()) { - args.push_back(make(type)); - } - // TODO: use a random table - return builder.makeCallIndirect( - funcrefTableName, target, args, targetFn->getSig(), isReturn); - } - - Expression* makeCallRef(Type type) { - // look for a call target with the right type - Function* target; - bool isReturn; - size_t i = 0; - while (1) { - if (i == TRIES || wasm.functions.empty()) { - // We can't find a proper target, give up. - return makeTrivial(type); - } - // TODO: handle unreachable - target = wasm.functions[upTo(wasm.functions.size())].get(); - isReturn = type == Type::unreachable && wasm.features.hasTailCall() && - funcContext->func->getResults() == target->getResults(); - if (target->getResults() == type || isReturn) { - break; - } - i++; - } - std::vector<Expression*> args; - for (const auto& type : target->getParams()) { - args.push_back(make(type)); - } - // TODO: half the time make a completely random item with that type. - return builder.makeCallRef( - builder.makeRefFunc(target->name, target->type), args, type, isReturn); - } - - Expression* makeLocalGet(Type type) { - auto& locals = funcContext->typeLocals[type]; - if (locals.empty()) { - return makeConst(type); - } - return builder.makeLocalGet(pick(locals), type); - } - - Expression* makeLocalSet(Type type) { - bool tee = type != Type::none; - Type valueType; - if (tee) { - valueType = type; - } else { - valueType = getConcreteType(); - } - auto& locals = funcContext->typeLocals[valueType]; - if (locals.empty()) { - return makeTrivial(type); - } - auto* value = make(valueType); - if (tee) { - return builder.makeLocalTee(pick(locals), value, valueType); - } else { - return builder.makeLocalSet(pick(locals), value); - } - } - + // Expression making methods. Always call the toplevel make(type) command, not + // the specific ones. + Expression* make(Type type); + Expression* _makeConcrete(Type type); + Expression* _makenone(); + Expression* _makeunreachable(); + + // Make something with no chance of infinite recursion. + Expression* makeTrivial(Type type); + + // Specific expression creators + Expression* makeBlock(Type type); + Expression* makeLoop(Type type); + Expression* makeCondition(); + // Make something, with a good chance of it being a block + Expression* makeMaybeBlock(Type type); + Expression* buildIf(const struct ThreeArgs& args, Type type); + Expression* makeIf(Type type); + Expression* makeBreak(Type type); + Expression* makeCall(Type type); + Expression* makeCallIndirect(Type type); + Expression* makeCallRef(Type type); + Expression* makeLocalGet(Type type); + Expression* makeLocalSet(Type type); // Some globals are for internal use, and should not be modified by random // fuzz code. - bool isValidGlobal(Name name) { return name != HANG_LIMIT_GLOBAL; } - - Expression* makeGlobalGet(Type type) { - auto it = globalsByType.find(type); - if (it == globalsByType.end() || it->second.empty()) { - return makeConst(type); - } - auto name = pick(it->second); - if (isValidGlobal(name)) { - return builder.makeGlobalGet(name, type); - } else { - return makeTrivial(type); - } - } - - Expression* makeGlobalSet(Type type) { - assert(type == Type::none); - type = getConcreteType(); - auto it = globalsByType.find(type); - if (it == globalsByType.end() || it->second.empty()) { - return makeTrivial(Type::none); - } - auto name = pick(it->second); - if (isValidGlobal(name)) { - return builder.makeGlobalSet(name, make(type)); - } else { - return makeTrivial(Type::none); - } - } - - Expression* makeTupleMake(Type type) { - assert(wasm.features.hasMultivalue()); - assert(type.isTuple()); - std::vector<Expression*> elements; - for (const auto& t : type) { - elements.push_back(make(t)); - } - return builder.makeTupleMake(std::move(elements)); - } - - Expression* makeTupleExtract(Type type) { - // Tuples can require locals in binary format conversions. - if (!type.isDefaultable()) { - return makeTrivial(type); - } - assert(wasm.features.hasMultivalue()); - assert(type.isSingle() && type.isConcrete()); - Type tupleType = getTupleType(); - - // Find indices from which we can extract `type` - std::vector<size_t> extractIndices; - size_t i = 0; - for (const auto& t : tupleType) { - if (t == type) { - extractIndices.push_back(i); - } - ++i; - } - - // If there are none, inject one - if (extractIndices.size() == 0) { - std::vector<Type> newElements(tupleType.begin(), tupleType.end()); - size_t injected = upTo(newElements.size()); - newElements[injected] = type; - tupleType = Type(newElements); - extractIndices.push_back(injected); - } - - Index index = pick(extractIndices); - Expression* child = make(tupleType); - return builder.makeTupleExtract(child, index); - } - - Expression* makePointer() { - auto* ret = make(wasm.memory.indexType); - // with high probability, mask the pointer so it's in a reasonable - // range. otherwise, most pointers are going to be out of range and - // most memory ops will just trap - if (!allowOOB || !oneIn(10)) { - if (wasm.memory.is64()) { - ret = builder.makeBinary( - AndInt64, ret, builder.makeConst(int64_t(USABLE_MEMORY - 1))); - } else { - ret = builder.makeBinary( - AndInt32, ret, builder.makeConst(int32_t(USABLE_MEMORY - 1))); - } - } - return ret; - } - - Expression* makeNonAtomicLoad(Type type) { - auto offset = logify(get()); - auto ptr = makePointer(); - switch (type.getBasic()) { - case Type::i32: { - bool signed_ = get() & 1; - switch (upTo(3)) { - case 0: - return builder.makeLoad(1, signed_, offset, 1, ptr, type); - case 1: - return builder.makeLoad(2, signed_, offset, pick(1, 2), ptr, type); - case 2: - return builder.makeLoad( - 4, signed_, offset, pick(1, 2, 4), ptr, type); - } - WASM_UNREACHABLE("unexpected value"); - } - case Type::i64: { - bool signed_ = get() & 1; - switch (upTo(4)) { - case 0: - return builder.makeLoad(1, signed_, offset, 1, ptr, type); - case 1: - return builder.makeLoad(2, signed_, offset, pick(1, 2), ptr, type); - case 2: - return builder.makeLoad( - 4, signed_, offset, pick(1, 2, 4), ptr, type); - case 3: - return builder.makeLoad( - 8, signed_, offset, pick(1, 2, 4, 8), ptr, type); - } - WASM_UNREACHABLE("unexpected value"); - } - case Type::f32: { - return builder.makeLoad(4, false, offset, pick(1, 2, 4), ptr, type); - } - case Type::f64: { - return builder.makeLoad(8, false, offset, pick(1, 2, 4, 8), ptr, type); - } - case Type::v128: { - if (!wasm.features.hasSIMD()) { - return makeTrivial(type); - } - return builder.makeLoad( - 16, false, offset, pick(1, 2, 4, 8, 16), ptr, type); - } - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("invalid type"); - } - WASM_UNREACHABLE("invalid type"); - } - - Expression* makeLoad(Type type) { - // reference types cannot be stored in memory - if (!allowMemory || type.isRef()) { - return makeTrivial(type); - } - auto* ret = makeNonAtomicLoad(type); - if (type != Type::i32 && type != Type::i64) { - return ret; - } - if (!wasm.features.hasAtomics() || oneIn(2)) { - return ret; - } - // make it atomic - auto* load = ret->cast<Load>(); - wasm.memory.shared = true; - load->isAtomic = true; - load->signed_ = false; - load->align = load->bytes; - return load; - } - - Expression* makeNonAtomicStore(Type type) { - if (type == Type::unreachable) { - // make a normal store, then make it unreachable - auto* ret = makeNonAtomicStore(getStorableType()); - auto* store = ret->dynCast<Store>(); - if (!store) { - return ret; - } - switch (upTo(3)) { - case 0: - store->ptr = make(Type::unreachable); - break; - case 1: - store->value = make(Type::unreachable); - break; - case 2: - store->ptr = make(Type::unreachable); - store->value = make(Type::unreachable); - break; - } - store->finalize(); - return store; - } - // the type is none or unreachable. we also need to pick the value - // type. - if (type == Type::none) { - type = getStorableType(); - } - auto offset = logify(get()); - auto ptr = makePointer(); - auto value = make(type); - switch (type.getBasic()) { - case Type::i32: { - switch (upTo(3)) { - case 0: - return builder.makeStore(1, offset, 1, ptr, value, type); - case 1: - return builder.makeStore(2, offset, pick(1, 2), ptr, value, type); - case 2: - return builder.makeStore( - 4, offset, pick(1, 2, 4), ptr, value, type); - } - WASM_UNREACHABLE("invalid value"); - } - case Type::i64: { - switch (upTo(4)) { - case 0: - return builder.makeStore(1, offset, 1, ptr, value, type); - case 1: - return builder.makeStore(2, offset, pick(1, 2), ptr, value, type); - case 2: - return builder.makeStore( - 4, offset, pick(1, 2, 4), ptr, value, type); - case 3: - return builder.makeStore( - 8, offset, pick(1, 2, 4, 8), ptr, value, type); - } - WASM_UNREACHABLE("invalid value"); - } - case Type::f32: { - return builder.makeStore(4, offset, pick(1, 2, 4), ptr, value, type); - } - case Type::f64: { - return builder.makeStore(8, offset, pick(1, 2, 4, 8), ptr, value, type); - } - case Type::v128: { - if (!wasm.features.hasSIMD()) { - return makeTrivial(type); - } - return builder.makeStore( - 16, offset, pick(1, 2, 4, 8, 16), ptr, value, type); - } - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("invalid type"); - } - WASM_UNREACHABLE("invalid type"); - } - - Expression* makeStore(Type type) { - if (!allowMemory || type.isRef()) { - return makeTrivial(type); - } - auto* ret = makeNonAtomicStore(type); - auto* store = ret->dynCast<Store>(); - if (!store) { - return ret; - } - if (store->value->type != Type::i32 && store->value->type != Type::i64) { - return store; - } - if (!wasm.features.hasAtomics() || oneIn(2)) { - return store; - } - // make it atomic - wasm.memory.shared = true; - store->isAtomic = true; - store->align = store->bytes; - return store; - } - + bool isValidGlobal(Name name); + + Expression* makeGlobalGet(Type type); + Expression* makeGlobalSet(Type type); + Expression* makeTupleMake(Type type); + Expression* makeTupleExtract(Type type); + Expression* makePointer(); + Expression* makeNonAtomicLoad(Type type); + Expression* makeLoad(Type type); + Expression* makeNonAtomicStore(Type type); + Expression* makeStore(Type type); // Makes a small change to a constant value. - Literal tweak(Literal value) { - auto type = value.type; - if (type.isVector()) { - // TODO: tweak each lane? - return value; - } - // +- 1 - switch (upTo(5)) { - case 0: - value = value.add(Literal::makeNegOne(type)); - break; - case 1: - value = value.add(Literal::makeOne(type)); - break; - default: { - } - } - // For floats, optionally add a non-integer adjustment in +- [-1, 1] - if (type.isFloat() && oneIn(2)) { - const int RANGE = 1000; - auto RANGE_LITERAL = Literal::makeFromInt32(RANGE, type); - // adjustment -> [0, 2 * RANGE] - auto adjustment = Literal::makeFromInt32(upTo(2 * RANGE + 1), type); - // adjustment -> [-RANGE, RANGE] - adjustment = adjustment.sub(RANGE_LITERAL); - // adjustment -> [-1, 1] - adjustment = adjustment.div(RANGE_LITERAL); - value = value.add(adjustment); - } - // Flip sign. - if (oneIn(2)) { - value = value.mul(Literal::makeNegOne(type)); - } - return value; - } - - Literal makeLiteral(Type type) { - if (type == Type::v128) { - // generate each lane individually for random lane interpretation - switch (upTo(6)) { - case 0: - return Literal(std::array<Literal, 16>{{makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32)}}); - case 1: - return Literal(std::array<Literal, 8>{{makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32)}}); - case 2: - return Literal(std::array<Literal, 4>{{makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32), - makeLiteral(Type::i32)}}); - case 3: - return Literal(std::array<Literal, 2>{ - {makeLiteral(Type::i64), makeLiteral(Type::i64)}}); - case 4: - return Literal(std::array<Literal, 4>{{makeLiteral(Type::f32), - makeLiteral(Type::f32), - makeLiteral(Type::f32), - makeLiteral(Type::f32)}}); - case 5: - return Literal(std::array<Literal, 2>{ - {makeLiteral(Type::f64), makeLiteral(Type::f64)}}); - default: - WASM_UNREACHABLE("unexpected value"); - } - } - - switch (upTo(4)) { - case 0: { - // totally random, entire range - switch (type.getBasic()) { - case Type::i32: - return Literal(get32()); - case Type::i64: - return Literal(get64()); - case Type::f32: - return Literal(getFloat()); - case Type::f64: - return Literal(getDouble()); - case Type::v128: - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("invalid type"); - } - break; - } - case 1: { - // small range - int64_t small; - switch (upTo(6)) { - case 0: - small = int8_t(get()); - break; - case 1: - small = uint8_t(get()); - break; - case 2: - small = int16_t(get16()); - break; - case 3: - small = uint16_t(get16()); - break; - case 4: - small = int32_t(get32()); - break; - case 5: - small = uint32_t(get32()); - break; - default: - WASM_UNREACHABLE("invalid value"); - } - switch (type.getBasic()) { - case Type::i32: - return Literal(int32_t(small)); - case Type::i64: - return Literal(int64_t(small)); - case Type::f32: - return Literal(float(small)); - case Type::f64: - return Literal(double(small)); - case Type::v128: - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - break; - } - case 2: { - // special values - Literal value; - switch (type.getBasic()) { - case Type::i32: - value = - Literal(pick<int32_t>(0, - std::numeric_limits<int8_t>::min(), - std::numeric_limits<int8_t>::max(), - std::numeric_limits<int16_t>::min(), - std::numeric_limits<int16_t>::max(), - std::numeric_limits<int32_t>::min(), - std::numeric_limits<int32_t>::max(), - std::numeric_limits<uint8_t>::max(), - std::numeric_limits<uint16_t>::max(), - std::numeric_limits<uint32_t>::max())); - break; - case Type::i64: - value = - Literal(pick<int64_t>(0, - std::numeric_limits<int8_t>::min(), - std::numeric_limits<int8_t>::max(), - std::numeric_limits<int16_t>::min(), - std::numeric_limits<int16_t>::max(), - std::numeric_limits<int32_t>::min(), - std::numeric_limits<int32_t>::max(), - std::numeric_limits<int64_t>::min(), - std::numeric_limits<int64_t>::max(), - std::numeric_limits<uint8_t>::max(), - std::numeric_limits<uint16_t>::max(), - std::numeric_limits<uint32_t>::max(), - std::numeric_limits<uint64_t>::max())); - break; - case Type::f32: - value = Literal(pick<float>(0.0f, - -0.0f, - std::numeric_limits<float>::min(), - std::numeric_limits<float>::max(), - std::numeric_limits<int32_t>::min(), - std::numeric_limits<int32_t>::max(), - std::numeric_limits<int64_t>::min(), - std::numeric_limits<int64_t>::max(), - std::numeric_limits<uint32_t>::max(), - std::numeric_limits<uint64_t>::max())); - break; - case Type::f64: - value = Literal(pick<double>(0.0, - -0.0, - std::numeric_limits<float>::min(), - std::numeric_limits<float>::max(), - std::numeric_limits<double>::min(), - std::numeric_limits<double>::max(), - std::numeric_limits<int32_t>::min(), - std::numeric_limits<int32_t>::max(), - std::numeric_limits<int64_t>::min(), - std::numeric_limits<int64_t>::max(), - std::numeric_limits<uint32_t>::max(), - std::numeric_limits<uint64_t>::max())); - break; - case Type::v128: - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - return tweak(value); - } - case 3: { - // powers of 2 - Literal value; - switch (type.getBasic()) { - case Type::i32: - value = Literal(int32_t(1) << upTo(32)); - break; - case Type::i64: - value = Literal(int64_t(1) << upTo(64)); - break; - case Type::f32: - value = Literal(float(int64_t(1) << upTo(64))); - break; - case Type::f64: - value = Literal(double(int64_t(1) << upTo(64))); - break; - case Type::v128: - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - return tweak(value); - } - } - WASM_UNREACHABLE("invalid value"); - } - - Expression* makeConst(Type type) { - if (type.isRef()) { - assert(wasm.features.hasReferenceTypes()); - // Check if we can use ref.func. - // 'funcContext->func' is the pointer to the last created function and can - // be null when we set up globals (before we create any functions), in - // which case we can't use ref.func. - if (type == Type::funcref && funcContext && oneIn(2)) { - // First set to target to the last created function, and try to select - // among other existing function if possible - Function* target = funcContext->func; - if (!wasm.functions.empty() && !oneIn(wasm.functions.size())) { - target = pick(wasm.functions).get(); - } - return builder.makeRefFunc(target->name, target->type); - } - if (type == Type::i31ref) { - return builder.makeI31New(makeConst(Type::i32)); - } - if (oneIn(2) && type.isNullable()) { - return builder.makeRefNull(type); - } - if (!type.isFunction()) { - // We don't know how to create an externref or GC data yet TODO - // For now, create a null, and if it must be non-null, cast it to such - // even though that traps at runtime. - auto nullable = Type(type.getHeapType(), Nullable); - Expression* ret = builder.makeRefNull(nullable); - if (!type.isNullable()) { - ret = builder.makeRefAs(RefAsNonNull, ret); - } - return ret; - } - // TODO: randomize the order - for (auto& func : wasm.functions) { - if (type == Type(func->type, NonNullable)) { - return builder.makeRefFunc(func->name, func->type); - } - } - // We failed to find a function, so create a null reference if we can. - if (type.isNullable()) { - return builder.makeRefNull(type); - } - // Last resort: create a function. - auto heapType = type.getHeapType(); - if (heapType == HeapType::func) { - // The specific signature does not matter. - heapType = Signature(Type::none, Type::none); - } - auto* func = wasm.addFunction(builder.makeFunction( - Names::getValidFunctionName(wasm, "ref_func_target"), - heapType, - {}, - builder.makeUnreachable())); - return builder.makeRefFunc(func->name, heapType); - } - if (type.isRtt()) { - return builder.makeRtt(type); - } - if (type.isTuple()) { - std::vector<Expression*> operands; - for (const auto& t : type) { - operands.push_back(makeConst(t)); - } - return builder.makeTupleMake(std::move(operands)); - } - auto* ret = wasm.allocator.alloc<Const>(); - ret->value = makeLiteral(type); - ret->type = type; - return ret; - } - - Expression* buildUnary(const UnaryArgs& args) { - return builder.makeUnary(args.a, args.b); - } - - Expression* makeUnary(Type type) { - assert(!type.isTuple()); - if (type == Type::unreachable) { - if (auto* unary = makeUnary(getSingleConcreteType())->dynCast<Unary>()) { - return builder.makeUnary(unary->op, make(Type::unreachable)); - } - // give up - return makeTrivial(type); - } - // There are no unary ops for reference or RTT types. - if (type.isRef() || type.isRtt()) { - return makeTrivial(type); - } - switch (type.getBasic()) { - case Type::i32: { - auto singleConcreteType = getSingleConcreteType(); - TODO_SINGLE_COMPOUND(singleConcreteType); - switch (singleConcreteType.getBasic()) { - case Type::i32: { - auto op = pick( - FeatureOptions<UnaryOp>() - .add(FeatureSet::MVP, EqZInt32, ClzInt32, CtzInt32, PopcntInt32) - .add(FeatureSet::SignExt, ExtendS8Int32, ExtendS16Int32)); - return buildUnary({op, make(Type::i32)}); - } - case Type::i64: - return buildUnary({pick(EqZInt64, WrapInt64), make(Type::i64)}); - case Type::f32: { - auto op = pick(FeatureOptions<UnaryOp>() - .add(FeatureSet::MVP, - TruncSFloat32ToInt32, - TruncUFloat32ToInt32, - ReinterpretFloat32) - .add(FeatureSet::TruncSat, - TruncSatSFloat32ToInt32, - TruncSatUFloat32ToInt32)); - return buildUnary({op, make(Type::f32)}); - } - case Type::f64: { - auto op = pick(FeatureOptions<UnaryOp>() - .add(FeatureSet::MVP, - TruncSFloat64ToInt32, - TruncUFloat64ToInt32) - .add(FeatureSet::TruncSat, - TruncSatSFloat64ToInt32, - TruncSatUFloat64ToInt32)); - return buildUnary({op, make(Type::f64)}); - } - case Type::v128: { - assert(wasm.features.hasSIMD()); - // TODO: Add the other SIMD unary ops - return buildUnary({pick(AnyTrueVec128, - AllTrueVecI8x16, - AllTrueVecI16x8, - AllTrueVecI32x4), - make(Type::v128)}); - } - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - return makeTrivial(type); - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - WASM_UNREACHABLE("invalid type"); - } - case Type::i64: { - switch (upTo(4)) { - case 0: { - auto op = - pick(FeatureOptions<UnaryOp>() - .add(FeatureSet::MVP, ClzInt64, CtzInt64, PopcntInt64) - .add(FeatureSet::SignExt, - ExtendS8Int64, - ExtendS16Int64, - ExtendS32Int64)); - return buildUnary({op, make(Type::i64)}); - } - case 1: - return buildUnary( - {pick(ExtendSInt32, ExtendUInt32), make(Type::i32)}); - case 2: { - auto op = pick(FeatureOptions<UnaryOp>() - .add(FeatureSet::MVP, - TruncSFloat32ToInt64, - TruncUFloat32ToInt64) - .add(FeatureSet::TruncSat, - TruncSatSFloat32ToInt64, - TruncSatUFloat32ToInt64)); - return buildUnary({op, make(Type::f32)}); - } - case 3: { - auto op = pick(FeatureOptions<UnaryOp>() - .add(FeatureSet::MVP, - TruncSFloat64ToInt64, - TruncUFloat64ToInt64, - ReinterpretFloat64) - .add(FeatureSet::TruncSat, - TruncSatSFloat64ToInt64, - TruncSatUFloat64ToInt64)); - return buildUnary({op, make(Type::f64)}); - } - } - WASM_UNREACHABLE("invalid value"); - } - case Type::f32: { - switch (upTo(4)) { - case 0: - return buildUnary({pick(NegFloat32, - AbsFloat32, - CeilFloat32, - FloorFloat32, - TruncFloat32, - NearestFloat32, - SqrtFloat32), - make(Type::f32)}); - case 1: - return buildUnary({pick(ConvertUInt32ToFloat32, - ConvertSInt32ToFloat32, - ReinterpretInt32), - make(Type::i32)}); - case 2: - return buildUnary( - {pick(ConvertUInt64ToFloat32, ConvertSInt64ToFloat32), - make(Type::i64)}); - case 3: - return buildUnary({DemoteFloat64, make(Type::f64)}); - } - WASM_UNREACHABLE("invalid value"); - } - case Type::f64: { - switch (upTo(4)) { - case 0: - return buildUnary({pick(NegFloat64, - AbsFloat64, - CeilFloat64, - FloorFloat64, - TruncFloat64, - NearestFloat64, - SqrtFloat64), - make(Type::f64)}); - case 1: - return buildUnary( - {pick(ConvertUInt32ToFloat64, ConvertSInt32ToFloat64), - make(Type::i32)}); - case 2: - return buildUnary({pick(ConvertUInt64ToFloat64, - ConvertSInt64ToFloat64, - ReinterpretInt64), - make(Type::i64)}); - case 3: - return buildUnary({PromoteFloat32, make(Type::f32)}); - } - WASM_UNREACHABLE("invalid value"); - } - case Type::v128: { - assert(wasm.features.hasSIMD()); - switch (upTo(5)) { - case 0: - return buildUnary( - {pick(SplatVecI8x16, SplatVecI16x8, SplatVecI32x4), - make(Type::i32)}); - case 1: - return buildUnary({SplatVecI64x2, make(Type::i64)}); - case 2: - return buildUnary({SplatVecF32x4, make(Type::f32)}); - case 3: - return buildUnary({SplatVecF64x2, make(Type::f64)}); - case 4: - return buildUnary({pick(NotVec128, - // TODO: add additional SIMD instructions - NegVecI8x16, - NegVecI16x8, - NegVecI32x4, - NegVecI64x2, - AbsVecF32x4, - NegVecF32x4, - SqrtVecF32x4, - AbsVecF64x2, - NegVecF64x2, - SqrtVecF64x2, - TruncSatSVecF32x4ToVecI32x4, - TruncSatUVecF32x4ToVecI32x4, - ConvertSVecI32x4ToVecF32x4, - ConvertUVecI32x4ToVecF32x4, - ExtendLowSVecI8x16ToVecI16x8, - ExtendHighSVecI8x16ToVecI16x8, - ExtendLowUVecI8x16ToVecI16x8, - ExtendHighUVecI8x16ToVecI16x8, - ExtendLowSVecI16x8ToVecI32x4, - ExtendHighSVecI16x8ToVecI32x4, - ExtendLowUVecI16x8ToVecI32x4, - ExtendHighUVecI16x8ToVecI32x4), - make(Type::v128)}); - } - WASM_UNREACHABLE("invalid value"); - } - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - WASM_UNREACHABLE("invalid type"); - } - - Expression* buildBinary(const BinaryArgs& args) { - return builder.makeBinary(args.a, args.b, args.c); - } - - Expression* makeBinary(Type type) { - assert(!type.isTuple()); - if (type == Type::unreachable) { - if (auto* binary = - makeBinary(getSingleConcreteType())->dynCast<Binary>()) { - return buildBinary( - {binary->op, make(Type::unreachable), make(Type::unreachable)}); - } - // give up - return makeTrivial(type); - } - // There are no binary ops for reference or RTT types. - if (type.isRef() || type.isRtt()) { - return makeTrivial(type); - } - switch (type.getBasic()) { - case Type::i32: { - switch (upTo(4)) { - case 0: - return buildBinary({pick(AddInt32, - SubInt32, - MulInt32, - DivSInt32, - DivUInt32, - RemSInt32, - RemUInt32, - AndInt32, - OrInt32, - XorInt32, - ShlInt32, - ShrUInt32, - ShrSInt32, - RotLInt32, - RotRInt32, - EqInt32, - NeInt32, - LtSInt32, - LtUInt32, - LeSInt32, - LeUInt32, - GtSInt32, - GtUInt32, - GeSInt32, - GeUInt32), - make(Type::i32), - make(Type::i32)}); - case 1: - return buildBinary({pick(EqInt64, - NeInt64, - LtSInt64, - LtUInt64, - LeSInt64, - LeUInt64, - GtSInt64, - GtUInt64, - GeSInt64, - GeUInt64), - make(Type::i64), - make(Type::i64)}); - case 2: - return buildBinary({pick(EqFloat32, - NeFloat32, - LtFloat32, - LeFloat32, - GtFloat32, - GeFloat32), - make(Type::f32), - make(Type::f32)}); - case 3: - return buildBinary({pick(EqFloat64, - NeFloat64, - LtFloat64, - LeFloat64, - GtFloat64, - GeFloat64), - make(Type::f64), - make(Type::f64)}); - } - WASM_UNREACHABLE("invalid value"); - } - case Type::i64: { - return buildBinary({pick(AddInt64, - SubInt64, - MulInt64, - DivSInt64, - DivUInt64, - RemSInt64, - RemUInt64, - AndInt64, - OrInt64, - XorInt64, - ShlInt64, - ShrUInt64, - ShrSInt64, - RotLInt64, - RotRInt64), - make(Type::i64), - make(Type::i64)}); - } - case Type::f32: { - return buildBinary({pick(AddFloat32, - SubFloat32, - MulFloat32, - DivFloat32, - CopySignFloat32, - MinFloat32, - MaxFloat32), - make(Type::f32), - make(Type::f32)}); - } - case Type::f64: { - return buildBinary({pick(AddFloat64, - SubFloat64, - MulFloat64, - DivFloat64, - CopySignFloat64, - MinFloat64, - MaxFloat64), - make(Type::f64), - make(Type::f64)}); - } - case Type::v128: { - assert(wasm.features.hasSIMD()); - return buildBinary({pick(EqVecI8x16, - NeVecI8x16, - LtSVecI8x16, - LtUVecI8x16, - GtSVecI8x16, - GtUVecI8x16, - LeSVecI8x16, - LeUVecI8x16, - GeSVecI8x16, - GeUVecI8x16, - EqVecI16x8, - NeVecI16x8, - LtSVecI16x8, - LtUVecI16x8, - GtSVecI16x8, - GtUVecI16x8, - LeSVecI16x8, - LeUVecI16x8, - GeSVecI16x8, - GeUVecI16x8, - EqVecI32x4, - NeVecI32x4, - LtSVecI32x4, - LtUVecI32x4, - GtSVecI32x4, - GtUVecI32x4, - LeSVecI32x4, - LeUVecI32x4, - GeSVecI32x4, - GeUVecI32x4, - EqVecF32x4, - NeVecF32x4, - LtVecF32x4, - GtVecF32x4, - LeVecF32x4, - GeVecF32x4, - EqVecF64x2, - NeVecF64x2, - LtVecF64x2, - GtVecF64x2, - LeVecF64x2, - GeVecF64x2, - AndVec128, - OrVec128, - XorVec128, - AndNotVec128, - AddVecI8x16, - AddSatSVecI8x16, - AddSatUVecI8x16, - SubVecI8x16, - SubSatSVecI8x16, - SubSatUVecI8x16, - MinSVecI8x16, - MinUVecI8x16, - MaxSVecI8x16, - MaxUVecI8x16, - // TODO: avgr_u - // TODO: q15mulr_sat_s - // TODO: extmul - AddVecI16x8, - AddSatSVecI16x8, - AddSatUVecI16x8, - SubVecI16x8, - SubSatSVecI16x8, - SubSatUVecI16x8, - MulVecI16x8, - MinSVecI16x8, - MinUVecI16x8, - MaxSVecI16x8, - MaxUVecI16x8, - AddVecI32x4, - SubVecI32x4, - MulVecI32x4, - MinSVecI32x4, - MinUVecI32x4, - MaxSVecI32x4, - MaxUVecI32x4, - DotSVecI16x8ToVecI32x4, - AddVecI64x2, - SubVecI64x2, - AddVecF32x4, - SubVecF32x4, - MulVecF32x4, - DivVecF32x4, - MinVecF32x4, - MaxVecF32x4, - AddVecF64x2, - SubVecF64x2, - MulVecF64x2, - DivVecF64x2, - MinVecF64x2, - MaxVecF64x2, - NarrowSVecI16x8ToVecI8x16, - NarrowUVecI16x8ToVecI8x16, - NarrowSVecI32x4ToVecI16x8, - NarrowUVecI32x4ToVecI16x8, - SwizzleVec8x16), - make(Type::v128), - make(Type::v128)}); - } - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - WASM_UNREACHABLE("invalid type"); - } - - Expression* buildSelect(const ThreeArgs& args, Type type) { - return builder.makeSelect(args.a, args.b, args.c, type); - } - - Expression* makeSelect(Type type) { - Type subType1 = getSubType(type); - Type subType2 = getSubType(type); - return buildSelect({make(Type::i32), make(subType1), make(subType2)}, type); - } - - Expression* makeSwitch(Type type) { - assert(type == Type::unreachable); - if (funcContext->breakableStack.empty()) { - return make(type); - } - // we need to find proper targets to break to; try a bunch - int tries = TRIES; - std::vector<Name> names; - Type valueType = Type::unreachable; - while (tries-- > 0) { - auto* target = pick(funcContext->breakableStack); - auto name = getTargetName(target); - auto currValueType = getTargetType(target); - if (names.empty()) { - valueType = currValueType; - } else { - if (valueType != currValueType) { - continue; // all values must be the same - } - } - names.push_back(name); - } - if (names.size() < 2) { - // we failed to find enough - return make(type); - } - auto default_ = names.back(); - names.pop_back(); - auto temp1 = make(Type::i32), - temp2 = valueType.isConcrete() ? make(valueType) : nullptr; - return builder.makeSwitch(names, default_, temp1, temp2); - } - - Expression* makeDrop(Type type) { - return builder.makeDrop( - make(type == Type::unreachable ? type : getConcreteType())); - } - - Expression* makeReturn(Type type) { - return builder.makeReturn(funcContext->func->getResults().isConcrete() - ? make(funcContext->func->getResults()) - : nullptr); - } - - Expression* makeNop(Type type) { - assert(type == Type::none); - return builder.makeNop(); - } - - Expression* makeUnreachable(Type type) { - assert(type == Type::unreachable); - return builder.makeUnreachable(); - } - - Expression* makeAtomic(Type type) { - assert(wasm.features.hasAtomics()); - if (!allowMemory) { - return makeTrivial(type); - } - wasm.memory.shared = true; - if (type == Type::none) { - return builder.makeAtomicFence(); - } - if (type == Type::i32 && oneIn(2)) { - if (ATOMIC_WAITS && oneIn(2)) { - auto* ptr = makePointer(); - auto expectedType = pick(Type::i32, Type::i64); - auto* expected = make(expectedType); - auto* timeout = make(Type::i64); - return builder.makeAtomicWait( - ptr, expected, timeout, expectedType, logify(get())); - } else { - auto* ptr = makePointer(); - auto* count = make(Type::i32); - return builder.makeAtomicNotify(ptr, count, logify(get())); - } - } - Index bytes; - switch (type.getBasic()) { - case Type::i32: { - switch (upTo(3)) { - case 0: - bytes = 1; - break; - case 1: - bytes = pick(1, 2); - break; - case 2: - bytes = pick(1, 2, 4); - break; - default: - WASM_UNREACHABLE("invalide value"); - } - break; - } - case Type::i64: { - switch (upTo(4)) { - case 0: - bytes = 1; - break; - case 1: - bytes = pick(1, 2); - break; - case 2: - bytes = pick(1, 2, 4); - break; - case 3: - bytes = pick(1, 2, 4, 8); - break; - default: - WASM_UNREACHABLE("invalide value"); - } - break; - } - default: - WASM_UNREACHABLE("unexpected type"); - } - auto offset = logify(get()); - auto* ptr = makePointer(); - if (oneIn(2)) { - auto* value = make(type); - return builder.makeAtomicRMW( - pick(RMWAdd, RMWSub, RMWAnd, RMWOr, RMWXor, RMWXchg), - bytes, - offset, - ptr, - value, - type); - } else { - auto* expected = make(type); - auto* replacement = make(type); - return builder.makeAtomicCmpxchg( - bytes, offset, ptr, expected, replacement, type); - } - } - - Expression* makeSIMD(Type type) { - assert(wasm.features.hasSIMD()); - if (type.isRef()) { - return makeTrivial(type); - } - if (type != Type::v128) { - return makeSIMDExtract(type); - } - // TODO: Add SIMDLoadStoreLane once it is generally available - switch (upTo(7)) { - case 0: - return makeUnary(Type::v128); - case 1: - return makeBinary(Type::v128); - case 2: - return makeSIMDReplace(); - case 3: - return makeSIMDShuffle(); - case 4: - return makeSIMDTernary(); - case 5: - return makeSIMDShift(); - case 6: - return makeSIMDLoad(); - } - WASM_UNREACHABLE("invalid value"); - } - - Expression* makeSIMDExtract(Type type) { - auto op = static_cast<SIMDExtractOp>(0); - switch (type.getBasic()) { - case Type::i32: - op = pick(ExtractLaneSVecI8x16, - ExtractLaneUVecI8x16, - ExtractLaneSVecI16x8, - ExtractLaneUVecI16x8, - ExtractLaneVecI32x4); - break; - case Type::i64: - op = ExtractLaneVecI64x2; - break; - case Type::f32: - op = ExtractLaneVecF32x4; - break; - case Type::f64: - op = ExtractLaneVecF64x2; - break; - case Type::v128: - case Type::funcref: - case Type::externref: - case Type::anyref: - case Type::eqref: - case Type::i31ref: - case Type::dataref: - case Type::none: - case Type::unreachable: - WASM_UNREACHABLE("unexpected type"); - } - Expression* vec = make(Type::v128); - uint8_t index = 0; - switch (op) { - case ExtractLaneSVecI8x16: - case ExtractLaneUVecI8x16: - index = upTo(16); - break; - case ExtractLaneSVecI16x8: - case ExtractLaneUVecI16x8: - index = upTo(8); - break; - case ExtractLaneVecI32x4: - case ExtractLaneVecF32x4: - index = upTo(4); - break; - case ExtractLaneVecI64x2: - case ExtractLaneVecF64x2: - index = upTo(2); - break; - } - return builder.makeSIMDExtract(op, vec, index); - } - - Expression* makeSIMDReplace() { - SIMDReplaceOp op = pick(ReplaceLaneVecI8x16, - ReplaceLaneVecI16x8, - ReplaceLaneVecI32x4, - ReplaceLaneVecI64x2, - ReplaceLaneVecF32x4, - ReplaceLaneVecF64x2); - Expression* vec = make(Type::v128); - uint8_t index; - Type lane_t; - switch (op) { - case ReplaceLaneVecI8x16: - index = upTo(16); - lane_t = Type::i32; - break; - case ReplaceLaneVecI16x8: - index = upTo(8); - lane_t = Type::i32; - break; - case ReplaceLaneVecI32x4: - index = upTo(4); - lane_t = Type::i32; - break; - case ReplaceLaneVecI64x2: - index = upTo(2); - lane_t = Type::i64; - break; - case ReplaceLaneVecF32x4: - index = upTo(4); - lane_t = Type::f32; - break; - case ReplaceLaneVecF64x2: - index = upTo(2); - lane_t = Type::f64; - break; - default: - WASM_UNREACHABLE("unexpected op"); - } - Expression* value = make(lane_t); - return builder.makeSIMDReplace(op, vec, index, value); - } - - Expression* makeSIMDShuffle() { - Expression* left = make(Type::v128); - Expression* right = make(Type::v128); - std::array<uint8_t, 16> mask; - for (size_t i = 0; i < 16; ++i) { - mask[i] = upTo(32); - } - return builder.makeSIMDShuffle(left, right, mask); - } - - Expression* makeSIMDTernary() { - // TODO: Enable qfma/qfms once it is implemented in V8 and the interpreter - // SIMDTernaryOp op = pick(Bitselect, - // QFMAF32x4, - // QFMSF32x4, - // QFMAF64x2, - // QFMSF64x2); - SIMDTernaryOp op = Bitselect; - Expression* a = make(Type::v128); - Expression* b = make(Type::v128); - Expression* c = make(Type::v128); - return builder.makeSIMDTernary(op, a, b, c); - } - - Expression* makeSIMDShift() { - SIMDShiftOp op = pick(ShlVecI8x16, - ShrSVecI8x16, - ShrUVecI8x16, - ShlVecI16x8, - ShrSVecI16x8, - ShrUVecI16x8, - ShlVecI32x4, - ShrSVecI32x4, - ShrUVecI32x4, - ShlVecI64x2, - ShrSVecI64x2, - ShrUVecI64x2); - Expression* vec = make(Type::v128); - Expression* shift = make(Type::i32); - return builder.makeSIMDShift(op, vec, shift); - } - - Expression* makeSIMDLoad() { - // TODO: add Load{32,64}Zero if merged to proposal - SIMDLoadOp op = pick(Load8SplatVec128, - Load16SplatVec128, - Load32SplatVec128, - Load64SplatVec128, - Load8x8SVec128, - Load8x8UVec128, - Load16x4SVec128, - Load16x4UVec128, - Load32x2SVec128, - Load32x2UVec128); - Address offset = logify(get()); - Address align; - switch (op) { - case Load8SplatVec128: - align = 1; - break; - case Load16SplatVec128: - align = pick(1, 2); - break; - case Load32SplatVec128: - align = pick(1, 2, 4); - break; - case Load64SplatVec128: - case Load8x8SVec128: - case Load8x8UVec128: - case Load16x4SVec128: - case Load16x4UVec128: - case Load32x2SVec128: - case Load32x2UVec128: - align = pick(1, 2, 4, 8); - break; - case Load32ZeroVec128: - case Load64ZeroVec128: - WASM_UNREACHABLE("Unexpected SIMD loads"); - } - Expression* ptr = makePointer(); - return builder.makeSIMDLoad(op, offset, align, ptr); - } - - Expression* makeBulkMemory(Type type) { - if (!allowMemory) { - return makeTrivial(type); - } - assert(wasm.features.hasBulkMemory()); - assert(type == Type::none); - switch (upTo(4)) { - case 0: - return makeMemoryInit(); - case 1: - return makeDataDrop(); - case 2: - return makeMemoryCopy(); - case 3: - return makeMemoryFill(); - } - WASM_UNREACHABLE("invalid value"); - } - + Literal tweak(Literal value); + Literal makeLiteral(Type type); + Expression* makeConst(Type type); + Expression* buildUnary(const UnaryArgs& args); + Expression* makeUnary(Type type); + Expression* buildBinary(const BinaryArgs& args); + Expression* makeBinary(Type type); + Expression* buildSelect(const ThreeArgs& args, Type type); + Expression* makeSelect(Type type); + Expression* makeSwitch(Type type); + Expression* makeDrop(Type type); + Expression* makeReturn(Type type); + Expression* makeNop(Type type); + Expression* makeUnreachable(Type type); + Expression* makeAtomic(Type type); + Expression* makeSIMD(Type type); + Expression* makeSIMDExtract(Type type); + Expression* makeSIMDReplace(); + Expression* makeSIMDShuffle(); + Expression* makeSIMDTernary(); + Expression* makeSIMDShift(); + Expression* makeSIMDLoad(); + Expression* makeBulkMemory(Type type); // TODO: support other RefIs variants, and rename this - Expression* makeRefIsNull(Type type) { - assert(type == Type::i32); - assert(wasm.features.hasReferenceTypes()); - return builder.makeRefIs(RefIsNull, make(getReferenceType())); - } - - Expression* makeRefEq(Type type) { - assert(type == Type::i32); - assert(wasm.features.hasReferenceTypes() && wasm.features.hasGC()); - auto* left = make(getEqReferenceType()); - auto* right = make(getEqReferenceType()); - return builder.makeRefEq(left, right); - } - - Expression* makeI31New(Type type) { - assert(type == Type::i31ref); - assert(wasm.features.hasReferenceTypes() && wasm.features.hasGC()); - auto* value = make(Type::i32); - return builder.makeI31New(value); - } - - Expression* makeI31Get(Type type) { - assert(type == Type::i32); - assert(wasm.features.hasReferenceTypes() && wasm.features.hasGC()); - auto* i31 = make(Type::i31ref); - return builder.makeI31Get(i31, bool(oneIn(2))); - } - - Expression* makeMemoryInit() { - if (!allowMemory) { - return makeTrivial(Type::none); - } - uint32_t segment = upTo(wasm.memory.segments.size()); - size_t totalSize = wasm.memory.segments[segment].data.size(); - size_t offsetVal = upTo(totalSize); - size_t sizeVal = upTo(totalSize - offsetVal); - Expression* dest = makePointer(); - Expression* offset = builder.makeConst(int32_t(offsetVal)); - Expression* size = builder.makeConst(int32_t(sizeVal)); - return builder.makeMemoryInit(segment, dest, offset, size); - } - - Expression* makeDataDrop() { - if (!allowMemory) { - return makeTrivial(Type::none); - } - return builder.makeDataDrop(upTo(wasm.memory.segments.size())); - } - - Expression* makeMemoryCopy() { - if (!allowMemory) { - return makeTrivial(Type::none); - } - Expression* dest = makePointer(); - Expression* source = makePointer(); - Expression* size = make(wasm.memory.indexType); - return builder.makeMemoryCopy(dest, source, size); - } - - Expression* makeMemoryFill() { - if (!allowMemory) { - return makeTrivial(Type::none); - } - Expression* dest = makePointer(); - Expression* value = make(Type::i32); - Expression* size = make(wasm.memory.indexType); - return builder.makeMemoryFill(dest, value, size); - } - - // special makers - - Expression* makeLogging() { - auto type = getLoggableType(); - return builder.makeCall( - std::string("log-") + type.toString(), {make(type)}, Type::none); - } - - Expression* makeMemoryHashLogging() { - auto* hash = builder.makeCall(std::string("hashMemory"), {}, Type::i32); - return builder.makeCall(std::string("log-i32"), {hash}, Type::none); - } - - // special getters - std::vector<Type> getSingleConcreteTypes() { - return items( - FeatureOptions<Type>() - .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64) - .add(FeatureSet::SIMD, Type::v128) - .add(FeatureSet::ReferenceTypes, Type::funcref, Type::externref) - .add(FeatureSet::ReferenceTypes | FeatureSet::GC, - Type::anyref, - Type::eqref)); - // TODO: emit typed function references types - // TODO: i31ref, dataref - } - - Type getSingleConcreteType() { return pick(getSingleConcreteTypes()); } - - std::vector<Type> getReferenceTypes() { - return items( - FeatureOptions<Type>() - .add(FeatureSet::ReferenceTypes, Type::funcref, Type::externref) - .add(FeatureSet::ReferenceTypes | FeatureSet::GC, - Type::anyref, - Type::eqref)); - // TODO: i31ref, dataref - } - - Type getReferenceType() { return pick(getReferenceTypes()); } - - std::vector<Type> getEqReferenceTypes() { - return items(FeatureOptions<Type>().add( - FeatureSet::ReferenceTypes | FeatureSet::GC, Type::eqref)); - // TODO: i31ref, dataref - } - - Type getEqReferenceType() { return pick(getEqReferenceTypes()); } - - Type getMVPType() { - return pick(items(FeatureOptions<Type>().add( - FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64))); - } - - Type getTupleType() { - std::vector<Type> elements; - size_t maxElements = 2 + upTo(MAX_TUPLE_SIZE - 1); - for (size_t i = 0; i < maxElements; ++i) { - auto type = getSingleConcreteType(); - // Don't add a non-defaultable type into a tuple, as currently we can't - // spill them into locals (that would require a "let"). - if (type.isDefaultable()) { - elements.push_back(type); - } - } - while (elements.size() < 2) { - elements.push_back(getMVPType()); - } - return Type(elements); - } - - Type getConcreteType() { - if (wasm.features.hasMultivalue() && oneIn(5)) { - return getTupleType(); - } else { - return getSingleConcreteType(); - } - } - - Type getControlFlowType() { - if (oneIn(10)) { - return Type::none; - } else { - return getConcreteType(); - } - } - - Type getStorableType() { - return pick( - FeatureOptions<Type>() - .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64) - .add(FeatureSet::SIMD, Type::v128)); - } - - // - funcref cannot be logged because referenced functions can be inlined or - // removed during optimization - // - there's no point in logging externref or anyref because these are opaque - // - don't bother logging tuples - std::vector<Type> loggableTypes; - - const std::vector<Type>& getLoggableTypes() { - if (loggableTypes.empty()) { - loggableTypes = items( - FeatureOptions<Type>() - .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64) - .add(FeatureSet::SIMD, Type::v128)); - } - return loggableTypes; - } - - Type getLoggableType() { return pick(getLoggableTypes()); } - - bool isLoggableType(Type type) { - const auto& types = getLoggableTypes(); - return std::find(types.begin(), types.end(), type) != types.end(); - } + Expression* makeRefIsNull(Type type); + Expression* makeRefEq(Type type); + Expression* makeI31New(Type type); + Expression* makeI31Get(Type type); + Expression* makeMemoryInit(); + Expression* makeDataDrop(); + Expression* makeMemoryCopy(); + Expression* makeMemoryFill(); + + // Getters for Types + Type getSingleConcreteType(); + Type getReferenceType(); + Type getEqReferenceType(); + Type getMVPType(); + Type getTupleType(); + Type getConcreteType(); + Type getControlFlowType(); + Type getStorableType(); + Type getLoggableType(); + bool isLoggableType(Type type); + Type getSubType(Type type); + + // Utilities + Name getTargetName(Expression* target); + Type getTargetType(Expression* target); // statistical distributions @@ -3193,40 +304,7 @@ private: return std::floor(std::log(std::max(Index(1) + x, Index(1)))); } - // one of the integer values in [0, x) - // this isn't a perfectly uniform distribution, but it's fast - // and reasonable - Index upTo(Index x) { - if (x == 0) { - return 0; - } - Index raw; - if (x <= 255) { - raw = get(); - } else if (x <= 65535) { - raw = get16(); - } else { - raw = get32(); - } - auto ret = raw % x; - // use extra bits as "noise" for later - xorFactor += raw / x; - return ret; - } - - bool oneIn(Index x) { return upTo(x) == 0; } - - bool onceEvery(Index x) { - static int counter = 0; - counter++; - return counter % x == 0; - } - - // apply upTo twice, generating a skewed distribution towards - // low values - Index upToSquared(Index x) { return upTo(upTo(x)); } - - // pick from a vector-like container + // Pick from a vector-like container template<typename T> const typename T::value_type& pick(const T& vec) { assert(!vec.empty()); auto index = upTo(vec.size()); @@ -3306,26 +384,6 @@ private: template<typename T> const T pick(FeatureOptions<T>& picker) { return pick(items(picker)); } - - // utilities - - Name getTargetName(Expression* target) { - if (auto* block = target->dynCast<Block>()) { - return block->name; - } else if (auto* loop = target->dynCast<Loop>()) { - return loop->name; - } - WASM_UNREACHABLE("unexpected expr type"); - } - - Type getTargetType(Expression* target) { - if (auto* block = target->dynCast<Block>()) { - return block->type; - } else if (target->is<Loop>()) { - return Type::none; - } - WASM_UNREACHABLE("unexpected expr type"); - } }; } // namespace wasm |