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

#include <chrono>
#include <sstream>

#ifdef __linux__
#include <unistd.h>
#endif

#include "ir/hashed.h"
#include "ir/module-utils.h"
#include "ir/type-updating.h"
#include "pass.h"
#include "passes/passes.h"
#include "support/colors.h"
#include "wasm-debug.h"
#include "wasm-io.h"
#include "wasm-validator.h"

namespace wasm {

// PassRegistry

PassRegistry::PassRegistry() { registerPasses(); }

static PassRegistry singleton;

PassRegistry* PassRegistry::get() { return &singleton; }

void PassRegistry::registerPass(const char* name,
                                const char* description,
                                Creator create) {
  assert(passInfos.find(name) == passInfos.end());
  passInfos[name] = PassInfo(description, create);
}

void PassRegistry::registerTestPass(const char* name,
                                    const char* description,
                                    Creator create) {
  assert(passInfos.find(name) == passInfos.end());
  passInfos[name] = PassInfo(description, create, true);
}

std::unique_ptr<Pass> PassRegistry::createPass(std::string name) {
  if (passInfos.find(name) == passInfos.end()) {
    Fatal() << "Could not find pass: " << name << "\n";
  }
  std::unique_ptr<Pass> ret;
  ret.reset(passInfos[name].create());
  ret->name = name;
  return ret;
}

std::vector<std::string> PassRegistry::getRegisteredNames() {
  std::vector<std::string> ret;
  for (auto& [name, _] : passInfos) {
    ret.push_back(name);
  }
  return ret;
}

std::string PassRegistry::getPassDescription(std::string name) {
  assert(passInfos.find(name) != passInfos.end());
  return passInfos[name].description;
}

bool PassRegistry::isPassHidden(std::string name) {
  assert(passInfos.find(name) != passInfos.end());
  return passInfos[name].hidden;
}

// PassRunner

void PassRegistry::registerPasses() {
  registerPass("alignment-lowering",
               "lower unaligned loads and stores to smaller aligned ones",
               createAlignmentLoweringPass);
  registerPass("asyncify",
               "async/await style transform, allowing pausing and resuming",
               createAsyncifyPass);
  registerPass("avoid-reinterprets",
               "Tries to avoid reinterpret operations via more loads",
               createAvoidReinterpretsPass);
  registerPass(
    "dae", "removes arguments to calls in an lto-like manner", createDAEPass);
  registerPass("dae-optimizing",
               "removes arguments to calls in an lto-like manner, and "
               "optimizes where we removed",
               createDAEOptimizingPass);
  registerPass("abstract-type-refining",
               "refine and merge abstract (never-created) types",
               createAbstractTypeRefiningPass);
  registerPass("coalesce-locals",
               "reduce # of locals by coalescing",
               createCoalesceLocalsPass);
  registerPass("coalesce-locals-learning",
               "reduce # of locals by coalescing and learning",
               createCoalesceLocalsWithLearningPass);
  registerPass("code-pushing",
               "push code forward, potentially making it not always execute",
               createCodePushingPass);
  registerPass(
    "code-folding", "fold code, merging duplicates", createCodeFoldingPass);
  registerPass("const-hoisting",
               "hoist repeated constants to a local",
               createConstHoistingPass);
  registerPass("cfp",
               "propagate constant struct field values",
               createConstantFieldPropagationPass);
  registerPass(
    "dce", "removes unreachable code", createDeadCodeEliminationPass);
  registerPass("dealign",
               "forces all loads and stores to have alignment 1",
               createDeAlignPass);
  registerPass("denan",
               "instrument the wasm to convert NaNs into 0 at runtime",
               createDeNaNPass);
  registerPass(
    "directize", "turns indirect calls into direct ones", createDirectizePass);
  registerPass("discard-global-effects",
               "discards global effect info",
               createDiscardGlobalEffectsPass);
  registerPass(
    "dfo", "optimizes using the DataFlow SSA IR", createDataFlowOptsPass);
  registerPass("dwarfdump",
               "dump DWARF debug info sections from the read binary",
               createDWARFDumpPass);
  registerPass("duplicate-import-elimination",
               "removes duplicate imports",
               createDuplicateImportEliminationPass);
  registerPass("duplicate-function-elimination",
               "removes duplicate functions",
               createDuplicateFunctionEliminationPass);
  registerPass("emit-target-features",
               "emit the target features section in the output",
               createEmitTargetFeaturesPass);
  registerPass("extract-function",
               "leaves just one function (useful for debugging)",
               createExtractFunctionPass);
  registerPass("extract-function-index",
               "leaves just one function selected by index",
               createExtractFunctionIndexPass);
  registerPass(
    "flatten", "flattens out code, removing nesting", createFlattenPass);
  registerPass("fpcast-emu",
               "emulates function pointer casts, allowing incorrect indirect "
               "calls to (sometimes) work",
               createFuncCastEmulationPass);
  registerPass(
    "func-metrics", "reports function metrics", createFunctionMetricsPass);
  registerPass("generate-dyncalls",
               "generate dynCall fuctions used by emscripten ABI",
               createGenerateDynCallsPass);
  registerPass(
    "generate-i64-dyncalls",
    "generate dynCall functions used by emscripten ABI, but only for "
    "functions with i64 in their signature (which cannot be invoked "
    "via the wasm table without JavaScript BigInt support).",
    createGenerateI64DynCallsPass);
  registerPass("generate-global-effects",
               "generate global effect info (helps later passes)",
               createGenerateGlobalEffectsPass);
  registerPass(
    "generate-stack-ir", "generate Stack IR", createGenerateStackIRPass);
  registerPass(
    "global-refining", "refine the types of globals", createGlobalRefiningPass);
  registerPass(
    "gsi", "globally optimize struct values", createGlobalStructInferencePass);
  registerPass(
    "gto", "globally optimize GC types", createGlobalTypeOptimizationPass);
  registerPass("gufa",
               "Grand Unified Flow Analysis: optimize the entire program using "
               "information about what content can actually appear in each "
               "location",
               createGUFAPass);
  registerPass("gufa-cast-all",
               "GUFA plus add casts for all inferences",
               createGUFACastAllPass);
  registerPass("gufa-optimizing",
               "GUFA plus local optimizations in functions we modified",
               createGUFAOptimizingPass);
  registerPass(
    "optimize-j2cl", "optimizes J2CL specific constructs.", createJ2CLOptsPass);
  registerPass("type-refining",
               "apply more specific subtypes to type fields where possible",
               createTypeRefiningPass);
  registerPass(
    "heap2local", "replace GC allocations with locals", createHeap2LocalPass);
  registerPass(
    "inline-main", "inline __original_main into main", createInlineMainPass);
  registerPass("inlining",
               "inline functions (you probably want inlining-optimizing)",
               createInliningPass);
  registerPass("inlining-optimizing",
               "inline functions and optimizes where we inlined",
               createInliningOptimizingPass);
  registerPass("intrinsic-lowering",
               "lower away binaryen intrinsics",
               createIntrinsicLoweringPass);
  registerPass("jspi",
               "wrap imports and exports for JavaScript promise integration",
               createJSPIPass);
  registerPass("legalize-js-interface",
               "legalizes i64 types on the import/export boundary",
               createLegalizeJSInterfacePass);
  registerPass("legalize-and-prune-js-interface",
               "legalizes the import/export boundary and prunes when needed",
               createLegalizeAndPruneJSInterfacePass);
  registerPass("local-cse",
               "common subexpression elimination inside basic blocks",
               createLocalCSEPass);
  registerPass("local-subtyping",
               "apply more specific subtypes to locals where possible",
               createLocalSubtypingPass);
  registerPass("log-execution",
               "instrument the build with logging of where execution goes",
               createLogExecutionPass);
  registerPass("i64-to-i32-lowering",
               "lower all uses of i64s to use i32s instead",
               createI64ToI32LoweringPass);
  registerPass(
    "instrument-locals",
    "instrument the build with code to intercept all loads and stores",
    createInstrumentLocalsPass);
  registerPass(
    "instrument-memory",
    "instrument the build with code to intercept all loads and stores",
    createInstrumentMemoryPass);
  registerPass(
    "licm", "loop invariant code motion", createLoopInvariantCodeMotionPass);
  registerPass("limit-segments",
               "attempt to merge segments to fit within web limits",
               createLimitSegmentsPass);
  registerPass("memory64-lowering",
               "lower loads and stores to a 64-bit memory to instead use a "
               "32-bit one",
               createMemory64LoweringPass);
  registerPass("memory-packing",
               "packs memory into separate segments, skipping zeros",
               createMemoryPackingPass);
  registerPass(
    "merge-blocks", "merges blocks to their parents", createMergeBlocksPass);
  registerPass("merge-similar-functions",
               "merges similar functions when benefical",
               createMergeSimilarFunctionsPass);
  registerPass(
    "merge-locals", "merges locals when beneficial", createMergeLocalsPass);
  registerPass("metrics", "reports metrics", createMetricsPass);
  registerPass("minify-imports",
               "minifies import names (only those, and not export names), and "
               "emits a mapping to the minified ones",
               createMinifyImportsPass);
  registerPass("minify-imports-and-exports",
               "minifies both import and export names, and emits a mapping to "
               "the minified ones",
               createMinifyImportsAndExportsPass);
  registerPass("minify-imports-and-exports-and-modules",
               "minifies both import and export names, and emits a mapping to "
               "the minified ones, and minifies the modules as well",
               createMinifyImportsAndExportsAndModulesPass);
  registerPass("mod-asyncify-always-and-only-unwind",
               "apply the assumption that asyncify imports always unwind, "
               "and we never rewind",
               createModAsyncifyAlwaysOnlyUnwindPass);
  registerPass("mod-asyncify-never-unwind",
               "apply the assumption that asyncify never unwinds",
               createModAsyncifyNeverUnwindPass);
  registerPass("monomorphize",
               "creates specialized versions of functions",
               createMonomorphizePass);
  registerPass("monomorphize-always",
               "creates specialized versions of functions (even if unhelpful)",
               createMonomorphizeAlwaysPass);
  registerPass("multi-memory-lowering",
               "combines multiple memories into a single memory",
               createMultiMemoryLoweringPass);
  registerPass(
    "multi-memory-lowering-with-bounds-checks",
    "combines multiple memories into a single memory, trapping if the read or "
    "write is larger than the length of the memory's data",
    createMultiMemoryLoweringWithBoundsChecksPass);
  registerPass("nm", "name list", createNameListPass);
  registerPass("name-types", "(re)name all heap types", createNameTypesPass);
  registerPass("no-inline", "mark functions as no-inline", createNoInlinePass);
  registerPass("no-full-inline",
               "mark functions as no-inline (for full inlining only)",
               createNoFullInlinePass);
  registerPass("no-partial-inline",
               "mark functions as no-inline (for partial inlining only)",
               createNoPartialInlinePass);
  registerPass("once-reduction",
               "reduces calls to code that only runs once",
               createOnceReductionPass);
  registerPass("optimize-added-constants",
               "optimizes added constants into load/store offsets",
               createOptimizeAddedConstantsPass);
  registerPass("optimize-added-constants-propagate",
               "optimizes added constants into load/store offsets, propagating "
               "them across locals too",
               createOptimizeAddedConstantsPropagatePass);
  registerPass(
    "optimize-casts", "eliminate and reuse casts", createOptimizeCastsPass);
  registerPass("optimize-instructions",
               "optimizes instruction combinations",
               createOptimizeInstructionsPass);
  registerPass(
    "optimize-stack-ir", "optimize Stack IR", createOptimizeStackIRPass);
// Outlining currently relies on LLVM's SuffixTree, which we can't rely upon
// when building Binaryen for Emscripten.
#ifndef SKIP_OUTLINING
  registerPass("outlining", "outline instructions", createOutliningPass);
#endif
  registerPass("pick-load-signs",
               "pick load signs based on their uses",
               createPickLoadSignsPass);
  registerPass(
    "poppify", "Tranform Binaryen IR into Poppy IR", createPoppifyPass);
  registerPass("post-emscripten",
               "miscellaneous optimizations for Emscripten-generated code",
               createPostEmscriptenPass);
  registerPass("optimize-for-js",
               "early optimize of the instruction combinations for js",
               createOptimizeForJSPass);
  registerPass("precompute",
               "computes compile-time evaluatable expressions",
               createPrecomputePass);
  registerPass("precompute-propagate",
               "computes compile-time evaluatable expressions and propagates "
               "them through locals",
               createPrecomputePropagatePass);
  registerPass("print", "print in s-expression format", createPrinterPass);
  registerPass("print-minified",
               "print in minified s-expression format",
               createMinifiedPrinterPass);
  registerPass("print-features",
               "print options for enabled features",
               createPrintFeaturesPass);
  registerPass(
    "print-full", "print in full s-expression format", createFullPrinterPass);
  registerPass(
    "print-call-graph", "print call graph", createPrintCallGraphPass);

  // Register PrintFunctionMap using its normal name.
  registerPass("print-function-map",
               "print a map of function indexes to names",
               createPrintFunctionMapPass);
  // Also register it as "symbolmap" so that  wasm-opt --symbolmap=foo  is the
  // same as  wasm-as --symbolmap=foo  even though the latter is not a pass
  // (wasm-as cannot run arbitrary passes).
  // TODO: switch emscripten to this name, then remove the old one
  registerPass(
    "symbolmap", "(alias for print-function-map)", createPrintFunctionMapPass);

  registerPass("print-stack-ir",
               "print out Stack IR (useful for internal debugging)",
               createPrintStackIRPass);
  registerPass("propagate-globals-globally",
               "propagate global values to other globals (useful for tests)",
               createPropagateGlobalsGloballyPass);
  registerPass("remove-non-js-ops",
               "removes operations incompatible with js",
               createRemoveNonJSOpsPass);
  registerPass("remove-imports",
               "removes imports and replaces them with nops",
               createRemoveImportsPass);
  registerPass(
    "remove-memory", "removes memory segments", createRemoveMemoryPass);
  registerPass("remove-unused-brs",
               "removes breaks from locations that are not needed",
               createRemoveUnusedBrsPass);
  registerPass("remove-unused-module-elements",
               "removes unused module elements",
               createRemoveUnusedModuleElementsPass);
  registerPass("remove-unused-nonfunction-module-elements",
               "removes unused module elements that are not functions",
               createRemoveUnusedNonFunctionModuleElementsPass);
  registerPass("remove-unused-names",
               "removes names from locations that are never branched to",
               createRemoveUnusedNamesPass);
  registerPass("remove-unused-types",
               "remove unused private GC types",
               createRemoveUnusedTypesPass);
  registerPass("reorder-functions-by-name",
               "sorts functions by name (useful for debugging)",
               createReorderFunctionsByNamePass);
  registerPass("reorder-functions",
               "sorts functions by access frequency",
               createReorderFunctionsPass);
  registerPass("reorder-globals",
               "sorts globals by access frequency",
               createReorderGlobalsPass);
  registerTestPass("reorder-globals-always",
                   "sorts globals by access frequency (even if there are few)",
                   createReorderGlobalsAlwaysPass);
  registerPass("reorder-locals",
               "sorts locals by access frequency",
               createReorderLocalsPass);
  registerPass("rereloop",
               "re-optimize control flow using the relooper algorithm",
               createReReloopPass);
  registerPass(
    "rse", "remove redundant local.sets", createRedundantSetEliminationPass);
  registerPass("roundtrip",
               "write the module to binary, then read it",
               createRoundTripPass);
  registerPass("safe-heap",
               "instrument loads and stores to check for invalid behavior",
               createSafeHeapPass);
  registerPass("set-globals",
               "sets specified globals to specified values",
               createSetGlobalsPass);
  registerPass("separate-data-segments",
               "write data segments to a file and strip them from the module",
               createSeparateDataSegmentsPass);
  registerPass("signature-pruning",
               "remove params from function signature types where possible",
               createSignaturePruningPass);
  registerPass("signature-refining",
               "apply more specific subtypes to signature types where possible",
               createSignatureRefiningPass);
  registerPass("signext-lowering",
               "lower sign-ext operations to wasm mvp and disable the sign "
               "extension feature",
               createSignExtLoweringPass);
  registerPass("simplify-globals",
               "miscellaneous globals-related optimizations",
               createSimplifyGlobalsPass);
  registerPass("simplify-globals-optimizing",
               "miscellaneous globals-related optimizations, and optimizes "
               "where we replaced global.gets with constants",
               createSimplifyGlobalsOptimizingPass);
  registerPass("simplify-locals",
               "miscellaneous locals-related optimizations",
               createSimplifyLocalsPass);
  registerPass("simplify-locals-nonesting",
               "miscellaneous locals-related optimizations (no nesting at all; "
               "preserves flatness)",
               createSimplifyLocalsNoNestingPass);
  registerPass("simplify-locals-notee",
               "miscellaneous locals-related optimizations (no tees)",
               createSimplifyLocalsNoTeePass);
  registerPass("simplify-locals-nostructure",
               "miscellaneous locals-related optimizations (no structure)",
               createSimplifyLocalsNoStructurePass);
  registerPass(
    "simplify-locals-notee-nostructure",
    "miscellaneous locals-related optimizations (no tees or structure)",
    createSimplifyLocalsNoTeeNoStructurePass);
  registerPass("souperify", "emit Souper IR in text form", createSouperifyPass);
  registerPass("souperify-single-use",
               "emit Souper IR in text form (single-use nodes only)",
               createSouperifySingleUsePass);
  registerPass("spill-pointers",
               "spill pointers to the C stack (useful for Boehm-style GC)",
               createSpillPointersPass);
  registerPass("stub-unsupported-js",
               "stub out unsupported JS operations",
               createStubUnsupportedJSOpsPass);
  registerPass("ssa",
               "ssa-ify variables so that they have a single assignment",
               createSSAifyPass);
  registerPass(
    "ssa-nomerge",
    "ssa-ify variables so that they have a single assignment, ignoring merges",
    createSSAifyNoMergePass);
  registerPass("string-gathering",
               "gathers wasm strings to globals",
               createStringGatheringPass);
  registerPass("string-lowering",
               "lowers wasm strings and operations to imports",
               createStringLoweringPass);
  registerPass(
    "strip", "deprecated; same as strip-debug", createStripDebugPass);
  registerPass("stack-check",
               "enforce limits on llvm's __stack_pointer global",
               createStackCheckPass);
  registerPass("strip-debug",
               "strip debug info (including the names section)",
               createStripDebugPass);
  registerPass("strip-dwarf", "strip dwarf debug info", createStripDWARFPass);
  registerPass("strip-producers",
               "strip the wasm producers section",
               createStripProducersPass);
  registerPass("strip-eh", "strip EH instructions", createStripEHPass);
  registerPass("strip-target-features",
               "strip the wasm target features section",
               createStripTargetFeaturesPass);
  registerPass("translate-to-new-eh",
               "translate old EH instructions to new ones",
               createTranslateToNewEHPass);
  registerPass("trap-mode-clamp",
               "replace trapping operations with clamping semantics",
               createTrapModeClamp);
  registerPass("trap-mode-js",
               "replace trapping operations with js semantics",
               createTrapModeJS);
  registerPass("tuple-optimization",
               "optimize trivial tuples away",
               createTupleOptimizationPass);
  registerPass("type-finalizing",
               "mark all leaf types as final",
               createTypeFinalizingPass);
  registerPass("type-merging",
               "merge types to their supertypes where possible",
               createTypeMergingPass);
  registerPass("type-ssa",
               "create new nominal types to help other optimizations",
               createTypeSSAPass);
  registerPass("type-unfinalizing",
               "mark all types as non-final (open)",
               createTypeUnFinalizingPass);
  registerPass("unsubtyping",
               "removes unnecessary subtyping relationships",
               createUnsubtypingPass);
  registerPass("untee",
               "removes local.tees, replacing them with sets and gets",
               createUnteePass);
  registerPass("vacuum", "removes obviously unneeded code", createVacuumPass);
  // registerPass(
  //   "lower-i64", "lowers i64 into pairs of i32s", createLowerInt64Pass);

  // Register passes used for internal testing. These don't show up in --help.
  registerTestPass("catch-pop-fixup",
                   "fixup nested pops within catches",
                   createCatchPopFixupPass);
  registerTestPass("experimental-type-generalizing",
                   "generalize types (not yet sound)",
                   createTypeGeneralizingPass);
}

void PassRunner::addIfNoDWARFIssues(std::string passName) {
  auto pass = PassRegistry::get()->createPass(passName);
  if (!pass->invalidatesDWARF() || !shouldPreserveDWARF()) {
    doAdd(std::move(pass));
  }
}

void PassRunner::addDefaultOptimizationPasses() {
  addDefaultGlobalOptimizationPrePasses();
  addDefaultFunctionOptimizationPasses();
  addDefaultGlobalOptimizationPostPasses();
}

void PassRunner::addDefaultFunctionOptimizationPasses() {
  // All the additions here are optional if DWARF must be preserved. That is,
  // when DWARF is relevant we run fewer optimizations.
  // FIXME: support DWARF in all of them.

  // Untangling to semi-ssa form is helpful (but best to ignore merges
  // so as to not introduce new copies).
  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues("ssa-nomerge");
  }
  // if we are willing to work very very hard, flatten the IR and do opts
  // that depend on flat IR
  if (options.optimizeLevel >= 4) {
    addIfNoDWARFIssues("flatten");
    // LocalCSE is particularly useful after flatten (see comment in the pass
    // itself), but we must simplify locals a little first (as flatten adds many
    // new and redundant ones, which make things seem different if we do not
    // run some amount of simplify-locals first).
    addIfNoDWARFIssues("simplify-locals-notee-nostructure");
    addIfNoDWARFIssues("local-cse");
    // TODO: add rereloop etc. here
  }
  addIfNoDWARFIssues("dce");
  addIfNoDWARFIssues("remove-unused-names");
  addIfNoDWARFIssues("remove-unused-brs");
  addIfNoDWARFIssues("remove-unused-names");
  addIfNoDWARFIssues("optimize-instructions");
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("pick-load-signs");
  }
  // early propagation
  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("precompute-propagate");
  } else {
    addIfNoDWARFIssues("precompute");
  }
  if (options.lowMemoryUnused) {
    if (options.optimizeLevel >= 3 || options.shrinkLevel >= 1) {
      addIfNoDWARFIssues("optimize-added-constants-propagate");
    } else {
      addIfNoDWARFIssues("optimize-added-constants");
    }
  }
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("code-pushing");
  }
  if (wasm->features.hasMultivalue()) {
    // Optimize tuples before local opts (as splitting tuples can help local
    // opts), but also not too early, as we want to be after
    // optimize-instructions at least (which can remove tuple-related things).
    addIfNoDWARFIssues("tuple-optimization");
  }
  // don't create if/block return values yet, as coalesce can remove copies that
  // that could inhibit
  addIfNoDWARFIssues("simplify-locals-nostructure");
  addIfNoDWARFIssues("vacuum"); // previous pass creates garbage
  addIfNoDWARFIssues("reorder-locals");
  // simplify-locals opens opportunities for optimizations
  addIfNoDWARFIssues("remove-unused-brs");
  if (options.optimizeLevel > 1 && wasm->features.hasGC()) {
    addIfNoDWARFIssues("heap2local");
  }
  // if we are willing to work hard, also optimize copies before coalescing
  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("merge-locals"); // very slow on e.g. sqlite
  }
  if (options.optimizeLevel > 1 && wasm->features.hasGC()) {
    addIfNoDWARFIssues("optimize-casts");
    // Coalescing may prevent subtyping (as a coalesced local must have the
    // supertype of all those combined into it), so subtype first.
    // TODO: when optimizing for size, maybe the order should reverse?
    addIfNoDWARFIssues("local-subtyping");
  }
  addIfNoDWARFIssues("coalesce-locals");
  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues("local-cse");
  }
  addIfNoDWARFIssues("simplify-locals");
  addIfNoDWARFIssues("vacuum");
  addIfNoDWARFIssues("reorder-locals");
  addIfNoDWARFIssues("coalesce-locals");
  addIfNoDWARFIssues("reorder-locals");
  addIfNoDWARFIssues("vacuum");
  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues("code-folding");
  }
  addIfNoDWARFIssues("merge-blocks"); // makes remove-unused-brs more effective
  addIfNoDWARFIssues(
    "remove-unused-brs"); // coalesce-locals opens opportunities
  addIfNoDWARFIssues(
    "remove-unused-names");           // remove-unused-brs opens opportunities
  addIfNoDWARFIssues("merge-blocks"); // clean up remove-unused-brs new blocks
  // late propagation
  if (options.optimizeLevel >= 3 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("precompute-propagate");
  } else {
    addIfNoDWARFIssues("precompute");
  }
  addIfNoDWARFIssues("optimize-instructions");
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues(
      "rse"); // after all coalesce-locals, and before a final vacuum
  }
  addIfNoDWARFIssues("vacuum"); // just to be safe
}

