#include <cstdint>

#include <cstdio>

#include <cmath>

#include <string>

#include <algorithm>

#include <map>

#include "simple_ast.h"

#include "optimizer.h"

using namespace cashew;

typedef std::vector<IString> StringVec;

//==================

// Globals

//==================

Ref extraInfo;

//==================

// Infrastructure

//==================

template<class T, class V>

int indexOf(T list, V value) {

for (size_t i = 0; i < list.size(); i++) {

if (list[i] == value) return i;

}

return -1;

}

int jsD2I(double x) {

return (int)((int64_t)x);

}

char *strdupe(const char *str) {

char *ret = (char *)malloc(strlen(str)+1); // leaked!

strcpy(ret, str);

return ret;

}

IString getHeapStr(int x, bool unsign) {

switch (x) {

case 8: return unsign ? HEAPU8 : HEAP8;

case 16: return unsign ? HEAPU16 : HEAP16;

case 32: return unsign ? HEAPU32 : HEAP32;

}

assert(0);

return ":(";

}

Ref deStat(Ref node) {

if (node[0] == STAT) return node[1];

return node;

}

Ref getStatements(Ref node) {

if (node[0] == DEFUN) {

return node[3];

} else if (node[0] == BLOCK) {

return node->size() > 1 ? node[1] : nullptr;

} else {

return arena.alloc();

}

}

// Types

AsmType intToAsmType(int type) {

if (type >= 0 && type <= ASM_NONE) return (AsmType)type;

else {

assert(0);

return ASM_NONE;

}

}

// forward decls

Ref makeEmpty();

bool isEmpty(Ref node);

Ref makeAsmVarDef(const IString& v, AsmType type);

Ref makeArray(int size_hint);

Ref makeBool(bool b);

Ref makeNum(double x);

Ref makeName(IString str);

Ref makeAsmCoercion(Ref node, AsmType type);

Ref make1(IString type, Ref a);

Ref make3(IString type, Ref a, Ref b, Ref c);

AsmData::AsmData(Ref f) {

func = f;

// process initial params

Ref stats = func[3];

size_t i = 0;

while (i < stats->size()) {

Ref node = stats[i];

if (node[0] != STAT || node[1][0] != ASSIGN || node[1][2][0] != NAME) break;

node = node[1];

Ref name = node[2][1];

int index = func[2]->indexOf(name);

if (index < 0) break; // not an assign into a parameter, but a global

IString& str = name->getIString();

if (locals.count(str) > 0) break; // already done that param, must be starting function body

locals[str] = Local(detectType(node[3]), true);

params.push_back(str);

stats[i] = makeEmpty();

i++;

}

// process initial variable definitions and remove '= 0' etc parts - these

// are not actually assignments in asm.js

while (i < stats->size()) {

Ref node = stats[i];

if (node[0] != VAR) break;

for (size_t j = 0; j < node[1]->size(); j++) {

Ref v = node[1][j];

IString& name = v[0]->getIString();

Ref value = v[1];

if (locals.count(name) == 0) {

locals[name] = Local(detectType(value, nullptr, true), false);

vars.push_back(name);

v->setSize(1); // make an un-assigning var

} else {

assert(j == 0); // cannot break in the middle

goto outside;

}

}

i++;

}

outside:

// look for other var definitions and collect them

while (i < stats->size()) {

traversePre(stats[i], [&](Ref node) {

Ref type = node[0];

if (type == VAR) {

dump("bad, seeing a var in need of fixing", func);

abort(); //, 'should be no vars to fix! ' + func[1] + ' : ' + JSON.stringify(node));

}

});

i++;

}

// look for final RETURN statement to get return type.

Ref retStmt = stats->back();

if (!!retStmt && retStmt[0] == RETURN && !!retStmt[1]) {

ret = detectType(retStmt[1]);

} else {

ret = ASM_NONE;

}

}

