#!/usr/bin/env node

// Copyright 2011 The Emscripten Authors. All rights reserved.

// Emscripten is available under two separate licenses, the MIT license and the

// University of Illinois/NCSA Open Source License. Both these licenses can be

// found in the LICENSE file.

//

// Optimizer tool. This is meant to be run after the emscripten compiler has

// finished generating code. These optimizations are done on the generated

// code to further improve it.

//

// Be aware that this is *not* a general JS optimizer. It assumes that the

// input is valid asm.js and makes strong assumptions based on this. It may do

// anything from crashing to optimizing incorrectly if the input is not valid!

//

// TODO: Optimize traverse to modify a node we want to replace, in-place,

// instead of returning it to the previous call frame where we check?

// TODO: Share EMPTY_NODE instead of emptyNode that constructs?

var uglify = require('../third_party/uglify-js');

var fs = require('fs');

var path = require('path');

var fs = require('fs');

var arguments_ = process['argv'].slice(2);

var debug = false;

function printErr(x) {

process.stderr.write(x + '\n');

}

function print(x) {

process.stdout.write(x + '\n');

}

function assert(x, msg) {

if (!x) throw 'assertion failed (' + msg + ') : ' + new Error().stack;

}

function read(filename) {

return fs.readFileSync(filename).toString();

}

function load(f) {

f = path.join(__dirname, f)

eval.call(null, read(f));

};

load('../src/utility.js');

// Utilities

var LOOP = set('do', 'while', 'for');

var LOOP_FLOW = set('break', 'continue');

var CONTROL_FLOW = set('do', 'while', 'for', 'if', 'switch');

var NAME_OR_NUM = set('name', 'num');

var ASSOCIATIVE_BINARIES = set('+', '*', '|', '&', '^');

var ALTER_FLOW = set('break', 'continue', 'return');

var BITWISE = set('|', '&', '^');

var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch');

var CONTINUE_CAPTURERS = LOOP;

var COMMABLE = set('assign', 'binary', 'unary-prefix', 'unary-postfix', 'name', 'num', 'call', 'seq', 'conditional', 'sub');

var CONDITION_CHECKERS = set('if', 'do', 'while', 'switch');

var BOOLEAN_RECEIVERS = set('if', 'do', 'while', 'conditional');

var FUNCTIONS_THAT_ALWAYS_THROW = set('abort', '___resumeException', '___cxa_throw', '___cxa_rethrow');

var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]];

var GENERATED_FUNCTIONS_MARKER = '// EMSCRIPTEN_GENERATED_FUNCTIONS';

var generatedFunctions = false; // whether we have received only generated functions

var extraInfo = null;

function srcToAst(src) {

return uglify.parser.parse(src, false, debug);

}

function astToSrc(ast, minifyWhitespace) {

return uglify.uglify.gen_code(ast, {

debug: debug,

ascii_only: true,

beautify: !minifyWhitespace,

indent_level: 1

});

}

function srcToStat(src) {

return srcToAst(src)[1][0]; // look into toplevel

}

function srcToExp(src) {

return srcToStat(src)[1];

}

// Traverses the children of a node. If the traverse function returns an object,

// replaces the child. If it returns true, stop the traversal and return true.

function traverseChildren(node, traverse, pre, post) {

if (node[0] === 'var') {

// don't traverse the names, just the values

var children = node[1];

if (!Array.isArray(children)) return;

for (var i = 0; i < children.length; i++) {

var subnode = children[i];

if (subnode.length === 2) {

var value = subnode[1];

if (Array.isArray(value)) {

var subresult = traverse(value, pre, post);

if (subresult === true) return true;

if (subresult !== null && typeof subresult === 'object') subnode[1] = subresult;

}

}

}

} else if (node[0] === 'object') {

// don't traverse the names, just the values

var children = node[1];

if (!Array.isArray(children)) return;

for (var i = 0; i < children.length; i++) {

var subnode = children[i];

var value = subnode[1];

if (Array.isArray(value)) {

var subresult = traverse(value, pre, post);

if (subresult === true) return true;

if (subresult !== null && typeof subresult === 'object') subnode[1] = subresult;

}

}

} else {

// generic traversal

for (var i = 0; i < node.length; i++) {

var subnode = node[i];

if (Array.isArray(subnode)) {

var subresult = traverse(subnode, pre, post);

if (subresult === true) return true;

if (subresult !== null && typeof subresult === 'object') node[i] = subresult;

}

}

}

}