void PassRunner::addDefaultGlobalOptimizationPrePasses() {
  addIfNoDWARFIssues("duplicate-function-elimination");
  addIfNoDWARFIssues("memory-packing");
  if (options.optimizeLevel >= 2) {
    addIfNoDWARFIssues("once-reduction");
  }
  if (wasm->features.hasGC() && options.optimizeLevel >= 2) {
    if (options.closedWorld) {
      addIfNoDWARFIssues("type-refining");
      addIfNoDWARFIssues("signature-pruning");
      addIfNoDWARFIssues("signature-refining");
    }
    addIfNoDWARFIssues("global-refining");
    // Global type optimization can remove fields that are not needed, which can
    // remove ref.funcs that were once assigned to vtables but are no longer
    // needed, which can allow more code to be removed globally. After those,
    // constant field propagation can be more effective.
    if (options.closedWorld) {
      addIfNoDWARFIssues("gto");
    }
    addIfNoDWARFIssues("remove-unused-module-elements");
    if (options.closedWorld) {
      addIfNoDWARFIssues("remove-unused-types");
      addIfNoDWARFIssues("cfp");
      addIfNoDWARFIssues("gsi");
      addIfNoDWARFIssues("abstract-type-refining");
    }
  }
  // TODO: generate-global-effects here, right before function passes, then
  //       discard in addDefaultGlobalOptimizationPostPasses? the benefit seems
  //       quite minor so far, except perhaps when using call.without.effects
  //       which can lead to more opportunities for global effects to matter.
}

