while (true) {

if (auto super = type.getDeclaredSuperType()) {

type = *super;

continue;

}

break;

}

return type;

// Analysis results. For each parameter, whether it is used.

Params paramUsages;

// Analysis result for the function result. It will remain bot if there is no

// result.

Used::Element resultUsage;

// Map direct callee function names to the source locations forwarded to their

// parameters.

std::unordered_map<Name, ParamLocations> forwardedToDirectParams;

// Map the root supertypes of indirect callee types to the source locations

// forwarded to their parameters.

std::unordered_map<HeapType, ParamLocations> forwardedToIndirectParams;

// Locations forwarded to this function's result. These locations will become

// used if the result turns out ot be used.

std::vector<Location> resultSources;

// For each parameter of this function, the list of locations that will become

// used if the parameter turns out to be used. Computed by reversing the

// forwardedToDirectParams graph.

ParamLocations paramSources;

// Locations used in an observable way by the code in this function.

// Propagation of usage will begin at these locations.

// TODO: Experiment with making this a set.

std::vector<Location> usedLocations;

// The gets that may read from parameters. These are the gets that might be

// optimized out if their results are unused or forwarded to another function

// where they will be unused.

std::unordered_set<LocalGet*> paramGets;

// We do not yet analyze parameter or result usage in stack switching

// instructions. Collect the used continuation types so we can be sure not to

// modify their associated function types.

// TODO: Analyze stack switching.

std::unordered_set<HeapType> contTypes;

// Whether we need to additionally propagate param usage to and result usage

// from indirect callers of this function's type. Atomic because it can be set

// when visiting other functions in parallel.

std::atomic<bool> referenced = false;

// We cannot yet fully analyze and optimize call.without.effects, which would

// require creating new imports for new signatures, etc. Functions that are

// called via these intrinsics will not be optimized.

// TODO: Fix this.

std::atomic<bool> usedInIntrinsic = false;

// Unreferenced functions can be optimized separately from referenced

// functions with the same type. For unreferenced functions in that situation,

// this is the new type that should be applied before global type rewriting to

// prevent the function from getting the wrong optimizations.

std::optional<HeapType> replacementType;

// Functions that this function directly tail-calls.

std::vector<Index> tailCallees;

// Root function types that this function indirectly tail-calls.

std::vector<HeapType> tailCalleeTypes;

// For each parameter in the type, whether it is used.

Params paramUsages;

// Analysis result for the function result.

Used::Element resultUsage;

// The list of referenced functions with types in this tree. When a parameter

// in this type tree is used, the parameter becomes used in these functions

// and vice versa.

std::vector<Index> referencedFuncs;

// For each parameter in this root function type, the list of locations that

// become used when the parameter in this root function type becomes used.

// Computed by reversing indirectForwardedParams from the function infos for

// functions with this root type.

ParamLocations paramSources;

// Tail-callers of this type tree. If this type tree's result is used,

// these callers' results must also be used. Normally, result usage only

// flows from types to their referenced functions, but tail calls require

// this reverse constraint.

std::vector<Location> resultSources;

RootFuncTypeInfo(Used& used, HeapType type)

: paramUsages(type.getSignature().params.size(), used.getBottom()),

resultUsage(used.getBottom()),

paramSources(type.getSignature().params.size()) {}

// Analysis lattice.

Used used;

Module* wasm = nullptr;

// Map function name to index.

std::unordered_map<Name, Index> funcIndices;

// Intermediate and final analysis results by function index.

std::vector<FunctionInfo> funcInfos;

// Intermediate and final analysis results for each function type tree, keyed

// by root type in the tree.

std::unordered_map<HeapType, RootFuncTypeInfo> typeTreeInfos;

RootFuncTypeInfo& getTypeTreeInfo(HeapType rootType) {

return typeTreeInfos.try_emplace(rootType, used, rootType).first->second;

}

// In general referenced functions may escape and be called externally in an

// open world, so we require a closed world to optimize referenced functions.

// Further, without GC we cannot differentiate the types of unreferenced and

// referenced functions before global type rewriting, so we cannot optimize

// them separately. Do not constrain the optimization of unreferenced