// Traverses a JavaScript syntax tree rooted at the given node calling the given

// callback for each node.

// @arg node: The root of the AST.

// @arg pre: The pre to call for each node. This will be called with

// the node as the first argument and its type as the second. If true is

// returned, the traversal is stopped. If an object is returned,

// it replaces the passed node in the tree. If null is returned, we stop

// traversing the subelements (but continue otherwise).

// @arg post: A callback to call after traversing all children.

// @returns: If the root node was replaced, the new root node. If the traversal

// was stopped, true. Otherwise undefined.

function traverse(node, pre, post) {

var type = node[0], result, len;

var relevant = typeof type === 'string';

if (relevant) {

var result = pre(node, type);

if (result === true) return true;

if (result && result !== null) node = result; // Continue processing on this node

}

if (result !== null) {

if (traverseChildren(node, traverse, pre, post) === true) return true;

}

if (relevant) {

if (post) {

var postResult = post(node, type);

result = result || postResult;

}

}

return result;

}

// Only walk through the generated functions

function traverseGeneratedFunctions(ast, callback) {

assert(generatedFunctions);

if (ast[0] === 'toplevel') {

var stats = ast[1];

for (var i = 0; i < stats.length; i++) {

var curr = stats[i];

if (curr[0] === 'defun') callback(curr);

}

} else if (ast[0] === 'defun') {

callback(ast);

}

}

function traverseGenerated(ast, pre, post) {

traverseGeneratedFunctions(ast, function(func) {

traverse(func, pre, post);

});

}

function deStat(node) {

if (node[0] === 'stat') return node[1];

return node;

}

function emptyNode() { // XXX do we need to create new nodes here? can't we reuse?

return ['toplevel', []]

}

function isEmptyNode(node) {

return node.length === 2 && node[0] === 'toplevel' && node[1].length === 0;

}

function clearEmptyNodes(list) {

for (var i = 0; i < list.length;) {

if (isEmptyNode(list[i]) || (list[i][0] === 'stat' && isEmptyNode(list[i][1]))) {

list.splice(i, 1);

} else {

i++;

}

}

}

function filterEmptyNodes(list) { // creates a copy and returns it

return list.filter(function(node) {

return !(isEmptyNode(node) || (node[0] === 'stat' && isEmptyNode(node[1])));

});

}

function removeEmptySubNodes(node) {

if (node[0] === 'defun') {

node[3] = filterEmptyNodes(node[3]);

} else if (node[0] === 'block' && node[1]) {

node[1] = filterEmptyNodes(node[1]);

} else if (node[0] === 'seq' && isEmptyNode(node[1])) {

return node[2];

}

/*

var stats = getStatements(node);

if (stats) clearEmptyNodes(stats);

*/

}

function removeAllEmptySubNodes(ast) {

traverse(ast, removeEmptySubNodes);

}

function astCompare(x, y) {

if (!Array.isArray(x)) return x === y;

if (!Array.isArray(y)) return false;

if (x.length !== y.length) return false;

for (var i = 0; i < x.length; i++) {

if (!astCompare(x[i], y[i])) return false;

}

return true;

}

// calls definitely on child nodes that will be called, in order, and calls maybe on nodes that might be called.

// a(); if (b) c(); d(); will call definitely(a, arg), maybe(c, arg), definitely(d, arg)