void PassRunner::addDefaultGlobalOptimizationPostPasses() {
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues("dae-optimizing");
  }
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("inlining-optimizing");
  }

  // Optimizations show more functions as duplicate, so run this here in Post.
  addIfNoDWARFIssues("duplicate-function-elimination");
  addIfNoDWARFIssues("duplicate-import-elimination");

  // perform after the number of functions is reduced by inlining-optimizing
  if (options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("merge-similar-functions");
  }

  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) {
    addIfNoDWARFIssues("simplify-globals-optimizing");
  } else {
    addIfNoDWARFIssues("simplify-globals");
  }
  addIfNoDWARFIssues("remove-unused-module-elements");
  if (options.optimizeLevel >= 2 && wasm->features.hasStrings()) {
    // Gather strings to globals right before reorder-globals, which will then
    // sort them properly.
    addIfNoDWARFIssues("string-gathering");
  }
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues("reorder-globals");
  }
  // may allow more inlining/dae/etc., need --converge for that
  addIfNoDWARFIssues("directize");
  // perform Stack IR optimizations here, at the very end of the
  // optimization pipeline
  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
    addIfNoDWARFIssues("generate-stack-ir");
    addIfNoDWARFIssues("optimize-stack-ir");
  }
}

static void dumpWasm(Name name, Module* wasm) {
  static int counter = 0;
  std::string numstr = std::to_string(counter++);
  while (numstr.size() < 3) {
    numstr = '0' + numstr;
  }
  auto fullName = std::string("byn-");
#ifdef __linux__
  // TODO: use _getpid() on windows, elsewhere?
  fullName += std::to_string(getpid()) + '-';
#endif
  fullName += numstr + "-" + name.toString();
  Colors::setEnabled(false);
  ModuleWriter writer;
  writer.setDebugInfo(true);
  writer.writeBinary(*wasm, fullName + ".wasm");
}

