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.js333
1 files changed, 191 insertions, 142 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 161ed59c..5324e15c 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -1743,6 +1743,36 @@ function getStackBumpSize(ast) {
return node ? node[3][2][3][1] : 0;
}
+// Name minification
+
+var RESERVED = set('do', 'if', 'in', 'for', 'new', 'try', 'var', 'env', 'let');
+var VALID_MIN_INITS = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$';
+var VALID_MIN_LATERS = VALID_MIN_INITS + '0123456789';
+
+var minifiedNames = [];
+var minifiedState = [0];
+
+function ensureMinifiedNames(n) { // make sure the nth index in minifiedNames exists. done 100% deterministically
+ while (minifiedNames.length < n+1) {
+ // generate the current name
+ var name = VALID_MIN_INITS[minifiedState[0]];
+ for (var i = 1; i < minifiedState.length; i++) {
+ name += VALID_MIN_LATERS[minifiedState[i]];
+ }
+ if (!(name in RESERVED)) minifiedNames.push(name);
+ // increment the state
+ var i = 0;
+ while (1) {
+ minifiedState[i]++;
+ if (minifiedState[i] < (i === 0 ? VALID_MIN_INITS : VALID_MIN_LATERS).length) break;
+ // overflow
+ minifiedState[i] = 0;
+ i++;
+ if (i === minifiedState.length) minifiedState.push(-1); // will become 0 after increment in next loop head
+ }
+ }
+}
+
// 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.)
@@ -1853,14 +1883,14 @@ function registerize(ast) {
return ret;
}
// find the next free minified name that is not used by a global that shows up in this function
- while (nextRegName < extraInfo.names.length) {
- var ret = extraInfo.names[nextRegName++];
+ while (1) {
+ ensureMinifiedNames(nextRegName);
+ var ret = minifiedNames[nextRegName++];
if (!usedGlobals[ret]) {
regTypes[ret] = type;
return ret;
}
}
- assert('ran out of names');
}
// Find the # of uses of each variable.
// While doing so, check if all a variable's uses are dominated in a simple
@@ -2847,16 +2877,16 @@ function minifyGlobals(ast) {
var vars = node[1];
for (var i = 0; i < vars.length; i++) {
var name = vars[i][0];
- assert(next < extraInfo.names.length);
- vars[i][0] = minified[name] = extraInfo.names[next++];
+ ensureMinifiedNames(next);
+ vars[i][0] = minified[name] = minifiedNames[next++];
}
}
});
// add all globals in function chunks, i.e. not here but passed to us
for (var i = 0; i < extraInfo.globals.length; i++) {
name = extraInfo.globals[i];
- assert(next < extraInfo.names.length);
- minified[name] = extraInfo.names[next++];
+ ensureMinifiedNames(next);
+ minified[name] = minifiedNames[next++];
}
// apply minification
traverse(ast, function(node, type) {
@@ -2930,162 +2960,180 @@ function relocate(ast) {
var NODES_WITHOUT_ELIMINATION_SENSITIVITY = set('name', 'num', 'binary', 'unary-prefix');
var FAST_ELIMINATION_BINARIES = setUnion(setUnion(USEFUL_BINARY_OPS, COMPARE_OPS), set('+'));
-function outline(ast) {
- function measureSize(ast) {
- var size = 0;
- traverse(ast, function() {
- size++;
- });
- return size;
- }
-
- function aggressiveVariableElimination(func, asmData) {
- // This removes as many variables as possible. This is often not the best thing because it increases
- // code size, but it is far preferable to the risk of split functions needing to do more spilling. Specifically,
- // it finds 'trivial' variables: ones with 1 definition, and that definition is not sensitive to any changes: it
- // only depends on constants and local variables that are themselves trivial. We can unquestionably eliminate
- // such variables in a trivial manner.
-
- var assignments = {};
- var appearances = {};
- var defs = {};
- var considered = {};
+function measureSize(ast) {
+ var size = 0;
+ traverse(ast, function() {
+ size++;
+ });
+ return size;
+}
- traverse(func, function(node, type) {
- if (type == 'assign' && node[2][0] == 'name') {
- var name = node[2][1];
- if (name in asmData.vars) {
- assignments[name] = (assignments[name] || 0) + 1;
- appearances[name] = (appearances[name] || 0) - 1; // this appearance is a definition, offset the counting later
- 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
- }
- }
- } else if (type == 'name') {
- var name = node[1];
- if (name in asmData.vars) {
- appearances[name] = (appearances[name] || 0) + 1;
+function aggressiveVariableEliminationInternal(func, asmData) {
+ // This removes as many variables as possible. This is often not the best thing because it increases
+ // code size, but it is far preferable to the risk of split functions needing to do more spilling, so
+ // we use it when outlining.
+ // Specifically, this finds 'trivial' variables: ones with 1 definition, and that definition is not sensitive to any changes: it
+ // only depends on constants and local variables that are themselves trivial. We can unquestionably eliminate
+ // such variables in a trivial manner.
+
+ var assignments = {};
+ var appearances = {};
+ var defs = {};
+ var considered = {};
+
+ traverse(func, function(node, type) {
+ if (type == 'assign' && node[2][0] == 'name') {
+ var name = node[2][1];
+ if (name in asmData.vars) {
+ assignments[name] = (assignments[name] || 0) + 1;
+ appearances[name] = (appearances[name] || 0) - 1; // this appearance is a definition, offset the counting later
+ 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
}
}
- });
+ } else if (type == 'name') {
+ var name = node[1];
+ if (name in asmData.vars) {
+ appearances[name] = (appearances[name] || 0) + 1;
+ }
+ }
+ });
- var allTrivials = {}; // key of a trivial var => size of its (expanded) value, at least 1
-
- // three levels of variables:
- // 1. trivial: 1 def (or less), uses nothing sensitive, can be eliminated
- // 2. safe: 1 def (or less), can be used in a trivial, but cannot itself be eliminated
- // 3. sensitive: uses a global or memory or something else that prevents trivial elimination.
-
- function assessTriviality(name) {
- // only care about vars with 0-1 assignments of (0 for parameters), and can ignore label (which is not explicitly initialized, but cannot be eliminated ever anyhow)
- if (assignments[name] > 1 || (!(name in asmData.vars) && !(name in asmData.params)) || name == 'label') return false;
- if (considered[name]) return allTrivials[name];
- considered[name] = true;
- var sensitive = false;
- var size = 0, originalSize = 0;
- var def = defs[name];
- if (def) {
- var value = def[3];
- originalSize = measureSize(value);
- if (value) {
- traverse(value, function recurseValue(node, type) {
- var one = node[1];
- if (!(type in NODES_WITHOUT_ELIMINATION_SENSITIVITY)) { // || (type == 'binary' && !(one in FAST_ELIMINATION_BINARIES))) {
- sensitive = true;
+ var allTrivials = {}; // key of a trivial var => size of its (expanded) value, at least 1
+
+ // three levels of variables:
+ // 1. trivial: 1 def (or less), uses nothing sensitive, can be eliminated
+ // 2. safe: 1 def (or less), can be used in a trivial, but cannot itself be eliminated
+ // 3. sensitive: uses a global or memory or something else that prevents trivial elimination.
+
+ function assessTriviality(name) {
+ // only care about vars with 0-1 assignments of (0 for parameters), and can ignore label (which is not explicitly initialized, but cannot be eliminated ever anyhow)
+ if (assignments[name] > 1 || (!(name in asmData.vars) && !(name in asmData.params)) || name == 'label') return false;
+ if (considered[name]) return allTrivials[name];
+ considered[name] = true;
+ var sensitive = false;
+ var size = 0, originalSize = 0;
+ var def = defs[name];
+ if (def) {
+ var value = def[3];
+ originalSize = measureSize(value);
+ if (value) {
+ traverse(value, function recurseValue(node, type) {
+ var one = node[1];
+ if (!(type in NODES_WITHOUT_ELIMINATION_SENSITIVITY)) { // || (type == 'binary' && !(one in FAST_ELIMINATION_BINARIES))) {
+ sensitive = true;
+ return true;
+ }
+ if (type == 'name' && !assessTriviality(one)) {
+ if (assignments[one] > 1 || (!(one in asmData.vars) && !(one in asmData.params))) {
+ sensitive = true; // directly using something sensitive
return true;
- }
- if (type == 'name' && !assessTriviality(one)) {
- if (assignments[one] > 1 || (!(one in asmData.vars) && !(one in asmData.params))) {
- sensitive = true; // directly using something sensitive
- return true;
- } // otherwise, not trivial, but at least safe.
- }
- // if this is a name, it must be a trivial variable (or a safe one) and we know its size
- size += ((type == 'name') ? allTrivials[one] : 1) || 1;
- });
- }
- }
- if (!sensitive) {
- size = size || 1;
- originalSize = originalSize || 1;
- var factor = ((appearances[name] - 1) || 0) * (size - originalSize); // If no size change or just one appearance, always ok to trivially eliminate. otherwise, tradeoff
- if (factor <= 12) {
- allTrivials[name] = size; // trivial!
- return true;
- }
+ } // otherwise, not trivial, but at least safe.
+ }
+ // if this is a name, it must be a trivial variable (or a safe one) and we know its size
+ size += ((type == 'name') ? allTrivials[one] : 1) || 1;
+ });
}
- return false;
}
- for (var name in asmData.vars) {
- assessTriviality(name);
+ if (!sensitive) {
+ size = size || 1;
+ originalSize = originalSize || 1;
+ var factor = ((appearances[name] - 1) || 0) * (size - originalSize); // If no size change or just one appearance, always ok to trivially eliminate. otherwise, tradeoff
+ if (factor <= 12) {
+ allTrivials[name] = size; // trivial!
+ return true;
+ }
}
- var trivials = {};
+ return false;
+ }
+ for (var name in asmData.vars) {
+ assessTriviality(name);
+ }
+ var trivials = {};
- for (var name in allTrivials) { // from now on, ignore parameters
- if (name in asmData.vars) trivials[name] = true;
- }
+ for (var name in allTrivials) { // from now on, ignore parameters
+ if (name in asmData.vars) trivials[name] = true;
+ }
- allTrivials = {};
+ allTrivials = {};
- var values = {};
+ var values = {}, recursives = {};
- function evaluate(name) {
- var node = values[name];
- if (node) return node;
- values[node] = null; // prevent infinite recursion
- var def = defs[name];
- if (def) {
- node = def[3];
- if (node[0] == 'name') {
- var name2 = node[1];
- if (name2 in trivials) {
- node = evaluate(name2);
- }
- } else {
- traverse(node, function(node, type) {
- if (type == 'name') {
- var name2 = node[1];
- if (name2 in trivials) {
- return evaluate(name2);
- }
- }
- });
+ function evaluate(name) {
+ var node = values[name];
+ if (node) return node;
+ values[name] = null; // prevent infinite recursion
+ var def = defs[name];
+ if (def) {
+ node = def[3];
+ if (node[0] == 'name') {
+ var name2 = node[1];
+ assert(name2 !== name);
+ if (name2 in trivials) {
+ node = evaluate(name2);
}
- values[name] = node;
+ } else {
+ traverse(node, function(node, type) {
+ if (type == 'name') {
+ var name2 = node[1];
+ if (name2 === name) {
+ recursives[name] = 1;
+ return false;
+ }
+ if (name2 in trivials) {
+ return evaluate(name2);
+ }
+ }
+ });
}
- return node;
+ values[name] = node;
}
+ return node;
+ }
+
+ for (var name in trivials) {
+ evaluate(name);
+ }
+ for (var name in recursives) {
+ delete trivials[name];
+ }
- for (var name in trivials) {
- evaluate(name);
+ for (var name in trivials) {
+ var def = defs[name];
+ if (def) {
+ def.length = 0;
+ def[0] = 'toplevel';
+ def[1] = [];
}
+ delete asmData.vars[name];
+ }
- for (var name in trivials) {
- var def = defs[name];
- if (def) {
- def.length = 0;
- def[0] = 'toplevel';
- def[1] = [];
+ // Perform replacements TODO: save list of uses objects before, replace directly, avoid extra traverse
+ traverse(func, function(node, type) {
+ if (type == 'name') {
+ var name = node[1];
+ if (name in trivials) {
+ var value = values[name];
+ if (!value) throw 'missing value: ' + [func[1], name, values[name]] + ' - faulty reliance on asm zero-init?';
+ return copy(value); // must copy, or else the same object can be used multiple times
}
- delete asmData.vars[name];
}
+ });
+}
- // Perform replacements TODO: save list of uses objects before, replace directly, avoid extra traverse
- traverse(func, function(node, type) {
- if (type == 'name') {
- var name = node[1];
- if (name in trivials) {
- var value = values[name];
- if (!value) throw 'missing value: ' + [func[1], name, values[name]] + ' - faulty reliance on asm zero-init?';
- return copy(value); // must copy, or else the same object can be used multiple times
- }
- }
- });
- }
+function aggressiveVariableElimination(ast) {
+ assert(asm, 'need ASM_JS for aggressive variable elimination');
+ traverseGeneratedFunctions(ast, function(func, type) {
+ var asmData = normalizeAsm(func);
+ aggressiveVariableEliminationInternal(func, asmData);
+ denormalizeAsm(func, asmData);
+ });
+}
+function outline(ast) {
// Try to flatten out code as much as possible, to make outlining more feasible.
function flatten(func, asmData) {
var minSize = extraInfo.sizeToOutline/4;
@@ -3740,7 +3788,7 @@ function outline(ast) {
var size = measureSize(func);
if (size >= extraInfo.sizeToOutline && maxTotalFunctions > 0) {
maxTotalFunctions--;
- aggressiveVariableElimination(func, asmData);
+ aggressiveVariableEliminationInternal(func, asmData);
flatten(func, asmData);
analyzeFunction(func, asmData);
calculateThreshold(func, asmData);
@@ -3921,6 +3969,7 @@ var passes = {
registerize: registerize,
eliminate: eliminate,
eliminateMemSafe: eliminateMemSafe,
+ aggressiveVariableElimination: aggressiveVariableElimination,
minifyGlobals: minifyGlobals,
relocate: relocate,
outline: outline,
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-25 17:03:18 +0000