// functions by optimizing referenced functions in that case.

// TODO: Find a way to optimize referenced functions without GC enabled as

// long as traps never happen so call_indirect cannot distinguish separate

// types.

bool optimizeReferencedFuncs = false;

// Cache the public heap types to avoid gathering them more than once.

std::vector<HeapType> publicHeapTypes;

void run(Module* wasm) override {

this->wasm = wasm;

for (auto& func : wasm->functions) {

funcIndices.insert({func->name, funcIndices.size()});

}

optimizeReferencedFuncs =

getPassOptions().worldMode == WorldMode::Closed && wasm->features.hasGC();

TIME(Timer timer);

analyzeModule();

TIME(std::cerr << "analysis: " << timer.lastElapsed() << "\n");

prepareReverseGraph();

TIME(std::cerr << "prepare: " << timer.lastElapsed() << "\n");

computeFixedPoint();

TIME(std::cerr << "fixed point: " << timer.lastElapsed() << "\n");

#if DAE_STATS

collectStats();

TIME(std::cerr << "stats: " << timer.lastElapsed() << "\n");

#endif // DAE_STATS

optimize();

TIME(auto [last, total] = timer.elapsed());

TIME(std::cerr << "optimize: " << last << "\n");

TIME(std::cerr << "total: " << total << "\n");

}

void analyzeModule();

void prepareReverseGraph();

void computeFixedPoint();

void optimize();

template<typename F> void forEachSuccessor(Location loc, F&& f);

#if DAE_STATS

void collectStats();

#endif // DAE_STATS

void makeUnreferencedFunctionTypes(const std::vector<HeapType>& oldTypes,

const TypeMap& newTypes);

void markParamsUsed(Index funcIndex) {

auto& usages = funcInfos[funcIndex].paramUsages;

std::fill(usages.begin(), usages.end(), used.getTop());

}

void markParamsUsed(Name func) { markParamsUsed(funcIndices.at(func)); }

void markParamsUsed(HeapType rootType) {

auto& usages = getTypeTreeInfo(rootType).paramUsages;

std::fill(usages.begin(), usages.end(), used.getTop());

}

void markResultsUsed(Index funcIndex) {

funcInfos[funcIndex].resultUsage = used.getTop();

}

void markResultsUsed(Name func) { markResultsUsed(funcIndices.at(func)); }

void markResultsUsed(HeapType rootType) {

getTypeTreeInfo(rootType).resultUsage = used.getTop();

}

Used::Element& elem(Location loc) {

if (auto* l = std::get_if<FuncParamLoc>(&loc)) {

return funcInfos[l->first].paramUsages[l->second];

}

if (auto* l = std::get_if<FuncResultLoc>(&loc)) {

return funcInfos[*l].resultUsage;

}

if (auto* l = std::get_if<TypeParamLoc>(&loc)) {

assert(l->first == getRootType(l->first));

return getTypeTreeInfo(l->first).paramUsages[l->second];

}

if (auto* l = std::get_if<TypeResultLoc>(&loc)) {

assert(*l == getRootType(*l));

return getTypeTreeInfo(*l).resultUsage;

}

WASM_UNREACHABLE("unexpected location");

}

bool isFunctionParallel() override { return true; }

bool modifiesBinaryenIR() override { return false; }

// Analysis lattice.

const Used& used;

// The function info graph is stored as vectors accessed by function index.

// Map function names to their indices.

const std::unordered_map<Name, Index>& funcIndices;

// Vector of analysis info representing the analysis graph we are building.

// This is populated safely in parallel because the visitor for each function

// only modifies the entry for that function.

std::vector<FunctionInfo>& funcInfos;

// The index of the function we are currently walking.

Index index = -1;

// A use of a parameter local does not necessarily imply the use of the

// parameter value. We use a local graph to check where parameter values may

// be used.

std::optional<LazyLocalGraph> localGraph;

bool optimizeReferencedFuncs;

GraphBuilder(const Used& used,

const std::unordered_map<Name, Index>& funcIndices,

std::vector<FunctionInfo>& funcInfos,

bool optimizeReferencedFuncs)