void PassRunner::run() {
  static const int passDebug = getPassDebug();
  // Emit logging information when asked for. At passDebug level 1+ we log
  // the main passes, while in 2 we also log nested ones. Note that for
  // nested ones we can only emit their name - we can't validate, or save the
  // file, or print, as the wasm may be in an intermediate state that is not
  // valid.
  if (options.debug || (passDebug == 2 || (passDebug && !isNested))) {
    // for debug logging purposes, run each pass in full before running the
    // other
    auto totalTime = std::chrono::duration<double>(0);
    auto what = isNested ? "nested passes" : "passes";
    std::cerr << "[PassRunner] running " << what << std::endl;
    size_t padding = 0;
    for (auto& pass : passes) {
      padding = std::max(padding, pass->name.size());
    }
    if (passDebug >= 3 && !isNested) {
      dumpWasm("before", wasm);
    }
    for (auto& pass : passes) {
      // ignoring the time, save a printout of the module before, in case this
      // pass breaks it, so we can print the before and after
      std::stringstream moduleBefore;
      if (passDebug == 2 && !isNested) {
        moduleBefore << *wasm << '\n';
      }
      // prepare to run
      std::cerr << "[PassRunner]   running pass: " << pass->name << "... ";
      for (size_t i = 0; i < padding - pass->name.size(); i++) {
        std::cerr << ' ';
      }
      auto before = std::chrono::steady_clock::now();
      if (pass->isFunctionParallel()) {
        // function-parallel passes should get a new instance per function
        ModuleUtils::iterDefinedFunctions(
          *wasm, [&](Function* func) { runPassOnFunction(pass.get(), func); });
      } else {
        runPass(pass.get());
      }
      auto after = std::chrono::steady_clock::now();
      std::chrono::duration<double> diff = after - before;
      std::cerr << diff.count() << " seconds." << std::endl;
      totalTime += diff;
      if (options.validate && !isNested) {
        // validate, ignoring the time
        std::cerr << "[PassRunner]   (validating)\n";
        if (!WasmValidator().validate(*wasm, options)) {
          std::cout << *wasm << '\n';
          if (passDebug >= 2) {
            Fatal() << "Last pass (" << pass->name
                    << ") broke validation. Here is the module before: \n"
                    << moduleBefore.str() << "\n";
          } else {
            Fatal() << "Last pass (" << pass->name
                    << ") broke validation. Run with BINARYEN_PASS_DEBUG=2 "
                       "in the env to see the earlier state, or 3 to dump "
                       "byn-* files for each pass\n";
          }
        }
      }
      if (passDebug >= 3) {
        dumpWasm(pass->name, wasm);
      }
    }
    std::cerr << "[PassRunner] " << what << " took " << totalTime.count()
              << " seconds." << std::endl;
    if (options.validate && !isNested) {
      std::cerr << "[PassRunner] (final validation)\n";
      if (!WasmValidator().validate(*wasm, options)) {
        std::cout << *wasm << '\n';
        Fatal() << "final module does not validate\n";
      }
    }
  } else {
    // non-debug normal mode, run them in an optimal manner - for locality it is
    // better to run as many passes as possible on a single function before
    // moving to the next
    std::vector<Pass*> stack;
    auto flush = [&]() {
      if (stack.size() > 0) {
        // run the stack of passes on all the functions, in parallel
        size_t num = ThreadPool::get()->size();
        std::vector<std::function<ThreadWorkState()>> doWorkers;
        std::atomic<size_t> nextFunction;
        nextFunction.store(0);
        size_t numFunctions = wasm->functions.size();
        for (size_t i = 0; i < num; i++) {
          doWorkers.push_back([&]() {
            auto index = nextFunction.fetch_add(1);
            // get the next task, if there is one
            if (index >= numFunctions) {
              return ThreadWorkState::Finished; // nothing left
            }
            Function* func = this->wasm->functions[index].get();
            if (!func->imported()) {
              // do the current task: run all passes on this function
              for (auto* pass : stack) {
                runPassOnFunction(pass, func);
              }
            }
            if (index + 1 == numFunctions) {
              return ThreadWorkState::Finished; // we did the last one
            }
            return ThreadWorkState::More;
          });
        }
        ThreadPool::get()->work(doWorkers);
      }
      stack.clear();
    };
    for (auto& pass : passes) {
      if (pass->isFunctionParallel()) {
        stack.push_back(pass.get());
      } else {
        flush();
        runPass(pass.get());
      }
    }
    flush();
  }
}

