src/tools/wasm-reduce/wasm-reduce.cpp

/*
 * 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.
 */

//
// Tries to reduce the input wasm into the smallest possible wasm
// that still generates the same result on a given command. This is
// useful to reduce bug testcases, for example, if a file crashes
// the optimizer, you can reduce it to find the smallest file that
// also crashes it (which generally will show the same bug, in a
// much more debuggable manner).
//

#include <cstdio>
#include <cstdlib>
#include <memory>

#include "ir/branch-utils.h"
#include "ir/eh-utils.h"
#include "ir/iteration.h"
#include "ir/localize.h"
#include "ir/properties.h"
#include "ir/utils.h"
#include "pass.h"
#include "support/colors.h"
#include "support/command-line.h"
#include "support/delta_debugging.h"
#include "support/file.h"
#include "support/hash.h"
#include "support/js-embedded-module.h"
#include "support/path.h"
#include "support/timing.h"
#include "tools/tool-options.h"
#include "wasm-builder.h"
#include "wasm-io.h"
#include "wasm-validator.h"

#ifdef _WIN32
#ifndef NOMINMAX
#define NOMINMAX
#endif
#include <windows.h>
// Create a string with last error message
std::string GetLastErrorStdStr() {
  DWORD error = GetLastError();
  if (error) {
    LPVOID lpMsgBuf;
    DWORD bufLen = FormatMessage(FORMAT_MESSAGE_ALLOCATE_BUFFER |
                                   FORMAT_MESSAGE_FROM_SYSTEM |
                                   FORMAT_MESSAGE_IGNORE_INSERTS,
                                 NULL,
                                 error,
                                 MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
                                 (LPTSTR)&lpMsgBuf,
                                 0,
                                 NULL);
    if (bufLen) {
      LPCSTR lpMsgStr = (LPCSTR)lpMsgBuf;
      std::string result(lpMsgStr, lpMsgStr + bufLen);
      LocalFree(lpMsgBuf);
      return result;
    }
  }
  return std::string();
}
#endif

using namespace wasm;

// A timeout on every execution of the command.
static size_t timeout = 2;

// A string of feature flags and other things to pass while reducing. The
// default of enabling all features should work in most cases.
static std::string extraFlags = "-all";

// Whether to save all intermediate working files as we go.
static bool saveAllWorkingFiles = false;

struct ProgramResult {
  int code;
  std::string output;
  double time;

  ProgramResult() = default;
  ProgramResult(std::string command) { getFromExecution(command); }

#ifdef _WIN32
  void getFromExecution(std::string command) {
    Timer timer;
    SECURITY_ATTRIBUTES saAttr;
    saAttr.nLength = sizeof(SECURITY_ATTRIBUTES);
    saAttr.bInheritHandle = TRUE;
    saAttr.lpSecurityDescriptor = NULL;

    HANDLE hChildStd_OUT_Rd;
    HANDLE hChildStd_OUT_Wr;

    if (
      // Create a pipe for the child process's STDOUT.
      !CreatePipe(&hChildStd_OUT_Rd, &hChildStd_OUT_Wr, &saAttr, 0) ||
      // Ensure the read handle to the pipe for STDOUT is not inherited.
      !SetHandleInformation(hChildStd_OUT_Rd, HANDLE_FLAG_INHERIT, 0)) {
      Fatal() << "CreatePipe \"" << command
              << "\" failed: " << GetLastErrorStdStr() << ".\n";
    }

    STARTUPINFO si;
    PROCESS_INFORMATION pi;

    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    si.hStdError = hChildStd_OUT_Wr;
    si.hStdOutput = hChildStd_OUT_Wr;
    si.dwFlags |= STARTF_USESTDHANDLES;
    ZeroMemory(&pi, sizeof(pi));

    // Start the child process.
    if (!CreateProcess(NULL, // No module name (use command line)
                       (LPSTR)command.c_str(), // Command line
                       NULL,                   // Process handle not inheritable
                       NULL,                   // Thread handle not inheritable
                       TRUE,                   // Set handle inheritance to TRUE
                       0,                      // No creation flags
                       NULL,                   // Use parent's environment block
                       NULL, // Use parent's starting directory
                       &si,  // Pointer to STARTUPINFO structure
                       &pi)  // Pointer to PROCESS_INFORMATION structure
    ) {
      Fatal() << "CreateProcess \"" << command
              << "\" failed: " << GetLastErrorStdStr() << ".\n";
    }

    // Wait until child process exits.
    DWORD retVal = WaitForSingleObject(pi.hProcess, timeout * 1000);
    if (retVal == WAIT_TIMEOUT) {
      printf("Command timeout: %s", command.c_str());
      TerminateProcess(pi.hProcess, -1);
    }
    DWORD dwordExitCode;
    if (!GetExitCodeProcess(pi.hProcess, &dwordExitCode)) {
      Fatal() << "GetExitCodeProcess failed: " << GetLastErrorStdStr() << ".\n";
    }
    code = (int)dwordExitCode;

    // Close process and thread handles.
    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);

    // Read output from the child process's pipe for STDOUT
    // Stop when there is no more data.
    {
      const int BUFSIZE = 4096;
      DWORD dwRead, dwTotal, dwTotalRead = 0;
      CHAR chBuf[BUFSIZE];
      BOOL bSuccess = FALSE;

      PeekNamedPipe(hChildStd_OUT_Rd, NULL, 0, NULL, &dwTotal, NULL);
      while (dwTotalRead < dwTotal) {
        bSuccess =
          ReadFile(hChildStd_OUT_Rd, chBuf, BUFSIZE - 1, &dwRead, NULL);
        if (!bSuccess || dwRead == 0)
          break;
        chBuf[dwRead] = 0;
        dwTotalRead += dwRead;
        output.append(chBuf);
      }
    }
    time = timer.totalElapsed();
  }
#else  // POSIX
  // runs the command and notes the output
  // TODO: also stderr, not just stdout?
  void getFromExecution(std::string command) {
    Timer timer;
    const int MAX_BUFFER = 1024;
    char buffer[MAX_BUFFER];
    FILE* stream = popen(
      ("timeout " + std::to_string(timeout) + "s " + command + " 2> /dev/null")
        .c_str(),
      "r");
    while (fgets(buffer, MAX_BUFFER, stream) != NULL) {
      output.append(buffer);
    }
    code = pclose(stream);
    time = timer.totalElapsed();
  }
#endif // _WIN32

  bool operator==(ProgramResult& other) {
    return code == other.code && output == other.output;
  }
  bool operator!=(ProgramResult& other) { return !(*this == other); }

  bool failed() { return code != 0; }

  void dump(std::ostream& o) {
    o << "[ProgramResult] code: " << code << " stdout: \n"
      << output << "[====]\nin " << time << " seconds\n[/ProgramResult]\n";
  }
};

namespace std {

inline std::ostream& operator<<(std::ostream& o, ProgramResult& result) {
  result.dump(o);
  return o;
}

} // namespace std

ProgramResult expected;

// The index of the working file we save, when saveAllWorkingFiles. We must
// store this globally so that the difference instances of Reducer do not
// overlap.
static size_t workingFileIndex = 0;