function traverseChildrenInExecutionOrder(node, definitely, maybe, arg) {

switch (node[0]) {

default: throw '!' + node[0];

case 'num': case 'var': case 'name': case 'toplevel': case 'string':

case 'break': case 'continue': break; // nodes with no interesting children; they themselves have already been definitely or maybe'd

case 'assign': case 'binary': {

definitely(node[2], arg);

definitely(node[3], arg);

break;

}

case 'sub': case 'seq': {

definitely(node[1], arg);

definitely(node[2], arg);

break;

}

case 'while': {

definitely(node[1], arg);

maybe(node[2], arg); // may never enter the loop

maybe(node[1], arg); // may enter the loop a second time

maybe(node[2], arg);

break;

}

case 'do': {

definitely(node[2], arg);

maybe(node[1], arg); // may never reach the condition if we break

maybe(node[2], arg);

maybe(node[1], arg);

break;

}

case 'binary': {

definitely(node[2], arg);

definitely(node[3], arg);

break;

}

case 'dot': {

definitely(node[1], arg);

break;

}

case 'unary-prefix': case 'label': {

definitely(node[2], arg);

break;

}

case 'call': {

definitely(node[1], arg);

var args = node[2];

for (var i = 0; i < args.length; i++) {

definitely(args[i], arg);

}

break;

}

case 'if': case 'conditional': {

definitely(node[1], arg);

maybe(node[2], arg);

if (node[3]) { maybe(node[3], arg); }

break;

}

case 'defun': case 'func': case 'block': {

var stats = getStatements(node);

if (!stats || stats.length === 0) break;

for (var i = 0; i < stats.length; i++) {

definitely(stats[i], arg);

// check if we might break, if we have more to do

if (i === stats.length - 1) break;

var labels = {};

var breakCaptured = 0;

var mightBreak = false;

traverse(stats[i], function(node, type) {

if (type === 'label') labels[node[1]] = true;

else if (type in BREAK_CAPTURERS) {

breakCaptured++;

} else if (type === 'break') {

if (node[1]) {

// labeled break

if (!(node[1] in labels)) mightBreak = true;

} else {

if (!breakCaptured) mightBreak = true;

}

}

}, function(node, type) {

if (type === 'label') delete labels[node[1]];

else if (type in BREAK_CAPTURERS) {

breakCaptured--;

}

});

if (mightBreak) {

// all the rest are in one big maybe

return maybe(['block', stats.slice(i+1)], arg);

}

}

break;

}

case 'stat': case 'return': {

definitely(node[1], arg);

break;

}

case 'switch': {

definitely(node[1], arg);

var cases = node[2];

for (var i = 0; i < cases.length; i++) {

var c = cases[i];

var stats = c[1];

var temp = ['block', stats];

maybe(temp, arg);

}

}

}

}

// Passes

// Dump the AST. Useful for debugging. For example,

// node tools/js-optimizer.js ABSOLUTE_PATH_TO_FILE dumpAst

function dumpAst(ast) {

printErr(JSON.stringify(ast, null, ' '));

}

function dumpSrc(ast) {

printErr(astToSrc(ast));

}

