#include <cstdint>

#include <cstdio>

#include <cmath>

#include <string>

#include <algorithm>

#include <map>

#include "simple_ast.h"

#include "optimizer.h"

typedef std::vector<IString> StringVec;

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

// Globals

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

Ref extraInfo;

IString SIMD_INT8X16_CHECK("SIMD_Int8x16_check"),

SIMD_INT16X8_CHECK("SIMD_Int16x8_check"),

SIMD_INT32X4_CHECK("SIMD_Int32x4_check"),

SIMD_FLOAT32X4_CHECK("SIMD_Float32x4_check"),

SIMD_FLOAT64X2_CHECK("SIMD_Float64x2_check");

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

// 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;

}

int parseInt(const char *str) {

int ret = *str - '0';

while (*(++str)) {

ret *= 10;

ret += *str - '0';

}

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

enum AsmType {

ASM_INT = 0,

ASM_DOUBLE,

ASM_FLOAT,

ASM_FLOAT32X4,

ASM_FLOAT64X2,

ASM_INT8X16,

ASM_INT16X8,

ASM_INT32X4,

ASM_NONE // number of types

};

AsmType intToAsmType(int type) {

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

else {

assert(0);

return ASM_NONE;

}

}

// forward decls

struct AsmData;

AsmType detectType(Ref node, AsmData *asmData=nullptr, bool inVarDef=false);

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);

struct AsmData {

struct Local {

Local() {}

Local(AsmType type, bool param) : type(type), param(param) {}

AsmType type;

bool param; // false if a var

};

typedef std::unordered_map<IString, Local> Locals;

Locals locals;

std::vector<IString> params; // in order

std::vector<IString> vars; // in order

AsmType ret;

Ref func;

AsmType getType(const IString& name) {

auto ret = locals.find(name);

if (ret != locals.end()) return ret->second.type;

return ASM_NONE;

}

void setType(const IString& name, AsmType type) {

locals[name].type = type;

}

bool isLocal(const IString& name) {

return locals.count(name) > 0;

}

bool isParam(const IString& name) {

return isLocal(name) && locals[name].param;

}

bool isVar(const IString& name) {

return isLocal(name) && !locals[name].param;

}

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 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');

}

void addParam(IString name, AsmType type) {

locals[name] = Local(type, true);

params.push_back(name);

}

void addVar(IString name, AsmType type) {

locals[name] = Local(type, false);

vars.push_back(name);

}

void deleteVar(IString name) {

locals.erase(name);

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

if (vars[i] == name) {

vars.erase(vars.begin() + i);

break;

}

}

}

};

struct HeapInfo {

bool valid, unsign, floaty;

int bits;

AsmType type;

};

HeapInfo parseHeap(const char *name) {

HeapInfo ret;

if (name[0] != 'H' || name[1] != 'E' || name[2] != 'A' || name[3] != 'P') {

ret.valid = false;

return ret;

}

ret.valid = true;

ret.unsign = name[4] == 'U';

ret.floaty = name[4] == 'F';

ret.bits = parseInt(name + (ret.unsign || ret.floaty ? 5 : 4));

ret.type = !ret.floaty ? ASM_INT : (ret.bits == 64 ? ASM_DOUBLE : ASM_FLOAT);

return ret;

}

bool isInteger(double x) {

return fmod(x, 1) == 0;

}

bool isInteger32(double x) {

return isInteger(x) && (x == (int32_t)x || x == (uint32_t)x);

}

IString ASM_FLOAT_ZERO;

AsmType detectType(Ref node, AsmData *asmData, bool inVarDef) {

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

case 'n': {

if (node[0] == NUM) {

if (!isInteger(node[1]->getNumber())) return ASM_DOUBLE;

return ASM_INT;

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

if (asmData) {

AsmType ret = asmData->getType(node[1]->getCString());

if (ret != ASM_NONE) return ret;

}

if (!inVarDef) {

if (node[1] == INF || node[1] == NaN) return ASM_DOUBLE;

if (node[1] == TEMP_RET0) return ASM_INT;

return ASM_NONE;

}

// We are in a variable definition, where Math_fround(0) optimized into a global constant becomes f0 = Math_fround(0)

if (ASM_FLOAT_ZERO.isNull()) ASM_FLOAT_ZERO = node[1]->getIString();

else assert(node[1] == ASM_FLOAT_ZERO);

return ASM_FLOAT;

}

break;

}

case 'u': {

if (node[0] == UNARY_PREFIX) {

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

case '+': return ASM_DOUBLE;

case '-': return detectType(node[2], asmData, inVarDef);

case '!': case '~': return ASM_INT;

}

break;

}

break;

}

case 'c': {

if (node[0] == CALL) {

if (node[1][0] == NAME) {

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

if (name == MATH_FROUND) return ASM_FLOAT;

else if (name == SIMD_FLOAT32X4 || name == SIMD_FLOAT32X4_CHECK) return ASM_FLOAT32X4;

else if (name == SIMD_FLOAT64X2 || name == SIMD_FLOAT64X2_CHECK) return ASM_FLOAT64X2;

else if (name == SIMD_INT8X16 || name == SIMD_INT8X16_CHECK) return ASM_INT8X16;

else if (name == SIMD_INT16X8 || name == SIMD_INT16X8_CHECK) return ASM_INT16X8;

else if (name == SIMD_INT32X4 || name == SIMD_INT32X4_CHECK) return ASM_INT32X4;

}

return ASM_NONE;

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

return detectType(node[2], asmData, inVarDef);

}

break;

}

case 'b': {

if (node[0] == BINARY) {

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

case '+': case '-':

case '*': case '/': case '%': return detectType(node[2], asmData, inVarDef);

case '|': case '&': case '^': case '<': case '>': // handles <<, >>, >>=, <=, >=

case '=': case '!': { // handles ==, !=

return ASM_INT;

}

}

}

break;

}

case 's': {

if (node[0] == SEQ) {

return detectType(node[2], asmData, inVarDef);

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

assert(node[1][0] == NAME);

HeapInfo info = parseHeap(node[1][1]->getCString());

if (info.valid) return ASM_NONE;

return info.floaty ? ASM_DOUBLE : ASM_INT; // XXX ASM_FLOAT?

}

break;

}

}

dump("horrible", node);

assert(0);

return ASM_NONE;

}

// 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) {