/// Runs the external `wasm-opt` binary with `args` on `inBytes` by writing to
// `testPath` and reading the result back into `outBytes`.
static bool runWasmOpt(const std::string& testPath,
                       const std::vector<char>& inBytes,
                       const std::string& args,
                       std::vector<char>& outBytes,
                       ProgramResult& result,
                       bool verbose = false,
                       std::string* outCmd = nullptr) {
  write_file(testPath, inBytes);
  std::string cmd = Path::getBinaryenBinaryTool("wasm-opt") + " " + testPath +
                    " -o " + testPath + " " + args;
  if (outCmd) {
    *outCmd = cmd;
  }
  if (verbose) {
    std::cerr << "|    trying pass command: " << cmd << "\n";
  }
  result.getFromExecution(cmd);
  if (result.failed()) {
    return false;
  }
  outBytes = read_file<std::vector<char>>(testPath, Flags::Binary);
  return true;
}

// Abstracts reading/writing the active WebAssembly module and testing candidate
// reductions. This allows the core reduction logic to operate identically on
// standalone .wasm/.wat files and embedded Wasm modules inside .js files.
struct TestCaseHandler {
  virtual ~TestCaseHandler() = default;

  // Returns the raw Wasm module bytes (binary or WAT text) of the active module
  // from the working state (extracting it from the working JS file in --js
  // mode).
  virtual std::vector<char> readWorking(const std::string& working) = 0;

  // Writes candidate raw Wasm module bytes to the working file (splicing them
  // as a JS byte array into the working .js file in --js mode).
  virtual void writeWorking(const std::vector<char>& bytes,
                            const std::string& working) = 0;

  // Writes candidate raw Wasm module bytes to the test file (splicing them as a
  // JS byte array into the test .js file in --js mode).
  virtual void writeTest(const std::vector<char>& bytes,
                         const std::string& test) = 0;

  // Writes candidate Wasm bytes to `test`, executes `command`, and returns true
  // if the output matches `expected`.
  bool testCandidate(const std::vector<char>& bytes,
                     const std::string& test,
                     const std::string& command,
                     ProgramResult& out) {
    writeTest(bytes, test);
    out.getFromExecution(command);
    return out == expected;
  }

  bool testCandidate(const std::vector<char>& bytes,
                     const std::string& test,
                     const std::string& command) {
    ProgramResult out;
    return testCandidate(bytes, test, command, out);
  }
};

// Handles standalone Wasm/WAT test cases where the working and test files are
// raw module files on disk.
struct WasmTestCaseHandler : public TestCaseHandler {
  std::vector<char> readWorking(const std::string& working) override {
    return read_file<std::vector<char>>(working, Flags::Binary);
  }

  void writeWorking(const std::vector<char>& bytes,
                    const std::string& working) override {
    write_file(working, bytes);
  }

  void writeTest(const std::vector<char>& bytes,
                 const std::string& test) override {
    write_file(test, bytes);
  }
};

// Handles JavaScript test cases containing embedded WebAssembly byte arrays.
struct JsTestCaseHandler : public TestCaseHandler {
  std::string workingJs;
  size_t moduleStart = 0;
  size_t moduleEnd = 0;
  std::vector<char> moduleBytes;

  explicit JsTestCaseHandler(std::string workingJs)
    : workingJs(std::move(workingJs)) {}

  void setActiveModule(const EmbeddedModule& mod) {
    moduleStart = mod.start;
    moduleEnd = mod.end;
    moduleBytes = mod.bytes;
  }

  std::vector<char> readWorking(const std::string& working) override {
    // Return the cached working bytes instead of reading them back from the
    // file because we wouldn't know which of potentially many modules embedded
    // in the file is the current one.
    return moduleBytes;
  }

  void writeWorking(const std::vector<char>& bytes,
                    const std::string& working) override {
    std::string formatted = formatByteArray(bytes);
    workingJs.replace(moduleStart, moduleEnd - moduleStart, formatted);
    moduleEnd = moduleStart + formatted.size();
    moduleBytes = bytes;
    write_file(working, workingJs);
  }

  void writeTest(const std::vector<char>& bytes,
                 const std::string& test) override {
    std::string formatted = formatByteArray(bytes);
    std::string candidateJs = workingJs.substr(0, moduleStart) + formatted +
                              workingJs.substr(moduleEnd);
    write_file(test, candidateJs);
  }
};