: used(used), funcIndices(funcIndices), funcInfos(funcInfos),

optimizeReferencedFuncs(optimizeReferencedFuncs) {}

std::unique_ptr<Pass> create() override {

return std::make_unique<GraphBuilder>(

used, funcIndices, funcInfos, optimizeReferencedFuncs);

}

void runOnFunction(Module* wasm, Function* func) override {

assert(index == Index(-1));

index = funcIndices.at(func->name);

localGraph.emplace(func);

WalkerPass<ExpressionStackWalker<GraphBuilder>>::runOnFunction(wasm, func);

}

void visitRefFunc(RefFunc* curr) {

funcInfos[funcIndices.at(curr->func)].referenced = true;

}

void noteContinuation(Type type) {

if (type.isContinuation()) {

funcInfos[index].contTypes.insert(type.getHeapType());

}

}

void visitResumeHandlers(const ArenaVector<Name>& labels) {

for (Index i = 0; i < labels.size(); ++i) {

if (labels[i]) {

auto* target = findBreakTarget(labels[i]);

assert(target->type.size() >= 1);

auto newContType = target->type[target->type.size() - 1];

assert(newContType.isContinuation());

noteContinuation(newContType);

}

}

}

void visitResume(Resume* curr) {

noteContinuation(curr->cont->type);

visitResumeHandlers(curr->handlerBlocks);

}

void visitResumeThrow(ResumeThrow* curr) {

noteContinuation(curr->cont->type);

visitResumeHandlers(curr->handlerBlocks);

}

void visitStackSwitch(StackSwitch* curr) {

noteContinuation(curr->cont->type);

// Do not optimize the return continuation either because that would

// require us to update the type of the switch expression.

if (curr->cont->type.isContinuation()) {

auto retParams = curr->cont->type.getHeapType()

.getContinuation()

.type.getSignature()

.params;

noteContinuation(retParams[retParams.size() - 1]);

}

}

void visitContBind(ContBind* curr) {

noteContinuation(curr->cont->type);

noteContinuation(curr->type);

}

Index getArgIndex(const ExpressionList& operands, Expression* arg) {

for (Index i = 0; i < operands.size(); ++i) {

if (operands[i] == arg) {

return i;

}

}

WASM_UNREACHABLE("expected arg");

}

void forwardToDirectParam(Location source,

const ExpressionList& operands,

Expression* arg,

Name target) {

auto argIndex = getArgIndex(operands, arg);

auto& forwarded = funcInfos[index].forwardedToDirectParams[target];

if (forwarded.empty()) {

forwarded.resize(operands.size());

}

forwarded[argIndex].push_back(source);

}

void forwardToIndirectParam(Location source,

const ExpressionList& operands,

Expression* arg,

HeapType type) {

auto rootType = getRootType(type);

auto argIndex = getArgIndex(operands, arg);

auto& forwarded = funcInfos[index].forwardedToIndirectParams[rootType];

if (forwarded.empty()) {

forwarded.resize(operands.size());

}

forwarded[argIndex].push_back(source);

}

void forwardToResult(Location source) {

funcInfos[index].resultSources.push_back(source);

}

// Record the fact that `curr`'s result comes from `source`.