void AsmData::denormalize() {

Ref stats = func[3];

// Remove var definitions, if any

for (size_t i = 0; i < stats->size(); i++) {

if (stats[i][0] == VAR) {

stats[i] = makeEmpty();

} else {

if (!isEmpty(stats[i])) break;

}

}

// calculate variable definitions

Ref varDefs = makeArray(vars.size());

for (auto v : vars) {

varDefs->push_back(makeAsmVarDef(v, locals[v].type));

}

// each param needs a line; reuse emptyNodes as much as we can

size_t numParams = params.size();

size_t emptyNodes = 0;

while (emptyNodes < stats->size()) {

if (!isEmpty(stats[emptyNodes])) break;

emptyNodes++;

}

size_t neededEmptyNodes = numParams + (varDefs->size() ? 1 : 0); // params plus one big var if there are vars

if (neededEmptyNodes > emptyNodes) {

stats->insert(0, neededEmptyNodes - emptyNodes);

} else if (neededEmptyNodes < emptyNodes) {

stats->splice(0, emptyNodes - neededEmptyNodes);

}

// add param coercions

int next = 0;

for (auto param : func[2]->getArray()) {

IString str = param->getIString();

assert(locals.count(str) > 0);

stats[next++] = make1(STAT, make3(ASSIGN, makeBool(true), makeName(str.c_str()), makeAsmCoercion(makeName(str.c_str()), locals[str].type)));

}

if (varDefs->size()) {

stats[next] = make1(VAR, varDefs);

}

/*

if (inlines->size() > 0) {

var i = 0;

traverse(func, function(node, type) {

if (type == CALL && node[1][0] == NAME && node[1][1] == 'inlinejs') {

node[1] = inlines[i++]; // swap back in the body

}

});

}

*/

// ensure that there's a final RETURN statement if needed.

if (ret != ASM_NONE) {

Ref retStmt = stats->back();

if (!retStmt || retStmt[0] != RETURN) {

Ref retVal = makeNum(0);

if (ret != ASM_INT) {

retVal = makeAsmCoercion(retVal, ret);

}

stats->push_back(make1(RETURN, retVal));

}

}

//printErr('denormalized \n\n' + astToSrc(func) + '\n\n');

}

// Constructions TODO: share common constructions, and assert they remain frozen

Ref makeArray(int size_hint=0) {

return &arena.alloc()->setArray(size_hint);

}

Ref makeBool(bool b) {

return &arena.alloc()->setBool(b);

}

Ref makeString(const IString& s) {

return &arena.alloc()->setString(s);

}

Ref makeEmpty() {

return ValueBuilder::makeToplevel();

}

Ref makeNum(double x) {

return ValueBuilder::makeDouble(x);

}

Ref makeName(IString str) {

return ValueBuilder::makeName(str);

}

Ref makeBlock() {

return ValueBuilder::makeBlock();

}

Ref make1(IString s1, Ref a) {

Ref ret(makeArray(2));

ret->push_back(makeString(s1));

ret->push_back(a);

return ret;

}

Ref make2(IString s1, IString s2, Ref a) {

Ref ret(makeArray(2));

ret->push_back(makeString(s1));

ret->push_back(makeString(s2));

ret->push_back(a);

return ret;

}

Ref make2(IString s1, Ref a, Ref b) {

Ref ret(makeArray(3));

ret->push_back(makeString(s1));

ret->push_back(a);

ret->push_back(b);

return ret;

}

Ref make3(IString type, IString a, Ref b, Ref c) {

Ref ret(makeArray(4));

ret->push_back(makeString(type));

ret->push_back(makeString(a));

ret->push_back(b);

ret->push_back(c);

return ret;

}

Ref make3(IString type, Ref a, Ref b, Ref c) {

Ref ret(makeArray(4));

ret->push_back(makeString(type));

ret->push_back(a);

ret->push_back(b);

ret->push_back(c);

return ret;

}

Ref makeAsmVarDef(const IString& v, AsmType type) {

Ref val;

switch (type) {

case ASM_INT: val = makeNum(0); break;

case ASM_DOUBLE: val = make2(UNARY_PREFIX, PLUS, makeNum(0)); break;

case ASM_FLOAT: {

if (!ASM_FLOAT_ZERO.isNull()) {

val = makeName(ASM_FLOAT_ZERO);

} else {

val = make2(CALL, makeName(MATH_FROUND), &(makeArray(1))->push_back(makeNum(0)));

}

break;

}

case ASM_FLOAT32X4: {

val = make2(CALL, makeName(SIMD_FLOAT32X4), &(makeArray(4))->push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)));

break;

}

case ASM_FLOAT64X2: {

val = make2(CALL, makeName(SIMD_FLOAT64X2), &(makeArray(2))->push_back(makeNum(0)).push_back(makeNum(0)));

break;

}

