bool isFunctionParallel() override { return true; }

// SSAify maps each original local to a number of new ones.

// FIXME DWARF updating does not handle local changes yet.

bool invalidatesDWARF() override { return true; }

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

return std::make_unique<SSAify>(allowMerges);

}

SSAify(bool allowMerges) : allowMerges(allowMerges) {}

bool allowMerges;

Module* module;

Function* func;

// things we add to the function prologue

std::vector<Expression*> functionPrepends;

bool refinalize = false;

void runOnFunction(Module* module_, Function* func_) override {

module = module_;

func = func_;

LocalGraph graph(func, module);

graph.computeSetInfluences();

graph.computeSSAIndexes();

// create new local indexes, one for each set

createNewIndexes(graph);

// we now know the sets for each get, and can compute get indexes and handle

// phis

computeGetsAndPhis(graph);

// add prepends to function

addPrepends();

if (refinalize) {

ReFinalize().walkFunctionInModule(func, module);

}

}

void createNewIndexes(LocalGraph& graph) {

FindAll<LocalSet> sets(func->body);

for (auto* set : sets.list) {

// Indexes already in SSA form do not need to be modified - there is

// already just one set for that index. Otherwise, use a new index, unless

// merges are disallowed.

if (!graph.isSSA(set->index) && (allowMerges || !hasMerges(set, graph))) {

set->index = addLocal(func->getLocalType(set->index));

}

}

}

bool hasMerges(LocalSet* set, LocalGraph& graph) {

for (auto* get : graph.getSetInfluences(set)) {

if (graph.getSets(get).size() > 1) {

return true;

}

}

return false;

}

void computeGetsAndPhis(LocalGraph& graph) {

FindAll<LocalGet> gets(func->body);

for (auto* get : gets.list) {

auto& sets = graph.getSets(get);

if (sets.size() == 0) {

continue; // unreachable, ignore

}

if (sets.size() == 1) {

// easy, just one set, use its index

auto* set = *sets.begin();

if (set) {

get->index = set->index;

} else {

// no set, assign param or zero

if (func->isParam(get->index)) {

// leave it, it's fine

} else if (LiteralUtils::canMakeZero(get->type)) {

// zero it out

(*graph.locations[get]) =

LiteralUtils::makeZero(get->type, *module);

// If we replace a local.get with a null then we are refining the

// type that the parent receives to a bottom type.

if (get->type.hasRef()) {

refinalize = true;

}

} else {

// No zero exists here, so this is a nondefaultable type. The

// default won't be used anyhow, so this value does not really

// matter and we have nothing to do.

}

}

continue;

}

if (!allowMerges) {

continue;

}

// more than 1 set, need a phi: a new local written to at each of the sets

auto new_ = addLocal(get->type);

auto old = get->index;

get->index = new_;

Builder builder(*module);

// write to the local in each of our sets

for (auto* set : sets) {

if (set) {

// a set exists, just add a tee of its value

auto* value = set->value;

auto* tee = builder.makeLocalTee(new_, value, get->type);

set->value = tee;

// the value may have been something we tracked the location

// of. if so, update that, since we moved it into the tee

if (graph.locations.contains(value)) {

assert(graph.locations[value] == &set->value);

graph.locations[value] = &tee->value;

}

} else {

// this is a param or the zero init value.

if (func->isParam(old)) {

// we add a set with the proper

// param value at the beginning of the function

auto* set = builder.makeLocalSet(

new_, builder.makeLocalGet(old, func->getLocalType(old)));

functionPrepends.push_back(set);

} else {

// this is a zero init, so we don't need to do anything actually

}

}

}

}

}

Index addLocal(Type type) { return Builder::addVar(func, type); }

void addPrepends() {

if (functionPrepends.size() > 0) {

Builder builder(*module);

auto* block = builder.makeBlock();

for (auto* pre : functionPrepends) {

block->list.push_back(pre);

}

block->list.push_back(func->body);

block->finalize(func->body->type);

func->body = block;

}

}