function minifyGlobals(ast) {

// The input is in form

//

// function instantiate(asmLibraryArg, wasmMemory, wasmTable) {

// var helper..

// function asmFunc(global, env, buffer) {

// var memory = env.memory;

// var HEAP8 = new global.Int8Array(buffer);

//

// We want to minify the interior instantiate, basically everything but

// the name instantiate itself, which is used externally to call it.

//

// This is *not* a complete minification algorithm. It does not have a full

// understanding of nested scopes. Instead it assumes the code is fairly

// simple - as wasm2js output is - and looks at all the minifiable names as

// a whole. A possible bug here is something like

//

// function instantiate(asmLibraryArg, wasmMemory, wasmTable) {

// var x = foo;

// function asmFunc(global, env, buffer) {

// var foo = 10;

//

// Here foo is declared in an inner scope, and the outer use of foo looks

// to the global scope. The analysis here only thinks something is from the

// global scope if it is not in any var or function declaration. In practice,

// the globals used from wasm2js output are things like Int8Array that we

// don't declare as locals, but we should probably have a fully scope-aware

// analysis here. FIXME

assert(ast[0] === 'toplevel');

var instantiateFunc = ast[1][0];

assert(instantiateFunc[0] === 'defun');

assert(instantiateFunc[1] === 'instantiate');

var minified = new Map();

var next = 0;

function getMinified(name) {

assert(name);

if (minified.has(name)) return minified.get(name);

ensureMinifiedNames(next);

var m = minifiedNames[next++];

minified.set(name, m);

return m;

}

// name nodes, ['name', name]

var allNames = [];

// functions, whose element func[1] is the name

var allNamedFunctions = [];

// name arrays, as in func[2], [name1, name2] which are the arguments

var allNameArrays = [];

// var arrays, as in [[name, init], ..] in a var or const

var allVarArrays = [];

// Add instantiate's parameters, but *not* its own name, which is used

// externally.

allNameArrays.push(instantiateFunc[2]);

// First, find all the other things to minify.

instantiateFunc[3].forEach(function(ast) {

traverse(ast, function(node, type) {

if (type === 'defun') {

allNamedFunctions.push(node);

allNameArrays.push(node[2]);

} else if (type === 'function') {

allNameArrays.push(node[2]);

} else if (type === 'var' || type === 'const') {

allVarArrays.push(node[1]);

} else if (type === 'name') {

allNames.push(node);

}

});

});

// All the things that are valid to minify: names declared in vars, or

// params, etc.

var validNames = new Set();

// TODO: sort to find the optimal minification

allVarArrays.forEach(function(array) {

for (var i = 0; i < array.length; i++) {

var name = array[i][0];

validNames.add(name);

array[i][0] = getMinified(name);

}

});

// add all globals in function chunks, i.e. not here but passed to us

for (var i = 0; i < extraInfo.globals.length; i++) {

var name = extraInfo.globals[i];

validNames.add(name);

getMinified(name);

}

allNamedFunctions.forEach(function(node) {

var name = node[1];

validNames.add(name);

node[1] = getMinified(name);

});

allNameArrays.forEach(function(array) {

for (var i = 0; i < array.length; i++) {

var name = array[i];

validNames.add(name);

array[i] = getMinified(name);

}

});

allNames.forEach(function(node) {

var name = node[1];

// A name may refer to a true global like Int8Array, which is not a valid

// name to minify, as we didn't see it declared.

if (validNames.has(name)) {

node[1] = getMinified(name);

}

});

var json = {};

for (var x of minified.entries()) json[x[0]] = x[1];

suffix = '// EXTRA_INFO:' + JSON.stringify(json);

}

// Name minification

var RESERVED = set('do', 'if', 'in', 'for', 'new', 'try', 'var', 'env', 'let', 'case', 'else', 'enum', 'void', 'this', 'void', 'with');

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

}

}

}

