diff options
Diffstat (limited to 'tools/js-optimizer.js')
| -rw-r--r-- | tools/js-optimizer.js | 1555 |
1 files changed, 1435 insertions, 120 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 5324e15c..81bf8824 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 FUNCTIONS_THAT_ALWAYS_THROW = set('abort', '___resumeException', '___cxa_throw', '___cxa_rethrow'); + var NULL_NODE = ['name', 'null']; var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]]; var TRUE_NODE = ['unary-prefix', '!', ['num', 0]]; @@ -214,16 +216,6 @@ function traverse(node, pre, post, stack) { } // Only walk through the generated functions -function traverseGenerated(ast, pre, post, stack) { - assert(generatedFunctions); - traverse(ast, function(node) { - if (node[0] === 'defun') { - traverse(node, pre, post, stack); - return null; - } - }); -} - function traverseGeneratedFunctions(ast, callback) { assert(generatedFunctions); if (ast[0] === 'toplevel') { @@ -237,6 +229,12 @@ function traverseGeneratedFunctions(ast, callback) { } } +function traverseGenerated(ast, pre, post, stack) { + traverseGeneratedFunctions(ast, function(func) { + traverse(func, pre, post, stack); + }); +} + // 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) { @@ -281,6 +279,28 @@ 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]); + } +/* + var stats = getStatements(node); + if (stats) clearEmptyNodes(stats); +*/ +} + +function removeAllEmptySubNodes(ast) { + traverse(ast, removeEmptySubNodes); +} + // Passes // Dump the AST. Useful for debugging. For example, @@ -722,14 +742,19 @@ function simplifyExpressions(ast) { if (correct === 'HEAP32') { define[3] = ['binary', '|', define[3], ['num', 0]]; } else { - define[3] = ['unary-prefix', '+', define[3]]; + define[3] = makeAsmCoercion(define[3], asmPreciseF32 ? ASM_FLOAT : ASM_DOUBLE); } // do we want a simplifybitops on the new values here? }); info.uses.forEach(function(use) { use[2][1][1] = correct; }); - asmData.vars[v] = 1 - asmData.vars[v]; + var correctType; + switch(asmData.vars[v]) { + case ASM_INT: correctType = asmPreciseF32 ? ASM_FLOAT : ASM_DOUBLE; break; + case ASM_FLOAT: case ASM_DOUBLE: correctType = ASM_INT; break; + } + asmData.vars[v] = correctType; } } denormalizeAsm(ast, asmData); @@ -1138,7 +1163,9 @@ function optimizeShiftsAggressive(ast) { // or such. Simplifying these saves space and time. function simplifyNotCompsDirect(node) { if (node[0] === 'unary-prefix' && node[1] === '!') { - if (node[2][0] === 'binary') { + // de-morgan's laws do not work on floats, due to nans >:( + if (node[2][0] === 'binary' && (!asm || (((node[2][2][0] === 'binary' && node[2][2][1] === '|') || node[2][2][0] === 'num') && + ((node[2][3][0] === 'binary' && node[2][3][1] === '|') || node[2][3][0] === 'num')))) { switch(node[2][1]) { case '<': return ['binary', '>=', node[2][2], node[2][3]]; case '>': return ['binary', '<=', node[2][2], node[2][3]]; @@ -1276,6 +1303,7 @@ function vacuum(ast) { traverseGeneratedFunctions(ast, function(node) { vacuumInternal(node); simplifyNotComps(node); + removeEmptySubNodes(node); }); } @@ -1553,6 +1581,7 @@ function unVarify(vars, ret) { // transform var x=1, y=2 etc. into (x=1, y=2), i var ASM_INT = 0; var ASM_DOUBLE = 1; var ASM_FLOAT = 2; +var ASM_NONE = 3; function detectAsmCoercion(node, asmInfo) { // for params, +x vs x|0, for vars, 0.0 vs 0 @@ -1560,6 +1589,7 @@ function detectAsmCoercion(node, asmInfo) { if (node[0] === 'unary-prefix') return ASM_DOUBLE; if (node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'Math_fround') return ASM_FLOAT; if (asmInfo && node[0] == 'name') return getAsmType(node[1], asmInfo); + if (node[0] === 'name') return ASM_NONE; return ASM_INT; } @@ -1568,7 +1598,8 @@ function makeAsmCoercion(node, type) { case ASM_INT: return ['binary', '|', node, ['num', 0]]; case ASM_DOUBLE: return ['unary-prefix', '+', node]; case ASM_FLOAT: return ['call', ['name', 'Math_fround'], [node]]; - default: throw 'wha? ' + JSON.stringify([node, type]) + new Error().stack; + case ASM_NONE: return node; // non-validating code, emit nothing + default: throw 'whaa?'; } } @@ -1577,7 +1608,7 @@ function makeAsmVarDef(v, type) { case ASM_INT: return [v, ['num', 0]]; case ASM_DOUBLE: return [v, ['unary-prefix', '+', ['num', 0]]]; case ASM_FLOAT: return [v, ['call', ['name', 'Math_fround'], [['num', 0]]]]; - default: throw 'wha?'; + default: throw 'wha? ' + JSON.stringify([node, type]) + new Error().stack; } } @@ -1593,6 +1624,7 @@ function normalizeAsm(func) { params: {}, // ident => ASM_* type vars: {}, // ident => ASM_* type inlines: [], // list of inline assembly copies + ret: undefined, }; // process initial params var stats = func[3]; @@ -1603,6 +1635,7 @@ function normalizeAsm(func) { node = node[1]; var name = node[2][1]; if (func[2] && func[2].indexOf(name) < 0) break; // not an assign into a parameter, but a global + if (name in data.params) break; // already done that param, must be starting function body data.params[name] = detectAsmCoercion(node[3]); stats[i] = emptyNode(); i++; @@ -1628,7 +1661,7 @@ function normalizeAsm(func) { } i++; } - // finally, look for other var definitions and collect them + // look for other var definitions and collect them while (i < stats.length) { traverse(stats[i], function(node, type) { if (type === 'var') { @@ -1657,6 +1690,11 @@ function normalizeAsm(func) { }); i++; } + // look for final 'return' statement to get return type. + var retStmt = stats[stats.length - 1]; + if (retStmt && retStmt[0] === 'return' && retStmt[1]) { + data.ret = detectAsmCoercion(retStmt[1]); + } //printErr('normalized \n\n' + astToSrc(func) + '\n\nwith: ' + JSON.stringify(data)); return data; } @@ -1672,6 +1710,11 @@ function denormalizeAsm(func, data) { if (!isEmptyNode(stats[i])) break; } } + // calculate variable definitions + var varDefs = []; + for (var v in data.vars) { + varDefs.push(makeAsmVarDef(v, data.vars[v])); + } // each param needs a line; reuse emptyNodes as much as we can var numParams = 0; for (var i in data.params) numParams++; @@ -1680,26 +1723,21 @@ function denormalizeAsm(func, data) { if (!isEmptyNode(stats[emptyNodes])) break; emptyNodes++; } - var neededEmptyNodes = numParams + 1; // params plus one big var + var neededEmptyNodes = numParams + (varDefs.length ? 1 : 0); // params plus one big var if there are vars if (neededEmptyNodes > emptyNodes) { var args = [0, 0]; for (var i = 0; i < neededEmptyNodes - emptyNodes; i++) args[i+2] = 0; stats.splice.apply(stats, args); + } else if (neededEmptyNodes < emptyNodes) { + stats.splice(0, emptyNodes - neededEmptyNodes); } // add param coercions var next = 0; func[2].forEach(function(param) { stats[next++] = ['stat', ['assign', true, ['name', param], makeAsmCoercion(['name', param], data.params[param])]]; }); - // add variable definitions - var varDefs = []; - for (var v in data.vars) { - varDefs.push(makeAsmVarDef(v, data.vars[v])); - } if (varDefs.length) { stats[next] = ['var', varDefs]; - } else { - stats[next] = emptyNode(); } if (data.inlines.length > 0) { var i = 0; @@ -1709,6 +1747,17 @@ function denormalizeAsm(func, data) { } }); } + // ensure that there's a final 'return' statement if needed. + if (data.ret !== undefined) { + var retStmt = stats[stats.length - 1]; + if (!retStmt || retStmt[0] !== 'return') { + var retVal = ['num', 0]; + if (data.ret !== ASM_INT) { + retVal = makeAsmCoercion(retVal, data.ret); + } + stats.push(['return', retVal]); + } + } //printErr('denormalized \n\n' + astToSrc(func) + '\n\n'); } @@ -1773,9 +1822,7 @@ function ensureMinifiedNames(n) { // make sure the nth index in minifiedNames ex } } -// Very simple 'registerization', coalescing of variables into a smaller number, -// as part of minification. Globals-level minification began in a previous pass, -// we receive extraInfo which tells us how to rename globals. (Only in asm.js.) +// Very simple 'registerization', coalescing of variables into a smaller number. // // We do not optimize when there are switches, so this pass only makes sense with // relooping. @@ -1811,6 +1858,7 @@ function registerize(ast) { // Replace all var definitions with assignments; we will add var definitions at the top after we registerize // We also mark local variables - i.e., having a var definition var localVars = {}; + var allVars = {}; var hasSwitch = false; // we cannot optimize variables if there is a switch, unless in asm mode traverse(fun, function(node, type) { if (type === 'var') { @@ -1823,74 +1871,25 @@ function registerize(ast) { } } else if (type === 'switch') { hasSwitch = true; + } else if (type === 'name') { + allVars[node[1]] = 1; } }); vacuum(fun); - if (extraInfo && extraInfo.globals) { - assert(asm); - var usedGlobals = {}; - var nextLocal = 0; - // Minify globals using the mapping we were given - traverse(fun, function(node, type) { - if (type === 'name') { - var name = node[1]; - var minified = extraInfo.globals[name]; - if (minified) { - assert(!localVars[name], name); // locals must not shadow globals, or else we don't know which is which - if (localVars[minified]) { - // trying to minify a global into a name used locally. rename all the locals - var newName = '$_newLocal_' + (nextLocal++); - assert(!localVars[newName]); - if (params[minified]) { - params[newName] = 1; - delete params[minified]; - } - localVars[newName] = 1; - delete localVars[minified]; - asmData.vars[newName] = asmData.vars[minified]; - delete asmData.vars[minified]; - asmData.params[newName] = asmData.params[minified]; - delete asmData.params[minified]; - traverse(fun, function(node, type) { - if (type === 'name' && node[1] === minified) { - node[1] = newName; - } - }); - if (fun[2]) { - for (var i = 0; i < fun[2].length; i++) { - if (fun[2][i] === minified) fun[2][i] = newName; - } - } - } - node[1] = minified; - usedGlobals[minified] = 1; - } - } - }); - if (fun[1] in extraInfo.globals) { // if fun was created by a previous optimization pass, it will not be here - fun[1] = extraInfo.globals[fun[1]]; - assert(fun[1]); - } - var nextRegName = 0; - } var regTypes = {}; function getNewRegName(num, name) { - if (!asm) return 'r' + num; - var type = asmData.vars[name]; - if (!extraInfo || !extraInfo.globals) { - var ret = (type ? 'd' : 'i') + num; + var ret; + if (!asm) { + ret = 'r' + num; + } else { + var type = asmData.vars[name]; + ret = (type ? 'd' : 'i') + num; regTypes[ret] = type; - return ret; } - // find the next free minified name that is not used by a global that shows up in this function - while (1) { - ensureMinifiedNames(nextRegName); - var ret = minifiedNames[nextRegName++]; - if (!usedGlobals[ret]) { - regTypes[ret] = type; - return ret; - } + if (ret in allVars) { + assert(ret in localVars, 'register shadows non-local name'); } + return ret; } // Find the # of uses of each variable. // While doing so, check if all a variable's uses are dominated in a simple @@ -1997,7 +1996,7 @@ function registerize(ast) { // we just use a fresh register to make sure we avoid this, but it could be // optimized to check for safe registers (free, and not used in this loop level). var varRegs = {}; // maps variables to the register they will use all their life - var freeRegsClasses = asm ? [[], [], []] : []; // two classes for asm, one otherwise XXX - hardcoded length + var freeRegsClasses = asm ? [[], [], [], []] : []; // two classes for asm, one otherwise XXX - hardcoded length var nextReg = 1; var fullNames = {}; var loopRegs = {}; // for each loop nesting level, the list of bound variables @@ -2099,6 +2098,7 @@ function registerize(ast) { params: {}, vars: {}, inlines: asmData.inlines, + ret: asmData.ret, }; for (var i = 1; i < nextReg; i++) { var reg = fullNames[i]; @@ -2111,37 +2111,1067 @@ function registerize(ast) { } } denormalizeAsm(fun, finalAsmData); - if (extraInfo && extraInfo.globals) { - // minify in asm var definitions, that denormalizeAsm just generated - function minify(value) { - if (value && value[0] === 'call' && value[1][0] === 'name') { - var name = value[1][1]; - var minified = extraInfo.globals[name]; - if (minified) { - value[1][1] = minified; + } + }); +} + + +// Assign variables to 'registers', coalescing them onto a smaller number of shared +// variables. +// +// This does the same job as 'registerize' above, but burns a lot more cycles trying +// to reduce the total number of register variables. Key points about the operation: +// +// * we decompose the AST into a flow graph and perform a full liveness +// analysis, to determine which variables are live at each point. +// +// * variables that are live concurrently are assigned to different registers. +// +// * variables that are linked via 'x=y' style statements are assigned the same +// register if possible, so that the redundant assignment can be removed. +// (e.g. assignments used to pass state around through loops). +// +// * any code that cannot be reached through the flow-graph is removed. +// (e.g. redundant break statements like 'break L123; break;'). +// +// * any assignments that we can prove are not subsequently used are removed. +// (e.g. unnecessary assignments to the 'label' variable). +// +function registerizeHarder(ast) { + assert(asm); + + traverseGeneratedFunctions(ast, function(fun) { + + var asmData = normalizeAsm(fun); + + var localVars = asmData.vars; + for (var name in asmData.params) { + localVars[name] = asmData.params[name]; + } + + // Utilities for allocating register variables. + // We need distinct register pools for each type of variable. + + var allRegsByType = [{}, {}, {}, {}]; + var regPrefixByType = ['i', 'd', 'f', 'n']; + var nextReg = 1; + + function createReg(forName) { + // Create a new register of type suitable for the given variable name. + var allRegs = allRegsByType[localVars[forName]]; + reg = nextReg++; + allRegs[reg] = regPrefixByType[localVars[forName]] + reg; + return reg; + } + + // Traverse the tree in execution order and synthesize a basic flow-graph. + // It's convenient to build a kind of "dual" graph where the nodes identify + // the junctions between blocks at which control-flow may branch, and each + // basic block is an edge connecting two such junctions. + // For each junction we store: + // * set of blocks that originate at the junction + // * set of blocks that terminate at the junction + // For each block we store: + // * a single entry junction + // * a single exit junction + // * a 'use' and 'kill' set of names for the block + // * full sequence of 'name' and 'assign' nodes in the block + // * whether each such node appears as part of a larger expression + // (and therefore cannot be safely eliminated) + // * set of labels that can be used to jump to this block + + var junctions = []; + var blocks = []; + var currEntryJunction = null; + var nextBasicBlock = null; + var isInExpr = 0; + var activeLabels = [{}]; + var nextLoopLabel = null; + + var ENTRY_JUNCTION = 0; + var EXIT_JUNCTION = 1; + var ENTRY_BLOCK = 0; + + function addJunction() { + // Create a new junction, without inserting it into the graph. + // This is useful for e.g. pre-allocating an exit node. + var id = junctions.length; + junctions[id] = {id: id, inblocks: {}, outblocks: {}}; + return id; + } + + function markJunction(id) { + // Mark current traversal location as a junction. + // This makes a new basic block exiting at this position. + if (id === undefined || id === null) { + id = addJunction(); + } + joinJunction(id, true); + return id; + } + + function setJunction(id, force) { + // Set the next entry junction to the given id. + // This can be used to enter at a previously-declared point. + // You can't return to a junction with no incoming blocks + // unless the 'force' parameter is specified. + assert(nextBasicBlock.nodes.length === 0, 'refusing to abandon an in-progress basic block') + if (force || setSize(junctions[id].inblocks) > 0) { + currEntryJunction = id; + } else { + currEntryJunction = null; + } + } + + function joinJunction(id, force) { + // Complete the pending basic block by exiting at this position. + // This can be used to exit at a previously-declared point. + if (currEntryJunction !== null) { + nextBasicBlock.id = blocks.length; + nextBasicBlock.entry = currEntryJunction; + nextBasicBlock.exit = id; + junctions[currEntryJunction].outblocks[nextBasicBlock.id] = 1; + junctions[id].inblocks[nextBasicBlock.id] = 1; + blocks.push(nextBasicBlock); + } + nextBasicBlock = { id: null, entry: null, exit: null, labels: {}, nodes: [], isexpr: [], use: {}, kill: {} }; + setJunction(id, force); + return id; + } + + function pushActiveLabels(onContinue, onBreak) { + // Push the target junctions for continuing/breaking a loop. + // This should be called before traversing into a loop. + var newLabels = copy(activeLabels[activeLabels.length-1]); + newLabels[null] = [onContinue, onBreak]; + if (nextLoopLabel) { + newLabels[nextLoopLabel] = [onContinue, onBreak]; + nextLoopLabel = null; + } + activeLabels.push(newLabels); + } + + function popActiveLabels() { + // Pop the target junctions for continuing/breaking a loop. + // This should be called after traversing into a loop. + activeLabels.pop(); + } + + function markNonLocalJump(type, label) { + // Complete a block via 'return', 'break' or 'continue'. + // This joins the targetted junction and then sets the current junction to null. + // Any code traversed before we get back an existing junction is dead code. + if (type === 'return') { + joinJunction(EXIT_JUNCTION); + } else { + label = label ? label : null; + var targets = activeLabels[activeLabels.length-1][label]; + assert(targets, 'jump to unknown label'); + if (type === 'continue') { + joinJunction(targets[0]); + } else if (type === 'break') { + joinJunction(targets[1]); + } else { + assert(false, 'unknown jump node type'); + } + } + currEntryJunction = null; + } + + function addUseNode(node) { + // Mark a use of the given name node in the current basic block. + assert(node[0] === 'name', 'not a use node'); + var name = node[1]; + if (name in localVars) { + nextBasicBlock.nodes.push(node); + nextBasicBlock.isexpr.push(isInExpr); + if (!nextBasicBlock.kill[name]) { + nextBasicBlock.use[name] = 1; + } + } + } + + function addKillNode(node) { + // Mark an assignment to the given name node in the current basic block. + assert(node[0] === 'assign', 'not a kill node'); + assert(node[1] === true, 'not a kill node'); + assert(node[2][0] === 'name', 'not a kill node'); + var name = node[2][1]; + if (name in localVars) { + nextBasicBlock.nodes.push(node); + nextBasicBlock.isexpr.push(isInExpr); + nextBasicBlock.kill[name] = 1; + } + } + + function lookThroughCasts(node) { + // Look through value-preserving casts, like "x | 0" => "x" + if (node[0] === 'binary' && node[1] === '|') { + if (node[3][0] === 'num' && node[3][1] === 0) { + return lookThroughCasts(node[2]); + } + } + return node; + } + + function addBlockLabel(node) { + assert(nextBasicBlock.nodes.length === 0, 'cant add label to an in-progress basic block') + if (node[0] === 'num') { + nextBasicBlock.labels[node[1]] = 1; + } + } + + function isTrueNode(node) { + // Check if the given node is statically truthy. + return (node[0] === 'num' && node[1] != 0); + } + + function isFalseNode(node) { + // Check if the given node is statically falsy. + return (node[0] === 'num' && node[1] == 0); + } + + function morphNode(node, newNode) { + // In-place morph a node into some other type of node. + var i = 0; + while (i < node.length && i < newNode.length) { + node[i] = newNode[i]; + i++; + } + while (i < newNode.length) { + node.push(newNode[i]); + i++; + } + if (node.length > newNode.length) { + node.length = newNode.length; + } + } + + function buildFlowGraph(node) { + // Recursive function to build up the flow-graph. + // It walks the tree in execution order, calling the above state-management + // functions at appropriate points in the traversal. + var type = node[0]; + + // Any code traversed without an active entry junction must be dead, + // as the resulting block could never be entered. Let's remove it. + if (currEntryJunction === null && junctions.length > 0) { + morphNode(node, ['block', []]); + return; + } + + // Traverse each node type according to its particular control-flow semantics. + switch (type) { + case 'defun': + var jEntry = markJunction(); + assert(jEntry === ENTRY_JUNCTION); + var jExit = addJunction(); + assert(jExit === EXIT_JUNCTION); + for (var i = 0; i < node[3].length; i++) { + buildFlowGraph(node[3][i]); + } + joinJunction(jExit); + break; + case 'if': + isInExpr++; + buildFlowGraph(node[1]); + isInExpr--; + var jEnter = markJunction(); + var jExit = addJunction(); + if (node[2]) { + // Detect and mark "if (label == N) { <labelled block> }". + if (node[1][0] === 'binary' && node[1][1] === '==') { + var lhs = lookThroughCasts(node[1][2]); + if (lhs[0] === 'name' && lhs[1] === 'label') { + addBlockLabel(lookThroughCasts(node[1][3])); + } + } + buildFlowGraph(node[2]); + } + joinJunction(jExit); + setJunction(jEnter); + if (node[3]) { + buildFlowGraph(node[3]); + } + joinJunction(jExit); + break; + case 'conditional': + isInExpr++; + buildFlowGraph(node[1]); + var jEnter = markJunction(); + var jExit = addJunction(); + if (node[2]) { + buildFlowGraph(node[2]); + } + joinJunction(jExit); + setJunction(jEnter); + if (node[3]) { + buildFlowGraph(node[3]); + } + joinJunction(jExit); + isInExpr--; + break; + case 'while': + // Special-case "while (1) {}" to use fewer junctions, + // since emscripten generates a lot of these. + if (isTrueNode(node[1])) { + var jLoop = markJunction(); + var jExit = addJunction(); + pushActiveLabels(jLoop, jExit); + buildFlowGraph(node[2]); + popActiveLabels(); + joinJunction(jLoop); + setJunction(jExit); + } else { + var jCond = markJunction(); + var jLoop = addJunction(); + var jExit = addJunction(); + isInExpr++; + buildFlowGraph(node[1]); + isInExpr--; + joinJunction(jLoop); + pushActiveLabels(jCond, jExit); + buildFlowGraph(node[2]); + popActiveLabels(); + joinJunction(jCond); + // An empty basic-block linking condition exit to loop exit. + setJunction(jLoop); + joinJunction(jExit); + } + break; + case 'do': + // Special-case "do {} while (1)" and "do {} while (0)" to use + // fewer junctions, since emscripten generates a lot of these. + if (isFalseNode(node[1])) { + var jExit = addJunction(); + pushActiveLabels(jExit, jExit); + buildFlowGraph(node[2]); + popActiveLabels(); + joinJunction(jExit); + } else if (isTrueNode(node[1])) { + var jLoop = markJunction(); + var jExit = addJunction(); + pushActiveLabels(jLoop, jExit); + buildFlowGraph(node[2]); + popActiveLabels(); + joinJunction(jLoop); + setJunction(jExit); + } else { + var jLoop = markJunction(); + var jCond = addJunction(); + var jCondExit = addJunction(); + var jExit = addJunction(); + pushActiveLabels(jCond, jExit); + buildFlowGraph(node[2]); + popActiveLabels(); + joinJunction(jCond); + isInExpr++; + buildFlowGraph(node[1]); + isInExpr--; + joinJunction(jCondExit); + joinJunction(jLoop); + setJunction(jCondExit); + joinJunction(jExit) + } + break; + case 'for': + var jTest = addJunction(); + var jBody = addJunction(); + var jStep = addJunction(); + var jExit = addJunction(); + buildFlowGraph(node[1]); + joinJunction(jTest); + isInExpr++; + buildFlowGraph(node[2]); + isInExpr--; + joinJunction(jBody); + pushActiveLabels(jStep, jExit); + buildFlowGraph(node[4]); + popActiveLabels(); + joinJunction(jStep); + buildFlowGraph(node[3]); + joinJunction(jTest); + setJunction(jBody); + joinJunction(jExit); + break; + case 'label': + assert(node[2][0] in BREAK_CAPTURERS, 'label on non-loop, non-switch statement') + nextLoopLabel = node[1]; + buildFlowGraph(node[2]); + break; + case 'switch': + // Emscripten generates switch statements of a very limited + // form: all case clauses are numeric literals, and all + // case bodies end with a (maybe implicit) break. So it's + // basically equivalent to a multi-way 'if' statement. + isInExpr++; + buildFlowGraph(node[1]); + isInExpr--; + var condition = lookThroughCasts(node[1]); + var jCheckExit = markJunction(); + var jExit = addJunction(); + pushActiveLabels(null, jExit); + var hasDefault = false; + for (var i=0; i<node[2].length; i++) { + setJunction(jCheckExit); + // All case clauses are either 'default' or a numeric literal. + if (!node[2][i][0]) { + hasDefault = true; + } else { + // Detect switches dispatching to labelled blocks. + if (condition[0] === 'name' && condition[1] === 'label') { + addBlockLabel(lookThroughCasts(node[2][i][0])); + } + } + for (var j = 0; j < node[2][i][1].length; j++) { + buildFlowGraph(node[2][i][1][j]); + } + // Control flow will never actually reach the end of the case body. + // If there's live code here, assume it jumps to case exit. + if (currEntryJunction !== null && nextBasicBlock.nodes.length > 0) { + if (node[2][i][0]) { + markNonLocalJump('return'); + } else { + joinJunction(jExit); + } + } + } + // If there was no default case, we also need an empty block + // linking straight from the test evaluation to the exit. + if (!hasDefault) { + setJunction(jCheckExit); + } + joinJunction(jExit); + popActiveLabels() + break; + case 'return': + if (node[1]) { + isInExpr++; + buildFlowGraph(node[1]); + isInExpr--; + } + markNonLocalJump(type); + break; + case 'break': + case 'continue': + markNonLocalJump(type, node[1]); + break; + case 'assign': + isInExpr++; + buildFlowGraph(node[3]); + isInExpr--; + if (node[1] === true && node[2][0] === 'name') { + addKillNode(node); + } else { + buildFlowGraph(node[2]); + } + break; + case 'name': + addUseNode(node); + break; + case 'block': + case 'toplevel': + if (node[1]) { + for (var i = 0; i < node[1].length; i++) { + buildFlowGraph(node[1][i]); + } + } + break; + case 'stat': + buildFlowGraph(node[1]); + break; + case 'unary-prefix': + case 'unary-postfix': + isInExpr++; + buildFlowGraph(node[2]); + isInExpr--; + break; + case 'binary': + isInExpr++; + buildFlowGraph(node[2]); + buildFlowGraph(node[3]); + isInExpr--; + break; + case 'call': + isInExpr++; + buildFlowGraph(node[1]); + if (node[2]) { + for (var i = 0; i < node[2].length; i++) { + buildFlowGraph(node[2][i]); + } + } + isInExpr--; + // If the call is statically known to throw, + // treat it as a jump to function exit. + if (!isInExpr && node[1][0] === 'name') { + if (node[1][1] in FUNCTIONS_THAT_ALWAYS_THROW) { + markNonLocalJump('return'); } } + break; + case 'seq': + case 'sub': + isInExpr++; + buildFlowGraph(node[1]); + buildFlowGraph(node[2]); + isInExpr--; + break; + case 'dot': + case 'throw': + isInExpr++; + buildFlowGraph(node[1]); + isInExpr--; + break; + case 'num': + case 'string': + case 'var': + break; + default: + printErr(JSON.stringify(node)); + assert(false, 'unsupported node type: ' + type); + } + } + buildFlowGraph(fun); + + assert(setSize(junctions[ENTRY_JUNCTION].inblocks) === 0, 'function entry must have no incoming blocks'); + assert(setSize(junctions[EXIT_JUNCTION].outblocks) === 0, 'function exit must have no outgoing blocks'); + assert(blocks[ENTRY_BLOCK].entry === ENTRY_JUNCTION, 'block zero must be the initial block'); + + // Fix up implicit jumps done by assigning to the 'label' variable. + // If a block ends with an assignment to 'label' and there's another block + // with that value of 'label' as precondition, we tweak the flow graph so + // that the former jumps straight to the later. + + var labelledBlocks = {}; + var labelledJumps = []; + FINDLABELLEDBLOCKS: + for (var i = 0; i < blocks.length; i++) { + var block = blocks[i]; + // Does it have any labels as preconditions to its entry? + for (var labelVal in block.labels) { + // 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 (labelVal in labelledBlocks) { + labelledBlocks = {}; + labelledJumps = []; + break FINDLABELLEDBLOCKS; } - var stats = fun[3]; - for (var i = 0; i < stats.length; i++) { - var line = stats[i]; - if (i >= fun[2].length && line[0] !== 'var') break; // when we pass the arg and var coercions, break - if (line[0] === 'stat') { - assert(line[1][0] === 'assign'); - minify(line[1][3]); + labelledBlocks[labelVal] = block; + } + // Does it assign a specific label value at exit? + if ('label' in block.kill) { + var finalNode = block.nodes[block.nodes.length - 1]; + if (finalNode[0] === 'assign' && finalNode[2][1] === 'label') { + // If labels are computed dynamically then all bets are off. + // This can happen due to indirect branching in llvm output. + if (finalNode[3][0] !== 'num') { + labelledBlocks = {}; + labelledJumps = []; + break FINDLABELLEDBLOCKS; + } + labelledJumps.push([finalNode[3][1], block]); + } else { + // If label is assigned a non-zero value elsewhere in the block + // then all bets are off. This can happen e.g. due to outlining + // saving/restoring label to the stack. + for (var j = 0; j < block.nodes.length - 1; j++) { + if (block.nodes[j][0] === 'assign' && block.nodes[j][2][1] === 'label') { + if (block.nodes[j][3][0] !== 'num' && block.nodes[j][3][1] !== 0) { + labelledBlocks = {}; + labelledJumps = []; + break FINDLABELLEDBLOCKS; + } + } + } + } + } + } + for (var labelVal in labelledBlocks) { + var block = labelledBlocks[labelVal]; + // Disconnect it from the graph, and create a + // new junction for jumps targetting this label. + delete junctions[block.entry].outblocks[block.id]; + block.entry = addJunction(); + junctions[block.entry].outblocks[block.id] = 1; + // Add a fake use of 'label' to keep it alive in predecessor. + block.use['label'] = 1; + block.nodes.unshift(['name', 'label']); + block.isexpr.unshift(1); + } + for (var i = 0; i < labelledJumps.length; i++) { + var labelVal = labelledJumps[i][0]; + var block = labelledJumps[i][1]; + var targetBlock = labelledBlocks[labelVal]; + if (targetBlock) { + // Redirect its exit to entry of the target block. + delete junctions[block.exit].inblocks[block.id]; + block.exit = targetBlock.entry; + junctions[block.exit].inblocks[block.id] = 1; + } + } + labelledBlocks = null; + labelledJumps = null; + + // Do a backwards data-flow analysis to determine the set of live + // variables at each junction, and to use this information to eliminate + // any unused assignments. + // We run two nested phases. The inner phase builds the live set for each + // junction. The outer phase uses this to try to eliminate redundant + // stores in each basic block, which might in turn affect liveness info. + + function analyzeJunction(junc) { + // Update the live set for this jun |