fuzzing.h

/*
 * Copyright 2017 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Translate a binary stream of bytes into a valid wasm module, *somehow*.
// This is helpful for fuzzing.
//

/*
high chance for set at start of loop
  high chance of get of a set local in the scope of that scope
    high chance of a tee in that case => loop var
*/

// TODO Generate exception handling instructions

#include "ir/memory-utils.h"
#include <ir/find_all.h>
#include <ir/literal-utils.h>
#include <ir/manipulation.h>
#include <ir/utils.h>
#include <support/file.h>
#include <tools/optimization-options.h>
#include <wasm-builder.h>

namespace wasm {

// helper structs, since list initialization has a fixed order of
// evaluation, avoiding UB

struct ThreeArgs {
  Expression* a;
  Expression* b;
  Expression* c;
};

struct UnaryArgs {
  UnaryOp a;
  Expression* b;
};

struct BinaryArgs {
  BinaryOp a;
  Expression* b;
  Expression* c;
};

// main reader

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';
  }

  void setAllowMemory(bool allowMemory_) { allowMemory = allowMemory_; }

  void setAllowOOB(bool allowOOB_) { allowOOB = allowOOB_; }

  void build() {
    if (allowMemory) {
      setupMemory();
    }
    setupTable();
    setupGlobals();
    if (wasm.features.hasExceptionHandling()) {
      setupEvents();
    }
    addImportLoggingSupport();
    // keep adding functions until we run out of input
    while (!finishedInput) {
      auto* func = addFunction();
      addInvocations(func);
    }
    if (HANG_LIMIT > 0) {
      addHangLimitSupport();
    }
    finalizeTable();
  }