case ASM_INT8X16: {

val = make2(CALL, makeName(SIMD_INT8X16), &(makeArray(16))->push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)));

break;

}

case ASM_INT16X8: {

val = make2(CALL, makeName(SIMD_INT16X8), &(makeArray(8))->push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)));

break;

}

case ASM_INT32X4: {

val = make2(CALL, makeName(SIMD_INT32X4), &(makeArray(4))->push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)));

break;

}

default: assert(0);

}

return make1(v, val);

}

Ref makeAsmCoercion(Ref node, AsmType type) {

switch (type) {

case ASM_INT: return make3(BINARY, OR, node, makeNum(0));

case ASM_DOUBLE: return make2(UNARY_PREFIX, PLUS, node);

case ASM_FLOAT: return make2(CALL, makeName(MATH_FROUND), &(makeArray(1))->push_back(node));

case ASM_FLOAT32X4: return make2(CALL, makeName(SIMD_FLOAT32X4_CHECK), &(makeArray(1))->push_back(node));

case ASM_FLOAT64X2: return make2(CALL, makeName(SIMD_FLOAT64X2_CHECK), &(makeArray(1))->push_back(node));

case ASM_INT8X16: return make2(CALL, makeName(SIMD_INT8X16_CHECK), &(makeArray(1))->push_back(node));

case ASM_INT16X8: return make2(CALL, makeName(SIMD_INT16X8_CHECK), &(makeArray(1))->push_back(node));

case ASM_INT32X4: return make2(CALL, makeName(SIMD_INT32X4_CHECK), &(makeArray(1))->push_back(node));

case ASM_NONE:

default: return node; // non-validating code, emit nothing XXX this is dangerous, we should only allow this when we know we are not validating

}

}

// Checks

bool isEmpty(Ref node) {

return (node->size() == 2 && node[0] == TOPLEVEL && node[1]->size() == 0) ||

(node->size() > 0 && node[0] == BLOCK && (!node[1] || node[1]->size() == 0));

}

bool commable(Ref node) { // TODO: hashing

IString type = node[0]->getIString();

if (type == ASSIGN || type == BINARY || type == UNARY_PREFIX || type == NAME || type == NUM || type == CALL || type == SEQ || type == CONDITIONAL || type == SUB) return true;

return false;

}

bool isMathFunc(const char *name) {

static const char *Math_ = "Math_";

static unsigned size = strlen(Math_);

return strncmp(name, Math_, size) == 0;

}

bool isMathFunc(Ref value) {

return value->isString() && isMathFunc(value->getCString());

}

bool callHasSideEffects(Ref node) { // checks if the call itself (not the args) has side effects (or is not statically known)

return !(node[1][0] == NAME && isMathFunc(node[1][1]));

}

bool hasSideEffects(Ref node) { // this is 99% incomplete!

IString type = node[0]->getIString();

switch (type[0]) {

case 'n':

if (type == NUM || type == NAME) return false;

break;

case 's':

if (type == STRING) return false;

if (type == SUB) return hasSideEffects(node[1]) || hasSideEffects(node[2]);

break;

case 'u':

if (type == UNARY_PREFIX) return hasSideEffects(node[2]);

break;

case 'b':

if (type == BINARY) return hasSideEffects(node[2]) || hasSideEffects(node[3]);

break;

case 'c':

if (type == CALL) {

if (callHasSideEffects(node)) return true;

// This is a statically known call, with no side effects. only args can side effect us

for (auto arg : node[2]->getArray()) {

if (hasSideEffects(arg)) return true;

}

return false;

} else if (type == CONDITIONAL) return hasSideEffects(node[1]) || hasSideEffects(node[2]) || hasSideEffects(node[3]);

break;

}

return true;

}

// checks if a node has just basic operations, nothing with side effects nor that can notice side effects, which

// implies we can move it around in the code

bool triviallySafeToMove(Ref node, AsmData& asmData) {

bool ok = true;

traversePre(node, [&](Ref node) {

Ref type = node[0];

if (type == STAT || type == BINARY || type == UNARY_PREFIX || type == ASSIGN || type == NUM) return;

else if (type == NAME) {

if (!asmData.isLocal(node[1]->getIString())) ok = false;

} else if (type == CALL) {

if (callHasSideEffects(node)) ok = false;

} else {

ok = false;

}

});

return ok;

}