struct Reducer
  : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<Reducer>>> {
  TestCaseHandler& handler;
  std::string command, test, working;
  bool binary, deNan, verbose, debugInfo;
  ToolOptions& toolOptions;

  Reducer(TestCaseHandler& handler,
          std::string command,
          std::string test,
          std::string working,
          bool binary,
          bool deNan,
          bool verbose,
          bool debugInfo,
          ToolOptions& toolOptions)
    : handler(handler), command(command), test(test), working(working),
      binary(binary), deNan(deNan), verbose(verbose), debugInfo(debugInfo),
      toolOptions(toolOptions) {}

  // Runs passes in order to reduce as long as binary size continues to shrink.
  // Returns the pair of (original size, reduced size).
  std::pair<size_t, size_t> reduceUsingPasses() {
    // run optimization passes until we can't shrink it any more
    std::vector<std::string> passes = {
      // Optimization modes.
      "-Oz",
      "-Os",
      "-O1",
      "-O2",
      "-O3",
      "-O4",
      // Optimization modes + passes that work well with them.
      "--flatten -Os",
      "--flatten -O3",
      "--flatten --simplify-locals-notee-nostructure --local-cse -Os",
      "--type-ssa -Os --type-merging",
      "--gufa -O1",
      // Individual passes or combinations of them.
      "--coalesce-locals --vacuum",
      "--dae",
      "--dae-optimizing",
      "--dce",
      "--duplicate-function-elimination",
      "--enclose-world",
      "--gto --closed-world",
      "--inlining",
      "--inlining-optimizing",
      "--optimize-level=3 --inlining-optimizing",
      "--local-cse",
      "--memory-packing",
      "--remove-unused-names --merge-blocks --vacuum",
      "--optimize-instructions",
      "--precompute",
      "--remove-imports",
      "--remove-memory-init",
      "--remove-unused-names --remove-unused-brs",
      "--remove-unused-module-elements",
      "--remove-unused-nonfunction-module-elements",
      "--reorder-functions",
      "--reorder-locals",
      // TODO: signature* passes
      "--simplify-globals",
      "--simplify-locals --vacuum",
      "--strip",
      "--remove-unused-types --closed-world",
      "--vacuum"};
    auto workingBytes = handler.readWorking(working);
    auto initialSize = workingBytes.size();
    auto oldSize = initialSize;
    bool more = true;
    while (more) {
      // std::cerr << "|    starting passes loop iteration\n";
      more = false;
      // try both combining with a generic shrink (so minor pass overhead is
      // compensated for), and without
      for (auto pass : passes) {
        std::string args = pass + " " + extraFlags;
        if (!binary) {
          args += " -S ";
        }
        ProgramResult result;
        std::vector<char> candidateBytes;
        std::string currCommand;
        if (runWasmOpt(test,
                       workingBytes,
                       args,
                       candidateBytes,
                       result,
                       verbose,
                       &currCommand)) {
          auto newSize = candidateBytes.size();
          if (newSize < oldSize) {
            // the pass didn't fail, and the size looks smaller, so promising
            // see if it is still has the property we are preserving
            if (handler.testCandidate(candidateBytes, test, command)) {
              std::cerr << "|    command \"" << currCommand
                        << "\" succeeded, reduced size to " << newSize << '\n';
              saveWorking(candidateBytes);
              workingBytes = candidateBytes;
              more = true;
              oldSize = newSize;
            }
          }
        }
      }
    }
    if (verbose) {
      std::cerr << "|    done with passes for now\n";
    }
    return {initialSize, oldSize};
  }

  // does one pass of slow and destructive reduction. returns whether it
  // succeeded or not
  // the criterion here is a logical change in the program. this may actually
  // increase wasm size in some cases, but it should allow more reduction later.
  // @param factor how much to ignore. starting with a high factor skips through
  //               most of the file, which is often faster than going one by one
  //               from the start
  size_t reduceDestructively(uint64_t factor_) {
    factor = factor_;
    // prepare
    loadWorking();
    reduced = 0;
    funcsSeen = 0;
    // Before we do any changes, it should be valid to write out the module:
    // size should be as expected, and output should be as expected.
    ProgramResult result;
    if (!writeAndTestReduction(result)) {
      std::cerr << "\n|! WARNING: writing before destructive reduction fails, "
                   "very unlikely reduction can work\n"
                << result << '\n';
    }
    // destroy!
    walkModule(getModule());
    return reduced;
  }

  void loadWorking() {
    module = std::make_unique<Module>();

    toolOptions.applyOptionsBeforeParse(*module);

    // Assume we may need all features.
    module->features = FeatureSet::All;

    ModuleReader reader;
    try {
      reader.readData(handler.readWorking(working), *module);
    } catch (ParseException& p) {
      p.dump(std::cerr);
      std::cerr << '\n';
      Fatal() << "error in parsing working wasm binary";
    }

    toolOptions.applyOptionsAfterParse(*module);

    builder = std::make_unique<Builder>(*module);
    setModule(module.get());
  }

  // destructive reduction state

  size_t reduced;
  Expression* beforeReduction;
  std::unique_ptr<Module> module;
  std::unique_ptr<Builder> builder;
  Index funcsSeen;
  uint64_t factor;
  std::vector<char> lastTestBytes;

  // write the module and see if the command still fails on it as expected
  bool writeAndTestReduction() {
    ProgramResult result;
    return writeAndTestReduction(result);
  }

  bool writeAndTestReduction(ProgramResult& out) {
    // write the module out
    ModuleWriter writer(toolOptions.passOptions);
    writer.setBinary(binary);
    writer.setDebugInfo(debugInfo);
    lastTestBytes.clear();
    toolOptions.write(writer, *getModule(), lastTestBytes);
    // note that it is ok for the destructively-reduced module to be bigger
    // than the previous - each destructive reduction removes logical code,
    // and so is strictly better, even if the wasm binary format happens to
    // encode things slightly less efficiently.
    // test it
    return handler.testCandidate(lastTestBytes, test, command, out);
  }

  size_t decisionCounter = 0;

  bool shouldTryToReduce(size_t bonus = 1) {
    assert(bonus > 0);
    // Increment to avoid returning the same result each time.
    decisionCounter += bonus;
    return (decisionCounter % factor) <= bonus;
  }

  // Returns a random number in the range [0, max). This is deterministic given
  // all the previous work done in the reducer.
  size_t deterministicRandom(size_t max) {
    assert(max > 0);
    hash_combine(decisionCounter, max);
    return decisionCounter % max;
  }

  bool isOkReplacement(Expression* with) {
    if (deNan) {
      if (auto* c = with->dynCast<Const>()) {
        if (c->value.isNaN()) {
          return false;
        }
      }
    }
    return true;
  }

  // tests a reduction on the current traversal node, and undos if it failed
  bool tryToReplaceCurrent(Expression* with) {
    if (!isOkReplacement(with)) {
      return false;
    }
    auto* curr = getCurrent();
    // std::cerr << "try " << curr << " => " << with << '\n';
    if (curr->type != with->type) {
      return false;
    }
    if (!shouldTryToReduce()) {
      return false;
    }
    replaceCurrent(with);
    if (!writeAndTestReduction()) {
      replaceCurrent(curr);
      return false;
    }
    std::cerr << "|      tryToReplaceCurrent succeeded (in " << getLocation()
              << ")\n";
    noteReduction();
    return true;
  }

  void saveWorking(const std::vector<char>& bytes) {
    handler.writeWorking(bytes, working);
    if (saveAllWorkingFiles) {
      copy_file(working, working + '.' + std::to_string(workingFileIndex++));
    }
  }

  void noteReduction(size_t amount = 1) {
    reduced += amount;
    saveWorking(lastTestBytes);
  }

  // tests a reduction on an arbitrary child
  bool tryToReplaceChild(Expression*& child, Expression* with) {
    if (!isOkReplacement(with)) {
      return false;
    }
    if (child->type != with->type) {
      return false;
    }
    if (!shouldTryToReduce()) {
      return false;
    }
    auto* before = child;
    child = with;
    if (!writeAndTestReduction()) {
      child = before;
      return false;
    }
    std::cerr << "|      tryToReplaceChild succeeded (in " << getLocation()
              << ")\n";
    // std::cerr << "|      " << before << " => " << with << '\n';
    noteReduction();
    return true;
  }

  std::string getLocation() {
    if (getFunction()) {
      return getFunction()->name.toString();
    }
    return "(non-function context)";
  }

  // visitors. in each we try to remove code in a destructive and nontrivial
  // way. "nontrivial" means something that optimization passes can't achieve,
  // since we don't need to duplicate work that they do

  void visitExpression(Expression* curr) {
    // type-based reductions
    if (curr->type == Type::none) {
      if (tryToReduceCurrentToNop()) {
        return;
      }
    } else if (curr->type.isConcrete()) {
      if (tryToReduceCurrentToConst()) {
        return;
      }
    } else {
      assert(curr->type == Type::unreachable);
      if (tryToReduceCurrentToUnreachable()) {
        return;
      }
    }
    // specific reductions
    if (auto* iff = curr->dynCast<If>()) {
      if (iff->type == Type::none) {
        // perhaps we need just the condition?
        if (tryToReplaceCurrent(builder->makeDrop(iff->condition))) {
          return;
        }
      }
      handleCondition(iff->condition);
    } else if (auto* br = curr->dynCast<Break>()) {
      handleCondition(br->condition);
    } else if (auto* select = curr->dynCast<Select>()) {
      handleCondition(select->condition);
    } else if (auto* sw = curr->dynCast<Switch>()) {
      handleCondition(sw->condition);
      // Try to replace switch targets with the default
      for (auto& target : sw->targets) {
        if (target != sw->default_) {
          auto old = target;
          target = sw->default_;
          if (!tryToReplaceCurrent(curr)) {
            target = old;
          }
        }
      }
      // Try to shorten the list of targets.
      while (sw->targets.size() > 1) {
        auto last = sw->targets.back();
        sw->targets.pop_back();
        if (!tryToReplaceCurrent(curr)) {
          sw->targets.push_back(last);
          break;
        }
      }
    } else if (auto* block = curr->dynCast<Block>()) {
      if (!shouldTryToReduce()) {
        return;
      }
      // replace a singleton
      auto& list = block->list;
      if (list.size() == 1 &&
          !BranchUtils::BranchSeeker::has(block, block->name)) {
        if (tryToReplaceCurrent(block->list[0])) {
          return;
        }
      }
      // try to get rid of nops
      Index i = 0;
      while (list.size() > 1 && i < list.size()) {
        auto* curr = list[i];
        if (curr->is<Nop>() && shouldTryToReduce()) {
          // try to remove it
          for (Index j = i; j < list.size() - 1; j++) {
            list[j] = list[j + 1];
          }
          list.pop_back();
          if (writeAndTestReduction()) {
            std::cerr << "|      block-nop removed\n";
            noteReduction();
            return;
          }
          list.push_back(nullptr);
          // we failed; undo
          for (Index j = list.size() - 1; j > i; j--) {
            list[j] = list[j - 1];
          }
          list[i] = curr;
        }
        i++;
      }
      return; // nothing more to do
    } else if (auto* loop = curr->dynCast<Loop>()) {
      if (shouldTryToReduce() &&
          !BranchUtils::BranchSeeker::has(loop, loop->name)) {
        tryToReplaceCurrent(loop->body);
      }
      return; // nothing more to do
    } else if (curr->is<Drop>()) {
      if (curr->type == Type::none) {
        // We can't improve this: the child has a different type than us. Return
        // here to avoid reaching the code below that tries to add a drop on
        // children (which would recreate the current state).
        return;
      }
    } else if (auto* structNew = curr->dynCast<StructNew>()) {
      // If all the fields are defaultable, try to replace this with a
      // struct.new_with_default.
      if (!structNew->isWithDefault() && structNew->type != Type::unreachable) {
        auto& fields = structNew->type.getHeapType().getStruct().fields;
        if (std::all_of(fields.begin(), fields.end(), [&](auto& field) {
              return field.type.isDefaultable();
            })) {
          ExpressionList operands(getModule()->allocator);
          operands.swap(structNew->operands);
          assert(structNew->isWithDefault());
          if (tryToReplaceCurrent(structNew)) {
            return;
          } else {
            structNew->operands.swap(operands);
            assert(!structNew->isWithDefault());
          }
        }
      }
    }
    // Finally, try to replace with a child.
    for (auto* child : ChildIterator(curr)) {
      if (child->type.isConcrete() && curr->type == Type::none) {
        if (tryToReplaceCurrent(builder->makeDrop(child))) {
          return;
        }
      } else {
        if (tryToReplaceCurrent(child)) {
          return;
        }
      }
    }
    // If that didn't work, try to replace with a child + a unary conversion,
    // but not if it's already unary
    if (curr->type.isSingle() && !curr->is<Unary>()) {
      for (auto* child : ChildIterator(curr)) {
        if (child->type == curr->type) {
          continue; // already tried
        }
        if (!child->type.isSingle()) {
          continue; // no conversion
        }
        Expression* fixed = nullptr;
        if (!curr->type.isBasic() || !child->type.isBasic()) {
          // TODO: handle compound types
          continue;
        }
        switch (curr->type.getBasic()) {
          case Type::i32: {
            TODO_SINGLE_COMPOUND(child->type);
            switch (child->type.getBasic()) {
              case Type::i32:
                WASM_UNREACHABLE("invalid type");
              case Type::i64:
                fixed = builder->makeUnary(WrapInt64, child);
                break;
              case Type::f32:
                fixed = builder->makeUnary(TruncSFloat32ToInt32, child);
                break;
              case Type::f64:
                fixed = builder->makeUnary(TruncSFloat64ToInt32, child);
                break;
              // not implemented yet
              case Type::v128:
                continue;
              case Type::none:
              case Type::unreachable:
                WASM_UNREACHABLE("unexpected type");
            }
            break;
          }
          case Type::i64: {
            TODO_SINGLE_COMPOUND(child->type);
            switch (child->type.getBasic()) {
              case Type::i32:
                fixed = builder->makeUnary(ExtendSInt32, child);
                break;
              case Type::i64:
                WASM_UNREACHABLE("invalid type");
              case Type::f32:
                fixed = builder->makeUnary(TruncSFloat32ToInt64, child);
                break;
              case Type::f64:
                fixed = builder->makeUnary(TruncSFloat64ToInt64, child);
                break;
              // not implemented yet
              case Type::v128:
                continue;
              case Type::none:
              case Type::unreachable:
                WASM_UNREACHABLE("unexpected type");
            }
            break;
          }
          case Type::f32: {
            TODO_SINGLE_COMPOUND(child->type);
            switch (child->type.getBasic()) {
              case Type::i32:
                fixed = builder->makeUnary(ConvertSInt32ToFloat32, child);
                break;
              case Type::i64:
                fixed = builder->makeUnary(ConvertSInt64ToFloat32, child);
                break;
              case Type::f32:
                WASM_UNREACHABLE("unexpected type");
              case Type::f64:
                fixed = builder->makeUnary(DemoteFloat64, child);
                break;
              // not implemented yet
              case Type::v128:
                continue;
              case Type::none:
              case Type::unreachable:
                WASM_UNREACHABLE("unexpected type");
            }
            break;
          }
          case Type::f64: {
            TODO_SINGLE_COMPOUND(child->type);
            switch (child->type.getBasic()) {
              case Type::i32:
                fixed = builder->makeUnary(ConvertSInt32ToFloat64, child);
                break;
              case Type::i64:
                fixed = builder->makeUnary(ConvertSInt64ToFloat64, child);
                break;
              case Type::f32:
                fixed = builder->makeUnary(PromoteFloat32, child);
                break;
              case Type::f64:
                WASM_UNREACHABLE("unexpected type");
              // not implemented yet
              case Type::v128:
                continue;
              case Type::none:
              case Type::unreachable:
                WASM_UNREACHABLE("unexpected type");
            }
            break;
          }
          // not implemented yet
          case Type::v128:
            continue;
          case Type::none:
          case Type::unreachable:
            WASM_UNREACHABLE("unexpected type");
        }
        assert(fixed->type == curr->type);
        if (tryToReplaceCurrent(fixed)) {
          return;
        }
      }
    }
  }

  void visitFunction(Function* curr) {
    // finish function
    funcsSeen++;
    static int last = 0;
    int percentage = (100 * funcsSeen) / getModule()->functions.size();
    if (std::abs(percentage - last) >= 5) {
      std::cerr << "|    " << percentage << "% of funcs complete\n";
      last = percentage;
    }
  }

  // TODO: bisection on segment shrinking?

  void visitDataSegment(DataSegment* curr) {
    // try to reduce to first function. first, shrink segment elements.
    // while we are shrinking successfully, keep going exponentially.
    bool shrank = false;
    shrank = shrinkByReduction(curr, 2);
    // the "opposite" of shrinking: copy a 'zero' element
    reduceByZeroing(curr, 0, [](char item) { return item == 0; }, 2, shrank);
  }

  template<typename T, typename U, typename C>
  void
  reduceByZeroing(T* segment, U zero, C isZero, size_t bonus, bool shrank) {
    for (auto& item : segment->data) {
      if (!shouldTryToReduce(bonus) || isZero(item)) {
        continue;
      }
      auto save = item;
      item = zero;
      if (writeAndTestReduction()) {
        std::cerr << "|      zeroed elem segment\n";
        noteReduction();
      } else {
        item = save;
      }
      if (shrank) {
        // zeroing is fairly inefficient. if we are managing to shrink
        // (which we do exponentially), just zero one per segment at most
        break;
      }
    }
  }

  template<typename T> bool shrinkByReduction(T* segment, size_t bonus) {
    // try to reduce to first function. first, shrink segment elements.
    // while we are shrinking successfully, keep going exponentially.
    bool justShrank = false;

    auto& data = segment->data;
    // when we succeed, try to shrink by more and more, similar to bisection
    uint64_t skip = 1;
    for (size_t i = 0; i < data.size() && !data.empty(); i++) {
      if (justShrank || shouldTryToReduce(bonus)) {
        auto save = data;
        for (size_t j = 0; j < skip; j++) {
          if (data.empty()) {
            break;
          } else {
            data.pop_back();
          }
        }
        justShrank = writeAndTestReduction();
        if (justShrank) {
          std::cerr << "|      shrank segment from " << save.size() << " => "
                    << data.size() << " (skip: " << skip << ")\n";
          noteReduction();
          skip = std::min(factor, 2 * skip);
        } else {
          data = std::move(save);
          return false;
        }
      }
    }

    return true;
  }

  void shrinkElementSegments() {
    std::cerr << "|    try to simplify elem segments\n";

    // First, shrink segment elements.
    bool shrank = false;
    for (auto& segment : module->elementSegments) {
      // Try to shrink all the segments (code in shrinkByReduction will decide
      // which to actually try to shrink, based on the current factor), and note
      // if we shrank anything at all (which we'll use later down).
      shrank = shrinkByReduction(segment.get(), 1) || shrank;
    }

    // Second, try to replace elements with a "zero".
    auto it =
      std::find_if_not(module->elementSegments.begin(),
                       module->elementSegments.end(),
                       [&](auto& segment) { return segment->data.empty(); });

    Expression* first = nullptr;
    if (it != module->elementSegments.end()) {
      first = it->get()->data[0];
    }
    if (first == nullptr) {
      // The elements are all empty, nothing left to do.
      return;
    }

    // the "opposite" of shrinking: copy a 'zero' element
    for (auto& segment : module->elementSegments) {
      reduceByZeroing(
        segment.get(),
        first,
        [&](Expression* elem) {
          if (elem->is<RefNull>()) {
            // We don't need to replace a ref.null.
            return true;
          }
          // Is the element equal to our first "zero" element?
          return ExpressionAnalyzer::equal(first, elem);
        },
        1,
        shrank);
    }
  }

  bool isEmptyBody(Expression* body) {
    if (body->is<Nop>() || body->is<Unreachable>()) {
      return true;
    }
    if (auto* block = body->dynCast<Block>()) {
      return block->list.empty();
    }
    return false;
  }

  void reduceFunctionBodies() {
    std::cerr << "|    try to remove function bodies\n";
    // Use function indices to speed up finding the complement of the kept
    // partition.
    std::vector<Index> nontrivialFuncIndices;
    nontrivialFuncIndices.reserve(module->functions.size());
    for (Index i = 0; i < module->functions.size(); ++i) {
      auto& func = module->functions[i];
      // Skip functions that already have trivial bodies.
      if (func->imported() || isEmptyBody(func->body)) {
        continue;
      }
      nontrivialFuncIndices.push_back(i);
    }
    DeltaDebugger<Index> dd(std::move(nontrivialFuncIndices));
    while (!dd.finished()) {
      // Stop early if the partition size is less than the square root of
      // the remaining set. We don't want to waste time on very fine-grained
      // partitions when we could switch to another reduction strategy
      // instead.
      if (size_t sqrtRemaining = std::sqrt(dd.working.size());
          dd.test.size() > 0 && dd.test.size() < sqrtRemaining) {
        break;
      }

      std::cerr << "|     try partition " << dd.partitionIndex() + 1 << " / "
                << dd.partitionCount() << " (size " << dd.test.size() << " / "
                << dd.working.size() << ")\n";
      Index removedSize = dd.working.size() - dd.test.size();
      std::vector<Expression*> oldBodies(removedSize);

      // We first need to remove each non-kept function body, and later we
      // might need to restore the same function bodies. Abstract the logic
      // for iterating over these function bodies. `f` takes a Function* and
      // Expression*& for the stashed body.
      auto forEachRemovedFuncBody = [&](auto f) {
        Index bodyIndex = 0;
        Index workingIndex = 0;
        Index testIndex = 0;
        while (workingIndex < dd.working.size()) {
          if (testIndex < dd.test.size() &&
              dd.working[workingIndex] == dd.test[testIndex]) {
            // Kept, skip it.
            workingIndex++;
            testIndex++;
          } else {
            // Removed, process it
            Index funcIndex = dd.working[workingIndex++];
            f(module->functions[funcIndex].get(), oldBodies[bodyIndex++]);
          }
        }
        assert(bodyIndex == removedSize);
        assert(testIndex == dd.test.size());
      };

      // Stash the bodies.
      forEachRemovedFuncBody([&](Function* func, Expression*& oldBody) {
        oldBody = func->body;
        Builder builder(*module);
        if (func->getResults() == Type::none) {
          func->body = builder.makeNop();
        } else {
          func->body = builder.makeUnreachable();
        }
      });

      if (!writeAndTestReduction()) {
        // Failure. Restore the bodies.
        forEachRemovedFuncBody(
          [](Function* func, Expression*& oldBody) { func->body = oldBody; });
        dd.reject();
      } else {
        // Success!
        noteReduction(removedSize);
        dd.accept();
      }
    }
  }

  void reduceFunctions() {
    std::cerr << "|    try to remove functions\n";

    // Find functions referenced from module code (i.e. global initializers). We
    // will not attempt to remove these functions because we cannot generally
    // replace their references with something valid.
    // TODO: Look at how the function references are used. If they can be
    // nullable, we can still consider deleting the functions.
    struct UnremovableFinder : public PostWalker<UnremovableFinder> {
      std::unordered_set<Name> unremovable;
      void visitRefFunc(RefFunc* curr) { unremovable.insert(curr->func); }
    };
    UnremovableFinder finder;
    finder.walkModuleCode(module.get());

    // Find the indices of functions we can consider removing or must not
    // remove.
    std::vector<Index> unremovableIndices;
    std::vector<Index> initialCandidates;
    initialCandidates.reserve(module->functions.size() -
                              finder.unremovable.size());
    for (Index i = 0; i < module->functions.size(); ++i) {
      if (finder.unremovable.contains(module->functions[i]->name)) {
        unremovableIndices.push_back(i);
      } else {
        initialCandidates.push_back(i);
      }
    }

    if (initialCandidates.empty()) {
      return;
    }

    // Indices will change as we remove functions. Map the original indices to
    // the present indices so we can use the original indices as stable
    // identifiers. (Function names are not necessarily preserved through
    // round-tripping.)
    std::vector<std::optional<Index>> currentIndices;
    currentIndices.reserve(module->functions.size());
    for (Index i = 0; i < module->functions.size(); ++i) {
      currentIndices.push_back(i);
    }

    DeltaDebugger<Index> dd(std::move(initialCandidates));
    while (!dd.finished()) {
      // Exit early if the test set size is less than the square root of the
      // working set size. We don't want to waste time on very fine-grained
      // partitions when we could switch to a different reduction strategy
      // instead.
      if (size_t sqrtRemaining = std::sqrt(dd.working.size());
          dd.test.size() > 0 && dd.test.size() < sqrtRemaining) {
        break;
      }

      std::cerr << "|     try partition " << dd.partitionIndex() + 1 << " / "
                << dd.partitionCount() << " (size " << dd.test.size() << " / "
                << dd.working.size() << ")\n";

      std::unordered_set<Index> keptIndices;
      for (Index i : unremovableIndices) {
        keptIndices.insert(*currentIndices[i]);
      }
      for (Index i : dd.test) {
        keptIndices.insert(*currentIndices[i]);
      }

      // Get the list of kept functions and the new index mapping we will have
      // to use if this reduction works.
      std::vector<std::unique_ptr<Function>> newFuncs;
      newFuncs.reserve(keptIndices.size());
      std::vector<std::optional<Index>> newCurrentIndices;
      newCurrentIndices.reserve(currentIndices.size());
      for (size_t i = 0; i < currentIndices.size(); ++i) {
        if (auto currIndex = currentIndices[i];
            currIndex && keptIndices.contains(*currIndex)) {
          newCurrentIndices.push_back(newFuncs.size());
          newFuncs.emplace_back(std::move(module->functions[*currIndex]));
        } else {
          newCurrentIndices.push_back(std::nullopt);
        }
      }

      module->functions = std::move(newFuncs);
      module->updateFunctionsMap();

      // Remove exports for functions we have removed.
      std::vector<Name> exportsToRemove;
      for (auto& exp : module->exports) {
        if (exp->kind == ExternalKind::Function &&
            !module->getFunctionOrNull(*exp->getInternalName())) {
          exportsToRemove.push_back(exp->name);
        }
      }
      for (auto expName : exportsToRemove) {
        module->removeExport(expName);
      }

      // We may have removed the start function.
      if (module->start && !module->getFunctionOrNull(module->start)) {
        module->start = Name();
      }

      struct FunctionReplacer
        : public WalkerPass<PostWalker<FunctionReplacer>> {
        bool isFunctionParallel() override { return true; }

        std::unique_ptr<Pass> create() override {
          return std::make_unique<FunctionReplacer>();
        };

        bool needEHFixups = false;

        void visitCall(Call* curr) {
          // Replace calls to functions we have removed.
          if (getModule()->getFunctionOrNull(curr->target)) {
            return;
          }
          Builder builder(*getModule());
          auto* block =
            ChildLocalizer(curr, getFunction(), *getModule(), getPassOptions())
              .getChildrenReplacement();
          auto originalType = curr->type;
          auto* replacement = builder.replaceWithIdenticalType(curr);
          // We may have failed to come up with a replacement (e.g. for
          // non-nullable references), so manually add an `unreachable` in that
          // case.
          if (replacement == curr) {
            replacement = builder.makeUnreachable();
          }
          block->list.push_back(replacement);
          block->type = originalType;
          replaceCurrent(block);
          // We added a block around content here, possibly causing us to need
          // EH fixups later.
          needEHFixups = true;
        }
        void visitRefFunc(RefFunc* curr) {
          // Replace references to functions we have removed.
          if (getModule()->getFunctionOrNull(curr->func)) {
            return;
          }
          Builder builder(*getModule());
          replaceCurrent(
            builder.makeBlock({builder.makeUnreachable()}, curr->type));
        }
        void visitFunction(Function* curr) {
          if (needEHFixups) {
            EHUtils::handleBlockNestedPops(curr, *getModule());
          }
        }
      };
      PassRunner runner(module.get());
      runner.add(std::make_unique<FunctionReplacer>());
      runner.run();

      assert(WasmValidator().validate(
        *module, WasmValidator::Globally | WasmValidator::Quiet));
      if (writeAndTestReduction()) {
        noteReduction(dd.working.size() - dd.test.size());
        currentIndices = std::move(newCurrentIndices);
        dd.accept();
      } else {
        loadWorking();
        dd.reject();
      }
    }
  }

  void visitModule([[maybe_unused]] Module* curr) {
    // The initial module given to us is our global object. As we continue to
    // process things here, we may replace the module, so we should never again
    // refer to curr.
    assert(curr == module.get());
    curr = nullptr;

    reduceFunctionBodies();
    reduceFunctions();

    shrinkElementSegments();

    // try to remove exports
    std::cerr << "|    try to remove exports (with factor " << factor << ")\n";
    std::vector<Export> exports;
    for (auto& exp : module->exports) {
      exports.push_back(*exp);
    }
    uint64_t skip = 1;
    for (size_t i = 0; i < exports.size(); i++) {
      if (!shouldTryToReduce(std::max((factor / 100) + 1, uint64_t(1000)))) {
        continue;
      }
      std::vector<Export> currExports;
      for (size_t j = 0; currExports.size() < skip && i + j < exports.size();
           j++) {
        auto exp = exports[i + j];
        if (module->getExportOrNull(exp.name)) {
          currExports.push_back(exp);
          module->removeExport(exp.name);
        }
      }
      ProgramResult result;
      if (!writeAndTestReduction(result)) {
        for (auto exp : currExports) {
          module->addExport(new Export(exp));
        }
        skip = std::max(skip / 2, uint64_t(1)); // or 1?
      } else {
        std::cerr << "|      removed " << currExports.size() << " exports\n";
        noteReduction(currExports.size());
        i += skip;
        skip = std::min(factor, 2 * skip);
      }
    }
    // If we are left with a single function that is not exported or used in
    // a table, that is useful as then we can change the return type.
    bool allTablesEmpty =
      std::all_of(module->elementSegments.begin(),
                  module->elementSegments.end(),
                  [&](auto& segment) { return segment->data.empty(); });

    if (module->functions.size() == 1 && module->exports.empty() &&
        allTablesEmpty) {
      auto* func = module->functions[0].get();
      // We can't remove something that might have breaks to it.
      if (!func->imported() && !Properties::isNamedControlFlow(func->body)) {
        auto funcType = func->type;
        auto* funcBody = func->body;
        for (auto* child : ChildIterator(func->body)) {
          if (!(child->type.isConcrete() || child->type == Type::none)) {
            continue; // not something a function can return
          }
          // Try to replace the body with the child, fixing up the function
          // to accept it.
          func->type =
            Type(Signature(funcType.getHeapType().getSignature().params,
                           child->type),
                 NonNullable,
                 Exact);
          func->body = child;
          if (writeAndTestReduction()) {
            // great, we succeeded!
            std::cerr << "|    altered function result type\n";
            noteReduction(1);
            break;
          }
          // Undo.
          func->type = funcType;
          func->body = funcBody;
        }
      }
    }
  }

  // helpers

  // try to replace condition with always true and always false
  void handleCondition(Expression*& condition) {
    if (!condition) {
      return;
    }
    if (condition->is<Const>()) {
      return;
    }
    auto* c = builder->makeConst(int32_t(0));
    if (!tryToReplaceChild(condition, c)) {
      c->value = Literal(int32_t(1));
      tryToReplaceChild(condition, c);
    }
  }

  bool tryToReduceCurrentToNop() {
    auto* curr = getCurrent();
    if (curr->is<Nop>()) {
      return false;
    }
    // try to replace with a trivial value
    Nop nop;
    if (tryToReplaceCurrent(&nop)) {
      replaceCurrent(builder->makeNop());
      return true;
    }
    return false;
  }

  // Try to replace a concrete value with a trivial constant.
  bool tryToReduceCurrentToConst() {
    auto* curr = getCurrent();

    // References.
    if (curr->type.isNullable() && !curr->is<RefNull>()) {
      RefNull* n = builder->makeRefNull(curr->type.getHeapType());
      return tryToReplaceCurrent(n);
    }

    // Tuples.
    if (curr->type.isTuple() && curr->type.isDefaultable()) {
      Expression* n =
        builder->makeConstantExpression(Literal::makeZeros(curr->type));
      if (ExpressionAnalyzer::equal(n, curr)) {
        return false;
      }
      return tryToReplaceCurrent(n);
    }

    // Numbers. We try to replace them with a 0 or a 1.
    if (!curr->type.isNumber()) {
      return false;
    }
    auto* existing = curr->dynCast<Const>();
    if (existing && existing->value.isZero()) {
      // It's already a zero.
      return false;
    }
    auto* c = builder->makeConst(Literal::makeZero(curr->type));
    if (tryToReplaceCurrent(c)) {
      return true;
    }
    // It's not a zero, and can't be replaced with a zero. Try to make it a one,
    // if it isn't already.
    if (existing &&
        existing->value == Literal::makeFromInt32(1, existing->type)) {
      // It's already a one.
      return false;
    }
    c->value = Literal::makeOne(curr->type);
    return tryToReplaceCurrent(c);
  }

  bool tryToReduceCurrentToUnreachable() {
    auto* curr = getCurrent();
    if (curr->is<Unreachable>()) {
      return false;
    }
    // try to replace with a trivial value
    Unreachable un;
    if (tryToReplaceCurrent(&un)) {
      replaceCurrent(builder->makeUnreachable());
      return true;
    }
    // maybe a return? TODO
    return false;
  }
};

