aboutsummaryrefslogtreecommitdiff
path: root/tools/js-optimizer.js
diff options
context:
space:
mode:
Diffstat (limited to 'tools/js-optimizer.js')
-rw-r--r--tools/js-optimizer.js193
1 files changed, 174 insertions, 19 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 06d82752..71a59921 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -136,6 +136,9 @@ var CONTROL_FLOW = set('do', 'while', 'for', 'if', 'switch');
var NAME_OR_NUM = set('name', 'num');
var ASSOCIATIVE_BINARIES = set('+', '*', '|', '&', '^');
+var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch');
+var CONTINUE_CAPTURERS = LOOP;
+
var NULL_NODE = ['name', 'null'];
var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]];
var TRUE_NODE = ['unary-prefix', '!', ['num', 0]];
@@ -559,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' &&
@@ -633,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]];
@@ -1531,10 +1536,15 @@ 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;
-function detectAsmCoercion(node) {
+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;
- return node[0] === 'unary-prefix' ? ASM_DOUBLE : ASM_INT;
+ 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]];
+ }
+ return ASM_INT;
}
function makeAsmParamCoercion(param, type) {
@@ -2974,17 +2984,31 @@ function outline(ast) {
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.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 labelCounter = 1; // 0 means no label
+
+ traverse(ast, function(node, type) {
+ if ((type == 'label' || type in LOOP_FLOW) && node[1] && !(node[1] in labels)) {
+ labels[node[1]] = labelCounter++;
+ }
+ });
+
var writes = {};
var appearances = {};
var hasReturn = false, hasBreak = false, hasContinue = false;
var breaks = {}; // set of labels we break or continue
var continues = {}; // to. '0' is an unlabeled one
+ var breakCapturers = 0;
+ var continueCapturers = 0;
traverse(ast, function(node, type) {
if (type == 'assign' && node[2][0] == 'name') {
@@ -3001,11 +3025,31 @@ function outline(ast) {
} else if (type == 'return') {
hasReturn = true;
} else if (type == 'break') {
- breaks[node[1] || 0] = 0;
+ 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;
hasBreak = true;
} else if (type == 'continue') {
- continues[node[1] || 0] = 0;
+ 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;
hasContinue = true;
+ } else {
+ if (type in BREAK_CAPTURERS) {
+ breakCapturers++;
+ }
+ if (type in CONTINUE_CAPTURERS) {
+ continueCapturers++;
+ }
+ }
+ }, function(node, type) {
+ if (type in BREAK_CAPTURERS) {
+ breakCapturers--;
+ }
+ if (type in CONTINUE_CAPTURERS) {
+ continueCapturers--;
}
});
@@ -3015,9 +3059,26 @@ function outline(ast) {
if (appearances[name] > 0) reads[name] = 0;
}
- return { writes: writes, reads: reads, hasReturn: hasReturn, breaks: breaks, continues: continues };
+ return { writes: writes, reads: reads, hasReturn: hasReturn, breaks: breaks, continues: continues, labels: labels };
+ }
+
+ function makeAssign(dst, src) {
+ return ['assign', true, dst, src];
+ }
+ function makeStackAccess(type, pos) { // TODO: float64, not 32
+ return ['sub', ['name', type == ASM_INT ? 'HEAP32' : 'HEAPF32'], ['binary', '>>', ['binary', '+', ['name', 'sp'], ['num', pos]], ['num', '2']]];
+ }
+ function makeIf(cond, then, else_) {
+ var ret = ['if', cond, ['block', then]];
+ if (else_) ret.push(['block', else_]);
+ return ret;
+ }
+ function makeComparison(left, comp, right) {
+ return ['binary', comp, left, right];
}
+ 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;
@@ -3025,7 +3086,7 @@ function outline(ast) {
printErr(' do outline ' + [func[1], level, 'range:', start, end, 'of', stats.length]);
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
+ // add spills and reads before and after the call to the outlined code, and in the outlined code itself
var codeInfo = analyzeCode(func, asmData, code);
var reps = [];
for (var v in codeInfo.reads) {
@@ -3039,21 +3100,109 @@ function outline(ast) {
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]]]);
}
- stats.splice.apply(stats, [start, end-start+1].concat(reps));
// Generate new function
if (codeInfo.hasReturn || 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) {
+ // 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++;
+ }
+ }
+ }, function(node, type) {
+ if (type in BREAK_CAPTURERS) {
+ breakCapturers--;
+ }
+ if (type in CONTINUE_CAPTURERS) {
+ continueCapturers--;
+ }
+ });
+ // read the control data at the callsite to the outlined function
+ if (codeInfo.hasReturn) {
+ reps.push(makeIf(
+ makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_RETURN_VOID]),
+ [['stat', ['return']]]
+ ));
+ reps.push(makeIf(
+ makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_RETURN_INT]),
+ [['stat', ['return', makeStackAccess(ASM_INT, asmData.controlDataStackPos)]]]
+ ));
+ reps.push(makeIf(
+ makeComparison(makeStackAccess(ASM_INT, asmData.controlStackPos), '==', ['num', CONTROL_RETURN_DOUBLE]),
+ [['stat', ['return', makeStackAccess(ASM_DOUBLE, asmData.controlDataStackPos)]]]
+ ));
+ }
+ 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
+ ));
+ }
+ 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
+ ));
+ }
}
var newFunc = ['defun', newIdent, ['sp'], code];
- var newAsmInfo = { params: { sp: ASM_INT }, vars: {} };
+ var newAsmData = { params: { sp: ASM_INT }, vars: {} };
for (var v in codeInfo.reads) {
- newAsmInfo.vars[v] = getAsmType(asmData, v);
+ newAsmData.vars[v] = getAsmType(asmData, v);
}
for (var v in codeInfo.writes) {
- newAsmInfo.vars[v] = getAsmType(asmData, v);
+ newAsmData.vars[v] = getAsmType(asmData, v);
}
- denormalizeAsm(newFunc, newAsmInfo);
+ denormalizeAsm(newFunc, newAsmData);
+ // replace in stats
+ stats.splice.apply(stats, [start, end-start+1].concat(reps));
return [newFunc];
}
@@ -3138,7 +3287,7 @@ function outline(ast) {
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 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
@@ -3175,12 +3324,13 @@ function fixDotZero(js) {
});
}
-function asmLoopOptimizer(ast) {
+function asmLastOpts(ast) {
traverseGeneratedFunctions(ast, function(fun) {
- // This is at the end of the pipeline, we can assume all other optimizations are done, and we modify loops
- // into shapes that might confuse other passes
traverse(fun, function(node, type) {
if (type === 'while' && node[1][0] === 'num' && node[1][1] === 1 && node[2][0] === 'block') {
+ // This is at the end of the pipeline, we can assume all other optimizations are done, and we modify loops
+ // into shapes that might confuse other passes
+
// while (1) { .. if (..) { break } } ==> do { .. } while(..)
var stats = node[2][1];
var last = stats[stats.length-1];
@@ -3208,6 +3358,11 @@ function asmLoopOptimizer(ast) {
node[1] = simplifyNotCompsDirect(['unary-prefix', '!', conditionToBreak]);
return node;
}
+ } else if (type == 'binary' && node[1] == '&' && node[3][0] == 'unary-prefix' && node[3][1] == '-' && node[3][2][0] == 'num' && node[3][2][1] == 1) {
+ // Change &-1 into |0, at this point the hint is no longer needed
+ node[1] = '|';
+ node[3] = node[3][2];
+ node[3][1] = 0;
}
});
});
@@ -3266,7 +3421,7 @@ arguments_.slice(1).forEach(function(arg) {
passes[arg](ast);
});
if (asm && last) {
- asmLoopOptimizer(ast); // TODO: move out of last, to make last faster when done later (as in side modules)
+ asmLastOpts(ast); // TODO: move out of last, to make last faster when done later (as in side modules)
prepDotZero(ast);
}
var js = astToSrc(ast, minifyWhitespace), old;
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-27 17:04:00 +0000