function minifyLocals(ast) {

assert(extraInfo && extraInfo.globals);

traverseGeneratedFunctions(ast, function(fun, type) {

// Find the list of local names, including params.

if (asm) {

// TODO: we can avoid modifying at all here - we just need a list of local vars+params

var asmData = normalizeAsm(fun);

denormalizeAsm(fun, asmData);

} else {

// non-asm.js code - scan the whole function, which is inefficient

var localNames = {};

for (var param of fun[2]) {

localNames[param] = 1;

}

traverse(fun, function(node, type) {

if (type === 'var') {

node[1].forEach(function(defn) {

var name = defn[0];

localNames[name] = 1;

});

}

});

}

var newNames = {};

var usedNames = {};

// Find all the globals that we need to minify using

// pre-assigned names. Don't actually minify them yet

// as that might interfere with local variable names.

function isLocalName(name) {

if (asm) {

return name in asmData.vars || name in asmData.params;

} else {

return Object.prototype.hasOwnProperty.call(localNames, name);

}

}

traverse(fun, function(node, type) {

if (type === 'name') {

var name = node[1];

if (!isLocalName(name)) {

var minified = extraInfo.globals[name];

if (minified){

newNames[name] = minified;

usedNames[minified] = 1;

}

}

} else if (type === 'call') {

// We should never call a local name, as in asm.js-style code our

// locals are just numbers, not functions; functions are all declared

// in the outer scope. If a local is called, that is a bug.

if (node[1][0] === 'name') {

var name = node[1][1];

assert(!isLocalName(name), 'cannot call a local');

}

}

});

// The first time we encounter a local name, we assign it a

// minified name that's not currently in use. Allocating on

// demand means they're processed in a predictable order,

// which is very handy for testing/debugging purposes.

var nextMinifiedName = 0;

function getNextMinifiedName() {

var minified;

while (1) {

ensureMinifiedNames(nextMinifiedName);

minified = minifiedNames[nextMinifiedName++];

// TODO: we can probably remove !isLocalName here

if (!usedNames[minified] && !isLocalName(minified)) {

return minified;

}

}

}

// We can also minify loop labels, using a separate namespace

// to the variable declarations.

var newLabels = {};

var nextMinifiedLabel = 0;

function getNextMinifiedLabel() {

ensureMinifiedNames(nextMinifiedLabel);

return minifiedNames[nextMinifiedLabel++];

}

// Traverse and minify all names.

assert(extraInfo.globals.hasOwnProperty(fun[1]));

fun[1] = extraInfo.globals[fun[1]];

assert(fun[1] && typeof fun[1] === 'string');

if (fun[2]) {

for (var i = 0; i < fun[2].length; i++) {

var minified = getNextMinifiedName();

newNames[fun[2][i]] = minified;

fun[2][i] = minified;

}

}

traverse(fun[3], function(node, type) {

if (type === 'name') {

var name = node[1];

var minified = newNames[name];

if (minified) {

node[1] = minified;

} else if (isLocalName(name)) {

minified = getNextMinifiedName();

newNames[name] = minified;

node[1] = minified;

}

} else if (type === 'var') {

node[1].forEach(function(defn) {

var name = defn[0];

if (!(name in newNames)) {

newNames[name] = getNextMinifiedName();

}

defn[0] = newNames[name];

});

} else if (type === 'label') {

if (!newLabels[node[1]]) {

newLabels[node[1]] = getNextMinifiedLabel();

}

node[1] = newLabels[node[1]];

} else if (type === 'break' || type === 'continue') {

if (node[1]) {

node[1] = newLabels[node[1]];

}

}

});

});

}

// Passes table

var minifyWhitespace = false, printMetadata = true, asm = false,

emitJSON = false, last = false,

emitAst = true;

var passes = {

// passes

dumpAst: dumpAst,

dumpSrc: dumpSrc,

minifyGlobals: minifyGlobals,

minifyLocals: minifyLocals,

noop: function() {},

// flags

minifyWhitespace: function() { minifyWhitespace = true },

noPrintMetadata: function() { printMetadata = false },

asm: function() { asm = true },

emitJSON: function() { emitJSON = true },

receiveJSON: function() { }, // handled in a special way, before passes are run

last: function() { last = true },

noEmitAst: function() { emitAst = false },

};

// Main

var suffix = '';

arguments_ = arguments_.filter(function (arg) {

if (!/^--/.test(arg)) return true;

if (arg === '--debug') debug = true;

else throw new Error('Unrecognized flag: ' + arg);

});

var src = read(arguments_[0]);

generatedFunctions = src.lastIndexOf(GENERATED_FUNCTIONS_MARKER) >= 0;

var extraInfoStart = src.lastIndexOf('// EXTRA_INFO:')

if (extraInfoStart > 0) extraInfo = JSON.parse(src.substr(extraInfoStart + 14));

//printErr(JSON.stringify(extraInfo));

var ast;

if (arguments_.indexOf('receiveJSON') < 0) {

ast = srcToAst(src);

} else {

var commentStart = src.indexOf('//');

if (commentStart >= 0) {

src = src.substr(0, commentStart); // JSON.parse will error on a trailing comment

}

ast = JSON.parse(src);

}

//printErr('ast: ' + JSON.stringify(ast));

arguments_.slice(1).forEach(function(arg) {

passes[arg](ast);

});

if (asm && last) {

prepDotZero(ast);

}

if (emitAst) {

if (!emitJSON) {

var js = astToSrc(ast, minifyWhitespace), old;

if (asm && last) {

js = fixDotZero(js);

}

// remove unneeded newlines+spaces, and print

do {

old = js;

js = js.replace(/\n *\n/g, '\n');

} while (js != old);

print(js);

print('\n');

print(suffix);

} else {

print(JSON.stringify(ast));

}

}