diff options
Diffstat (limited to 'tools')
26 files changed, 1980 insertions, 923 deletions
diff --git a/tools/eliminator/asm-eliminator-test-output.js b/tools/eliminator/asm-eliminator-test-output.js index 7a8baef2..1a5dca55 100644 --- a/tools/eliminator/asm-eliminator-test-output.js +++ b/tools/eliminator/asm-eliminator-test-output.js @@ -147,27 +147,25 @@ function looop3() { } } function looop4() { - var i = 0, helper = 0; + var i = 0, i$looptemp = 0; while (1) { do_it(); - helper = i + 1 | 0; - f(i, helper); - if (condition()) { - i = helper; - } else { + i$looptemp = i; + i = i + 1 | 0; + f(i$looptemp, i); + if (!condition()) { break; } } } function looop4b() { - var i = 0, helper = 0; + var i = 0, i$looptemp = 0; while (1) { do_it(); - helper = i + 1 | 0; - g(helper); - if (condition(i)) { - i = helper; - } else { + i$looptemp = i; + i = i + 1 | 0; + g(i); + if (!condition(i$looptemp)) { break; } } @@ -251,24 +249,22 @@ function multiloop($n_0, $35) { function multiloop2($n_0, $35) { $n_0 = $n_0 | 0; $35 = $35 | 0; - var $p_0 = 0, $39 = 0, $41 = 0, $46 = 0; + var $p_0 = 0, $41 = 0, $p_0$looptemp = 0; $n_0 = $35; $p_0 = (HEAP32[$15 >> 2] | 0) + ($35 << 1) | 0; while (1) { - $39 = $p_0 - 2 | 0; - $41 = HEAPU16[$39 >> 1] | 0; + $p_0$looptemp = $p_0; + $p_0 = $p_0 - 2 | 0; + $41 = HEAPU16[$p_0 >> 1] | 0; if ($41 >>> 0 < $2 >>> 0) { $_off0 = 0; } else { $_off0 = $41 - $2 & 65535; } - HEAP16[$39 >> 1] = $p_0; - $46 = $n_0 - 1 | 0; - if (($46 | 0) == 0) { + HEAP16[$p_0 >> 1] = $p_0$looptemp; + $n_0 = $n_0 - 1 | 0; + if (($n_0 | 0) == 0) { break; - } else { - $n_0 = $46; - $p_0 = $39; } } } @@ -810,4 +806,109 @@ function cute($this, $outImage) { } return 0; } +function selfAssign() { + var i1 = 0; + i1 = HEAP32[2] | 0; + HEAP32[2] = i1 + 1; + if (waka) { + return 0; + } + return i1 & 16384 | 0; +} +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; + $curri$012 = 2; + $primes$011 = 0; + while (1) { + $call10 = Math_fround(Math_sqrt(Math_fround(Math_fround($curri$012 | 0)))); + L15 : do { + 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) { + $ok$0 = 0; + break L15; + } + if (Math_fround($inc | 0) < $call10) { + $j$010 = $inc; + } else { + $ok$0 = 1; + break; + } + } + } else { + $ok$0 = 1; + } + } while (0); + $primes$011 = $ok$0 + $primes$011 | 0; + if (($primes$011 | 0) >= ($arg$0 | 0)) { + break; + } else { + $curri$012 = $curri$012 + 1 | 0; + } + } + HEAP32[$vararg_buffer1 >> 2] = $curri$012; + return $retval$0 | 0; +} +function elimOneLoopVar2() { + 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) { + break; + } else { + $storemerge3$neg9 = $26 ^ -1; + $26 = $30; + } + } +} +function elimOneLoopVar3() { + 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) { + break; + } else { + $storemerge3$neg9 = $30 ^ -1; + $26 = $30; + } + } +} +function elimOneLoopVar4() { + var $storemerge3$neg9 = 0, $18 = 0, $25 = 0, $26 = 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; + $26 = $26 + 1 | 0; + if (($26 | 0) == 63) { + break; + } else { + $storemerge3$neg9 = $18 ^ -1; + } + } +} +function elimOneLoopVarStillUsed() { + 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; + if ((($curri$012 | 0) % ($j$010$looptemp | 0) & -1 | 0) == 0) { + break; + } + if (!(Math_fround($j$010 | 0) < $call10)) { + break; + } + } + return $retval$0 | 0; +} diff --git a/tools/eliminator/asm-eliminator-test.js b/tools/eliminator/asm-eliminator-test.js index ad1ed05e..d5bbd8d5 100644 --- a/tools/eliminator/asm-eliminator-test.js +++ b/tools/eliminator/asm-eliminator-test.js @@ -1027,5 +1027,130 @@ function cute($this, $outImage) { } return 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"] +function selfAssign() { + var i1 = 0; + i1 = HEAP32[2] | 0; + HEAP32[2] = i1 + 1; + if (waka) { + return (STACKTOP = STACKTOP, 0); + } + STACKTOP = STACKTOP; + return i1 & 16384 | 0; +} +function elimOneLoopVar($argc, $argv) { + $argc = $argc | 0; + $argv = $argv | 0; + 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, $j$010$phi = 0, $ok$0 = 0; + var $primes$011 = 0, $rem = 0, $retval$0 = 0, $sub = 0, $vararg_buffer1 = 0, label = 0, sp = 0; + $curri$012 = 2; + $primes$011 = 0; + while (1) { + $conv9 = Math_fround($curri$012 | 0); + $call10 = Math_fround(Math_sqrt(Math_fround($conv9))); + $cmp119 = $call10 > Math_fround(+2); + L15 : do { + if ($cmp119) { + $j$010 = 2; + while (1) { + $rem = ($curri$012 | 0) % ($j$010 | 0) & -1; + $cmp12 = ($rem | 0) == 0; + $inc = $j$010 + 1 | 0; + if ($cmp12) { + $ok$0 = 0; + break L15; + } + $conv8 = Math_fround($inc | 0); + $cmp11 = $conv8 < $call10; + if ($cmp11) { + $j$010$phi = $inc; + $j$010 = $j$010$phi; + } else { + $ok$0 = 1; + break; + } + } + } else { + $ok$0 = 1; + } + } while (0); + $inc14$primes$0 = $ok$0 + $primes$011 | 0; + $inc16 = $curri$012 + 1 | 0; + $cmp7 = ($inc14$primes$0 | 0) < ($arg$0 | 0); + if ($cmp7) { + $curri$012 = $inc16; + $primes$011 = $inc14$primes$0; + } else { + break; + } + } + HEAP32[$vararg_buffer1 >> 2] = $curri$012; + return $retval$0 | 0; +} +function elimOneLoopVar2() { + 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) { + break; + } else { + $storemerge3$neg9 = $26 ^ -1; // $26 is a loopvar, use here is dangerous + $26 = $30; + } + } +} +function elimOneLoopVar3() { + 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) { + break; + } else { + $storemerge3$neg9 = $30 ^ -1; // $26 is a helper, use here is dangerous + $26 = $30; + } + } +} +function elimOneLoopVar4() { + 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) { + break; + } else { + $storemerge3$neg9 = $18 ^ -1; + $26 = $30; + } + } +} +function elimOneLoopVarStillUsed() { + 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 + 1 | 0; + 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; +} +// 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"] diff --git a/tools/file_packager.py b/tools/file_packager.py index 12cc5475..0ab68511 100644 --- a/tools/file_packager.py +++ b/tools/file_packager.py @@ -113,7 +113,7 @@ for arg in sys.argv[2:]: try: from shared import CRUNCH except Exception, e: - print >> sys.stderr, 'count not import CRUNCH (make sure it is defined properly in ~/.emscripten)' + print >> sys.stderr, 'could not import CRUNCH (make sure it is defined properly in ~/.emscripten)' raise e crunch = arg.split('=')[1] if '=' in arg else '128' leading = '' @@ -123,12 +123,13 @@ for arg in sys.argv[2:]: leading = '' elif leading == 'preload' or leading == 'embed': mode = leading - if '@' in arg: + uses_at_notation = '@' in arg + if uses_at_notation: srcpath, dstpath = arg.split('@') # User is specifying destination filename explicitly. else: srcpath = dstpath = arg # Use source path as destination path. if os.path.isfile(srcpath) or os.path.isdir(srcpath): - data_files.append({ 'srcpath': srcpath, 'dstpath': dstpath, 'mode': mode }) + data_files.append({ 'srcpath': srcpath, 'dstpath': dstpath, 'mode': mode, 'explicit_dst_path': uses_at_notation }) else: print >> sys.stderr, 'Warning: ' + arg + ' does not exist, ignoring.' elif leading == 'exclude': @@ -206,7 +207,7 @@ def add(arg, dirname, names): new_names.append(name) if not os.path.isdir(fullname): dstpath = os.path.join(rootpathdst, os.path.relpath(fullname, rootpathsrc)) # Convert source filename relative to root directory of target FS. - new_data_files.append({ 'srcpath': fullname, 'dstpath': dstpath, 'mode': mode }) + new_data_files.append({ 'srcpath': fullname, 'dstpath': dstpath, 'mode': mode, 'explicit_dst_path': True }) del names[:] names.extend(new_names) @@ -223,13 +224,14 @@ if len(data_files) == 0: sys.exit(1) # Absolutize paths, and check that they make sense -curr_abspath = os.path.abspath(os.getcwd()) +curr_abspath = os.path.abspath(os.getcwd()) # os.getcwd() always returns the hard path with any symbolic links resolved, even if we cd'd into a symbolic link. + for file_ in data_files: - if file_['srcpath'] == file_['dstpath']: + if not file_['explicit_dst_path']: # This file was not defined with src@dst, so we inferred the destination from the source. In that case, # we require that the destination not be under the current location path = file_['dstpath'] - abspath = os.path.abspath(path) + abspath = os.path.realpath(os.path.abspath(path)) # Use os.path.realpath to resolve any symbolic links to hard paths, to match the structure in curr_abspath. if DEBUG: print >> sys.stderr, path, abspath, curr_abspath if not abspath.startswith(curr_abspath): print >> sys.stderr, 'Error: Embedding "%s" which is below the current directory "%s". This is invalid since the current directory becomes the root that the generated code will see' % (path, curr_abspath) diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index fc195e03..32c26c51 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -140,6 +140,8 @@ var ALTER_FLOW = set('break', 'continue', 'return'); var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch'); var CONTINUE_CAPTURERS = LOOP; +var COMMABLE = set('assign', 'binary', 'unary-prefix', 'unary-postfix', 'name', 'num', 'call', 'seq', 'conditional', 'sub'); + var FUNCTIONS_THAT_ALWAYS_THROW = set('abort', '___resumeException', '___cxa_throw', '___cxa_rethrow'); var NULL_NODE = ['name', 'null']; @@ -167,11 +169,11 @@ function astToSrc(ast, minifyWhitespace) { // Traverses the children of a node. If the traverse function returns an object, // replaces the child. If it returns true, stop the traversal and return true. -function traverseChildren(node, traverse, pre, post, stack) { +function traverseChildren(node, traverse, pre, post) { for (var i = 0; i < node.length; i++) { var subnode = node[i]; if (Array.isArray(subnode)) { - var subresult = traverse(subnode, pre, post, stack); + var subresult = traverse(subnode, pre, post); if (subresult === true) return true; if (subresult !== null && typeof subresult === 'object') node[i] = subresult; } @@ -187,30 +189,24 @@ function traverseChildren(node, traverse, pre, post, stack) { // it replaces the passed node in the tree. If null is returned, we stop // traversing the subelements (but continue otherwise). // @arg post: A callback to call after traversing all children. -// @arg stack: If true, a stack will be implemented: If pre does not push on -// the stack, we push a 0. We pop when we leave the node. The -// stack is passed as a third parameter to the callbacks. // @returns: If the root node was replaced, the new root node. If the traversal // was stopped, true. Otherwise undefined. -function traverse(node, pre, post, stack) { +function traverse(node, pre, post) { var type = node[0], result, len; var relevant = typeof type === 'string'; if (relevant) { - if (stack) len = stack.length; - var result = pre(node, type, stack); + var result = pre(node, type); if (result === true) return true; if (result && result !== null) node = result; // Continue processing on this node - if (stack && len === stack.length) stack.push(0); } if (result !== null) { - if (traverseChildren(node, traverse, pre, post, stack) === true) return true; + if (traverseChildren(node, traverse, pre, post) === true) return true; } if (relevant) { if (post) { - var postResult = post(node, type, stack); + var postResult = post(node, type); result = result || postResult; } - if (stack) stack.pop(); } return result; } @@ -229,38 +225,12 @@ function traverseGeneratedFunctions(ast, callback) { } } -function traverseGenerated(ast, pre, post, stack) { +function traverseGenerated(ast, pre, post) { traverseGeneratedFunctions(ast, function(func) { - traverse(func, pre, post, stack); + traverse(func, pre, post); }); } -// Walk the ast in a simple way, with an understanding of which JS variables are defined) -function traverseWithVariables(ast, callback) { - traverse(ast, function(node, type, stack) { - if (type in FUNCTION) { - stack.push({ type: 'function', vars: node[2] }); - } else if (type === 'var') { - // Find our function, add our vars - var func = stack[stack.length-1]; - if (func) { - func.vars = func.vars.concat(node[1].map(function(varItem) { return varItem[0] })); - } - } - }, function(node, type, stack) { - if (type === 'toplevel' || type in FUNCTION) { - // We know all of the variables that are seen here, proceed to do relevant replacements - var allVars = stack.map(function(item) { return item ? item.vars : [] }).reduce(concatenator, []); // FIXME dictionary for speed? - traverse(node, function(node2, type2, stack2) { - // Be careful not to look into our inner functions. They have already been processed. - if (sum(stack2) > 1 || (type === 'toplevel' && sum(stack2) === 1)) return; - if (type2 in FUNCTION) stack2.push(1); - return callback(node2, type2, allVars); - }, null, []); - } - }, []); -} - function emptyNode() { // XXX do we need to create new nodes here? can't we reuse? return ['toplevel', []] } @@ -279,6 +249,40 @@ function clearEmptyNodes(list) { } } +function filterEmptyNodes(list) { // creates a copy and returns it + return list.filter(function(node) { + return !(isEmptyNode(node) || (node[0] === 'stat' && isEmptyNode(node[1]))); + }); +} + +function removeEmptySubNodes(node) { + if (node[0] === 'defun') { + node[3] = filterEmptyNodes(node[3]); + } else if (node[0] === 'block' && node[1]) { + node[1] = filterEmptyNodes(node[1]); + } else if (node[0] === 'seq' && isEmptyNode(node[1])) { + return node[2]; + } +/* + var stats = getStatements(node); + if (stats) clearEmptyNodes(stats); +*/ +} + +function removeAllEmptySubNodes(ast) { + traverse(ast, removeEmptySubNodes); +} + +function astCompare(x, y) { + if (!Array.isArray(x)) return x === y; + if (!Array.isArray(y)) return false; + if (x.length !== y.length) return false; + for (var i = 0; i < x.length; i++) { + if (!astCompare(x[i], y[i])) return false; + } + return true; +} + // Passes // Dump the AST. Useful for debugging. For example, @@ -291,58 +295,6 @@ function dumpSrc(ast) { printErr(astToSrc(ast)); } -// Undos closure's creation of global variables with values true, false, -// undefined, null. These cut down on size, but do not affect gzip size -// and make JS engine's lives slightly harder (?) -function unGlobalize(ast) { - - throw 'this is deprecated!'; // and does not work with parallel compilation - - assert(ast[0] === 'toplevel'); - var values = {}; - // Find global renamings of the relevant values - ast[1].forEach(function(node, i) { - if (node[0] != 'var') return; - node[1] = node[1].filter(function(varItem, j) { - var ident = varItem[0]; - var value = varItem[1]; - if (!value) return true; - var possible = false; - if (jsonCompare(value, NULL_NODE) || - jsonCompare(value, UNDEFINED_NODE) || - jsonCompare(value, TRUE_NODE) || - jsonCompare(value, FALSE_NODE)) { - possible = true; - } - if (!possible) return true; - // Make sure there are no assignments to this variable. (This isn't fast, we traverse many times..) - ast[1][i][1][j] = emptyNode(); - var assigned = false; - traverseWithVariables(ast, function(node, type, allVars) { - if (type === 'assign' && node[2][0] === 'name' && node[2][1] === ident) assigned = true; - }); - ast[1][i][1][j] = [ident, value]; - if (!assigned) { - values[ident] = value; - return false; - } - return true; - }); - - if (node[1].length === 0) { - ast[1][i] = emptyNode(); - } - }); - traverseWithVariables(ast, function(node, type, allVars) { - if (type === 'name') { - var ident = node[1]; - if (ident in values && allVars.indexOf(ident) < 0) { - return copy(values[ident]); - } - } - }); -} - // Closure compiler, when inlining, will insert assignments to // undefined for the shared variables. However, in compiled code // - and in library/shell code too! - we should never rely on @@ -414,7 +366,7 @@ function removeUnneededLabelSettings(ast) { }); } -// Various expression simplifications. Pre run before closure (where we still have metadata), Post run after. +// Various expression simplifications. Happens after elimination, which opens up many of these simplification opportunities. var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^'); var COMPARE_OPS = set('<', '<=', '>', '>=', '==', '===', '!=', '!=='); @@ -469,10 +421,12 @@ function simplifyExpressions(ast) { var rerun = true; while (rerun) { rerun = false; - traverse(ast, function process(node, type, stack) { + var stack = []; + traverse(ast, function process(node, type) { if (type === 'binary' && node[1] === '|') { if (node[2][0] === 'num' && node[3][0] === 'num') { node[2][1] |= node[3][1]; + stack.push(0); return node[2]; } var go = false; @@ -505,7 +459,7 @@ function simplifyExpressions(ast) { node[j] = result[j]; } rerun = true; - return process(result, result[0], stack); + return process(result, result[0]); } else if (stack[i] === -1) { break; // Too bad, we can't } @@ -521,7 +475,9 @@ function simplifyExpressions(ast) { } else { stack.push(-1); // This node is dangerous! Give up if you see this before you see '1' } - }, null, []); + }, function() { + stack.pop(); + }); } } @@ -797,344 +753,165 @@ function simplifyExpressions(ast) { simplifyIntegerConversions(func); simplifyBitops(func); joinAdditions(func); - // simplifyZeroComp(func); TODO: investigate performance simplifyNotComps(func); + // simplifyZeroComp(func); TODO: investigate performance }); } -// In typed arrays mode 2, we can have -// HEAP[x >> 2] -// very often. We can in some cases do the shift on the variable itself when it is set, -// to greatly reduce the number of shift operations. -// XXX this optimization is deprecated and currently invalid: does not handle overflows -// or non-aligned (round numbers, x >> 2 is a multiple of 4). Both are ok to assume -// for pointers (undefined behavior otherwise), but invalid in general, and we do -// no sufficiently-well distinguish the cases. -function optimizeShiftsInternal(ast, conservative) { - var MAX_SHIFTS = 3; - traverseGeneratedFunctions(ast, function(fun) { - var funMore = true; - var funFinished = {}; - 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 - var hasSwitch = traverse(fun, function(node, type) { - if (type === 'var') { - node[1].forEach(function(arg) { - newVar(arg[0], false, arg[1]); - }); - } else if (type === 'switch') { - // The relooper can't always optimize functions, and we currently don't work with - // switch statements when optimizing shifts. Bail. - return true; - } - }); - if (hasSwitch) { - break; - } - // 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]; - if (shifts <= MAX_SHIFTS) { - // Push the >> inside the value elements - function addShift(subNode) { - if (subNode[0] === 'binary' && subNode[1] === '+') { - subNode[2] = addShift(subNode[2]); - subNode[3] = addShift(subNode[3]); - return subNode; - } - if (subNode[0] === 'name' && !subNode[2]) { // names are returned with a shift, but we also note their being shifted - var name = subNode[1]; - if (vars[name]) { - vars[name].timesShifted[shifts]++; - subNode[2] = true; - } - } - return ['binary', '>>', subNode, ['num', shifts]]; - } - return addShift(node[2]); + +function simplifyIfs(ast) { + traverseGeneratedFunctions(ast, function(func) { + var simplifiedAnElse = false; + + traverse(func, function(node, type) { + // simplify if (x) { if (y) { .. } } to if (x ? y : 0) { .. } + if (type === 'if') { + var body = node[2]; + // recurse to handle chains + while (body[0] === 'block') { + var stats = body[1]; + if (stats.length === 0) break; + var other = stats[stats.length-1]; + if (other[0] !== 'if') { + // our if block does not end with an if. perhaps if have an else we can flip + if (node[3] && node[3][0] === 'block') { + var stats = node[3][1]; + if (stats.length === 0) break; + var other = stats[stats.length-1]; + if (other[0] === 'if') { + // flip node + node[1] = flipCondition(node[1]); + node[2] = node[3]; + node[3] = body; + body = node[2]; + } else break; + } else break; } - } - }); - 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 (funFinished[name]) continue; - // We have one shift size (and possible unshifted uses). Consider replacing this variable with a shifted clone. If - // the estimated benefit is >0, we will do it - if (data.defs === 1) { - data.benefit = totalTimesShifted - 2*(data.defs + (data.param ? 1 : 0)); - } - if (conservative) data.benefit = 0; - 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; + // we can handle elses, but must be fully identical + if (node[3] || other[3]) { + if (!node[3]) break; + if (!astCompare(node[3], other[3])) { + // the elses are different, but perhaps if we flipped a condition we can do better + if (astCompare(node[3], other[2])) { + // flip other. note that other may not have had an else! add one if so; we will eliminate such things later + if (!other[3]) other[3] = ['block', []]; + other[1] = flipCondition(other[1]); + var temp = other[2]; + other[2] = other[3]; + other[3] = temp; + } else break; } } - } - } - //printErr(JSON.stringify(vars)); - function cleanNotes() { // We need to mark 'name' nodes as 'processed' in some passes here; this cleans the notes up |