diff options
Diffstat (limited to 'tools/js-optimizer.js')
-rw-r--r-- | tools/js-optimizer.js | 3637 |
1 files changed, 3192 insertions, 445 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 09791150..f9be66df 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -11,6 +11,7 @@ // *** Environment setup code *** var arguments_ = []; +var debug = false; var ENVIRONMENT_IS_NODE = typeof process === 'object'; var ENVIRONMENT_IS_WEB = typeof window === 'object'; @@ -102,7 +103,7 @@ function globalEval(x) { eval.call(null, x); } -if (typeof load == 'undefined' && typeof read != 'undefined') { +if (typeof load === 'undefined' && typeof read != 'undefined') { this['load'] = function(f) { globalEval(read(f)); }; @@ -134,6 +135,12 @@ var ASSIGN_OR_ALTER = set('assign', 'unary-postfix', 'unary-prefix'); var CONTROL_FLOW = set('do', 'while', 'for', 'if', 'switch'); var NAME_OR_NUM = set('name', 'num'); var ASSOCIATIVE_BINARIES = set('+', '*', '|', '&', '^'); +var ALTER_FLOW = set('break', 'continue', 'return'); + +var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch'); +var CONTINUE_CAPTURERS = LOOP; + +var FUNCTIONS_THAT_ALWAYS_THROW = set('abort', '___resumeException', '___cxa_throw', '___cxa_rethrow'); var NULL_NODE = ['name', 'null']; var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]]; @@ -143,17 +150,18 @@ var FALSE_NODE = ['unary-prefix', '!', ['num', 1]]; var GENERATED_FUNCTIONS_MARKER = '// EMSCRIPTEN_GENERATED_FUNCTIONS'; var generatedFunctions = false; // whether we have received only generated functions -var minifierInfo = null; +var extraInfo = null; function srcToAst(src) { - return uglify.parser.parse(src); + return uglify.parser.parse(src, false, debug); } -function astToSrc(ast, compress) { +function astToSrc(ast, minifyWhitespace) { return uglify.uglify.gen_code(ast, { + debug: debug, ascii_only: true, - beautify: !compress, - indent_level: 2 + beautify: !minifyWhitespace, + indent_level: 1 }); } @@ -162,10 +170,10 @@ function astToSrc(ast, compress) { function traverseChildren(node, traverse, pre, post, stack) { for (var i = 0; i < node.length; i++) { var subnode = node[i]; - if (typeof subnode == 'object' && subnode && subnode.length) { + if (Array.isArray(subnode)) { var subresult = traverse(subnode, pre, post, stack); - if (subresult == true) return true; - if (subresult !== null && typeof subresult == 'object') node[i] = subresult; + if (subresult === true) return true; + if (subresult !== null && typeof subresult === 'object') node[i] = subresult; } } } @@ -186,16 +194,16 @@ function traverseChildren(node, traverse, pre, post, stack) { // was stopped, true. Otherwise undefined. function traverse(node, pre, post, stack) { var type = node[0], result, len; - var relevant = typeof type == 'string'; + var relevant = typeof type === 'string'; if (relevant) { if (stack) len = stack.length; var result = pre(node, type, stack); - if (result == true) return true; - if (result !== null && typeof result == 'object') node = result; // Continue processing on this node - if (stack && len == stack.length) stack.push(0); + 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, stack) === true) return true; } if (relevant) { if (post) { @@ -211,7 +219,7 @@ function traverse(node, pre, post, stack) { function traverseGenerated(ast, pre, post, stack) { assert(generatedFunctions); traverse(ast, function(node) { - if (node[0] == 'defun') { + if (node[0] === 'defun') { traverse(node, pre, post, stack); return null; } @@ -220,13 +228,13 @@ function traverseGenerated(ast, pre, post, stack) { function traverseGeneratedFunctions(ast, callback) { assert(generatedFunctions); - if (ast[0] == 'toplevel') { + if (ast[0] === 'toplevel') { var stats = ast[1]; for (var i = 0; i < stats.length; i++) { var curr = stats[i]; - if (curr[0] == 'defun') callback(curr); + if (curr[0] === 'defun') callback(curr); } - } else if (ast[0] == 'defun') { + } else if (ast[0] === 'defun') { callback(ast); } } @@ -236,7 +244,7 @@ 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') { + } else if (type === 'var') { // Find our function, add our vars var func = stack[stack.length-1]; if (func) { @@ -244,12 +252,12 @@ function traverseWithVariables(ast, callback) { } } }, function(node, type, stack) { - if (type == 'toplevel' || type in FUNCTION) { + 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 (sum(stack2) > 1 || (type === 'toplevel' && sum(stack2) === 1)) return; if (type2 in FUNCTION) stack2.push(1); return callback(node2, type2, allVars); }, null, []); @@ -262,7 +270,17 @@ function emptyNode() { // XXX do we need to create new nodes here? can't we reus } function isEmptyNode(node) { - return node.length == 2 && node[0] == 'toplevel' && node[1].length == 0; + return node.length === 2 && node[0] === 'toplevel' && node[1].length === 0; +} + +function clearEmptyNodes(list) { + for (var i = 0; i < list.length;) { + if (isEmptyNode(list[i]) || (list[i][0] === 'stat' && isEmptyNode(list[i][1]))) { + list.splice(i, 1); + } else { + i++; + } + } } // Passes @@ -284,7 +302,7 @@ function unGlobalize(ast) { throw 'this is deprecated!'; // and does not work with parallel compilation - assert(ast[0] == 'toplevel'); + assert(ast[0] === 'toplevel'); var values = {}; // Find global renamings of the relevant values ast[1].forEach(function(node, i) { @@ -305,7 +323,7 @@ function unGlobalize(ast) { 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; + if (type === 'assign' && node[2][0] === 'name' && node[2][1] === ident) assigned = true; }); ast[1][i][1][j] = [ident, value]; if (!assigned) { @@ -315,12 +333,12 @@ function unGlobalize(ast) { return true; }); - if (node[1].length == 0) { + if (node[1].length === 0) { ast[1][i] = emptyNode(); } }); traverseWithVariables(ast, function(node, type, allVars) { - if (type == 'name') { + if (type === 'name') { var ident = node[1]; if (ident in values && allVars.indexOf(ident) < 0) { return copy(values[ident]); @@ -343,9 +361,9 @@ function unGlobalize(ast) { // is now explicit. function removeAssignsToUndefined(ast) { traverse(ast, function(node, type) { - if (type == 'assign' && jsonCompare(node[3], ['unary-prefix', 'void', ['num', 0]])) { + if (type === 'assign' && jsonCompare(node[3], ['unary-prefix', 'void', ['num', 0]])) { return emptyNode(); - } else if (type == 'var') { + } else if (type === 'var') { node[1] = node[1].map(function(varItem, j) { var ident = varItem[0]; var value = varItem[1]; @@ -359,10 +377,10 @@ function removeAssignsToUndefined(ast) { while (modified) { modified = false; traverse(ast, function(node, type) { - if (type == 'assign' && jsonCompare(node[3], emptyNode())) { + if (type === 'assign' && jsonCompare(node[3], emptyNode())) { modified = true; return emptyNode(); - } else if (type == 'var') { + } else if (type === 'var') { node[1] = node[1].map(function(varItem, j) { var ident = varItem[0]; var value = varItem[1]; @@ -380,19 +398,19 @@ function removeAssignsToUndefined(ast) { // are actually necessary. It's easy to clean those up now. function removeUnneededLabelSettings(ast) { traverse(ast, function(node, type) { - if (type == 'defun') { // all of our compiled code is in defun nodes + if (type === 'defun') { // all of our compiled code is in defun nodes // Find all checks var checked = {}; traverse(node, function(node, type) { - if (type == 'binary' && node[1] == '==' && node[2][0] == 'name' && node[2][1] == 'label') { - assert(node[3][0] == 'num'); + if (type === 'binary' && node[1] === '==' && node[2][0] === 'name' && node[2][1] === 'label') { + assert(node[3][0] === 'num'); checked[node[3][1]] = 1; } }); // Remove unneeded sets traverse(node, function(node, type) { - if (type == 'assign' && node[2][0] == 'name' && node[2][1] == 'label') { - assert(node[3][0] == 'num'); + if (type === 'assign' && node[2][0] === 'name' && node[2][1] === 'label') { + assert(node[3][0] === 'num'); if (!(node[3][1] in checked)) return emptyNode(); } }); @@ -402,20 +420,34 @@ function removeUnneededLabelSettings(ast) { // Various expression simplifications. Pre run before closure (where we still have metadata), Post run after. -function simplifyExpressionsPre(ast) { - // Look for (x&A)<<B>>B and replace it with X&A if possible. - function simplifySignExtends(ast) { - traverseGenerated(ast, function(node, type) { - 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 USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^'); +var COMPARE_OPS = set('<', '<=', '>', '>=', '==', '===', '!=', '!=='); + +function simplifyExpressions(ast) { + // Simplify common expressions used to perform integer conversion operations + // in cases where no conversion is needed. + function simplifyIntegerConversions(ast) { + traverse(ast, function(node, type) { + 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]) { + // Transform (x&A)<<B>>B to X&A. var innerNode = node[2][2]; var shifts = node[3][1]; - if (innerNode[0] == 'binary' && innerNode[1] == '&' && innerNode[3][0] == 'num') { + if (innerNode[0] === 'binary' && innerNode[1] === '&' && innerNode[3][0] === 'num') { var mask = innerNode[3][1]; - if (mask << shifts >> shifts == mask) { + if (mask << shifts >> shifts === mask) { return innerNode; } } + } else if (type === 'binary' && node[1] === '&' && node[3][0] === 'num') { + // Rewrite (X < Y) & 1 to (X < Y)|0. (Subsequent passes will eliminate + // the |0 if possible.) + var input = node[2]; + var amount = node[3][1]; + if (input[0] === 'binary' && (input[1] in COMPARE_OPS) && amount == 1) { + node[1] = '|'; + node[3][1] = 0; + } } }); } @@ -427,20 +459,48 @@ function simplifyExpressionsPre(ast) { // 'useful' mathops already |0 anyhow. function simplifyBitops(ast) { - var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^'); - var SAFE_BINARY_OPS = set('+', '-', '*'); // division is unsafe as it creates non-ints in JS; mod is unsafe as signs matter so we can't remove |0's + var SAFE_BINARY_OPS; + if (asm) { + SAFE_BINARY_OPS = set('+', '-'); // 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 + } else { + SAFE_BINARY_OPS = set('+', '-', '*'); + } + var COERCION_REQUIRING_OPS = set('sub', 'unary-prefix'); // ops that in asm must be coerced right away + var COERCION_REQUIRING_BINARIES = set('*', '/', '%'); // binary ops that in asm must be coerced var ZERO = ['num', 0]; - var rerun = true; - while (rerun) { - rerun = false; - traverseGenerated(ast, function process(node, type, stack) { - if (type == 'binary' && node[1] == '|') { - if (node[2][0] == 'num' && node[3][0] == 'num') { - return ['num', node[2][1] | node[3][1]]; - } else if (jsonCompare(node[2], ZERO) || jsonCompare(node[3], ZERO)) { + + function removeMultipleOrZero() { + var rerun = true; + while (rerun) { + rerun = false; + traverse(ast, function process(node, type, stack) { + if (type === 'binary' && node[1] === '|') { + if (node[2][0] === 'num' && node[3][0] === 'num') { + node[2][1] |= node[3][1]; + return node[2]; + } + var go = false; + if (jsonCompare(node[2], ZERO)) { + // canonicalize order + var temp = node[3]; + node[3] = node[2]; + node[2] = temp; + go = true; + } else if (jsonCompare(node[3], ZERO)) { + go = true; + } + if (!go) { + stack.push(1); + return; + } // We might be able to remove this correction for (var i = stack.length-1; i >= 0; i--) { - if (stack[i] == 1) { + if (stack[i] >= 1) { + if (asm) { + if (stack[stack.length-1] < 2 && node[2][0] === 'call') break; // we can only remove multiple |0s on these + if (stack[stack.length-1] < 1 && (node[2][0] in COERCION_REQUIRING_OPS || + (node[2][0] === 'binary' && node[2][1] in COERCION_REQUIRING_BINARIES))) break; // we can remove |0 or >>2 + } // we will replace ourselves with the non-zero side. Recursively process that node. var result = jsonCompare(node[2], ZERO) ? node[3] : node[2], other; // replace node in-place @@ -450,49 +510,55 @@ function simplifyExpressionsPre(ast) { } rerun = true; return process(result, result[0], stack); - } else if (stack[i] == -1) { + } else if (stack[i] === -1) { break; // Too bad, we can't - } else if (asm) { - break; // we must keep a coercion right on top of a heap access in asm mode } } + stack.push(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' && node[1] in USEFUL_BINARY_OPS) { + stack.push(1); + } else if ((type === 'binary' && node[1] in SAFE_BINARY_OPS) || type === 'num' || type === 'name') { + stack.push(0); // This node is safe in that it does not interfere with this optimization + } else if (type === 'unary-prefix' && node[1] === '~') { + stack.push(1); + } else { + stack.push(-1); // This node is dangerous! Give up if you see this before you see '1' } - stack.push(1); // 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' && node[1] in USEFUL_BINARY_OPS) { - stack.push(1); - } else if ((type == 'binary' && node[1] in SAFE_BINARY_OPS) || type == 'num' || type == 'name') { - stack.push(0); // This node is safe in that it does not interfere with this optimization - } else { - stack.push(-1); // This node is dangerous! Give up if you see this before you see '1' - } - }, null, []); + }, null, []); + } } + removeMultipleOrZero(); + // & and heap-related optimizations var heapBits, heapUnsigned; function parseHeap(name) { if (name.substr(0, 4) != 'HEAP') return false; - heapUnsigned = name[4] == 'U'; + heapUnsigned = name[4] === 'U'; heapBits = parseInt(name.substr(heapUnsigned ? 5 : 4)); return true; } - traverseGenerated(ast, function(node, type) { - if (type == 'binary' && node[1] == '&' && node[3][0] == 'num') { - if (node[2][0] == 'num') return ['num', node[2][1] & node[3][1]]; + var hasTempDoublePtr = false, rerunOrZeroPass = false; + + traverse(ast, function(node, type) { + if (type === 'name') { + if (node[1] === 'tempDoublePtr') hasTempDoublePtr = true; + } else if (type === 'binary' && node[1] === '&' && node[3][0] === 'num') { + if (node[2][0] === 'num') return ['num', node[2][1] & node[3][1]]; var input = node[2]; var amount = node[3][1]; - if (input[0] == 'binary' && input[1] == '&' && input[3][0] == 'num') { + if (input[0] === 'binary' && input[1] === '&' && input[3][0] === 'num') { // Collapse X & 255 & 1 node[3][1] = amount & input[3][1]; node[2] = input[2]; - } else if (input[0] == 'sub' && input[1][0] == 'name') { + } else if (input[0] === 'sub' && input[1][0] === 'name') { // HEAP8[..] & 255 => HEAPU8[..] var name = input[1][1]; if (parseHeap(name)) { - if (amount == Math.pow(2, heapBits)-1) { + if (amount === Math.pow(2, heapBits)-1) { if (!heapUnsigned) { input[1][1] = 'HEAPU' + heapBits; // make unsigned } @@ -506,29 +572,179 @@ function simplifyExpressionsPre(ast) { } } } - } else if (type == 'binary' && node[1] == '>>' && node[3][0] == 'num' && - node[2][0] == 'binary' && node[2][1] == '<<' && node[2][3][0] == 'num' && - node[2][2][0] == 'sub' && node[2][2][1][0] == 'name') { + } else if (type === 'binary' && node[1] === '^') { + // 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] === '-' && node[3][2][0] === 'num' && + node[3][2][1] === 1 && + !(node[2][0] == 'unary-prefix' && node[2][1] == '~')) { // avoid creating ~~~ which is confusing for asm given the role of ~~ + return ['unary-prefix', '~', node[2]]; + } + } else if (type === 'binary' && node[1] === '>>' && node[3][0] === 'num' && + node[2][0] === 'binary' && node[2][1] === '<<' && 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 - // TODO: run this before | 0 | 0 removal, because we generate | 0 var amount = node[3][1]; var name = node[2][2][1][1]; - if (amount == node[2][3][1] && parseHeap(name)) { - if (heapBits == 32 - amount) { + if (amount === node[2][3][1] && parseHeap(name)) { + if (heapBits === 32 - amount) { node[2][2][1][1] = 'HEAP' + heapBits; node[1] = '|'; node[2] = node[2][2]; node[3][1] = 0; + rerunOrZeroPass = true; return node; } } + } else if (type === 'assign') { + // optimizations for assigning into HEAP32 specifically + if (node[1] === 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] === '|') { + if (node[3][2][0] === 'num' && node[3][2][1] === 0 && node[3][3][0] != 'call') { + node[3] = node[3][3]; + } else if (node[3][3][0] === 'num' && node[3][3][1] === 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] === '&' && node[3][3][0] == 'num' && node[3][3][1] == 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] === '&' && node[3][3][0] == 'num' && node[3][3][1] == 0xffff) { + node[3] = node[3][2]; + } + } + } + var value = node[3]; + if (value[0] === 'binary' && value[1] === '|') { + // canonicalize order of |0 to end + if (value[2][0] === 'num' && value[2][1] === 0) { + var 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' && value[2][2][1] in USEFUL_BINARY_OPS) { + node[3] = value[2]; + } + } + } else if (type == 'sub' && node[1][0] == 'name' && /^FUNCTION_TABLE.*/.exec(node[1][1])) { + return null; // do not traverse subchildren here, we should not collapse 55 & 126. TODO: optimize this into a nonvirtual call (also because we lose some other opts here)! } }); + if (rerunOrZeroPass) removeMultipleOrZero(); + if (asm) { + if (hasTempDoublePtr) { + var asmData = normalizeAsm(ast); + traverse(ast, function(node, type) { + if (type === 'assign') { + if (node[1] === 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; + var 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] === 'tempDoublePtr') { + // transform to HEAPF32[$45 >> 2] = ($14 < $28 ? $14 : $28) - $42; + node[2][1][1] = '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] === 'tempDoublePtr' && + 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] = 'HEAPF32'; + return makeAsmCoercion(node[1][3], detectAsmCoercion(node[2])); + } else { + node[1][3][1][1] = 'HEAP32'; + return ['binary', '|', node[1][3], ['num', 0]]; + } + } + } + }); + + // 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 + var bitcastVars = {}; + traverse(ast, function(node, type) { + if (type === 'assign' && node[1] === true && node[2][0] === 'name') { + var 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] === 'tempDoublePtr') { + var name = node[2][1]; + if (!bitcastVars[name]) bitcastVars[name] = { + define_HEAP32: 0, define_HEAPF32: 0, use_HEAP32: 0, use_HEAPF32: 0, bad: false, namings: 0, defines: [], uses: [] + }; + bitcastVars[name]['define_' + value[1][2][1][1]]++; + bitcastVars[name].defines.push(node); + } + } + }); + traverse(ast, function(node, type) { + if (type === 'name' && bitcastVars[node[1]]) { + bitcastVars[node[1]].namings++; + } else if (type === 'assign' && node[1] === true) { + var value = node[3]; + if (value[0] === 'name') { + var name = value[1]; + if (bitcastVars[name]) { + var target = node[2]; + if (target[0] === 'sub' && target[1][0] === 'name' && (target[1][1] === 'HEAP32' || target[1][1] === 'HEAPF32')) { + bitcastVars[name]['use_' + target[1][1]]++; + bitcastVars[name].uses.push(node); + } + } + } + } + }); + for (var v in bitcastVars) { + var info = bitcastVars[v]; + // 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 && + v in asmData.vars && info.namings === info.define_HEAP32+info.define_HEAPF32+info.use_HEAP32+info.use_HEAPF32) { + var correct = info.use_HEAP32 ? 'HEAPF32' : 'HEAP32'; + info.defines.forEach(function(define) { + define[3] = define[3][1][3]; + if (correct === 'HEAP32') { + define[3] = ['binary', '|', define[3], ['num', 0]]; + } else { + define[3] = makeAsmCoercion(define[3], asmPreciseF32 ? ASM_FLOAT : ASM_DOUBLE); + } + // do we want a simplifybitops on the new values here? + }); + info.uses.forEach(function(use) { + use[2][1][1] = correct; + }); + var correctType; + switch(asmData.vars[v]) { + case ASM_INT: correctType = asmPreciseF32 ? ASM_FLOAT : ASM_DOUBLE; break; + case ASM_FLOAT: case ASM_DOUBLE: correctType = ASM_INT; break; + } + asmData.vars[v] = correctType; + } + } + denormalizeAsm(ast, asmData); + } + // optimize num >> num, in asm we need this here since we do not run optimizeShifts - traverseGenerated(ast, function(node, type) { - if (type == 'binary' && node[1] == '>>' && node[2][0] == 'num' && node[3][0] == 'num') { + traverse(ast, function(node, type) { + if (type === 'binary' && node[1] === '>>' && node[2][0] === 'num' && node[3][0] === 'num') { node[0] = 'num'; node[1] = node[2][1] >> node[3][1]; node.length = 2; @@ -543,16 +759,17 @@ function simplifyExpressionsPre(ast) { var rerun = true; while (rerun) { rerun = false; - traverseGenerated(ast, function(node, type) { - if (type == 'binary' && node[1] == '+') { - if (node[2][0] == 'num' && node[3][0] == 'num') { + traverse(ast, function(node, type) { + if (type === 'binary' && node[1] === '+') { + if (node[2][0] === 'num' && node[3][0] === 'num') { rerun = true; - return ['num', node[2][1] + node[3][1]]; + node[2][1] += node[3][1]; + return node[2]; } for (var i = 2; i <= 3; i++) { var ii = 5-i; for (var j = 2; j <= 3; j++) { - if (node[i][0] == 'num' && node[ii][0] == 'binary' && node[ii][1] == '+' && node[ii][j][0] == 'num') { + if (node[i][0] === 'num' && node[ii][0] === 'binary' && node[ii][1] === '+' && node[ii][j][0] === 'num') { rerun = true; node[ii][j][1] += node[i][1]; return node[ii]; @@ -564,15 +781,15 @@ function simplifyExpressionsPre(ast) { } } - // if (x == 0) can be if (!x), etc. + // if (x === 0) can be if (!x), etc. function simplifyZeroComp(ast) { - traverseGenerated(ast, function(node, type) { + traverse(ast, function(node, type) { var binary; - if (type == 'if' && (binary = node[1])[0] == 'binary') { - if ((binary[1] == '!=' || binary[1] == '!==') && binary[3][0] == 'num' && binary[3][1] == 0) { + if (type === 'if' && (binary = node[1])[0] === 'binary') { + if ((binary[1] === '!=' || binary[1] === '!==') && binary[3][0] === 'num' && binary[3][1] === 0) { node[1] = binary[2]; return node; - } else if ((binary[1] == '==' || binary[1] == '===') && binary[3][0] == 'num' && binary[3][1] == 0) { + } else if ((binary[1] === '==' || binary[1] === '===') && binary[3][0] === 'num' && binary[3][1] === 0) { node[1] = ['unary-prefix', '!', binary[2]]; return node; } @@ -580,47 +797,23 @@ function simplifyExpressionsPre(ast) { }); } - function asmOpts(ast) { - // 1. Add final returns when necessary - // 2. Remove unneeded coercions on function calls that have no targets (eliminator removed it) - traverseGeneratedFunctions(ast, function(fun) { - var returnType = null; - traverse(fun, function(node, type) { - if (type == 'return' && node[1]) { - returnType = detectAsmCoercion(node[1]); - } else if (type == 'stat') { - var inner = node[1]; - if ((inner[0] == 'binary' && inner[1] in ASSOCIATIVE_BINARIES && inner[2][0] == 'call' && inner[3][0] == 'num') || - (inner[0] == 'unary-prefix' && inner[1] == '+' && inner[2][0] == 'call')) { - node[1] = inner[2]; - } - } - }); - // Add a final return if one is missing. - if (returnType !== null) { - var stats = getStatements(fun); - var last = stats[stats.length-1]; - if (last[0] != 'return') { - var returnValue = ['num', 0]; - if (returnType == ASM_DOUBLE) returnValue = ['unary-prefix', '+', returnValue]; - stats.push(['return', returnValue]); - } - } - }); - } - - simplifySignExtends(ast); - simplifyBitops(ast); - joinAdditions(ast); - // simplifyZeroComp(ast); TODO: investigate performance - if (asm) asmOpts(ast); + traverseGeneratedFunctions(ast, function(func) { + simplifyIntegerConversions(func); + simplifyBitops(func); + joinAdditions(func); + // simplifyZeroComp(func); TODO: investigate performance + simplifyNotComps(func); + }); } // 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. -// TODO: when shifting a variable, if there are other uses, keep an unshifted version too, to prevent slowdowns? +// 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) { @@ -651,11 +844,11 @@ function optimizeShiftsInternal(ast, conservative) { // 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') { + if (type === 'var') { node[1].forEach(function(arg) { newVar(arg[0], false, arg[1]); }); - } else if (type == 'switch') { + } 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; @@ -668,25 +861,25 @@ function optimizeShiftsInternal(ast, conservative) { // 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') { + 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]]) { + } 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') { + 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] == '+') { + 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 + 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]++; @@ -700,7 +893,7 @@ function optimizeShiftsInternal(ast, conservative) { } }); traverse(fun, function(node, type) { - if (node[0] == 'name' && node[2]) { + if (node[0] === 'name' && node[2]) { return node.slice(0, 2); // clean up our notes } }); @@ -709,7 +902,7 @@ function optimizeShiftsInternal(ast, conservative) { for (var name in vars) { var data = vars[name]; var totalTimesShifted = sum(data.timesShifted); - if (totalTimesShifted == 0) { + if (totalTimesShifted === 0) { continue; } if (totalTimesShifted != Math.max.apply(null, data.timesShifted)) { @@ -719,7 +912,7 @@ function optimizeShiftsInternal(ast, conservative) { 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) { + if (data.defs === 1) { data.benefit = totalTimesShifted - 2*(data.defs + (data.param ? 1 : 0)); } if (conservative) data.benefit = 0; @@ -735,7 +928,7 @@ function optimizeShiftsInternal(ast, conservative) { //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]) { + if (node[0] === 'name' && node[2]) { return node.slice(0, 2); } }); @@ -757,7 +950,7 @@ function optimizeShiftsInternal(ast, conservative) { } 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]) { + 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]; @@ -765,7 +958,7 @@ function optimizeShiftsInternal(ast, conservative) { 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') { + } else if (node[0] === 'var') { var args = node[1]; for (var i = 0; i < args.length; i++) { var arg = args[i]; @@ -781,14 +974,14 @@ function optimizeShiftsInternal(ast, conservative) { 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') { + 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' && |