void getValueFromLocation(Expression* curr, Location source) {

// Look at the transitive users of this value (i.e. its parent and further

// ancestors) to see if it flows (possibly with transformations) into

// another location, `dest`. If it is, we say that `src` is "forwarded" to

// `dest`. We will create an edge in the analysis graph so that if `dest` is

// used, then `src` will be marked as used as well. We must make sure the

// current function doesn't first use `src` in other ways, though, for

// example by teeing it to a local or by performing a branching or trapping

// cast on it. As a conservative approximation, consider the `src` used if

// any of the expressions between `curr` and `dest` have non-removable side

// effects (even if those side effects do not depend on the value flowing

// from `curr`).

if (curr == getFunction()->body) {

// No parents to look at, but the result is forwarded to the function

// result.

forwardToResult(source);

return;

}

for (Index i = expressionStack.size() - 1; i > 0; --i) {

auto* expr = expressionStack[i];

auto* parent = expressionStack[i - 1];

// TODO: Experiment with caching the location (or lack of location, or

// use) reached from parent expressions so we can avoid traversing the

// same parents more than once.

if (auto* call = parent->dynCast<Call>()) {

forwardToDirectParam(source, call->operands, expr, call->target);

return;

}

if (auto* call = parent->dynCast<CallIndirect>();

call && expr != call->target && optimizeReferencedFuncs) {

forwardToIndirectParam(source, call->operands, expr, call->heapType);

return;

}

if (auto* call = parent->dynCast<CallRef>();

call && expr != call->target && optimizeReferencedFuncs) {

if (!call->target->type.isSignature()) {

// The call will never happen, so we don't need to consider it.

return;

}

auto heapType = call->target->type.getHeapType();

forwardToIndirectParam(source, call->operands, expr, heapType);

return;

}

if (parent->is<Return>()) {

forwardToResult(source);

return;

}

// TODO: Handle unconditional branches to blocks that fall through to the

// end of the function as well? Handle all unconditional branches to

// blocks in general?

// If the value flows into an If condition, we must consider it used

// because removing it may visibly change which arm of the If gets

// executed. This is not captured by the effects analysis below.

if (auto* iff = parent->dynCast<If>(); iff && expr == iff->condition) {

break;

}

// TODO: Skip the effects analysis below when we are flowing out of a

// block. Side effects earlier in the block don't matter.

// If the current parent expression has unremovable side effects, we

// conservatively treat the value as used.

EffectAnalyzer effects(getPassOptions(), *getModule());

effects.visit(parent);

if (effects.hasUnremovableSideEffects()) {

// Conservatively assume this expression uses the value in some way that

// prevents us from removing it.

break;

}

if (!parent->type.isConcrete()) {

// The value flows no further, so it is not used in an observable way.

return;

}

// If the value flows out of the function body, it is forwarded to this

// function's results.

if (parent == getFunction()->body) {

forwardToResult(source);

return;

}

}

// The value is used by something we aren't analyzing.

if (auto* l = std::get_if<FuncParamLoc>(&source)) {

// Parameter uses are local to the function and can be updated in

// parallel.

funcInfos[index].paramUsages[l->second] = used.getTop();

} else {

// Other locations will have to be handled later.

funcInfos[index].usedLocations.push_back(source);

}

}

void visitLocalGet(LocalGet* curr) {

if (!getFunction()->isParam(curr->index)) {

return;

}

// A use of a parameter local does not necessarily imply the use of the

// parameter value. Check where the parameter value may be used.

const auto& sets = localGraph->getSets(curr);

bool usesParam = std::any_of(

sets.begin(), sets.end(), [](LocalSet* set) { return set == nullptr; });

if (!usesParam) {

// The original parameter value does not reach here.

return;

}

funcInfos[index].paramGets.insert(curr);

getValueFromLocation(curr, FuncParamLoc{index, curr->index});

}

void visitCall(Call* curr) {

if (Intrinsics(*getModule()).isCallWithoutEffects(curr)) {

auto target = curr->operands.back()->cast<RefFunc>()->func;

funcInfos[funcIndices.at(target)].usedInIntrinsic = true;

}

auto* callee = getModule()->getFunction(curr->target);

if (callee->getResults().isConcrete()) {

Location source = FuncResultLoc{funcIndices.at(curr->target)};

if (curr->isReturn) {

forwardToResult(source);

funcInfos[index].tailCallees.push_back(funcIndices.at(curr->target));

} else {

getValueFromLocation(curr, source);

}

}

}

void handleIndirectCall(Expression* curr, HeapType type, bool isReturn) {

auto sig = type.getSignature();

if (sig.results.isConcrete()) {

HeapType rootType = getRootType(type);

Location source = TypeResultLoc{rootType};

if (isReturn) {

forwardToResult(source);

funcInfos[index].tailCalleeTypes.push_back(rootType);

} else if (optimizeReferencedFuncs) {

getValueFromLocation(curr, source);

}

}

}

void visitCallIndirect(CallIndirect* curr) {

handleIndirectCall(curr, curr->heapType, curr->isReturn);

}

