diff options
Diffstat (limited to 'tools/js-optimizer.js')
| -rw-r--r-- | tools/js-optimizer.js | 396 |
1 files changed, 310 insertions, 86 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index c4585b84..9b8387be 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -136,6 +136,7 @@ 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 BITWISE = set('|', '&', '^'); var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch'); var CONTINUE_CAPTURERS = LOOP; @@ -387,14 +388,18 @@ function simplifyExpressions(ast) { 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; + } else if (type === 'binary' && (node[1] in BITWISE)) { + for (var i = 2; i <= 3; i++) { + var subNode = node[i]; + if (subNode[0] === 'binary' && subNode[1] === '&' && subNode[3][0] === 'num' && subNode[3][1] == 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. + var input = subNode[2]; + if (input[0] === 'binary' && (input[1] in COMPARE_OPS)) { + node[i] = input; + } + } } } }); @@ -749,11 +754,74 @@ function simplifyExpressions(ast) { }); } + function emitsBoolean(node) { + if (node[0] === 'num') { + return node[1] === 0 || node[1] === 1; + } + if (node[0] === 'binary') return node[1] in COMPARE_OPS; + if (node[0] === 'unary-prefix') return node[1] === '!'; + if (node[0] === '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. + function conditionalize(ast) { + var MIN_COST = 7; + traverse(ast, function(node, type) { + if (node[0] === 'binary' && (node[1] === '|' || node[1] === '&') && node[3][0] !== 'num' && node[2][0] !== 'num') { + // logical operator on two non-numerical values + var left = node[2]; + var right = node[3]; + if (!emitsBoolean(left) || !emitsBoolean(right)) return; + var leftEffects = hasSideEffects(left); + var 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 + var 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 + var leftCost = measureCost(left); + var rightCost = measureCost(right); + if (Math.max(leftCost, rightCost) < MIN_COST) return; // avoidable code is too cheap + // canonicalize with expensive code on the right + if (leftCost > rightCost) { + var temp = left; + left = right; + right = temp; + } + } + // worth it, perform conditionalization + var ret; + if (node[1] === '|') { + ret = ['conditional', left, ['num', 1], right]; + } else { // & + ret = ['conditional', left, right, ['num', 0]]; + } + if (left[0] === 'unary-prefix' && left[1] === '!') { + ret[1] = flipCondition(left); + var temp = ret[2]; + ret[2] = ret[3]; + ret[3] = temp; + } + return ret; + } + }); + } + traverseGeneratedFunctions(ast, function(func) { simplifyIntegerConversions(func); simplifyBitops(func); joinAdditions(func); simplifyNotComps(func); + conditionalize(func); // simplifyZeroComp(func); TODO: investigate performance }); } @@ -970,10 +1038,32 @@ function hasSideEffects(node) { // this is 99% incomplete! } return false; } + case 'conditional': return hasSideEffects(node[1]) || hasSideEffects(node[2]) || hasSideEffects(node[3]); default: 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 +function triviallySafeToMove(node, asmData) { + var ok = true; + traverse(node, function(node, type) { + switch (type) { + case 'stat': case 'binary': case 'unary-prefix': case 'assign': case 'num': + break; + case 'name': + if (!(node[1] in asmData.vars) && !(node[1] in asmData.params)) ok = false; + break; + case 'call': + if (callHasSideEffects(node)) ok = false; + break; + default: + ok = false; + } + }); + return ok; +} + // Clear out empty ifs and blocks, and redundant blocks/stats and so forth // Operates on generated functions only function vacuum(ast) { @@ -1342,13 +1432,21 @@ var ASM_DOUBLE = 1; var ASM_FLOAT = 2; var ASM_NONE = 3; -function detectAsmCoercion(node, asmInfo) { +var ASM_FLOAT_ZERO = null; // TODO: share the entire node? + +function detectAsmCoercion(node, asmInfo, inVarDef) { // for params, +x vs x|0, for vars, 0.0 vs 0 if (node[0] === 'num' && node[1].toString().indexOf('.') >= 0) return ASM_DOUBLE; 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; + if (node[0] === 'name') { + if (!inVarDef) return ASM_NONE; + // We are in a variable definition, where Math_fround(0) optimized into a global constant becomes f0 = Math_fround(0) + if (!ASM_FLOAT_ZERO) ASM_FLOAT_ZERO = node[1]; + else assert(ASM_FLOAT_ZERO === node[1]); + return ASM_FLOAT; + } return ASM_INT; } @@ -1366,7 +1464,13 @@ function makeAsmVarDef(v, type) { switch (type) { case ASM_INT: return [v, ['num', 0]]; case ASM_DOUBLE: return [v, ['unary-prefix', '+', ['num', 0]]]; - case ASM_FLOAT: return [v, ['call', ['name', 'Math_fround'], [['num', 0]]]]; + case ASM_FLOAT: { + if (ASM_FLOAT_ZERO) { + return [v, ['name', ASM_FLOAT_ZERO]]; + } else { + return [v, ['call', ['name', 'Math_fround'], [['num', 0]]]]; + } + } default: throw 'wha? ' + JSON.stringify([node, type]) + new Error().stack; } } @@ -1409,9 +1513,7 @@ function normalizeAsm(func) { var name = v[0]; var value = v[1]; if (!(name in data.vars)) { - assert(value[0] === 'num' || (value[0] === 'unary-prefix' && value[2][0] === 'num') // must be valid coercion no-op - || (value[0] === 'call' && value[1][0] === 'name' && value[1][1] === 'Math_fround')); - data.vars[name] = detectAsmCoercion(value); + data.vars[name] = detectAsmCoercion(value, null, true); v.length = 1; // make an un-assigning var } else { assert(j === 0, 'cannot break in the middle'); @@ -1425,22 +1527,6 @@ function normalizeAsm(func) { traverse(stats[i], function(node, type) { if (type === 'var') { assert(0, 'should be no vars to fix! ' + func[1] + ' : ' + JSON.stringify(node)); - /* - for (var j = 0; j < node[1].length; j++) { - var v = node[1][j]; - var name = v[0]; - var value = v[1]; - if (!(name in data.vars)) { - if (value[0] != 'name') { - data.vars[name] = detectAsmCoercion(value); // detect by coercion - } else { - var origin = value[1]; - data.vars[name] = data.vars[origin] || ASM_INT; // detect by origin variable, or assume int for non-locals - } - } - } - unVarify(node[1], node); - */ } else if (type === 'call' && node[1][0] === 'function') { assert(!node[1][1]); // anonymous functions only data.inlines.push(node[1]); @@ -2001,12 +2087,18 @@ function registerizeHarder(ast) { function pushActiveLabels(onContinue, onBreak) { // Push the target junctions for continuing/breaking a loop. // This should be called before traversing into a loop. - var newLabels = copy(activeLabels[activeLabels.length-1]); + var prevLabels = activeLabels[activeLabels.length-1]; + var newLabels = copy(prevLabels); newLabels[null] = [onContinue, onBreak]; if (nextLoopLabel) { newLabels[nextLoopLabel] = [onContinue, onBreak]; nextLoopLabel = null; } + // An unlabelled 'continue' should jump to innermost loop, + // ignoring any nested 'switch' statements. + if (onContinue === null && prevLabels[null]) { + newLabels[null][0] = prevLabels[null][0]; + } activeLabels.push(newLabels); } @@ -2156,18 +2248,30 @@ function registerizeHarder(ast) { break; case 'conditional': isInExpr++; - buildFlowGraph(node[1]); - var jEnter = markJunction(); - var jExit = addJunction(); - if (node[2]) { - buildFlowGraph(node[2]); - } - joinJunction(jExit); - setJunction(jEnter); - if (node[3]) { - buildFlowGraph(node[3]); + // 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]); + var jEnter = markJunction(); + var jExit = addJunction(); + if (node[2]) { + buildFlowGraph(node[2]); + } + joinJunction(jExit); + setJunction(jEnter); + if (node[3]) { + buildFlowGraph(node[3]); + } + joinJunction(jExit); } - joinJunction(jExit); isInExpr--; break; case 'while': @@ -3519,20 +3623,23 @@ function eliminate(ast, memSafe) { seenUses[name]++; } } else if (type === 'while') { + if (!asm) return; // try to remove loop helper variables specifically var stats = node[2][1]; var last = stats[stats.length-1]; if (last && last[0] === 'if' && last[2][0] === 'block' && last[3] && last[3][0] === 'block') { var ifTrue = last[2]; var ifFalse = last[3]; + clearEmptyNodes(ifTrue[1]); + clearEmptyNodes(ifFalse[1]); var flip = false; - if (ifFalse[1][0] && ifFalse[1][0][0] === 'break') { // canonicalize break in the if + if (ifFalse[1][0] && ifFalse[1][ifFalse[1].length-1][0] === 'break') { // canonicalize break in the if-true var temp = ifFalse; ifFalse = ifTrue; ifTrue = temp; flip = true; } - if (ifTrue[1][0] && ifTrue[1][0][0] === 'break') { + if (ifTrue[1][0] && ifTrue[1][ifTrue[1].length-1][0] === 'break') { var assigns = ifFalse[1]; clearEmptyNodes(assigns); var loopers = [], helpers = []; @@ -3569,6 +3676,17 @@ function eliminate(ast, memSafe) { } } } + // remove loop vars that are used in the if + traverse(ifTrue, function(node, type) { + if (type === 'name') { + var index = loopers.indexOf(node[1]); + if (index < 0) index = helpers.indexOf(node[1]); + if (index >= 0) { + loopers.splice(index, 1); + helpers.splice(index, 1); + } + } + }); if (loopers.length === 0) return; for (var l = 0; l < loopers.length; l++) { var looper = loopers[l]; @@ -3589,17 +3707,61 @@ function eliminate(ast, memSafe) { } } if (found < 0) return; - var looperUsed = false; - for (var i = found+1; i < stats.length && !looperUsed; i++) { + // 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 helper overlap + var firstLooperUsage = -1; + var lastLooperUsage = -1; + var firstHelperUsage = -1; + var lastHelperUsage = -1; + for (var i = found+1; i < stats.length; i++) { var curr = i < stats.length-1 ? stats[i] : last[1]; // on the last line, just look in the condition traverse(curr, function(node, type) { - if (type === 'name' && node[1] === looper) { - looperUsed = true; - return true; + if (type === 'name') { + if (node[1] === looper) { + if (firstLooperUsage < 0) firstLooperUsage = i; + lastLooperUsage = i; + } else if (node[1] === helper) { + if (firstHelperUsage < 0) firstHelperUsage = i; + lastHelperUsage = i; + } } }); } - if (looperUsed) return; + if (firstLooperUsage >= 0) { + // the looper is used, we cannot simply merge the two variables + if ((firstHelperUsage < 0 || firstHelperUsage > lastLooperUsage) && lastLooperUsage+1 < stats.length && 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.splice(lastLooperUsage+1, 0, 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 + var temp = looper + '$looptemp'; + assert(!(temp in asmData.vars)); + for (var i = firstLooperUsage; i <= lastLooperUsage; i++) { + var curr = i < stats.length-1 ? stats[i] : last[1]; // on the last line, just look in the condition + traverse(curr, function looperToLooptemp(node, type) { + if (type === 'name') { + if (node[1] === looper) { + node[1] = temp; + } + } else if (type === 'assign' && node[2][0] === 'name') { + // do not traverse the assignment target, phi assignments to the loop variable must remain + traverse(node[3], looperToLooptemp); + return null; + } + }); + } + asmData.vars[temp] = asmData.vars[looper]; + stats.splice(found, 0, ['stat', ['assign', true, ['name', temp], ['name', looper]]]); + } + } } for (var l = 0; l < helpers.length; l++) { for (var k = 0; k < helpers.length; k++) { @@ -3710,7 +3872,7 @@ function minifyGlobals(ast) { var first = true; // do not minify initial 'var asm =' // find the globals traverse(ast, function(node, type) { - if (type === 'var') { + if (type === 'var' || type === 'const') { if (first) { first = false; return; @@ -3914,6 +4076,21 @@ function measureSize(ast) { return size; } +function measureCost(ast) { + var size = 0; + traverse(ast, function(node, type) { + if (type === 'num' || type === 'unary-prefix') size--; + else if (type === 'binary') { + if (node[3][0] === 'num' && node[3][1] === 0) size--; + else if (node[1] === '/' || node[1] === '%') size += 2; + } + else if (type === 'call' && !callHasSideEffects(node)) size -= 2; + else if (type === 'sub') size++; + size++; + }); + return size; +} + function aggressiveVariableEliminationInternal(func, asmData) { // This removes as many variables as possible. This is often not the best thing because it increases // code size, but it is far preferable to the risk of split functions needing to do more spilling, so @@ -4915,36 +5092,44 @@ function safeHeap(ast) { } } } else if (type === 'sub') { - var heap = node[1][1]; - if (heap[0] !== 'H') return; - var ptr = fixPtr(node[2], heap); - // SAFE_HEAP_LOAD(ptr, bytes, isFloat) - switch (heap) { - case 'HEAP8': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 1], ['num', '0'], ['num', '0']]], ASM_INT); - } - case 'HEAPU8': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 1], ['num', '0'], ['num', '1']]], ASM_INT); - } - case 'HEAP16': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 2], ['num', '0'], ['num', '0']]], ASM_INT); - } - case 'HEAPU16': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 2], ['num', '0'], ['num', '1']]], ASM_INT); - } - case 'HEAP32': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', '0'], ['num', '0']]], ASM_INT); - } - case 'HEAPU32': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', '0'], ['num', '1']]], ASM_INT); - } - case 'HEAPF32': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', '1'], ['num', '0']]], ASM_DOUBLE); - } - case 'HEAPF64': { - return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 8], ['num', '1'], ['num', '0']]], ASM_DOUBLE); + var target = node[1][1]; + if (target[0] === 'H') { + // heap access + var heap = target; + var ptr = fixPtr(node[2], heap); + // SAFE_HEAP_LOAD(ptr, bytes, isFloat) + switch (heap) { + case 'HEAP8': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 1], ['num', '0'], ['num', '0']]], ASM_INT); + } + case 'HEAPU8': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 1], ['num', '0'], ['num', '1']]], ASM_INT); + } + case 'HEAP16': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 2], ['num', '0'], ['num', '0']]], ASM_INT); + } + case 'HEAPU16': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 2], ['num', '0'], ['num', '1']]], ASM_INT); + } + case 'HEAP32': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', '0'], ['num', '0']]], ASM_INT); + } + case 'HEAPU32': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', '0'], ['num', '1']]], ASM_INT); + } + case 'HEAPF32': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', '1'], ['num', '0']]], ASM_DOUBLE); + } + case 'HEAPF64': { + return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 8], ['num', '1'], ['num', '0']]], ASM_DOUBLE); + } + default: throw 'bad heap ' + heap; } - default: throw 'bad heap ' + heap; + } else { + assert(target[0] == 'F'); + // function table indexing mask + assert(node[2][0] === 'binary' && node[2][1] === '&'); + node[2][2] = makeAsmCoercion(['call', ['name', 'SAFE_FT_MASK'], [makeAsmCoercion(node[2][2], ASM_INT), makeAsmCoercion(node[2][3], ASM_INT)]], ASM_INT); } } }); @@ -4952,10 +5137,19 @@ function safeHeap(ast) { function optimizeFrounds(ast) { // collapse fround(fround(..)), which can happen due to elimination + // also emit f0 instead of fround(0) (except in returns) + var inReturn = false; function fix(node) { + if (node[0] === 'return') inReturn = true; traverseChildren(node, fix); - if (node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'Math_fround' && node[2][0][0] === 'call' && node[2][0][1][0] === 'name' && node[2][0][1][1] === 'Math_fround') { - return node[2][0]; + if (node[0] === 'return') inReturn = false; + if (node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'Math_fround') { + var arg = node[2][0]; + if (arg[0] === 'num') { + if (!inReturn && arg[1] === 0) return ['name', 'f0']; + } else if (arg[0] === 'call' && arg[1][0] === 'name' && arg[1][1] === 'Math_fround') { + return arg; + } } } traverseChildren(ast, fix); @@ -4977,7 +5171,9 @@ function prepDotZero(ast) { function fixDotZero(js) { return js.replace(/DOT\$ZERO\(([-+]?(0x)?[0-9a-f]*\.?[0-9]+([eE][-+]?[0-9]+)?)\)/g, function(m, num) { if (num.substr(0, 2) === '0x' || num.substr(0, 3) === '-0x') { - return eval(num) + '.0'; + var ret = eval(num).toString(); + if (ret.indexOf('.') < 0) return ret + '.0'; + return ret; } if (num.indexOf('.') >= 0) return num; var e = num.indexOf('e'); @@ -4987,8 +5183,11 @@ function fixDotZero(js) { } function asmLastOpts(ast) { + var statsStack = []; traverseGeneratedFunctions(ast, function(fun) { traverse(fun, function(node, type) { + var stats = getStatements(node); + if (stats) statsStack.push(stats); if (type === 'while' && node[1][0] === 'num' && node[1][1] === 1 && node[2][0] === 'block' && node[2].length == 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 @@ -4996,15 +5195,28 @@ function asmLastOpts(ast) { // while (1) { .. if (..) { break } } ==> do { .. } while(..) var stats = node[2][1]; var last = stats[stats.length-1]; - if (last && last[0] === 'if' && !last[3] && last[2][0] === 'block' && last[2][1][0] && last[2][1][0][0] === 'break' && !last[2][1][0][1]) { + if (last && last[0] === 'if' && !last[3] && last[2][0] === 'block' && last[2][1][0]) { + var lastStats = last[2][1]; + var lastNum = lastStats.length; + var lastLast = lastStats[lastNum-1]; + if (!(lastLast[0] === 'break' && !lastLast[1])) return;// if not a simple break, dangerous + for (var 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 var abort = false; var stack = 0; + var breaks = 0; traverse(stats, function(node, type) { - if (type == 'continue') { - if (stack == 0 || node[1]) { // abort if labeled (we do not analyze labels here yet), or a continue directly on us + 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; return 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 (type in LOOP) { stack++; } @@ -5014,6 +5226,15 @@ function asmLastOpts(ast) { } }); if (abort) return; + assert(breaks > 0); + if (lastStats.length > 1 && breaks !== 1) return; // if we have code aside from the break, we can only move it out if there is just one break + // start to optimize + if (lastStats.length > 1) { + var parent = statsStack[statsStack.length-1]; + var me = parent.indexOf(node); + if (me < 0) return; // not always directly on a stats, could be in a label for example + parent.splice.apply(parent, [me+1, 0].concat(lastStats.slice(0, lastStats.length-1))); + } var conditionToBreak = last[1]; stats.pop(); node[0] = 'do'; @@ -5042,6 +5263,9 @@ function asmLastOpts(ast) { } } } + }, function(node, type) { + var stats = getStatements(node); + if (stats) statsStack.pop(); }); }); } |