diff options
Diffstat (limited to 'tools')
-rw-r--r-- | tools/js-optimizer.js | 422 | ||||
-rw-r--r-- | tools/test-js-optimizer-t2-output.js | 47 | ||||
-rw-r--r-- | tools/test-js-optimizer-t2.js | 47 |
3 files changed, 316 insertions, 200 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index bfb1f16b..150b1c37 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -356,230 +356,258 @@ function simplifyExpressionsPre(ast) { // to greatly reduce the number of shift operations. function optimizeShifts(ast) { traverseGeneratedFunctions(ast, function(fun) { - // 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 - }; + var funMore = true; + 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 - traverse(fun, function(node, type) { - if (type == 'var') { - node[1].forEach(function(arg) { - newVar(arg[0], false, arg[1]); + // params + if (fun[2]) { + fun[2].forEach(function(arg) { + newVar(arg, true, true); }); } - }); - // 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]; - // Push the >> inside the value elements, doing some simplification while we are there - function addShift(subNode) { - if (subNode[0] == 'binary' && subNode[1] == '+') { - subNode[2] = addShift(subNode[2]); - subNode[3] = addShift(subNode[3]); - return subNode; - } - if (subNode[0] == 'binary' && subNode[1] == '<<' && subNode[3][0] == 'num') { - if (subNode[3][1] > shifts) { - subNode[3][1] -= shifts; + // vars + // XXX if var has >>=, ignore it here? That means a previous pass already optimized it + traverse(fun, function(node, type) { + if (type == 'var') { + node[1].forEach(function(arg) { + newVar(arg[0], false, arg[1]); + }); + } + }); + // 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]; + // Push the >> inside the value elements, doing some simplification while we are there + function addShift(subNode) { + if (subNode[0] == 'binary' && subNode[1] == '+') { + subNode[2] = addShift(subNode[2]); + subNode[3] = addShift(subNode[3]); return subNode; } - // fall through to >> case - subNode[1] = '>>'; - subNode[3][1] *= -1; - } - if (subNode[0] == 'binary' && subNode[1] == '>>') { - if (subNode[3][0] == 'num') { - subNode[3][1] += shifts; - } else { - subNode[3] = ['binary', '+', subNode[3], ['num', shifts]]; + if (subNode[0] == 'binary' && subNode[1] == '<<' && subNode[3][0] == 'num') { + if (subNode[3][1] > shifts) { + subNode[3][1] -= shifts; + return subNode; + } + // fall through to >> case + subNode[1] = '>>'; + subNode[3][1] *= -1; } - return subNode; - } - if (subNode[0] == 'num') { - assert(subNode[1] % Math.pow(2, shifts) == 0, subNode); - subNode[1] /= Math.pow(2, shifts); // bake the shift in - 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; + if (subNode[0] == 'binary' && subNode[1] == '>>') { + if (subNode[3][0] == 'num') { + subNode[3][1] += shifts; + // XXX this may be wrong, if we removed a |0 that assumed we had this >> which |0's anyhow! + if (subNode[3][1] == 0) return subNode[2]; + } else { + subNode[3] = ['binary', '+', subNode[3], ['num', shifts]]; + } + return subNode; } + if (subNode[0] == 'num') { + assert(subNode[1] % Math.pow(2, shifts) == 0, subNode); + subNode[1] /= Math.pow(2, shifts); // bake the shift in + 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 ['binary', '>>', subNode, ['num', shifts]]; - } - return addShift(node[2]); - } - }); - 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 (totalTimesShifted != data.uses) { - // TODO: Handle also being used unshifted - } - // We have one shift size. Consider replacing this variable with a shifted clone. If - // the estimated benefit is >0, we will replace - data.benefit = totalTimesShifted - data.defs*2; - if (data.benefit > 0) { - for (var i = 0; i < 4; i++) { - if (data.timesShifted[i]) { - data.primaryShift = i; - } + return addShift(node[2]); } - } - } - 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); + return node.slice(0, 2); // clean up our notes } }); - } - cleanNotes(); - // Apply changes - for (var name in vars) { // add shifts for params - var data = vars[name]; - if (data.primaryShift >= 0 && data.param) { - fun[3].unshift(['stat', ['assign', '>>', ['name', name], ['num', data.primaryShift]]]); + // 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; + } + // 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 replace + data.benefit = totalTimesShifted - data.defs*2 - (data.uses-totalTimesShifted); + 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; + } + } + } } - } - function needsShift(name) { - return vars[name] && vars[name].primaryShift >= 0; - } - - traverse(fun, function(node, type) { // add shift to assignments - if (node[0] == 'assign' && node[1] === true && node[2][0] == 'name' && needsShift(node[2][1])) { - node[3] = ['binary', '>>', node[3], ['num', vars[node[2][1]].primaryShift]]; - return node; - } else if (node[0] == 'var') { - node[1].forEach(function(arg) { - if (arg[1] && needsShift(arg[0])) { - arg[1] = ['binary', '>>', arg[1], ['num', vars[arg[0]].primaryShift]]; + 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); } }); - return node; } - }); - traverse(fun, function(node, type, stack) { // replace name with unshifted name, making everything valid again by balancing the assign changes - stack.push(node); - if (node[0] == 'name' && !node[2] && vars[node[1]] && vars[node[1]].primaryShift >= 0 && stack[stack.length-2][0] != 'assign') { - node[2] = true; - return ['binary', '<<', node, ['num', vars[node[1]].primaryShift]]; + cleanNotes(); + // Apply changes + for (var name in vars) { // add shifts for params + var data = vars[name]; + if (data.primaryShift >= 0 && data.param) { + fun[3].unshift(['stat', ['assign', '>>', ['name', name], ['num', data.primaryShift]]]); + } } - }, null, []); - cleanNotes(); - var more = true; - var SIMPLE_SHIFTS = set('<<', '>>'); - while (more) { - more = false; - traverse(fun, function(node, type) { // collapse shifts and unshifts, completing the optimization - if (node[0] == 'binary' && node[1] in SIMPLE_SHIFTS && node[2][0] == 'binary' && node[2][1] in SIMPLE_SHIFTS) { - more = true; - var combinedShift = '>>'; - var sign1 = node[1] == '>>' ? 1 : -1; - var sign2 = node[2][1] == '>>' ? 1 : -1; - var total = 0; - if (node[3][0] == 'num' && node[2][3][0] == 'num') { - total = ['num', sign1*node[3][1] + sign2*node[2][3][1]]; - if (total[1] == 0) { - // XXX this may be wrong, if we removed a |0 that assumed we had this >> which |0's anyhow! - return node[2][2]; + function needsShift(name) { + return vars[name] && vars[name].primaryShift >= 0; + } + + traverse(fun, function(node, type) { // add shift to assignments + if (node[0] == 'assign' && node[1] === true && node[2][0] == 'name' && needsShift(node[2][1])) { + node[3] = ['binary', '>>', node[3], ['num', vars[node[2][1]].primaryShift]]; + return node; + } else if (node[0] == 'var') { + node[1].forEach(function(arg) { + if (arg[1] && needsShift(arg[0])) { + arg[1] = ['binary', '>>', arg[1], ['num', vars[arg[0]].primaryShift]]; } - } else { - combinedShift = node[1]; - total = ['binary', sign1 == sign2 ? '+' : '-', node[3], node[2][3]]; - } - return ['binary', combinedShift, node[2][2], total]; + }); + return node; } }); - } - // 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] == '+') { - // 'Flatten' added items - var addedItems = []; - function flatten(node) { - if (node[0] == 'binary' && node[1] == '+') { - flatten(node[2]); - flatten(node[3]); - } else { - addedItems.push(node); - } + traverse(fun, function(node, type, stack) { // replace name with unshifted name, making everything valid again by balancing the assign changes + stack.push(node); + if (node[0] == 'name' && !node[2] && vars[node[1]] && vars[node[1]].primaryShift >= 0 && stack[stack.length-2][0] != 'assign') { + node[2] = true; + return ['binary', '<<', node, ['num', vars[node[1]].primaryShift]]; } - flatten(node); - function key(node) { // a unique value for all relevant shifts for recombining, non-unique for stuff we don't need to bother with - if (node[0] == 'binary' && node[1] in SIMPLE_SHIFTS) { - if (node[3][0] == 'num' && node[3][1] >= 0 && node[3][1] <= 3) return 2*node[3][1] + (node[1] == '>>' ? 100 : 0); // 0-106 - return node[1] == '>>' ? 2000 : 1000; + }, null, []); + cleanNotes(); + var more = true; + var SIMPLE_SHIFTS = set('<<', '>>'); + while (more) { // collapse shifts and unshifts, completing the optimization + more = false; + traverse(fun, function(node, type) { + if (node[0] == 'binary' && node[1] in SIMPLE_SHIFTS && node[2][0] == 'binary' && node[2][1] in SIMPLE_SHIFTS) { + more = true; + var combinedShift = '>>'; + var sign1 = node[1] == '>>' ? 1 : -1; + var sign2 = node[2][1] == '>>' ? 1 : -1; + var total = 0; + if (node[3][0] == 'num' && node[2][3][0] == 'num') { + total = ['num', sign1*node[3][1] + sign2*node[2][3][1]]; + if (total[1] == 0) { + // XXX this may be wrong, if we removed a |0 that assumed we had this >> which |0's anyhow! + return node[2][2]; + } + } else { + combinedShift = node[1]; + total = ['binary', sign1 == sign2 ? '+' : '-', node[3], node[2][3]]; + } + return ['binary', combinedShift, node[2][2], total]; } - if (node[0] == 'num') return -1000; - return -1; - } - 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++; + } + // Before recombining, do some additional optimizations + traverse(fun, function(node, type) { + // Optimize the case of ($a*80)>>2 + 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]); + return mulNode; + } else { + if (mulNode[3][1] % Math.pow(2, node[3][1]) == 0) { + mulNode[3][1] /= Math.pow(2, node[3][1]); + return mulNode; + } + } } } - var ret = addedItems.pop(); - while (addedItems.length > 0) { // re-create AST from addedItems - ret = ['binary', '+', ret, addedItems.pop()]; + }); + // 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] == '+') { + // '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); + function key(node) { // a unique value for all relevant shifts for recombining, non-unique for stuff we don't need to bother with + if (node[0] == 'binary' && node[1] in SIMPLE_SHIFTS) { + if (node[3][0] == 'num' && node[3][1] >= 0 && node[3][1] <= 3) return 2*node[3][1] + (node[1] == '>>' ? 100 : 0); // 0-106 + return node[1] == '>>' ? 2000 : 1000; + } + if (node[0] == 'num') return -1000; + return -1; + } + 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 ret = addedItems.pop(); + while (addedItems.length > 0) { // re-create AST from addedItems + ret = ['binary', '+', ret, addedItems.pop()]; + } + return ret; } - return ret; - } - }, null, []); + }, null, []); + } }); } diff --git a/tools/test-js-optimizer-t2-output.js b/tools/test-js-optimizer-t2-output.js index e75999b6..eb3f077a 100644 --- a/tools/test-js-optimizer-t2-output.js +++ b/tools/test-js-optimizer-t2-output.js @@ -3,10 +3,10 @@ function shifty($id) { q(HEAP32[$id]); q(HEAP32[$id + 10]); q(HEAP32[$id + 20]); - q(HEAP32[(unknown2 + unknown1 >> 2) + $id]); - q(HEAP32[(unknown2 + unknown1 >> 2) + $id]); + q(HEAP32[(unknown1 + unknown2 >> 2) + $id]); + q(HEAP32[(unknown1 + unknown2 >> 2) + $id]); var localUnchanged1 = get(1), localUnchanged2 = get(1); - q(HEAP32[(localUnchanged2 + localUnchanged1 >> 2) + $id]); + q(HEAP32[(localUnchanged1 + localUnchanged2 >> 2) + $id]); q($id >> _something_ - 2); q($id << _somethingElse_ + 2); pause(-1); @@ -15,5 +15,46 @@ function shifty($id) { q(HEAP32[$id2]); q(HEAP32[$id2 + 20]); q(HEAP32[$id2 + 40]); + var $id3 = get(74) >> 3; + q(HEAP32[$id3]); + q(HEAP32[$id3 + 5]); + q(HEAP32[$id3 + 10]); + pause(0); + var _idents = get("abc") >> 2; + q(HEAP32[(HEAP32[_idents] >> 2) + 2]); + q(HEAP32[(HEAP32[_idents] >> 2) + 2]); + q(HEAP32[(HEAP32[_idents] >> 2) + 2]); + pause(1); + var $sn_addr = get(12), $a_addr = get(999) >> 2; + var $i = get(112233); + q(HEAP32[($sn_addr - 1 << 1) + $a_addr + 1]); + q(HEAP32[($i - 1 << 1) + $a_addr + 1]); + $a_addr = $a_addr + 1; + q(HEAP32[($i << 1) + $a_addr]); + q(HEAP32[$a_addr + $i]); + q($a_addr, z($a_addr)); + pause(2); + var $level = HEAP[get(322) >> 2]; + var _dwt_norms_real = get("a") >> 2, $orient = get("cheez"); + q(HEAP32[($level << 1) + _dwt_norms_real + $orient * 20]); + q(HEAP32[($level << 1) + _dwt_norms_real + $orient * 20 + 1]); + q(HEAP32[($level << 1) + _dwt_norms_real + $orient * 20 + 2]); + pause(3); + var $wavelet38 = get(38) >> 2; + $k = $a_addr; + q(HEAPF32[(HEAP32[$wavelet38] >> 2) + ($k << 2) + 2]); + q(HEAPF32[(HEAP32[$wavelet38] >> 2) + ($k << 2) + 3]); + q(HEAPF32[(HEAP32[$wavelet38] >> 2) + ($k << 2) + 100]); + pause(4); + var $p = $k, $parameters_addr = get("burger") >> 2; + q(HEAP32[$parameters_addr + $p + 1406]); + q(HEAP32[$parameters_addr + $p + 1411]); + q(HEAP32[$parameters_addr + $p + 1416]); + pause(5); + var $res_spec242 = get($real), $cp = get("b"), $tileno = arguments[2]; + while (get(1)) { + q(HEAP32[$parameters_addr + ($res_spec242 - 1) + 1406]); + q(HEAP32[(HEAP32[($cp >> 2) + 27] >> 2) + $tileno * 1397 + 105]); + } } // EMSCRIPTEN_GENERATED_FUNCTIONS: ["shifty"] diff --git a/tools/test-js-optimizer-t2.js b/tools/test-js-optimizer-t2.js index f69e1aaf..e1abc092 100644 --- a/tools/test-js-optimizer-t2.js +++ b/tools/test-js-optimizer-t2.js @@ -17,5 +17,52 @@ function shifty($id) { q(HEAP32[$id2 >> 1]); q(HEAP32[($id2 + 40) >> 1]); q(HEAP32[($id2 + 80 | 0) >> 1]); + var $id3 = get(74); + q(HEAP32[$id3 >> 3]); + q(HEAP32[($id3 + 40) >> 3]); + q(HEAP32[($id3 + 80 | 0) >> 3]); + pause(0); + // similar, but inside another HEAP + var _idents = get('abc'); + q(HEAP32[(HEAP32[_idents >> 2] + 8 | 0) >> 2]); + q(HEAP32[(HEAP32[_idents >> 2] + 8 | 0) >> 2]); + q(HEAP32[(HEAP32[_idents >> 2] + 8 | 0) >> 2]); + pause(1); + // $a_addr is *not* ssa. $i's shifts should consolidate (the last should be 0..? + // since we may have had |0 in the middle!) + var $sn_addr = get(12), $a_addr = get(999); + var $i = get(112233); + q(HEAP32[($a_addr + ((($sn_addr - 1 << 1) + 1 | 0) << 2) | 0) >> 2]); + q(HEAP32[($a_addr + ((($i - 1 << 1) + 1 | 0) << 2) | 0) >> 2]); + $a_addr = $a_addr + 4; + q(HEAP32[($a_addr + (($i << 1 | 0) << 2) | 0) >> 2]); + q(HEAP32[($a_addr + ($i << 2)) >> 2]); + q($a_addr >> 2, z($a_addr >> 2)); + pause(2); + var $level = HEAP[get(322) >> 2]; // ignore this + var _dwt_norms_real = get('a'), $orient = get('cheez'); + q(HEAP32[(_dwt_norms_real + $orient * 80 + ($level << 3) | 0) >> 2]); + q(HEAP32[(_dwt_norms_real + $orient * 80 + ($level << 3) + 4 | 0) >> 2]); + q(HEAP32[(_dwt_norms_real + $orient * 80 + ($level << 3) + 8 | 0) >> 2]); + pause(3); + // reuse $a_addr here + var $wavelet38 = get(38); + $k = $a_addr; + q(HEAPF32[(HEAP32[$wavelet38 >> 2] + ($k << 4) + 8 | 0) >> 2]); + q(HEAPF32[(HEAP32[$wavelet38 >> 2] + ($k << 4) + 12 | 0) >> 2]); + q(HEAPF32[(HEAP32[$wavelet38 >> 2] + ($k << 4) + 400 | 0) >> 2]); + pause(4); + // reuse $k, which already reuses $a_addr + var $p = $k, $parameters_addr = get('burger') + q(HEAP32[($parameters_addr + 5624 + ($p << 2) | 0) >> 2]); + q(HEAP32[($parameters_addr + 5644 + ($p << 2) | 0) >> 2]); + q(HEAP32[($parameters_addr + 5664 + ($p << 2) | 0) >> 2]); + pause(5); + // loops count as more uses! + var $res_spec242 = get($real), $cp = get('b'), $tileno = arguments[2]; + while (get(1)) { + q(HEAP32[($parameters_addr + 5624 + (($res_spec242 - 1 | 0) << 2) | 0) >> 2]); + q(HEAP32[(HEAP32[($cp + 108 | 0) >> 2] + $tileno * 5588 + 420 | 0) >> 2]); + } } // EMSCRIPTEN_GENERATED_FUNCTIONS: ["shifty"] |