void visitCallRef(CallRef* curr) {

auto targetType = curr->target->type;

if (targetType.isSignature()) {

handleIndirectCall(curr, targetType.getHeapType(), curr->isReturn);

}

}

// Initialize the function infos. (The type infos are initialized

// on-demand instead.)

funcInfos = std::vector<FunctionInfo>(wasm->functions.size());

for (Index i = 0; i < funcInfos.size(); ++i) {

auto numParams = wasm->functions[i]->getNumParams();

funcInfos[i].paramUsages.resize(numParams, used.getBottom());

funcInfos[i].resultUsage = used.getBottom();

funcInfos[i].paramSources.resize(numParams);

}

// Analyze functions to find forwarded and used parameters as well as

// function references and other relevant information.

GraphBuilder builder(used, funcIndices, funcInfos, optimizeReferencedFuncs);

builder.run(getPassRunner(), wasm);

// Find additional function references at the module level.

builder.walkModuleCode(wasm);

// Update the locations for which we observed direct usage.

for (Index i = 0; i < wasm->functions.size(); ++i) {

auto& info = funcInfos[i];

for (auto loc : info.usedLocations) {

if (auto* l = std::get_if<FuncResultLoc>(&loc)) {

markResultsUsed(*l);

} else if (auto* l = std::get_if<TypeResultLoc>(&loc)) {

markResultsUsed(*l);

} else {

// Function parameter uses were already handled in parallel. It is

// impossible to directly use a type parameter since they are used only

// transitively through function parameters.

WASM_UNREACHABLE("unexpected location");

}

}

}

// Model imported and exported functions as referenced so that marking the

// parameters or results of their types as used will prevent optimizations of

// the functions themselves.

for (Index i = 0; i < wasm->functions.size(); ++i) {

if (wasm->functions[i]->imported()) {

funcInfos[i].referenced = true;

}

}

for (auto& export_ : wasm->exports) {

if (export_->kind == ExternalKind::Function) {

auto i = funcIndices.at(*export_->getInternalName());

funcInfos[i].referenced = true;

}

}

// Functions called with call.without.effects cannot yet be optimized. Mark

// their parameters and results as used.

for (Index i = 0; i < wasm->functions.size(); ++i) {

if (funcInfos[i].usedInIntrinsic) {

markParamsUsed(i);

markResultsUsed(i);

}

}

// JS-called functions will be called externally, so we cannot optimize out

// their parameters or results.

// TODO: Consider optimizing out a suffix of their parameters.

for (auto name : Intrinsics(*wasm).getJSCalledFunctions()) {

markParamsUsed(name);

markResultsUsed(name);

}

// If we're not optimizing referenced functions, mark all their parameters

// and results as used.

if (!optimizeReferencedFuncs) {

for (Index i = 0; i < wasm->functions.size(); ++i) {

if (funcInfos[i].referenced) {

markParamsUsed(i);

markResultsUsed(i);

}

}

}

// Additionally mark parameters of referenced functions with public types (or

// private subtypes of public types) as used because we cannot rewrite their

// types. Similarly, we do not rewrite tag types or function types used in

// continuations, so any referenced function whose type is in the same tree as

// a tag type or continuation function type will have its parameters marked as

// used.

//

// TODO: Consider analyzing whether we can rewrite the types of such

// referenced functions to new private types first. This would require

// analyzing whether they can escape the module.

//

// TODO: Analyze tags and remove their unused parameters.

std::unordered_set<HeapType> unrewritableRoots;

publicHeapTypes =

ModuleUtils::getPublicHeapTypes(*wasm, getPassOptions().worldMode);

for (auto type : publicHeapTypes) {

if (type.isSignature()) {

unrewritableRoots.insert(getRootType(type));

}

}

for (auto& tag : wasm->tags) {

unrewritableRoots.insert(getRootType(tag->type));

}

for (Index i = 0; i < wasm->functions.size(); ++i) {

for (auto type : funcInfos[i].contTypes) {

unrewritableRoots.insert(getRootType(type.getContinuation().type));

}

}

