Google Git
Sign in
chromium / external / github.com / kripken / emscripten / refs/heads/add_python2_warning / . / tools / optimizer / optimizer.cpp
blob: 973f2699832e66765b74a594c19e6297dbf769e9 [file] [log] [blame] [edit]
// Copyright 2014 The Emscripten Authors. All rights reserved.
// Emscripten is available under two separate licenses, the MIT license and the
// University of Illinois/NCSA Open Source License. Both these licenses can be
// found in the LICENSE file.
#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 makeAsmCoercedZero(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(make1(v, makeAsmCoercedZero(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) {
stats->push_back(make1(RETURN, makeAsmCoercedZero(ret)));
}
}
//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 makeAsmCoercedZero(AsmType type) {
switch (type) {
case ASM_INT: return makeNum(0); break;
case ASM_DOUBLE: return make2(UNARY_PREFIX, PLUS, makeNum(0)); break;
case ASM_FLOAT: {
if (!ASM_FLOAT_ZERO.isNull()) {
return makeName(ASM_FLOAT_ZERO);
} else {
return make2(CALL, makeName(MATH_FROUND), &(makeArray(1))->push_back(makeNum(0)));
}
break;
}
case ASM_FLOAT32X4: {
return 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: {
return make2(CALL, makeName(SIMD_FLOAT64X2), &(makeArray(2))->push_back(makeNum(0)).push_back(makeNum(0)));
break;
}
case ASM_INT8X16: {
return 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: {
return 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: {
return make2(CALL, makeName(SIMD_INT32X4), &(makeArray(4))->push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)));
break;
}
case ASM_BOOL8X16: {
return make2(CALL, makeName(SIMD_BOOL8X16), &(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_BOOL16X8: {
return make2(CALL, makeName(SIMD_BOOL16X8), &(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_BOOL32X4: {
return make2(CALL, makeName(SIMD_BOOL32X4), &(makeArray(4))->push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)).push_back(makeNum(0)));
break;
}
case ASM_BOOL64X2: {
return make2(CALL, makeName(SIMD_BOOL64X2), &(makeArray(2))->push_back(makeNum(0)).push_back(makeNum(0)));
break;
}
default: assert(0);
}
abort();
}
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"),
BOOLEAN_RECEIVERS("if do while conditional"),
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");
IString DCEABLE_TYPE_DECLS("__emscripten_dceable_type_decls");
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) {
if (isTempDoublePtrAccess(target)) {
if (!globalsInvalidated) {
invalidateGlobals();
globalsInvalidated = true;
}
} else if (!memoryInvalidated) {
invalidateMemory();
memoryInvalidated = true;
}
}
} else if (type == SUB) {
// Only keep track of the global array names in memsafe mode i.e.
// when they may change underneath us due to resizing
if (node[1][0] != NAME || memSafe) {
traverseInOrder(node[1], false); // evaluate inner
}
traverseInOrder(node[2], false); // evaluate outer
// ignoreSub means we are a write (happening later), not a read
if (!ignoreSub && !isTempDoublePtrAccess(node)) {
// do the memory access
if (!callsInvalidated) {
invalidateCalls();
callsInvalidated = true;
}
}
} else if (type == BINARY) {
bool flipped = false;
if (ASSOCIATIVE_BINARIES.has(node[1]) && !NAME_OR_NUM.has(node[2][0]) && NAME_OR_NUM.has(node[3][0])) { // TODO recurse here?
// associatives like + and * can be reordered in the simple case of one of the sides being a name, since we assume they are all just numbers
Ref temp = node[2];
node[2] = node[3];
node[3] = temp;
flipped = true;
}
traverseInOrder(node[2], false);
traverseInOrder(node[3], false);
if (flipped && NAME_OR_NUM.has(node[2][0])) { // dunno if we optimized, but safe to flip back - and keeps the code closer to the original and more readable
Ref temp = node[2];
node[2] = node[3];
node[3] = temp;
}
} else if (type == NAME) {
IString name = node[1]->getIString();
if (tracked.has(name)) {
doEliminate(name, node);
} else if (!asmData.isLocal(name) && !callsInvalidated && (memSafe || !HEAP_NAMES.has(name))) { // ignore HEAP8 etc when not memory safe, these are ok to
// access, e.g. SIMD_Int32x4_load(HEAP8, ...)
invalidateCalls();
callsInvalidated = true;
}
} else if (type == UNARY_PREFIX) {
traverseInOrder(node[2], false);
} else if (IGNORABLE_ELIMINATOR_SCAN_NODES.has(type)) {
} else if (type == CALL) {
// Named functions never change and are therefore safe to not track
if (node[1][0] != NAME) {
traverseInOrder(node[1], false);
}
Ref args = node[2];
for (size_t i = 0; i < args->size(); i++) {
traverseInOrder(args[i], false);
}
if (callHasSideEffects(node)) {
// these two invalidations will also invalidate calls
if (!globalsInvalidated) {
invalidateGlobals();
globalsInvalidated = true;
}
if (!memoryInvalidated) {
invalidateMemory();
memoryInvalidated = true;
}
}
} else if (type == IF) {
if (allowTracking) {
traverseInOrder(node[1], false); // can eliminate into condition, but nowhere else
if (!callsInvalidated) { // invalidate calls, since we cannot eliminate them into an if that may not execute!
invalidateCalls();
callsInvalidated = true;
}
allowTracking = false;
traverseInOrder(node[2], false); // 2 and 3 could be 'parallel', really..
if (!!node[3]) traverseInOrder(node[3], false);
allowTracking = true;
} else {
tracked.clear();
}
} else if (type == BLOCK) {
Ref stats = getStatements(node);
if (!!stats) {
for (size_t i = 0; i < stats->size(); i++) {
traverseInOrder(stats[i], false);
}
}
} else if (type == STAT) {
traverseInOrder(node[1], false);
} else if (type == LABEL) {
traverseInOrder(node[2], false);
} else if (type == SEQ) {
traverseInOrder(node[1], false);
traverseInOrder(node[2], false);
} else if (type == DO) {
if (node[1][0] == NUM && node[1][1]->getNumber() == 0) { // one-time loop
traverseInOrder(node[2], false);
} else {
tracked.clear();
}
} else if (type == RETURN) {
if (!!node[1]) traverseInOrder(node[1], false);
} else if (type == CONDITIONAL) {
if (!callsInvalidated) { // invalidate calls, since we cannot eliminate them into a branch of an LLVM select/JS conditional that does not execute
invalidateCalls();
callsInvalidated = true;
}
traverseInOrder(node[1], false);
traverseInOrder(node[2], false);
traverseInOrder(node[3], false);
} else if (type == SWITCH) {
traverseInOrder(node[1], false);
Tracked originalTracked = tracked;
Ref cases = node[2];
for (size_t i = 0; i < cases->size(); i++) {
Ref c = cases[i];
assert(c[0]->isNull() || c[0][0] == NUM || (c[0][0] == UNARY_PREFIX && c[0][2][0] == NUM));
Ref stats = c[1];
for (size_t j = 0; j < stats->size(); j++) {
traverseInOrder(stats[j], false);
}
// We cannot track from one switch case into another if there are external dependencies, undo all new trackings
// Otherwise we can track, e.g. a var used in a case before assignment in another case is UB in asm.js, so no need for the assignment
// TODO: general framework here, use in if-else as well
std::vector<IString> toDelete;
for (auto t : tracked) {
if (!originalTracked.has(t.first)) {
Tracking& info = tracked[t.first];
if (info.usesGlobals || info.usesMemory || info.hasDeps) {
toDelete.push_back(t.first);
}
}
}
for (auto t : toDelete) {
tracked.erase(t);
}
}
tracked.clear(); // do not track from inside the switch to outside
} else {
assert(ABORTING_ELIMINATOR_SCAN_NODES.has(type));
tracked.clear();
abort = true;
}
};
traverseInOrder(node, false);
};
//var eliminationLimit = 0; // used to debugging purposes
doEliminate = [&](IString name, Ref node) {
//if (eliminationLimit == 0) return;
//eliminationLimit--;
//printErr('elim!!!!! ' + name);
// yes, eliminate!
varsToRemove[name] = 2; // both assign and var definitions can have other vars we must clean up
assert(tracked.has(name));
Tracking& info = tracked[name];
Ref defNode = info.defNode;
assert(!!defNode);
if (!sideEffectFree.has(name)) {
assert(defNode[0] != VAR);
// assign
Ref value = defNode[3];
// wipe out the assign
safeCopy(defNode, makeEmpty());
// replace this node in-place
safeCopy(node, value);
} else {
// This has no side effects and no uses, empty it out in-place
safeCopy(node, makeEmpty());
}
tracked.erase(name);
};
traversePre(func, [&](Ref block) {
// Look for statements, including while-switch pattern
Ref stats = getStatements(block);
if (!stats && (block[0] == WHILE && block[2][0] == SWITCH)) {
stats = &(makeArray(1)->push_back(block[2]));
}
if (!stats) return;
tracked.clear();
for (size_t i = 0; i < stats->size(); i++) {
Ref node = deStat(stats[i]);
Ref type = node[0];
if (type == RETURN && i+1 < stats->size()) {
stats->setSize(i+1); // remove any code after a return
}
// Check for things that affect elimination
if (ELIMINATION_SAFE_NODES.has(type)) {
#ifdef PROFILING
tstmtelim += clock() - start;
start = clock();
#endif
scan(node);
#ifdef PROFILING
tstmtscan += clock() - start;
start = clock();
#endif
} else if (type == VAR) {
continue; // asm normalisation has reduced 'var' to just the names
} else {
tracked.clear(); // not a var or assign, break all potential elimination so far
}
}
});
#ifdef PROFILING
tstmtelim += clock() - start;
start = clock();
#endif
StringIntMap seenUses;
StringStringMap helperReplacements; // for looper-helper optimization
// clean up vars, and loop variable elimination
traversePrePost(func, [&](Ref node) {
// pre
Ref type = node[0];
/*if (type == VAR) {
node[1] = node[1].filter(function(pair) { return !varsToRemove[pair[0]] });
if (node[1]->size() == 0) {
// wipe out an empty |var;|
node[0] = TOPLEVEL;
node[1] = [];
}
} else */
if (type == ASSIGN && node[1]->isBool(true) && node[2][0] == NAME && node[3][0] == NAME && node[2][1] == node[3][1]) {
// elimination led to X = X, which we can just remove
safeCopy(node, makeEmpty());
}
}, [&](Ref node) {
// post
Ref type = node[0];
if (type == NAME) {
IString name = node[1]->getIString();
if (helperReplacements.has(name)) {
node[1]->setString(helperReplacements[name]);
return; // no need to track this anymore, we can't loop-optimize more than once
}
// track how many uses we saw. we need to know when a variable is no longer used (hence we run this in the post)
seenUses[name]++;
} else if (type == WHILE) {
// try to remove loop helper variables specifically
Ref stats = node[2][1];
Ref last = stats->back();
if (!!last && last[0] == IF && last[2][0] == BLOCK && !!last[3] && last[3][0] == BLOCK) {
Ref ifTrue = last[2];
Ref ifFalse = last[3];
clearEmptyNodes(ifTrue[1]);
clearEmptyNodes(ifFalse[1]);
bool flip = false;
if (ifFalse[1]->size() > 0 && !!ifFalse[1][0] && !!ifFalse[1]->back() && ifFalse[1]->back()[0] == BREAK) { // canonicalize break in the if-true
Ref temp = ifFalse;
ifFalse = ifTrue;
ifTrue = temp;
flip = true;
}
if (ifTrue[1]->size() > 0 && !!ifTrue[1][0] && !!ifTrue[1]->back() && ifTrue[1]->back()[0] == BREAK) {
Ref assigns = ifFalse[1];
clearEmptyNodes(assigns);
std::vector<IString> loopers, helpers;
for (size_t i = 0; i < assigns->size(); i++) {
if (assigns[i][0] == STAT && assigns[i][1][0] == ASSIGN) {
Ref assign = assigns[i][1];
if (assign[1]->isBool(true) && assign[2][0] == NAME && assign[3][0] == NAME) {
IString looper = assign[2][1]->getIString();
IString helper = assign[3][1]->getIString();
if (definitions[helper] == 1 && seenUses[looper] == namings[looper] &&
!helperReplacements.has(helper) && !helperReplacements.has(looper)) {
loopers.push_back(looper);
helpers.push_back(helper);
}
}
}
}
// remove loop vars that are used in the rest of the else
for (size_t i = 0; i < assigns->size(); i++) {
if (assigns[i][0] == STAT && assigns[i][1][0] == ASSIGN) {
Ref assign = assigns[i][1];
if (!(assign[1]->isBool(true) && assign[2][0] == NAME && assign[3][0] == NAME) || indexOf(loopers, assign[2][1]->getIString()) < 0) {
// this is not one of the loop assigns
traversePre(assign, [&](Ref node) {
if (node[0] == NAME) {
int index = indexOf(loopers, node[1]->getIString());
if (index < 0) index = indexOf(helpers, node[1]->getIString());
if (index >= 0) {
loopers.erase(loopers.begin() + index);
helpers.erase(helpers.begin() + index);
}
}
});
}
}
}
// remove loop vars that are used in the if
traversePre(ifTrue, [&](Ref node) {
if (node[0] == NAME) {
int index = indexOf(loopers, node[1]->getIString());
if (index < 0) index = indexOf(helpers, node[1]->getIString());
if (index >= 0) {
loopers.erase(loopers.begin() + index);
helpers.erase(helpers.begin() + index);
}
}
});
if (loopers.size() == 0) return;
for (size_t l = 0; l < loopers.size(); l++) {
IString looper = loopers[l];
IString helper = helpers[l];
// the remaining issue is whether loopers are used after the assignment to helper and before the last line (where we assign to it)
int found = -1;
for (int i = (int)stats->size()-2; i >= 0; i--) {
Ref curr = stats[i];
if (curr[0] == STAT && curr[1][0] == ASSIGN) {
Ref currAssign = curr[1];
if (currAssign[1]->isBool(true) && currAssign[2][0] == NAME) {
IString to = currAssign[2][1]->getIString();
if (to == helper) {
found = i;
break;
}
}
}
}
if (found < 0) return;
// if a loop variable is used after we assigned to the helper, we must save its value and use that.
// (note that this can happen due to elimination, if we eliminate an expression containing the
// loop var far down, past the assignment!)
// first, see if the looper and helpers overlap. Note that we check for this looper, compared to
// *ALL* the helpers. Helpers will be replaced by loopers as we eliminate them, potentially
// causing conflicts, so any helper is a concern.
int firstLooperUsage = -1;
int lastLooperUsage = -1;
int firstHelperUsage = -1;
for (int i = found+1; i < (int)stats->size(); i++) {
Ref curr = i < (int)stats->size()-1 ? stats[i] : last[1]; // on the last line, just look in the condition
traversePre(curr, [&](Ref node) {
if (node[0] == NAME) {
if (node[1] == looper) {
if (firstLooperUsage < 0) firstLooperUsage = i;
lastLooperUsage = i;
} else if (indexOf(helpers, node[1]->getIString()) >= 0) {
if (firstHelperUsage < 0) firstHelperUsage = i;
}
}
});
}
if (firstLooperUsage >= 0) {
// the looper is used, we cannot simply merge the two variables
if ((firstHelperUsage < 0 || firstHelperUsage > lastLooperUsage) && lastLooperUsage+1 < (int)stats->size() && triviallySafeToMove(stats[found], asmData) &&
seenUses[helper] == namings[helper]) {
// the helper is not used, or it is used after the last use of the looper, so they do not overlap,
// and the last looper usage is not on the last line (where we could not append after it), and the
// helper is not used outside of the loop.
// just move the looper definition to after the looper's last use
stats->insert(lastLooperUsage+1, stats[found]);
stats->splice(found, 1);
} else {
// they overlap, we can still proceed with the loop optimization, but we must introduce a
// loop temp helper variable
IString temp(strdupe((std::string(looper.c_str()) + "$looptemp").c_str()));
assert(!asmData.isLocal(temp));
for (int i = firstLooperUsage; i <= lastLooperUsage; i++) {
Ref curr = i < (int)stats->size()-1 ? stats[i] : last[1]; // on the last line, just look in the condition
std::function<bool (Ref)> looperToLooptemp = [&](Ref node) {
if (node[0] == NAME) {
if (node[1] == looper) {
node[1]->setString(temp);
}
} else if (node[0] == ASSIGN && node[2][0] == NAME) {
// do not traverse the assignment target, phi assignments to the loop variable must remain
traversePrePostConditional(node[3], looperToLooptemp, [](Ref node){});
return false;
}
return true;
};
traversePrePostConditional(curr, looperToLooptemp, [](Ref node){});
}
asmData.addVar(temp, asmData.getType(looper));
stats->insert(found, make1(STAT, make3(ASSIGN, makeBool(true), makeName(temp), makeName(looper))));
}
}
}
for (size_t l = 0; l < helpers.size(); l++) {
for (size_t k = 0; k < helpers.size(); k++) {
if (l != k && helpers[l] == helpers[k]) return; // it is complicated to handle a shared helper, abort
}
}
// hurrah! this is safe to do
for (size_t l = 0; l < loopers.size(); l++) {
IString looper = loopers[l];
IString helper = helpers[l];
varsToRemove[helper] = 2;
traversePre(node, [&](Ref node) { // replace all appearances of helper with looper
if (node[0] == NAME && node[1] == helper) node[1]->setString(looper);
});
helperReplacements[helper] = looper; // replace all future appearances of helper with looper
helperReplacements[looper] = looper; // avoid any further attempts to optimize looper in this manner (seenUses is wrong anyhow, too)
}
// simplify the if. we remove the if branch, leaving only the else
if (flip) {
last[1] = simplifyNotCompsDirect(make2(UNARY_PREFIX, L_NOT, last[1]));
Ref temp = last[2];
last[2] = last[3];
last[3] = temp;
}
if (loopers.size() == assigns->size()) {
last->pop_back();
} else {
Ref elseStats = getStatements(last[3]);
for (size_t i = 0; i < elseStats->size(); i++) {
Ref stat = deStat(elseStats[i]);
if (stat[0] == ASSIGN && stat[2][0] == NAME) {
if (indexOf(loopers, stat[2][1]->getIString()) >= 0) {
elseStats[i] = makeEmpty();
}
}
}
}
}
}
}
});
#ifdef PROFILING
tcleanvars += clock() - start;
start = clock();
#endif
for (auto v : varsToRemove) {
if (v.second == 2 && asmData.isVar(v.first)) asmData.deleteVar(v.first);
}
asmData.denormalize();
#ifdef PROFILING
treconstruct += clock() - start;
start = clock();
#endif
});
removeAllEmptySubNodes(ast);
#ifdef PROFILING
errv(" EL stages: a:%li fe:%li vc:%li se:%li (ss:%li) cv:%li r:%li",
tasmdata, tfnexamine, tvarcheck, tstmtelim, tstmtscan, tcleanvars, treconstruct);
#endif
}
void eliminateMemSafe(Ref ast) {
eliminate(ast, true);
}
void simplifyExpressions(Ref ast) {
// Simplify common expressions used to perform integer conversion operations
// in cases where no conversion is needed.
auto simplifyIntegerConversions = [](Ref ast) {
traversePre(ast, [](Ref node) {
Ref type = node[0];
if (type == BINARY && node[1] == RSHIFT && node[3][0] == NUM &&
node[2][0] == BINARY && node[2][1] == LSHIFT && node[2][3][0] == NUM && node[3][1]->getNumber() == node[2][3][1]->getNumber()) {
// Transform (x&A)<<B>>B to X&A.
Ref innerNode = node[2][2];
double shifts = node[3][1]->getNumber();
if (innerNode[0] == BINARY && innerNode[1] == AND && innerNode[3][0] == NUM) {
double mask = innerNode[3][1]->getNumber();
if (isInteger32(mask) && isInteger32(shifts) && ((jsD2I(mask) << jsD2I(shifts)) >> jsD2I(shifts)) == jsD2I(mask)) {
safeCopy(node, innerNode);
return;
}
}
} else if (type == BINARY && BITWISE.has(node[1])) {
for (int i = 2; i <= 3; i++) {
Ref subNode = node[i];
if (subNode[0] == BINARY && subNode[1] == AND && subNode[3][0] == NUM && subNode[3][1]->getNumber() == 1) {
// Rewrite (X < Y) & 1 to X < Y , when it is going into a bitwise operator. We could
// remove even more (just replace &1 with |0, then subsequent passes could remove the |0)
// but v8 issue #2513 means the code would then run very slowly in chrome.
Ref input = subNode[2];
if (input[0] == BINARY && COMPARE_OPS.has(input[1])) {
safeCopy(node[i], input);
}
}
}
}
});
};
// When there is a bunch of math like (((8+5)|0)+12)|0, only the external |0 is needed, one correction is enough.
// At each node, ((X|0)+Y)|0 can be transformed into (X+Y): The inner corrections are not needed
// TODO: Is the same is true for 0xff, 0xffff?
// Likewise, if we have |0 inside a block that will be >>'d, then the |0 is unnecessary because some
// 'useful' mathops already |0 anyhow.
auto simplifyOps = [](Ref ast) {
auto removeMultipleOrZero = [&ast] {
bool rerun = true;
while (rerun) {
rerun = false;
std::vector<int> stack;
std::function<void (Ref)> process = [&stack, &rerun, &process, &ast](Ref node) {
Ref type = node[0];
if (type == BINARY && node[1] == OR) {
if (node[2][0] == NUM && node[3][0] == NUM) {
node[2][1]->setNumber(jsD2I(node[2][1]->getNumber()) | jsD2I(node[3][1]->getNumber()));
stack.push_back(0);
safeCopy(node, node[2]);
return;
}
bool go = false;
if (node[2][0] == NUM && node[2][1]->getNumber() == 0) {
// canonicalize order
Ref temp = node[3];
node[3] = node[2];
node[2] = temp;
go = true;
} else if (node[3][0] == NUM && node[3][1]->getNumber() == 0) {
go = true;
}
if (!go) {
stack.push_back(1);
return;
}
// We might be able to remove this correction
for (int i = stack.size()-1; i >= 0; i--) {
if (stack[i] >= 1) {
if (stack.back() < 2 && node[2][0] == CALL) break; // we can only remove multiple |0s on these
if (stack.back() < 1 && (COERCION_REQUIRING_OPS.has(node[2][0]) ||
(node[2][0] == BINARY && COERCION_REQUIRING_BINARIES.has(node[2][1])))) break; // we can remove |0 or >>2
// we will replace ourselves with the non-zero side. Recursively process that node.
Ref result = node[2][0] == NUM && node[2][1]->getNumber() == 0 ? node[3] : node[2], other;
// replace node in-place
safeCopy(node, result);
rerun = true;
process(result);
return;
} else if (stack[i] == -1) {
break; // Too bad, we can't
}
}
stack.push_back(2); // From here on up, no need for this kind of correction, it's done at the top
// (Add this at the end, so it is only added if we did not remove it)
} else if (type == BINARY && USEFUL_BINARY_OPS.has(node[1])) {
stack.push_back(1);
} else if ((type == BINARY && SAFE_BINARY_OPS.has(node[1])) || type == NUM || type == NAME) {
stack.push_back(0); // This node is safe in that it does not interfere with this optimization
} else if (type == UNARY_PREFIX && node[1] == B_NOT) {
stack.push_back(1);
} else {
stack.push_back(-1); // This node is dangerous! Give up if you see this before you see '1'
}
};
traversePrePost(ast, process, [&stack](Ref node) {
assert(!stack.empty());
stack.pop_back();
});
}
};
removeMultipleOrZero();
// & and heap-related optimizations
bool hasTempDoublePtr = false, rerunOrZeroPass = false;
traversePrePostConditional(ast, [](Ref node) {
// Detect trees which should not
// be simplified.
if (node[0] == SUB && node[1][0] == NAME && isFunctionTable(node[1][1])) {
return false; // do not traverse subchildren here, we should not collapse 55 & 126.
}
return true;
}, [&hasTempDoublePtr, &rerunOrZeroPass](Ref node) {
// Simplifications are done now so
// that we simplify a node's operands before the node itself. This allows
// optimizations to cascade.
Ref type = node[0];
if (type == NAME) {
if (node[1] == TEMP_DOUBLE_PTR) hasTempDoublePtr = true;
} else if (type == BINARY && node[1] == AND && node[3][0] == NUM) {
if (node[2][0] == NUM) {
safeCopy(node, makeNum(jsD2I(node[2][1]->getNumber()) & jsD2I(node[3][1]->getNumber())));
return;
}
Ref input = node[2];
double amount = node[3][1]->getNumber();
if (input[0] == BINARY && input[1] == AND && input[3][0] == NUM) {
// Collapse X & 255 & 1
node[3][1]->setNumber(jsD2I(amount) & jsD2I(input[3][1]->getNumber()));
node[2] = input[2];
} else if (input[0] == SUB && input[1][0] == NAME) {
// HEAP8[..] & 255 => HEAPU8[..]
HeapInfo hi = parseHeap(input[1][1]->getCString());
if (hi.valid) {
if (isInteger32(amount) && amount == powl(2, hi.bits)-1) {
if (!hi.unsign) {
input[1][1]->setString(getHeapStr(hi.bits, true)); // make unsigned
}
// we cannot return HEAPU8 without a coercion, but at least we do HEAP8 & 255 => HEAPU8 | 0
node[1]->setString(OR);
node[3][1]->setNumber(0);
return;
}
}
} else if (input[0] == BINARY && input[1] == RSHIFT &&
input[2][0] == BINARY && input[2][1] == LSHIFT &&
input[2][3][0] == NUM && input[3][0] == NUM &&
input[2][3][1]->getInteger() == input[3][1]->getInteger() &&
(~(0xFFFFFFFFu >> input[3][1]->getInteger()) & jsD2I(amount)) == 0) {
// x << 24 >> 24 & 255 => x & 255
return safeCopy(node, make3(BINARY, AND, input[2][2], node[3]));
}
} else if (type == BINARY && node[1] == XOR) {
// LLVM represents bitwise not as xor with -1. Translate it back to an actual bitwise not.
if (node[3][0] == UNARY_PREFIX && node[3][1] == MINUS && node[3][2][0] == NUM &&
node[3][2][1]->getNumber() == 1 &&
!(node[2][0] == UNARY_PREFIX && node[2][1] == B_NOT)) { // avoid creating ~~~ which is confusing for asm given the role of ~~
safeCopy(node, make2(UNARY_PREFIX, B_NOT, node[2]));
return;
}
} else if (type == BINARY && node[1] == RSHIFT && node[3][0] == NUM &&
node[2][0] == BINARY && node[2][1] == LSHIFT && node[2][3][0] == NUM &&
node[2][2][0] == SUB && node[2][2][1][0] == NAME) {
// collapse HEAPU?8[..] << 24 >> 24 etc. into HEAP8[..] | 0
double amount = node[3][1]->getNumber();
if (amount == node[2][3][1]->getNumber()) {
HeapInfo hi = parseHeap(node[2][2][1][1]->getCString());
if (hi.valid && hi.bits == 32 - amount) {
node[2][2][1][1]->setString(getHeapStr(hi.bits, false));
node[1]->setString(OR);
node[2] = node[2][2];
node[3][1]->setNumber(0);
rerunOrZeroPass = true;
return;
}
}
} else if (type == ASSIGN) {
// optimizations for assigning into HEAP32 specifically
if (node[1]->isBool(true) && node[2][0] == SUB && node[2][1][0] == NAME) {
if (node[2][1][1] == HEAP32) {
// HEAP32[..] = x | 0 does not need the | 0 (unless it is a mandatory |0 of a call)
if (node[3][0] == BINARY && node[3][1] == OR) {
if (node[3][2][0] == NUM && node[3][2][1]->getNumber() == 0 && node[3][3][0] != CALL) {
node[3] = node[3][3];
} else if (node[3][3][0] == NUM && node[3][3][1]->getNumber() == 0 && node[3][2][0] != CALL) {
node[3] = node[3][2];
}
}
} else if (node[2][1][1] == HEAP8) {
// HEAP8[..] = x & 0xff does not need the & 0xff
if (node[3][0] == BINARY && node[3][1] == AND && node[3][3][0] == NUM && node[3][3][1]->getNumber() == 0xff) {
node[3] = node[3][2];
}
} else if (node[2][1][1] == HEAP16) {
// HEAP16[..] = x & 0xffff does not need the & 0xffff
if (node[3][0] == BINARY && node[3][1] == AND && node[3][3][0] == NUM && node[3][3][1]->getNumber() == 0xffff) {
node[3] = node[3][2];
}
}
}
Ref value = node[3];
if (value[0] == BINARY && value[1] == OR) {
// canonicalize order of |0 to end
if (value[2][0] == NUM && value[2][1]->getNumber() == 0) {
Ref temp = value[2];
value[2] = value[3];
value[3] = temp;
}
// if a seq ends in an |0, remove an external |0
// note that it is only safe to do this in assigns, like we are doing here (return (x, y|0); is not valid)
if (value[2][0] == SEQ && value[2][2][0] == BINARY && USEFUL_BINARY_OPS.has(value[2][2][1])) {
node[3] = value[2];
}
}
} else if (type == BINARY && node[1] == RSHIFT && node[2][0] == NUM && node[3][0] == NUM) {
// optimize num >> num, in asm we need this since we do not optimize shifts in asm.js
node[0]->setString(NUM);
node[1]->setNumber(jsD2I(node[2][1]->getNumber()) >> jsD2I(node[3][1]->getNumber()));
node->setSize(2);
return;
} else if (type == BINARY && node[1] == PLUS) {
// The most common mathop is addition, e.g. in getelementptr done repeatedly. We can join all of those,
// by doing (num+num) ==> newnum.
if (node[2][0] == NUM && node[3][0] == NUM) {
node[2][1]->setNumber(jsD2I(node[2][1]->getNumber()) + jsD2I(node[3][1]->getNumber()));
safeCopy(node, node[2]);
return;
}
}
});
if (rerunOrZeroPass) removeMultipleOrZero();
if (hasTempDoublePtr) {
AsmData asmData(ast);
traversePre(ast, [](Ref node) {
Ref type = node[0];
if (type == ASSIGN) {
if (node[1]->isBool(true) && node[2][0] == SUB && node[2][1][0] == NAME && node[2][1][1] == HEAP32) {
// remove bitcasts that are now obviously pointless, e.g.
// HEAP32[$45 >> 2] = HEAPF32[tempDoublePtr >> 2] = ($14 < $28 ? $14 : $28) - $42, HEAP32[tempDoublePtr >> 2] | 0;
Ref value = node[3];
if (value[0] == SEQ && value[1][0] == ASSIGN && value[1][2][0] == SUB && value[1][2][1][0] == NAME && value[1][2][1][1] == HEAPF32 &&
value[1][2][2][0] == BINARY && value[1][2][2][2][0] == NAME && value[1][2][2][2][1] == TEMP_DOUBLE_PTR) {
// transform to HEAPF32[$45 >> 2] = ($14 < $28 ? $14 : $28) - $42;
node[2][1][1]->setString(HEAPF32);
node[3] = value[1][3];
}
}
} else if (type == SEQ) {
// (HEAP32[tempDoublePtr >> 2] = HEAP32[$37 >> 2], +HEAPF32[tempDoublePtr >> 2])
// ==>
// +HEAPF32[$37 >> 2]
if (node[0] == SEQ && node[1][0] == ASSIGN && node[1][2][0] == SUB && node[1][2][1][0] == NAME &&
(node[1][2][1][1] == HEAP32 || node[1][2][1][1] == HEAPF32) &&
node[1][2][2][0] == BINARY && node[1][2][2][2][0] == NAME && node[1][2][2][2][1] == TEMP_DOUBLE_PTR &&
node[1][3][0] == SUB && node[1][3][1][0] == NAME && (node[1][3][1][1] == HEAP32 || node[1][3][1][1] == HEAPF32) &&
node[2][0] != SEQ) { // avoid (x, y, z) which can be used for tempDoublePtr on doubles for alignment fixes
if (node[1][2][1][1] == HEAP32) {
node[1][3][1][1]->setString(HEAPF32);
safeCopy(node, makeAsmCoercion(node[1][3], detectType(node[2])));
return;
} else {
node[1][3][1][1]->setString(HEAP32);
safeCopy(node, make3(BINARY, OR, node[1][3], makeNum(0)));
return;
}
}
}
});
// finally, wipe out remaining ones by finding cases where all assignments to X are bitcasts, and all uses are writes to
// the other heap type, then eliminate the bitcast
struct BitcastData {
int define_HEAP32, define_HEAPF32, use_HEAP32, use_HEAPF32, namings;
bool ok;
std::vector<Ref> defines, uses;
BitcastData() : define_HEAP32(0), define_HEAPF32(0), use_HEAP32(0), use_HEAPF32(0), namings(0), ok(false) {}
};
std::unordered_map<IString, BitcastData> bitcastVars;
traversePre(ast, [&bitcastVars](Ref node) {
if (node[0] == ASSIGN && node[1]->isBool(true) && node[2][0] == NAME) {
Ref value = node[3];
if (value[0] == SEQ && value[1][0] == ASSIGN && value[1][2][0] == SUB && value[1][2][1][0] == NAME &&
(value[1][2][1][1] == HEAP32 || value[1][2][1][1] == HEAPF32) &&
value[1][2][2][0] == BINARY && value[1][2][2][2][0] == NAME && value[1][2][2][2][1] == TEMP_DOUBLE_PTR) {
IString name = node[2][1]->getIString();
IString heap = value[1][2][1][1]->getIString();
if (heap == HEAP32) {
bitcastVars[name].define_HEAP32++;
} else {
assert(heap == HEAPF32);
bitcastVars[name].define_HEAPF32++;
}
bitcastVars[name].defines.push_back(node);
bitcastVars[name].ok = true;
}
}
});
traversePre(ast, [&bitcastVars](Ref node) {
Ref type = node[0];
if (type == NAME && bitcastVars[node[1]->getCString()].ok) {
bitcastVars[node[1]->getCString()].namings++;
} else if (type == ASSIGN && node[1]->isBool(true)) {
Ref value = node[3];
if (value[0] == NAME) {
IString name = value[1]->getIString();
if (bitcastVars[name].ok) {
Ref target = node[2];
if (target[0] == SUB && target[1][0] == NAME && (target[1][1] == HEAP32 || target[1][1] == HEAPF32)) {
if (target[1][1] == HEAP32) {
bitcastVars[name].use_HEAP32++;
} else {
bitcastVars[name].use_HEAPF32++;
}
bitcastVars[name].uses.push_back(node);
}
}
}
}
});
for (auto iter : bitcastVars) {
const IString& v = iter.first;
BitcastData& info = iter.second;
// good variables define only one type, use only one type, have definitions and uses, and define as a different type than they use
if (info.define_HEAP32*info.define_HEAPF32 == 0 && info.use_HEAP32*info.use_HEAPF32 == 0 &&
info.define_HEAP32+info.define_HEAPF32 > 0 && info.use_HEAP32+info.use_HEAPF32 > 0 &&
info.define_HEAP32*info.use_HEAP32 == 0 && info.define_HEAPF32*info.use_HEAPF32 == 0 &&
asmData.isLocal(v.c_str()) && info.namings == info.define_HEAP32+info.define_HEAPF32+info.use_HEAP32+info.use_HEAPF32) {
IString& correct = info.use_HEAP32 ? HEAPF32 : HEAP32;
for (auto define : info.defines) {
define[3] = define[3][1][3];
if (correct == HEAP32) {
define[3] = make3(BINARY, OR, define[3], makeNum(0));
} else {
assert(correct == HEAPF32);
define[3] = makeAsmCoercion(define[3], preciseF32 ? ASM_FLOAT : ASM_DOUBLE);
}
// do we want a simplifybitops on the new values here?
}
for (auto use : info.uses) {
use[2][1][1]->setString(correct.c_str());
}
AsmType correctType;
switch(asmData.getType(v.c_str())) {
case ASM_INT: correctType = preciseF32 ? ASM_FLOAT : ASM_DOUBLE; break;
case ASM_FLOAT: case ASM_DOUBLE: correctType = ASM_INT; break;
default: assert(0);
}
asmData.setType(v.c_str(), correctType);
}
}
asmData.denormalize();
}
};
std::function<bool (Ref)> emitsBoolean = [&emitsBoolean](Ref node) {
Ref type = node[0];
if (type == NUM) {
return node[1]->getNumber() == 0 || node[1]->getNumber() == 1;
}
if (type == BINARY) return COMPARE_OPS.has(node[1]);
if (type == UNARY_PREFIX) return node[1] == L_NOT;
if (type == CONDITIONAL) return emitsBoolean(node[2]) && emitsBoolean(node[3]);
return false;
};
// expensive | expensive can be turned into expensive ? 1 : expensive, and
// expensive | cheap can be turned into cheap ? 1 : expensive,
// so that we can avoid the expensive computation, if it has no side effects.
auto conditionalize = [&emitsBoolean](Ref ast) {
traversePre(ast, [&emitsBoolean](Ref node) {
const int MIN_COST = 7;
if (node[0] == BINARY && (node[1] == OR || node[1] == AND) && node[3][0] != NUM && node[2][0] != NUM) {
// logical operator on two non-numerical values
Ref left = node[2];
Ref right = node[3];
if (!emitsBoolean(left) || !emitsBoolean(right)) return;
bool leftEffects = hasSideEffects(left);
bool rightEffects = hasSideEffects(right);
if (leftEffects && rightEffects) return; // both must execute
// canonicalize with side effects, if any, happening on the left
if (rightEffects) {
if (measureCost(left) < MIN_COST) return; // avoidable code is too cheap
Ref temp = left;
left = right;
right = temp;
} else if (leftEffects) {
if (measureCost(right) < MIN_COST) return; // avoidable code is too cheap
} else {
// no side effects, reorder based on cost estimation
int leftCost = measureCost(left);
int rightCost = measureCost(right);
if (std::max(leftCost, rightCost) < MIN_COST) return; // avoidable code is too cheap
// canonicalize with expensive code on the right
if (leftCost > rightCost) {
Ref temp = left;
left = right;
right = temp;
}
}
// worth it, perform conditionalization
Ref ret;
if (node[1] == OR) {
ret = make3(CONDITIONAL, left, makeNum(1), right);
} else { // &
ret = make3(CONDITIONAL, left, right, makeNum(0));
}
if (left[0] == UNARY_PREFIX && left[1] == L_NOT) {
ret[1] = flipCondition(left);
Ref temp = ret[2];
ret[2] = ret[3];
ret[3] = temp;
}
safeCopy(node, ret);
return;
}
});
};
auto simplifyNotZero = [](Ref ast) {
traversePre(ast, [](Ref node) {
if (BOOLEAN_RECEIVERS.has(node[0])) {
auto boolean = node[1];
if (boolean[0] == BINARY && boolean[1] == NE && boolean[3][0] == NUM && boolean[3][1]->getNumber() == 0) {
node[1] = boolean[2];
}
}
});
};
traverseFunctions(ast, [&](Ref func) {
simplifyIntegerConversions(func);
simplifyOps(func);
traversePre(func, [](Ref node) {
Ref ret = simplifyNotCompsDirect(node);
if (ret.get() != node.get()) { // if we received a different pointer in return, then we need to copy the new value
safeCopy(node, ret);
}
});
conditionalize(func);
simplifyNotZero(func);
});
}
void simplifyIfs(Ref ast) {
traverseFunctions(ast, [](Ref func) {
bool simplifiedAnElse = false;
traversePre(func, [&simplifiedAnElse](Ref node) {
// simplify if (x) { if (y) { .. } } to if (x ? y : 0) { .. }
if (node[0] == IF) {
Ref body = node[2];
// recurse to handle chains
while (body[0] == BLOCK) {
Ref stats = body[1];
if (stats->size() == 0) break;
Ref other = stats->back();
if (other[0] != IF) {
// our if block does not end with an if. perhaps if have an else we can flip
if (node->size() > 3 && !!node[3] && node[3][0] == BLOCK) {
stats = node[3][1];
if (stats->size() == 0) break;
other = stats->back();
if (other[0] == IF) {
// flip node
node[1] = flipCondition(node[1]);
node[2] = node[3];
node[3] = body;
body = node[2];
} else break;
} else break;
}
// we can handle elses, but must be fully identical
if (!!node[3] || !!other[3]) {
if (!node[3]) break;
if (!node[3]->deepCompare(other[3])) {
// the elses are different, but perhaps if we flipped a condition we can do better
if (node[3]->deepCompare(other[2])) {
// flip other. note that other may not have had an else! add one if so; we will eliminate such things later
if (!other[3]) other[3] = makeBlock();
other[1] = flipCondition(other[1]);
Ref temp = other[2];
other[2] = other[3];
other[3] = temp;
} else break;
}
}
if (stats->size() > 1) {
// try to commaify - turn everything between the ifs into a comma operator inside the second if
bool ok = true;
for (size_t i = 0; i+1 < stats->size(); i++) {
Ref curr = deStat(stats[i]);
if (!commable(curr)) ok = false;
}
if (!ok) break;
for (int i = stats->size()-2; i >= 0; i--) {
Ref curr = deStat(stats[i]);
other[1] = make2(SEQ, curr, other[1]);
}
Ref temp = makeArray(1);
temp->push_back(other);
stats = body[1] = temp;
}
if (stats->size() != 1) break;
if (!!node[3]) simplifiedAnElse = true;
node[1] = make3(CONDITIONAL, node[1], other[1], makeNum(0));
body = node[2] = other[2];
}
}
});
if (simplifiedAnElse) {
// there may be fusing opportunities
// we can only fuse if we remove all uses of the label. if there are
// other ones - if the label check can be reached from elsewhere -
// we must leave it
bool abort = false;
std::unordered_map<int, int> labelAssigns;
traversePre(func, [&labelAssigns, &abort](Ref node) {
if (node[0] == ASSIGN && node[2][0] == NAME && node[2][1] == LABEL) {
if (node[3][0] == NUM) {
int value = node[3][1]->getInteger();
labelAssigns[value] = labelAssigns[value] + 1;
} else {
// label is assigned a dynamic value (like from indirectbr), we cannot do anything
abort = true;
}
}
});
if (abort) return;
std::unordered_map<int, int> labelChecks;
traversePre(func, [&labelChecks, &abort](Ref node) {
if (node[0] == BINARY && node[1] == EQ && node[2][0] == BINARY && node[2][1] == OR &&
node[2][2][0] == NAME && node[2][2][1] == LABEL) {
if (node[3][0] == NUM) {
int value = node[3][1]->getInteger();
labelChecks[value] = labelChecks[value] + 1;
} else {
// label is checked vs a dynamic value (like from indirectbr), we cannot do anything
abort = true;
}
}
});
if (abort) return;
int inLoop = 0; // when in a loop, we do not emit label = 0; in the relooper as there is no need
traversePrePost(func, [&inLoop, &labelAssigns, &labelChecks](Ref node) {
if (node[0] == WHILE) inLoop++;
Ref stats = getStatements(node);
if (!!stats && stats->size() > 0) {
for (int i = 0; i < (int)stats->size()-1; i++) {
Ref pre = stats[i];
Ref post = stats[i+1];
if (pre[0] == IF && pre->size() > 3 && !!pre[3] && post[0] == IF && (post->size() <= 3 || !post[3])) {
Ref postCond = post[1];
if (postCond[0] == BINARY && postCond[1] == EQ &&
postCond[2][0] == BINARY && postCond[2][1] == OR &&
postCond[2][2][0] == NAME && postCond[2][2][1] == LABEL &&
postCond[2][3][0] == NUM && postCond[2][3][1]->getNumber() == 0 &&
postCond[3][0] == NUM) {
int postValue = postCond[3][1]->getInteger();
Ref preElse = pre[3];
if (labelAssigns[postValue] == 1 && labelChecks[postValue] == 1 && preElse[0] == BLOCK && preElse->size() >= 2 && preElse[1]->size() == 1) {
Ref preStat = preElse[1][0];
if (preStat[0] == STAT && preStat[1][0] == ASSIGN &&
preStat[1][1]->isBool(true) && preStat[1][2][0] == NAME && preStat[1][2][1] == LABEL &&
preStat[1][3][0] == NUM && preStat[1][3][1]->getNumber() == postValue) {
// Conditions match, just need to make sure the post clears label
if (post[2][0] == BLOCK && post[2]->size() >= 2 && post[2][1]->size() > 0) {
Ref postStat = post[2][1][0];
bool haveClear =
postStat[0] == STAT && postStat[1][0] == ASSIGN &&
postStat[1][1]->isBool(true) && postStat[1][2][0] == NAME && postStat[1][2][1] == LABEL &&
postStat[1][3][0] == NUM && postStat[1][3][1]->getNumber() == 0;
if (!inLoop || haveClear) {
// Everything lines up, do it
pre[3] = post[2];
if (haveClear) pre[3][1]->splice(0, 1); // remove the label clearing
stats->splice(i+1, 1); // remove the post entirely
}
}
}
}
}
}
}
}
}, [&inLoop](Ref node) {
if (node[0] == WHILE) inLoop--;
});
assert(inLoop == 0);
}
});
}
void optimizeFrounds(Ref ast) {
// collapse fround(fround(..)), which can happen due to elimination
// also emit f0 instead of fround(0) (except in returns)
int inReturn = 0;
traversePrePost(ast, [&](Ref node) {
if (node[0] == RETURN) {
inReturn++;
}
}, [&](Ref node) {
if (node[0] == RETURN) {
inReturn--;
}
if (node[0] == CALL && node[1][0] == NAME && node[1][1] == MATH_FROUND) {
Ref arg = node[2][0];
if (arg[0] == NUM) {
if (!inReturn && arg[1]->getInteger() == 0) {
safeCopy(node, makeName(F0));
}
} else if (arg[0] == CALL && arg[1][0] == NAME && arg[1][1] == MATH_FROUND) {
safeCopy(node, arg);
}
}
});
}
// Very simple 'registerization', coalescing of variables into a smaller number.
const char* getRegPrefix(AsmType type) {
switch (type) {
case ASM_INT: return "i"; break;
case ASM_DOUBLE: return "d"; break;
case ASM_FLOAT: return "f"; break;
case ASM_FLOAT32X4: return "F4"; break;
case ASM_FLOAT64X2: return "F2"; break;
case ASM_INT8X16: return "I16"; break;
case ASM_INT16X8: return "I8"; break;
case ASM_INT32X4: return "I4"; break;
case ASM_BOOL8X16: return "B16"; break;
case ASM_BOOL16X8: return "B8"; break;
case ASM_BOOL32X4: return "B4"; break;
case ASM_BOOL64X2: return "B2"; break;
case ASM_NONE: return "Z"; break;
default: assert(0); // type doesn't have a name yet
}
return nullptr;
}
IString getRegName(AsmType type, int num) {
const char* str = getRegPrefix(type);
const int size = 256;
char temp[size];
int written = sprintf(temp, "%s%d", str, num);
assert(written < size);
temp[written] = 0;
IString ret;
ret.set(temp, false);
return ret;
}
void registerize(Ref ast) {
traverseFunctions(ast, [](Ref fun) {
AsmData asmData(fun);
// Add parameters as a first (fake) var (with assignment), so they get taken into consideration
// note: params are special, they can never share a register between them (see later)
Ref fake;
if (!!fun[2] && fun[2]->size()) {
Ref assign = makeNum(0);
// TODO: will be an isEmpty here, can reuse it.
fun[3]->insert(0, make1(VAR, fun[2]->map([&assign](Ref param) {
return &(makeArray(2)->push_back(param).push_back(assign));
})));
}
// Replace all var definitions with assignments; we will add var definitions at the top after we registerize
StringSet allVars;
traversePre(fun, [&](Ref node) {
Ref type = node[0];
if (type == VAR) {
Ref vars = node[1]->filter([](Ref varr) { return varr->size() > 1; });
if (vars->size() >= 1) {
safeCopy(node, unVarify(vars));
} else {
safeCopy(node, makeEmpty());
}
} else if (type == NAME) {
allVars.insert(node[1]->getIString());
}
});
removeAllUselessSubNodes(fun); // vacuum?
StringTypeMap regTypes; // reg name -> type
auto getNewRegName = [&](int num, IString name) {
AsmType type = asmData.getType(name);
IString ret = getRegName(type, num);
assert(!allVars.has(ret) || asmData.isLocal(ret)); // register must not shadow non-local name
regTypes[ret] = type;
return ret;
};
// Find the # of uses of each variable.
// While doing so, check if all a variable's uses are dominated in a simple
// way by a simple assign, if so, then we can assign its register to it
// just for its definition to its last use, and not to the entire toplevel loop,
// we call such variables "optimizable"
StringIntMap varUses;
int level = 1;
std::unordered_map<int, StringSet> levelDominations; // level => set of dominated variables XXX vector?
StringIntMap varLevels;
StringSet possibles;
StringSet unoptimizables;
auto purgeLevel = [&]() {
// Invalidate all dominating on this level, further users make it unoptimizable
for (auto name : levelDominations[level]) {
varLevels[name] = 0;
}
levelDominations[level].clear();
level--;
};
std::function<bool (Ref node)> possibilifier = [&](Ref node) {
Ref type = node[0];
if (type == NAME) {
IString name = node[1]->getIString();
if (asmData.isLocal(name)) {
varUses[name]++;
if (possibles.has(name) && !varLevels[name]) unoptimizables.insert(name); // used outside of simple domination
}
} else if (type == ASSIGN && node[1]->isBool(true)) {
if (!!node[2] && node[2][0] == NAME) {
IString name = node[2][1]->getIString();
// if local and not yet used, this might be optimizable if we dominate
// all other uses
if (asmData.isLocal(name) && !varUses[name] && !varLevels[name]) {
possibles.insert(name);
varLevels[name] = level;
levelDominations[level].insert(name);
}
}
} else if (CONTROL_FLOW.has(type)) {
// recurse children, in the context of a loop
if (type == WHILE || type == DO) {
traversePrePostConditional(node[1], possibilifier, [](Ref node){});
level++;
traversePrePostConditional(node[2], possibilifier, [](Ref node){});
purgeLevel();
} else if (type == FOR) {
traversePrePostConditional(node[1], possibilifier, [](Ref node){});
for (int i = 2; i <= 4; i++) {
level++;
traversePrePostConditional(node[i], possibilifier, [](Ref node){});
purgeLevel();
}
} else if (type == IF) {
traversePrePostConditional(node[1], possibilifier, [](Ref node){});
level++;
traversePrePostConditional(node[2], possibilifier, [](Ref node){});
purgeLevel();
if (node->size() > 3 && !!node[3]) {
level++;
traversePrePostConditional(node[3], possibilifier, [](Ref node){});
purgeLevel();
}
} else if (type == SWITCH) {
traversePrePostConditional(node[1], possibilifier, [](Ref node){});
Ref cases = node[2];
for (size_t i = 0; i < cases->size(); i++) {
level++;
traversePrePostConditional(cases[i][1], possibilifier, [](Ref node){});
purgeLevel();
}
} else assert(0);;
return false; // prevent recursion into children, which we already did
}
return true;
};
traversePrePostConditional(fun, possibilifier, [](Ref node){});
StringSet optimizables;
for (auto possible : possibles) {
if (!unoptimizables.has(possible)) optimizables.insert(possible);
}
// Go through the function's code, assigning 'registers'.
// The only tricky bit is to keep variables locked on a register through loops,
// since they can potentially be returned to. Optimizable variables lock onto
// loops that they enter, unoptimizable variables lock in a conservative way
// into the topmost loop.
// Note that we cannot lock onto a variable in a loop if it was used and free'd
// before! (then they could overwrite us in the early part of the loop). For now
// we just use a fresh register to make sure we avoid this, but it could be
// optimized to check for safe registers (free, and not used in this loop level).
StringStringMap varRegs; // maps variables to the register they will use all their life
std::vector<StringVec> freeRegsClasses;
freeRegsClasses.resize(ASM_NONE);
int nextReg = 1;
StringVec fullNames;
fullNames.push_back(EMPTY); // names start at 1
std::vector<StringVec> loopRegs; // for each loop nesting level, the list of bound variables
int loops = 0; // 0 is toplevel, 1 is first loop, etc
StringSet activeOptimizables;
StringIntMap optimizableLoops;
StringSet paramRegs; // true if the register is used by a parameter (and so needs no def at start of function; also cannot
// be shared with another param, each needs its own)
auto decUse = [&](IString name) {
if (!varUses[name]) return false; // no uses left, or not a relevant variable
if (optimizables.has(name)) activeOptimizables.insert(name);
IString reg = varRegs[name];
assert(asmData.isLocal(name));
StringVec& freeRegs = freeRegsClasses[asmData.getType(name)];
if (!reg) {
// acquire register
if (optimizables.has(name) && freeRegs.size() > 0 &&
!(asmData.isParam(name) && paramRegs.has(freeRegs.back()))) { // do not share registers between parameters
reg = freeRegs.back();
freeRegs.pop_back();
} else {
assert(fullNames.size() == nextReg);
reg = getNewRegName(nextReg++, name);
fullNames.push_back(reg);
if (asmData.isParam(name)) paramRegs.insert(reg);
}
varRegs[name] = reg;
}
varUses[name]--;
assert(varUses[name] >= 0);
if (varUses[name] == 0) {
if (optimizables.has(name)) activeOptimizables.erase(name);
// If we are not in a loop, or we are optimizable and not bound to a loop
// (we might have been in one but left it), we can free the register now.
if (loops == 0 || (optimizables.has(name) && !optimizableLoops.has(name))) {
// free register
freeRegs.push_back(reg);
} else {
// when the relevant loop is exited, we will free the register
int relevantLoop = optimizables.has(name) ? (optimizableLoops[name] ? optimizableLoops[name] : 1) : 1;
if ((int)loopRegs.size() <= relevantLoop+1) loopRegs.resize(relevantLoop+1);
loopRegs[relevantLoop].push_back(reg);
}
}
return true;
};
traversePrePost(fun, [&](Ref node) { // XXX we rely on traversal order being the same as execution order here
Ref type = node[0];
if (type == NAME) {
IString name = node[1]->getIString();
if (decUse(name)) {
node[1]->setString(varRegs[name]);
}
} else if (LOOP.has(type)) {
loops++;
// Active optimizables lock onto this loop, if not locked onto one that encloses this one
for (auto name : activeOptimizables) {
if (!optimizableLoops[name]) {
optimizableLoops[name] = loops;
}
}
}
}, [&](Ref node) {
Ref type = node[0];
if (LOOP.has(type)) {
// Free registers that were locked to this loop
if ((int)loopRegs.size() > loops && loopRegs[loops].size() > 0) {
for (auto loopReg : loopRegs[loops]) {
freeRegsClasses[regTypes[loopReg]].push_back(loopReg);
}
loopRegs[loops].clear();
}
loops--;
}
});
if (!!fun[2] && fun[2]->size()) {
fun[2]->setSize(0); // clear params, we will fill with registers
fun[3]->splice(0, 1); // remove fake initial var
}
asmData.locals.clear();
asmData.params.clear();
asmData.vars.clear();
for (int i = 1; i < nextReg; i++) {
IString reg = fullNames[i];
AsmType type = regTypes[reg];
if (!paramRegs.has(reg)) {
asmData.addVar(reg, type);
} else {
asmData.addParam(reg, type);
fun[2]->push_back(makeString(reg));
}
}
asmData.denormalize();
});
}
// Assign variables to 'registers', coalescing them onto a smaller number of shared
// variables.
//
// This does the same job as 'registerize' above, but burns a lot more cycles trying
// to reduce the total number of register variables. Key points about the operation:
//
// * we decompose the AST into a flow graph and perform a full liveness
// analysis, to determine which variables are live at each point.
//
// * variables that are live concurrently are assigned to different registers.
//
// * variables that are linked via 'x=y' style statements are assigned the same
// register if possible, so that the redundant assignment can be removed.
// (e.g. assignments used to pass state around through loops).
//
// * any code that cannot be reached through the flow-graph is removed.
// (e.g. redundant break statements like 'break L123; break;').
//
// * any assignments that we can prove are not subsequently used are removed.
// (e.g. unnecessary assignments to the 'label' variable).
//
void registerizeHarder(Ref ast) {
#ifdef PROFILING
clock_t tasmdata = 0;
clock_t tflowgraph = 0;
clock_t tlabelfix = 0;
clock_t tbackflow = 0;
clock_t tjuncvaruniqassign = 0;
clock_t tjuncvarsort = 0;
clock_t tregassign = 0;
clock_t tblockproc = 0;
clock_t treconstruct = 0;
#endif
traverseFunctions(ast, [&](Ref fun) {
#ifdef PROFILING
clock_t start = clock();
#endif
// Do not try to process non-validating methods, like the heap replacer
bool abort = false;
traversePre(fun, [&abort](Ref node) {
if (node[0] == NEW) abort = true;
});
if (abort) return;
// Do not process the dceable helper function for wasm, which declares
// types, we need to alive for asm2wasm
if (fun[1] == DCEABLE_TYPE_DECLS) return;
AsmData asmData(fun);
#ifdef PROFILING
tasmdata += clock() - start;
start = clock();
#endif
// Utilities for allocating register variables.
// We need distinct register pools for each type of variable.
typedef std::map<int, IString> IntStringMap;
std::vector<IntStringMap> allRegsByType;
allRegsByType.resize(ASM_NONE+1);
int nextReg = 1;
auto createReg = [&](IString forName) {
// Create a new register of type suitable for the given variable name.
AsmType type = asmData.getType(forName);
IntStringMap& allRegs = allRegsByType[type];
int reg = nextReg++;
allRegs[reg] = getRegName(type, reg);
return reg;
};
// Traverse the tree in execution order and synthesize a basic flow-graph.
// It's convenient to build a kind of "dual" graph where the nodes identify
// the junctions between blocks at which control-flow may branch, and each
// basic block is an edge connecting two such junctions.
// For each junction we store:
// * set of blocks that originate at the junction
// * set of blocks that terminate at the junction
// For each block we store:
// * a single entry junction
// * a single exit junction
// * a 'use' and 'kill' set of names for the block
// * full sequence of NAME and ASSIGN nodes in the block
// * whether each such node appears as part of a larger expression
// (and therefore cannot be safely eliminated)
// * set of labels that can be used to jump to this block
struct Junction {
int id;
std::set<int> inblocks, outblocks;
IOrderedStringSet live;
Junction(int id_) : id(id_) {}
};
struct Node {
};
struct Block {
int id, entry, exit;
std::set<int> labels;
std::vector<Ref> nodes;
std::vector<bool> isexpr;
StringIntMap use;
StringSet kill;
StringStringMap link;
StringIntMap lastUseLoc;
StringIntMap firstDeadLoc;
StringIntMap firstKillLoc;
StringIntMap lastKillLoc;
Block() : id(-1), entry(-1), exit(-1) {}
};
struct ContinueBreak {
int co, br;
ContinueBreak() : co(-1), br(-1) {}
ContinueBreak(int co_, int br_) : co(co_), br(br_) {}
};
typedef std::unordered_map<IString, ContinueBreak> LabelState;
std::vector<Junction> junctions;
std::vector<Block*> blocks;
int currEntryJunction = -1;
Block* nextBasicBlock = nullptr;
int isInExpr = 0;
std::vector<LabelState> activeLabels;
activeLabels.resize(1);
IString nextLoopLabel;
const int ENTRY_JUNCTION = 0;
const int EXIT_JUNCTION = 1;
const int ENTRY_BLOCK = 0;
auto addJunction = [&]() {
// Create a new junction, without inserting it into the graph.
// This is useful for e.g. pre-allocating an exit node.
int id = junctions.size();
junctions.push_back(Junction(id));
return id;
};
std::function<int (int, bool)> joinJunction;
auto markJunction = [&](int id) {
// Mark current traversal location as a junction.
// This makes a new basic block exiting at this position.
if (id < 0) {
id = addJunction();
}
joinJunction(id, true);
return id;
};
auto setJunction = [&](int id, bool force) {
// Set the next entry junction to the given id.
// This can be used to enter at a previously-declared point.
// You can't return to a junction with no incoming blocks
// unless the 'force' parameter is specified.
assert(nextBasicBlock->nodes.size() == 0); // refusing to abandon an in-progress basic block
if (force || junctions[id].inblocks.size() > 0) {
currEntryJunction = id;
} else {
currEntryJunction = -1;
}
};
joinJunction = [&](int id, bool force) {
// Complete the pending basic block by exiting at this position.
// This can be used to exit at a previously-declared point.
if (currEntryJunction >= 0) {
assert(nextBasicBlock);
nextBasicBlock->id = blocks.size();
nextBasicBlock->entry = currEntryJunction;
nextBasicBlock->exit = id;
junctions[currEntryJunction].outblocks.insert(nextBasicBlock->id);
junctions[id].inblocks.insert(nextBasicBlock->id);
blocks.push_back(nextBasicBlock);
}
nextBasicBlock = new Block();
setJunction(id, force);
return id;
};
auto pushActiveLabels = [&](int onContinue, int onBreak) {
// Push the target junctions for continuing/breaking a loop.
// This should be called before traversing into a loop.
assert(activeLabels.size() > 0);
LabelState& prevLabels = activeLabels.back();
LabelState newLabels = prevLabels;
newLabels[EMPTY] = ContinueBreak(onContinue, onBreak);
if (!!nextLoopLabel) {
newLabels[nextLoopLabel] = ContinueBreak(onContinue, onBreak);
nextLoopLabel = EMPTY;
}
// An unlabelled CONTINUE should jump to innermost loop,
// ignoring any nested SWITCH statements.
if (onContinue < 0 && prevLabels.count(EMPTY) > 0) {
newLabels[EMPTY].co = prevLabels[EMPTY].co;
}
activeLabels.push_back(newLabels);
};
auto popActiveLabels = [&]() {
// Pop the target junctions for continuing/breaking a loop.
// This should be called after traversing into a loop.
activeLabels.pop_back();
};
auto markNonLocalJump = [&](IString type, IString label) {
// Complete a block via RETURN, BREAK or CONTINUE.
// This joins the targetted junction and then sets the current junction to null.
// Any code traversed before we get back to an existing junction is dead code.
if (type == RETURN) {
joinJunction(EXIT_JUNCTION, false);
} else {
assert(activeLabels.size() > 0);
assert(activeLabels.back().count(label) > 0); // 'jump to unknown label');
auto targets = activeLabels.back()[label];
if (type == CONTINUE) {
joinJunction(targets.co, false);
} else if (type == BREAK) {
joinJunction(targets.br, false);
} else {
assert(0); // 'unknown jump node type');
}
}
currEntryJunction = -1;
};
auto addUseNode = [&](Ref node) {
// Mark a use of the given name node in the current basic block.
assert(node[0] == NAME); // 'not a use node');
IString name = node[1]->getIString();
if (asmData.isLocal(name)) {
nextBasicBlock->nodes.push_back(node);
nextBasicBlock->isexpr.push_back(isInExpr != 0);
if (nextBasicBlock->kill.count(name) == 0) {
nextBasicBlock->use[name] = 1;
}
}
};
auto addKillNode = [&](Ref node) {
// Mark an assignment to the given name node in the current basic block.
assert(node[0] == ASSIGN); //, 'not a kill node');
assert(node[1]->isBool(true)); // 'not a kill node');
assert(node[2][0] == NAME); //, 'not a kill node');
IString name = node[2][1]->getIString();
if (asmData.isLocal(name)) {
nextBasicBlock->nodes.push_back(node);
nextBasicBlock->isexpr.push_back(isInExpr != 0);
nextBasicBlock->kill.insert(name);
}
};
std::function<Ref (Ref)> lookThroughCasts = [&](Ref node) {
// Look through value-preserving casts, like "x | 0" => "x"
if (node[0] == BINARY && node[1] == OR) {
if (node[3][0] == NUM && node[3][1]->getNumber() == 0) {
return lookThroughCasts(node[2]);
}
}
return node;
};
auto addBlockLabel = [&](Ref node) {
assert(nextBasicBlock->nodes.size() == 0); // 'cant add label to an in-progress basic block')
if (node[0] == NUM) {
nextBasicBlock->labels.insert(node[1]->getInteger());
}
};
auto isTrueNode = [&](Ref node) {
// Check if the given node is statically truthy.
return (node[0] == NUM && node[1]->getNumber() != 0);
};
auto isFalseNode = [&](Ref node) {
// Check if the given node is statically falsy.
return (node[0] == NUM && node[1]->getNumber() == 0);
};
std::function<void (Ref)> buildFlowGraph = [&](Ref node) {
// Recursive function to build up the flow-graph.
// It walks the tree in execution order, calling the above state-management
// functions at appropriate points in the traversal.
Ref type = node[0];
// Any code traversed without an active entry junction must be dead,
// as the resulting block could never be entered. Let's remove it.
if (currEntryJunction < 0 && junctions.size() > 0) {
safeCopy(node, makeEmpty());
return;
}
// Traverse each node type according to its particular control-flow semantics.
// TODO: switchify this
if (type == DEFUN) {
int jEntry = markJunction(-1);
assert(jEntry == ENTRY_JUNCTION);
int jExit = addJunction();
assert(jExit == EXIT_JUNCTION);
for (size_t i = 0; i < node[3]->size(); i++) {
buildFlowGraph(node[3][i]);
}
joinJunction(jExit, false);
} else if (type == IF) {
isInExpr++;
buildFlowGraph(node[1]);
isInExpr--;
int jEnter = markJunction(-1);
int jExit = addJunction();
if (!!node[2]) {
// Detect and mark "if (label == N) { <labelled block> }".
if (node[1][0] == BINARY && node[1][1] == EQ) {
Ref lhs = lookThroughCasts(node[1][2]);
if (lhs[0] == NAME && lhs[1] == LABEL) {
addBlockLabel(lookThroughCasts(node[1][3]));
}
}
buildFlowGraph(node[2]);
}
joinJunction(jExit, false);
setJunction(jEnter, false);
if (node->size() > 3 && !!node[3]) {
buildFlowGraph(node[3]);
}
joinJunction(jExit, false);
} else if (type == CONDITIONAL) {
isInExpr++;
// If the conditional has no side-effects, we can treat it as a single
// block, which might open up opportunities to remove it entirely.
if (!hasSideEffects(node)) {
buildFlowGraph(node[1]);
if (!!node[2]) {
buildFlowGraph(node[2]);
}
if (!!node[3]) {
buildFlowGraph(node[3]);
}
} else {
buildFlowGraph(node[1]);
int jEnter = markJunction(-1);
int jExit = addJunction();
if (!!node[2]) {
buildFlowGraph(node[2]);
}
joinJunction(jExit, false);
setJunction(jEnter, false);
if (!!node[3]) {
buildFlowGraph(node[3]);
}
joinJunction(jExit, false);
}
isInExpr--;
} else if (type == WHILE) {
// Special-case "while (1) {}" to use fewer junctions,
// since emscripten generates a lot of these.
if (isTrueNode(node[1])) {
int jLoop = markJunction(-1);
int jExit = addJunction();
pushActiveLabels(jLoop, jExit);
buildFlowGraph(node[2]);
popActiveLabels();
joinJunction(jLoop, false);
setJunction(jExit, false);
} else {
int jCond = markJunction(-1);
int jLoop = addJunction();
int jExit = addJunction();
isInExpr++;
buildFlowGraph(node[1]);
isInExpr--;
joinJunction(jLoop, false);
pushActiveLabels(jCond, jExit);
buildFlowGraph(node[2]);
popActiveLabels();
joinJunction(jCond, false);
// An empty basic-block linking condition exit to loop exit.
setJunction(jLoop, false);
joinJunction(jExit, false);
}
} else if (type == DO) {
// Special-case "do {} while (1)" and "do {} while (0)" to use
// fewer junctions, since emscripten generates a lot of these.
if (isFalseNode(node[1])) {
int jExit = addJunction();
pushActiveLabels(jExit, jExit);
buildFlowGraph(node[2]);
popActiveLabels();
joinJunction(jExit, false);
} else if (isTrueNode(node[1])) {
int jLoop = markJunction(-1);
int jExit = addJunction();
pushActiveLabels(jLoop, jExit);
buildFlowGraph(node[2]);
popActiveLabels();
joinJunction(jLoop, false);
setJunction(jExit, false);
} else {
int jLoop = markJunction(-1);
int jCond = addJunction();
int jCondExit = addJunction();
int jExit = addJunction();
pushActiveLabels(jCond, jExit);
buildFlowGraph(node[2]);
popActiveLabels();
joinJunction(jCond, false);
isInExpr++;
buildFlowGraph(node[1]);
isInExpr--;
joinJunction(jCondExit, false);
joinJunction(jLoop, false);
setJunction(jCondExit, false);
joinJunction(jExit, false);
}
} else if (type == FOR) {
int jTest = addJunction();
int jBody = addJunction();
int jStep = addJunction();
int jExit = addJunction();
buildFlowGraph(node[1]);
joinJunction(jTest, false);
isInExpr++;
buildFlowGraph(node[2]);
isInExpr--;
joinJunction(jBody, false);
pushActiveLabels(jStep, jExit);
buildFlowGraph(node[4]);
popActiveLabels();
joinJunction(jStep, false);
buildFlowGraph(node[3]);
joinJunction(jTest, false);
setJunction(jBody, false);
joinJunction(jExit, false);
} else if (type == LABEL) {
assert(BREAK_CAPTURERS.has(node[2][0])); // 'label on non-loop, non-switch statement')
nextLoopLabel = node[1]->getIString();
buildFlowGraph(node[2]);
} else if (type == SWITCH) {
// Emscripten generates switch statements of a very limited
// form: all case clauses are numeric literals, and all
// case bodies end with a (maybe implicit) break. So it's
// basically equivalent to a multi-way IF statement.
isInExpr++;
buildFlowGraph(node[1]);
isInExpr--;
Ref condition = lookThroughCasts(node[1]);
int jCheckExit = markJunction(-1);
int jExit = addJunction();
pushActiveLabels(-1, jExit);
bool hasDefault = false;
for (size_t i = 0; i < node[2]->size(); i++) {
setJunction(jCheckExit, false);
// All case clauses are either 'default' or a numeric literal.
if (!node[2][i][0]) {
hasDefault = true;
} else {
// Detect switches dispatching to labelled blocks.
if (condition[0] == NAME && condition[1] == LABEL) {
addBlockLabel(lookThroughCasts(node[2][i][0]));
}
}
for (size_t j = 0; j < node[2][i][1]->size(); j++) {
buildFlowGraph(node[2][i][1][j]);
}
// Control flow will never actually reach the end of the case body.
// If there's live code here, assume it jumps to case exit.
if (currEntryJunction >= 0 && nextBasicBlock->nodes.size() > 0) {
if (!!node[2][i][0]) {
markNonLocalJump(RETURN, EMPTY);
} else {
joinJunction(jExit, false);
}
}
}
// If there was no default case, we also need an empty block
// linking straight from the test evaluation to the exit.
if (!hasDefault) {
setJunction(jCheckExit, false);
}
joinJunction(jExit, false);
popActiveLabels();
} else if (type == RETURN) {
if (!!node[1]) {
isInExpr++;
buildFlowGraph(node[1]);
isInExpr--;
}
markNonLocalJump(type->getIString(), EMPTY);
} else if (type == BREAK || type == CONTINUE) {
markNonLocalJump(type->getIString(), !!node[1] ? node[1]->getIString() : EMPTY);
} else if (type == ASSIGN) {
isInExpr++;
buildFlowGraph(node[3]);
isInExpr--;
if (node[1]->isBool(true) && node[2][0] == NAME) {
addKillNode(node);
} else {
buildFlowGraph(node[2]);
}
} else if (type == NAME) {
addUseNode(node);
} else if (type == BLOCK || type == TOPLEVEL) {
if (!!node[1]) {
for (size_t i = 0; i < node[1]->size(); i++) {
buildFlowGraph(node[1][i]);
}
}
} else if (type == STAT) {
buildFlowGraph(node[1]);
} else if (type == UNARY_PREFIX) {
isInExpr++;
buildFlowGraph(node[2]);
isInExpr--;
} else if (type == BINARY) {
isInExpr++;
buildFlowGraph(node[2]);
buildFlowGraph(node[3]);
isInExpr--;
} else if (type == CALL) {
isInExpr++;
buildFlowGraph(node[1]);
if (!!node[2]) {
for (size_t i = 0; i < node[2]->size(); i++) {
buildFlowGraph(node[2][i]);
}
}
isInExpr--;
// If the call is statically known to throw,
// treat it as a jump to function exit.
if (!isInExpr && node[1][0] == NAME) {
if (FUNCTIONS_THAT_ALWAYS_THROW.has(node[1][1])) {
markNonLocalJump(RETURN, EMPTY);
}
}
} else if (type == SEQ || type == SUB) {
isInExpr++;
buildFlowGraph(node[1]);
buildFlowGraph(node[2]);
isInExpr--;
} else if (type == DOT || type == THROW) {
isInExpr++;
buildFlowGraph(node[1]);
isInExpr--;
} else if (type == NUM || type == STRING || type == VAR) {
// nada
} else {
assert(0); // 'unsupported node type: ' + type);
}
};
buildFlowGraph(fun);
#ifdef PROFILING
tflowgraph += clock() - start;
start = clock();
#endif
assert(junctions[ENTRY_JUNCTION].inblocks.size() == 0); // 'function entry must have no incoming blocks');
assert(junctions[EXIT_JUNCTION].outblocks.size() == 0); // 'function exit must have no outgoing blocks');
assert(blocks[ENTRY_BLOCK]->entry == ENTRY_JUNCTION); //, 'block zero must be the initial block');
// Fix up implicit jumps done by assigning to the LABEL variable.
// If a block ends with an assignment to LABEL and there's another block
// with that value of LABEL as precondition, we tweak the flow graph so
// that the former jumps straight to the later.
std::map<int, Block*> labelledBlocks;
typedef std::pair<Ref, Block*> Jump;
std::vector<Jump> labelledJumps;
for (size_t i = 0; i < blocks.size(); i++) {
Block* block = blocks[i];
// Does it have any labels as preconditions to its entry?
for (auto labelVal : block->labels) {
// If there are multiple blocks with the same label, all bets are off.
// This seems to happen sometimes for short blocks that end with a return.
// TODO: it should be safe to merge the duplicates if they're identical.
if (labelledBlocks.count(labelVal) > 0) {
labelledBlocks.clear();
labelledJumps.clear();
goto AFTER_FINDLABELLEDBLOCKS;
}
labelledBlocks[labelVal] = block;
}
// Does it assign a specific label value at exit?
if (block->kill.has(LABEL)) {
Ref finalNode = block->nodes.back();
if (finalNode[0] == ASSIGN && finalNode[2][1] == LABEL) {
// If labels are computed dynamically then all bets are off.
// This can happen due to indirect branching in llvm output.
if (finalNode[3][0] != NUM) {
labelledBlocks.clear();
labelledJumps.clear();
goto AFTER_FINDLABELLEDBLOCKS;
}
labelledJumps.push_back(Jump(finalNode[3][1], block));
} else {
// If label is assigned a non-zero value elsewhere in the block
// then all bets are off. This can happen e.g. due to outlining
// saving/restoring label to the stack.
for (size_t j = 0; j < block->nodes.size() - 1; j++) {
if (block->nodes[j][0] == ASSIGN && block->nodes[j][2][1] == LABEL) {
if (block->nodes[j][3][0] != NUM || block->nodes[j][3][1]->getNumber() != 0) {
labelledBlocks.clear();
labelledJumps.clear();
goto AFTER_FINDLABELLEDBLOCKS;
}
}
}
}
}
}
AFTER_FINDLABELLEDBLOCKS:
for (auto labelVal : labelledBlocks) {
Block* block = labelVal.second;
// Disconnect it from the graph, and create a
// new junction for jumps targetting this label.
junctions[block->entry].outblocks.erase(block->id);
block->entry = addJunction();
junctions[block->entry].outblocks.insert(block->id);
// Add a fake use of LABEL to keep it alive in predecessor.
block->use[LABEL] = 1;
block->nodes.insert(block->nodes.begin(), makeName(LABEL));
block->isexpr.insert(block->isexpr.begin(), 1);
}
for (size_t i = 0; i < labelledJumps.size(); i++) {
auto labelVal = labelledJumps[i].first;
auto block = labelledJumps[i].second;
Block* targetBlock = labelledBlocks[labelVal->getInteger()];
if (targetBlock) {
// Redirect its exit to entry of the target block.
junctions[block->exit].inblocks.erase(block->id);
block->exit = targetBlock->entry;
junctions[block->exit].inblocks.insert(block->id);
}
}
#ifdef PROFILING
tlabelfix += clock() - start;
start = clock();
#endif
// Do a backwards data-flow analysis to determine the set of live
// variables at each junction, and to use this information to eliminate
// any unused assignments.
// We run two nested phases. The inner phase builds the live set for each
// junction. The outer phase uses this to try to eliminate redundant
// stores in each basic block, which might in turn affect liveness info.
auto analyzeJunction = [&](Junction& junc) {
// Update the live set for this junction.
IOrderedStringSet live;
for (auto b : junc.outblocks) {
Block* block = blocks[b];
IOrderedStringSet& liveSucc = junctions[block->exit].live;
for (auto name : liveSucc) {
if (!block->kill.has(name)) {
live.insert(name);
}
}
for (auto name : block->use) {
live.insert(name.first);
}
}
junc.live = live;
};
auto analyzeBlock = [&](Block* block) {
// Update information about the behaviour of the block.
// This includes the standard 'use' and 'kill' information,
// plus a 'link' set naming values that flow through from entry
// to exit, possibly changing names via simple 'x=y' assignments.
// As we go, we eliminate assignments if the variable is not
// subsequently used.
auto live = junctions[block->exit].live;
StringIntMap use;
StringSet kill;
StringStringMap link;
StringIntMap lastUseLoc;
StringIntMap firstDeadLoc;
StringIntMap firstKillLoc;
StringIntMap lastKillLoc;
for (auto name : live) {
link[name] = name;
lastUseLoc[name] = block->nodes.size();
firstDeadLoc[name] = block->nodes.size();
}
for (int j = block->nodes.size() - 1; j >= 0 ; j--) {
Ref node = block->nodes[j];
if (node[0] == NAME) {
IString name = node[1]->getIString();
live.insert(name);
use[name] = j;
if (lastUseLoc.count(name) == 0) {
lastUseLoc[name] = j;
firstDeadLoc[name] = j;
}
} else {
IString name = node[2][1]->getIString();
// We only keep assignments if they will be subsequently used.
if (live.has(name)) {
kill.insert(name);
use.erase(name);
live.erase(name);
firstDeadLoc[name] = j;
firstKillLoc[name] = j;
if (lastUseLoc.count(name) == 0) {
lastUseLoc[name] = j;
}
if (lastKillLoc.count(name) == 0) {
lastKillLoc[name] = j;
}
// If it's an "x=y" and "y" is not live, then we can create a
// flow-through link from "y" to "x". If not then there's no
// flow-through link for "x".
if (link.has(name)) {
IString oldLink = link[name];
link.erase(name);
if (node[3][0] == NAME) {
if (asmData.isLocal(node[3][1]->getIString())) {
link[node[3][1]->getIString()] = oldLink;
}
}
}
} else {
// The result of this assignment is never used, so delete it.
// We may need to keep the RHS for its value or its side-effects.
auto removeUnusedNodes = [&](int j, int n) {
for (auto pair : lastUseLoc) {
pair.second -= n;
}
for (auto pair : firstKillLoc) {
pair.second -= n;
}
for (auto pair : lastKillLoc) {
pair.second -= n;
}
for (auto pair : firstDeadLoc) {
pair.second -= n;
}
block->nodes.erase(block->nodes.begin() + j, block->nodes.begin() + j + n);
block->isexpr.erase(block->isexpr.begin() + j, block->isexpr.begin() + j + n);
};
if (block->isexpr[j] || hasSideEffects(node[3])) {
safeCopy(node, node[3]);
removeUnusedNodes(j, 1);
} else {
int numUsesInExpr = 0;
traversePre(node[3], [&](Ref node) {
if (node[0] == NAME && asmData.isLocal(node[1]->getIString())) {
numUsesInExpr++;
}
});
safeCopy(node, makeEmpty());
j = j - numUsesInExpr;
removeUnusedNodes(j, 1 + numUsesInExpr);
}
}
}
}
// XXX efficiency
block->use = use;
block->kill = kill;
block->link = link;
block->lastUseLoc = lastUseLoc;
block->firstDeadLoc = firstDeadLoc;
block->firstKillLoc = firstKillLoc;
block->lastKillLoc = lastKillLoc;
};
// Ordered map to work in approximate reverse order of junction appearance
std::set<int> jWorkSet;
std::set<int> bWorkSet;
// Be sure to visit every junction at least once.
// This avoids missing some vars because we disconnected them
// when processing the labelled jumps.
for (size_t i = EXIT_JUNCTION; i < junctions.size(); i++) {
jWorkSet.insert(i);
for (auto b : junctions[i].inblocks) {
bWorkSet.insert(b);
}
}
// Exit junction never has any live variable changes to propagate
jWorkSet.erase(EXIT_JUNCTION);
do {
// Iterate on just the junctions until we get stable live sets.
// The first run of this loop will grow the live sets to their maximal size.
// Subsequent runs will shrink them based on eliminated in-block uses.
while (jWorkSet.size() > 0) {
auto last = jWorkSet.end();
--last;
Junction& junc = junctions[*last];
jWorkSet.erase(last);
IOrderedStringSet oldLive = junc.live; // copy it here, to check for changes later
analyzeJunction(junc);
if (oldLive != junc.live) {
// Live set changed, updated predecessor blocks and junctions.
for (auto b : junc.inblocks) {
bWorkSet.insert(b);
jWorkSet.insert(blocks[b]->entry);
}
}
}
// Now update the blocks based on the calculated live sets.
while (bWorkSet.size() > 0) {
auto last = bWorkSet.end();
--last;
Block* block = blocks[*last];
bWorkSet.erase(last);
auto oldUse = block->use;
analyzeBlock(block);
if (oldUse != block->use) {
// The use set changed, re-process the entry junction.
jWorkSet.insert(block->entry);
}
}
} while (jWorkSet.size() > 0);
#ifdef PROFILING
tbackflow += clock() - start;
start = clock();
#endif
// Insist that all function parameters are alive at function entry.
// This ensures they will be assigned independent registers, even
// if they happen to be unused.
for (auto name : asmData.params) {
junctions[ENTRY_JUNCTION].live.insert(name);
}
// For variables that are live at one or more junctions, we assign them
// a consistent register for the entire scope of the function. Find pairs
// of variable that cannot use the same register (the "conflicts") as well
// as pairs of variables that we'd like to have share the same register
// (the "links").
struct JuncVar {
std::vector<bool> conf;
IOrderedStringSet link;
std::unordered_set<int> excl;
int reg;
bool used;
JuncVar() : reg(-1), used(false) {}
};
size_t numLocals = asmData.locals.size();
std::unordered_map<IString, size_t> nameToNum;
std::vector<IString> numToName;
nameToNum.reserve(numLocals);
numToName.reserve(numLocals);
for (auto kv : asmData.locals) {
nameToNum[kv.first] = numToName.size();
numToName.push_back(kv.first);
}
std::vector<JuncVar> juncVars(numLocals);
for (Junction& junc : junctions) {
for (IString name : junc.live) {
JuncVar& jVar = juncVars[nameToNum[name]];
jVar.used = true;
jVar.conf.assign(numLocals, false);
}
}
std::map<IString, std::vector<Block*>> possibleBlockConflictsMap;
std::vector<std::pair<size_t, std::vector<Block*>>> possibleBlockConflicts;
std::unordered_map<IString, std::vector<Block*>> possibleBlockLinks;
possibleBlockConflicts.reserve(numLocals);
possibleBlockLinks.reserve(numLocals);
for (Junction& junc : junctions) {
// Pre-compute the possible conflicts and links for each block rather
// than checking potentially impossible options for each var
possibleBlockConflictsMap.clear();
possibleBlockConflicts.clear();
possibleBlockLinks.clear();
for (auto b : junc.outblocks) {
Block* block = blocks[b];
Junction& jSucc = junctions[block->exit];
for (auto name : jSucc.live) {
possibleBlockConflictsMap[name].push_back(block);
}
for (auto name_linkname : block->link) {
if (name_linkname.first != name_linkname.second) {
possibleBlockLinks[name_linkname.first].push_back(block);
}
}
}
// Find the live variables in this block, mark them as unnecessary to
// check for conflicts (we mark all live vars as conflicting later)
std::vector<size_t> liveJVarNums;
liveJVarNums.reserve(junc.live.size());
for (auto name : junc.live) {
size_t jVarNum = nameToNum[name];
liveJVarNums.push_back(jVarNum);
possibleBlockConflictsMap.erase(name);
}
// Extract just the variables we might want to check for conflicts
for (auto kv : possibleBlockConflictsMap) {
possibleBlockConflicts.push_back(std::make_pair(nameToNum[kv.first], kv.second));
}
for (size_t jVarNum : liveJVarNums) {
JuncVar& jvar = juncVars[jVarNum];
IString name = numToName[jVarNum];
// It conflicts with all other names live at this junction.
for (size_t liveJVarNum : liveJVarNums) {
jvar.conf[liveJVarNum] = true;
}
jvar.conf[jVarNum] = false; // except for itself, of course
// It conflicts with any output vars of successor blocks,
// if they're assigned before it goes dead in that block.
for (auto jvarnum_blocks : possibleBlockConflicts) {
size_t otherJVarNum = jvarnum_blocks.first;
IString otherName = numToName[otherJVarNum];
for (auto block : jvarnum_blocks.second) {
if (block->lastKillLoc[otherName] < block->firstDeadLoc[name]) {
jvar.conf[otherJVarNum] = true;
juncVars[otherJVarNum].conf[jVarNum] = true;
break;
}
}
}
// It links with any linkages in the outgoing blocks.
for (auto block: possibleBlockLinks[name]) {
IString linkName = block->link[name];
jvar.link.insert(linkName);
juncVars[nameToNum[linkName]].link.insert(name);
}
}
}
#ifdef PROFILING
tjuncvaruniqassign += clock() - start;
start = clock();
#endif
// Attempt to sort the junction variables to heuristically reduce conflicts.
// Simple starting point: handle the most-conflicted variables first.
// This seems to work pretty well.
std::vector<size_t> sortedJVarNums;
sortedJVarNums.reserve(juncVars.size());
std::vector<size_t> jVarConfCounts(numLocals);
for (size_t jVarNum = 0; jVarNum < juncVars.size(); jVarNum++) {
JuncVar& jVar = juncVars[jVarNum];
if (!jVar.used) continue;
jVarConfCounts[jVarNum] = std::count(jVar.conf.begin(), jVar.conf.end(), true);
sortedJVarNums.push_back(jVarNum);
}
std::sort(sortedJVarNums.begin(), sortedJVarNums.end(), [&](const size_t vi1, const size_t vi2) {
// sort by # of conflicts
if (jVarConfCounts[vi1] < jVarConfCounts[vi2]) return true;
if (jVarConfCounts[vi1] == jVarConfCounts[vi2]) return numToName[vi1] < numToName[vi2];
return false;
});
#ifdef PROFILING
tjuncvarsort += clock() - start;
start = clock();
#endif
// We can now assign a register to each junction variable.
// Process them in order, trying available registers until we find
// one that works, and propagating the choice to linked/conflicted
// variables as we go.
std::function<bool (IString, int)> tryAssignRegister = [&](IString name, int reg) {
// Try to assign the given register to the given variable,
// and propagate that choice throughout the graph.
// Returns true if successful, false if there was a conflict.
JuncVar& jv = juncVars[nameToNum[name]];
if (jv.reg > 0) {
return jv.reg == reg;
}
if (jv.excl.count(reg) > 0) {
return false;
}
jv.reg = reg;
// Exclude use of this register at all conflicting variables.
for (size_t confNameNum = 0; confNameNum < jv.conf.size(); confNameNum++) {
if (jv.conf[confNameNum]) {
juncVars[confNameNum].excl.insert(reg);
}
}
// Try to propagate it into linked variables.
// It's not an error if we can't.
for (auto linkName : jv.link) {
tryAssignRegister(linkName, reg);
}
return true;
};
for (size_t jVarNum : sortedJVarNums) {
// It may already be assigned due to linked-variable propagation.
if (juncVars[jVarNum].reg > 0) {
continue;
}
IString name = numToName[jVarNum];
// Try to use existing registers first.
auto& allRegs = allRegsByType[asmData.getType(name)];
bool moar = false;
for (auto reg : allRegs) {
if (tryAssignRegister(name, reg.first)) {
moar = true;
break;
}
}
if (moar) continue;
// They're all taken, create a new one.
tryAssignRegister(name, createReg(name));
}
#ifdef PROFILING
tregassign += clock() - start;
start = clock();
#endif
// Each basic block can now be processed in turn.
// There may be internal-use-only variables that still need a register
// assigned, but they can be treated just for this block. We know
// that all inter-block variables are in a good state thanks to
// junction variable consistency.
for (size_t i = 0; i < blocks.size(); i++) {
Block* block = blocks[i];
if (block->nodes.size() == 0) continue;
Junction& jEnter = junctions[block->entry];
Junction& jExit = junctions[block->exit];
// Mark the point at which each input reg becomes dead.
// Variables alive before this point must not be assigned
// to that register.
StringSet inputVars;
std::unordered_map<int, int> inputDeadLoc;
std::unordered_map<int, IString> inputVarsByReg;
for (auto name : jExit.live) {
if (!block->kill.has(name)) {
inputVars.insert(name);
int reg = juncVars[nameToNum[name]].reg;
assert(reg > 0); // 'input variable doesnt have a register');
inputDeadLoc[reg] = block->firstDeadLoc[name];
inputVarsByReg[reg] = name;
}
}
for (auto pair : block->use) {
IString name = pair.first;
if (!inputVars.has(name)) {
inputVars.insert(name);
int reg = juncVars[nameToNum[name]].reg;
assert(reg > 0); // 'input variable doesnt have a register');
inputDeadLoc[reg] = block->firstDeadLoc[name];
inputVarsByReg[reg] = name;
}
}
// TODO assert(setSize(setSub(inputVars, jEnter.live)) == 0);
// Scan through backwards, allocating registers on demand.
// Be careful to avoid conflicts with the input registers.
// We consume free registers in last-used order, which helps to
// eliminate "x=y" assignments that are the last use of "y".
StringIntMap assignedRegs;
auto freeRegsByTypePre = allRegsByType; // XXX copy
// Begin with all live vars assigned per the exit junction.
for (auto name : jExit.live) {
int reg = juncVars[nameToNum[name]].reg;
assert(reg > 0); // 'output variable doesnt have a register');
assignedRegs[name] = reg;
freeRegsByTypePre[asmData.getType(name)].erase(reg); // XXX assert?
}
std::vector<std::vector<int>> freeRegsByType;
freeRegsByType.resize(freeRegsByTypePre.size());
for (size_t j = 0; j < freeRegsByTypePre.size(); j++) {
for (auto pair : freeRegsByTypePre[j]) {
freeRegsByType[j].push_back(pair.first);
}
}
// Scan through the nodes in sequence, modifying each node in-place
// and grabbing/freeing registers as needed.
std::vector<std::pair<int, Ref>> maybeRemoveNodes;
for (int j = block->nodes.size() - 1; j >= 0; j--) {
Ref node = block->nodes[j];
IString name = (node[0] == ASSIGN ? node[2][1] : node[1])->getIString();
IntStringMap& allRegs = allRegsByType[asmData.getType(name)];
std::vector<int>& freeRegs = freeRegsByType[asmData.getType(name)];
int reg = assignedRegs[name]; // XXX may insert a zero
if (node[0] == NAME) {
// A use. Grab a register if it doesn't have one.
if (reg <= 0) {
if (inputVars.has(name) && j <= block->firstDeadLoc[name]) {
// Assignment to an input variable, must use pre-assigned reg.
reg = juncVars[nameToNum[name]].reg;
assignedRegs[name] = reg;
for (int k = freeRegs.size() - 1; k >= 0; k--) {
if (freeRegs[k] == reg) {
freeRegs.erase(freeRegs.begin() + k);
break;
}
}
} else {
// Try to use one of the existing free registers.
// It must not conflict with an input register.
for (int k = freeRegs.size() - 1; k >= 0; k--) {
reg = freeRegs[k];
// Check for conflict with input registers.
if (inputDeadLoc.count(reg) > 0) {
if (block->firstKillLoc[name] <= inputDeadLoc[reg]) {
if (name != inputVarsByReg[reg]) {
continue;
}
}
}
// Found one!
assignedRegs[name] = reg;
assert(reg > 0);
freeRegs.erase(freeRegs.begin() + k);
break;
}
// If we didn't find a suitable register, create a new one.
if (assignedRegs[name] <= 0) {
reg = createReg(name);
assignedRegs[name] = reg;
}
}
}
node[1]->setString(allRegs[reg]);
} else {
// A kill. This frees the assigned register.
assert(reg > 0); //, 'live variable doesnt have a reg?')
node[2][1]->setString(allRegs[reg]);
freeRegs.push_back(reg);
assignedRegs.erase(name);
if (node[3][0] == NAME && asmData.isLocal(node[3][1]->getIString())) {
maybeRemoveNodes.push_back(std::pair<int, Ref>(j, node));
}
}
}
// If we managed to create any "x=x" assignments, remove them.
for (size_t j = 0; j < maybeRemoveNodes.size(); j++) {
Ref node = maybeRemoveNodes[j].second;
if (node[2][1] == node[3][1]) {
if (block->isexpr[maybeRemoveNodes[j].first]) {
safeCopy(node, node[2]);
} else {
safeCopy(node, makeEmpty());
}
}
}
}
#ifdef PROFILING
tblockproc += clock() - start;
start = clock();
#endif
// Assign registers to function params based on entry junction
StringSet paramRegs;
if (!!fun[2]) {
for (size_t i = 0; i < fun[2]->size(); i++) {
auto& allRegs = allRegsByType[asmData.getType(fun[2][i]->getIString())];
fun[2][i]->setString(allRegs[juncVars[nameToNum[fun[2][i]->getIString()]].reg]);
paramRegs.insert(fun[2][i]->getIString());
}
}
// That's it!
// Re-construct the function with appropriate variable definitions.
asmData.locals.clear();
asmData.params.clear();
asmData.vars.clear();
for (int i = 1; i < nextReg; i++) {
for (size_t type = 0; type < allRegsByType.size(); type++) {
if (allRegsByType[type].count(i) > 0) {
IString reg = allRegsByType[type][i];
if (!paramRegs.has(reg)) {
asmData.addVar(reg, intToAsmType(type));
} else {
asmData.addParam(reg, intToAsmType(type));
}
break;
}
}
}
asmData.denormalize();
removeAllUselessSubNodes(fun); // XXX vacuum? vacuum(fun);
#ifdef PROFILING
treconstruct += clock() - start;
start = clock();
#endif
});
#ifdef PROFILING
errv(" RH stages: a:%li fl:%li lf:%li bf:%li jvua:%li jvs:%li jra:%li bp:%li r:%li",
tasmdata, tflowgraph, tlabelfix, tbackflow, tjuncvaruniqassign, tjuncvarsort, tregassign, tblockproc, treconstruct);
#endif
}
// end registerizeHarder
// minified names generation
StringSet RESERVED("do if in for new try var env let case else enum this void with");
const char *VALID_MIN_INITS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$";
const char *VALID_MIN_LATERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$0123456789";
StringVec minifiedNames;
std::vector<int> minifiedState;
void ensureMinifiedNames(int n) { // make sure the nth index in minifiedNames exists. done 100% deterministically
static int VALID_MIN_INITS_LEN = strlen(VALID_MIN_INITS);
static int VALID_MIN_LATERS_LEN = strlen(VALID_MIN_LATERS);
while ((int)minifiedNames.size() < n+1) {
// generate the current name
std::string name;
name += VALID_MIN_INITS[minifiedState[0]];
for (size_t i = 1; i < minifiedState.size(); i++) {
name += VALID_MIN_LATERS[minifiedState[i]];
}
IString str(strdupe(name.c_str())); // leaked!
if (!RESERVED.has(str)) minifiedNames.push_back(str);
// increment the state
size_t i = 0;
while (1) {
minifiedState[i]++;
if (minifiedState[i] < (i == 0 ? VALID_MIN_INITS_LEN : VALID_MIN_LATERS_LEN)) break;
// overflow
minifiedState[i] = 0;
i++;
if (i == minifiedState.size()) minifiedState.push_back(-1); // will become 0 after increment in next loop head
}
}
}
void minifyLocals(Ref ast) {
assert(!!extraInfo);
IString GLOBALS("globals");
assert(extraInfo->has(GLOBALS));
Ref globals = extraInfo[GLOBALS];
if (minifiedState.size() == 0) minifiedState.push_back(0);
traverseFunctions(ast, [&globals](Ref fun) {
// Analyse the asmjs to figure out local variable names,
// but operate on the original source tree so that we don't
// miss any global names in e.g. variable initializers.
AsmData asmData(fun);
asmData.denormalize(); // TODO: we can avoid modifying at all here - we just need a list of local vars+params
StringStringMap newNames;
StringSet usedNames;
// Find all the globals that we need to minify using
// pre-assigned names. Don't actually minify them yet
// as that might interfere with local variable names.
traversePre(fun, [&](Ref node) {
if (node[0] == NAME) {
IString name = node[1]->getIString();
if (!asmData.isLocal(name)) {
if (globals->has(name)) {
IString minified = globals[name]->getIString();
assert(!!minified);
newNames[name] = minified;
usedNames.insert(minified);
}
}
}
});
// The first time we encounter a local name, we assign it a
// minified name that's not currently in use. Allocating on
// demand means they're processed in a predictable order,
// which is very handy for testing/debugging purposes.
int nextMinifiedName = 0;
auto getNextMinifiedName = [&]() {
IString minified;
while (1) {
ensureMinifiedNames(nextMinifiedName);
minified = minifiedNames[nextMinifiedName++];
// TODO: we can probably remove !isLocalName here
if (!usedNames.has(minified) && !asmData.isLocal(minified)) {
return minified;
}
}
};
// We can also minify loop labels, using a separate namespace
// to the variable declarations.
StringStringMap newLabels;
int nextMinifiedLabel = 0;
auto getNextMinifiedLabel = [&]() {
ensureMinifiedNames(nextMinifiedLabel);
return minifiedNames[nextMinifiedLabel++];
};
// Traverse and minify all names.
if (globals->has(fun[1]->getIString())) {
fun[1]->setString(globals[fun[1]->getIString()]->getIString());
assert(!!fun[1]);
}
if (!!fun[2]) {
for (size_t i = 0; i < fun[2]->size(); i++) {
IString minified = getNextMinifiedName();
newNames[fun[2][i]->getIString()] = minified;
fun[2][i]->setString(minified);
}
}
traversePre(fun[3], [&](Ref node) {
Ref type = node[0];
if (type == NAME) {
IString name = node[1]->getIString();
IString minified = newNames[name];
if (!!minified) {
node[1]->setString(minified);
} else if (asmData.isLocal(name)) {
minified = getNextMinifiedName();
newNames[name] = minified;
node[1]->setString(minified);
}
} else if (type == VAR) {
for (size_t i = 0; i < node[1]->size(); i++) {
Ref defn = node[1][i];
IString name = defn[0]->getIString();
if (!(newNames.has(name))) {
newNames[name] = getNextMinifiedName();
}
defn[0]->setString(newNames[name]);
}
} else if (type == LABEL) {
IString name = node[1]->getIString();
if (!newLabels.has(name)) {
newLabels[name] = getNextMinifiedLabel();
}
node[1]->setString(newLabels[name]);
} else if (type == BREAK || type == CONTINUE) {
if (node->size() > 1 && !!node[1]) {
node[1]->setString(newLabels[node[1]->getIString()]);
}
}
});
});
}
void asmLastOpts(Ref ast) {
std::vector<Ref> statsStack;
traverseFunctions(ast, [&](Ref fun) {
traversePrePost(fun, [&](Ref node) {
Ref type = node[0];
Ref stats = getStatements(node);
if (!!stats) statsStack.push_back(stats);
if (CONDITION_CHECKERS.has(type)) {
node[1] = simplifyCondition(node[1]);
}
if (type == WHILE && node[1][0] == NUM && node[1][1]->getNumber() == 1 && node[2][0] == BLOCK && node[2]->size() == 2) {
// This is at the end of the pipeline, we can assume all other optimizations are done, and we modify loops
// into shapes that might confuse other passes
// while (1) { .. if (..) { break } } ==> do { .. } while(..)
Ref stats = node[2][1];
Ref last = stats->back();
if (!!last && last[0] == IF && (last->size() < 4 || !last[3]) && last[2][0] == BLOCK && !!last[2][1][0]) {
Ref lastStats = last[2][1];
int lastNum = lastStats->size();
Ref lastLast = lastStats[lastNum-1];
if (!(lastLast[0] == BREAK && !lastLast[1])) return;// if not a simple break, dangerous
for (int i = 0; i < lastNum; i++) {
if (lastStats[i][0] != STAT && lastStats[i][0] != BREAK) return; // something dangerous
}
// ok, a bunch of statements ending in a break
bool abort = false;
int stack = 0;
int breaks = 0;
traversePrePost(stats, [&](Ref node) {
Ref type = node[0];
if (type == CONTINUE) {
if (stack == 0 || !!node[1]) { // abort if labeled (we do not analyze labels here yet), or a continue directly on us
abort = true;
}
} else if (type == BREAK) {
if (stack == 0 || !!node[1]) { // relevant if labeled (we do not analyze labels here yet), or a break directly on us
breaks++;
}
} else if (LOOP.has(type)) {
stack++;
}
}, [&](Ref node) {
if (LOOP.has(node[0])) {
stack--;
}
});
if (abort) return;
assert(breaks > 0);
if (lastStats->size() > 1 && breaks != 1) return; // if we have code aside from the break, we can only move it out if there is just one break
if (statsStack.size() < 1) return; // no chance we have this stats on hand
// start to optimize
if (lastStats->size() > 1) {
Ref parent = statsStack.back();
int me = parent->indexOf(node);
if (me < 0) return; // not always directly on a stats, could be in a label for example
parent->insert(me+1, lastStats->size()-1);
for (size_t i = 0; i+1 < lastStats->size(); i++) {
parent[me+1+i] = lastStats[i];
}
}
Ref conditionToBreak = last[1];
stats->pop_back();
node[0]->setString(DO);
node[1] = simplifyNotCompsDirect(make2(UNARY_PREFIX, L_NOT, conditionToBreak));
}
} else if (type == BINARY) {
if (node[1] == AND) {
if (node[3][0] == UNARY_PREFIX && node[3][1] == MINUS && node[3][2][0] == NUM && node[3][2][1]->getNumber() == 1) {
// Change &-1 into |0, at this point the hint is no longer needed
node[1]->setString(OR);
node[3] = node[3][2];
node[3][1]->setNumber(0);
}
} else if (node[1] == MINUS && node[3][0] == UNARY_PREFIX) {
// avoid X - (-Y) because some minifiers buggily emit X--Y which is invalid as -- can be a unary. Transform to
// X + Y
if (node[3][1] == MINUS) { // integer
node[1]->setString(PLUS);
node[3] = node[3][2];
} else if (node[3][1] == PLUS) { // float
if (node[3][2][0] == UNARY_PREFIX && node[3][2][1] == MINUS) {
node[1]->setString(PLUS);
node[3][2] = node[3][2][2];
}
}
}
}
}, [&](Ref node) {
if (statsStack.size() > 0) {
Ref stats = getStatements(node);
if (!!stats) statsStack.pop_back();
}
});
// convert { singleton } into singleton
traversePre(fun, [](Ref node) {
if (node[0] == BLOCK && !!getStatements(node) && node[1]->size() == 1) {
safeCopy(node, node[1][0]);
}
});
// convert L: do { .. } while(0) into L: { .. }
traversePre(fun, [](Ref node) {
if (node[0] == LABEL && node[1]->isString() /* careful of var label = 5 */ &&
node[2][0] == DO && node[2][1][0] == NUM && node[2][1][1]->getNumber() == 0 && node[2][2][0] == BLOCK) {
// there shouldn't be any continues on this, not direct break or continue
IString label = node[1]->getIString();
bool abort = false;
int breakCaptured = 0, continueCaptured = 0;
traversePrePost(node[2][2], [&](Ref node) {
if (node[0] == CONTINUE) {
if (!node[1] && !continueCaptured) {
abort = true;
} else if (node[1]->isString() && node[1]->getIString() == label) {
abort = true;
}
}
if (node[0] == BREAK && !node[1] && !breakCaptured) {
abort = true;
}
if (BREAK_CAPTURERS.has(node[0])) {
breakCaptured++;
}
if (CONTINUE_CAPTURERS.has(node[0])) {
continueCaptured++;
}
}, [&](Ref node) {
if (BREAK_CAPTURERS.has(node[0])) {
breakCaptured--;
}
if (CONTINUE_CAPTURERS.has(node[0])) {
continueCaptured--;
}
});
if (abort) return;
safeCopy(node[2], node[2][2]);
}
});
});
}
// Contrary to the name this does not eliminate actual dead functions, only
// those marked as such with DEAD_FUNCTIONS
void eliminateDeadFuncs(Ref ast) {
assert(!!extraInfo);
IString DEAD_FUNCTIONS("dead_functions");
IString ABORT("abort");
assert(extraInfo->has(DEAD_FUNCTIONS));
StringSet deadFunctions;
for (size_t i = 0; i < extraInfo[DEAD_FUNCTIONS]->size(); i++) {
deadFunctions.insert(extraInfo[DEAD_FUNCTIONS][i]->getIString());
}
traverseFunctions(ast, [&](Ref fun) {
if (!deadFunctions.has(fun[1].get()->getIString())) {
return;
}
AsmData asmData(fun);
fun[3]->setSize(1);
fun[3][0] = make1(STAT, make2(CALL, makeName(ABORT), &(makeArray(1))->push_back(makeNum(-1))));
asmData.vars.clear();
asmData.denormalize();
});
}