private:
  Module& wasm;
  Builder builder;
  std::vector<char> bytes; // the input bytes
  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
  static const int 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;

  // Whether to emit memory operations like loads and stores.
  bool allowMemory = true;

  // Whether to emit loads, stores, and call_indirects that may be out
  // of bounds (which traps in wasm, and is undefined behavior in C).
  bool allowOOB = true;

  // Whether to emit atomic waits (which in single-threaded mode, may hang...)
  static const bool ATOMIC_WAITS = false;

  // After we finish the input, we start going through it again, but xoring
  // so it's not identical
  int xorFactor = 0;

  // The chance to emit a logging operation for a none expression. We
  // 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);
    }
    SmallVector<Type, 2> options;
    options.push_back(type); // includes itself
    // TODO (GC): subtyping
    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))));
    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(uint32_t(0)), 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
    wasm.addExport(builder.makeExport("memory", "0", ExternalKind::Memory));
  }

  void setupTable() {
    wasm.table.exists = true;
    wasm.table.segments.emplace_back(builder.makeConst(int32_t(0)));
  }

  std::map<Type, std::vector<Name>> globalsByType;

  void setupGlobals() {
    for (size_t index = upTo(MAX_GLOBALS); index > 0; --index) {
      auto type = getConcreteType();
      auto* global =
        builder.makeGlobal(std::string("global$") + std::to_string(index),
                           type,
                           makeConst(type),
                           Builder::Mutable);
      wasm.addGlobal(global);
      globalsByType[type].push_back(global->name);
    }
  }

  void setupEvents() {
    Index num = upTo(3);
    for (size_t i = 0; i < num; i++) {
      auto* event =
        builder.makeEvent(std::string("event$") + std::to_string(i),
                          WASM_EVENT_ATTRIBUTE_EXCEPTION,
                          Signature(getControlFlowType(), Type::none));
      wasm.addEvent(event);
    }
  }

  void finalizeTable() {
    wasm.table.initial = wasm.table.segments[0].data.size();
    wasm.table.max =
      oneIn(2) ? Address(Table::kUnlimitedSize) : wasm.table.initial;
  }

  const Name HANG_LIMIT_GLOBAL = "hangLimit";

  void addHangLimitSupport() {
    auto* glob = builder.makeGlobal(HANG_LIMIT_GLOBAL,
                                    Type::i32,
                                    builder.makeConst(int32_t(HANG_LIMIT)),
                                    Builder::Mutable);
    wasm.addGlobal(glob);

    auto* func = new Function;
    func->name = "hangLimitInitializer";
    func->sig = Signature(Type::none, Type::none);
    func->body =
      builder.makeGlobalSet(glob->name, builder.makeConst(int32_t(HANG_LIMIT)));
    wasm.addFunction(func);

    auto* export_ = new Export;
    export_->name = func->name;
    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->sig = 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)))));
  }

  // function generation state

  Function* func = nullptr;
  std::vector<Expression*> breakableStack; // things we can break to
  Index labelIndex;

  // a list of things relevant to computing the odds of an infinite loop,
  // which we try to minimize the risk of
  std::vector<Expression*> hangStack;

  std::map<Type, std::vector<Index>>
    typeLocals; // type => list of locals with that type

  Function* addFunction() {
    LOGGING_PERCENT = upToSquared(100);
    Index num = wasm.functions.size();
    func = new Function;
    func->name = std::string("func_") + std::to_string(num);
    assert(typeLocals.empty());
    Index numParams = upToSquared(MAX_PARAMS);
    std::vector<Type> params;
    params.reserve(numParams);
    for (Index i = 0; i < numParams; i++) {
      auto type = getSingleConcreteType();
      typeLocals[type].push_back(params.size());
      params.push_back(type);
    }
    func->sig = Signature(Type(params), getControlFlowType());
    Index numVars = upToSquared(MAX_VARS);
    for (Index i = 0; i < numVars; i++) {
      auto type = getConcreteType();
      typeLocals[type].push_back(params.size() + func->vars.size());
      func->vars.push_back(type);
    }
    labelIndex = 0;
    assert(breakableStack.empty());
    assert(hangStack.empty());
    // with small chance, make the body unreachable
    auto bodyType = func->sig.results;
    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.
    if (HANG_LIMIT > 0) {
      addHangLimitChecks(func);
    }
    assert(breakableStack.empty());
    assert(hangStack.empty());
    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 (num == 0 || oneIn(2)) {
      auto* export_ = new Export;
      export_->name = func->name;
      export_->value = func->name;
      export_->kind = ExternalKind::Function;
      wasm.addExport(export_);
    }
    // add some to the table
    while (oneIn(3) && !finishedInput) {
      wasm.table.segments[0].data.push_back(func->name);
    }
    // cleanup
    typeLocals.clear();
    return func;
  }

  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->sig.results);
  }

  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.
      std::map<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)) {
          // 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)) {
          // Replace it!
          // (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);
  }

  // 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> {
      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 visitBlock(Block* curr) {
        if (curr->name.is()) {
          if (seen.count(curr->name)) {
            replace();
          } else {
            seen.insert(curr->name);
          }
        }
      }

      void visitLoop(Loop* curr) {
        if (curr->name.is()) {
          if (seen.count(curr->name)) {
            replace();
          } else {
            seen.insert(curr->name);
          }
        }
      }

      void visitSwitch(Switch* curr) {
        for (auto name : curr->targets) {
          if (replaceIfInvalid(name)) {
            return;
          }
        }
        replaceIfInvalid(curr->default_);
      }

      void visitBreak(Break* curr) { replaceIfInvalid(curr->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 (Block* block = curr->dynCast<Block>()) {
            if (name == block->name) {
              return true;
            }
          } else if (Loop* loop = curr->dynCast<Loop>()) {
            if (name == loop->name) {
              return true;
            }
          } else {
            // an if, ignorable
            assert(curr->is<If>());
          }
          if (i == 0) {
            return false;
          }
          i--;
        }
      }
    };
    Fixer fixer(wasm, *this);
    fixer.walk(func->body);
    ReFinalize().walkFunctionInModule(func, &wasm);
  }

  // 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) {
    std::vector<Expression*> invocations;
    while (oneIn(2) && !finishedInput) {
      std::vector<Expression*> args;
      for (const auto& type : func->sig.params) {
        args.push_back(makeConst(type));
      }
      Expression* invoke =
        builder.makeCall(func->name, args, func->sig.results);
      if (func->sig.results.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 = func->name.str + std::string("_invoker");
    invoker->sig = Signature(Type::none, Type::none);
    invoker->body = builder.makeBlock(invocations);
    wasm.addFunction(invoker);
    auto* export_ = new Export;
    export_->name = invoker->name;
    export_->value = invoker->name;
    export_->kind = ExternalKind::Function;
    wasm.addExport(export_);
  }

  Name makeLabel() {
    return std::string("label$") + std::to_string(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.has(FeatureSet::Multivalue);
    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);
    }
    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()) {
      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);
    }
    if (type.isTuple()) {
      options.add(FeatureSet::Multivalue, &Self::makeTupleMake);
    }
    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);
    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);
    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 (func->sig.results.isConcrete()) {
      ret = makeTrivial(func->sig.results);
    }
    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();
    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));
    }
    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();
    breakableStack.push_back(ret);
    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);
    }
    breakableStack.pop_back();
    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();
    hangStack.push_back(nullptr);
    auto* ret =
      buildIf({condition, makeMaybeBlock(type), makeMaybeBlock(type)}, type);
    hangStack.pop_back();
    return ret;
  }

  Expression* makeBreak(Type type) {
    if (breakableStack.empty()) {
      return makeTrivial(type);
    }
    Expression* condition = nullptr;
    if (type != Type::unreachable) {
      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(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);
        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);
        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 = hangStack.size();
        while (--i >= 0) {
          auto* item = 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) {
      hangStack.pop_back();
    }
    return makeTrivial(type);
  }

  Expression* makeCall(Type type) {
    // seems ok, go on
    int tries = TRIES;
    bool isReturn;
    while (tries-- > 0) {
      Function* target = func;
      if (!wasm.functions.empty() && !oneIn(wasm.functions.size())) {
        target = pick(wasm.functions).get();
      }
      isReturn = type == Type::unreachable && wasm.features.hasTailCall() &&
                 func->sig.results == target->sig.results;
      if (target->sig.results != type && !isReturn) {
        continue;
      }
      // we found one!
      std::vector<Expression*> args;
      for (const auto& argType : target->sig.params) {
        args.push_back(make(argType));
      }
      return builder.makeCall(target->name, args, type, isReturn);
    }
    // we failed to find something
    return make(type);
  }

  Expression* makeCallIndirect(Type type) {
    auto& data = wasm.table.segments[0].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
      targetFn = wasm.getFunction(data[i]);
      isReturn = type == Type::unreachable && wasm.features.hasTailCall() &&
                 func->sig.results == targetFn->sig.results;
      if (targetFn->sig.results == type || isReturn) {
        break;
      }
      i++;
      if (i == data.size()) {
        i = 0;
      }
      if (i == start) {
        return make(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->sig.params) {
      args.push_back(make(type));
    }
    return builder.makeCallIndirect(target, args, targetFn->sig, isReturn);
  }

  Expression* makeLocalGet(Type type) {
    auto& locals = 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 = 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* makeGlobalGet(Type type) {
    auto it = globalsByType.find(type);
    if (it == globalsByType.end() || it->second.empty()) {
      return makeConst(type);
    }
    return builder.makeGlobalGet(pick(it->second), 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* value = make(type);
    return builder.makeGlobalSet(pick(it->second), value);
  }

  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) {
    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(Type::i32);
    // 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)) {
      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::exnref:
      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::exnref:
      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;
  }

  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");
      }
    }

    // Optional tweaking of the value by a small adjustment.
    auto tweak = [this, type](Literal value) {
      // +- 1
      switch (upTo(5)) {
        case 0:
          value = value.add(Literal::makeFromInt32(-1, type));
          break;
        case 1:
          value = value.add(Literal::makeFromInt32(1, 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::makeFromInt32(-1, type));
      }
      return 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::exnref:
          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::exnref:
          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,
                                        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,
                                         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::exnref:
          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::exnref:
          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.
      // '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 && func && oneIn(2)) {
        // First set to target to the last created function, and try to select
        // among other existing function if possible
        Function* target = func;
        if (!wasm.functions.empty() && !oneIn(wasm.functions.size())) {
          target = pick(wasm.functions).get();
        }
        return builder.makeRefFunc(target->name);
      }
      return builder.makeRefNull(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's no unary ops for reference types
    if (type.isRef()) {
      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());
            return buildUnary({pick(AnyTrueVecI8x16,
                                    AllTrueVecI8x16,
                                    AnyTrueVecI16x8,
                                    AllTrueVecI16x8,
                                    AnyTrueVecI32x4,
                                    AllTrueVecI32x4,
                                    AnyTrueVecI64x2,
                                    AllTrueVecI64x2),
                               make(Type::v128)});
          }
          case Type::funcref:
          case Type::externref:
          case Type::exnref:
            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,
                                    NegVecI8x16,
                                    NegVecI16x8,
                                    NegVecI32x4,
                                    NegVecI64x2,
                                    AbsVecF32x4,
                                    NegVecF32x4,
                                    SqrtVecF32x4,
                                    AbsVecF64x2,
                                    NegVecF64x2,
                                    SqrtVecF64x2,
                                    TruncSatSVecF32x4ToVecI32x4,
                                    TruncSatUVecF32x4ToVecI32x4,
                                    TruncSatSVecF64x2ToVecI64x2,
                                    TruncSatUVecF64x2ToVecI64x2,
                                    ConvertSVecI32x4ToVecF32x4,
                                    ConvertUVecI32x4ToVecF32x4,
                                    ConvertSVecI64x2ToVecF64x2,
                                    ConvertUVecI64x2ToVecF64x2,
                                    WidenLowSVecI8x16ToVecI16x8,
                                    WidenHighSVecI8x16ToVecI16x8,
                                    WidenLowUVecI8x16ToVecI16x8,
                                    WidenHighUVecI8x16ToVecI16x8,
                                    WidenLowSVecI16x8ToVecI32x4,
                                    WidenHighSVecI16x8ToVecI32x4,
                                    WidenLowUVecI16x8ToVecI32x4,
                                    WidenHighUVecI16x8ToVecI32x4),
                               make(Type::v128)});
        }
        WASM_UNREACHABLE("invalid value");
      }
      case Type::funcref:
      case Type::externref:
      case Type::exnref:
      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's no binary ops for reference types
    if (type.isRef()) {
      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,
                                 MulVecI8x16,
                                 MinSVecI8x16,
                                 MinUVecI8x16,
                                 MaxSVecI8x16,
                                 MaxUVecI8x16,
                                 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::exnref:
      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 (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(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(
      func->sig.results.isConcrete() ? make(func->sig.results) : 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(AtomicRMWOp::Add,
                                        AtomicRMWOp::Sub,
                                        AtomicRMWOp::And,
                                        AtomicRMWOp::Or,
                                        AtomicRMWOp::Xor,
                                        AtomicRMWOp::Xchg),
                                   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);
    }
    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::exnref:
      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(LoadSplatVec8x16,
                         LoadSplatVec16x8,
                         LoadSplatVec32x4,
                         LoadSplatVec64x2,
                         LoadExtSVec8x8ToVecI16x8,
                         LoadExtUVec8x8ToVecI16x8,
                         LoadExtSVec16x4ToVecI32x4,
                         LoadExtUVec16x4ToVecI32x4,
                         LoadExtSVec32x2ToVecI64x2,
                         LoadExtUVec32x2ToVecI64x2);
    Address offset = logify(get());
    Address align;
    switch (op) {
      case LoadSplatVec8x16:
        align = 1;
        break;
      case LoadSplatVec16x8:
        align = pick(1, 2);
        break;
      case LoadSplatVec32x4:
        align = pick(1, 2, 4);
        break;
      case LoadSplatVec64x2:
      case LoadExtSVec8x8ToVecI16x8:
      case LoadExtUVec8x8ToVecI16x8:
      case LoadExtSVec16x4ToVecI32x4:
      case LoadExtUVec16x4ToVecI32x4:
      case LoadExtSVec32x2ToVecI64x2:
      case LoadExtUVec32x2ToVecI64x2:
        align = pick(1, 2, 4, 8);
        break;
      case Load32Zero:
      case Load64Zero:
        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");
  }

  Expression* makeRefIsNull(Type type) {
    assert(type == Type::i32);
    assert(wasm.features.hasReferenceTypes());
    SmallVector<Type, 2> options;
    options.push_back(Type::externref);
    options.push_back(Type::funcref);
    if (wasm.features.hasExceptionHandling()) {
      options.push_back(Type::exnref);
    }
    return builder.makeRefIsNull(make(pick(options)));
  }

  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(Type::i32);
    return builder.makeMemoryCopy(dest, source, size);
  }

  Expression* makeMemoryFill() {
    if (!allowMemory) {
      return makeTrivial(Type::none);
    }
    Expression* dest = makePointer();
    Expression* value = makePointer();
    Expression* size = make(Type::i32);
    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::ExceptionHandling,
             Type::exnref));
  }

  Type getSingleConcreteType() { return pick(getSingleConcreteTypes()); }

  Type getTupleType() {
    std::vector<Type> elements;
    size_t numElements = 2 + upTo(MAX_TUPLE_SIZE - 1);
    elements.resize(numElements);
    for (size_t i = 0; i < numElements; ++i) {
      elements[i] = getSingleConcreteType();
    }
    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 because it is opaque
  // - don't bother logging tuples
  std::vector<Type> getLoggableTypes() {
    return items(
      FeatureOptions<Type>()
        .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64)
        .add(FeatureSet::SIMD, Type::v128)
        .add(FeatureSet::ReferenceTypes | FeatureSet::ExceptionHandling,
             Type::exnref));
  }

  Type getLoggableType() { return pick(getLoggableTypes()); }

  // statistical distributions

  // 0 to the limit, logarithmic scale
  Index logify(Index x) {
    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
  template<typename T> const typename T::value_type& pick(const T& vec) {
    assert(!vec.empty());
    auto index = upTo(vec.size());
    return vec[index];
  }

  // pick from a fixed list
  template<typename T, typename... Args> T pick(T first, Args... args) {
    auto num = sizeof...(Args) + 1;
    auto temp = upTo(num);
    return pickGivenNum<T>(temp, first, args...);
  }

  template<typename T> T pickGivenNum(size_t num, T first) {
    assert(num == 0);
    return first;
  }

// Trick to avoid a bug in GCC 7.x.
// Upstream bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82800
#define GCC_VERSION                                                            \
  (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
#if GCC_VERSION > 70000 && GCC_VERSION < 70300
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif

  template<typename T, typename... Args>
  T pickGivenNum(size_t num, T first, Args... args) {
    if (num == 0) {
      return first;
    }
    return pickGivenNum<T>(num - 1, args...);
  }

#if GCC_VERSION > 70000 && GCC_VERSION < 70300
#pragma GCC diagnostic pop
#endif

  template<typename T> struct FeatureOptions {
    template<typename... Ts>
    FeatureOptions<T>& add(FeatureSet feature, T option, Ts... rest) {
      options[feature].push_back(option);
      return add(feature, rest...);
    }

    struct WeightedOption {
      T option;
      size_t weight;
    };

    template<typename... Ts>
    FeatureOptions<T>&
    add(FeatureSet feature, WeightedOption weightedOption, Ts... rest) {
      for (size_t i = 0; i < weightedOption.weight; i++) {
        options[feature].push_back(weightedOption.option);
      }
      return add(feature, rest...);
    }

    FeatureOptions<T>& add(FeatureSet feature) { return *this; }

    std::map<FeatureSet, std::vector<T>> options;
  };

  template<typename T> std::vector<T> items(FeatureOptions<T>& picker) {
    std::vector<T> matches;
    for (const auto& item : picker.options) {
      if (wasm.features.has(item.first)) {
        matches.reserve(matches.size() + item.second.size());
        matches.insert(matches.end(), item.second.begin(), item.second.end());
      }
    }
    return matches;
  }

  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

// XXX Switch class has a condition?! is it real? should the node type be the
// value type if it exists?!

// TODO copy an existing function and replace just one node in it