diff options
author | Alon Zakai <alonzakai@gmail.com> | 2014-01-23 20:28:18 -0800 |
---|---|---|
committer | Alon Zakai <alonzakai@gmail.com> | 2014-01-23 20:28:18 -0800 |
commit | 64d37b601f9180c66a4b10476ef3a4a614c78de6 (patch) | |
tree | 9fbddd951bb2ab5dcd3cd50ac8d4d61321f4bada | |
parent | 42efac37f1866d2084a610b4161495efb36dca19 (diff) | |
parent | d55c07198d9aa3352cda6e44d73dc160e9a877fe (diff) |
Merge pull request #2046 from rfk/rfk/registerize-harder-followups
Some follow-up fixes to registerizeHarder
-rw-r--r-- | tests/test_other.py | 2 | ||||
-rw-r--r-- | tools/js-optimizer.js | 205 | ||||
-rw-r--r-- | tools/test-js-optimizer-asm-regs-harder-output.js | 129 | ||||
-rw-r--r-- | tools/test-js-optimizer-asm-regs-harder.js | 150 |
4 files changed, 379 insertions, 107 deletions
diff --git a/tests/test_other.py b/tests/test_other.py index 53128391..8895a911 100644 --- a/tests/test_other.py +++ b/tests/test_other.py @@ -1773,6 +1773,8 @@ f.close() ['asm', 'eliminate']), (path_from_root('tools', 'test-js-optimizer-asm-regs.js'), open(path_from_root('tools', 'test-js-optimizer-asm-regs-output.js')).read(), ['asm', 'registerize']), + (path_from_root('tools', 'test-js-optimizer-asm-regs-harder.js'), open(path_from_root('tools', 'test-js-optimizer-asm-regs-harder-output.js')).read(), + ['asm', 'registerizeHarder']), (path_from_root('tools', 'test-js-optimizer-asm-regs-min.js'), open(path_from_root('tools', 'test-js-optimizer-asm-regs-min-output.js')).read(), ['asm', 'registerize', 'minifyLocals']), (path_from_root('tools', 'test-js-optimizer-asm-pre.js'), open(path_from_root('tools', 'test-js-optimizer-asm-pre-output.js')).read(), diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index b35da99d..21d521fd 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -2460,55 +2460,40 @@ function registerizeHarder(ast) { buildFlowGraph(node[2]); break; case 'switch': - // This is horrific. It need to capture the default flow-through - // logic of sequential case bodies, as well as the theoretical - // sequential evaluation of each case clause. - // TODO: simplify based on asmjs switch-statement restrictions. + // Emscripten generates switch statements of a very limited + // form: all case clauses are numeric literals, and all + // case bodies end with a break. So it's basically equivalent + // to a multi-way 'if' statement. isInExpr++; buildFlowGraph(node[1]); isInExpr--; var jCheckExit = markJunction(); var jExit = addJunction(); pushActiveLabels(null, jExit); - // Process all cases as a sequential chain of checks. - // Process all case bodies as one big flow-through statement. - // They might break themselves out of it but this implements the - // default fall-through case logic. var hasDefault = false; - var jPrevCaseExit = jCheckExit; - var jPrevBodyExit = jCheckExit; for (var i=0; i<node[2].length; i++) { - // In the general case we'll need a basic block for the case clause. - // Try to avoid it for common, simple, non-var-using cases. + setJunction(jCheckExit); if (!node[2][i][0]) { hasDefault = true; } else { if (node[2][i][0][0] !== 'num') { - setJunction(jPrevCaseExit); - isInExpr++; - buildFlowGraph(node[2][i][0]); - isInExpr--; - jPrevCaseExit = markJunction(); + if (node[2][i][0][0] !== 'unary-prefix' || node[2][i][0][2][0] !== 'num') { + assert(false, 'non-numeric switch case clause'); + } } - } - // The next case body flows from the exit of the prev one, - // or may be entered directly from the case statement exit. - setJunction(jPrevCaseExit); - if (jPrevBodyExit !== jCheckExit) { - joinJunction(jPrevBodyExit); + addPreCondTrue(['binary', '==', node[1], node[2][i][0]]); } for (var j = 0; j < node[2][i][1].length; j++) { buildFlowGraph(node[2][i][1][j]); } - jPrevBodyExit = markJunction(); + if (currEntryJunction !== null, 'switch case body did not break'); } - markJunction(jExit); // If there was no default case, we also need an empty block - // linking straight from entry to exit. - if (!hasDefault && jCheckExit !== jPrevBodyExit) { + // linking straight from the test evaluation to the exit. + if (!hasDefault) { setJunction(jCheckExit); - joinJunction(jExit); } + markJunction(jExit); popActiveLabels() break; case 'return': @@ -2612,6 +2597,7 @@ function registerizeHarder(ast) { if (labelCond && labelCond[0] === '==') { // If there are multiple blocks with the same label, all bets are off. // This seems to happen sometimes for short blocks that end with a return. + // TODO: it should be safe to merge the duplicates if they're identical. if (labelCond[1] in labelledBlocks) { labelledBlocks = {}; labelledJumps = []; @@ -2711,6 +2697,7 @@ function registerizeHarder(ast) { var link = {}; var lastUseLoc = {}; var firstDeadLoc = {}; + var firstKillLoc = {}; var lastKillLoc = {}; for (var name in live) { link[name] = name; @@ -2735,6 +2722,7 @@ function registerizeHarder(ast) { delete use[name]; delete live[name]; firstDeadLoc[name] = j; + firstKillLoc[name] = j; if (lastUseLoc[name] === undefined) { lastUseLoc[name] = j; } @@ -2760,6 +2748,9 @@ function registerizeHarder(ast) { for (var name in lastUseLoc) { lastUseLoc[name] -= n; } + for (var name in firstKillLoc) { + firstKillLoc[name] -= n; + } for (var name in lastKillLoc) { lastKillLoc[name] -= n; } @@ -2791,6 +2782,7 @@ function registerizeHarder(ast) { block.link = link; block.lastUseLoc = lastUseLoc; block.firstDeadLoc = firstDeadLoc; + block.firstKillLoc = firstKillLoc; block.lastKillLoc = lastKillLoc; } @@ -2975,47 +2967,41 @@ function registerizeHarder(ast) { if (block.nodes.length === 0) continue; var jEnter = junctions[block.entry]; var jExit = junctions[block.exit]; - // Calculate the full internal liveness states for this block. - var liveness = [{}]; - for (var name in jExit.live) { - liveness[0][name] = 1; - } - for (var j=block.nodes.length-1; j>=0; j--) { - var node = block.nodes[j]; - liveness.unshift(copy(liveness[0])); - if (node[0] === 'assign') { - var name = node[2][1]; - delete liveness[0][name]; - } else if (node[0] === 'name') { - var name = node[1]; - liveness[0][name] = 1; - } else { - assert(false, 'unexpected node type: ' + node[0]); - } - } - assert(liveness.length == block.nodes.length + 1); - assert(setSize(setSub(liveness[0], jEnter.live)) == 0); - // Mark the point at which each output reg gets assigned. - // Variables that live past this point must not be assigned + // Mark the point at which each input reg becomes dead. + // Variables alive before this point must not be assigned // to that register. - var outputAssignLoc = {}; - var outputVars = {}; + var inputVars = {} + var inputDeadLoc = {}; + var inputVarsByReg = {}; for (var name in jExit.live) { - var reg = junctionVariables[name].reg; - assert(reg !== null, 'output variable doesnt have a register'); - outputAssignLoc[reg] = block.lastKillLoc[name]; - outputVars[reg] = name; - } - // Scan through in execution order, allocating registers on demand. - // Be careful to avoid conflicts with the output registers. + if (!(name in block.kill)) { + inputVars[name] = 1; + var reg = junctionVariables[name].reg; + assert(reg !== null, 'input variable doesnt have a register'); + inputDeadLoc[reg] = block.firstDeadLoc[name]; + inputVarsByReg[reg] = name; + } + } + for (var name in block.use) { + if (!(name in inputVars)) { + inputVars[name] = 1; + var reg = junctionVariables[name].reg; + assert(reg !== null, 'input variable doesnt have a register'); + inputDeadLoc[reg] = block.firstDeadLoc[name]; + inputVarsByReg[reg] = name; + } + } + assert(setSize(setSub(inputVars, jEnter.live)) == 0); + // Scan through backwards, allocating registers on demand. + // Be careful to avoid conflicts with the input registers. // We consume free registers in last-used order, which helps to // eliminate "x=y" assignments that are the last use of "y". var assignedRegs = {}; var freeRegsByType = copy(allRegsByType); - // Begin with all live vars assigned per the entry-point. - for (var name in liveness[0]) { + // Begin with all live vars assigned per the exit junction. + for (var name in jExit.live) { var reg = junctionVariables[name].reg; - assert(reg !== null, 'input variable doesnt have a register'); + assert(reg !== null, 'output variable doesnt have a register'); assignedRegs[name] = reg; delete freeRegsByType[localVars[name]][reg]; } @@ -3023,66 +3009,71 @@ function registerizeHarder(ast) { freeRegsByType[j] = keys(freeRegsByType[j]); } // Scan through the nodes in sequence, modifying each node in-place - // and freeing registers according to the calculated liveness info. - for (var j = 0; j < block.nodes.length; j++) { + // and grabbing/freeing registers as needed. + var maybeRemoveNodes = []; + for (var j = block.nodes.length - 1; j >= 0; j--) { var node = block.nodes[j]; var name = node[0] === 'assign' ? node[2][1] : node[1]; var allRegs = allRegsByType[localVars[name]]; var freeRegs = freeRegsByType[localVars[name]]; var reg = assignedRegs[name]; if (node[0] === 'name') { - // A use. It should already be in a register. - assert(liveness[j][name], 'use node, but name was not alive?') - assert(reg, 'live variable did not have a reg?') - node[1] = allRegs[reg]; - } else { - // A kill. This should assign it a new register. - assert(!liveness[j][name], 'kill node, but name was alive?') - assert(!reg, 'non-live variable still had a reg?') - if (name in jExit.live && j === block.lastKillLoc[name]) { - // Assignment to an output variable, must use pre-assigned reg. - reg = junctionVariables[name].reg; - assignedRegs[name] = reg; - for (var k = freeRegs.length - 1; k >= 0; k--) { - if (freeRegs[k] === reg) { + // A use. Grab a register if it doesn't have one. + if (!reg) { + if (name in inputVars && j <= block.firstDeadLoc[name]) { + // Assignment to an input variable, must use pre-assigned reg. + reg = junctionVariables[name].reg; + assignedRegs[name] = reg; + for (var k = freeRegs.length - 1; k >= 0; k--) { + if (freeRegs[k] === reg) { + freeRegs.splice(k, 1); + break; + } + } + } else { + // Try to use one of the existing free registers. + // It must not conflict with an input register. + for (var k = freeRegs.length - 1; k >= 0; k--) { + reg = freeRegs[k]; + // Check for conflict with input registers. + if (block.firstKillLoc[name] <= inputDeadLoc[reg]) { + if (name !== inputVarsByReg[reg]) { + continue; + } + } + // Found one! + assignedRegs[name] = reg; freeRegs.splice(k, 1); break; } - } - } else { - // Try to use one of the existing free registers. - // It must not conflict with an output register. - for (var k = freeRegs.length - 1; k >= 0; k--) { - reg = freeRegs[k]; - // Check for conflict with output registers. - if (block.lastUseLoc[name] > outputAssignLoc[reg]) { - if (name !== outputVars[reg]) { - continue; - } + // If we didn't find a suitable register, create a new one. + if (!assignedRegs[name]) { + reg = createReg(name); + assignedRegs[name] = reg; } - // Found one! - assignedRegs[name] = reg; - freeRegs.splice(k, 1); - break; - } - // If we didn't find a suitable register, create a new one. - if (!assignedRegs[name]) { - reg = createReg(name); - assignedRegs[name] = reg; } } - // Modify assignment to use the new name. - // If we happen to create a "x=x" type do-nothing assignment, - // we can safely morph it into a no-op. + node[1] = allRegs[reg]; + } else { + // A kill. This frees the assigned register. + assert(reg, 'live variable doesnt have a reg?') node[2][1] = allRegs[reg]; - if (node[3][0] === 'name' && node[3][1] === node[2][1]) { - morphNode(node, ['block', []]); + freeRegs.push(reg); + delete assignedRegs[name]; + if (node[3][0] === 'name' && node[3][1] in localVars) { + maybeRemoveNodes.push([j, node]); } } - // Free the reg if it's not live in the next step. - if (!liveness[j+1][name]) { - delete assignedRegs[name]; - freeRegs.push(reg); + } + // If we managed to create an "x=x" assignments, remove them. + for (var j = 0; j < maybeRemoveNodes.length; j++) { + var node = maybeRemoveNodes[j][1]; + if (node[2][1] === node[3][1]) { + if (block.isexpr[maybeRemoveNodes[j][0]]) { + morphNode(node, node[2]); + } else { + morphNode(node, ['block', []]); + } } } } diff --git a/tools/test-js-optimizer-asm-regs-harder-output.js b/tools/test-js-optimizer-asm-regs-harder-output.js new file mode 100644 index 00000000..448fb67a --- /dev/null +++ b/tools/test-js-optimizer-asm-regs-harder-output.js @@ -0,0 +1,129 @@ +function asm(d1, i2) { + d1 = +d1; + i2 = i2 | 0; + i2 = d1 + d1 | 0; + d1 = d(Math_max(10, Math_min(5, f()))); + i2 = i2 + 2 | 0; + print(i2); + d1 = d1 * 5; + return d1; +} +function _doit(i3, i2, i1) { + i3 = i3 | 0; + i2 = i2 | 0; + i1 = i1 | 0; + i3 = STACKTOP; + _printf(__str | 0, (tempInt = STACKTOP, STACKTOP = STACKTOP + 8 | 0, HEAP32[(tempInt & 16777215) >> 2] = i2, HEAP32[(tempInt + 4 & 16777215) >> 2] = i1, tempInt)); + STACKTOP = i3; + return 0 | 0; +} +function stackRestore(i1) { + i1 = i1 | 0; + STACKTOP = i1; +} +function switchey(d1, i2) { + d1 = +d1; + i2 = i2 | 0; + switch (d1 | 0) { + case 0: + i2 = d1 + d1 | 0; + d1 = d(Math_max(10, Math_min(5, f()))); + i2 = i2 + 2 | 0; + print(i2); + d1 = d1 * 5; + return d1; + case 1: + return 20; + } +} +function switchey2() { + var i1 = 0, i2 = 0, i3 = 0, i4 = 0, i5 = 0, d6 = +0, d7 = +0; + i2 = STACKTOP; + STACKTOP = STACKTOP + 8 | 0; + i3 = 1; + while (1) switch (i3 | 0) { + case 1: + i1 = i2 | 0; + __ZN6RandomC1Ev(i1); + i4 = 0; + i5 = 0; + i3 = 2; + break; + case 2: + d7 = +__ZN6Random3getEf(8, +1); + d6 = +__ZN6Random3getEf(i1, +1); + _printf(24, (tempInt = STACKTOP, STACKTOP = STACKTOP + 16 | 0, HEAPF64[CHECK_ALIGN_8(tempInt | 0) >> 3] = d7, HEAPF64[CHECK_ALIGN_8(tempInt + 8 | 0) >> 3] = d6, tempInt) | 0); + i5 = (d7 != d6 & 1) + i5 | 0; + i4 = i4 + 1 | 0; + if ((i4 | 0) < 100) { + i3 = 2; + break; + } else { + i3 = 3; + break; + } + case 3: + _printf(16, (tempInt = STACKTOP, STACKTOP = STACKTOP + 8 | 0, HEAP32[CHECK_ALIGN_4(tempInt | 0) >> 2] = i5, tempInt) | 0); + STACKTOP = i2; + return 0; + } + return 0; +} +function iffey() { + var i1 = 0, i2 = 0, i3 = 0, i4 = 0, i5 = 0, d6 = +0, d7 = +0; + i2 = STACKTOP; + STACKTOP = STACKTOP + 8 | 0; + i4 = 1; + while (1) { + if (i4 | 0) { + i1 = i2 | 0; + __ZN6RandomC1Ev(i1); + i3 = 0; + i5 = 0; + i4 = 2; + } else { + d7 = +__ZN6Random3getEf(8, +1); + d6 = +__ZN6Random3getEf(i1, +1); + _printf(24, (tempInt = STACKTOP, STACKTOP = STACKTOP + 16 | 0, HEAPF64[CHECK_ALIGN_8(tempInt | 0) >> 3] = d7, HEAPF64[CHECK_ALIGN_8(tempInt + 8 | 0) >> 3] = d6, tempInt) | 0); + i5 = (d7 != d6 & 1) + i5 | 0; + i3 = i3 + 1 | 0; + if ((i3 | 0) < 100) { + i4 = 2; + } else { + return 10; + } + } + } + return 0; +} +function labelledJump(i3) { + i3 = i3 | 0; + var i1 = 0, i2 = 0; + i2 = 2; + if (i3) { + i2 = 17; + i1 = 1; + } + if (i1 == 1) { + i3 = i2 + 1; + } else { + i3 = i2 + 1; + } + return i3; +} +function linkedVars() { + var i1 = 0, i2 = 0; + while (1) { + i2 = 9; + i1 = 5; + while (i2 > 0 || i1 > 0) { + if (i2 < i1) { + i2 = i2 - 1; + } else { + i1 = i1 - 1; + } + } + } + return i2 + i1; +} + diff --git a/tools/test-js-optimizer-asm-regs-harder.js b/tools/test-js-optimizer-asm-regs-harder.js new file mode 100644 index 00000000..cf44c1dd --- /dev/null +++ b/tools/test-js-optimizer-asm-regs-harder.js @@ -0,0 +1,150 @@ +function asm(x, y) { + x = +x; + y = y | 0; + var int1 = 0, int2 = 0; // do not mix the types! + var double1 = +0, double2 = +0; + int1 = (x+x)|0; + double1 = d(Math_max(10, Math_min(5, f()))); + int2 = (int1+2)|0; + print(int2); + double2 = double1*5; + return double2; +} +function _doit($x, $y$0, $y$1) { + $x = $x | 0; + $y$0 = $y$0 | 0; + $y$1 = $y$1 | 0; + var __stackBase__ = 0; + __stackBase__ = STACKTOP; + _printf(__str | 0, (tempInt = STACKTOP, STACKTOP = STACKTOP + 8 | 0, HEAP32[(tempInt & 16777215) >> 2] = $y$0, HEAP32[(tempInt + 4 & 16777215) >> 2] = $y$1, tempInt)); + STACKTOP = __stackBase__; + return 0 | 0; +} +function stackRestore(top) { + top = top|0; + STACKTOP = top; +} +function switchey(x, y) { + x = +x; + y = y | 0; + var int1 = 0, int2 = 0; // do not mix the types! + var double1 = +0, double2 = +0; + switch(x|0) { + case 0: + int1 = (x+x)|0; + double1 = d(Math_max(10, Math_min(5, f()))); + int2 = (int1+2)|0; + print(int2); + double2 = double1*5; + return double2; + case 1: + return 20; + } +} +function switchey2() { + var $rng2 = 0, $count_06 = 0, $i_05 = 0, $2 = +0, $3 = +0, $count_1 = 0, $9 = 0, label = 0, __stackBase__ = 0; + __stackBase__ = STACKTOP; + STACKTOP = STACKTOP + 8 | 0; + label = 1; + while (1) switch (label | 0) { + case 1: + $rng2 = __stackBase__ | 0; + __ZN6RandomC1Ev($rng2); + $i_05 = 0; + $count_06 = 0; + label = 2; + break; + case 2: + $2 = +__ZN6Random3getEf(8, +1); + $3 = +__ZN6Random3getEf($rng2, +1); + _printf(24, (tempInt = STACKTOP, STACKTOP = STACKTOP + 16 | 0, HEAPF64[CHECK_ALIGN_8(tempInt | 0) >> 3] = $2, HEAPF64[CHECK_ALIGN_8(tempInt + 8 | 0) >> 3] = $3, tempInt) | 0); + $count_1 = ($2 != $3 & 1) + $count_06 | 0; + $9 = $i_05 + 1 | 0; + if (($9 | 0) < 100) { + $i_05 = $9; + $count_06 = $count_1; + label = 2; + break; + } else { + label = 3; + break; + } + case 3: + _printf(16, (tempInt = STACKTOP, STACKTOP = STACKTOP + 8 | 0, HEAP32[CHECK_ALIGN_4(tempInt | 0) >> 2] = $count_1, tempInt) | 0); + STACKTOP = __stackBase__; + return 0; + } + return 0; +} +function iffey() { + var $rng2 = 0, $count_06 = 0, $i_05 = 0, $2 = +0, $3 = +0, $count_1 = 0, $9 = 0, label = 0, __stackBase__ = 0; + __stackBase__ = STACKTOP; + STACKTOP = STACKTOP + 8 | 0; + label = 1; + while (1) { + if (label | 0) { + $rng2 = __stackBase__ | 0; + __ZN6RandomC1Ev($rng2); + $i_05 = 0; + $count_06 = 0; + label = 2; + } else { + $2 = +__ZN6Random3getEf(8, +1); + $3 = +__ZN6Random3getEf($rng2, +1); + _printf(24, (tempInt = STACKTOP, STACKTOP = STACKTOP + 16 | 0, HEAPF64[CHECK_ALIGN_8(tempInt | 0) >> 3] = $2, HEAPF64[CHECK_ALIGN_8(tempInt + 8 | 0) >> 3] = $3, tempInt) | 0); + $count_1 = ($2 != $3 & 1) + $count_06 | 0; + $9 = $i_05 + 1 | 0; + if (($9 | 0) < 100) { + $i_05 = $9; + $count_06 = $count_1; + label = 2; + } else { + label = 3; + return 10; + } + } + } + return 0; +} +function labelledJump(x) { + x = x | 0; + var label = 0 + // y and z don't conflict, but only if you know about labelled jumps. + var y = 0, z = 0; + y = 2; + if (x) { + z = 17; + label = 1; + } + if (label == 1) { + x = z + 1; + } else { + x = y + 1; + } + return x; +} +function linkedVars() { + var outer1 = 0, outer2 = 0; + var inner1_0 = 0, inner1_1 = 0, inner2_0 = 0, inner2_1 = 0; + while (1) { + outer1 = 9; + outer2 = 5; + while (outer1 > 0 || outer2 > 0) { + // All these copy assignment should be eliminated by var sharing. + inner1_0 = outer1; + inner2_0 = outer2; + if (inner1_0 < inner2_0) { + inner1_1 = inner1_0 - 1; + inner2_1 = inner2_0; + } else { + inner1_1 = inner1_0; + inner2_1 = inner2_0 - 1; + } + outer1 = inner1_1; + outer2 = inner2_1; + } + } + return outer1 + outer2; +} +// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "_doit", "stackRestore", "switchey", "switchey2", "iffey", "labelledJump", "linkedVars'] + |