void PassRunner::runOnFunction(Function* func) {
  if (options.debug) {
    std::cerr << "[PassRunner] running passes on function " << func->name
              << std::endl;
  }
  for (auto& pass : passes) {
    runPassOnFunction(pass.get(), func);
  }
}

void PassRunner::doAdd(std::unique_ptr<Pass> pass) {
  if (pass->invalidatesDWARF() && shouldPreserveDWARF()) {
    std::cerr << "warning: running pass '" << pass->name
              << "' which is not fully compatible with DWARF\n";
  }
  if (passRemovesDebugInfo(pass->name)) {
    addedPassesRemovedDWARF = true;
  }
  passes.emplace_back(std::move(pass));
}

void PassRunner::clear() { passes.clear(); }

// Checks that the state is valid before and after a
// pass runs on a function. We run these extra checks when
// pass-debug mode is enabled.
struct AfterEffectFunctionChecker {
  Function* func;
  Name name;

  // Check Stack IR state: if the main IR changes, there should be no
  // stack IR, as the stack IR would be wrong.
  bool beganWithStackIR;
  size_t originalFunctionHash;

  // In the creator we can scan the state of the module and function before the
  // pass runs.
  AfterEffectFunctionChecker(Function* func) : func(func), name(func->name) {
    beganWithStackIR = func->stackIR != nullptr;
    if (beganWithStackIR) {
      originalFunctionHash = FunctionHasher::hashFunction(func);
    }
  }

