aboutsummaryrefslogtreecommitdiff
path: root/tools/js-optimizer.js
diff options
context:
space:
mode:
Diffstat (limited to 'tools/js-optimizer.js')
-rw-r--r--tools/js-optimizer.js272
1 files changed, 254 insertions, 18 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index fc195e03..129c493f 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -140,6 +140,8 @@ var ALTER_FLOW = set('break', 'continue', 'return');
var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch');
var CONTINUE_CAPTURERS = LOOP;
+var COMMABLE = set('assign', 'binary', 'unary-prefix', 'unary-postfix', 'name', 'num', 'call', 'seq', 'conditional', 'sub');
+
var FUNCTIONS_THAT_ALWAYS_THROW = set('abort', '___resumeException', '___cxa_throw', '___cxa_rethrow');
var NULL_NODE = ['name', 'null'];
@@ -279,6 +281,38 @@ function clearEmptyNodes(list) {
}
}
+function filterEmptyNodes(list) { // creates a copy and returns it
+ return list.filter(function(node) {
+ return !(isEmptyNode(node) || (node[0] === 'stat' && isEmptyNode(node[1])));
+ });
+}
+
+function removeEmptySubNodes(node) {
+ if (node[0] === 'defun') {
+ node[3] = filterEmptyNodes(node[3]);
+ } else if (node[0] === 'block' && node[1]) {
+ node[1] = filterEmptyNodes(node[1]);
+ }
+/*
+ var stats = getStatements(node);
+ if (stats) clearEmptyNodes(stats);
+*/
+}
+
+function removeAllEmptySubNodes(ast) {
+ traverse(ast, removeEmptySubNodes);
+}
+
+function astCompare(x, y) {
+ if (!Array.isArray(x)) return x === y;
+ if (!Array.isArray(y)) return false;
+ if (x.length !== y.length) return false;
+ for (var i = 0; i < x.length; i++) {
+ if (!astCompare(x[i], y[i])) return false;
+ }
+ return true;
+}
+
// Passes
// Dump the AST. Useful for debugging. For example,
@@ -414,7 +448,7 @@ function removeUnneededLabelSettings(ast) {
});
}
-// Various expression simplifications. Pre run before closure (where we still have metadata), Post run after.
+// Various expression simplifications. Happens after elimination, which opens up many of these simplification opportunities.
var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^');
var COMPARE_OPS = set('<', '<=', '>', '>=', '==', '===', '!=', '!==');
@@ -797,11 +831,166 @@ function simplifyExpressions(ast) {
simplifyIntegerConversions(func);
simplifyBitops(func);
joinAdditions(func);
- // simplifyZeroComp(func); TODO: investigate performance
simplifyNotComps(func);
+ // simplifyZeroComp(func); TODO: investigate performance
+ });
+}
+
+
+function simplifyIfs(ast) {
+ traverseGeneratedFunctions(ast, function(func) {
+ var simplifiedAnElse = false;
+
+ traverse(func, function(node, type) {
+ // simplify if (x) { if (y) { .. } } to if (x ? y : 0) { .. }
+ if (type === 'if') {
+ var body = node[2];
+ // recurse to handle chains
+ while (body[0] === 'block') {
+ var stats = body[1];
+ if (stats.length === 0) break;
+ var other = stats[stats.length-1];
+ if (other[0] !== 'if') {
+ // our if block does not end with an if. perhaps if have an else we can flip
+ if (node[3] && node[3][0] === 'block') {
+ var stats = node[3][1];
+ if (stats.length === 0) break;
+ var other = stats[stats.length-1];
+ 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 (!astCompare(node[3], other[3])) {
+ // the elses are different, but perhaps if we flipped a condition we can do better
+ if (astCompare(node[3], 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] = ['block', []];
+ other[1] = flipCondition(other[1]);
+ var temp = other[2];
+ other[2] = other[3];
+ other[3] = temp;
+ } else break;
+ }
+ }
+ if (stats.length > 1) {
+ // try to commaify - turn everything between the ifs into a comma operator inside the second if
+ var ok = true;
+ for (var i = 0; i < stats.length-1; i++) {
+ var curr = stats[i];
+ if (curr[0] === 'stat') curr = curr[1];
+ if (!(curr[0] in COMMABLE)) ok = false;
+ }
+ if (!ok) break;
+ for (var i = stats.length-2; i >= 0; i--) {
+ var curr = stats[i];
+ if (curr[0] === 'stat') curr = curr[1];
+ other[1] = ['seq', curr, other[1]];
+ }
+ stats = body[1] = [other];
+ }
+ if (stats.length !== 1) break;
+ if (node[3]) simplifiedAnElse = true;
+ node[1] = ['conditional', node[1], other[1], ['num', 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
+ var abort = false;
+
+ var labelAssigns = {};
+ traverse(func, function(node, type) {
+ if (type === 'assign' && node[2][0] === 'name' && node[2][1] === 'label') {
+ if (node[3][0] === 'num') {
+ var value = node[3][1];
+ labelAssigns[value] = (labelAssigns[value] || 0) + 1;
+ } else {
+ // label is assigned a dynamic value (like from indirectbr), we cannot do anything
+ abort = true;
+ }
+ }
+ });
+ if (abort) return;
+
+ var labelChecks = {};
+ traverse(func, function(node, type) {
+ if (type === 'binary' && node[1] === '==' && node[2][0] === 'binary' && node[2][1] === '|' &&
+ node[2][2][0] === 'name' && node[2][2][1] === 'label') {
+ if (node[3][0] === 'num') {
+ var value = node[3][1];
+ labelChecks[value] = (labelChecks[value] || 0) + 1;
+ } else {
+ // label is checked vs a dynamic value (like from indirectbr), we cannot do anything
+ abort = true;
+ }
+ }
+ });
+ if (abort) return;
+
+ var inLoop = 0; // when in a loop, we do not emit label = 0; in the relooper as there is no need
+ traverse(func, function(node, type) {
+ if (type === 'while') inLoop++;
+ var stats = getStatements(node);
+ if (stats) {
+ for (var i = 0; i < stats.length-1; i++) {
+ var pre = stats[i];
+ var post = stats[i+1];
+ if (pre[0] === 'if' && pre[3] && post[0] === 'if' && !post[3]) {
+ var postCond = post[1];
+ if (postCond[0] === 'binary' && postCond[1] === '==' &&
+ postCond[2][0] === 'binary' && postCond[2][1] === '|' &&
+ postCond[2][2][0] === 'name' && postCond[2][2][1] === 'label' &&
+ postCond[2][3][0] === 'num' && postCond[2][3][1] === 0 &&
+ postCond[3][0] === 'num') {
+ var postValue = postCond[3][1];
+ var preElse = pre[3];
+ if (labelAssigns[postValue] === 1 && labelChecks[postValue] === 1 && preElse[0] === 'block' && preElse[1] && preElse[1].length === 1) {
+ var preStat = preElse[1][0];
+ if (preStat[0] === 'stat' && preStat[1][0] === 'assign' &&
+ preStat[1][1] === true && preStat[1][2][0] === 'name' && preStat[1][2][1] === 'label' &&
+ preStat[1][3][0] === 'num' && preStat[1][3][1] === postValue) {
+ // Conditions match, just need to make sure the post clears label
+ if (post[2][0] === 'block' && post[2][1] && post[2][1].length > 0) {
+ var postStat = post[2][1][0];
+ var haveClear =
+ postStat[0] === 'stat' && postStat[1][0] === 'assign' &&
+ postStat[1][1] === true && postStat[1][2][0] === 'name' && postStat[1][2][1] === 'label' &&
+ postStat[1][3][0] === 'num' && postStat[1][3][1] === 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
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }, function(node, type) {
+ if (type === 'while') inLoop--;
+ });
+ }
});
}
+
// In typed arrays mode 2, we can have
// HEAP[x >> 2]
// very often. We can in some cases do the shift on the variable itself when it is set,
@@ -1161,6 +1350,10 @@ function simplifyNotCompsDirect(node) {
if (!simplifyNotCompsPass) return node;
}
+function flipCondition(cond) {
+ return simplifyNotCompsDirect(['unary-prefix', '!', cond]);
+}
+
var simplifyNotCompsPass = false;
function simplifyNotComps(ast) {
@@ -1281,6 +1474,7 @@ function vacuum(ast) {
traverseGeneratedFunctions(ast, function(node) {
vacuumInternal(node);
simplifyNotComps(node);
+ removeEmptySubNodes(node);
});
}
@@ -1426,7 +1620,7 @@ function hoistMultiples(ast) {
var temp = node[3];
node[3] = node[2];
node[2] = temp;
- node[1] = simplifyNotCompsDirect(['unary-prefix', '!', node[1]]);
+ node[1] = flipCondition(node[1]);
stat1 = node[2][1];
stat2 = node[3][1];
}
@@ -1687,6 +1881,11 @@ function denormalizeAsm(func, data) {
if (!isEmptyNode(stats[i])) break;
}
}
+ // calculate variable definitions
+ var varDefs = [];
+ for (var v in data.vars) {
+ varDefs.push(makeAsmVarDef(v, data.vars[v]));
+ }
// each param needs a line; reuse emptyNodes as much as we can
var numParams = 0;
for (var i in data.params) numParams++;
@@ -1695,26 +1894,21 @@ function denormalizeAsm(func, data) {
if (!isEmptyNode(stats[emptyNodes])) break;
emptyNodes++;
}
- var neededEmptyNodes = numParams + 1; // params plus one big var
+ var neededEmptyNodes = numParams + (varDefs.length ? 1 : 0); // params plus one big var if there are vars
if (neededEmptyNodes > emptyNodes) {
var args = [0, 0];
for (var i = 0; i < neededEmptyNodes - emptyNodes; i++) args[i+2] = 0;
stats.splice.apply(stats, args);
+ } else if (neededEmptyNodes < emptyNodes) {
+ stats.splice(0, emptyNodes - neededEmptyNodes);
}
// add param coercions
var next = 0;
func[2].forEach(function(param) {
stats[next++] = ['stat', ['assign', true, ['name', param], makeAsmCoercion(['name', param], data.params[param])]];
});
- // add variable definitions
- var varDefs = [];
- for (var v in data.vars) {
- varDefs.push(makeAsmVarDef(v, data.vars[v]));
- }
if (varDefs.length) {
stats[next] = ['var', varDefs];
- } else {
- stats[next] = emptyNode();
}
if (data.inlines.length > 0) {
var i = 0;
@@ -3877,6 +4071,8 @@ function eliminate(ast, memSafe) {
}
new ExpressionOptimizer(ast).run();
}
+
+ removeAllEmptySubNodes(ast);
}
function eliminateMemSafe(ast) {
@@ -4247,6 +4443,8 @@ function aggressiveVariableEliminationInternal(func, asmData) {
}
}
});
+
+ removeAllEmptySubNodes(func);
}
function aggressiveVariableElimination(ast) {
@@ -4525,10 +4723,10 @@ function outline(ast) {
var size = measureSize(func);
if (size <= extraInfo.sizeToOutline) {
sizeToOutline = Infinity;
- printErr(' no point in trying to reduce the size of ' + func[1] + ' which is ' + size + ' <= ' + extraInfo.sizeToOutline);
+ //printErr(' no point in trying to reduce the size of ' + func[1] + ' which is ' + size + ' <= ' + extraInfo.sizeToOutline);
} else {
sizeToOutline = Math.round(size/Math.max(2, asmData.intendedPieces--));
- printErr('trying to reduce the size of ' + func[1] + ' which is ' + size + ' (>=? ' + extraInfo.sizeToOutline + '), aim for ' + sizeToOutline);
+ //printErr('trying to reduce the size of ' + func[1] + ' which is ' + size + ' (>=? ' + extraInfo.sizeToOutline + '), aim for ' + sizeToOutline);
}
}
@@ -4753,7 +4951,7 @@ function outline(ast) {
}
}
outliningParents[newIdent] = func[1];
- printErr('performed outline ' + [func[1], newIdent, 'pre size', originalCodeSize, 'resulting size', measureSize(code), 'overhead (w/r):', setSize(setSub(codeInfo.writes, owned)), setSize(setSub(codeInfo.reads, owned)), ' owned: ', setSize(owned), ' left: ', setSize(asmData.vars), setSize(asmData.params), ' loopsDepth: ', loops]);
+ //printErr('performed outline ' + [func[1], newIdent, 'pre size', originalCodeSize, 'resulting size', measureSize(code), 'overhead (w/r):', setSize(setSub(codeInfo.writes, owned)), setSize(setSub(codeInfo.reads, owned)), ' owned: ', setSize(owned), ' left: ', setSize(asmData.vars), setSize(asmData.params), ' loopsDepth: ', loops]);
calculateThreshold(func, asmData);
return [newFunc];
}
@@ -4775,7 +4973,16 @@ function outline(ast) {
for (var i = minIndex; i < stats.length; i++) {
var stat = stats[i];
if (stat[0] == 'stat') stat = stat[1];
- if (stat[0] == 'assign' && stat[2][0] == 'name' && stat[2][1] == 'sp') minIndex = i+1; // cannot outline |sp = |
+ if (stat[0] == 'assign' && stat[2][0] == 'name' && stat[2][1] == 'sp') {
+ // cannot outline |sp = |
+ minIndex = i+1;
+ // When followed by a STACKTOP bump, preserve that too (we may need to replace it later)
+ stat = stats[i+1];
+ if (stat[0] == 'stat') stat = stat[1];
+ if (stat && stat[0] == 'assign' && stat[2][0] == 'name' && stat[2][1] == 'STACKTOP') {
+ minIndex = i+2;
+ }
+ }
}
}
}
@@ -4899,7 +5106,7 @@ function outline(ast) {
var maxTotalFunctions = Infinity; // debugging tool
- printErr('\n');
+ //printErr('\n');
var more = true;
while (more) {
@@ -4926,7 +5133,27 @@ function outline(ast) {
if ('sp' in asmData.vars) {
// find stack bump (STACKTOP = STACKTOP + X | 0) and add the extra space
var stackBumpNode = getStackBumpNode(stats);
- if (stackBumpNode) stackBumpNode[3][2][3][1] = asmData.totalStackSize;
+ if (stackBumpNode) {
+ stackBumpNode[3][2][3][1] = asmData.totalStackSize;
+ } else {
+ // sp exists, but no stack bump, so we need to add it
+ var found = false;
+ for (var i = 0; i < stats.length; i++) {
+ var stat = stats[i];
+ if (stat[0] === 'stat') stat = stat[1];
+ if (stat[0] === 'assign' && stat[2][0] === 'name' && stat[2][1] === 'sp') {
+ var newNode = ['stat', makeAssign(['name', 'STACKTOP'], ['binary', '|', ['binary', '+', ['name', 'STACKTOP'], ['num', asmData.totalStackSize]], ['num', 0]])];
+ if (i+1 < stats.length) {
+ stats.splice(i+1, 0, newNode);
+ } else {
+ stats.push(newNode);
+ }
+ found = true;
+ break;
+ }
+ }
+ assert(found);
+ }
} else if (!('sp' in asmData.params)) { // if sp is a param, then we are an outlined function, no need to add stack support for us
// add sp variable and stack bump
var index = getFirstIndexInNormalized(func, asmData);
@@ -4961,7 +5188,7 @@ function outline(ast) {
}
if (ret) {
ret.push(func);
- printErr('... resulting sizes of ' + func[1] + ' is ' + ret.map(measureSize) + '\n');
+ //printErr('... resulting sizes of ' + func[1] + ' is ' + ret.map(measureSize) + '\n');
}
}
denormalizeAsm(func, asmData);
@@ -5206,6 +5433,7 @@ var passes = {
removeAssignsToUndefined: removeAssignsToUndefined,
//removeUnneededLabelSettings: removeUnneededLabelSettings,
simplifyExpressions: simplifyExpressions,
+ simplifyIfs: simplifyIfs,
optimizeShiftsConservative: optimizeShiftsConservative,
optimizeShiftsAggressive: optimizeShiftsAggressive,
hoistMultiples: hoistMultiples,
@@ -5252,7 +5480,15 @@ if (extraInfoStart > 0) extraInfo = JSON.parse(src.substr(extraInfoStart + 14));
arguments_.slice(1).forEach(function(arg) {
+ //traverse(ast, function(node) {
+ // if (node[0] === 'defun' && node[1] === 'copyTempFloat') printErr('pre ' + JSON.stringify(node, null, ' '));
+ //});
passes[arg](ast);
+ //var func;
+ //traverse(ast, function(node) {
+ // if (node[0] === 'defun') func = node;
+ // if (isEmptyNode(node)) throw 'empty node after ' + arg + ', in ' + func[1];
+ //});
});
if (asm && last) {
asmLastOpts(ast); // TODO: move out of last, to make last faster when done later (as in side modules)
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-28 04:14:22 +0000