Reduce memory usage when assigning registers in a block.

Rather than pre-calculating liveness states and then processing nodes
in execution order, we process nodes in reverse execution order and
use the liveness info implicit in this traversal.  Names are assigned
a register when they're used for the first time, and the register is
freed when we reach an assignment.

1 files changed, 84 insertions, 79 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index b35da99d..78676681 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -2711,6 +2711,7 @@ function registerizeHarder(ast) {
       var link = {};
       var lastUseLoc = {};
       var firstDeadLoc = {};
+      var firstKillLoc = {};
       var lastKillLoc = {};
       for (var name in live) {
         link[name] = name;
@@ -2735,6 +2736,7 @@ function registerizeHarder(ast) {
             delete use[name];
             delete live[name];
             firstDeadLoc[name] = j;
+            firstKillLoc[name] = j;
             if (lastUseLoc[name] === undefined) {
               lastUseLoc[name] = j;
             }
@@ -2760,6 +2762,9 @@ function registerizeHarder(ast) {
               for (var name in lastUseLoc) {
                 lastUseLoc[name] -= n;
               }
+              for (var name in firstKillLoc) {
+                firstKillLoc[name] -= n;
+              }
               for (var name in lastKillLoc) {
                 lastKillLoc[name] -= n;
               }
@@ -2791,6 +2796,7 @@ function registerizeHarder(ast) {
       block.link = link;
       block.lastUseLoc = lastUseLoc;
       block.firstDeadLoc = firstDeadLoc;
+      block.firstKillLoc = firstKillLoc;
       block.lastKillLoc = lastKillLoc;
     }
 
@@ -2975,47 +2981,41 @@ function registerizeHarder(ast) {
       if (block.nodes.length === 0) continue;
       var jEnter = junctions[block.entry];
       var jExit = junctions[block.exit];
-      // Calculate the full internal liveness states for this block.
-      var liveness = [{}];
-      for (var name in jExit.live) {
-        liveness[0][name] = 1;
-      }
-      for (var j=block.nodes.length-1; j>=0; j--) {
-        var node = block.nodes[j];
-        liveness.unshift(copy(liveness[0]));
-        if (node[0] === 'assign') {
-          var name = node[2][1];
-          delete liveness[0][name];
-        } else if (node[0] === 'name') {
-          var name = node[1];
-          liveness[0][name] = 1;
-        } else {
-          assert(false, 'unexpected node type: ' + node[0]);
-        }
-      }
-      assert(liveness.length == block.nodes.length + 1);
-      assert(setSize(setSub(liveness[0], jEnter.live)) == 0);
-      // Mark the point at which each output reg gets assigned.
-      // Variables that live past this point must not be assigned
+      // Mark the point at which each input reg becomes dead.
+      // Variables alive before this point must not be assigned
       // to that register.
-      var outputAssignLoc = {};
-      var outputVars = {};
+      var inputVars = {}
+      var inputDeadLoc = {};
+      var inputVarsByReg = {};
       for (var name in jExit.live) {
-        var reg = junctionVariables[name].reg;
-        assert(reg !== null, 'output variable doesnt have a register');
-        outputAssignLoc[reg] = block.lastKillLoc[name];
-        outputVars[reg] = name;
-      }
-      // Scan through in execution order, allocating registers on demand.
-      // Be careful to avoid conflicts with the output registers.
+        if (!(name in block.kill)) {
+          inputVars[name] = 1;
+          var reg = junctionVariables[name].reg;
+          assert(reg !== null, 'input variable doesnt have a register');
+          inputDeadLoc[reg] = block.firstDeadLoc[name];
+          inputVarsByReg[reg] = name;
+        }
+      }
+      for (var name in block.use) {
+        if (!(name in inputVars)) {
+          inputVars[name] = 1;
+          var reg = junctionVariables[name].reg;
+          assert(reg !== null, 'input variable doesnt have a register');
+          inputDeadLoc[reg] = block.firstDeadLoc[name];
+          inputVarsByReg[reg] = name;
+        }
+      }
+      assert(setSize(setSub(inputVars, jEnter.live)) == 0);
+      // Scan through backwards, allocating registers on demand.
+      // Be careful to avoid conflicts with the input registers.
       // We consume free registers in last-used order, which helps to
       // eliminate "x=y" assignments that are the last use of "y".
       var assignedRegs = {};
       var freeRegsByType = copy(allRegsByType);
-      // Begin with all live vars assigned per the entry-point.
-      for (var name in liveness[0]) {
+      // Begin with all live vars assigned per the exit junction.
+      for (var name in jExit.live) {
         var reg = junctionVariables[name].reg;
-        assert(reg !== null, 'input variable doesnt have a register');
+        assert(reg !== null, 'output variable doesnt have a register');
         assignedRegs[name] = reg;
         delete freeRegsByType[localVars[name]][reg];
       }
@@ -3023,66 +3023,71 @@ function registerizeHarder(ast) {
         freeRegsByType[j] = keys(freeRegsByType[j]);
       }
       // Scan through the nodes in sequence, modifying each node in-place
-      // and freeing registers according to the calculated liveness info.
-      for (var j = 0; j < block.nodes.length; j++) {
+      // and grabbing/freeing registers as needed.
+      var maybeRemoveNodes = [];
+      for (var j = block.nodes.length - 1; j >= 0; j--) {
         var node = block.nodes[j];
         var name = node[0] === 'assign' ? node[2][1] : node[1];
         var allRegs = allRegsByType[localVars[name]];
         var freeRegs = freeRegsByType[localVars[name]];
         var reg = assignedRegs[name];
         if (node[0] === 'name') {
-          // A use.  It should already be in a register.
-          assert(liveness[j][name], 'use node, but name was not alive?')
-          assert(reg, 'live variable did not have a reg?')
-          node[1] = allRegs[reg];
-        } else {
-          // A kill. This should assign it a new register.
-          assert(!liveness[j][name], 'kill node, but name was alive?')
-          assert(!reg, 'non-live variable still had a reg?')
-          if (name in jExit.live && j === block.lastKillLoc[name]) {
-            // Assignment to an output variable, must use pre-assigned reg.
-            reg = junctionVariables[name].reg;
-            assignedRegs[name] = reg;
-            for (var k = freeRegs.length - 1; k >= 0; k--) {
-              if (freeRegs[k] === reg) {
+          // A use.  Grab a register if it doesn't have one.
+          if (!reg) {
+            if (name in inputVars && j <= block.firstDeadLoc[name]) {
+              // Assignment to an input variable, must use pre-assigned reg.
+              reg = junctionVariables[name].reg;
+              assignedRegs[name] = reg;
+              for (var k = freeRegs.length - 1; k >= 0; k--) {
+                if (freeRegs[k] === reg) {
+                  freeRegs.splice(k, 1);
+                  break;
+                }
+              }
+            } else {
+              // Try to use one of the existing free registers.
+              // It must not conflict with an input register.
+              for (var k = freeRegs.length - 1; k >= 0; k--) {
+                reg = freeRegs[k];
+                // Check for conflict with input registers.
+                if (block.firstKillLoc[name] <= inputDeadLoc[reg]) {
+                  if (name !== inputVarsByReg[reg]) {
+                    continue;
+                  }
+                }
+                // Found one!
+                assignedRegs[name] = reg;
                 freeRegs.splice(k, 1);
                 break;
               }
-            }
-          } else {
-            // Try to use one of the existing free registers.
-            // It must not conflict with an output register.
-            for (var k = freeRegs.length - 1; k >= 0; k--) {
-              reg = freeRegs[k];
-              // Check for conflict with output registers.
-              if (block.lastUseLoc[name] > outputAssignLoc[reg]) {
-                if (name !== outputVars[reg]) {
-                  continue;
-                }
+              // If we didn't find a suitable register, create a new one.
+              if (!assignedRegs[name]) {
+                reg = createReg(name);
+                assignedRegs[name] = reg;
               }
-              // Found one!
-              assignedRegs[name] = reg;
-              freeRegs.splice(k, 1);
-              break;
-            }
-            // If we didn't find a suitable register, create a new one.
-            if (!assignedRegs[name]) {
-              reg = createReg(name);
-              assignedRegs[name] = reg;
             }
           }
-          // Modify assignment to use the new name.
-          // If we happen to create a "x=x" type do-nothing assignment,
-          // we can safely morph it into a no-op.
+          node[1] = allRegs[reg];
+        } else {
+          // A kill. This frees the assigned register.
+          assert(reg, 'live variable doesnt have a reg?')
           node[2][1] = allRegs[reg];
-          if (node[3][0] === 'name' && node[3][1] === node[2][1]) {
-            morphNode(node, ['block', []]);
+          freeRegs.push(reg);
+          delete assignedRegs[name];
+          if (node[3][0] === 'name' && node[3][1] in localVars) {
+            maybeRemoveNodes.push([j, node]);
           }
         }
-        // Free the reg if it's not live in the next step.
-        if (!liveness[j+1][name]) {
-          delete assignedRegs[name];
-          freeRegs.push(reg);
+      }
+      // If we managed to create an "x=x" assignments, remove them.
+      for (var j = 0; j < maybeRemoveNodes.length; j++) {
+        var node = maybeRemoveNodes[j][1];
+        if (node[2][1] === node[3][1]) {
+          if (block.isexpr[maybeRemoveNodes[j][0]]) {
+            morphNode(node, node[2]);
+          } else {
+            morphNode(node, ['block', []]);
+          }
         }
       }
     }