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.js720
1 files changed, 279 insertions, 441 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index c8766bc6..086ed30e 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'];
@@ -167,11 +169,11 @@ function astToSrc(ast, minifyWhitespace) {
// Traverses the children of a node. If the traverse function returns an object,
// replaces the child. If it returns true, stop the traversal and return true.
-function traverseChildren(node, traverse, pre, post, stack) {
+function traverseChildren(node, traverse, pre, post) {
for (var i = 0; i < node.length; i++) {
var subnode = node[i];
if (Array.isArray(subnode)) {
- var subresult = traverse(subnode, pre, post, stack);
+ var subresult = traverse(subnode, pre, post);
if (subresult === true) return true;
if (subresult !== null && typeof subresult === 'object') node[i] = subresult;
}
@@ -187,45 +189,29 @@ function traverseChildren(node, traverse, pre, post, stack) {
// it replaces the passed node in the tree. If null is returned, we stop
// traversing the subelements (but continue otherwise).
// @arg post: A callback to call after traversing all children.
-// @arg stack: If true, a stack will be implemented: If pre does not push on
-// the stack, we push a 0. We pop when we leave the node. The
-// stack is passed as a third parameter to the callbacks.
// @returns: If the root node was replaced, the new root node. If the traversal
// was stopped, true. Otherwise undefined.
-function traverse(node, pre, post, stack) {
+function traverse(node, pre, post) {
var type = node[0], result, len;
var relevant = typeof type === 'string';
if (relevant) {
- if (stack) len = stack.length;
- var result = pre(node, type, stack);
+ var result = pre(node, type);
if (result === true) return true;
if (result && result !== null) node = result; // Continue processing on this node
- if (stack && len === stack.length) stack.push(0);
}
if (result !== null) {
- if (traverseChildren(node, traverse, pre, post, stack) === true) return true;
+ if (traverseChildren(node, traverse, pre, post) === true) return true;
}
if (relevant) {
if (post) {
- var postResult = post(node, type, stack);
+ var postResult = post(node, type);
result = result || postResult;
}
- if (stack) stack.pop();
}
return result;
}
// Only walk through the generated functions
-function traverseGenerated(ast, pre, post, stack) {
- assert(generatedFunctions);
- traverse(ast, function(node) {
- if (node[0] === 'defun') {
- traverse(node, pre, post, stack);
- return null;
- }
- });
-}
-
function traverseGeneratedFunctions(ast, callback) {
assert(generatedFunctions);
if (ast[0] === 'toplevel') {
@@ -239,30 +225,10 @@ function traverseGeneratedFunctions(ast, callback) {
}
}
-// Walk the ast in a simple way, with an understanding of which JS variables are defined)
-function traverseWithVariables(ast, callback) {
- traverse(ast, function(node, type, stack) {
- if (type in FUNCTION) {
- stack.push({ type: 'function', vars: node[2] });
- } else if (type === 'var') {
- // Find our function, add our vars
- var func = stack[stack.length-1];
- if (func) {
- func.vars = func.vars.concat(node[1].map(function(varItem) { return varItem[0] }));
- }
- }
- }, function(node, type, stack) {
- if (type === 'toplevel' || type in FUNCTION) {
- // We know all of the variables that are seen here, proceed to do relevant replacements
- var allVars = stack.map(function(item) { return item ? item.vars : [] }).reduce(concatenator, []); // FIXME dictionary for speed?
- traverse(node, function(node2, type2, stack2) {
- // Be careful not to look into our inner functions. They have already been processed.
- if (sum(stack2) > 1 || (type === 'toplevel' && sum(stack2) === 1)) return;
- if (type2 in FUNCTION) stack2.push(1);
- return callback(node2, type2, allVars);
- }, null, []);
- }
- }, []);
+function traverseGenerated(ast, pre, post) {
+ traverseGeneratedFunctions(ast, function(func) {
+ traverse(func, pre, post);
+ });
}
function emptyNode() { // XXX do we need to create new nodes here? can't we reuse?
@@ -283,6 +249,40 @@ 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]);
+ } else if (node[0] === 'seq' && isEmptyNode(node[1])) {
+ return node[2];
+ }
+/*
+ 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,
@@ -295,58 +295,6 @@ function dumpSrc(ast) {
printErr(astToSrc(ast));
}
-// Undos closure's creation of global variables with values true, false,
-// undefined, null. These cut down on size, but do not affect gzip size
-// and make JS engine's lives slightly harder (?)
-function unGlobalize(ast) {
-
- throw 'this is deprecated!'; // and does not work with parallel compilation
-
- assert(ast[0] === 'toplevel');
- var values = {};
- // Find global renamings of the relevant values
- ast[1].forEach(function(node, i) {
- if (node[0] != 'var') return;
- node[1] = node[1].filter(function(varItem, j) {
- var ident = varItem[0];
- var value = varItem[1];
- if (!value) return true;
- var possible = false;
- if (jsonCompare(value, NULL_NODE) ||
- jsonCompare(value, UNDEFINED_NODE) ||
- jsonCompare(value, TRUE_NODE) ||
- jsonCompare(value, FALSE_NODE)) {
- possible = true;
- }
- if (!possible) return true;
- // Make sure there are no assignments to this variable. (This isn't fast, we traverse many times..)
- ast[1][i][1][j] = emptyNode();
- var assigned = false;
- traverseWithVariables(ast, function(node, type, allVars) {
- if (type === 'assign' && node[2][0] === 'name' && node[2][1] === ident) assigned = true;
- });
- ast[1][i][1][j] = [ident, value];
- if (!assigned) {
- values[ident] = value;
- return false;
- }
- return true;
- });
-
- if (node[1].length === 0) {
- ast[1][i] = emptyNode();
- }
- });
- traverseWithVariables(ast, function(node, type, allVars) {
- if (type === 'name') {
- var ident = node[1];
- if (ident in values && allVars.indexOf(ident) < 0) {
- return copy(values[ident]);
- }
- }
- });
-}
-
// Closure compiler, when inlining, will insert assignments to
// undefined for the shared variables. However, in compiled code
// - and in library/shell code too! - we should never rely on
@@ -418,7 +366,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('<', '<=', '>', '>=', '==', '===', '!=', '!==');
@@ -473,10 +421,12 @@ function simplifyExpressions(ast) {
var rerun = true;
while (rerun) {
rerun = false;
- traverse(ast, function process(node, type, stack) {
+ var stack = [];
+ traverse(ast, function process(node, type) {
if (type === 'binary' && node[1] === '|') {
if (node[2][0] === 'num' && node[3][0] === 'num') {
node[2][1] |= node[3][1];
+ stack.push(0);
return node[2];
}
var go = false;
@@ -509,7 +459,7 @@ function simplifyExpressions(ast) {
node[j] = result[j];
}
rerun = true;
- return process(result, result[0], stack);
+ return process(result, result[0]);
} else if (stack[i] === -1) {
break; // Too bad, we can't
}
@@ -525,7 +475,9 @@ function simplifyExpressions(ast) {
} else {
stack.push(-1); // This node is dangerous! Give up if you see this before you see '1'
}
- }, null, []);
+ }, function() {
+ stack.pop();
+ });
}
}
@@ -801,344 +753,165 @@ function simplifyExpressions(ast) {
simplifyIntegerConversions(func);
simplifyBitops(func);
joinAdditions(func);
- // simplifyZeroComp(func); TODO: investigate performance
simplifyNotComps(func);
+ // simplifyZeroComp(func); TODO: investigate performance
});
}
-// 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,
-// to greatly reduce the number of shift operations.
-// XXX this optimization is deprecated and currently invalid: does not handle overflows
-// or non-aligned (round numbers, x >> 2 is a multiple of 4). Both are ok to assume
-// for pointers (undefined behavior otherwise), but invalid in general, and we do
-// no sufficiently-well distinguish the cases.
-function optimizeShiftsInternal(ast, conservative) {
- var MAX_SHIFTS = 3;
- traverseGeneratedFunctions(ast, function(fun) {
- var funMore = true;
- var funFinished = {};
- while (funMore) {
- funMore = false;
- // Recognize variables and parameters
- var vars = {};
- function newVar(name, param, addUse) {
- if (!vars[name]) {
- vars[name] = {
- param: param,
- defs: addUse ? 1 : 0,
- uses: 0,
- timesShifted: [0, 0, 0, 0], // zero shifts of size 0, 1, 2, 3
- benefit: 0,
- primaryShift: -1
- };
- }
- }
- // params
- if (fun[2]) {
- fun[2].forEach(function(arg) {
- newVar(arg, true, true);
- });
- }
- // vars
- // XXX if var has >>=, ignore it here? That means a previous pass already optimized it
- var hasSwitch = traverse(fun, function(node, type) {
- if (type === 'var') {
- node[1].forEach(function(arg) {
- newVar(arg[0], false, arg[1]);
- });
- } else if (type === 'switch') {
- // The relooper can't always optimize functions, and we currently don't work with
- // switch statements when optimizing shifts. Bail.
- return true;
- }
- });
- if (hasSwitch) {
- break;
- }
- // uses and defs TODO: weight uses by being inside a loop (powers). without that, we
- // optimize for code size, not speed.
- traverse(fun, function(node, type, stack) {
- stack.push(node);
- if (type === 'name' && vars[node[1]] && stack[stack.length-2][0] != 'assign') {
- vars[node[1]].uses++;
- } else if (type === 'assign' && node[2][0] === 'name' && vars[node[2][1]]) {
- vars[node[2][1]].defs++;
- }
- }, null, []);
- // First, break up elements inside a shift. This lets us see clearly what to do next.
- traverse(fun, function(node, type) {
- if (type === 'binary' && node[1] === '>>' && node[3][0] === 'num') {
- var shifts = node[3][1];
- if (shifts <= MAX_SHIFTS) {
- // Push the >> inside the value elements
- function addShift(subNode) {
- if (subNode[0] === 'binary' && subNode[1] === '+') {
- subNode[2] = addShift(subNode[2]);
- subNode[3] = addShift(subNode[3]);
- return subNode;
- }
- if (subNode[0] === 'name' && !subNode[2]) { // names are returned with a shift, but we also note their being shifted
- var name = subNode[1];
- if (vars[name]) {
- vars[name].timesShifted[shifts]++;
- subNode[2] = true;
- }
- }
- return ['binary', '>>', subNode, ['num', shifts]];
- }
- return addShift(node[2]);
+
+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;
}
- }
- });
- traverse(fun, function(node, type) {
- if (node[0] === 'name' && node[2]) {
- return node.slice(0, 2); // clean up our notes
- }
- });
- // At this point, shifted expressions are split up, and we know who the vars are and their info, so we can decide
- // TODO: vars that depend on other vars
- for (var name in vars) {
- var data = vars[name];
- var totalTimesShifted = sum(data.timesShifted);
- if (totalTimesShifted === 0) {
- continue;
- }
- if (totalTimesShifted != Math.max.apply(null, data.timesShifted)) {
- // TODO: Handle multiple different shifts
- continue;
- }
- if (funFinished[name]) continue;
- // We have one shift size (and possible unshifted uses). Consider replacing this variable with a shifted clone. If
- // the estimated benefit is >0, we will do it
- if (data.defs === 1) {
- data.benefit = totalTimesShifted - 2*(data.defs + (data.param ? 1 : 0));
- }
- if (conservative) data.benefit = 0;
- if (data.benefit > 0) {
- funMore = true; // We will reprocess this function
- for (var i = 0; i < 4; i++) {
- if (data.timesShifted[i]) {
- data.primaryShift = i;
+ // 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;
}
}
- }
- }
- //printErr(JSON.stringify(vars));
- function cleanNotes() { // We need to mark 'name' nodes as 'processed' in some passes here; this cleans the notes up
- traverse(fun, function(node, type) {
- if (node[0] === 'name' && node[2]) {
- return node.slice(0, 2);
- }
- });
- }
- cleanNotes();
- // Apply changes
- function needsShift(name) {
- return vars[name] && vars[name].primaryShift >= 0;
- }
- for (var name in vars) { // add shifts for params and var's for all new variables
- var data = vars[name];
- if (needsShift(name)) {
- if (data.param) {
- fun[3].unshift(['var', [[name + '$s' + data.primaryShift, ['binary', '>>', ['name', name], ['num', data.primaryShift]]]]]);
- } else {
- fun[3].unshift(['var', [[name + '$s' + data.primaryShift]]]);
- }
- }
- }
- traverse(fun, function(node, type, stack) { // add shift to assignments
- stack.push(node);
- if (node[0] === 'assign' && node[1] === true && node[2][0] === 'name' && needsShift(node[2][1]) && !node[2][2]) {
- var name = node[2][1];
- var data = vars[name];
- var parent = stack[stack.length-3];
- var statements = getStatements(parent);
- assert(statements, 'Invalid parent for assign-shift: ' + dump(parent));
- var i = statements.indexOf(stack[stack.length-2]);
- statements.splice(i+1, 0, ['stat', ['assign', true, ['name', name + '$s' + data.primaryShift], ['binary', '>>', ['name', name, true], ['num', data.primaryShift]]]]);
- } else if (node[0] === 'var') {
- var args = node[1];
- for (var i = 0; i < args.length; i++) {
- var arg = args[i];
- var name = arg[0];
- var data = vars[name];
- if (arg[1] && needsShift(name)) {
- args.splice(i+1, 0, [name + '$s' + data.primaryShift, ['binary', '>>', ['name', name, true], ['num', data.primaryShift]]]);
+ 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];
}
- return node;
- }
- }, null, []);
- cleanNotes();
- traverse(fun, function(node, type, stack) { // replace shifted name with new variable
- stack.push(node);
- if (node[0] === 'binary' && node[1] === '>>' && node[2][0] === 'name' && needsShift(node[2][1]) && node[3][0] === 'num') {
- var name = node[2][1];
- var data = vars[name];
- var parent = stack[stack.length-2];
- // Don't modify in |x$sN = x >> 2|, in normal assigns and in var assigns
- if (parent[0] === 'assign' && parent[2][0] === 'name' && parent[2][1] === name + '$s' + data.primaryShift) return;
- if (parent[0] === name + '$s' + data.primaryShift) return;
- if (node[3][1] === data.primaryShift) {
- return ['name', name + '$s' + data.primaryShift];
- }
+ if (stats.length !== 1) break;
+ if (node[3]) simplifiedAnElse = true;
+ node[1] = ['conditional', node[1], other[1], ['num', 0]];
+ body = node[2] = other[2];
}
- }, null, []);
- cleanNotes();
- var SIMPLE_SHIFTS = set('<<', '>>');
- var more = true;
- while (more) { // combine shifts in the same direction as an optimization
- more = false;
- traverse(fun, function(node, type) {
- if (node[0] === 'binary' && node[1] in SIMPLE_SHIFTS && node[2][0] === 'binary' && node[2][1] === node[1] &&
- node[3][0] === 'num' && node[2][3][0] === 'num') { // do not turn a << b << c into a << b + c; while logically identical, it is slower
- more = true;
- return ['binary', node[1], node[2][2], ['num', node[3][1] + node[2][3][1]]];
- }
- });
}
- // Before recombining, do some additional optimizations
- traverse(fun, function(node, type) {
- // Apply constant shifts onto constants
- if (type === 'binary' && node[1] === '>>' && node[2][0] === 'num' && node[3][0] === 'num' && node[3][1] <= MAX_SHIFTS) {
- var subNode = node[2];
- var shifts = node[3][1];
- var result = subNode[1] / Math.pow(2, shifts);
- if (result % 1 === 0) {
- subNode[1] = result;
- return subNode;
+ });
+
+ 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;
}
}
- // Optimize the case of ($a*80)>>2 into ($a*20)|0
- if (type === 'binary' && node[1] in SIMPLE_SHIFTS &&
- node[2][0] === 'binary' && node[2][1] === '*') {
- var mulNode = node[2];
- if (mulNode[2][0] === 'num') {
- var temp = mulNode[2];
- mulNode[2] = mulNode[3];
- mulNode[3] = temp;
- }
- if (mulNode[3][0] === 'num') {
- if (node[1] === '<<') {
- mulNode[3][1] *= Math.pow(2, node[3][1]);
- node[1] = '|';
- node[3][1] = 0;
- return node;
- } else {
- if (mulNode[3][1] % Math.pow(2, node[3][1]) === 0) {
- mulNode[3][1] /= Math.pow(2, node[3][1]);
- node[1] = '|';
- node[3][1] = 0;
- return node;
- }
- }
+ });
+ 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;
}
}
- /* XXX - theoretically useful optimization(s), but commented out as not helpful in practice
- // Transform (x << 2) >> 2 into x & mask or something even simpler
- if (type === 'binary' && node[1] === '>>' && node[3][0] === 'num' &&
- node[2][0] === 'binary' && node[2][1] === '<<' && node[2][3][0] === 'num' && node[3][1] === node[2][3][1]) {
- var subNode = node[2];
- var shifts = node[3][1];
- var mask = ((0xffffffff << shifts) >>> shifts) | 0;
- return ['binary', '&', subNode[2], ['num', mask]];
- //return ['binary', '|', subNode[2], ['num', 0]];
- //return subNode[2];
- }
- */
});
- // Re-combine remaining shifts, to undo the breaking up we did before. may require reordering inside +'s
- traverse(fun, function(node, type, stack) {
- stack.push(node);
- if (type === 'binary' && node[1] === '+' && (stack[stack.length-2][0] != 'binary' || stack[stack.length-2][1] !== '+')) {
- // 'Flatten' added items
- var addedItems = [];
- function flatten(node) {
- if (node[0] === 'binary' && node[1] === '+') {
- flatten(node[2]);
- flatten(node[3]);
- } else {
- addedItems.push(node);
- }
- }
- flatten(node);
- var originalOrder = addedItems.slice();
- function key(node) { // a unique value for all relevant shifts for recombining, non-unique for stuff we don't need to bother with
- function originalOrderKey(item) {
- return -originalOrder.indexOf(item);
- }
- if (node[0] === 'binary' && node[1] in SIMPLE_SHIFTS) {
- if (node[3][0] === 'num' && node[3][1] <= MAX_SHIFTS) return 2*node[3][1] + (node[1] === '>>' ? 100 : 0); // 0-106
- return (node[1] === '>>' ? 20000 : 10000) + originalOrderKey(node);
- }
- if (node[0] === 'num') return -20000 + node[1];
- return -10000 + originalOrderKey(node); // Don't modify the original order if we don't modify anything
- }
- for (var i = 0; i < addedItems.length; i++) {
- if (addedItems[i][0] === 'string') return; // this node is not relevant for us
- }
- addedItems.sort(function(node1, node2) {
- return key(node1) - key(node2);
- });
- // Regenerate items, now sorted
- var i = 0;
- while (i < addedItems.length-1) { // re-combine inside addedItems
- var k = key(addedItems[i]), k1 = key(addedItems[i+1]);
- if (k === k1 && k >= 0 && k1 <= 106) {
- addedItems[i] = ['binary', addedItems[i][1], ['binary', '+', addedItems[i][2], addedItems[i+1][2]], addedItems[i][3]];
- addedItems.splice(i+1, 1);
- } else {
- i++;
- }
- }
- var num = 0;
- for (i = 0; i < addedItems.length; i++) { // combine all numbers into one
- if (addedItems[i][0] === 'num') {
- num += addedItems[i][1];
- addedItems.splice(i, 1);
- i--;
- }
- }
- if (num != 0) { // add the numbers into an existing shift, we
- // prefer (x+5)>>7 over (x>>7)+5 , since >>'s result is known to be 32-bit and is more easily optimized.
- // Also, in the former we can avoid the parentheses, which saves a little space (the number will be bigger,
- // so it might take more space, but normally at most one more digit).
- var added = false;
- for (i = 0; i < addedItems.length; i++) {
- if (addedItems[i][0] === 'binary' && addedItems[i][1] === '>>' && addedItems[i][3][0] === 'num' && addedItems[i][3][1] <= MAX_SHIFTS) {
- addedItems[i] = ['binary', '>>', ['binary', '+', addedItems[i][2], ['num', num << addedItems[i][3][1]]], addedItems[i][3]];
- added = 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
+ }
+ }
+ }
+ }
}
}
- if (!added) {
- addedItems.unshift(['num', num]);
- }
- }
- var ret = addedItems.pop();
- while (addedItems.length > 0) { // re-create AST from addedItems
- ret = ['binary', '+', ret, addedItems.pop()];
}
- return ret;
}
- }, null, []);
- // Note finished variables
- for (var name in vars) {
- funFinished[name] = true;
- }
+ }, function(node, type) {
+ if (type === 'while') inLoop--;
+ });
}
});
}
-function optimizeShiftsConservative(ast) {
- optimizeShiftsInternal(ast, true);
-}
-
-function optimizeShiftsAggressive(ast) {
- optimizeShiftsInternal(ast, false);
-}
-
// We often have branchings that are simplified so one end vanishes, and
// we then get
// if (!(x < 5))
@@ -1165,6 +938,10 @@ function simplifyNotCompsDirect(node) {
if (!simplifyNotCompsPass) return node;
}
+function flipCondition(cond) {
+ return simplifyNotCompsDirect(['unary-prefix', '!', cond]);
+}
+
var simplifyNotCompsPass = false;
function simplifyNotComps(ast) {
@@ -1285,6 +1062,7 @@ function vacuum(ast) {
traverseGeneratedFunctions(ast, function(node) {
vacuumInternal(node);
simplifyNotComps(node);
+ removeEmptySubNodes(node);
});
}
@@ -1430,7 +1208,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];
}
@@ -1562,6 +1340,7 @@ function unVarify(vars, ret) { // transform var x=1, y=2 etc. into (x=1, y=2), i
var ASM_INT = 0;
var ASM_DOUBLE = 1;
var ASM_FLOAT = 2;
+var ASM_NONE = 3;
function detectAsmCoercion(node, asmInfo) {
// for params, +x vs x|0, for vars, 0.0 vs 0
@@ -1569,6 +1348,7 @@ function detectAsmCoercion(node, asmInfo) {
if (node[0] === 'unary-prefix') return ASM_DOUBLE;
if (node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'Math_fround') return ASM_FLOAT;
if (asmInfo && node[0] == 'name') return getAsmType(node[1], asmInfo);
+ if (node[0] === 'name') return ASM_NONE;
return ASM_INT;
}
@@ -1577,7 +1357,8 @@ function makeAsmCoercion(node, type) {
case ASM_INT: return ['binary', '|', node, ['num', 0]];
case ASM_DOUBLE: return ['unary-prefix', '+', node];
case ASM_FLOAT: return ['call', ['name', 'Math_fround'], [node]];
- default: throw 'wha? ' + JSON.stringify([node, type]) + new Error().stack;
+ case ASM_NONE: return node; // non-validating code, emit nothing
+ default: throw 'whaa?';
}
}
@@ -1688,6 +1469,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++;
@@ -1696,26 +1482,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;
@@ -1974,7 +1755,7 @@ function registerize(ast) {
// 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).
var varRegs = {}; // maps variables to the register they will use all their life
- var freeRegsClasses = asm ? [[], [], []] : []; // two classes for asm, one otherwise XXX - hardcoded length
+ var freeRegsClasses = asm ? [[], [], [], []] : []; // two classes for asm, one otherwise XXX - hardcoded length
var nextReg = 1;
var fullNames = {};
var loopRegs = {}; // for each loop nesting level, the list of bound variables
@@ -2130,8 +1911,8 @@ function registerizeHarder(ast) {
// Utilities for allocating register variables.
// We need distinct register pools for each type of variable.
- var allRegsByType = [{}, {}, {}];
- var regPrefixByType = ['i', 'd', 'f'];
+ var allRegsByType = [{}, {}, {}, {}];
+ var regPrefixByType = ['i', 'd', 'f', 'n'];
var nextReg = 1;
function createReg(forName) {
@@ -3719,6 +3500,9 @@ function eliminate(ast, memSafe) {
node[0] = 'toplevel';
node[1] = [];
}
+ } else if (type === 'assign' && node[1] === 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
+ return emptyNode();
}
}, function(node, type) {
// post
@@ -3766,7 +3550,7 @@ function eliminate(ast, memSafe) {
}
}
}
- if (loopers.length < assigns.length) return; // TODO: handle the case where can can just eliminate one. (we can't optimize the break, but we can remove the var at least)
+ if (loopers.length === 0) return;
for (var l = 0; l < loopers.length; l++) {
var looper = loopers[l];
var helper = helpers[l];
@@ -3818,9 +3602,24 @@ function eliminate(ast, memSafe) {
// simplify the if. we remove the if branch, leaving only the else
if (flip) {
last[1] = simplifyNotCompsDirect(['unary-prefix', '!', last[1]]);
+ var temp = last[2];
last[2] = last[3];
+ last[3] = temp;
+ }
+ if (loopers.length === assigns.length) {
+ last.pop();
+ } else {
+ var elseStats = getStatements(last[3]);
+ for (var i = 0; i < elseStats.length; i++) {
+ var stat = elseStats[i];
+ if (stat[0] === 'stat') stat = stat[1];
+ if (stat[0] === 'assign' && stat[2][0] === 'name') {
+ if (loopers.indexOf(stat[2][1]) >= 0) {
+ elseStats[i] = emptyNode();
+ }
+ }
+ }
}
- last.pop();
}
}
}
@@ -3878,6 +3677,8 @@ function eliminate(ast, memSafe) {
}
new ExpressionOptimizer(ast).run();
}
+
+ removeAllEmptySubNodes(ast);
}
function eliminateMemSafe(ast) {
@@ -4248,6 +4049,8 @@ function aggressiveVariableEliminationInternal(func, asmData) {
}
}
});
+
+ removeAllEmptySubNodes(func);
}
function aggressiveVariableElimination(ast) {
@@ -4526,10 +4329,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] + '