static void
stopIfNotForced(std::string message, ProgramResult& result, bool force) {
  std::cerr << "|! " << message << '\n' << result << '\n';
  if (!force) {
    Fatal() << "|! stopping, as it is very unlikely reduction can succeed "
               "(use -f to ignore this check)";
  }
}

static void checkTimeout(ProgramResult& result, bool force) {
  if (result.time + 1 >= timeout) {
    stopIfNotForced("execution time is dangerously close to the timeout - you "
                    "should probably increase the timeout",
                    result,
                    force);
  }
}

static void checkDifferentBehaviorOnDifferentInputs(TestCaseHandler& handler,
                                                    const std::string& test,
                                                    const std::string& command,
                                                    bool force,
                                                    ToolOptions& options) {
  if (force) {
    return;
  }
  std::cerr << "|checking that command has different behavior on different "
               "inputs (this "
               "verifies that the test file is used by the command)\n";
  // Try it on an invalid input.
  std::string nonsenseStr = "waka waka\n";
  std::vector<char> nonsense(nonsenseStr.begin(), nonsenseStr.end());
  ProgramResult resultOnInvalid;
  if (handler.testCandidate(nonsense, test, command, resultOnInvalid)) {
    // Try it on a valid input.
    Module emptyModule;
    ModuleWriter writer(options.passOptions);
    writer.setBinary(true);
    std::vector<char> emptyBytes;
    options.write(writer, emptyModule, emptyBytes);
    ProgramResult resultOnValid;
    if (handler.testCandidate(emptyBytes, test, command, resultOnValid)) {
      Fatal()
        << "running the command on the given input gives the same result as "
           "when running it on either a trivial valid wasm or a file with "
           "nonsense in it. does the script not look at the test file (" +
             test + ")? (use -f to ignore this check)";
    }
  }
}

