diff options
Diffstat (limited to 'tools/js-optimizer.js')
| -rw-r--r-- | tools/js-optimizer.js | 203 |
1 files changed, 199 insertions, 4 deletions
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js index 7094cdfc..d58c8c6c 100644 --- a/tools/js-optimizer.js +++ b/tools/js-optimizer.js @@ -24,11 +24,14 @@ if (ENVIRONMENT_IS_NODE) { }; var nodeFS = require('fs'); + var nodePath = require('path'); read = function(filename) { + filename = nodePath['normalize'](filename); var ret = nodeFS['readFileSync'](filename).toString(); - if (!ret && filename[0] != '/') { - filename = __dirname.split('/').slice(0, -1).join('/') + '/src/' + filename; + // The path is absolute if the normalized version is the same as the resolved. + if (!ret && filename != nodePath['resolve'](filename)) { + filename = path.join(__dirname, '..', 'src', filename); ret = nodeFS['readFileSync'](filename).toString(); } return ret; @@ -97,12 +100,15 @@ if (typeof print === 'undefined') { // Fix read for our location read = function(filename) { - if (filename[0] != '/') filename = __dirname.split('/').slice(0, -1).join('/') + '/src/' + filename; + // The path is absolute if the normalized version is the same as the resolved. + filename = path.normalize(filename); + if (filename != path.resolve(filename)) filename = path.join(__dirname, '..', 'src', filename); return fs.readFileSync(filename).toString(); } var uglify = require('../tools/eliminator/node_modules/uglify-js'); var fs = require('fs'); +var path = require('path'); // Load some modules @@ -113,6 +119,8 @@ load('utility.js'); var FUNCTION = set('defun', 'function'); var LOOP = set('do', 'while', 'for'); var LOOP_FLOW = set('break', 'continue'); +var ASSIGN_OR_ALTER = set('assign', 'unary-postfix', 'unary-prefix'); +var CONTROL_FLOW = set('do', 'while', 'for', 'if', 'switch'); var NULL_NODE = ['name', 'null']; var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]]; @@ -382,7 +390,7 @@ function simplifyExpressionsPre(ast) { function simplifyBitops(ast) { var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^'); - var SAFE_BINARY_OPS = set('+', '-', '*', '/', '%'); + var SAFE_BINARY_OPS = set('+', '-', '*', '%'); // division is unsafe as it creates non-ints in JS var ZERO = ['num', 0]; var rerun = true; while (rerun) { @@ -663,6 +671,18 @@ function optimizeShiftsInternal(ast, conservative) { } } } + /* XXX - theoretically useful optimization(s), but commented out as not helpful in practice + // Transform (x << 2) >> 2 into x & mask or something even simpler + if (type == 'binary' && node[1] == '>>' && node[3][0] == 'num' && + node[2][0] == 'binary' && node[2][1] == '<<' && node[2][3][0] == 'num' && node[3][1] == node[2][3][1]) { + var subNode = node[2]; + var shifts = node[3][1]; + var mask = ((0xffffffff << shifts) >>> shifts) | 0; + return ['binary', '&', subNode[2], ['num', mask]]; + //return ['binary', '|', subNode[2], ['num', 0]]; + //return subNode[2]; + } + */ }); // Re-combine remaining shifts, to undo the breaking up we did before. may require reordering inside +'s traverse(fun, function(node, type, stack) { @@ -1134,6 +1154,180 @@ function loopOptimizer(ast) { vacuum(ast); } +// Very simple 'registerization', coalescing of variables into a smaller number. +// We do not optimize when there are switches, so this pass only makes sense with +// relooping. +// TODO: Consider how this fits in with the rest of the optimization toolchain. Do +// we still need the eliminator? Closure? And in what order? Perhaps just +// closure simple? +function registerize(ast) { + traverseGeneratedFunctions(ast, function(fun) { + // Replace all var definitions with assignments; we will add var definitions at the top after we registerize + // We also mark local variables - i.e., having a var definition + var localVars = {}; + var hasSwitch = false; // we cannot optimize variables if there is a switch + traverse(fun, function(node, type) { + if (type == 'var') { + node[1].forEach(function(defined) { localVars[defined[0]] = 1 }); + var vars = node[1].filter(function(varr) { return varr[1] }); + if (vars.length > 1) { + var ret = ['stat', []]; + var curr = ret[1]; + for (var i = 0; i < vars.length-1; i++) { + curr[0] = 'seq'; + curr[1] = ['assign', true, ['name', vars[i][0]], vars[i][1]]; + if (i != vars.length-2) curr = curr[2] = []; + } + curr[2] = ['assign', true, ['name', vars[vars.length-1][0]], vars[vars.length-1][1]]; + return ret; + } else if (vars.length == 1) { + return ['stat', ['assign', true, ['name', vars[0][0]], vars[0][1]]]; + } else { + return emptyNode(); + } + } else if (type == 'switch') { + hasSwitch = true; + } + }); + vacuum(fun); + // Find the # of uses of each variable. + // While doing so, check if all a variable's uses are dominated in a simple + // way by a simple assign, if so, then we can assign its register to it + // just for its definition to its last use, and not to the entire toplevel loop, + // we call such variables "optimizable" + var varUses = {}; + var level = 1; + var levelDominations = {}; + var varLevels = {}; + var possibles = {}; + var unoptimizables = {}; + traverse(fun, function(node, type) { + if (type == 'name') { + var name = node[1]; + if (localVars[name]) { + if (!varUses[name]) varUses[name] = 0; + varUses[name]++; + if (possibles[name] && !varLevels[name]) unoptimizables[name] = 1; // used outside of simple domination + } + } else if (type == 'assign' && typeof node[1] != 'string') { + if (node[2] && node[2][0] == 'name') { + var name = node[2][1]; + // if local and not yet used, this might be optimizable if we dominate + // all other uses + if (localVars[name] && !varUses[name] && !varLevels[name]) { + possibles[name] = 1; + varLevels[name] = level; + if (!levelDominations[level]) levelDominations[level] = {}; + levelDominations[level][name] = 1; + } + } + } else if (type in CONTROL_FLOW) { + level++; + } + }, function(node, type) { + if (type in CONTROL_FLOW) { + // Invalidate all dominating on this level, further users make it unoptimizable + for (var name in levelDominations[level]) { + varLevels[name] = 0; + } + levelDominations[level] = null; + level--; + } + }); + var optimizables = {}; + if (!hasSwitch) { + for (var possible in possibles) { + if (!unoptimizables[possible]) optimizables[possible] = 1; + } + } + // Go through the function's code, assigning 'registers'. + // The only tricky bit is to keep variables locked on a register through loops, + // since they can potentially be returned to. Optimizable variables lock onto + // loops that they enter, unoptimizable variables lock in a conservative way + // into the topmost loop. + // Note that we cannot lock onto a variable in a loop if it was used and free'd + // before! (then they could overwrite us in the early part of the loop). For now + // we just use a fresh register to make sure we avoid this, but it could be + // optimized to check for safe registers (free, and not used in this loop level). + var varRegs = {}; // maps variables to the register they will use all their life + var freeRegs = []; + var nextReg = 1; + var fullNames = {}; + var loopRegs = {}; // for each loop nesting level, the list of bound variables + var loops = 0; // 0 is toplevel, 1 is first loop, etc + var saved = 0; + var activeOptimizables = {}; + var optimizableLoops = {}; + function decUse(name) { + if (!varUses[name]) return false; // no uses left, or not a relevant variable + if (optimizables[name]) activeOptimizables[name] = 1; + var reg = varRegs[name]; + if (!reg) { + // acquire register + if (optimizables[name] && freeRegs.length > 0) { + reg = freeRegs.pop(); + saved++; + } else { + reg = nextReg++; + fullNames[reg] = 'r' + reg; // TODO: even smaller names + } + varRegs[name] = reg; + } + varUses[name]--; + assert(varUses[name] >= 0); + if (varUses[name] == 0) { + if (optimizables[name]) delete activeOptimizables[name]; + // If we are not in a loop, or we are optimizable and not bound to a loop + // (we might have been in one but left it), we can free the register now. + if (loops == 0 || (optimizables[name] && !optimizableLoops[name])) { + // free register + freeRegs.push(reg); + } else { + // when the relevant loop is exited, we will free the register + var releventLoop = optimizables[name] ? (optimizableLoops[name] || 1) : 1; + if (!loopRegs[releventLoop]) loopRegs[releventLoop] = []; + loopRegs[releventLoop].push(reg); + } + } + return true; + } + traverse(fun, function(node, type) { // XXX we rely on traversal order being the same as execution order here + if (type == 'name') { + var name = node[1]; + if (decUse(name)) { + node[1] = fullNames[varRegs[name]]; + } + } else if (type in LOOP) { + loops++; + // Active optimizables lock onto this loop, if not locked onto one that encloses this one + for (var name in activeOptimizables) { + if (!optimizableLoops[name]) { + optimizableLoops[name] = loops; + } + } + } + }, function(node, type) { + if (type in LOOP) { + // Free registers that were locked to this loop + if (loopRegs[loops]) { + freeRegs = freeRegs.concat(loopRegs[loops]); + loopRegs[loops] = []; + } + loops--; + } + }); + // Add vars at the beginning + if (nextReg > 1) { + var vars = []; + for (var i = 1; i < nextReg; i++) { + vars.push([fullNames[i]]); + } + getStatements(fun).unshift(['var', vars]); + } + //printErr(fun[1] + ': saved ' + saved + ' / ' + (saved + nextReg - 1) + ' vars through registerization'); // not totally accurate + }); +} + // Passes table var compress = false; @@ -1150,6 +1344,7 @@ var passes = { simplifyExpressionsPost: simplifyExpressionsPost, hoistMultiples: hoistMultiples, loopOptimizer: loopOptimizer, + registerize: registerize, compress: function() { compress = true; } }; |