diff options
Diffstat (limited to 'tools/js-optimizer.js')
| -rw-r--r-- | tools/js-optimizer.js | 604 |
1 files changed, 474 insertions, 130 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 6987511c..29b36cad 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -410,7 +410,7 @@ function removeUnneededLabelSettings(ast) { var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^'); var COMPARE_OPS = set('<', '<=', '>', '>=', '==', '===', '!=', '!=='); -function simplifyExpressionsPre(ast) { +function simplifyExpressions(ast) { // Simplify common expressions used to perform integer conversion operations // in cases where no conversion is needed. function simplifyIntegerConversions(ast) { @@ -562,7 +562,8 @@ function simplifyExpressionsPre(ast) { } else if (type === 'binary' && node[1] === '^') { // LLVM represents bitwise not as xor with -1. Translate it back to an actual bitwise not. if (node[3][0] === 'unary-prefix' && node[3][1] === '-' && node[3][2][0] === 'num' && - node[3][2][1] === 1) { + node[3][2][1] === 1 && + !(node[2][0] == 'unary-prefix' && node[2][1] == '~')) { // avoid creating ~~~ which is confusing for asm given the role of ~~ return ['unary-prefix', '~', node[2]]; } } else if (type === 'binary' && node[1] === '>>' && node[3][0] === 'num' && @@ -636,7 +637,8 @@ function simplifyExpressionsPre(ast) { if (node[0] === 'seq' && node[1][0] === 'assign' && node[1][2][0] === 'sub' && node[1][2][1][0] === 'name' && (node[1][2][1][1] === 'HEAP32' || node[1][2][1][1] === 'HEAPF32') && node[1][2][2][0] === 'binary' && node[1][2][2][2][0] === 'name' && node[1][2][2][2][1] === 'tempDoublePtr' && - node[1][3][0] === 'sub' && node[1][3][1][0] === 'name' && (node[1][3][1][1] === 'HEAP32' || node[1][3][1][1] === 'HEAPF32')) { + node[1][3][0] === 'sub' && node[1][3][1][0] === 'name' && (node[1][3][1][1] === 'HEAP32' || node[1][3][1][1] === 'HEAPF32') && + node[2][0] !== 'seq') { // avoid (x, y, z) which can be used for tempDoublePtr on doubles for alignment fixes if (node[1][2][1][1] === 'HEAP32') { node[1][3][1][1] = 'HEAPF32'; return ['unary-prefix', '+', node[1][3]]; @@ -791,6 +793,7 @@ function simplifyExpressionsPre(ast) { joinAdditions(func); // simplifyZeroComp(func); TODO: investigate performance if (asm) asmOpts(func); + simplifyNotComps(func); }); } @@ -1156,10 +1159,6 @@ function simplifyNotComps(ast) { simplifyNotCompsPass = false; } -function simplifyExpressionsPost(ast) { - simplifyNotComps(ast); -} - var NO_SIDE_EFFECTS = set('num', 'name'); function hasSideEffects(node) { // this is 99% incomplete! @@ -1538,24 +1537,22 @@ function detectAsmCoercion(node, asmInfo) { // for params, +x vs x|0, for vars, 0.0 vs 0 if (node[0] === 'num' && node[1].toString().indexOf('.') >= 0) return ASM_DOUBLE; if (node[0] === 'unary-prefix') return ASM_DOUBLE; - if (asmInfo && node[0] == 'name') { - if (node[1] in asmInfo.vars) return asmInfo.vars[node[1]]; - if (node[1] in asmInfo.params) return asmInfo.params[node[1]]; - } + if (asmInfo && node[0] == 'name') return getAsmType(node[1], asmInfo); return ASM_INT; } -function makeAsmParamCoercion(param, type) { - return type === ASM_INT ? ['binary', '|', ['name', param], ['num', 0]] : ['unary-prefix', '+', ['name', param]]; +function makeAsmCoercion(node, type) { + return type === ASM_INT ? ['binary', '|', node, ['num', 0]] : ['unary-prefix', '+', node]; } function makeAsmVarDef(v, type) { return [v, type === ASM_INT ? ['num', 0] : ['unary-prefix', '+', ['num', 0]]]; } -function getAsmType(asmInfo, name) { +function getAsmType(name, asmInfo) { if (name in asmInfo.vars) return asmInfo.vars[name]; - return asmInfo.params[name]; + if (name in asmInfo.params) return asmInfo.params[name]; + assert(false, 'unknown var ' + name); } function normalizeAsm(func) { @@ -1656,7 +1653,7 @@ function denormalizeAsm(func, data) { // add param coercions var next = 0; func[2].forEach(function(param) { - stats[next++] = ['stat', ['assign', true, ['name', param], makeAsmParamCoercion(param, data.params[param])]]; + stats[next++] = ['stat', ['assign', true, ['name', param], makeAsmCoercion(['name', param], data.params[param])]]; }); // add variable definitions var varDefs = []; @@ -1671,6 +1668,37 @@ function denormalizeAsm(func, data) { //printErr('denormalized \n\n' + astToSrc(func) + '\n\n'); } +function getFirstIndexInNormalized(func, data) { + // In a normalized asm function, return the index of the first element that is not not defs or annotation + var stats = func[3]; + var i = stats.length-1; + while (i >= 0) { + var stat = stats[i]; + if (stat[0] == 'var') break; + i--; + } + return i+1; +} + +function getStackBumpNode(ast) { + var found = null; + traverse(ast, function(node, type) { + if (type === 'assign' && node[2][0] === 'name' && node[2][1] === 'STACKTOP') { + var value = node[3]; + if (value[0] === 'name') return true; + assert(value[0] == 'binary' && value[1] == '|' && value[2][0] == 'binary' && value[2][1] == '+' && value[2][2][0] == 'name' && value[2][2][1] == 'STACKTOP' && value[2][3][0] == 'num'); + found = node; + return true; + } + }); + return found; +} + +function getStackBumpSize(ast) { + var node = getStackBumpNode(ast); + return node ? node[3][2][3][1] : 0; +} + // 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.) @@ -1715,7 +1743,7 @@ function registerize(ast) { } }); vacuum(fun); - if (extraInfo) { + if (extraInfo && extraInfo.globals) { assert(asm); var usedGlobals = {}; var nextLocal = 0; @@ -1756,16 +1784,17 @@ function registerize(ast) { } } }); - assert(fun[1] in extraInfo.globals, fun[1]); - fun[1] = extraInfo.globals[fun[1]]; - assert(fun[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) { + if (!extraInfo || !extraInfo.globals) { var ret = (type ? 'd' : 'i') + num; regTypes[ret] = type; return ret; @@ -2844,6 +2873,7 @@ function outline(ast) { defs[name] = node; } else { if (name in asmData.params) { + assignments[name] = (assignments[name] || 1) + 1; // init to 1 for initial parameter assignment considered[name] = true; // this parameter is not ssa, it must be in a hand-optimized function, so it is not trivial } } @@ -2969,6 +2999,95 @@ function outline(ast) { }); } + // Try to flatten out code as much as possible, to make outlining more feasible. + function flatten(func, asmData) { + var minSize = sizeToOutline; + var helperId = 0; + function getHelper() { + while (1) { + var ret = 'helper$' + (helperId++); + if (!(ret in asmData.vars) && !(ret in asmData.params)) { + asmData.vars[ret] = ASM_INT; + return ret; + } + } + } + var ignore = []; + traverse(func, function(node) { + var stats = getStatements(node); + if (stats) { + for (var i = 0; i < stats.length; i++) { + var node = stats[i]; // step over param + if (ignore.indexOf(node) >= 0) continue; + if (node[0] == 'stat') node = node[1]; + if (ignore.indexOf(node) >= 0) continue; + var type = node[0]; + if (measureSize(node) >= minSize) { + if (type === 'if' && node[3]) { + var reps = []; + var helper = getHelper(); + // clear helper + reps.push(['stat', ['assign', true, ['name', helper], ['num', 1]]]); // 1 means continue in ifs + // gather parts + var parts = []; + var curr = node; + while (1) { + parts.push({ condition: curr[1], body: curr[2] }); + curr = curr[3]; + if (!curr) break; + if (curr[0] != 'if') { + parts.push({ condition: null, body: curr }); + break; + } + } + // chunkify. Each chunk is a chain of if-elses, with the new overhead just on entry and exit + var chunks = []; + var currSize = 0; + var currChunk = []; + parts.forEach(function(part) { + var size = (part.condition ? measureSize(part.condition) : 0) + measureSize(part.body) + 5; // add constant for overhead of extra code + assert(size > 0); + if (size + currSize >= minSize && currSize) { + chunks.push(currChunk); + currChunk = []; + currSize = 0; + } + currChunk.push(part); + currSize += size; + }); + assert(currSize); + chunks.push(currChunk); + // generate flattened code + chunks.forEach(function(chunk) { + var pre = ['stat', ['assign', true, ['name', helper], ['num', 0]]]; + var chain = null, tail = null; + chunk.forEach(function(part) { + // add to chain + var contents = makeIf(part.condition || ['num', 1], part.body[1]); + if (chain) { + tail[3] = contents; + } else { + chain = contents; + ignore.push(contents); + } + tail = contents; + }); + // if none of the ifs were entered, in the final else note that we need to continue + tail[3] = ['block', [['stat', ['assign', true, ['name', helper], ['num', 1]]]]]; + reps.push(makeIf(['name', helper], [pre, chain])); + }); + // replace code and update i + stats.splice.apply(stats, [i, 1].concat(reps)); + i--; // negate loop increment + i += reps.length; + continue; + } + } + } + } + }); + } + // Prepares information for spilling of local variables function analyzeFunction(func, asmData) { var stack = []; // list of variables, each gets 8 bytes @@ -2979,32 +3098,37 @@ function outline(ast) { stack.push(name); } asmData.stackPos = {}; + var stackSize = getStackBumpSize(func); + if (stackSize % 8 === 0) stackSize += 8 - (stackSize % 8); for (var i = 0; i < stack.length; i++) { - asmData.stackPos[stack[i]] = i*8; - } - // Reserve an extra two spots: one for control flow var, the other for control flow data - asmData.stackSize = (stack.length + 2)*8; - asmData.controlStackPos = asmData.stackSize - 16; - asmData.controlDataStackPos = asmData.stackSize - 8; + asmData.stackPos[stack[i]] = stackSize + i*8; + } + // Reserve an extra two spots per possible outlining: one for control flow var, the other for control flow data + // The control variables are zeroed out when calling an outlined function, and after using + // the value after they return. + asmData.maxOutlinings = Math.round(3*measureSize(func)/sizeToOutline); + asmData.totalStackSize = stackSize + (stack.length + 2*asmData.maxOutlinings)*8; + asmData.controlStackPos = function(i) { return stackSize + (stack.length + i)*8 }; + asmData.controlDataStackPos = function(i) { return stackSize + (stack.length + i)*8 + 4 }; asmData.splitCounter = 0; } // Analyze uses - reads and writes - of variables in part of the AST of a function function analyzeCode(func, asmData, ast) { - var labels = {}; + var labels = {}; // labels defined in this code var labelCounter = 1; // 0 means no label traverse(ast, function(node, type) { - if ((type == 'label' || type in LOOP_FLOW) && node[1] && !(node[1] in labels)) { + if (type == 'label' && !(node[1] in labels)) { labels[node[1]] = labelCounter++; } }); var writes = {}; - var appearances = {}; - var hasReturn = false, hasBreak = false, hasContinue = false; + var namings = {}; + var hasReturn = false, hasReturnInt = false, hasReturnDouble = false, hasBreak = false, hasContinue = false; var breaks = {}; // set of labels we break or continue - var continues = {}; // to. '0' is an unlabeled one + var continues = {}; // to (name -> id, just like labels) var breakCapturers = 0; var continueCapturers = 0; @@ -3012,27 +3136,32 @@ function outline(ast) { if (type == 'assign' && node[2][0] == 'name') { var name = node[2][1]; if (name in asmData.vars || name in asmData.params) { - writes[name] = 0; - appearances[name] = (appearances[name] || 0) - 1; // this appearance is a definition, offset the counting later + writes[name] = (writes[name] || 0) + 1; } } else if (type == 'name') { var name = node[1]; if (name in asmData.vars || name in asmData.params) { - appearances[name] = (appearances[name] || 0) + 1; + namings[name] = (namings[name] || 0) + 1; } } else if (type == 'return') { - hasReturn = true; + if (!node[1]) { + hasReturn = true; + } else if (detectAsmCoercion(node[1]) == ASM_INT) { + hasReturnInt = true; + } else { + hasReturnDouble = true; + } } else if (type == 'break') { var label = node[1] || 0; if (!label && breakCapturers > 0) return; // no label, and captured if (label && (label in labels)) return; // label, and defined in this code, so captured - breaks[label || 0] = 0; + if (label) breaks[label] = labelCounter++; hasBreak = true; } else if (type == 'continue') { var label = node[1] || 0; if (!label && continueCapturers > 0) return; // no label, and captured if (label && (label in labels)) return; // label, and defined in this code, so captured - continues[label || 0] = 0; + if (label) continues[label] = labelCounter++; hasContinue = true; } else { if (type in BREAK_CAPTURERS) { @@ -3050,14 +3179,15 @@ function outline(ast) { continueCapturers--; } }); + assert(hasReturn + hasReturnInt + hasReturnDouble <= 1); var reads = {}; - - for (var name in appearances) { - if (appearances[name] > 0) reads[name] = 0; + for (var v in namings) { + var actualReads = namings[v] - (writes[v] || 0); + if (actualReads > 0) reads[v] = actualReads; } - return { writes: writes, reads: reads, hasReturn: hasReturn, breaks: breaks, continues: continues, labels: labels }; + return { writes: writes, reads: reads, hasReturn: hasReturn, hasReturnInt: hasReturnInt, hasReturnDouble: hasReturnDouble, hasBreak: hasBreak, hasContinue: hasContinue, breaks: breaks, continues: continues, labels: labels }; } function makeAssign(dst, src) { @@ -3074,76 +3204,106 @@ function outline(ast) { function makeComparison(left, comp, right) { return ['binary', comp, left, right]; } + function makeSwitch(value, cases) { + return ['switch', value, cases]; + } var CONTROL_BREAK = 1, CONTROL_BREAK_LABEL = 2, CONTROL_CONTINUE = 3, CONTROL_CONTINUE_LABEL = 4, CONTROL_RETURN_VOID = 5, CONTROL_RETURN_INT = 6, CONTROL_RETURN_DOUBLE = 7; var sizeToOutline = extraInfo.sizeToOutline; var level = 0; + var outliningParents = {}; // function name => parent it was outlined from + function doOutline(func, asmData, stats, start, end) { - printErr(' do outline ' + [func[1], level, 'range:', start, end, 'of', stats.length]); + if (asmData.splitCounter === asmData.maxOutlinings) return []; + if (!extraInfo.allowCostlyOutlines) var originalStats = copy(stats); var code = stats.slice(start, end+1); - var newIdent = func[1] + '$' + (asmData.splitCounter++); - // add spills and reads before and after the call to the outlined code, and in the outlined code itself + var funcSize = measureSize(func); + var outlineIndex = asmData.splitCounter++; + var newIdent = func[1] + '$' + outlineIndex; + // analyze variables, and find 'owned' variables - that only appear in the outlined code, and do not need any spill support var codeInfo = analyzeCode(func, asmData, code); + var allCodeInfo = analyzeCode(func, asmData, func); + //printErr(' do outline ' + [func[1], level, 'range:', start, end, 'of', stats.length, newIdent, measureSize(code), JSON.stringify(codeInfo.labels), JSON.stringify(codeInfo.breaks), JSON.stringify(codeInfo.continues)]); + var owned = { sp: 1 }; // sp is always owned, each has its own + keys(setUnion(codeInfo.reads, codeInfo.writes)).forEach(function(v) { + if (allCodeInfo.reads[v] === codeInfo.reads[v] && allCodeInfo.writes[v] === codeInfo.writes[v] && !(v in asmData.params)) { + owned[v] = 1; + } + }); var reps = []; - for (var v in codeInfo.reads) { - if (v != 'sp') { - reps.push(['stat', ['assign', true, ['sub', ['name', getAsmType(asmData, v) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], ['name', v]]]); - code.unshift(['stat', ['assign', true, ['name', v], ['sub', ['name', getAsmType(asmData, v) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]]]]); + // wipe out control variable + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ['num', 0])]); + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos(outlineIndex)), ['num', 0])]); // XXX not really needed + // add spills and reads before and after the call to the outlined code, and in the outlined code itself + keys(setUnion(codeInfo.reads, codeInfo.writes)).forEach(function(v) { + if (!(v in owned)) { + reps.push(['stat', ['assign', true, ['sub', ['name', getAsmType(v, asmData) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], ['name', v]]]); } - } + }); reps.push(['stat', ['call', ['name', newIdent], [['name', 'sp']]]]); for (var v in codeInfo.writes) { - reps.push(['stat', ['assign', true, ['name', v], ['sub', ['name', getAsmType(asmData, v) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]]]]); - code.push(['stat', ['assign', true, ['sub', ['name', getAsmType(asmData, v) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], ['name', v]]]); + if (!(v in owned)) { + reps.push(['stat', ['assign', true, ['name', v], makeAsmCoercion(['sub', ['name', getAsmType(v, asmData) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], getAsmType(v, asmData))]]); + } } // Generate new function - if (codeInfo.hasReturn || codeInfo.hasBreak || codeInfo.hasContinue) { + if (codeInfo.hasReturn || codeInfo.hasReturnInt || codeInfo.hasReturnDouble || codeInfo.hasBreak || codeInfo.hasContinue) { // we need to capture all control flow using a top-level labeled one-time loop in the outlined function - code = [['label', 'OL', ['do', ['num', 0], ['block', code]]]]; var breakCapturers = 0; var continueCapturers = 0; - traverse(code, function(node, type) { + traverse(['block', code], function(node, type) { // traverse on dummy block, so we get the toplevel statements // replace all break/continue/returns with code to break out of the main one-time loop, and set the control data - if (type == 'return') { - var ret = ['break', 'OL']; - if (!node[1]) { - ret = ['seq', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos), ['num', CONTROL_RETURN_VOID]), ret]; - } else { - var type = detectAsmCoercion(node[1], asmData); - ret = ['seq', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos), ['num', type == ASM_INT ? CONTROL_RETURN_INT : CONTROL_RETURN_DOUBLE]), ret]; - ret = ['seq', makeAssign(makeStackAccess(type, asmData.controlDataStackPos), node[1]), ret]; - } - return ret; - } else if (type == 'break') { - var label = node[1] || 0; - if (label == 'OL') return; // this was just added before us, it is new replacement code - if (!label && breakCapturers > 0) return; // no label, and captured - if (label && (label in codeInfo.labels)) return; // label, and defined in this code, so captured - var ret = ['break', 'OL']; - ret = ['seq', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos), ['num', label ? CONTROL_BREAK_LABEL : CONTROL_BREAK]), ret]; - if (label) { - assert(label in codeInfo.labels, label + ' in ' + keys(codeInfo.labels)); - ret = ['seq', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ['num', codeInfo.labels[label]]), ret]; - } - return ret; - } else if (type == 'continue') { - var label = node[1] || 0; - if (!label && continueCapturers > 0) return; // no label, and captured - if (label && (label in codeInfo.labels)) return; // label, and defined in this code, so captured - var ret = ['break', 'OL']; - ret = ['seq', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos), ['num', label ? CONTROL_CONTINUE_LABEL : CONTROL_CONTINUE]), ret]; - if (label) { - ret = ['seq', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ['num', codeInfo.labels[label]]), ret]; - } - return ret; - } else { - if (type in BREAK_CAPTURERS) { - breakCapturers++; - } - if (type in CONTINUE_CAPTURERS) { - continueCapturers++; + if (type in BREAK_CAPTURERS) { + breakCapturers++; + } + if (type in CONTINUE_CAPTURERS) { + continueCapturers++; + } + var stats = node === code ? node : getStatements(node); + if (stats) { + for (var i = 0; i < stats.length; i++) { + var node = stats[i]; // step all over node and type here, for convenience + if (node[0] == 'stat') node = node[1]; + var type = node[0]; + var ret = null; + if (type == 'return') { + ret = []; + if (!node[1]) { + ret.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ['num', CONTROL_RETURN_VOID])]); + } else { + var type = detectAsmCoercion(node[1], asmData); + ret.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ['num', type == ASM_INT ? CONTROL_RETURN_INT : CONTROL_RETURN_DOUBLE])]); + ret.push(['stat', makeAssign(makeStackAccess(type, asmData.controlDataStackPos(outlineIndex)), node[1])]); + } + ret.push(['stat', ['break', 'OL']]); + } else if (type == 'break') { + var label = node[1] || 0; + if (label == 'OL') continue; // this was just added before us, it is new replacement code + if (!label && breakCapturers > 0) continue; // no label, and captured + if (label && (label in codeInfo.labels)) continue; // label, and defined in this code, so captured + ret = [['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ['num', label ? CONTROL_BREAK_LABEL : CONTROL_BREAK])]]; + if (label) { + assert(label in codeInfo.breaks); + ret.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos(outlineIndex)), ['num', codeInfo.breaks[label]])]); + } + ret.push(['stat', ['break', 'OL']]); + } else if (type == 'continue') { + var label = node[1] || 0; + if (!label && continueCapturers > 0) continue; // no label, and captured + if (label && (label in codeInfo.labels)) continue; // label, and defined in this code, so captured + ret = [['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ['num', label ? CONTROL_CONTINUE_LABEL : CONTROL_CONTINUE])]]; + if (label) { + assert(label in codeInfo.continues); + ret.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos(outlineIndex)), ['num', codeInfo.continues[label]])]); + } + ret.push(['stat', ['break', 'OL']]); + } + if (ret) { + stats.splice.apply(stats, [i, 1].concat(ret)); + i += ret.length-1; + } } } }, function(node, type) { @@ -3154,70 +3314,179 @@ function outline(ast) { continueCapturers--; } }); - // read the control data at the callsite to the outlined function + code = [['label', 'OL', ['do', ['num', 0], ['block', code]]]]; // do this after processing, to not confuse breakCapturers etc. + // read the control data at the callsite to the outlined function, and clear the control values + reps.push(['stat', makeAssign( + ['name', 'tempValue'], + makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ASM_INT) + )]); + reps.push(['stat', makeAssign( + ['name', 'tempInt'], + makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlDataStackPos(outlineIndex)), ASM_INT) + )]); + reps.push(['stat', makeAssign( + ['name', 'tempDouble'], + makeAsmCoercion(makeStackAccess(ASM_DOUBLE, asmData.controlDataStackPos(outlineIndex)), ASM_DOUBLE) + )]); + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos(outlineIndex)), ['num', 0])]); + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos(outlineIndex)), ['num', 0])]); // XXX not really needed + // use the control data information if (codeInfo.hasReturn) { reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_RETURN_VOID]), + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_RETURN_VOID]), [['stat', ['return']]] )); + } + if (codeInfo.hasReturnInt) { reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_RETURN_INT]), - [['stat', ['return', makeStackAccess(ASM_INT, asmData.controlDataStackPos)]]] + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_RETURN_INT]), + [['stat', ['return', makeAsmCoercion(['name', 'tempInt'], ASM_INT)]]] )); + } + if (codeInfo.hasReturnDouble) { reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_RETURN_DOUBLE]), - [['stat', ['return', makeStackAccess(ASM_DOUBLE, asmData.controlDataStackPos)]]] + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_RETURN_DOUBLE]), + [['stat', ['return', makeAsmCoercion(['name', 'tempDouble'], ASM_DOUBLE)]]] )); } if (codeInfo.hasBreak) { reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_BREAK]), - ['stat', ['break']] - )); - reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_BREAK_LABEL]), - ['stat', ['break', makeStackAccess(ASM_INT, asmData.controlDataStackPos)]] // XXX here and below, need a switch overall possible labels + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_BREAK]), + [['stat', ['break']]] )); + if (keys(codeInfo.breaks).length > 0) { + reps.push(makeIf( + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_BREAK_LABEL]), + [makeSwitch(makeAsmCoercion(['name', 'tempInt'], ASM_INT), keys(codeInfo.breaks).map(function(key) { + var id = codeInfo.breaks[key]; + return [['num', id], [['block', [['stat', ['break', key]]]]]]; + }))] + )); + } } if (codeInfo.hasContinue) { reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_CONTINUE]), - ['stat', ['break']] - )); - reps.push(makeIf( - makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_CONTINUE_LABEL]), - ['stat', ['continue', makeStackAccess(ASM_INT, asmData.controlDataStackPos)]] // XXX + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_CONTINUE]), + [['stat', ['continue']]] )); + if (keys(codeInfo.continues).length > 0) { + reps.push(makeIf( + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_CONTINUE_LABEL]), + [makeSwitch(makeAsmCoercion(['name', 'tempInt'], ASM_INT), keys(codeInfo.continues).map(function(key) { + var id = codeInfo.continues[key]; + return [['num', id], [['block', [['stat', ['continue', key]]]]]]; + }))] + )); + } } } + // add spills and unspills in outlined code outside the OL loop + keys(setUnion(codeInfo.reads, codeInfo.writes)).forEach(function(v) { + if (!(v in owned)) { + code.unshift(['stat', ['assign', true, ['name', v], makeAsmCoercion(['sub', ['name', getAsmType(v, asmData) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], getAsmType(v, asmData))]]); + } + }); + for (var v in codeInfo.writes) { + if (!(v in owned)) { + code.push(['stat', ['assign', true, ['sub', ['name', getAsmType(v, asmData) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], ['name', v]]]); + } + } + // finalize var newFunc = ['defun', newIdent, ['sp'], code]; var newAsmData = { params: { sp: ASM_INT }, vars: {} }; for (var v in codeInfo.reads) { - newAsmData.vars[v] = getAsmType(asmData, v); + if (v != 'sp') newAsmData.vars[v] = getAsmType(v, asmData); } for (var v in codeInfo.writes) { - newAsmData.vars[v] = getAsmType(asmData, v); + assert(v != 'sp'); // we send sp as a read-only parameter, cannot be written to in outlined code + newAsmData.vars[v] = getAsmType(v, asmData); } denormalizeAsm(newFunc, newAsmData); + // add outline call markers (we cannot do later outlinings that cut through an outlining call) + reps.unshift(['begin-outline-call', newIdent]); + reps.push(['end-outline-call', newIdent]); // replace in stats stats.splice.apply(stats, [start, end-start+1].concat(reps)); + // final evaluation and processing + if (!extraInfo.allowCostlyOutlines && (measureSize(func) >= funcSize || measureSize(newFunc) >= funcSize)) { + // abort, this was pointless + stats.length = originalStats.length; + for (var i = 0; i < stats.length; i++) stats[i] = originalStats[i]; + return []; + } + for (var v in owned) { + if (v != 'sp') delete asmData.vars[v]; // parent does not need these anymore + } + // if we just removed a final return from the original function, add one + var last = getStatements(func)[getStatements(func).length-1]; + if (last[0] === 'stat') last = last[1]; + if (last[0] !== 'return') { + if (allCodeInfo.hasReturnInt || allCodeInfo.hasReturnDouble) { + getStatements(func).push(['stat', ['return', makeAsmCoercion(['num', 0], allCodeInfo.hasReturnInt ? ASM_INT : ASM_DOUBLE)]]); + } + } + outliningParents[newIdent] = func[1]; return [newFunc]; } function outlineStatements(func, asmData, stats, maxSize) { level++; - if (measureSize(stats) < sizeToOutline) return; + //printErr('outlineStatements: ' + [func[1], level, measureSize(func)]); + var lastSize = measureSize(stats); + if (lastSize < sizeToOutline) { level--; return } var ret = []; var sizeSeen = 0; var end = stats.length-1; var i = stats.length; - while (--i >= 0) { + var canRestart = false; + var minIndex = 0; + function calcMinIndex() { + if (stats == getStatements(func)) { + minIndex = getFirstIndexInNormalized(func, asmData); + for (var i = minIndex; i < stats.length; i++) { + var stat = stats[i]; + if (stat[0] == 'stat') stat = stat[1]; + if (stat[0] == 'assign' && stat[2][0] == 'name' && stat[2][1] == 'sp') minIndex = i+1; // cannot outline |sp = | + } + } + } + while (1) { + i--; + calcMinIndex(); + if (i < minIndex) { + // we might be done. but, if we have just outlined, do a further attempt from the beginning. + // (but only if the total costs are not extravagant) + var currSize = measureSize(stats); + var outlinedSize = measureSize(ret); + if (canRestart && currSize > 1.2*sizeToOutline && lastSize - currSize >= 0.75*sizeToOutline) { + //printErr('restarting ' + func[1] + ' since ' + [currSize, outlinedSize, lastSize] + ' in level ' + level); + lastSize = currSize; + i = stats.length; + end = stats.length-1; + sizeSeen = 0; + canRestart = false; + continue; + } else { + break; + } + } + var stat = stats[i]; + while (stat[0] === 'end-outline-call') { + // we cannot outline through an outline call, so include all of it + while (stats[--i][0] !== 'begin-outline-call') { + assert(i >= minIndex+1); + assert(stats[i][0] !== 'end-outline-call'); + } + stat = stats[i]; + } + var size = measureSize(stat); //printErr(level + ' size ' + [i, size]); if (size >= sizeToOutline) { // this by itself is big enough to inline, recurse into it and find statements to split on var subStatements = null; + var pre = ret.length; traverse(stat, function(node, type) { if (type == 'block') { if (measureSize(node) >= sizeToOutline) { @@ -3227,14 +3496,20 @@ function outline(ast) { return null; // do not recurse into children, outlineStatements will do so if necessary } }); - sizeSeen = 0; - continue; + if (ret.length > pre) { + // we outlined recursively, reset our state here + //printErr('successful outline in recursion ' + func[1] + ' due to recursive in level ' + level); + end = i-1; + sizeSeen = 0; + canRestart = true; + continue; + } } sizeSeen += size; - // If this is big enough to outline, but no too big (if very close to the size of the full function, + // If this is big enough to outline, but not too big (if very close to the size of the full function, // outlining is pointless; remove stats from the end to try to achieve the good case), then outline. // Also, try to reduce the size if it is much larger than the hoped-for size - while ((sizeSeen > maxSize || sizeSeen > 2*sizeToOutline) && i < end) { + while ((sizeSeen > maxSize || sizeSeen > 2*sizeToOutline) && end > i+1 && stats[end][0] !== 'begin-outline-call' && stats[end][0] !== 'end-outline-call') { sizeSeen -= measureSize(stats[end]); if (sizeSeen >= sizeToOutline) { end--; @@ -3243,10 +3518,30 @@ function outline(ast) { break; } } + // verify we are not outlining through an outline call + var sum = 0; + stats.slice(i, end+1).forEach(function(stat) { + if (stat[0] == 'begin-outline-call') { + assert(sum == 0); + sum++; + } else if (stat[0] == 'end-outline-call') { + assert(sum == 1); + sum--; + } + }); + assert(sum == 0); + // final decision and action if (sizeSeen >= sizeToOutline && sizeSeen <= maxSize) { - ret.push.apply(ret, doOutline(func, asmData, stats, i, end)); // outline [i, .. ,end] inclusive + assert(i >= minIndex); + var newFuncs = doOutline(func, asmData, stats, i, end); // outline [i, .. ,end] inclusive + if (newFuncs.length) { + ret.push.apply(ret, newFuncs); + printErr('performed outline on ' + func[1] + ' of ' + sizeSeen + ', func is now size ' + measureSize(func) + ' ==> ' + newFuncs[0][1]); + } sizeSeen = 0; end = i-1; + canRestart = true; + continue; } } level--; @@ -3272,29 +3567,79 @@ function outline(ast) { var asmData = normalizeAsm(func); var size = measureSize(func); if (size >= sizeToOutline) { + printErr('trying to reduce the size of ' + func[1] + ' which is ' + size + ' (>= ' + sizeToOutline + ')'); aggressiveVariableElimination(func, asmData); + flatten(func, asmData); analyzeFunction(func, asmData); - var ret = outlineStatements(func, asmData, getStatements(func), 0.5*size); - if (ret && ret.length > 0) newFuncs.push.apply(newFuncs, ret); + var stats = getStatements(func); + var ret = outlineStatements(func, asmData, stats, 0.9*size); + assert(level == 0); + if (ret && ret.length > 0) { + newFuncs.push.apply(newFuncs, ret); + // We have outlined. Add stack support + if ('sp' in asmData.vars) { + // find stack bump (STACKTOP = STACKTOP + X | 0) and add the extra space + var stackBumpNode = getStackBumpNode(stats); + if (stackBumpNode) stackBumpNode[3][2][3][1] = asmData.totalStackSize; + } else if (!('sp' in asmData.params)) { // if sp is a param, then we are an outlined function, no need to add stack support for us + // add sp variable and stack bump + var index = getFirstIndexInNormalized(func, asmData); + stats.splice(index, 0, + ['stat', makeAssign(['name', 'sp'], ['name', 'STACKTOP'])], + ['stat', makeAssign(['name', 'STACKTOP'], ['binary', '|', ['binary', '+', ['name', 'STACKTOP'], ['num', asmData.totalStackSize]], ['num', 0]])] + ); + asmData.vars.sp = ASM_INT; // no need to add to vars, we are about to denormalize anyhow + // we added sp, so we must add stack popping + function makePop() { + return ['stat', makeAssign(['name', 'STACKTOP'], ['name', 'sp'])]; + } + traverse(func, function(node, type) { + var stats = getStatements(node); + if (!stats) return; + for (var i = 0; i < stats.length; i++) { + |