simple optimization to allow more registerization inside loops

3 files changed, 62 insertions, 33 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index d1f164d4..ee067a19 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -120,6 +120,7 @@ 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]];
@@ -1169,26 +1170,54 @@ function registerize(ast) {
       }
     });
     vacuum(fun);
-    // Find the # of uses of each variable
+    // 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 varAssigns = {};
+    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 in ASSIGN_OR_ALTER) {
+      } else if (type == 'assign' && typeof node[1] != 'string') {
         if (node[2] && node[2][0] == 'name') {
           var name = node[2][1];
-          if (localVars[name]) {
-            if (!varAssigns[name]) varAssigns[name] = 0;
-            varAssigns[name]++;
+          // 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 = {};
+    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. We use a simple approach of
@@ -1217,7 +1246,7 @@ function registerize(ast) {
       varUses[name]--;
       assert(varUses[name] >= 0);
       if (varUses[name] == 0) {
-        if (loops == 0) {
+        if (loops == 0 || optimizables[name]) {
           // free register
           freeRegs.push(reg);
         } else {
diff --git a/tools/test-js-optimizer-regs-output.js b/tools/test-js-optimizer-regs-output.js
index f038a11c..3a0db393 100644
--- a/tools/test-js-optimizer-regs-output.js
+++ b/tools/test-js-optimizer-regs-output.js
@@ -1,8 +1,8 @@
 function test() {
-  var r1, r2, r3;
+  var r1, r2;
   r1 = 0;
   f(r1);
-  r1++;
+  r1 += 1;
   r2 = r1 + 2;
   g(r1, r2);
   f(r1);
@@ -18,47 +18,47 @@ function test() {
     r2 = 5;
     r1 = 12;
     gg(r2, r1 * 2);
-    r3 = 100;
-    gg(r3, 20);
+    r1 = 100;
+    gg(r1, 20);
   }
-  r3 = f(), r1 = 100, r1 = 1e3, r1 = 1e5;
-  f(r3());
+  r1 = f(), r2 = 100, r2 = 1e3, r2 = 1e5;
+  f(r1());
 }
 function primes() {
-  var r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14;
+  var r1, r2, r3, r4, r5, r6;
   r1 = 2;
   r2 = 0;
   $_$2 : while (1) {
     r3 = r1 | 0;
     r4 = _sqrtf(r3);
-    r5 = 2;
+    r3 = 2;
     $_$4 : while (1) {
-      r6 = r5 | 0;
-      r7 = r6 < r4;
-      if (!r7) {
-        r8 = 1;
+      r5 = r3 | 0;
+      r6 = r5 < r4;
+      if (!r6) {
+        r6 = 1;
         break $_$4;
       }
-      r9 = (r1 | 0) % (r5 | 0);
-      r10 = (r9 | 0) == 0;
-      if (r10) {
-        r8 = 0;
+      r4 = (r1 | 0) % (r3 | 0);
+      r5 = (r4 | 0) == 0;
+      if (r5) {
+        r6 = 0;
         break $_$4;
       }
-      r11 = r5 + 1 | 0;
-      r5 = r11;
+      r5 = r3 + 1 | 0;
+      r3 = r5;
     }
-    r12 = r8 + r2 | 0;
-    r13 = r1 + 1 | 0;
-    r14 = (r12 | 0) < 1e5;
-    if (r14) {
-      r1 = r13;
-      r2 = r12;
+    r5 = r6 + r2 | 0;
+    r3 = r1 + 1 | 0;
+    r4 = (r5 | 0) < 1e5;
+    if (r4) {
+      r1 = r3;
+      r2 = r5;
     } else {
       break $_$2;
     }
   }
-  r12 = _printf(STRING_TABLE.__str | 0, (tempInt = STACKTOP, STACKTOP += 4, HEAP32[tempInt >> 2] = r1, tempInt));
+  r6 = _printf(STRING_TABLE.__str | 0, (tempInt = STACKTOP, STACKTOP += 4, HEAP32[tempInt >> 2] = r1, tempInt));
   return 1;
   return null;
 }
diff --git a/tools/test-js-optimizer-regs.js b/tools/test-js-optimizer-regs.js
index d54ce508..b70ce040 100644
--- a/tools/test-js-optimizer-regs.js
+++ b/tools/test-js-optimizer-regs.js
@@ -1,7 +1,7 @@
 function test() {
   var i = 0;
   f(i);
-  i++;
+  i+=1;
   var j = i + 2;
   g(i, j);
   f(i);