static void checkCanonicalizedBinary(TestCaseHandler& handler,
                                     const std::string& working,
                                     const std::string& test,
                                     const std::string& command,
                                     bool binary,
                                     bool force) {
  std::cerr << "|checking that command has expected behavior on canonicalized "
               "(read-written) binary\n";
  std::string args = extraFlags;
  if (!binary) {
    args += " -S ";
  }
  ProgramResult readWrite;
  std::vector<char> canonicalBytes;
  if (!runWasmOpt(
        test, handler.readWorking(working), args, canonicalBytes, readWrite)) {
    stopIfNotForced("failed to read and write the binary", readWrite, force);
  } else {
    ProgramResult result;
    if (!handler.testCandidate(canonicalBytes, test, command, result)) {
      stopIfNotForced("running command on the canonicalized module should "
                      "give the same results",
                      result,
                      force);
    }
  }
}

static void reduceModule(TestCaseHandler& handler,
                         const std::string& command,
                         const std::string& test,
                         const std::string& working,
                         bool binary,
                         bool deNan,
                         bool verbose,
                         bool debugInfo,
                         bool force,
                         ToolOptions& options) {
  checkDifferentBehaviorOnDifferentInputs(
    handler, test, command, force, options);
  checkCanonicalizedBinary(handler, working, test, command, binary, force);

  auto workingSize = handler.readWorking(working).size();
  std::cerr << "|input size: " << workingSize << "\n";

  std::cerr << "|starting reduction!\n";

  uint64_t factor = binary ? uint64_t(workingSize) * 2 : workingSize / 10;

  size_t lastDestructiveReductions = 0;
  size_t lastPostPassesSize = 0;

  bool stopping = false;

  bool first = true;
  while (1) {
    Reducer reducer(handler,
                    command,
                    test,
                    working,
                    binary,
                    deNan,
                    verbose,
                    debugInfo,
                    options);

    // For extremely large modules with slow reproduction commands, reducing
    // function bodies first can be more effective than running passes. TODO:
    // clean this up and reconsider the order of reducers.
    if (first) {
      reducer.loadWorking();
      reducer.reduceFunctionBodies();
      reducer.reduceFunctions();
      first = false;
    }

    // run binaryen optimization passes to reduce. passes are fast to run
    // and can often reduce large amounts of code efficiently, as opposed
    // to destructive reduction (i.e., that doesn't preserve correctness as
    // passes do) since destructive must operate one change at a time
    std::cerr << "|  reduce using passes...\n";
    auto [oldSize, newSize] = reducer.reduceUsingPasses();
    auto passProgress = oldSize - newSize;
    std::cerr << "|  after pass reduction: " << newSize << "\n";

    // always stop after a pass reduction attempt, for final cleanup
    if (stopping) {
      break;
    }

    // check if the full cycle (destructive/passes) has helped or not
    if (lastPostPassesSize && newSize >= lastPostPassesSize) {
      std::cerr << "|  progress has stopped, skipping to the end\n";
      if (factor == 1) {
        // this is after doing work with factor 1, so after the remaining work,
        // stop
        stopping = true;
      } else {
        // decrease the factor quickly
        factor = (factor + 1) / 2; // stable on 1
      }
    }
    lastPostPassesSize = newSize;

    // If destructive reductions lead to useful proportionate pass reductions,
    // keep going at the same factor, as pass reductions are far faster.
    std::cerr << "|  pass progress: " << passProgress
              << ", last destructive: " << lastDestructiveReductions << '\n';
    if (passProgress >= 4 * lastDestructiveReductions) {
      std::cerr << "|  progress is good, do not quickly decrease factor\n";
      // While the amount of pass reductions is proportionately high, we do
      // still want to reduce the factor by some amount. If we do not then there
      // is a risk that both pass and destructive reductions are very low, and
      // we get "stuck" cycling through them. In that case we simply need to do
      // more destructive reductions to make real progress. For that reason,
      // decrease the factor by some small percentage.
      factor = std::max(uint64_t(1), uint64_t(factor * 0.9));
    } else {
      if (factor > 10) {
        factor = (factor / 3) + 1;
      } else {
        factor = (factor + 1) / 2; // stable on 1
      }
    }

    // no point in a factor larger than the size
    assert(newSize > 4); // wasm modules are >4 bytes anyhow
    factor = std::min(factor, uint64_t(newSize / 4));

    // try to reduce destructively. if a high factor fails to find anything,
    // quickly try a lower one (no point in doing passes until we reduce
    // destructively at least a little)
    while (1) {
      std::cerr << "|  reduce destructively... (factor: " << factor << ")\n";
      lastDestructiveReductions = reducer.reduceDestructively(factor);
      if (lastDestructiveReductions > 0) {
        break;
      }
      // we failed to reduce destructively
      if (factor == 1) {
        stopping = true;
        break;
      }
      // Quickly try to find *something* we can reduce.
      factor = std::max(uint64_t(1), factor / 4);
    }

    std::cerr << "|  destructive reduction led to size: "
              << handler.readWorking(working).size() << '\n';
  }
  auto finalBytes = handler.readWorking(working);
  std::cerr << "|finished, final size: " << finalBytes.size() << "\n";
  handler.writeTest(finalBytes, test); // just to avoid confusion
}