  // This is called after the pass is run, at which time we can check things.
  void check() {
    assert(func->name == name); // no global module changes should have occurred
    if (beganWithStackIR && func->stackIR) {
      auto after = FunctionHasher::hashFunction(func);
      if (after != originalFunctionHash) {
        Fatal() << "[PassRunner] PASS_DEBUG check failed: had Stack IR before "
                   "and after the pass ran, and the pass modified the main IR, "
                   "which invalidates Stack IR - pass should have been marked "
                   "'modifiesBinaryenIR'";
      }
    }
  }
};

// Runs checks on the entire module, in a non-function-parallel pass.
// In particular, in such a pass functions may be removed or renamed, track
// that.
struct AfterEffectModuleChecker {
  Module* module;

  std::vector<AfterEffectFunctionChecker> checkers;

  bool beganWithAnyStackIR;

  AfterEffectModuleChecker(Module* module) : module(module) {
    for (auto& func : module->functions) {
      checkers.emplace_back(func.get());
    }
    beganWithAnyStackIR = hasAnyStackIR();
  }

  void check() {
    if (beganWithAnyStackIR && hasAnyStackIR()) {
      // If anything changed to the functions, that's not good.
      if (checkers.size() != module->functions.size()) {
        error();
      }
      for (Index i = 0; i < checkers.size(); i++) {
        // Did a pointer change? (a deallocated function could cause that)
        if (module->functions[i].get() != checkers[i].func ||
            module->functions[i]->body != checkers[i].func->body) {
          error();
        }
        // Did a name change?
        if (module->functions[i]->name != checkers[i].name) {
          error();
        }
      }
      // Global function state appears to not have been changed: the same
      // functions are there. Look into their contents.
      for (auto& checker : checkers) {
        checker.check();
      }
    }
  }

