From a2440907aeb89069a6f2a13bdaff888984cd3c62 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Tue, 13 May 2014 13:49:59 -0700 Subject: conditionalize when it can avoid costly side-effect free code --- tools/js-optimizer.js | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) (limited to 'tools/js-optimizer.js') diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 2914b6e8..678ba0d5 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -749,11 +749,64 @@ function simplifyExpressions(ast) { }); } + // 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 = 4; + traverse(ast, function(node, type) { + if (type === 'if' || type === 'while') { + var cond = node[1]; + if (cond[0] === 'binary' && (cond[1] === '|' || cond[1] === '&') && cond[3][0] !== 'num' && cond[2][0] !== 'num') { + // logical operator on two non-numerical values, all inside a condition + var left = cond[2]; + var right = cond[3]; + 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 + if (cond[1] === '|') { + node[1] = ['conditional', left, ['num', 1], right]; + } else { // & + node[1] = ['conditional', left, right, ['num', 0]]; + } + if (left[0] === 'unary-prefix' && left[1] === '!') { + node[1][1] = flipCondition(left); + var temp = node[1][2]; + node[1][2] = node[1][3]; + node[1][3] = temp; + } + } + } + }); + } + traverseGeneratedFunctions(ast, function(func) { simplifyIntegerConversions(func); simplifyBitops(func); joinAdditions(func); simplifyNotComps(func); + conditionalize(func); // simplifyZeroComp(func); TODO: investigate performance }); } @@ -3921,6 +3974,18 @@ 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' && node[3][0] === 'num' && node[3][1] === 0) size--; + 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 -- cgit v1.2.3-70-g09d2 From eef1e214a698ae6e4f8b2c375536b268f0a95dd2 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Tue, 13 May 2014 14:14:29 -0700 Subject: update heuristic --- tools/js-optimizer.js | 2 +- tools/test-js-optimizer-asm-pre-output.js | 2 +- tools/test-js-optimizer-asm-pre.js | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-) (limited to 'tools/js-optimizer.js') diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 678ba0d5..d79e8f23 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -753,7 +753,7 @@ function simplifyExpressions(ast) { // 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 = 4; + var MIN_COST = 7; traverse(ast, function(node, type) { if (type === 'if' || type === 'while') { var cond = node[1]; diff --git a/tools/test-js-optimizer-asm-pre-output.js b/tools/test-js-optimizer-asm-pre-output.js index ce45645c..d6a7a04b 100644 --- a/tools/test-js-optimizer-asm-pre-output.js +++ b/tools/test-js-optimizer-asm-pre-output.js @@ -593,7 +593,7 @@ function conditionalizeMe() { if ($sub$i480 >= Math_fround(+0) ? !($sub4$i483 >= Math_fround(HEAPF32[x + y | 0])) : 1) { b(); } - if (x > 10 ? 1 : HEAP[20] > 5) { + if (x > 10 | HEAP[20] + 2 > 5) { b(); } } diff --git a/tools/test-js-optimizer-asm-pre.js b/tools/test-js-optimizer-asm-pre.js index b9773bb5..f930fc13 100644 --- a/tools/test-js-optimizer-asm-pre.js +++ b/tools/test-js-optimizer-asm-pre.js @@ -605,7 +605,7 @@ function conditionalizeMe() { if (!($sub$i480 >= Math_fround(+0)) | !($sub4$i483 >= Math_fround(HEAPF32[x+y|0]))) { b(); } - if (x > 10 | HEAP[20] > 5) { + if (x > 10 | (HEAP[20] + 2) > 5) { b(); } } -- cgit v1.2.3-70-g09d2 From 17ba5c2b0712b8c871a260f3e1ce00527c5a4d1d Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Tue, 13 May 2014 15:00:34 -0700 Subject: conditionalize in all boolean-emitting expressions --- tests/test_benchmark.py | 36 +++++++++++++ tools/js-optimizer.js | 86 +++++++++++++++++-------------- tools/test-js-optimizer-asm-pre-output.js | 1 + tools/test-js-optimizer-asm-pre.js | 1 + 4 files changed, 86 insertions(+), 38 deletions(-) (limited to 'tools/js-optimizer.js') diff --git a/tests/test_benchmark.py b/tests/test_benchmark.py index 821caa6b..16abbfdd 100644 --- a/tests/test_benchmark.py +++ b/tests/test_benchmark.py @@ -408,6 +408,42 @@ class benchmark(RunnerCore): ''' self.do_benchmark('ifs', src, 'ok', reps=TEST_REPS*5) + def test_conditionals(self): + src = r''' + #include + #include + + int main(int argc, char *argv[]) { + int arg = argc > 1 ? argv[1][0] - '0' : 3; + switch(arg) { + case 0: return 0; break; + case 1: arg = 3*75; break; + case 2: arg = 3*625; break; + case 3: arg = 3*1250; break; + case 4: arg = 3*5*1250; break; + case 5: arg = 3*10*1250; break; + default: printf("error: %d\\n", arg); return -1; + } + + int x = 0; + + for (int j = 0; j < 27000; j++) { + for (int i = 0; i < arg; i++) { + if (((x*x+11) % 3 == 0) | ((x*(x+2)+17) % 5 == 0)) { + x += 2; + } else { + x++; + } + } + } + + printf("ok %d\n", x); + + return x; + } + ''' + self.do_benchmark('conditionals', src, 'ok', reps=TEST_REPS*5) + def test_fannkuch(self): src = open(path_from_root('tests', 'fannkuch.cpp'), 'r').read().replace( 'int n = argc > 1 ? atoi(argv[1]) : 0;', diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index d79e8f23..f38ff08c 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -749,54 +749,61 @@ function simplifyExpressions(ast) { }); } + function emitsBoolean(node) { + if (node[0] === 'binary') return node[1] in COMPARE_OPS; + if (node[0] === 'unary-prefix') return node[1] === '!'; + if (node[0] === 'conditional') return true; + 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 (type === 'if' || type === 'while') { - var cond = node[1]; - if (cond[0] === 'binary' && (cond[1] === '|' || cond[1] === '&') && cond[3][0] !== 'num' && cond[2][0] !== 'num') { - // logical operator on two non-numerical values, all inside a condition - var left = cond[2]; - var right = cond[3]; - 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 + 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; - } 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 - if (cond[1] === '|') { - node[1] = ['conditional', left, ['num', 1], right]; - } else { // & - node[1] = ['conditional', left, right, ['num', 0]]; - } - if (left[0] === 'unary-prefix' && left[1] === '!') { - node[1][1] = flipCondition(left); - var temp = node[1][2]; - node[1][2] = node[1][3]; - node[1][3] = 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; } }); } @@ -3978,7 +3985,10 @@ function measureCost(ast) { var size = 0; traverse(ast, function(node, type) { if (type === 'num' || type === 'unary-prefix') size--; - else if (type === 'binary' && node[3][0] === 'num' && node[3][1] === 0) 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++; diff --git a/tools/test-js-optimizer-asm-pre-output.js b/tools/test-js-optimizer-asm-pre-output.js index d6a7a04b..31b9cfd7 100644 --- a/tools/test-js-optimizer-asm-pre-output.js +++ b/tools/test-js-optimizer-asm-pre-output.js @@ -596,5 +596,6 @@ function conditionalizeMe() { if (x > 10 | HEAP[20] + 2 > 5) { b(); } + return (((((Math_imul(i6 + 1, i7) | 0) + 17 | 0) % 5 | 0) == 0 ? 1 : ((((Math_imul(i7 + 1, i7) | 0) + 11 | 0) >>> 0) % 3 | 0) == 0) | 0) == 0; } diff --git a/tools/test-js-optimizer-asm-pre.js b/tools/test-js-optimizer-asm-pre.js index f930fc13..2a6ea4a9 100644 --- a/tools/test-js-optimizer-asm-pre.js +++ b/tools/test-js-optimizer-asm-pre.js @@ -608,5 +608,6 @@ function conditionalizeMe() { if (x > 10 | (HEAP[20] + 2) > 5) { b(); } + return ((((Math_imul(i6+1, i7) | 0) + 17 | 0) % 5 | 0 | 0) == 0 | ((((Math_imul(i7+1, i7) | 0) + 11 | 0) >>> 0) % 3 | 0 | 0) == 0 | 0) == 0; } // EMSCRIPTEN_GENERATED_FUNCTIONS: ["a", "b", "rett", "ret2t", "retf", "i32_8", "tempDoublePtr", "boxx", "_main", "badf", "badf2", "fcomp", "conditionalizeMe"] -- cgit v1.2.3-70-g09d2 From b312ce10210b22db941c64502b87c032360a0f70 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Fri, 16 May 2014 11:02:03 -0700 Subject: optimize loop vars even if there is some code (like a phi) in the if block where the loop break is, if it does not interfere --- tools/eliminator/asm-eliminator-test-output.js | 35 ++++++++++++++++++-------- tools/eliminator/asm-eliminator-test.js | 18 ++++++++++++- tools/js-optimizer.js | 15 +++++++++-- 3 files changed, 54 insertions(+), 14 deletions(-) (limited to 'tools/js-optimizer.js') diff --git a/tools/eliminator/asm-eliminator-test-output.js b/tools/eliminator/asm-eliminator-test-output.js index 1a5dca55..bf4b111f 100644 --- a/tools/eliminator/asm-eliminator-test-output.js +++ b/tools/eliminator/asm-eliminator-test-output.js @@ -24,7 +24,7 @@ function __Z11printResultPiS_j($needle, $haystack, $len) { } function _segment_holding($addr) { $addr = $addr | 0; - var $sp_0 = 0, $3 = 0, $12 = 0, $_0 = 0, label = 0; + var $sp_0 = 0, $3 = 0, $_0 = 0, label = 0; $sp_0 = __gm_ + 444 | 0; while (1) { $3 = HEAP32[(($sp_0 | 0) & 16777215) >> 2] | 0; @@ -35,13 +35,11 @@ function _segment_holding($addr) { break; } } - $12 = HEAP32[(($sp_0 + 8 | 0) & 16777215) >> 2] | 0; - if (($12 | 0) == 0) { + $sp_0 = HEAP32[(($sp_0 + 8 | 0) & 16777215) >> 2] | 0; + if (($sp_0 | 0) == 0) { $_0 = 0; label = 1659; break; - } else { - $sp_0 = $12; } } if (label == 1659) { @@ -818,7 +816,7 @@ function selfAssign() { function elimOneLoopVar($argc, $argv) { $argc = $argc | 0; $argv = $argv | 0; - var $arg$0 = 0, $call10 = Math_fround(0), $curri$012 = 0, $inc = 0, $j$010 = 0, $ok$0 = 0, $primes$011 = 0, $retval$0 = 0, $vararg_buffer1 = 0; + var $arg$0 = 0, $call10 = Math_fround(0), $curri$012 = 0, $j$010 = 0, $ok$0 = 0, $primes$011 = 0, $retval$0 = 0, $vararg_buffer1 = 0, $j$010$looptemp = 0; $curri$012 = 2; $primes$011 = 0; while (1) { @@ -827,14 +825,13 @@ function elimOneLoopVar($argc, $argv) { if ($call10 > Math_fround(+2)) { $j$010 = 2; while (1) { - $inc = $j$010 + 1 | 0; - if ((($curri$012 | 0) % ($j$010 | 0) & -1 | 0) == 0) { + $j$010$looptemp = $j$010; + $j$010 = $j$010 + 1 | 0; + if ((($curri$012 | 0) % ($j$010$looptemp | 0) & -1 | 0) == 0) { $ok$0 = 0; break L15; } - if (Math_fround($inc | 0) < $call10) { - $j$010 = $inc; - } else { + if (!(Math_fround($j$010 | 0) < $call10)) { $ok$0 = 1; break; } @@ -911,4 +908,20 @@ function elimOneLoopVarStillUsed() { } return $retval$0 | 0; } +function elimOneLoopVar5() { + var $storemerge3$neg9 = 0, $18 = 0, $25 = 0, $26 = 0, $30 = 0, $jp = 0; + $storemerge3$neg9 = -1; + while (1) { + $25 = $jp + ($26 << 2) | 0; + HEAP32[$25 >> 2] = ($18 + $storemerge3$neg9 | 0) + (HEAP32[$25 >> 2] | 0) | 0; + $30 = $26 + 1 | 0; + if (($30 | 0) == 63) { + f($30); + break; + } else { + $storemerge3$neg9 = $18 ^ -1; + $26 = $30; + } + } +} diff --git a/tools/eliminator/asm-eliminator-test.js b/tools/eliminator/asm-eliminator-test.js index d5bbd8d5..5bec0507 100644 --- a/tools/eliminator/asm-eliminator-test.js +++ b/tools/eliminator/asm-eliminator-test.js @@ -1152,5 +1152,21 @@ function elimOneLoopVarStillUsed() { } return $retval$0 | 0; } -// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed"] +function elimOneLoopVar5() { + var $storemerge3$neg9 = 0, $18 = 0, $25 = 0, $26 = 0, $30 = 0, $jp = 0; + $storemerge3$neg9 = -1; + while (1) { + $25 = $jp + ($26 << 2) | 0; + HEAP32[$25 >> 2] = ($18 + $storemerge3$neg9 | 0) + (HEAP32[$25 >> 2] | 0) | 0; + $30 = $26 + 1 | 0; + if (($30 | 0) == 63) { + f($30); // loop var used here, so cannot be easily optimized + break; + } else { + $storemerge3$neg9 = $18 ^ -1; + $26 = $30; + } + } +} +// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed", "elimOneLoopVar5"] diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index f38ff08c..699ea280 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -3585,13 +3585,13 @@ function eliminate(ast, memSafe) { 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 = []; @@ -3628,6 +3628,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]; -- cgit v1.2.3-70-g09d2 From 398cded47b7e08fbb753fb7b4788da29a22195bb Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Fri, 16 May 2014 14:16:40 -0700 Subject: merge loop and helper variables when their use ranges do not overlap --- tools/eliminator/asm-eliminator-test-output.js | 22 ++++++-- tools/eliminator/asm-eliminator-test.js | 23 ++++++++- tools/js-optimizer.js | 69 ++++++++++++++++++++++---- 3 files changed, 99 insertions(+), 15 deletions(-) (limited to 'tools/js-optimizer.js') diff --git a/tools/eliminator/asm-eliminator-test-output.js b/tools/eliminator/asm-eliminator-test-output.js index bf4b111f..50bd8f49 100644 --- a/tools/eliminator/asm-eliminator-test-output.js +++ b/tools/eliminator/asm-eliminator-test-output.js @@ -816,7 +816,7 @@ function selfAssign() { function elimOneLoopVar($argc, $argv) { $argc = $argc | 0; $argv = $argv | 0; - var $arg$0 = 0, $call10 = Math_fround(0), $curri$012 = 0, $j$010 = 0, $ok$0 = 0, $primes$011 = 0, $retval$0 = 0, $vararg_buffer1 = 0, $j$010$looptemp = 0; + var $arg$0 = 0, $call10 = Math_fround(0), $curri$012 = 0, $j$010 = 0, $ok$0 = 0, $primes$011 = 0, $retval$0 = 0, $vararg_buffer1 = 0; $curri$012 = 2; $primes$011 = 0; while (1) { @@ -825,12 +825,11 @@ function elimOneLoopVar($argc, $argv) { if ($call10 > Math_fround(+2)) { $j$010 = 2; while (1) { - $j$010$looptemp = $j$010; - $j$010 = $j$010 + 1 | 0; - if ((($curri$012 | 0) % ($j$010$looptemp | 0) & -1 | 0) == 0) { + if ((($curri$012 | 0) % ($j$010 | 0) & -1 | 0) == 0) { $ok$0 = 0; break L15; } + $j$010 = $j$010 + 1 | 0; if (!(Math_fround($j$010 | 0) < $call10)) { $ok$0 = 1; break; @@ -895,10 +894,23 @@ function elimOneLoopVar4() { } } function elimOneLoopVarStillUsed() { + var $call10 = Math_fround(0), $curri$012 = 0, $j$010 = 0, $retval$0 = 0; + while (1) { + if ((($curri$012 | 0) % ($j$010 | 0) & -1 | 0) == 0) { + break; + } + $j$010 = $j$010 + 1 | 0; + if (!(Math_fround($j$010 | 0) < $call10)) { + break; + } + } + return $retval$0 | 0; +} +function elimOneLoopVarStillUsedSE() { var $call10 = Math_fround(0), $curri$012 = 0, $j$010 = 0, $retval$0 = 0, $j$010$looptemp = 0; while (1) { $j$010$looptemp = $j$010; - $j$010 = $j$010 + 1 | 0; + $j$010 = $j$010 + sideeffect() | 0; if ((($curri$012 | 0) % ($j$010$looptemp | 0) & -1 | 0) == 0) { break; } diff --git a/tools/eliminator/asm-eliminator-test.js b/tools/eliminator/asm-eliminator-test.js index 5bec0507..2613b356 100644 --- a/tools/eliminator/asm-eliminator-test.js +++ b/tools/eliminator/asm-eliminator-test.js @@ -1152,6 +1152,27 @@ function elimOneLoopVarStillUsed() { } return $retval$0 | 0; } +function elimOneLoopVarStillUsedSE() { + var $0 = 0, $1 = 0, $arg$0 = 0, $arrayidx = 0, $call10 = Math_fround(0), $cmp = 0, $cmp11 = 0, $cmp119 = 0, $cmp12 = 0, $cmp7 = 0, $conv = 0, $conv8 = Math_fround(0), $conv9 = Math_fround(0), $curri$012 = 0, $inc = 0, $inc14$primes$0 = 0, $inc16 = 0, $j$010 = 0, $ok$0 = 0; + var $primes$011 = 0, $rem = 0, $retval$0 = 0, $sub = 0, $vararg_buffer1 = 0, label = 0, sp = 0; + while (1) { + $rem = ($curri$012 | 0) % ($j$010 | 0) & -1; + $cmp12 = ($rem | 0) == 0; + $inc = $j$010 + sideeffect() | 0; // side effect! + if ($cmp12) { + $ok$0 = 0; + break; + } + $conv8 = Math_fround($inc | 0); + $cmp11 = $conv8 < $call10; + if ($cmp11) { + $j$010 = $inc; + } else { + break; + } + } + return $retval$0 | 0; +} function elimOneLoopVar5() { var $storemerge3$neg9 = 0, $18 = 0, $25 = 0, $26 = 0, $30 = 0, $jp = 0; $storemerge3$neg9 = -1; @@ -1168,5 +1189,5 @@ function elimOneLoopVar5() { } } } -// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed", "elimOneLoopVar5"] +// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed", "elimOneLoopVarStillUsedSE", "elimOneLoopVar5"] diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 699ea280..fe00254a 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -1034,6 +1034,27 @@ function hasSideEffects(node) { // this is 99% incomplete! } } +// 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) { @@ -3662,21 +3683,51 @@ function eliminate(ast, memSafe) { // 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!) - var temp = looper + '$looptemp'; - var looperUsed = false; - assert(!(temp in asmData.vars)); + // 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) { - node[1] = temp; - looperUsed = 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) { - asmData.vars[temp] = asmData.vars[looper]; - stats.splice(found, 0, ['stat', ['assign', true, ['name', temp], ['name', looper]]]); + 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)) { + // 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 + // 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(node, type) { + if (type === 'name') { + if (node[1] === looper) { + node[1] = temp; + } + } + }); + } + 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++) { -- cgit v1.2.3-70-g09d2 From 57360800512dc1b23532e1c125c8e0627ccdbcfa Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 17 May 2014 20:53:41 -0700 Subject: fix looptemp replacements when there is a continue with a phi of the loop variable --- tools/eliminator/asm-eliminator-test-output.js | 18 ++++++++++++++++++ tools/eliminator/asm-eliminator-test.js | 19 +++++++++++++++++++ tools/js-optimizer.js | 6 +++++- 3 files changed, 42 insertions(+), 1 deletion(-) (limited to 'tools/js-optimizer.js') diff --git a/tools/eliminator/asm-eliminator-test-output.js b/tools/eliminator/asm-eliminator-test-output.js index 50bd8f49..d530a90c 100644 --- a/tools/eliminator/asm-eliminator-test-output.js +++ b/tools/eliminator/asm-eliminator-test-output.js @@ -936,4 +936,22 @@ function elimOneLoopVar5() { } } } +function loopVarWithContinue() { + var i = 0, i$looptemp = 0; + i = 0; + while (1) { + i$looptemp = i; + i = i + 1; + if (check()) { + i = i$looptemp + 1; + continue; + } + work(i); + work(i$looptemp); + work(i); + if (check()) { + break; + } + } +} diff --git a/tools/eliminator/asm-eliminator-test.js b/tools/eliminator/asm-eliminator-test.js index 2613b356..8c469964 100644 --- a/tools/eliminator/asm-eliminator-test.js +++ b/tools/eliminator/asm-eliminator-test.js @@ -1189,5 +1189,24 @@ function elimOneLoopVar5() { } } } +function loopVarWithContinue() { + var i = 0, inc = 0; + i = 0; + while (1) { + inc = i + 1; + if (check()) { + i = i + 1; + continue; + } + work(inc); + work(i); + work(inc); + if (check()) { + break; + } else { + i = inc; + } + } +} // EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed", "elimOneLoopVarStillUsedSE", "elimOneLoopVar5"] diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index fe00254a..c0096df4 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -3717,11 +3717,15 @@ function eliminate(ast, memSafe) { 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(node, type) { + 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; } }); } -- cgit v1.2.3-70-g09d2 From a4ae7a1c29e7873f77ea4168e1c8c2c66a7cb34a Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 19 May 2014 10:45:29 -0700 Subject: do not move around loop variable incrementations when the helper is used outside the loop --- tools/eliminator/asm-eliminator-test-output.js | 14 ++++++++++++++ tools/eliminator/asm-eliminator-test.js | 17 ++++++++++++++++- tools/js-optimizer.js | 4 +++- 3 files changed, 33 insertions(+), 2 deletions(-) (limited to 'tools/js-optimizer.js') diff --git a/tools/eliminator/asm-eliminator-test-output.js b/tools/eliminator/asm-eliminator-test-output.js index d530a90c..ab4c13cc 100644 --- a/tools/eliminator/asm-eliminator-test-output.js +++ b/tools/eliminator/asm-eliminator-test-output.js @@ -954,4 +954,18 @@ function loopVarWithContinue() { } } } +function helperExtraUse() { + var i = 0, i$looptemp = 0; + i = 0; + while (1) { + i$looptemp = i; + i = i + 1; + work(i$looptemp); + work(i); + if (check()) { + break; + } + } + return i; +} diff --git a/tools/eliminator/asm-eliminator-test.js b/tools/eliminator/asm-eliminator-test.js index 8c469964..7b949c44 100644 --- a/tools/eliminator/asm-eliminator-test.js +++ b/tools/eliminator/asm-eliminator-test.js @@ -1208,5 +1208,20 @@ function loopVarWithContinue() { } } } -// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed", "elimOneLoopVarStillUsedSE", "elimOneLoopVar5"] +function helperExtraUse() { + var i = 0, inc = 0; + i = 0; + while (1) { + inc = i + 1; + work(i); + work(inc); + if (check()) { + break; + } else { + i = inc; + } + } + return inc; +} +// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc", "label", "confuusion", "tempDouble", "_org_apache_harmony_luni_util_NumberConverter_freeFormat__", "__ZN23b2EdgeAndPolygonContact8EvaluateEP10b2ManifoldRK11b2TransformS4_", "_java_nio_charset_Charset_forNameInternal___java_lang_String", "looop2", "looop3", "looop4", "looop5", "looop6", "looop7", "looop8", "multiloop", "multiloop2", "tempDouble2", "watIf", "select2", "binary", "cute", "selfAssign", "elimOneLoopVar", "elimOneLoopVar2", "elimOneLoopVar3", "elimOneLoopVar4", "elimOneLoopVarStillUsed", "elimOneLoopVarStillUsedSE", "elimOneLoopVar5", "helperExtraUse"] diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index c0096df4..0cd27aa8 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -3704,9 +3704,11 @@ function eliminate(ast, memSafe) { } 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)) { + 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); -- cgit v1.2.3-70-g09d2 From 4de2914fe17f3b3e169329ad35022e3ee124114a Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 19 May 2014 11:51:06 -0700 Subject: fix emitsBoolean handling of conditional, and add handling of num --- tools/js-optimizer.js | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'tools/js-optimizer.js') diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 0cd27aa8..d89145d5 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -750,9 +750,12 @@ 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 true; + if (node[0] === 'conditional') return emitsBoolean(node[2]) && emitsBoolean(node[3]); return false; } -- cgit v1.2.3-70-g09d2 From a89d3e95a760f8ed931a762a60d3103cb526d7dc Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 19 May 2014 11:51:53 -0700 Subject: add conditional to hasSideEffects --- tools/js-optimizer.js | 1 + 1 file changed, 1 insertion(+) (limited to 'tools/js-optimizer.js') diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index d89145d5..088c4f0f 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -1033,6 +1033,7 @@ function hasSideEffects(node) { // this is 99% incomplete! } return false; } + case 'conditional': return hasSideEffects(node[1]) || hasSideEffects(node[2]) || hasSideEffects(node[3]); default: return true; } } -- cgit v1.2.3-70-g09d2