rewrite of eliminator to better approach

1 files changed, 211 insertions, 413 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index b84b2b7c..569d8eca 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -1,8 +1,12 @@
 //==============================================================================
-//  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. Some of the modifications also work in
-//  conjunction with closure compiler.
+// 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. Some of the modifications also work in
+// conjunction with closure compiler.
+//
+// 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?
 //==============================================================================
 
 // *** Environment setup code ***
@@ -250,7 +254,7 @@ function traverseWithVariables(ast, callback) {
   }, []);
 }
 
-function emptyNode() {
+function emptyNode() { // XXX do we need to create new nodes here? can't we reuse?
   return ['toplevel', []]
 }
 
@@ -1360,421 +1364,238 @@ function registerize(ast) {
 }
 
 function eliminate(ast) {
-  /*
-    A script to eliminate redundant variables common in Emscripted code.
-
-    A variable === eliminateable if (it matches a leaf of that condition tree:
-
-    Single-def
-      Uses only side-effect-free nodes
-        Unused
-          *
-        Has at most MAX_USES uses
-          No mutations to any dependencies between def && last use
-            No global dependencies or no indirect accesses between def && use
-              *
-
-    TODO(max99x): Eliminate single-def undefined-initialized vars with no uses
-                  between declaration && definition.
-  */
-
-  // Maximum number of uses to consider a variable not worth eliminating.
-  // The risk with using > 1 === that a variable used by another can have
-  // a chain that leads to exponential uses
-  var MAX_USES = 1;
-
-  // The UglifyJs code generator settings to use.
-  var GEN_OPTIONS = {
-    ascii_only: true,
-    beautify: true,
-    indent_level: 2
-  };
-
-  // Node types which can be evaluated without side effects.
-  var NODES_WITHOUT_SIDE_EFFECTS = {
-    name: true,
-    sname: true,
-    num: true,
-    string: true,
-    binary: true,
-    sub: true,
-    'unary-prefix': true // ++x can have side effects, but we never have that in generated code
-  };
-
-  // Nodes which may break control flow. Moving a variable beyond them may have
-  // side effects.
-  var CONTROL_FLOW_NODES = {
-    new: true,
-    throw: true,
-    call: true,
-    label: true,
-    debugger: true,
-    seq: true
-  };
-
-  var ANALYZE_BLOCK_TYPES = {
-    'switch': true,
-    'if': true,
-    'try': true,
-    'do': true,
-    'while': true,
-    'for': true,
-    'for-in': true
-  };
-
-  // Traverses a JavaScript syntax tree rooted at the given node calling the given
-  // callback for each node.
-  //   that.arg node: The root of the AST.
-  //   that.arg callback: The callback to call for each node. This will be called with
-  //     the node as the first argument && its type as the second. If false is
-  //     returned, the traversal === stopped. If a non-undefined value === returned,
-  //     it replaces the passed node in the tree.
-  //   that.returns: If the root node was replaced, the new root node. If the traversal
-  //     was stopped, false. Otherwise undefined.
-  function traverse(node, callback) {
-    var type = node[0];
-    if (typeof type == 'string') {
-      result = callback(node, type);
-      if (result) return result;
-    }
-    for (var index = 0; index < node.length; index++) {
-      var subnode = node[index];
-      if (subnode && typeof subnode == 'object' && subnode.length) {
-        // NOTE: For-in nodes have unspecified var mutations. Skip them.
-        if (type == 'for-in' && subnode[0] == 'var') continue;
-        var subresult = traverse(subnode, callback);
-        if (subresult === false) {
-          return false;
-        } else if (subresult) {
-          node[index] = subresult;
-        }
+  // Find variables that have a single use, and if they can be eliminated, do so
+  traverseGeneratedFunctions(ast, function(func, type) {
+    // 'hide' X in X[10] so we don't get confused by it - these do not matter to variable effects
+    traverse(func, function(node, type) {
+      if (type === 'sub' && node[1][0] == 'name') {
+        node[1][0] = 'sname';
       }
-    }
-  }
+    });
 
-  // A class for eliminating redundant variables from JavaScript. Give it an AST
-  // function/defun node && call run() to apply the optimization (in-place).
-  var that = that; // there is always a single global Eliminator instance
-  function Eliminator(func) {
-    that = this;
-    // The statements of the function to analyze.
-    this.body = func[3];
-
-    // Identifier stats. Each of these objects === indexed by the identifier name.
-    // Whether the identifier === a local variable.
-    this.isLocal = {};
-    // Whether the identifier === never modified after initialization.
-    this.isSingleDef = {};
-    // How many times the identifier === used.
-    this.useCount = {};
-    // Whether the initial value of a single-def identifier uses only nodes
-    // evaluating which has no side effects.
-    this.usesOnlySimpleNodes = {};
-    // Whether the identifier depends on any non-local name, perhaps indirectly.
-    this.dependsOnAGlobal = {};
-    // Whether the dependencies of the single-def identifier may be mutated
-    // within its live range.
-    this.depsMutatedInLiveRange = {};
-    // Maps a given single-def variable to the AST expression of its initial value.
-    this.initialValue = {};
-    // Maps identifiers to single-def variables which reference it in their
-    // initial value, i.e., which other variables it affects.
-    this.affects = {};
-
-    // Runs the eliminator on a given function body updating the AST in-place.
-    //   that.returns: The number of variables eliminated, or undefined if (skipped.
-    this.run = function() {
-      this.calculateBasicVarStats();
-      this.analyzeInitialValues();
-      this.calculateTransitiveDependencies();
-      this.analyzeLiveRanges();
-
-      var toReplace = {};
-      var eliminated = 0;
-      for (var varName in this.isSingleDef) {
-        if (this.isEliminateable(varName)) {
-          toReplace[varName] = this.initialValue[varName];
-          eliminated++;
+    // First, find the potentially eliminatable functions: that have one definition and one use
+    var definitions = {};
+    var uses = {};
+    var locals = {};
+    traverse(func, function(node, type) {
+      if (type === 'var') {
+        var node1 = node[1];
+        for (var i = 0; i < node1.length; i++) {
+          var node1i = node1[i];
+          var name = node1i[0];
+          var value = node1i[1];
+          if (value) {
+            if (!definitions[name]) definitions[name] = 0;
+            definitions[name]++;
+          }
+          if (!uses[name]) uses[name] = 0;
+          locals[name] = true;
+        }
+      } else if (type === 'name') {
+        var name = node[1];
+        if (!uses[name]) uses[name] = 0;
+        uses[name]++;
+      } else if (type == 'assign') {
+        var target = node[2];
+        if (target[0] == 'name') {
+          var name = target[1];
+          if (!definitions[name]) definitions[name] = 0;
+          definitions[name]++;
+          if (!uses[name]) uses[name] = 0;
+          if (node[1] === true) { // not +=, -= etc., just =
+            uses[name]--; // because the name node will show up by itself in the previous case
+          }
         }
       }
-
-      this.removeDeclarations(toReplace);
-      this.collapseValues(toReplace);
-      this.updateUses(toReplace);
-
-      return eliminated;
-    };
-
-    // Runs the basic variable scan pass. Fills the following member variables:
-    //   isLocal
-    //   isSingleDef
-    //   useCount
-    //   initialValue
-    this.calculateBasicVarStats = function() {
-      traverse(this.body, function(node, type) {
-        if (type === 'var') {
-          var node1 = node[1];
-          for (var i = 0; i < node1.length; i++) {
-            var node1i = node1[i];
-            var varName = node1i[0];
-            var varValue = node1i[1];
-            that.isLocal[varName] = true;
-            if (!varValue) varValue = ['name', 'undefined']; // XXX share?
-            that.isSingleDef[varName] = !that.isSingleDef.hasOwnProperty(varName);
-            that.initialValue[varName] = varValue;
-            that.useCount[varName] = 0;
+    });
+    var potentials = {}; // local variables with 1 definition and 1 use
+    for (var name in locals) {
+      if (definitions[name] == 1 && uses[name] == 1) {
+        potentials[name] = 1;
+      }
+    }
+    //printErr('defs: ' + JSON.stringify(definitions));
+    //printErr('uses: ' + JSON.stringify(uses));
+    //printErr('locals: ' + JSON.stringify(locals));
+    definitions = uses = null;
+    //printErr('potentials: ' + JSON.stringify(potentials));
+    // We can now proceed through the function. In each list of statements, we try to eliminate
+    var tracked = {};
+    function track(name, value, defNode) { // add a potential that has just been defined to the tracked list, we hope to eliminate it
+      var usesGlobals = false, usesMemory = false;
+      traverse(defNode, function(node, type) {
+        if (type == 'name') {
+          if (!(node[1] in locals)) {
+            usesGlobals = true;
           }
-        } else if (type === 'name') {
-          varName = node[1];
-          if (that.useCount.hasOwnProperty(varName)) that.useCount[varName]++;
-          else that.isSingleDef[varName] = false;
-        } else if (type == 'assign') {
-          varName = node[2][1];
-          if (that.isSingleDef[varName]) that.isSingleDef[varName] = false;
+        } else if (type == 'sub') {
+          usesMemory = true;
+        } else if (type == 'call') {
+          usesGlobals = true;
+          usesMemory = true;
         }
       });
-    };
-
-    // Analyzes the initial values of single-def variables. Requires basic variable
-    // stats to have been calculated. Fills the following member variables:
-    //   affects
-    //   dependsOnAGlobal
-    //   usesOnlySimpleNodes
-    this.analyzeInitialValues = function() {
-      for (var varName in this.isSingleDef) {
-        if (!this.isSingleDef[varName]) continue;
-        this.usesOnlySimpleNodes[varName] = true;
-        traverse(this.initialValue[varName], function(node, type) {
-          if (!(type in NODES_WITHOUT_SIDE_EFFECTS)) {
-            that.usesOnlySimpleNodes[varName] = false;
-          } else if (type === 'name') {
-            var reference = node[1];
-            if (reference != 'undefined') {
-              if (!that.affects[reference]) that.affects[reference] = {};
-              if (!that.isLocal[reference]) that.dependsOnAGlobal[varName] = true;
-              that.affects[reference][varName] = true;
-            }
-          }
-        });
+      tracked[name] = {
+        usesGlobals: usesGlobals,
+        usesMemory: usesMemory,
+        defNode: defNode
+      };
+      //printErr('track ' + [name, JSON.stringify(tracked[name])]);
+    }
+    var temp = [];
+    var needGlobalsInvalidated = false;
+    var needMemoryInvalidated = false;
+    function invalidateGlobals() {
+      //printErr('invalidate globals');
+      temp.length = [];
+      for (var name in tracked) {
+        var info = tracked[name];
+        if (info.usesGlobals) {
+          temp.push(name);
+        }
       }
-    };
-
-    // Updates the dependency graph (@affects) to its transitive closure && 
-    // synchronizes this.dependsOnAGlobal to the new dependencies.
-    this.calculateTransitiveDependencies = function() {
-      var incomplete = true;
-      var todo = {};
-      for (var element in this.affects) {
-        todo[element] = 1;
+      for (var i = 0; i < temp.length; i++) {
+        delete tracked[temp[i]];
       }
-
-      //process.stdout.write 'pre ' + JSON.stringify(@affects, null, '  ') + '\n'
-
-      while (incomplete) {
-        incomplete = false;
-        var nextTodo = {};
-        for (var source in this.affects) {
-          var targets = this.affects[source];
-          for (var target in targets) {
-            if (todo[target]) {
-              var this_affects_target = this.affects[target];
-              for (target2 in this_affects_target) {
-                if (!targets[target2]) {
-                  if (!this.isLocal[source]) this.dependsOnAGlobal[target2] = true;
-                  targets[target2] = true;
-                  nextTodo[source] = 1;
-                  incomplete = true;
-                }
-              }
-            }
-          }
+    }
+    function invalidateMemory() {
+      //printErr('invalidate memory');
+      temp.length = [];
+      for (var name in tracked) {
+        var info = tracked[name];
+        if (info.usesMemory) {
+          temp.push(name);
         }
-        todo = nextTodo;
       }
-
-      //process.stdout.write 'post ' + JSON.stringify(@affects, null, '  ') + '\n'
-    };
-
-    // Analyzes the live ranges of single-def variables. Requires dependencies to
-    // have been calculated. Fills the following member variables:
-    //   depsMutatedInLiveRange
-    this.analyzeLiveRanges = function() {
-      var isLive = {};
-
-      // Checks if (a given node may mutate any of the currently live variables.
-      function checkForMutations(node, type) {
-        var usedInThisStatement = {};
-        if (type == 'assign' || type == 'call') {
-          traverse(node.slice(2, 4), function(node, type) {
-            if (type === 'name') usedInThisStatement[node[1]] = true;
-          });
+      for (var i = 0; i < temp.length; i++) {
+        delete tracked[temp[i]];
+      }
+    }
+    function check(node) { // checks a potential (var/assign) node for things that affect elimination. returns if ok to process this node
+      //printErr('check ' + JSON.stringify(node));
+      var ok = true;
+      needGlobalsInvalidated = false;
+      needMemoryInvalidated = false;
+      traverse(node, function(node, type) {
+        if (type == 'assign') {
+          if (node[2][0] == 'name' && !(node[2][1] in locals)) {
+            needGlobalsInvalidated = true;
+          } else if (node[2][0] == 'sub') {
+            needMemoryInvalidated = true;
+          }
+        } else if (type == 'call') {
+          needGlobalsInvalidated = true;
+          needMemoryInvalidated = true;
+        } else if (type == 'seq') {
+          tracked = {};
+          ok = false;
+          return true;
         }
-
-        if (type == 'assign' || type == 'unary-prefix' || type == 'unary-postfix') {
-          if (type === 'assign' || node[1] == '--' || node[1] == '++') {
-            var reference = node[2];
-            while (reference[0] != 'name' && reference[0] != 'sname') {
-              reference = reference[1];
-            }
-            reference = reference[1];
-            var aff = that.affects[reference]
-            if (aff) {
-              for (var varName in aff) {
-                if (isLive[varName]) {
-                  isLive[varName] = false;
+      });
+      return ok;
+    }
+    var varsToRemove = {}; // must remove vars in a post pass; there can be multiple 'var x;' for an x.
+    function tryEliminate(node) { // it is ok to try to eliminate on this node, try all currently tracked
+      //printErr('tryelim ' + JSON.stringify(node));
+      traverse(node, function(node, type) {
+        if (type == 'name') {
+          var name = node[1];
+          if (name in tracked) {
+            //printErr('elim!!!!! ' + name);
+            // yes, eliminate!
+            varsToRemove[name] = 1; // both assign and var definitions can have other vars we must clean up
+            var info = tracked[name];
+            delete tracked[name];
+            var defNode = info.defNode;
+            if (defNode[0] == 'var') {
+              var value;
+              defNode[1].forEach(function(pair) {
+                if (pair[0] == name) {
+                  value = pair[1];
                 }
-              }
+              });
+              assert(value);
+              return value;
+            } else { // assign
+              var value = defNode[3];
+              // wipe out the assign
+              defNode[0] = 'toplevel';
+              defNode[1] = [];
+              defNode.length = 2;
+              return value;
             }
           }
         }
-
-        if (type in CONTROL_FLOW_NODES) {
-          for (var varName in isLive) {
-            if (that.dependsOnAGlobal[varName] || !usedInThisStatement[varName]) {
-              isLive[varName] = false;
-            }
-          }
-        } else if (type === 'assign') {
-          for (var varName in isLive) {
-            if (that.dependsOnAGlobal[varName] && !usedInThisStatement[varName]) {
-              isLive[varName] = false;
-            }
-          }
-        } else if (type === 'name') {
-          var reference = node[1];
-          if (that.isSingleDef[reference]) {
-            if (!isLive[reference]) {
-              that.depsMutatedInLiveRange[reference] = true;
-            }
-          }
+      });
+    }
+    traverse(func, function(block) {
+      var stats = getStatements(block);
+      if (!stats) return;
+      tracked = {};
+      for (var i = 0; i < stats.length; i++) {
+        var node = stats[i];
+        var type = node[0];
+        //printErr('line ' + i + ' : ' + JSON.stringify(node));
+        if (type == 'stat') {
+          node = node[1];
+          type = node[0];
         }
-      }
-
-      // Analyzes a block && all its children for variable ranges. Makes sure to
-      // account for the worst case of possible mutations.
-      function analyzeBlock(node, type) {
-        if (type in ANALYZE_BLOCK_TYPES) {
-          function traverseChild(child) {
-            if (child && typeof child == 'object' && child.length) {
-              var savedLive = {};
-              for (var name in isLive) savedLive[name] = true;
-              traverse(child, analyzeBlock);
-              for (var name in isLive) {
-                if (!isLive[name]) savedLive[name] = false;
+        // Check for things that affect elimination
+        if (type == 'var' || type == 'assign' || type == 'call') {
+          // can we eliminate and/or track?
+          if (!check(node)) continue;
+          // try to eliminate
+          tryEliminate(node);
+          // apply invalidations from the check (after elimination - they affect the future, not the present)
+          if (needGlobalsInvalidated) invalidateGlobals();
+          if (needMemoryInvalidated) invalidateMemory();
+          // try to track
+          if (type == 'var') {
+            var node1 = node[1];
+            for (var j = 0; j < node1.length; j++) {
+              var node1j = node1[j];
+              var name = node1j[0];
+              var value = node1j[1];
+              if (value && (name in potentials)) {
+                track(name, value, node);
               }
-              isLive = savedLive;
-            }
-          }
-          if (type === 'switch') {
-            traverseChild(node[1]);
-            var node2 = node[2];
-            for (var i = 0; i < node2.length; i++) {
-              traverseChild(node2[i]);
             }
-          } else if (type == 'if' || type == 'try') {
-            for (var i = 0; i < node.length; i++) {
-              traverseChild(node[i]);
-            }
-          } else {
-            // Don't put anything from outside into the body of a loop.
-            isLive = {};
-            node.forEach(traverseChild);
-            // Don't keep anything alive through a loop
-            isLive = {};
-          }
-          return node;
-        }  else if (type === 'var') {
-          var node1 = node[1];
-          for (var i = 0; i < node1.length; i++) {
-            var node1i = node1[i];
-            var varName = node1i[0];
-            var varValue = node1i[1];
-            if (varValue) traverse(varValue, checkForMutations);
-            // Mark the variable as live
-            if (that.isSingleDef[varName]) {
-              isLive[varName] = true;
-            }
-            // Mark variables that depend on it as no longer live
-            if (that.affects[varName]) {
-              var aff = that.affects[varName];
-              for (var varNameDep in aff) {
-                if (isLive[varNameDep]) {
-                  isLive[varNameDep] = false;
-                }
+          } else if (type == 'assign') {
+            if (node[1] === true && node[2][0] == 'name') {
+              var name = node[2][1];
+              if (name in potentials) {
+                track(name, node[3], node);
               }
             }
           }
-          return node;
         } else {
-          checkForMutations(node, type);
+          tracked = {}; // not a var or assign, break all potential elimination so far
         }
       }
+    });
 
-      traverse(this.body, analyzeBlock);
-    };
-
-    // Determines whether a given variable can be safely eliminated. Requires all
-    // analysis passes to have been run.
-    this.isEliminateable = function(varName) {
-      if (this.isSingleDef[varName] && this.usesOnlySimpleNodes[varName]) {
-        if (this.useCount[varName] == 0) {
-          return true;
-        } else if (this.useCount[varName] <= MAX_USES) {
-          return !this.depsMutatedInLiveRange[varName];
+    // clean up vars
+    //printErr('cleaning up ' + JSON.stringify(varsToRemove));
+    traverse(func, function(node, type) {
+      if (type === 'var') {
+        node[1] = node[1].filter(function(pair) { return !(pair[0] in varsToRemove) });
+        if (node[1].length == 0) {
+          // wipe out an empty |var;|
+          node[0] = 'toplevel';
+          node[1] = [];
         }
       }
-      return false;
-    };
-
-    // Removes all var declarations for the specified variables.
-    //   this.arg toRemove: An object whose keys are the variable names to remove.
-    this.removeDeclarations = function(toRemove) {
-      traverse(this.body, function(node, type) {
-        if (type === 'var') {
-          var intactVars = node[1].filter(function(i) { return !toRemove.hasOwnProperty(i[0]) });
-          if (intactVars.length) {
-            node[1] = intactVars;
-            return node;
-          } else {
-            return ['toplevel', []];
-          }
-        }
-      });
-    };
+    });
 
-    // Updates all the values for the given variables to eliminate reference to any
-    // of the other variables in the group.
-    //   this.arg values: A map from variable names to their values as AST expressions.
-    this.collapseValues = function(values) {
-      var incomplete = true;
-      while (incomplete) {
-        incomplete = false;
-        for (var varName in values) {
-          var varValue = values[varName];
-          var result = traverse(varValue, function(node, type) {
-            if (type == 'name' && values.hasOwnProperty(node[1]) && node[1] != varName) {
-              incomplete = true;
-              return values[node[1]];
-            }
-          });
-          if (result) values[varName] = result;
-        }
+    // Undo X[10] hiding
+    traverse(func, function(node, type) {
+      if (type === 'sname') {
+        node[0] = 'name';
       }
-    };
-
-    // Replaces all uses of the specified variables with their respective
-    // expressions.
-    //   this.arg replacements: A map from variable names to AST expressions.
-    this.updateUses = function(replacements) {
-      traverse(this.body, function(node, type) {
-        if (type === 'name' && replacements.hasOwnProperty(node[1])) {
-          return replacements[node[1]];
-        }
-      });
-    };
-  }
+    });
+  });
 
-  // A class for optimizing expressions. We know that it === legitimate to collapse
+  // A class for optimizing expressions. We know that it is legitimate to collapse
   // 5+7 in the generated code, as it will always be numerical, for example. XXX do we need this? here?
   function ExpressionOptimizer(node) {
     this.node = node;
@@ -1815,30 +1636,7 @@ function eliminate(ast) {
       });
     };
   }
-
-  // The main entry point. runs the eliminator on each function
-
-  // Run on all functions.
-  traverse(ast, function(node, type) {
-    if ((type == 'defun' || type == 'function') && isGenerated(node[1])) {
-      // 'hide' X in X[10] so we don't get confused by it - these do not matter to variable effects
-      traverse(node, function(node, type) {
-        if (type === 'sub' && node[1][0] == 'name') {
-          node[1][0] = 'sname';
-        }
-      });
-      // Run the eliminator
-      var eliminated = new Eliminator(node).run();
-      // Undo X[10] hiding
-      traverse(node, function(node, type) {
-        if (type === 'sname') {
-          node[0] = 'name';
-        }
-      });
-      // Run the expression optimizer
-      new ExpressionOptimizer(node[3]).run();
-    }
-  });
+  new ExpressionOptimizer(ast).run();
 }
 
 // Passes table