// The types of the call.without.effects imports are excluded from the set of

// public heap types, but until we can handle analyzing and updating them in

// this pass, we must treat them the same as any other imported function

// types.

for (auto& func : wasm->functions) {

if (Intrinsics(*wasm).isCallWithoutEffects(func.get())) {

unrewritableRoots.insert(getRootType(func->type.getHeapType()));

}

}

for (auto root : unrewritableRoots) {

markParamsUsed(root);

markResultsUsed(root);

}

// Compute the reverse graph used by the fixed point analysis from the

// forward graph we have built.

// Collect the referenced functions for each type tree.

for (Index i = 0; i < funcInfos.size(); ++i) {

funcInfos[i].paramSources.resize(funcInfos[i].paramUsages.size());

if (funcInfos[i].referenced) {

auto root = getRootType(wasm->functions[i]->type.getHeapType());

getTypeTreeInfo(root).referencedFuncs.push_back(i);

}

}

for (Index callerIndex = 0; callerIndex < funcInfos.size(); ++callerIndex) {

auto& callerInfo = funcInfos[callerIndex];

// Collect the source locations for direct callees.

for (auto& [callee, forwardedParams] : callerInfo.forwardedToDirectParams) {

auto& calleeInfo = funcInfos[funcIndices.at(callee)];

for (Index destParam = 0; destParam < forwardedParams.size();

++destParam) {

for (auto sourceLoc : forwardedParams[destParam]) {

calleeInfo.paramSources[destParam].push_back(sourceLoc);

}

}

}

// Collect the source locations for indirect callees.

for (auto& [calleeRootType, forwardedParams] :

callerInfo.forwardedToIndirectParams) {

assert(getRootType(calleeRootType) == calleeRootType);

auto& typeTreeInfo = getTypeTreeInfo(calleeRootType);

for (Index destParam = 0; destParam < forwardedParams.size();

++destParam) {

for (auto sourceLoc : forwardedParams[destParam]) {

typeTreeInfo.paramSources[destParam].push_back(sourceLoc);

}

}

}

// Collect the tail callers of each callee function and type tree.

Location callerResult = FuncResultLoc{callerIndex};

for (auto calleeIndex : callerInfo.tailCallees) {

funcInfos[calleeIndex].resultSources.push_back(callerResult);

}

for (auto calleeRootType : callerInfo.tailCalleeTypes) {

getTypeTreeInfo(calleeRootType).resultSources.push_back(callerResult);

}

}

if (auto* l = std::get_if<TypeParamLoc>(&loc)) {

auto [rootType, paramIndex] = *l;

auto& typeTreeInfo = getTypeTreeInfo(rootType);

// Propagate usage back to locations forwarded from indirect callers.

for (auto source : typeTreeInfo.paramSources[paramIndex]) {

f(source);

}

// Propagate usage to referenced functions with types in the same type tree

// to ensure their types can all be updated uniformly.

for (auto funcIndex : typeTreeInfo.referencedFuncs) {

f(FuncParamLoc{funcIndex, paramIndex});

}

} else if (auto* l = std::get_if<TypeResultLoc>(&loc)) {

auto& typeTreeInfo = getTypeTreeInfo(*l);

// Propagate usage to referenced functions with types in the same type tree

// to ensure their types can all be updated uniformly.

for (auto funcIndex : typeTreeInfo.referencedFuncs) {

f(FuncResultLoc{funcIndex});

}

// Propagate to tail callers.

for (auto source : typeTreeInfo.resultSources) {

f(source);

}

} else if (auto* l = std::get_if<FuncParamLoc>(&loc)) {

auto [calleeIndex, calleeParamIndex] = *l;

auto& calleeInfo = funcInfos[calleeIndex];

// Propagate usage back to locations forwarded from direct callers.

for (auto source : calleeInfo.paramSources[calleeParamIndex]) {

f(source);

}

if (calleeInfo.referenced) {

// Propagate the use to the function type. It will be propagated from

// there to indirect callers and other functions of this type.

auto calleeType = wasm->functions[calleeIndex]->type.getHeapType();

f(TypeParamLoc{getRootType(calleeType), calleeParamIndex});

}

} else if (auto* l = std::get_if<FuncResultLoc>(&loc)) {

auto calleeIndex = *l;

auto& calleeInfo = funcInfos[calleeIndex];

// Propagate usage back to sources of this result, including tail callers.

for (auto source : calleeInfo.resultSources) {

f(source);

}

if (calleeInfo.referenced) {

// Propagate the use to the function type. It will be propagated from

// there to other functions of this type.

auto calleeType = wasm->functions[calleeIndex]->type.getHeapType();

f(TypeResultLoc{getRootType(calleeType)});

}

} else {

WASM_UNREACHABLE("unexpected location");

}

