aboutsummaryrefslogtreecommitdiff
path: root/tools
diff options
context:
space:
mode:
Diffstat (limited to 'tools')
-rw-r--r--tools/bisect_pair.py40
-rw-r--r--tools/eliminator/asm-eliminator-test-output.js103
-rw-r--r--tools/eliminator/asm-eliminator-test.js134
-rw-r--r--tools/eliminator/eliminator-test-output.js8
-rw-r--r--tools/eliminator/eliminator-test.js9
-rw-r--r--tools/js-optimizer.js342
-rw-r--r--tools/js_optimizer.py10
-rw-r--r--tools/shared.py9
-rw-r--r--tools/test-js-optimizer-asm-regs-output.js21
-rw-r--r--tools/test-js-optimizer-asm-regs.js24
-rw-r--r--tools/test-js-optimizer-output.js16
-rw-r--r--tools/test-js-optimizer-regs-output.js36
-rw-r--r--tools/test-js-optimizer.js14
13 files changed, 670 insertions, 96 deletions
diff --git a/tools/bisect_pair.py b/tools/bisect_pair.py
index 8eea0d61..cdb76286 100644
--- a/tools/bisect_pair.py
+++ b/tools/bisect_pair.py
@@ -23,9 +23,15 @@ rightf = open('right', 'w')
rightf.write(file2)
rightf.close()
+def run_code(name):
+ ret = run_js(name, stderr=PIPE, full_output=True)
+ # fix stack traces
+ ret = filter(lambda line: not line.startswith(' at ') and not name in line, ret.split('\n'))
+ return '\n'.join(ret)
+
print 'running files'
-left_result = run_js('left', stderr=PIPE)
-right_result = run_js('right', stderr=PIPE) # right as in left-right, not as in correct
+left_result = run_code('left')
+right_result = run_code('right') # right as in left-right, not as in correct
assert left_result != right_result
# Calculate diff chunks
@@ -52,31 +58,31 @@ high = len(chunks)
print 'beginning bisection, %d chunks' % high
for mid in range(high):
- print ' current: %d' % mid
+ print ' current: %d' % mid,
# Take chunks from the middle and on. This is important because the eliminator removes variables, so starting from the beginning will add errors
curr_diff = '\n'.join(map(lambda parts: '\n'.join(parts), chunks[mid:])) + '\n'
difff = open('diff.diff', 'w')
difff.write(curr_diff)
difff.close()
shutil.copy('left', 'middle')
- Popen(['patch', 'middle', 'diff.diff'], stdout=PIPE, stderr=PIPE).communicate()
- result = run_js('middle', stderr=PIPE)
- if result == left_result:
- print 'found where it starts to work: %d' % mid
+ Popen(['patch', 'middle', 'diff.diff'], stdout=PIPE).communicate()
+ shutil.copyfile('middle', 'middle' + str(mid))
+ result = run_code('middle')
+ print result == left_result, result == right_result#, 'XXX', left_result, 'YYY', result, 'ZZZ', right_result
+ if mid == 0:
+ assert result == right_result, '<<< ' + result + ' ??? ' + right_result + ' >>>'
+ print 'sanity check passed (a)'
+ if mid == high-1:
+ assert result == left_result, '<<< ' + result + ' ??? ' + left_result + ' >>>'
+ print 'sanity check passed (b)'
+ if result != right_result:
+ print 'found where it changes: %d' % mid
found = mid
break
-critical = '\n'.join(chunks[found-1]) + '\n'
-
+critical = Popen(['diff', '-U', '5', 'middle' + str(mid-1), 'middle' + str(mid)], stdout=PIPE).communicate()[0]
c = open('critical.diff', 'w')
c.write(critical)
c.close()
-print 'sanity check'
-shutil.copy('middle', 'middle2')
-Popen(['patch', 'middle2', 'critical.diff'], stdout=PIPE, stderr=PIPE).communicate()
-assert run_js('middle', stderr=PIPE) == left_result, 'middle was expected %s' % left_result
-assert run_js('middle2', stderr=PIPE) != left_result, 'middle2 was expected NOT %s' % left_result
-
-print 'middle is like left, middle2 is like right, critical.diff is the difference that matters,'
-print critical
+print 'middle%d is like left, middle%d is like right, critical.diff is the difference that matters' % (mid-1, mid), 'diff:', critical
diff --git a/tools/eliminator/asm-eliminator-test-output.js b/tools/eliminator/asm-eliminator-test-output.js
new file mode 100644
index 00000000..3170bd9c
--- /dev/null
+++ b/tools/eliminator/asm-eliminator-test-output.js
@@ -0,0 +1,103 @@
+function asm(x, y) {
+ x = +x;
+ y = y | 0;
+ var a = 0;
+ a = cheez(y + ~~x | 0) | 0;
+ fleefl(a * a | 0, a | 0);
+}
+function __Z11printResultPiS_j($needle, $haystack, $len) {
+ $needle = $needle | 0;
+ $haystack = $haystack | 0;
+ $len = $len | 0;
+ var $3 = 0, __stackBase__ = 0;
+ __stackBase__ = STACKTOP;
+ $3 = _bsearch($needle, $haystack, $len, 4, 2);
+ if (($3 | 0) == 0) {
+ _puts(_str | 0);
+ STACKTOP = __stackBase__;
+ return;
+ } else {
+ _printf(__str1 | 0, (tempInt = STACKTOP, STACKTOP = STACKTOP + 4 | 0, HEAP32[(tempInt & 16777215) >> 2] = HEAP32[($3 & 16777215) >> 2] | 0, tempInt));
+ STACKTOP = __stackBase__;
+ return;
+ }
+}
+function _segment_holding($addr) {
+ $addr = $addr | 0;
+ var $sp_0 = 0, $3 = 0, $12 = 0, $_0 = 0, label = 0;
+ $sp_0 = __gm_ + 444 | 0;
+ while (1) {
+ $3 = HEAP32[(($sp_0 | 0) & 16777215) >> 2] | 0;
+ if (!($3 >>> 0 > $addr >>> 0)) {
+ if (($3 + (HEAP32[(($sp_0 + 4 | 0) & 16777215) >> 2] | 0) | 0) >>> 0 > $addr >>> 0) {
+ $_0 = $sp_0;
+ label = 1658;
+ break;
+ }
+ }
+ $12 = HEAP32[(($sp_0 + 8 | 0) & 16777215) >> 2] | 0;
+ if (($12 | 0) == 0) {
+ $_0 = 0;
+ label = 1659;
+ break;
+ } else {
+ $sp_0 = $12;
+ }
+ }
+ if (label == 1659) {
+ return $_0;
+ } else if (label == 1658) {
+ return $_0;
+ }
+}
+function __ZN5identC2EiPKcPci($this, $n, $a) {
+ $this = $this | 0;
+ $n = $n | 0;
+ $a = $a | 0;
+ HEAP32[($this & 16777215) >> 2] = __ZTV5ident + 8 | 0;
+ HEAP32[($this + 4 & 16777215) >> 2] = 5;
+ HEAP32[($this + 8 & 16777215) >> 2] = $n;
+ HEAP32[($this + 20 & 16777215) >> 2] = 2147483647;
+ HEAP32[($this + 24 & 16777215) >> 2] = 0;
+ HEAP32[($this + 28 & 16777215) >> 2] = $a;
+ HEAP32[($this + 32 & 16777215) >> 2] = 0;
+ HEAP32[($this + 40 & 16777215) >> 2] = 1;
+ return;
+}
+function _vec2Length($this) {
+ $this = $this | 0;
+ var $__first_addr_i = 0, $__last_addr_i = 0, __stackBase__ = 0;
+ __stackBase__ = STACKTOP;
+ STACKTOP = STACKTOP + 8 | 0;
+ $__first_addr_i = __stackBase__;
+ $__last_addr_i = __stackBase__ + 4;
+ STACKTOP = __stackBase__;
+ return 0;
+}
+function exc($this) {
+ $this = $this | 0;
+ var $1 = 0, $5 = 0;
+ $1 = (function() {
+ try {
+ __THREW__ = false;
+ return __ZNSt3__16locale8__globalEv();
+ } catch (e) {
+ if (typeof e != "number") throw e;
+ if (ABORT) throw e;
+ __THREW__ = true;
+ Module.print("Exception: " + e + ", currently at: " + (new Error).stack);
+ return null;
+ }
+ })();
+ if (!__THREW__) {
+ $5 = HEAP32[(($1 | 0) & 16777215) >> 2] | 0;
+ HEAP32[(($this | 0) & 16777215) >> 2] = $5;
+ __ZNSt3__114__shared_count12__add_sharedEv($5 | 0);
+ return;
+ } else {
+ $8$0 = ___cxa_find_matching_catch(HEAP32[(_llvm_eh_exception.buf & 16777215) >> 2] | 0, HEAP32[(_llvm_eh_exception.buf + 4 & 16777215) >> 2] | 0, []);
+ $8$1 = tempRet0;
+ ___cxa_call_unexpected($8$0);
+ }
+}
+
diff --git a/tools/eliminator/asm-eliminator-test.js b/tools/eliminator/asm-eliminator-test.js
new file mode 100644
index 00000000..ce34a7a6
--- /dev/null
+++ b/tools/eliminator/asm-eliminator-test.js
@@ -0,0 +1,134 @@
+function asm(x, y) {
+ x = +x;
+ y = y|0;
+ var a = 0, b = +0, c = 0;
+ var label = 0;
+ a = cheez((y+~~x)|0)|0;
+ b = a*a;
+ fleefl(b|0, a|0);
+}
+function __Z11printResultPiS_j($needle, $haystack, $len) {
+ $needle = $needle | 0;
+ $haystack = $haystack | 0;
+ $len = $len | 0;
+ var $1 = 0, $2 = 0, $3 = 0, $4 = 0, $puts = 0, $7 = 0, $8 = 0, $9 = 0;
+ var label = 0;
+ var __stackBase__ = 0;
+ __stackBase__ = STACKTOP;
+ $1 = $needle;
+ $2 = $haystack;
+ $3 = _bsearch($1, $2, $len, 4, 2);
+ $4 = ($3 | 0) == 0;
+ if ($4) {
+ $puts = _puts(_str | 0);
+ STACKTOP = __stackBase__;
+ return;
+ } else {
+ $7 = $3;
+ $8 = HEAP32[($7 & 16777215) >> 2] | 0;
+ $9 = _printf(__str1 | 0, (tempInt = STACKTOP, STACKTOP = STACKTOP + 4 | 0, HEAP32[(tempInt & 16777215) >> 2] = $8, tempInt));
+ STACKTOP = __stackBase__;
+ return;
+ }
+}
+function _segment_holding($addr) {
+ $addr = $addr | 0;
+ var $sp_0 = 0, $2 = 0, $3 = 0, $4 = 0, $6 = 0, $7 = 0, $8 = 0, $9 = 0;
+ var $11 = 0, $12 = 0, $13 = 0, $_0 = 0;
+ var label = 0;
+ $sp_0 = __gm_ + 444 | 0;
+ while (1) {
+ $2 = $sp_0 | 0;
+ $3 = HEAP32[($2 & 16777215) >> 2] | 0;
+ $4 = $3 >>> 0 > $addr >>> 0;
+ if (!$4) {
+ $6 = $sp_0 + 4 | 0;
+ $7 = HEAP32[($6 & 16777215) >> 2] | 0;
+ $8 = $3 + $7 | 0;
+ $9 = $8 >>> 0 > $addr >>> 0;
+ if ($9) {
+ $_0 = $sp_0;
+ label = 1658;
+ break;
+ }
+ }
+ $11 = $sp_0 + 8 | 0;
+ $12 = HEAP32[($11 & 16777215) >> 2] | 0;
+ $13 = ($12 | 0) == 0;
+ if ($13) {
+ $_0 = 0;
+ label = 1659;
+ break;
+ } else {
+ $sp_0 = $12;
+ }
+ }
+ if (label == 1659) {
+ return $_0;
+ } else if (label == 1658) {
+ return $_0;
+ }
+}
+function __ZN5identC2EiPKcPci($this, $n, $a) {
+ $this = $this | 0;
+ $n = $n | 0;
+ $a = $a | 0;
+ HEAP32[($this & 16777215) >> 2] = __ZTV5ident + 8 | 0;
+ HEAP32[($this + 4 & 16777215) >> 2] = 5;
+ HEAP32[($this + 8 & 16777215) >> 2] = $n;
+ HEAP32[($this + 20 & 16777215) >> 2] = 2147483647;
+ HEAP32[($this + 24 & 16777215) >> 2] = 0;
+ HEAP32[($this + 28 & 16777215) >> 2] = $a;
+ HEAP32[($this + 32 & 16777215) >> 2] = 0;
+ HEAP32[($this + 40 & 16777215) >> 2] = 1;
+ return;
+}
+function _vec2Length($this) {
+ $this = $this | 0;
+ var $__first_addr_i = 0, $__last_addr_i = 0, $__comp_addr_i = 0, $a13 = 0, $a14 = 0, $a18 = 0, $a19 = 0;
+ var label = 0;
+ var __stackBase__ = 0;
+ __stackBase__ = STACKTOP;
+ STACKTOP = STACKTOP + 8 | 0;
+ $__first_addr_i = __stackBase__;
+ $__last_addr_i = __stackBase__ + 4;
+ $a13 = $__first_addr_i;
+ $a14 = $__last_addr_i;
+ $a18 = $__first_addr_i;
+ $a19 = $__last_addr_i;
+ STACKTOP = __stackBase__;
+ return 0;
+}
+function exc($this) {
+ $this = $this | 0;
+ var $1 = 0, $3 = 0, $4 = 0, $5 = 0, $6 = 0, $8 = +0, $9 = 0;
+ var label = 0;
+ var $1 = (function() {
+ try {
+ __THREW__ = false;
+ return __ZNSt3__16locale8__globalEv();
+ } catch (e) {
+ if (typeof e != "number") throw e;
+ if (ABORT) throw e;
+ __THREW__ = true;
+ Module.print("Exception: " + e + ", currently at: " + (new Error).stack);
+ return null;
+ }
+ })();
+ if (!__THREW__) {
+ $3 = $this | 0;
+ $4 = $1 | 0;
+ $5 = HEAP32[($4 & 16777215) >> 2] | 0;
+ HEAP32[($3 & 16777215) >> 2] = $5;
+ $6 = $5 | 0;
+ __ZNSt3__114__shared_count12__add_sharedEv($6);
+ return;
+ } else {
+ $8$0 = ___cxa_find_matching_catch(HEAP32[(_llvm_eh_exception.buf & 16777215) >> 2] | 0, HEAP32[(_llvm_eh_exception.buf + 4 & 16777215) >> 2] | 0, []);
+ $8$1 = tempRet0;
+ $9 = $8$0;
+ ___cxa_call_unexpected($9);
+ }
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["asm", "__Z11printResultPiS_j", "_segment_holding", "__ZN5identC2EiPKcPci", "_vec2Length", "exc"]
+
diff --git a/tools/eliminator/eliminator-test-output.js b/tools/eliminator/eliminator-test-output.js
index 37a5d104..a005a0a5 100644
--- a/tools/eliminator/eliminator-test-output.js
+++ b/tools/eliminator/eliminator-test-output.js
@@ -6132,6 +6132,14 @@ function _mallocNoU($bytes) {
return $mem_0;
return null;
}
+function asm(x, y) {
+ x = +x;
+ y = y | 0;
+ var a = 0, b = +0;
+ a = cheez(y + ~~x | 0) | 0;
+ b = a * a;
+ fleefl(b | 0, a | 0);
+}
function phi() {
if (wat()) {
var $10 = 1;
diff --git a/tools/eliminator/eliminator-test.js b/tools/eliminator/eliminator-test.js
index 32bb9d5b..13ecab59 100644
--- a/tools/eliminator/eliminator-test.js
+++ b/tools/eliminator/eliminator-test.js
@@ -8828,6 +8828,15 @@ function _mallocNoU($bytes) {
return $mem_0;
return null;
}
+function asm(x, y) { // asm-style code, without special asm requested so will not be fully optimized
+ x = +x;
+ y = y|0;
+ var a = 0, b = +0, c = 0;
+ var label = 0;
+ a = cheez((y+~~x)|0)|0;
+ b = a*a;
+ fleefl(b|0, a|0);
+}
function phi() {
if (wat()) {
var $10 = 1;
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index dbef9c0c..77c48a23 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -263,6 +263,10 @@ function emptyNode() { // XXX do we need to create new nodes here? can't we reus
return ['toplevel', []]
}
+function isEmptyNode(node) {
+ return node.length == 2 && node[0] == 'toplevel' && node[1].length == 0;
+}
+
// Passes
// Dump the AST. Useful for debugging. For example,
@@ -409,7 +413,7 @@ function simplifyExpressionsPre(ast) {
function simplifyBitops(ast) {
var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^');
- var SAFE_BINARY_OPS = set('+', '-', '*', '%'); // division is unsafe as it creates non-ints in JS
+ var SAFE_BINARY_OPS = set('+', '-', '*'); // division is unsafe as it creates non-ints in JS; mod is unsafe as signs matter so we can't remove |0's
var ZERO = ['num', 0];
var rerun = true;
while (rerun) {
@@ -437,6 +441,32 @@ function simplifyExpressionsPre(ast) {
}
}, null, []);
}
+
+ // &-related optimizations
+ traverseGenerated(ast, function(node, type) {
+ if (type == 'binary' && node[1] == '&' && node[3][0] == 'num') {
+ var input = node[2];
+ var amount = node[3][1];
+ if (input[0] == 'binary' && input[1] == '&' && input[3][0] == 'num') {
+ // Collapse X & 255 & 1
+ node[3][1] = amount & input[3][1];
+ node[2] = input[2];
+ } else if (input[0] == 'sub' && input[1][0] == 'name') {
+ // HEAP8[..] & 255 => HEAPU8[..]
+ var name = input[1][1];
+ if (name.substr(0, 4) == 'HEAP') {
+ var unsigned = name[4] == 'U';
+ var bits = parseInt(name.substr(unsigned ? 5 : 4));
+ if (amount == Math.pow(2, bits)-1) {
+ if (!unsigned) {
+ input[1][1] = 'HEAPU' + bits; // make unsigned
+ }
+ return input;
+ }
+ }
+ }
+ }
+ });
}
// The most common mathop is addition, e.g. in getelementptr done repeatedly. We can join all of those,
@@ -1197,14 +1227,163 @@ function loopOptimizer(ast) {
vacuum(ast);
}
+function unVarify(vars, ret) { // transform var x=1, y=2 etc. into (x=1, y=2), i.e., the same assigns, but without a var definition
+ ret = ret || [];
+ ret[0] = 'stat';
+ if (vars.length == 1) {
+ ret[1] = ['assign', true, ['name', vars[0][0]], vars[0][1]];
+ } else {
+ ret[1] = [];
+ 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;
+}
+
+// asm.js support code - normalize (convert asm.js code to 'normal' JS, without
+// annotations, plus explicit metadata) and denormalize (vice versa)
+var ASM_INT = 0;
+var ASM_DOUBLE = 1;
+
+function detectAsmCoercion(node) {
+ // for params, +x vs x|0, for vars, +0 vs 0, so check for "+"
+ return node[0] == 'unary-prefix' ? ASM_DOUBLE : ASM_INT;
+}
+
+function makeAsmParamCoercion(param, type) {
+ return type == ASM_INT ? ['binary', '|', ['name', param], ['num', 0]] : ['unary-prefix', '+', ['name', param]];
+}
+
+function makeAsmVarDef(v, type) {
+ return [v, type == ASM_INT ? ['num', 0] : ['unary-prefix', '+', ['num', 0]]];
+}
+
+function normalizeAsm(func) {
+ //printErr('pre-normalize \n\n' + astToSrc(func) + '\n\n');
+ var data = {
+ params: {}, // ident => ASM_* type
+ vars: {}, // ident => ASM_* type
+ };
+ // process initial params
+ var stats = func[3];
+ var i = 0;
+ while (i < stats.length) {
+ var node = stats[i];
+ if (node[0] != 'stat' || node[1][0] != 'assign' || node[1][2][0] != 'name') break;
+ node = node[1];
+ data.params[node[2][1]] = detectAsmCoercion(node[3]);
+ stats[i] = emptyNode();
+ i++;
+ }
+ // process initial variable definitions
+ outer:
+ while (i < stats.length) {
+ var node = stats[i];
+ if (node[0] != 'var') break;
+ for (var j = 0; j < node[1].length; j++) {
+ var v = node[1][j];
+ var name = v[0];
+ var value = v[1];
+ if (!(name in data.vars)) {
+ assert(value[0] == 'num' || (value[0] == 'unary-prefix' && value[2][0] == 'num')); // must be valid coercion no-op
+ data.vars[name] = detectAsmCoercion(value);
+ v.length = 1; // make an un-assigning var
+ } else {
+ break outer;
+ }
+ }
+ i++;
+ }
+ // finally, look for other var definitions and collect them
+ while (i < stats.length) {
+ traverse(stats[i], function(node, type) {
+ if (type == 'var') {
+ unVarify(node[1], node);
+ } else if (type == 'dot') {
+ if (node[1][0] == 'name' && node[1][1] == 'Math') {
+ // transform Math.max to Math_max; we forward in the latter version
+ node[0] = 'name';
+ node[1] = 'Math_' + node[2];
+ }
+ }
+ });
+ i++;
+ }
+ //printErr('normalized \n\n' + astToSrc(func) + '\n\nwith: ' + JSON.stringify(data));
+ return data;
+}
+
+function denormalizeAsm(func, data) {
+ //printErr('pre-denormalize \n\n' + astToSrc(func) + '\n\nwith: ' + JSON.stringify(data));
+ var stats = func[3];
+ // Remove var definitions, if any
+ for (var i = 0; i < stats.length; i++) {
+ if (stats[i][0] == 'var') {
+ stats[i] = emptyNode();
+ } else {
+ if (!isEmptyNode(stats[i])) break;
+ }
+ }
+ // each param needs a line; reuse emptyNodes as much as we can
+ var numParams = 0;
+ for (var i in data.params) numParams++;
+ var emptyNodes = 0;
+ while (emptyNodes < stats.length) {
+ if (!isEmptyNode(stats[emptyNodes])) break;
+ emptyNodes++;
+ }
+ var neededEmptyNodes = numParams + 1; // params plus one big var
+ if (neededEmptyNodes > emptyNodes) {
+ var args = [0, 0];
+ for (var i = 0; i < neededEmptyNodes - emptyNodes; i++) args[i+2] = 0;
+ stats.splice.apply(stats, args);
+ }
+ // add param coercions
+ var next = 0;
+ func[2].forEach(function(param) {
+ stats[next++] = ['stat', ['assign', true, ['name', param], makeAsmParamCoercion(param, data.params[param])]];
+ });
+ // add variable definitions
+ var varDefs = [];
+ for (var v in data.vars) {
+ varDefs.push(makeAsmVarDef(v, data.vars[v]));
+ }
+ if (varDefs.length) {
+ stats[next] = ['var', varDefs];
+ } else {
+ stats[next] = emptyNode();
+ }
+ //printErr('denormalized \n\n' + astToSrc(func) + '\n\n');
+}
+
// 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) {
+function registerize(ast, asm) {
traverseGeneratedFunctions(ast, function(fun) {
+ if (asm) var asmData = normalizeAsm(fun);
+ // Add parameters as a first (fake) var (with assignment), so they get taken into consideration
+ var params = {}; // note: params are special, they can never share a register between them (see later)
+ if (fun[2] && fun[2].length) {
+ var assign = ['num', 0];
+ fun[3].unshift(['var', fun[2].map(function(param) {
+ params[param] = 1;
+ return [param, assign];
+ })]);
+ }
+ if (asm) {
+ // copy params into vars
+ for (var p in asmData.params) asmData.vars[p] = asmData.params[p];
+ //printErr('fake params: \n\n' + astToSrc(fun) + '\n\n');
+ }
// 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 = {};
@@ -1213,18 +1392,8 @@ function registerize(ast) {
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]]];
+ if (vars.length >= 1) {
+ return unVarify(vars);
} else {
return emptyNode();
}
@@ -1293,7 +1462,7 @@ function registerize(ast) {
// 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 freeRegsClasses = asm ? [[], []] : []; // two classes for asm, one otherwise
var nextReg = 1;
var fullNames = {};
var loopRegs = {}; // for each loop nesting level, the list of bound variables
@@ -1301,18 +1470,24 @@ function registerize(ast) {
var saved = 0;
var activeOptimizables = {};
var optimizableLoops = {};
+ var paramRegs = {}; // true if the register is used by a parameter (and so needs no def at start of function; also cannot
+ // be shared with another param, each needs its own)
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 (asm) assert(name in asmData.vars, name);
+ var freeRegs = asm ? freeRegsClasses[asmData.vars[name]] : freeRegsClasses;
if (!reg) {
// acquire register
- if (optimizables[name] && freeRegs.length > 0) {
+ if (optimizables[name] && freeRegs.length > 0 &&
+ !(params[name] && paramRegs[freeRegs[freeRegs.length-1]])) { // do not share registers between parameters
reg = freeRegs.pop();
saved++;
} else {
reg = nextReg++;
- fullNames[reg] = 'r' + reg; // TODO: even smaller names
+ fullNames[reg] = (asm ? (asmData.vars[name] ? 'd' : 'i') : 'r') + reg; // TODO: even smaller names
+ if (params[name]) paramRegs[reg] = 1;
}
varRegs[name] = reg;
}
@@ -1353,24 +1528,61 @@ function registerize(ast) {
if (type in LOOP) {
// Free registers that were locked to this loop
if (loopRegs[loops]) {
- freeRegs = freeRegs.concat(loopRegs[loops]);
- loopRegs[loops] = [];
+ if (asm) {
+ loopRegs[loops].forEach(function(loopReg) {
+ freeRegsClasses[fullNames[loopReg][0] == 'i' ? ASM_INT : ASM_DOUBLE].push(loopReg);
+ });
+ } else {
+ freeRegsClasses = freeRegsClasses.concat(loopRegs[loops]);
+ }
+ loopRegs[loops].length = 0;
}
loops--;
}
});
- // Add vars at the beginning
- if (nextReg > 1) {
- var vars = [];
+ if (fun[2] && fun[2].length) {
+ fun[2].length = 0; // clear params, we will fill with registers
+ fun[3].shift(); // remove fake initial var
+ }
+ //printErr('var regs: ' + JSON.stringify(varRegs) + '\n\nparam regs: ' + JSON.stringify(paramRegs));
+ if (!asm) {
+ if (nextReg > 1) {
+ var vars = [];
+ for (var i = 1; i < nextReg; i++) {
+ var reg = fullNames[i];
+ if (!paramRegs[i]) {
+ vars.push([reg]);
+ } else {
+ fun[2].push(reg);
+ }
+ }
+ getStatements(fun).unshift(['var', vars]);
+ }
+ } else {
+ //printErr('unfake params: \n\n' + astToSrc(fun) + '\n\n');
+ var finalAsmData = {
+ params: {},
+ vars: {},
+ };
for (var i = 1; i < nextReg; i++) {
- vars.push([fullNames[i]]);
+ var reg = fullNames[i];
+ var type = reg[0] == 'i' ? ASM_INT : ASM_DOUBLE
+ if (!paramRegs[i]) {
+ finalAsmData.vars[reg] = type;
+ } else {
+ finalAsmData.params[reg] = type;
+ fun[2].push(reg);
+ }
}
- getStatements(fun).unshift(['var', vars]);
+ denormalizeAsm(fun, finalAsmData);
}
- //printErr(fun[1] + ': saved ' + saved + ' / ' + (saved + nextReg - 1) + ' vars through registerization'); // not totally accurate
});
}
+function registerizeAsm(ast) {
+ registerize(ast, true);
+}
+
// Eliminator aka Expressionizer
//
// The goal of this pass is to eliminate unneeded variables (which represent one of the infinite registers in the LLVM
@@ -1408,9 +1620,10 @@ var NODES_WITHOUT_ELIMINATION_SIDE_EFFECTS = set('name', 'num', 'string', 'binar
var IGNORABLE_ELIMINATOR_SCAN_NODES = set('num', 'toplevel', 'string', 'break', 'continue', 'dot'); // dot can only be STRING_TABLE.*
var ABORTING_ELIMINATOR_SCAN_NODES = set('new', 'object', 'function', 'defun', 'switch', 'for', 'while', 'array', 'throw'); // we could handle some of these, TODO, but nontrivial (e.g. for while, the condition is hit multiple times after the body)
-function eliminate(ast, memSafe) {
+function eliminate(ast, memSafe, asm) {
// Find variables that have a single use, and if they can be eliminated, do so
traverseGeneratedFunctions(ast, function(func, type) {
+ if (asm) var asmData = normalizeAsm(func);
//printErr('eliminate in ' + func[1]);
// First, find the potentially eliminatable functions: that have one definition and one use
@@ -1418,7 +1631,7 @@ function eliminate(ast, memSafe) {
var uses = {};
var values = {};
var locals = {};
- var varsToRemove = {}; // variables being removed, that we can eliminate all 'var x;' of
+ var varsToRemove = {}; // variables being removed, that we can eliminate all 'var x;' of (this refers to 'var' nodes we should remove)
var varsToTryToRemove = {}; // variables that have 0 uses, but have side effects - when we scan we can try to remove them
// add arguments as locals
if (func[2]) {
@@ -1435,7 +1648,7 @@ function eliminate(ast, memSafe) {
var name = node1i[0];
var value = node1i[1];
if (value) {
- if (!definitions[name]) definitions[name] = 0;
+ if (!(name in definitions)) definitions[name] = 0;
definitions[name]++;
if (!values[name]) values[name] = value;
}
@@ -1450,7 +1663,7 @@ function eliminate(ast, memSafe) {
var target = node[2];
if (target[0] == 'name') {
var name = target[1];
- if (!definitions[name]) definitions[name] = 0;
+ if (!(name in definitions)) definitions[name] = 0;
definitions[name]++;
if (!uses[name]) uses[name] = 0;
if (!values[name]) values[name] = node[3];
@@ -1461,6 +1674,7 @@ function eliminate(ast, memSafe) {
}
});
var potentials = {}; // local variables with 1 definition and 1 use
+ var sideEffectFree = {}; // whether a local variable has no side effects in its definition
for (var name in locals) {
if (definitions[name] == 1 && uses[name] == 1) {
potentials[name] = 1;
@@ -1476,6 +1690,7 @@ function eliminate(ast, memSafe) {
}
if (!hasSideEffects) {
varsToRemove[name] = 1; // remove it normally
+ sideEffectFree[name] = true;
} else {
varsToTryToRemove[name] = 1; // try to remove it later during scanning
}
@@ -1483,10 +1698,11 @@ function eliminate(ast, memSafe) {
}
//printErr('defs: ' + JSON.stringify(definitions));
//printErr('uses: ' + JSON.stringify(uses));
+ //printErr('values: ' + JSON.stringify(values));
//printErr('locals: ' + JSON.stringify(locals));
//printErr('varsToRemove: ' + JSON.stringify(varsToRemove));
- //printErr('2varsToTryToRemove: ' + JSON.stringify(varsToTryToRemove));
- definitions = uses = values = null;
+ //printErr('varsToTryToRemove: ' + JSON.stringify(varsToTryToRemove));
+ definitions = values = null;
//printErr('potentials: ' + JSON.stringify(potentials));
// We can now proceed through the function. In each list of statements, we try to eliminate
var tracked = {};
@@ -1618,6 +1834,12 @@ function eliminate(ast, memSafe) {
invalidateGlobals();
globalsInvalidated = true;
}
+ // if we can track this name (that we assign into), and it has 0 uses and we want to remove its 'var'
+ // definition - then remove it right now, there is no later chance
+ if (allowTracking && (name in varsToRemove) && uses[name] == 0) {
+ track(name, node[3], node);
+ doEliminate(name, node);
+ }
} else {
// replace it in-place
node.length = value.length;
@@ -1772,24 +1994,31 @@ function eliminate(ast, memSafe) {
var info = tracked[name];
delete tracked[name];
var defNode = info.defNode;
- if (defNode[0] == 'var') {
- defNode[1].forEach(function(pair) {
- if (pair[0] == name) {
- value = pair[1];
- }
- });
- assert(value);
- } else { // assign
- value = defNode[3];
- // wipe out the assign
- defNode[0] = 'toplevel';
- defNode[1] = [];
- defNode.length = 2;
- }
- // replace this node in-place
- node.length = 0;
- for (var i = 0; i < value.length; i++) {
- node[i] = value[i];
+ if (!sideEffectFree[name]) {
+ if (defNode[0] == 'var') {
+ defNode[1].forEach(function(pair) {
+ if (pair[0] == name) {
+ value = pair[1];
+ }
+ });
+ assert(value);
+ } else { // assign
+ value = defNode[3];
+ // wipe out the assign
+ defNode[0] = 'toplevel';
+ defNode[1] = [];
+ defNode.length = 2;
+ }
+ // replace this node in-place
+ node.length = 0;
+ for (var i = 0; i < value.length; i++) {
+ node[i] = value[i];
+ }
+ } else {
+ // empty it out in-place
+ node.length = 0;
+ node[0] = 'toplevel';
+ node[1] = [];
}
}
traverse(func, function(block) {
@@ -1812,6 +2041,7 @@ function eliminate(ast, memSafe) {
tracked = {}; // not a var or assign, break all potential elimination so far
}
}
+ //printErr('delete StatBlock');
});
// clean up vars
@@ -1826,6 +2056,13 @@ function eliminate(ast, memSafe) {
}
}
});
+
+ if (asm) {
+ for (var v in varsToRemove) {
+ delete asmData.vars[v];
+ }
+ denormalizeAsm(func, asmData);
+ }
});
// A class for optimizing expressions. We know that it is legitimate to collapse
@@ -1876,6 +2113,10 @@ function eliminateMemSafe(ast) {
eliminate(ast, true);
}
+function eliminateAsm(ast) {
+ eliminate(ast, false, true);
+}
+
// Passes table
var compress = false, printMetadata = true;
@@ -1893,8 +2134,10 @@ var passes = {
hoistMultiples: hoistMultiples,
loopOptimizer: loopOptimizer,
registerize: registerize,
+ registerizeAsm: registerizeAsm,
eliminate: eliminate,
eliminateMemSafe: eliminateMemSafe,
+ eliminateAsm: eliminateAsm,
compress: function() { compress = true; },
noPrintMetadata: function() { printMetadata = false; }
};
@@ -1911,7 +2154,6 @@ if (metadata) setGeneratedFunctions(metadata);
arguments_.slice(1).forEach(function(arg) {
passes[arg](ast);
});
-
var js = astToSrc(ast, compress), old;
// remove unneeded newlines+spaces, and print
diff --git a/tools/js_optimizer.py b/tools/js_optimizer.py
index 3f978605..b72a2084 100644
--- a/tools/js_optimizer.py
+++ b/tools/js_optimizer.py
@@ -54,7 +54,7 @@ def run_on_js(filename, passes, js_engine, jcache):
jcache = False
# If we process only generated code, find that and save the rest on the side
- func_sig = re.compile('function (_[\w$]+)\(')
+ func_sig = re.compile('( *)function (_[\w$]+)\(')
if suffix:
pos = 0
gen_start = 0
@@ -63,12 +63,13 @@ def run_on_js(filename, passes, js_engine, jcache):
m = func_sig.search(js, pos)
if not m: break
pos