text: /*
   * 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
  */
  
  #include <wasm-builder.h>
  #include <ir/literal-utils.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, Flags::Release));
      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();
        }
      }
      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 build(bool initEmitAtomics = true) {
      emitAtomics = initEmitAtomics;
      setupMemory();
      setupTable();
      setupGlobals();
      // keep adding functions until we run out of input
      while (!finishedInput) {
        auto* func = addFunction();
        addInvocations(func);
      }
      if (HANG_LIMIT > 0) {
        addHangLimitSupport();
      }
      if (DE_NAN) {
        addDeNanSupport();
      }
      finalizeTable();
    }
  
  private:
    Module& wasm;
    Builder builder;
    std::vector<char> bytes; // the input bytes
    size_t pos; // the position in the input
    bool finishedInput; // whether we already cycled through all the input (if so, we should try to finish things off)
  
    // 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;
  
    // 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;
  
    // Optionally remove NaNs, which are a source of nondeterminism (which makes
    // cross-VM comparisons harder)
    static const bool DE_NAN = true;
  
    // Whether to emit atomics
    bool emitAtomics = 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;
  
  
    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();
    }
  
    void setupMemory() {
      wasm.memory.exists = true;
      // use one page
      wasm.memory.initial = wasm.memory.max = 1;
      // init some data
      wasm.memory.segments.emplace_back(builder.makeConst(Literal(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));
      }
    }
  
    void setupTable() {
      wasm.table.exists = true;
      wasm.table.segments.emplace_back(builder.makeConst(Literal(int32_t(0))));
    }
  
    std::map<Type, std::vector<Name>> globalsByType;
  
    void setupGlobals() {
      size_t index = 0;
      for (auto type : { i32, i64, f32, f64 }) {
        auto num = upTo(3);
        for (size_t i = 0; i < num; i++) {
          auto* glob = builder.makeGlobal(
            std::string("global$") + std::to_string(index++),
            type,
            makeConst(type),
            Builder::Mutable
          );
          wasm.addGlobal(glob);
          globalsByType[type].push_back(glob->name);
        }
      }
    }
  
    void finalizeTable() {
      wasm.table.initial = wasm.table.segments[0].data.size();
      wasm.table.max = oneIn(2) ? Address(Table::kMaxSize) : wasm.table.initial;
    }
  
    const Name HANG_LIMIT_GLOBAL = "hangLimit";
  
    void addHangLimitSupport() {
      auto* glob = builder.makeGlobal(
        HANG_LIMIT_GLOBAL,
        i32,
        builder.makeConst(Literal(int32_t(HANG_LIMIT))),
        Builder::Mutable
      );
      wasm.addGlobal(glob);
  
      auto* func = new Function;
      func->name = "hangLimitInitializer";
      func->result = none;
      func->body = builder.makeSetGlobal(glob->name,
        builder.makeConst(Literal(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_);
    }
  
    Expression* makeHangLimitCheck() {
      return builder.makeSequence(
        builder.makeIf(
          builder.makeUnary(
            UnaryOp::EqZInt32,
            builder.makeGetGlobal(HANG_LIMIT_GLOBAL, i32)
          ),
          makeTrivial(unreachable)
        ),
        builder.makeSetGlobal(
          HANG_LIMIT_GLOBAL,
          builder.makeBinary(
            BinaryOp::SubInt32,
            builder.makeGetGlobal(HANG_LIMIT_GLOBAL, i32),
            builder.makeConst(Literal(int32_t(1)))
          )
        )
      );
    }
  
    void addDeNanSupport() {
      auto add = [&](Name name, Type type, Literal literal, BinaryOp op) {
        auto* func = new Function;
        func->name = name;
        func->params.push_back(type);
        func->result = type;
        func->body = builder.makeIf(
          builder.makeBinary(
            op,
            builder.makeGetLocal(0, type),
            builder.makeGetLocal(0, type)
          ),
          builder.makeGetLocal(0, type),
          builder.makeConst(literal)
        );
        wasm.addFunction(func);
      };
      add("deNan32", f32, Literal(float(0)), EqFloat32);
      add("deNan64", f64, Literal(double(0)), EqFloat64);
    }
  
    Expression* makeDeNanOp(Expression* expr) {
      if (!DE_NAN) return expr;
      if (expr->type == f32) {
        return builder.makeCall("deNan32", { expr }, f32);
      } else if (expr->type == f64) {
        return builder.makeCall("deNan64", { expr }, f64);
      }
      return expr; // unreachable etc. is fine
    }
  
    // function generation state
  
    Function* func;
    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() {
      Index num = wasm.functions.size();
      func = new Function;
      func->name = std::string("func_") + std::to_string(num);
      func->result = getReachableType();
      assert(typeLocals.empty());
      Index numParams = upToSquared(MAX_PARAMS);
      for (Index i = 0; i < numParams; i++) {
        auto type = getConcreteType();
        typeLocals[type].push_back(func->params.size());
        func->params.push_back(type);
      }
      Index numVars = upToSquared(MAX_VARS);
      for (Index i = 0; i < numVars; i++) {
        auto type = getConcreteType();
        typeLocals[type].push_back(func->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->result;
      if (oneIn(10)) {
        bodyType = unreachable;
      }
      // with reasonable chance make the body a block
      if (oneIn(2)) {
        func->body = makeBlock(bodyType);
      } else {
        func->body = make(bodyType);
      }
      if (HANG_LIMIT > 0) {
        func->body = builder.makeSequence(
          makeHangLimitCheck(),
          func->body
        );
      }
      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)) {
        func->type = ensureFunctionType(getSig(func), &wasm)->name;
        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)) {
        wasm.table.segments[0].data.push_back(func->name);
      }
      // cleanup
      typeLocals.clear();
      return func;
    }
  
    // the fuzzer external interface sends in zeros (simpler to compare
    // across invocations from JS or wasm-opt etc.). Add invocations in
    // the wasm, so they run everywhere
    void addInvocations(Function* func) {
      std::vector<Expression*> invocations;
      while (oneIn(2) && !finishedInput) {
        std::vector<Expression*> args;
        for (auto type : func->params) {
          args.push_back(makeConst(type));
        }
        Expression* invoke = builder.makeCall(func->name, args, func->result);
        if (isConcreteType(func->result)) {
          invoke = builder.makeDrop(invoke);
        }
        invocations.push_back(invoke);
      }
      if (invocations.empty()) return;
      auto* invoker = new Function;
      invoker->name = func->name.str + std::string("_invoker");
      invoker->result = none;
      invoker->body = builder.makeBlock(invocations);
      wasm.addFunction(invoker);
      invoker->type = ensureFunctionType(getSig(invoker), &wasm)->name;
      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++);
    }
  
    // 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 (isConcreteType(type)) {
          if (oneIn(2)) {
            return makeConst(type);
          } else {
            return makeGetLocal(type);
          }
        } else if (type == none) {
          if (oneIn(2)) {
            return makeNop(type);
          } else {
            return makeSetLocal(type);
          }
        }
        assert(type == unreachable);
        return makeTrivial(type);
      }
      nesting++;
      Expression* ret;
      switch (type) {
        case i32:
        case i64:
        case f32:
        case f64: ret = _makeConcrete(type); break;
        case none: ret = _makenone(); break;
        case unreachable: ret = _makeunreachable(); break;
        default: WASM_UNREACHABLE();
      }
      assert(ret->type == type); // we should create the right type of thing
      nesting--;
      return ret;
    }
  
    Expression* _makeConcrete(Type type) {
      auto choice = upTo(100);
      if (choice < 10) return makeConst(type);
      if (choice < 30) return makeSetLocal(type);
      if (choice < 50) return makeGetLocal(type);
      if (choice < 60) return makeBlock(type);
      if (choice < 70) return makeIf(type);
      if (choice < 80) return makeLoop(type);
      if (choice < 90) return makeBreak(type);
      switch (upTo(15)) {
        case 0: return makeBlock(type);
        case 1: return makeIf(type);
        case 2: return makeLoop(type);
        case 3: return makeBreak(type);
        case 4: return makeCall(type);
        case 5: return makeCallIndirect(type);
        case 6: return makeGetLocal(type);
        case 7: return makeSetLocal(type);
        case 8: return makeLoad(type);
        case 9: return makeConst(type);
        case 10: return makeUnary(type);
        case 11: return makeBinary(type);
        case 12: return makeSelect(type);
        case 13: return makeGetGlobal(type);
        case 14: return makeAtomic(type);
      }
      WASM_UNREACHABLE();
    }
  
    Expression* _makenone() {
      auto choice = upTo(100);
      if (choice < 50) return makeSetLocal(none);
      if (choice < 60) return makeBlock(none);
      if (choice < 70) return makeIf(none);
      if (choice < 80) return makeLoop(none);
      if (choice < 90) return makeBreak(none);
      switch (upTo(11)) {
        case 0: return makeBlock(none);
        case 1: return makeIf(none);
        case 2: return makeLoop(none);
        case 3: return makeBreak(none);
        case 4: return makeCall(none);
        case 5: return makeCallIndirect(none);
        case 6: return makeSetLocal(none);
        case 7: return makeStore(none);
        case 8: return makeDrop(none);
        case 9: return makeNop(none);
        case 10: return makeSetGlobal(none);
      }
      WASM_UNREACHABLE();
    }
  
    Expression* _makeunreachable() {
      switch (upTo(15)) {
        case 0: return makeBlock(unreachable);
        case 1: return makeIf(unreachable);
        case 2: return makeLoop(unreachable);
        case 3: return makeBreak(unreachable);
        case 4: return makeCall(unreachable);
        case 5: return makeCallIndirect(unreachable);
        case 6: return makeSetLocal(unreachable);
        case 7: return makeStore(unreachable);
        case 8: return makeUnary(unreachable);
        case 9: return makeBinary(unreachable);
        case 10: return makeSelect(unreachable);
        case 11: return makeSwitch(unreachable);
        case 12: return makeDrop(unreachable);
        case 13: return makeReturn(unreachable);
        case 14: return makeUnreachable(unreachable);
      }
      WASM_UNREACHABLE();
    }
  
    // make something with no chance of infinite recursion
    Expression* makeTrivial(Type type) {
      if (isConcreteType(type)) {
        if (oneIn(2)) {
          return makeGetLocal(type);
        } else {
          return makeConst(type);
        }
      } else if (type == none) {
        return makeNop(type);
      }
      assert(type == unreachable);
      Expression* ret = nullptr;
      if (isConcreteType(func->result)) {
        ret = makeTrivial(func->result);
      }
      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(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 && isConcreteType(type) && oneIn(2)) {
        ret->list.push_back(makeBreak(unreachable));
      } else {
        ret->list.push_back(make(type));
      }
      breakableStack.pop_back();
      if (isConcreteType(type)) {
        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 == unreachable && ret->type == none);
        return builder.makeSequence(ret, make(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(none)); // primary contents
        list.push_back(builder.makeBreak(ret->name, nullptr, makeCondition())); // possible branch back
        list.push_back(make(type)); // final element, so we have the right type
        ret->body = builder.makeBlock(list);
      }
      breakableStack.pop_back();
      hangStack.pop_back();
      if (HANG_LIMIT > 0) {
        ret->body = builder.makeSequence(
          makeHangLimitCheck(),
          ret->body
        );
      }
      ret->finalize();
      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(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* makeIf(Type type) {
      auto* condition = makeCondition();
      hangStack.push_back(nullptr);
      auto* ret = makeIf({ condition, makeMaybeBlock(type), makeMaybeBlock(type) });
      hangStack.pop_back();
      return ret;
    }
  
    Expression* makeIf(const struct ThreeArgs& args) {
      return builder.makeIf(args.a, args.b, args.c);
    }
  
    Expression* makeBreak(Type type) {
      if (breakableStack.empty()) return makeTrivial(type);
      Expression* condition = nullptr;
      if (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 = vectorPick(breakableStack);
        auto name = getTargetName(target);
        auto valueType = getTargetType(target);
        if (isConcreteType(type)) {
          // 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 == none) {
          if (valueType != 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 == unreachable);
          if (valueType != 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 != unreachable) {
        hangStack.pop_back();
      }
      return makeTrivial(type);
    }
  
    Expression* makeCall(Type type) {
      // seems ok, go on
      int tries = TRIES;
      while (tries-- > 0) {
        Function* target = func;
        if (!wasm.functions.empty() && !oneIn(wasm.functions.size())) {
          target = vectorPick(wasm.functions).get();
        }
        if (target->result != type) continue;
        // we found one!
        std::vector<Expression*> args;
        for (auto argType : target->params) {
          args.push_back(make(argType));
        }
        return builder.makeCall(target->name, args, type);
      }
      // 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* func;
      while (1) {
        // TODO: handle unreachable
        func = wasm.getFunction(data[i]);
        if (func->result == type) {
          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 (!oneIn(10)) {
        target = builder.makeConst(Literal(int32_t(i)));
      } else {
        target = make(i32);
      }
      std::vector<Expression*> args;
      for (auto type : func->params) {
        args.push_back(make(type));
      }
      func->type = ensureFunctionType(getSig(func), &wasm)->name;
      return builder.makeCallIndirect(
        func->type,
        target,
        args,
        func->result
      );
    }
  
    Expression* makeGetLocal(Type type) {
      auto& locals = typeLocals[type];
      if (locals.empty()) return makeConst(type);
      return builder.makeGetLocal(vectorPick(locals), type);
    }
  
    Expression* makeSetLocal(Type type) {
      bool tee = 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.makeTeeLocal(vectorPick(locals), value);
      } else {
        return builder.makeSetLocal(vectorPick(locals), value);
      }
    }
  
    Expression* makeGetGlobal(Type type) {
      auto& globals = globalsByType[type];
      if (globals.empty()) return makeConst(type);
      return builder.makeGetGlobal(vectorPick(globals), type);
    }
  
    Expression* makeSetGlobal(Type type) {
      assert(type == none);
      type = getConcreteType();
      auto& globals = globalsByType[type];
      if (globals.empty()) return makeTrivial(none);
      auto* value = make(type);
      return builder.makeSetGlobal(vectorPick(globals), value);
    }
  
    Expression* makePointer() {
      auto* ret = make(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 (!oneIn(10)) {
        ret = builder.makeBinary(AndInt32,
          ret,
          builder.makeConst(Literal(int32_t(USABLE_MEMORY - 1)))
        );
      }
      return ret;
    }
  
    Load* makeNonAtomicLoad(Type type) {
      auto offset = logify(get());
      auto ptr = makePointer();
      switch (type) {
        case 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();
        }
        case 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();
        }
        case f32: {
          return builder.makeLoad(4, false, offset, pick(1, 2, 4), ptr, type);
        }
        case f64: {
          return builder.makeLoad(8, false, offset, pick(1, 2, 4, 8), ptr, type);
        }
        default: WASM_UNREACHABLE();
      }
    }
  
    Expression* makeLoad(Type type) {
      auto* ret = makeNonAtomicLoad(type);
      if (type != i32 && type != i64) return ret;
      if (!emitAtomics || oneIn(2)) return ret;
      // make it atomic
      wasm.memory.shared = true;
      ret->isAtomic = true;
      ret->signed_ = false;
      ret->align = ret->bytes;
      return ret;
    }
  
    Store* makeNonAtomicStore(Type type) {
      if (type == unreachable) {
        // make a normal store, then make it unreachable
        auto* ret = makeNonAtomicStore(getConcreteType());
        switch (upTo(3)) {
          case 0: ret->ptr = make(unreachable); break;
          case 1: ret->value = make(unreachable); break;
          case 2: ret->ptr = make(unreachable); ret->value = make(unreachable); break;
        }
        ret->finalize();
        return ret;
      }
      // the type is none or unreachable. we also need to pick the value
      // type.
      if (type == none) {
        type = getConcreteType();
      }
      auto offset = logify(get());
      auto ptr = makePointer();
      auto value = make(type);
      switch (type) {
        case 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();
        }
        case 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();
        }
        case f32: {
          return builder.makeStore(4, offset, pick(1, 2, 4), ptr, value, type);
        }
        case f64: {
          return builder.makeStore(8, offset, pick(1, 2, 4, 8), ptr, value, type);
        }
        default: WASM_UNREACHABLE();
      }
    }
  
    Store* makeStore(Type type) {
      auto* ret = makeNonAtomicStore(type);
      if (ret->value->type != i32 && ret->value->type != i64) return ret;
      if (!emitAtomics || oneIn(2)) return ret;
      // make it atomic
      wasm.memory.shared = true;
      ret->isAtomic = true;
      ret->align = ret->bytes;
      return ret;
    }
  
    Expression* makeConst(Type type) {
      Literal value;
      switch (upTo(4)) {
        case 0: {
          // totally random, entire range
          switch (type) {
            case i32: value = Literal(get32()); break;
            case i64: value = Literal(get64()); break;
            case f32: value = Literal(getFloat()); break;
            case f64: value = Literal(getDouble()); break;
            default: WASM_UNREACHABLE();
          }
          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();
          }
          switch (type) {
            case i32: value = Literal(int32_t(small)); break;
            case i64: value = Literal(int64_t(small)); break;
            case f32: value = Literal(float(small)); break;
            case f64: value = Literal(double(small)); break;
            default: WASM_UNREACHABLE();
          }
          break;
        }
        case 2: {
          // special values
          switch (type) {
            case 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 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 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 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;
            default: WASM_UNREACHABLE();
          }
          // tweak around special values
          if (oneIn(3)) { // +- 1
            value = value.add(LiteralUtils::makeLiteralFromInt32(upTo(3) - 1, type));
          }
          if (oneIn(2)) { // flip sign
            value = value.mul(LiteralUtils::makeLiteralFromInt32(-1, type));
          }
          break;
        }
        case 3: {
          // powers of 2
          switch (type) {
            case i32: value = Literal(int32_t(1) << upTo(32)); break;
            case i64: value = Literal(int64_t(1) << upTo(64)); break;
            case f32: value = Literal(float(int64_t(1) << upTo(64))); break;
            case f64: value = Literal(double(int64_t(1) << upTo(64))); break;
            default: WASM_UNREACHABLE();
          }
          // maybe negative
          if (oneIn(2)) {
            value = value.mul(LiteralUtils::makeLiteralFromInt32(-1, type));
          }
        }
      }
      auto* ret = wasm.allocator.alloc<Const>();
      ret->value = value;
      ret->type = value.type;
      return ret;
    }
  
    Expression* makeUnary(const UnaryArgs& args) {
      return builder.makeUnary(args.a, args.b);
    }
  
    Expression* makeUnary(Type type) {
      if (type == unreachable) {
        if (auto* unary = makeUnary(getConcreteType())->dynCast<Unary>()) {
          return makeDeNanOp(builder.makeUnary(unary->op, make(unreachable)));
        }
        // give up
        return makeTrivial(type);
      }
      switch (type) {
        case i32: {
          switch (upTo(4)) {
            case 0: {
              if (emitAtomics) {
                return makeUnary({ pick(EqZInt32, ClzInt32, CtzInt32, PopcntInt32, ExtendS8Int32, ExtendS16Int32), make(i32) });
              } else {
                return makeUnary({ pick(EqZInt32, ClzInt32, CtzInt32, PopcntInt32), make(i32) });
              }
              break;
            }
            case 1: return makeUnary({ pick(EqZInt64, WrapInt64), make(i64) });
            case 2: return makeUnary({ pick(TruncSFloat32ToInt32, TruncUFloat32ToInt32, ReinterpretFloat32), make(f32) });
            case 3: return makeUnary({ pick(TruncSFloat64ToInt32, TruncUFloat64ToInt32), make(f64) });
          }
          WASM_UNREACHABLE();
        }
        case i64: {
          switch (upTo(4)) {
            case 0: {
              if (emitAtomics) {
                return makeUnary({ pick(ClzInt64, CtzInt64, PopcntInt64, ExtendS8Int64, ExtendS16Int64, ExtendS32Int64), make(i64) });
              } else {
                return makeUnary({ pick(ClzInt64, CtzInt64, PopcntInt64), make(i64) });
              }
              break;
            }
            case 1: return makeUnary({ pick(ExtendSInt32, ExtendUInt32), make(i32) });
            case 2: return makeUnary({ pick(TruncSFloat32ToInt64, TruncUFloat32ToInt64), make(f32) });
            case 3: return makeUnary({ pick(TruncSFloat64ToInt64, TruncUFloat64ToInt64, ReinterpretFloat64), make(f64) });
          }
          WASM_UNREACHABLE();
        }
        case f32: {
          switch (upTo(4)) {
            case 0: return makeDeNanOp(makeUnary({ pick(NegFloat32, AbsFloat32, CeilFloat32, FloorFloat32, TruncFloat32, NearestFloat32, SqrtFloat32), make(f32) }));
            case 1: return makeDeNanOp(makeUnary({ pick(ConvertUInt32ToFloat32, ConvertSInt32ToFloat32, ReinterpretInt32), make(i32) }));
            case 2: return makeDeNanOp(makeUnary({ pick(ConvertUInt64ToFloat32, ConvertSInt64ToFloat32), make(i64) }));
            case 3: return makeDeNanOp(makeUnary({ DemoteFloat64, make(f64) }));
          }
          WASM_UNREACHABLE();
        }
        case f64: {
          switch (upTo(4)) {
            case 0: return makeDeNanOp(makeUnary({ pick(NegFloat64, AbsFloat64, CeilFloat64, FloorFloat64, TruncFloat64, NearestFloat64, SqrtFloat64), make(f64) }));
            case 1: return makeDeNanOp(makeUnary({ pick(ConvertUInt32ToFloat64, ConvertSInt32ToFloat64), make(i32) }));
            case 2: return makeDeNanOp(makeUnary({ pick(ConvertUInt64ToFloat64, ConvertSInt64ToFloat64, ReinterpretInt64), make(i64) }));
            case 3: return makeDeNanOp(makeUnary({ PromoteFloat32, make(f32) }));
          }
          WASM_UNREACHABLE();
        }
        default: WASM_UNREACHABLE();
      }
      WASM_UNREACHABLE();
    }
  
    Expression* makeBinary(const BinaryArgs& args) {
      return builder.makeBinary(args.a, args.b, args.c);
    }
  
    Expression* makeBinary(Type type) {
      if (type == unreachable) {
        if (auto* binary = makeBinary(getConcreteType())->dynCast<Binary>()) {
          return makeDeNanOp(makeBinary({ binary->op, make(unreachable), make(unreachable) }));
        }
        // give up
        return makeTrivial(type);
      }
      switch (type) {
        case i32: {
          switch (upTo(4)) {
            case 0: return makeBinary({ 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(i32), make(i32) });
            case 1: return makeBinary({ pick(EqInt64, NeInt64, LtSInt64, LtUInt64, LeSInt64, LeUInt64, GtSInt64, GtUInt64, GeSInt64, GeUInt64), make(i64), make(i64) });
            case 2: return makeBinary({ pick(EqFloat32, NeFloat32, LtFloat32, LeFloat32, GtFloat32, GeFloat32), make(f32), make(f32) });
            case 3: return makeBinary({ pick(EqFloat64, NeFloat64, LtFloat64, LeFloat64, GtFloat64, GeFloat64), make(f64), make(f64) });
          }
          WASM_UNREACHABLE();
        }
        case i64: {
          return makeBinary({ pick(AddInt64, SubInt64, MulInt64, DivSInt64, DivUInt64, RemSInt64, RemUInt64, AndInt64, OrInt64, XorInt64, ShlInt64, ShrUInt64, ShrSInt64, RotLInt64, RotRInt64), make(i64), make(i64) });
        }
        case f32: {
          return makeDeNanOp(makeBinary({ pick(AddFloat32, SubFloat32, MulFloat32, DivFloat32, CopySignFloat32, MinFloat32, MaxFloat32), make(f32), make(f32) }));
        }
        case f64: {
          return makeDeNanOp(makeBinary({ pick(AddFloat64, SubFloat64, MulFloat64, DivFloat64, CopySignFloat64, MinFloat64, MaxFloat64), make(f64), make(f64) }));
        }
        default: WASM_UNREACHABLE();
      }
      WASM_UNREACHABLE();
    }
  
    Expression* makeSelect(const ThreeArgs& args) {
      return builder.makeSelect(args.a, args.b, args.c);
    }
  
    Expression* makeSelect(Type type) {
      return makeDeNanOp(makeSelect({ make(i32), make(type), make(type) }));
    }
  
    Expression* makeSwitch(Type type) {
      assert(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 = unreachable;
      while (tries-- > 0) {
        auto* target = vectorPick(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(i32), temp2 = isConcreteType(valueType) ? make(valueType) : nullptr;
      return builder.makeSwitch(names, default_, temp1, temp2);
    }
  
    Expression* makeDrop(Type type) {
      return builder.makeDrop(make(type == unreachable ? type : getConcreteType()));
    }
  
    Expression* makeReturn(Type type) {
      return builder.makeReturn(isConcreteType(func->result) ? make(func->result) : nullptr);
    }
  
    Expression* makeNop(Type type) {
      assert(type == none);
      return builder.makeNop();
    }
  
    Expression* makeUnreachable(Type type) {
      assert(type == unreachable);
      return builder.makeUnreachable();
    }
  
    Expression* makeAtomic(Type type) {
      if (!emitAtomics || (type != i32 && type != i64)) return makeTrivial(type);
      wasm.memory.shared = true;
      if (type == i32 && oneIn(2)) {
        if (ATOMIC_WAITS && oneIn(2)) {
          auto* ptr = makePointer();
          auto expectedType = pick(i32, i64);
          auto* expected = make(expectedType);
          auto* timeout = make(i64);
          return builder.makeAtomicWait(ptr, expected, timeout, expectedType, logify(get()));
        } else {
          auto* ptr = makePointer();
          auto* count = make(i32);
          return builder.makeAtomicWake(ptr, count, logify(get()));
        }
      }
      Index bytes;
      switch (type) {
        case 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();
          }
          break;
        }
        case 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();
          }
          break;
        }
        default: WASM_UNREACHABLE();
      }
      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);
      }
    }
  
    // special getters
  
    Type getType() {
      switch (upTo(6)) {
        case 0: return i32;
        case 1: return i64;
        case 2: return f32;
        case 3: return f64;
        case 4: return none;
        case 5: return unreachable;
      }
      WASM_UNREACHABLE();
    }
  
    Type getReachableType() {
      switch (upTo(5)) {
        case 0: return i32;
        case 1: return i64;
        case 2: return f32;
        case 3: return f64;
        case 4: return none;
      }
      WASM_UNREACHABLE();
    }
  
    Type getConcreteType() {
      switch (upTo(4)) {
        case 0: return i32;
        case 1: return i64;
        case 2: return f32;
        case 3: return f64;
      }
      WASM_UNREACHABLE();
    }
  
    // 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
    template<typename T>
    const T& vectorPick(const std::vector<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
  
    // 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();
    }
  
    Type getTargetType(Expression* target) {
      if (auto* block = target->dynCast<Block>()) {
        return block->type;
      } else if (target->is<Loop>()) {
        return none;
      }
      WASM_UNREACHABLE();
    }
  };
  
  } // 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
  
  