  void error() {
    Fatal() << "[PassRunner] PASS_DEBUG check failed: had Stack IR before and "
               "after the pass ran, and the pass modified global function "
               "state - pass should have been marked 'modifiesBinaryenIR'";
  }

  bool hasAnyStackIR() {
    for (auto& func : module->functions) {
      if (func->stackIR) {
        return true;
      }
    }
    return false;
  }
};

void PassRunner::runPass(Pass* pass) {
  assert(!pass->isFunctionParallel());

  if (options.passesToSkip.count(pass->name)) {
    return;
  }

  std::unique_ptr<AfterEffectModuleChecker> checker;
  if (getPassDebug()) {
    checker = std::unique_ptr<AfterEffectModuleChecker>(
      new AfterEffectModuleChecker(wasm));
  }
  // Passes can only be run once and we deliberately do not clear the pass
  // runner after running the pass, so there must not already be a runner here.
  assert(!pass->getPassRunner());
  pass->setPassRunner(this);
  pass->run(wasm);
  handleAfterEffects(pass);
  if (getPassDebug()) {
    checker->check();
  }
}

void PassRunner::runPassOnFunction(Pass* pass, Function* func) {
  assert(pass->isFunctionParallel());

  if (options.passesToSkip.count(pass->name)) {
    return;
  }

  auto passDebug = getPassDebug();

  // Add extra validation logic in pass-debug mode 2. The main logic in
  // PassRunner::run will work at the module level, and here for a function-
  // parallel pass we can do the same at the function level: we can print the
  // function before the pass, run the pass on the function, and then if it
  // fails to validate we can show an error and print the state right before the
  // pass broke it.
  //
  // Skip nameless passes for this. Anything without a name is an internal
  // component of some larger pass, and information about it won't be very
  // useful - leave it to the entire module to fail validation in that case.
  bool extraFunctionValidation =
    passDebug == 2 && options.validate && !pass->name.empty();
  std::stringstream bodyBefore;
  if (extraFunctionValidation) {
    bodyBefore << *func->body << '\n';
  }

  std::unique_ptr<AfterEffectFunctionChecker> checker;
  if (passDebug) {
    checker = std::make_unique<AfterEffectFunctionChecker>(func);
  }

  // Function-parallel passes get a new instance per function
  auto instance = pass->create();
  instance->setPassRunner(this);
  instance->runOnFunction(wasm, func);
  handleAfterEffects(pass, func);

  if (passDebug) {
    checker->check();
  }

  if (extraFunctionValidation) {
    if (!WasmValidator().validate(func, *wasm, WasmValidator::Minimal)) {
      Fatal() << "Last nested function-parallel pass (" << pass->name
              << ") broke validation of function " << func->name
              << ". Here is the function body before:\n"
              << bodyBefore.str() << "\n\nAnd here it is now:\n"
              << *func->body << '\n';
    }
  }
}

