diff options
Diffstat (limited to 'tools/js-optimizer.js')
| -rw-r--r-- | tools/js-optimizer.js | 200 |
1 files changed, 154 insertions, 46 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index dfc4d5dd..46b9c731 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -3012,6 +3012,8 @@ function outline(ast) { asmData.stackPos[stack[i]] = stackSize + i*8; } // Reserve an extra two spots: 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.extraStackSize = (stack.length + 2)*8; asmData.controlStackPos = stackSize + asmData.extraStackSize - 16; asmData.controlDataStackPos = stackSize + asmData.extraStackSize - 8; @@ -3030,8 +3032,8 @@ function outline(ast) { }); 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 (name -> id, just like labels) var breakCapturers = 0; @@ -3041,16 +3043,21 @@ 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 @@ -3079,13 +3086,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, hasBreak: hasBreak, hasContinue: hasContinue, 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) { @@ -3111,24 +3120,41 @@ function outline(ast) { var sizeToOutline = extraInfo.sizeToOutline; var level = 0; + var costs = {}; // new function name => overhead cost of outlining + function doOutline(func, asmData, stats, start, end) { - printErr(' do outline ' + [func[1], level, 'range:', start, end, 'of', stats.length]); + if (!extraInfo.allowCostlyOutlines) var originalStats = copy(stats); var code = stats.slice(start, end+1); + var funcSize = measureSize(func); 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 + // 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') { + // wipe out control variable + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos), ['num', 0])]); + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ['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], makeAsmCoercion(['sub', ['name', getAsmType(v, asmData) == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', asmData.stackPos[v]]], ['num', '2']]], getAsmType(v, asmData))]]); + 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 var breakCapturers = 0; var continueCapturers = 0; @@ -3144,6 +3170,7 @@ function outline(ast) { 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') { @@ -3193,61 +3220,84 @@ function outline(ast) { } }); 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 + // 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), ASM_INT) + )]); + reps.push(['stat', makeAssign( + ['name', 'tempInt'], + makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ASM_INT) + )]); + reps.push(['stat', makeAssign( + ['name', 'tempDouble'], + makeAsmCoercion(makeStackAccess(ASM_DOUBLE, asmData.controlDataStackPos), ASM_DOUBLE) + )]); + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlStackPos), ['num', 0])]); + reps.push(['stat', makeAssign(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ['num', 0])]); // XXX not really needed + // use the control data information if (codeInfo.hasReturn) { reps.push(makeIf( - makeComparison(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['num', CONTROL_RETURN_VOID]), + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_RETURN_VOID]), [['stat', ['return']]] )); + } + if (codeInfo.hasReturnInt) { reps.push(makeIf( - makeComparison(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['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(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['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(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['num', CONTROL_BREAK]), + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_BREAK]), [['stat', ['break']]] )); if (keys(codeInfo.breaks).length > 0) { reps.push(makeIf( - makeComparison(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['num', CONTROL_BREAK_LABEL]), - [makeSwitch(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ASM_INT), keys(codeInfo.breaks).map(function(key) { + 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], [['stat', ['break', key]]]]; + return [['num', id], [['block', [['stat', ['break', key]]]]]]; }))] )); } } if (codeInfo.hasContinue) { reps.push(makeIf( - makeComparison(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['num', CONTROL_CONTINUE]), + makeComparison(makeAsmCoercion(['name', 'tempValue'], ASM_INT), '==', ['num', CONTROL_CONTINUE]), [['stat', ['continue']]] )); if (keys(codeInfo.continues).length > 0) { reps.push(makeIf( - makeComparison(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlStackPos), ASM_INT), '==', ['num', CONTROL_CONTINUE_LABEL]), - [makeSwitch(makeAsmCoercion(makeStackAccess(ASM_INT, asmData.controlDataStackPos), ASM_INT), keys(codeInfo.continues).map(function(key) { + 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], [['stat', ['continue', key]]]]; + return [['num', id], [['block', [['stat', ['continue', key]]]]]]; }))] )); } } } // add spills and unspills in outlined code outside the OL loop - for (var v in codeInfo.reads) { - if (v != 'sp') { + 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) { - 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]]]); + 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: {} }; @@ -3255,30 +3305,72 @@ function outline(ast) { if (v != 'sp') newAsmData.vars[v] = getAsmType(v, asmData); } for (var v in codeInfo.writes) { - assert(v != 'sp'); - newAsmData.vars[v] = getAsmType(v, asmData); + if (v != 'sp') newAsmData.vars[v] = getAsmType(v, asmData); } denormalizeAsm(newFunc, newAsmData); // replace in stats stats.splice.apply(stats, [start, end-start+1].concat(reps)); + 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)]]); + } + } + // the cost is the total size increase of all code, after the outlining operation. We also + // inherit the outlining cost of the parent function, if any, so the repeated outlining + // cannot infinitely recurse. + costs[newIdent] = measureSize(func) + measureSize(newFunc) - funcSize + (costs[func[1]] || 0); 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; var minIndex = stats == getStatements(func) ? getFirstIndexInNormalized(func, asmData) : 0; - while (--i >= minIndex) { + 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]; 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) { @@ -3288,8 +3380,14 @@ 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, @@ -3306,8 +3404,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--; @@ -3333,10 +3434,12 @@ 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 stats = getStatements(func); - var ret = outlineStatements(func, asmData, stats, 0.5*size); + 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 @@ -3377,11 +3480,12 @@ function outline(ast) { } } } + printErr('... resulting size of ' + func[1] + ' is ' + measureSize(func)); } denormalizeAsm(func, asmData); }); - sizeToOutline *= 2; // be more and more conservative about outlining as we look into outlined functions + 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. @@ -3390,8 +3494,12 @@ function outline(ast) { // 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; } } } |