unenabled experimental registerization pass in js optimizer

4 files changed, 142 insertions, 0 deletions

diff --git a/tests/runner.py b/tests/runner.py
index 434f71a1..39614139 100755
--- a/tests/runner.py
+++ b/tests/runner.py
@@ -6707,6 +6707,8 @@ f.close()
          ['simplifyExpressionsPre', 'optimizeShiftsConservative']),
         (path_from_root('tools', 'test-js-optimizer-t2.js'), open(path_from_root('tools', 'test-js-optimizer-t2-output.js')).read(),
          ['simplifyExpressionsPre', 'optimizeShiftsAggressive']),
+        (path_from_root('tools', 'test-js-optimizer-regs.js'), open(path_from_root('tools', 'test-js-optimizer-regs-output.js')).read(),
+         ['registerize']),
       ]:
         output = Popen([NODE_JS, JS_OPTIMIZER, input] + passes, stdin=PIPE, stdout=PIPE).communicate()[0]
         self.assertIdentical(expected, output.replace('\n\n', '\n'))
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index b51fe22e..d51c1c18 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -1140,6 +1140,93 @@ function loopOptimizer(ast) {
   vacuum(ast);
 }
 
+// Very simple 'registerization', coalescing of variables into a smaller number.
+function registerize(ast, conservative) {
+  traverseGeneratedFunctions(ast, function(fun) {
+    // Find the # of uses of each variable. The definition is considered a 'use'
+    // First, find all the var definitions
+    var varUses = {};
+    traverse(fun, function(node, type) {
+      if (type == 'var') {
+        node[1].forEach(function(arg) {
+          var name = arg[0];
+          varUses[name] = 1;
+        });
+      }
+    });
+    // Find uses of those variables
+    traverse(fun, function(node, type) {
+      if (type == 'name') {
+        var name = node[1];
+        if (varUses[name]) {
+          varUses[name]++;
+        }
+      }
+    });
+    // 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. We use a simple approach of
+    // locking the register to the topmost loop.
+    var varRegs = {}; // maps variables to the register they will use all their life
+    var freeRegs = [];
+    var nextReg = 1;
+    var fullNames = {};
+    var loopRegs = [];
+    var loops = 0;
+    function decUse(name) {
+      if (!varUses[name]) return varRegs[name]; // no uses left, but still need to replace the name if it has a register
+      var reg = varRegs[name];
+      if (!reg) {
+        // acquire register
+        if (freeRegs.length > 0) {
+          reg = freeRegs.pop();
+        } else {
+          reg = nextReg++;
+          fullNames[reg] = 'r' + reg;
+        }
+        varRegs[name] = reg;
+      }
+      varUses[name]--;
+      assert(varUses[name] >= 0);
+      if (varUses[name] == 0) {
+        if (loops == 0) {
+          // free register
+          freeRegs.push(reg);
+        } else {
+          loopRegs.push(reg);
+        }
+      }
+      return true;
+    }
+    traverse(fun, function(node, type) { // XXX we rely on traversal order being the same as execution order here
+      if (type == 'var') {
+        node[1].forEach(function(arg) {
+          var name = arg[0];
+          if (decUse(name)) {
+            arg[0] = fullNames[varRegs[name]];
+          }
+        });
+      } else if (type == 'name') {
+        var name = node[1];
+        if (decUse(name)) {
+          node[1] = fullNames[varRegs[name]];
+        }
+      } else if (type in LOOP) {
+        loops++;
+      }
+    }, function(node, type) {
+      if (type in LOOP) {
+        loops--;
+        if (loops == 0 && loopRegs.length > 0) {
+          freeRegs = freeRegs.concat(loopRegs);
+          loopRegs = [];
+        }
+      }
+    });
+  });
+  //printErr('zz post: ' + dump(ast));
+}
+
 // Passes table
 
 var compress = false;
@@ -1156,6 +1243,7 @@ var passes = {
   simplifyExpressionsPost: simplifyExpressionsPost,
   hoistMultiples: hoistMultiples,
   loopOptimizer: loopOptimizer,
+  registerize: registerize,
   compress: function() { compress = true; }
 };
 
diff --git a/tools/test-js-optimizer-regs-output.js b/tools/test-js-optimizer-regs-output.js
new file mode 100644
index 00000000..30b504be
--- /dev/null
+++ b/tools/test-js-optimizer-regs-output.js
@@ -0,0 +1,26 @@
+function test() {
+  var r1 = 0;
+  f(r1);
+  r1++;
+  var r2 = r1 + 2;
+  g(r1, r2);
+  f(r1);
+  var r1 = cheez();
+  var r2 = r1 + 2;
+  g(r2, r2);
+  var r2 = 200;
+  var r2 = 203;
+  var r2 = 205;
+  var r1 = 208;
+  c(r2);
+  while (f()) {
+    var r2 = 5;
+    var r1 = 12;
+    gg(r2, r1 * 2);
+    var r3 = 100;
+    gg(r3, 20);
+  }
+  var r3 = f(), r1 = 100, r1 = 1e3, r1 = 1e5;
+  f(r3());
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["test"]
diff --git a/tools/test-js-optimizer-regs.js b/tools/test-js-optimizer-regs.js
new file mode 100644
index 00000000..2be4ee6a
--- /dev/null
+++ b/tools/test-js-optimizer-regs.js
@@ -0,0 +1,26 @@
+function test() {
+  var i = 0;
+  f(i);
+  i++;
+  var j = i + 2;
+  g(i, j);
+  f(i);
+  var i2 = cheez();
+  var j2 = i2 + 2;
+  g(j2, j2);
+  var k1 = 200;
+  var k2 = 203;
+  var k3 = 205;
+  var k4 = 208;
+  c(k3);
+  while (f()) {
+    var apple = 5;
+    var orange = 12;
+    gg(apple, orange*2);
+    var tangerine = 100;
+    gg(tangerine, 20);
+  }
+  var ck = f(), ck2 = 100, ck3 = 1000, ck4 = 100000;
+  f(ck());
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["test"]