void PassRunner::handleAfterEffects(Pass* pass, Function* func) {
  if (!pass->modifiesBinaryenIR()) {
    return;
  }

  // Binaryen IR is modified, so we may have work here.

  if (!func) {
    // If no function is provided, then this is not a function-parallel pass,
    // and it may have operated on any of the functions in theory, so run on
    // them all.
    assert(!pass->isFunctionParallel());
    for (auto& func : wasm->functions) {
      handleAfterEffects(pass, func.get());
    }
    return;
  }

  // If Binaryen IR is modified, Stack IR must be cleared - it would
  // be out of sync in a potentially dangerous way.
  func->stackIR.reset(nullptr);

  if (pass->requiresNonNullableLocalFixups()) {
    TypeUpdating::handleNonDefaultableLocals(func, *wasm);
  }

  if (options.funcEffectsMap && pass->addsEffects()) {
    // Effects were added, so discard any computed effects for this function.
    options.funcEffectsMap->erase(func->name);
  }
}

int PassRunner::getPassDebug() {
  static const int passDebug =
    getenv("BINARYEN_PASS_DEBUG") ? atoi(getenv("BINARYEN_PASS_DEBUG")) : 0;
  return passDebug;
}

bool PassRunner::passRemovesDebugInfo(const std::string& name) {
  return name == "strip" || name == "strip-debug" || name == "strip-dwarf";
}

bool PassRunner::shouldPreserveDWARF() {
  // Check if the debugging subsystem wants to preserve DWARF.
  if (!Debug::shouldPreserveDWARF(options, *wasm)) {
    return false;
  }

  // We may need DWARF. Check if one of our previous passes would remove it
  // anyhow, in which case, there is nothing to preserve.
  if (addedPassesRemovedDWARF) {
    return false;
  }

  return true;
}

} // namespace wasm