// Transforms

// We often have branchings that are simplified so one end vanishes, and

// we then get

// if (!(x < 5))

// or such. Simplifying these saves space and time.

Ref simplifyNotCompsDirect(Ref node) {

if (node[0] == UNARY_PREFIX && node[1] == L_NOT) {

// de-morgan's laws do not work on floats, due to nans >:(

if (node[2][0] == BINARY && (detectType(node[2][2]) == ASM_INT && detectType(node[2][3]) == ASM_INT)) {

Ref op = node[2][1];

switch(op->getCString()[0]) {

case '<': {

if (op == LT) { op->setString(GE); break; }

if (op == LE) { op->setString(GT); break; }

return node;

}

case '>': {

if (op == GT) { op->setString(LE); break; }

if (op == GE) { op->setString(LT); break; }

return node;

}

case '=': {

if (op == EQ) { op->setString(NE); break; }

return node;

}

case '!': {

if (op == NE) { op->setString(EQ); break; }

return node;

}

default: return node;

}

return make3(BINARY, op, node[2][2], node[2][3]);

} else if (node[2][0] == UNARY_PREFIX && node[2][1] == L_NOT) {

return node[2][2];

}

}

return node;

}

Ref flipCondition(Ref cond) {

return simplifyNotCompsDirect(make2(UNARY_PREFIX, L_NOT, cond));

}

void safeCopy(Ref target, Ref source) { // safely copy source onto target, even if source is a subnode of target

Ref temp = source; // hold on to source

*target = *temp;

}

void clearEmptyNodes(Ref arr) {

int skip = 0;

for (size_t i = 0; i < arr->size(); i++) {

if (skip) {

arr[i-skip] = arr[i];

}

if (isEmpty(deStat(arr[i]))) {

skip++;

}

}

if (skip) arr->setSize(arr->size() - skip);

}

void clearUselessNodes(Ref arr) {

int skip = 0;

for (size_t i = 0; i < arr->size(); i++) {

Ref curr = arr[i];

if (skip) {

arr[i-skip] = curr;

}

if (isEmpty(deStat(curr)) || (curr[0] == STAT && !hasSideEffects(curr[1]))) {

skip++;

}

}

if (skip) arr->setSize(arr->size() - skip);

}

void removeAllEmptySubNodes(Ref ast) {

traversePre(ast, [](Ref node) {

if (node[0] == DEFUN) {

clearEmptyNodes(node[3]);

} else if (node[0] == BLOCK && node->size() > 1 && !!node[1]) {

clearEmptyNodes(node[1]);

} else if (node[0] == SEQ && isEmpty(node[1])) {

safeCopy(node, node[2]);

}

});

}

void removeAllUselessSubNodes(Ref ast) {

traversePrePost(ast, [](Ref node) {

Ref type = node[0];

if (type == DEFUN) {

clearUselessNodes(node[3]);

} else if (type == BLOCK && node->size() > 1 && !!node[1]) {

clearUselessNodes(node[1]);

} else if (type == SEQ && isEmpty(node[1])) {

safeCopy(node, node[2]);

}

}, [](Ref node) {

Ref type = node[0];

if (type == IF) {

bool empty2 = isEmpty(node[2]), has3 = node->size() == 4 && !!node[3], empty3 = !has3 || isEmpty(node[3]);

if (!empty2 && empty3 && has3) { // empty else clauses

node->setSize(3);

} else if (empty2 && !empty3) { // empty if blocks

safeCopy(node, make2(IF, make2(UNARY_PREFIX, L_NOT, node[1]), node[3]));

} else if (empty2 && empty3) {

if (hasSideEffects(node[1])) {

safeCopy(node, make1(STAT, node[1]));

} else {

safeCopy(node, makeEmpty());

}

}

}

});

}