// List of destination locations (i.e. params and results, either of functions

// or root function types) from which we may need to propagate usage

// information. Initialized with all locations we have observed to be used in

// the IR.

// TODO: Consider propagating by connected components instead.

std::vector<Location> work;

for (Index i = 0; i < funcInfos.size(); ++i) {

for (Index j = 0; j < funcInfos[i].paramUsages.size(); ++j) {

if (funcInfos[i].paramUsages[j]) {

work.push_back(FuncParamLoc{i, j});

}

}

if (funcInfos[i].resultUsage) {

work.push_back(FuncResultLoc{i});

}

}

for (auto& [rootType, info] : typeTreeInfos) {

for (Index i = 0; i < info.paramUsages.size(); ++i) {

if (info.paramUsages[i]) {

work.push_back(TypeParamLoc{rootType, i});

}

}

if (info.resultUsage) {

work.push_back(TypeResultLoc{rootType});

}

}

while (!work.empty()) {

auto loc = work.back();

work.pop_back();

auto& e = elem(loc);

assert(e && "unexpected unused location");

forEachSuccessor(loc, [&](Location succ) {

if (used.join(elem(succ), e)) {

work.push_back(succ);

}

});

}

DAE2& parent;

DAETypeUpdater(DAE2& parent)

: GlobalTypeRewriter(*parent.wasm, parent.getPassOptions().worldMode),

parent(parent) {}

void modifySignature(HeapType oldType, Signature& sig) override {

// All signature types in a type tree will have the same parameters removed

// to keep subtyping valid. Look up which parameters to keep by the root

// type in the tree.

auto& info = parent.getTypeTreeInfo(getRootType(oldType));

auto& usages = info.paramUsages;

bool hasRemoved = std::any_of(

usages.begin(), usages.end(), [&](auto& use) { return !use; });

if (hasRemoved) {

std::vector<Type> keptParams;

keptParams.reserve(usages.size());

for (Index i = 0; i < usages.size(); ++i) {

if (usages[i]) {

keptParams.push_back(sig.params[i]);

}

}

sig.params = getTempTupleType(std::move(keptParams));

}

if (!info.resultUsage) {

sig.results = Type::none;

}

}

// Return the sorted list of old types (used for deterministic ordering) and

// the unordered map from old to new types.

std::pair<std::vector<HeapType>, TypeMap> rebuildTypes() {

auto types = getSortedTypes(getPrivatePredecessors());

auto map = GlobalTypeRewriter::rebuildTypes(types);

return {std::move(types), std::move(map)};

}

: public WalkerPass<

ExpressionStackWalker<Optimizer, UnifiedExpressionVisitor<Optimizer>>> {

using Super = WalkerPass<

ExpressionStackWalker<Optimizer, UnifiedExpressionVisitor<Optimizer>>>;

bool isFunctionParallel() override { return true; }

// We handle non-nullable local fixups in the pass itself. If we ran the

// fixups after the pass, they could get confused and produce invalid code

// because this pass updates local indices but does not always update function

// types to match. Function types are updated after this pass runs.

bool requiresNonNullableLocalFixups() override { return false; }

const DAE2& parent;

// The info for the function we are running on.

const FunctionInfo* funcInfo = nullptr;

// Map old local indices to new local indices for the function we are

// currently optimizing. Kept parameters and locals may need to have their

// indices shifted down to account for removed parameters, and removed

// parameters will need to be mapped to their new replacement locals.

std::vector<Index> newIndices;