//
// main
//

int main(int argc, const char* argv[]) {
  std::string input, test, working, command;
  // By default, look for binaries alongside our own binary.
  std::string binDir = Path::getDirName(argv[0]);
  bool binary = true, deNan = false, verbose = false, debugInfo = false,
       force = false, js = false;

  const std::string WasmReduceOption = "wasm-reduce options";

  ToolOptions options(
    "wasm-reduce",
    R"(Reduce a wasm file to a smaller one with the same behavior on a given command.

Typical usage:

  wasm-reduce orig.wasm '--command=bash a.sh' --test t.wasm --working w.wasm

The original file orig.wasm is where we begin. We then repeatedly test a small
reduction of it by writing that modification to the 'test file' (specified by
'--test'), and we run the command, in this example 'bash a.sh'. That command
should use the test file (and not the original file or any other one). Whenever
the reduction works, we write that new smaller file to the 'working file'
(specified by '--working'). The reduction 'works' if it correctly preserves the
behavior of the command on the original input, specifically, that it has the
same stdout and the result return code. Each time reduction works we continue to
reduce from that point (and each time it fails, we go back and try something
else).

As mentioned above, the command should run on the test file. That is, the first
thing that wasm-reduce does on the example above is, effectively,

  cp orig.wasm t.wasm
  bash a.sh

In other words, it copies the original to the test file, and runs the command.
Whatever the command does, we will preserve as we copy progressively smaller
files to t.wasm. As we make progress, the smallest file will be written to
the working file, w.wasm, and when reduction is done you will find the final
result there.

Comparison to creduce:

1. creduce requires the command to return 0. wasm-reduce is often used to reduce
   crashes, which have non-zero return codes, so it is natural to allow any
   return code. As mentioned above, we preserve the return code as we reduce.
2. creduce ignores stdout. wasm-reduce preserves stdout as it reduces, as part
   of the principle of preserving the original behavior of the command (if your
   stdout varies in uninteresting ways, your command can be a script that runs
   the real command and captures stdout to /dev/null, or filters it).
3. creduce tramples the original input file as it reduces. wasm-reduce never
   modifies the input (to avoid mistakes that cause data loss). Instead,
   when reductions work we write to the 'working file' as mentioned above, and
   the final reduction will be there.
4. creduce runs the command in a temp directory. That is safer in general, but
   it is not how the original command ran, and in particular forces additional
   work if you have multiple files (which, for wasm-reduce, is common, e.g. if
   the testcase is a combination of JavaScript and wasm). wasm-reduce runs the
   command in the current directory (of course, your command can be a script
   that changes directory to anywhere else).

More documentation can be found at

  https://github.com/WebAssembly/binaryen/wiki/Fuzzing#reducing
)");
  options
    .add("--command",
         "-cmd",
         "The command to run on the test, that we want to reduce while keeping "
         "the command's output identical. "
         "We look at the command's return code and stdout here (TODO: stderr), "
         "and we reduce while keeping those unchanged.",
         WasmReduceOption,
         Options::Arguments::One,
         [&](Options* o, const std::string& argument) { command = argument; })
    .add("--test",
         "-t",
         "Test file (this will be written to test, the given command should "
         "read it when we call it)",
         WasmReduceOption,
         Options::Arguments::One,
         [&](Options* o, const std::string& argument) { test = argument; })
    .add("--working",
         "-w",
         "Working file (this will contain the current good state while doing "
         "temporary computations, "
         "and will contain the final best result at the end)",
         WasmReduceOption,
         Options::Arguments::One,
         [&](Options* o, const std::string& argument) { working = argument; })
    .add("--binaries",
         "-b",
         "binaryen binaries location (bin/ directory)",
         WasmReduceOption,
         Options::Arguments::One,
         [&](Options* o, const std::string& argument) {
           // Add separator just in case
           binDir = argument + Path::getPathSeparator();
         })
    .add("--text",
         "-S",
         "Emit intermediate files as text, instead of binary (also make sure "
         "the test and working files have a .wat or .wast suffix)",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) { binary = false; })
    .add("--js",
         "",
         "Reduce embedded WebAssembly modules inside a JavaScript file",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) { js = true; })
    .add("--denan",
         "",
         "Avoid nans when reducing",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) { deNan = true; })
    .add("--verbose",
         "-v",
         "Verbose output mode",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) { verbose = true; })
    .add("--debugInfo",
         "-g",
         "Keep debug info in binaries",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) { debugInfo = true; })
    .add("--force",
         "-f",
         "Force the reduction attempt, ignoring problems that imply it is "
         "unlikely to succeed",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) { force = true; })
    .add("--timeout",
         "-to",
         "A timeout to apply to each execution of the command, in seconds "
         "(default: 2)",
         WasmReduceOption,
         Options::Arguments::One,
         [&](Options* o, const std::string& argument) {
           timeout = atoi(argument.c_str());
           std::cout << "|applying timeout: " << timeout << "\n";
         })
    .add("--extra-flags",
         "-ef",
         "Extra commandline flags to pass to wasm-opt while reducing. "
         "(default: --enable-all)",
         WasmReduceOption,
         Options::Arguments::One,
         [&](Options* o, const std::string& argument) {
           extraFlags = argument;
           std::cout << "|applying extraFlags: " << extraFlags << "\n";
         })
    .add("--save-all-working",
         "-saw",
         "Save all intermediate working files, as $WORKING.0, .1, .2 etc",
         WasmReduceOption,
         Options::Arguments::Zero,
         [&](Options* o, const std::string& argument) {
           saveAllWorkingFiles = true;
           std::cout << "|saving all intermediate working files\n";
         })
    .add_positional(
      "INFILE",
      Options::Arguments::One,
      [&](Options* o, const std::string& argument) { input = argument; });
  options.parse(argc, argv);

  if (js && !binary) {
    Fatal() << "--js and --text cannot be used together\n";
  }

  if (debugInfo) {
    extraFlags += " -g ";
  }
  if (options.emitModuleNames) {
    extraFlags += " --emit-module-names ";
  }

  if (test.size() == 0) {
    Fatal() << "test file not provided\n";
  }
  if (working.size() == 0) {
    Fatal() << "working file not provided\n";
  }

  if (!binary) {
    Colors::setEnabled(false);
  }

  Path::setBinaryenBinDir(binDir);

  std::cerr << "|wasm-reduce\n";
  std::cerr << "|input: " << input << '\n';
  std::cerr << "|test: " << test << '\n';
  std::cerr << "|working: " << working << '\n';
  std::cerr << "|bin dir: " << binDir << '\n';
  std::cerr << "|extra flags: " << extraFlags << '\n';

  // get the expected output
  copy_file(input, test);
  expected.getFromExecution(command);

  std::cerr << "|expected result:\n" << expected << '\n';
  std::cerr << "|!! Make sure the above is what you expect! !!\n\n";

  checkTimeout(expected, force);

  copy_file(input, working);

  if (js) {
    auto workingJs = read_file<std::string>(working, Flags::Binary);
    auto modules = findEmbeddedModules(workingJs);
    if (modules.empty()) {
      Fatal() << "no embedded wasm modules found in " << input << "\n";
    }
    JsTestCaseHandler handler(std::move(workingJs));
    for (size_t i = modules.size(); i > 0; --i) {
      size_t idx = i - 1;
      std::cerr << "|reducing embedded module " << idx << " of "
                << modules.size() << "\n";
      handler.setActiveModule(modules[idx]);
      reduceModule(handler,
                   command,
                   test,
                   working,
                   binary,
                   deNan,
                   verbose,
                   debugInfo,
                   force,
                   options);
    }
  } else {
    WasmTestCaseHandler handler;
    reduceModule(handler,
                 command,
                 test,
                 working,
                 binary,
                 deNan,
                 verbose,
                 debugInfo,
                 force,
                 options);
  }
}