Ref unVarify(Ref vars) { // transform var x=1, y=2 etc. into (x=1, y=2), i.e., the same assigns, but without a var definition

Ref ret = makeArray(1);

ret->push_back(makeString(STAT));

if (vars->size() == 1) {

ret->push_back(make3(ASSIGN, makeBool(true), makeName(vars[0][0]->getIString()), vars[0][1]));

} else {

ret->push_back(makeArray(vars->size()-1));

Ref curr = ret[1];

for (size_t i = 0; i+1 < vars->size(); i++) {

curr->push_back(makeString(SEQ));

curr->push_back(make3(ASSIGN, makeBool(true), makeName(vars[i][0]->getIString()), vars[i][1]));

if (i != vars->size()-2) {

curr->push_back(makeArray());

curr = curr[2];

}

}

curr->push_back(make3(ASSIGN, makeBool(true), makeName(vars->back()[0]->getIString()), vars->back()[1]));

}

return ret;

}

// Calculations

int measureCost(Ref ast) {

int size = 0;

traversePre(ast, [&size](Ref node) {

Ref type = node[0];

if (type == NUM || type == UNARY_PREFIX) size--;

else if (type == BINARY) {

if (node[3][0] == NUM && node[3][1]->getNumber() == 0) size--;

else if (node[1] == DIV || node[1] == MOD) size += 2;

}

else if (type == CALL && !callHasSideEffects(node)) size -= 2;

else if (type == SUB) size++;

size++;

});

return size;

}

//==================

// Params

//==================

bool preciseF32 = false,

receiveJSON = false,

emitJSON = false,

minifyWhitespace = false,

last = false;

//=====================

// Optimization passes

//=====================

#define HASES \

bool has(const IString& str) { \

return count(str) > 0; \

} \

bool has(Ref node) { \

return node->isString() && count(node->getIString()) > 0; \

}

class StringSet : public cashew::IStringSet {

public:

StringSet() {}

StringSet(const char *str) : IStringSet(str) {}

HASES

void dump() {

err("===");

for (auto str : *this) {

errv("%s", str.c_str());

}

err("===");

}

};

StringSet USEFUL_BINARY_OPS("<< >> | & ^"),

COMPARE_OPS("< <= > >= == == != !=="),

BITWISE("| & ^"),

SAFE_BINARY_OPS("+ -"), // division is unsafe as it creates non-ints in JS; mod is unsafe as signs matter so we can't remove |0's; mul does not nest with +,- in asm

COERCION_REQUIRING_OPS("sub unary-prefix"), // ops that in asm must be coerced right away

COERCION_REQUIRING_BINARIES("* / %"); // binary ops that in asm must be coerced

StringSet ASSOCIATIVE_BINARIES("+ * | & ^"),

CONTROL_FLOW("do while for if switch"),

LOOP("do while for"),

NAME_OR_NUM("name num"),

CONDITION_CHECKERS("if do while switch"),

SAFE_TO_DROP_COERCION("unary-prefix name num");

StringSet BREAK_CAPTURERS("do while for switch"),

CONTINUE_CAPTURERS("do while for"),

FUNCTIONS_THAT_ALWAYS_THROW("abort ___resumeException ___cxa_throw ___cxa_rethrow");

bool isFunctionTable(const char *name) {

static const char *functionTable = "FUNCTION_TABLE";

static unsigned size = strlen(functionTable);

return strncmp(name, functionTable, size) == 0;

}

bool isFunctionTable(Ref value) {

return value->isString() && isFunctionTable(value->getCString());

}

// Internal utilities

bool canDropCoercion(Ref node) {

if (SAFE_TO_DROP_COERCION.has(node[0])) return true;

if (node[0] == BINARY) {

switch (node[1]->getCString()[0]) {

case '>': return node[1] == RSHIFT || node[1] == TRSHIFT;

case '<': return node[1] == LSHIFT;

case '|': case '^': case '&': return true;

}

}

return false;

}

Ref simplifyCondition(Ref node) {

node = simplifyNotCompsDirect(node);

// on integers, if (x == 0) is the same as if (x), and if (x != 0) as if (!x)

if (node[0] == BINARY && (node[1] == EQ || node[1] == NE)) {

Ref target;

if (detectType(node[2]) == ASM_INT && node[3][0] == NUM && node[3][1]->getNumber() == 0) {

target = node[2];

} else if (detectType(node[3]) == ASM_INT && node[2][0] == NUM && node[2][1]->getNumber() == 0) {

target = node[3];

}

if (!!target) {

if (target[0] == BINARY && (target[1] == OR || target[1] == TRSHIFT) && target[3][0] == NUM && target[3][1]->getNumber() == 0 &&

canDropCoercion(target[2])) {

target = target[2]; // drop the coercion, in a condition it is ok to do if (x)

}

if (node[1] == EQ) {

return make2(UNARY_PREFIX, L_NOT, target);

} else {

return target;

}

}

}

return node;

}

