diff options
Diffstat (limited to 'tools/js-optimizer.js')
| -rw-r--r-- | tools/js-optimizer.js | 467 |
1 files changed, 344 insertions, 123 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 71a59921..a7f1e4e1 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) { @@ -793,6 +793,7 @@ function simplifyExpressionsPre(ast) { joinAdditions(func); // simplifyZeroComp(func); TODO: investigate performance if (asm) asmOpts(func); + simplifyNotComps(func); }); } @@ -1158,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! @@ -1540,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) { @@ -1658,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 = []; @@ -1673,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.) @@ -2981,32 +3007,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(1.5*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; @@ -3014,27 +3045,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) { @@ -3052,14 +3088,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) { @@ -3076,76 +3113,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']]]]); + }); + reps.push(['stat', ['assign', true, ['name', 'sp'], makeAsmCoercion(['call', ['name', newIdent], [['name', 'sp']]], ASM_INT)]]); 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) { @@ -3156,70 +3223,167 @@ 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]]]); } } + // add final return of sp. the model is that we send sp as the single param, and get it back out + code.push(['stat', ['return', makeAsmCoercion(['name', 'sp'], ASM_INT)]]); + // 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); + if (v != 'sp') 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 minIndex = stats == getStatements(func) ? getFirstIndexInNormalized(func, asmData) : 0; + var canRestart = false; + while (1) { + i--; + 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]; + if (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 >= 0); + } + assert(i >= 0); + 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) { @@ -3229,14 +3393,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) && i < end && stats[i][0] !== 'end-outline-call') { sizeSeen -= measureSize(stats[end]); if (sizeSeen >= sizeToOutline) { end--; @@ -3247,8 +3417,11 @@ function outline(ast) { } if (sizeSeen >= sizeToOutline && sizeSeen <= maxSize) { ret.push.apply(ret, doOutline(func, asmData, stats, i, end)); // outline [i, .. ,end] inclusive + printErr('performed outline on ' + func[1] + ' of ' + sizeSeen + ', func is now size ' + measureSize(func)); sizeSeen = 0; end = i-1; + canRestart = true; + continue; } } level--; @@ -3274,29 +3447,78 @@ 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); 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++) { + var subNode = stats[i]; + if (subNode[0] === 'stat') subNode = subNode[1]; + if (subNode[0] == 'return') { + stats.splice(i, 0, makePop()); + i++; + } + } + }); + // pop the stack at the end if there is not a return + var last = stats[stats.length-1]; + if (last[0] === 'stat') last = last[1]; + if (last[0] !== 'return') { + stats.push(makePop()); + } + } + } + printErr('... resulting size of ' + func[1] + ' is ' + measureSize(func)); } denormalizeAsm(func, asmData); }); + funcs = null; + // TODO: control flow: route returns and breaks. outlined code should have all breaks/continues/returns break into the outermost scope, // after setting a state variable, etc. if (newFuncs.length > 0) { - // We have outlined. Add stack support: header in which we allocate enough stack space TODO - // If sp was not present before, add it and before each return, pop the stack. also a final pop if not ending with a return TODO - // (none of this should be done in inner functions, of course, just the original) - // add new functions to the toplevel, or create a toplevel if there isn't one ast[1].push.apply(ast[1], newFuncs); - funcs = newFuncs; - more = true; + // TODO: check if in some cases we do need to outline new functions + //funcs = newFuncs.filter(function(newFunc) { + // // recursively outline if we have a large new function that did not come at a high cost + // return measureSize(newFunc) > sizeToOutline && costs[newFunc[1]] < 0.1*sizeToOutline; + //}); + //more = funcs.length > 0; } } + + // clear out markers + traverse(ast, function(node, type) { + if (type === 'begin-outline-call' || type === 'end-outline-call') return emptyNode(); + }); } // Last pass utilities @@ -3378,10 +3600,9 @@ var passes = { unGlobalize: unGlobalize, removeAssignsToUndefined: removeAssignsToUndefined, //removeUnneededLabelSettings: removeUnneededLabelSettings, - simplifyExpressionsPre: simplifyExpressionsPre, + simplifyExpressions: simplifyExpressions, optimizeShiftsConservative: optimizeShiftsConservative, optimizeShiftsAggressive: optimizeShiftsAggressive, - simplifyExpressionsPost: simplifyExpressionsPost, hoistMultiples: hoistMultiples, loopOptimizer: loopOptimizer, registerize: registerize, |