// Passes

// Eliminator aka Expressionizer

//

// The goal of this pass is to eliminate unneeded variables (which represent one of the infinite registers in the LLVM

// model) and thus to generate complex expressions where possible, for example

//

// var x = a(10);

// var y = HEAP[20];

// print(x+y);

//

// can be transformed into

//

// print(a(10)+HEAP[20]);

//

// The basic principle is to scan along the code in the order of parsing/execution, and keep a list of tracked

// variables that are current contenders for elimination. We must untrack when we see something that we cannot

// cross, for example, a write to memory means we must invalidate variables that depend on reading from

// memory, since if we change the order then we do not preserve the computation.

//

// We rely on some assumptions about emscripten-generated code here, which means we can do a lot more than

// a general JS optimization can. For example, we assume that SUB nodes (indexing like HEAP[..]) are

// memory accesses or FUNCTION_TABLE accesses, and in both cases that the symbol cannot be replaced although

// the contents can. So we assume FUNCTION_TABLE might have its contents changed but not be pointed to

// a different object, which allows

//

// var x = f();

// FUNCTION_TABLE[x]();

//

// to be optimized (f could replace FUNCTION_TABLE, so in general JS eliminating x is not valid).

//

// In memSafe mode, we are more careful and assume functions can replace HEAP and FUNCTION_TABLE, which

// can happen in ALLOW_MEMORY_GROWTH mode

StringSet ELIMINATION_SAFE_NODES("assign call if toplevel do return label switch binary unary-prefix"); // do is checked carefully, however

StringSet IGNORABLE_ELIMINATOR_SCAN_NODES("num toplevel string break continue dot"); // dot can only be STRING_TABLE.*

StringSet ABORTING_ELIMINATOR_SCAN_NODES("new object function defun for while array throw"); // we could handle some of these, TODO, but nontrivial (e.g. for while, the condition is hit multiple times after the body)

StringSet HEAP_NAMES("HEAP8 HEAP16 HEAP32 HEAPU8 HEAPU16 HEAPU32 HEAPF32 HEAPF64");

bool isTempDoublePtrAccess(Ref node) { // these are used in bitcasts; they are not really affecting memory, and should cause no invalidation

assert(node[0] == SUB);

return (node[2][0] == NAME && node[2][1] == TEMP_DOUBLE_PTR) ||

(node[2][0] == BINARY && ((node[2][2][0] == NAME && node[2][2][1] == TEMP_DOUBLE_PTR) ||

(node[2][3][0] == NAME && node[2][3][1] == TEMP_DOUBLE_PTR)));

}

class StringIntMap : public std::unordered_map<IString, int> {

public:

HASES

};

class StringStringMap : public std::unordered_map<IString, IString> {

public:

HASES

};

class StringRefMap : public std::unordered_map<IString, Ref> {

public:

HASES

};

class StringTypeMap : public std::unordered_map<IString, AsmType> {

public:

HASES

};

void eliminate(Ref ast, bool memSafe) {

#ifdef PROFILING

clock_t tasmdata = 0;

clock_t tfnexamine = 0;

clock_t tvarcheck = 0;

clock_t tstmtelim = 0;

clock_t tstmtscan = 0;

clock_t tcleanvars = 0;

clock_t treconstruct = 0;

#endif

// Find variables that have a single use, and if they can be eliminated, do so

traverseFunctions(ast, [&](Ref func) {

#ifdef PROFILING

clock_t start = clock();

#endif

AsmData asmData(func);

#ifdef PROFILING

tasmdata += clock() - start;

start = clock();

#endif

// First, find the potentially eliminatable functions: that have one definition and one use

StringIntMap definitions;

StringIntMap uses;

StringIntMap namings;

StringRefMap values;

StringIntMap varsToRemove; // variables being removed, that we can eliminate all 'var x;' of (this refers to VAR nodes we should remove)

// 1 means we should remove it, 2 means we successfully removed it

StringSet varsToTryToRemove; // variables that have 0 uses, but have side effects - when we scan we can try to remove them

// examine body and note locals

traversePre(func, [&](Ref node) {

Ref type = node[0];

if (type == NAME) {

IString& name = node[1]->getIString();

uses[name]++;

namings[name]++;

} else if (type == ASSIGN) {

Ref target = node[2];

if (target[0] == NAME) {

IString& name = target[1]->getIString();

// values is only used if definitions is 1

if (definitions[name]++ == 0) {

values[name] = node[3];

}

assert(node[1]->isBool(true)); // not +=, -= etc., just =

uses[name]--; // because the name node will show up by itself in the previous case

}

}

});

#ifdef PROFILING

tfnexamine += clock() - start;

start = clock();

#endif

StringSet potentials; // local variables with 1 definition and 1 use

StringSet sideEffectFree; // whether a local variable has no side effects in its definition. Only relevant when there are no uses

auto unprocessVariable = [&](IString name) {

potentials.erase(name);

varsToRemove.erase(name);

sideEffectFree.erase(name);

varsToTryToRemove.erase(name);

};

std::function<void (IString)> processVariable = [&](IString name) {

if (definitions[name] == 1 && uses[name] == 1) {

potentials.insert(name);

} else if (uses[name] == 0 && definitions[name] <= 1) { // no uses, no def or 1 def (cannot operate on phis, and the llvm optimizer will remove unneeded phis anyhow) (no definition means it is a function parameter, or a local with just |var x;| but no defining assignment)

bool sideEffects = false;

auto val = values.find(name);

Ref value;

if (val != values.end()) {

value = val->second;

// TODO: merge with other side effect code

// First, pattern-match

// (HEAP32[((tempDoublePtr)>>2)]=((HEAP32[(($_sroa_0_0__idx1)>>2)])|0),HEAP32[(((tempDoublePtr)+(4))>>2)]=((HEAP32[((($_sroa_0_0__idx1)+(4))>>2)])|0),(+(HEAPF64[(tempDoublePtr)>>3])))

// which has no side effects and is the special form of converting double to i64.

if (!(value[0] == SEQ && value[1][0] == ASSIGN && value[1][2][0] == SUB && value[1][2][2][0] == BINARY && value[1][2][2][1] == RSHIFT &&

value[1][2][2][2][0] == NAME && value[1][2][2][2][1] == TEMP_DOUBLE_PTR)) {

// If not that, then traverse and scan normally.

sideEffects = hasSideEffects(value);

}

}

if (!sideEffects) {

varsToRemove[name] = !definitions[name] ? 2 : 1; // remove it normally

sideEffectFree.insert(name);

// Each time we remove a variable with 0 uses, if its value has no

// side effects and vanishes too, then we can remove a use from variables

// appearing in it, and possibly eliminate again

if (!!value) {

traversePre(value, [&](Ref node) {

if (node[0] == NAME) {

IString name = node[1]->getIString();

node[1]->setString(EMPTY); // we can remove this - it will never be shown, and should not be left to confuse us as we traverse

if (asmData.isLocal(name)) {

uses[name]--; // cannot be infinite recursion since we descend an energy function

assert(uses[name] >= 0);

unprocessVariable(name);

processVariable(name);

}

} else if (node[0] == CALL) {

// no side effects, so this must be a Math.* call or such. We can just ignore it and all children

node[0]->setString(NAME);

node[1]->setString(EMPTY);

}

});

}

} else {

varsToTryToRemove.insert(name); // try to remove it later during scanning

}

}

};

for (auto name : asmData.locals) {

processVariable(name.first);

}

#ifdef PROFILING

tvarcheck += clock() - start;

start = clock();

#endif

//printErr('defs: ' + JSON.stringify(definitions));

//printErr('uses: ' + JSON.stringify(uses));

//printErr('values: ' + JSON.stringify(values));

//printErr('locals: ' + JSON.stringify(locals));

//printErr('varsToRemove: ' + JSON.stringify(varsToRemove));

//printErr('varsToTryToRemove: ' + JSON.stringify(varsToTryToRemove));

values.clear();

//printErr('potentials: ' + JSON.stringify(potentials));

// We can now proceed through the function. In each list of statements, we try to eliminate

struct Tracking {

bool usesGlobals, usesMemory, hasDeps;

Ref defNode;

bool doesCall;

};

class Tracked : public std::unordered_map<IString, Tracking> {

public:

HASES

};

Tracked tracked;

#define dumpTracked() { errv("tracking %d", tracked.size()); for (auto t : tracked) errv("... %s", t.first.c_str()); }

// Although a set would be more appropriate, it would also be slower

std::unordered_map<IString, StringVec> depMap;

bool globalsInvalidated = false; // do not repeat invalidations, until we track something new

bool memoryInvalidated = false;

bool callsInvalidated = false;

auto track = [&](IString name, Ref value, Ref defNode) { // add a potential that has just been defined to the tracked list, we hope to eliminate it

Tracking& track = tracked[name];

track.usesGlobals = false;

track.usesMemory = false;

track.hasDeps = false;

track.defNode = defNode;

track.doesCall = false;

bool ignoreName = false; // one-time ignorings of names, as first op in sub and call

traversePre(value, [&](Ref node) {

Ref type = node[0];

if (type == NAME) {

if (!ignoreName) {

IString depName = node[1]->getIString();

if (!asmData.isLocal(depName)) {

track.usesGlobals = true;

}

if (!potentials.has(depName)) { // deps do not matter for potentials - they are defined once, so no complexity

depMap[depName].push_back(name);

track.hasDeps = true;

}

} else {

ignoreName = false;

}

} else if (type == SUB) {

track.usesMemory = true;

ignoreName = true;

} else if (type == CALL) {

track.usesGlobals = true;

track.usesMemory = true;

track.doesCall = true;

ignoreName = true;

} else {

ignoreName = false;

}

});

if (track.usesGlobals) globalsInvalidated = false;

if (track.usesMemory) memoryInvalidated = false;

if (track.doesCall) callsInvalidated = false;

};

// TODO: invalidate using a sequence number for each type (if you were tracked before the last invalidation, you are cancelled). remove for.in loops

#define INVALIDATE(what, check) \

auto invalidate##what = [&]() { \

std::vector<IString> temp; \

for (auto t : tracked) { \

IString name = t.first; \

Tracking& info = tracked[name]; \

if (check) { \

temp.push_back(name); \

} \

} \

for (size_t i = 0; i < temp.size(); i++) { \

tracked.erase(temp[i]); \

} \

};

INVALIDATE(Globals, info.usesGlobals);

INVALIDATE(Memory, info.usesMemory);

INVALIDATE(Calls, info.doesCall);

auto invalidateByDep = [&](IString dep) {

for (auto name : depMap[dep]) {

tracked.erase(name);

}

depMap.erase(dep);

};

std::function<void (IString name, Ref node)> doEliminate;

// Generate the sequence of execution. This determines what is executed before what, so we know what can be reordered. Using

// that, performs invalidations and eliminations

auto scan = [&](Ref node) {

bool abort = false;

bool allowTracking = true; // false inside an if; also prevents recursing in an if

std::function<void (Ref, bool)> traverseInOrder = [&](Ref node, bool ignoreSub) {

if (abort) return;

Ref type = node[0];

if (type == ASSIGN) {

Ref target = node[2];

Ref value = node[3];

bool nameTarget = target[0] == NAME;

// If this is an assign to a name, handle it below rather than

// traversing and treating as a read

if (!nameTarget) {

traverseInOrder(target, true); // evaluate left

}

traverseInOrder(value, false); // evaluate right

// do the actual assignment

if (nameTarget) {

IString name = target[1]->getIString();

if (potentials.has(name) && allowTracking) {

track(name, node[3], node);

} else if (varsToTryToRemove.has(name)) {

// replace it in-place

safeCopy(node, value);

varsToRemove[name] = 2;

} else {

// expensive check for invalidating specific tracked vars. This list is generally quite short though, because of

// how we just eliminate in short spans and abort when control flow happens TODO: history numbers instead

invalidateByDep(name); // can happen more than once per dep..

if (!asmData.isLocal(name) && !globalsInvalidated) {

invalidateGlobals();

globalsInvalidated = true;

}

// if we can track this name (that we assign into), and it has 0 uses and we want to remove its VAR

// definition - then remove it right now, there is no later chance

if (allowTracking && varsToRemove.has(name) && uses[name] == 0) {

track(name, node[3], node);

doEliminate(name, node);

}

}

} else if (target[0] == SUB) {