Updated the eliminator, mainly to support use-before-declaration cases.

3 files changed, 163 insertions, 65 deletions

diff --git a/tools/eliminator/eliminator-test-output.js b/tools/eliminator/eliminator-test-output.js
index 4ff8a965..1480f5e5 100644
--- a/tools/eliminator/eliminator-test-output.js
+++ b/tools/eliminator/eliminator-test-output.js
@@ -6,7 +6,6 @@ function f() {
   HEAP[123] = (GLOB[1] + 1) / 2;
 }
 var g = function(a1, a2) {
-  var __label__;
   var a = 1;
   
   var c = a * 2 - 1;
@@ -24,7 +23,7 @@ var g = function(a1, a2) {
     quux(iterator);
   }
   var $0 = HEAP[5];
-  HEAP[myglobal] = 123;
+  MAYBE_HEAP[myglobal] = 123;
   
   if ($0 < 0) {
     __label__ = 1;
@@ -41,3 +40,44 @@ var g = function(a1, a2) {
     4: 5
   };
 };
+function h() {
+  var out;
+  bar(hello);
+  var hello = 5;
+  if (0) {
+    var sb1 = 21;
+  }
+  out = sb1;
+  if (0) {
+    var sb2 = 23;
+  } else {
+    out = sb2;
+  }
+  if (0) {
+    out = sb3;
+  } else {
+    var sb3 = 23;
+  }
+  for (var it = 0; it < 5; it++) {
+    x = y ? x + 1 : 7;
+    var x = -5;
+  }
+  return out;
+}
+function strtok_part(b, j, f) {
+  var a;
+  for (;;) {
+    h = a == 13 ? h : 0;
+    a = HEAP[d + h];
+    if (a == g != 0) break;
+    var h = h + 1;
+    if (a != 0) a = 13;
+  }
+}
+function py() {
+  
+  
+  
+  
+  HEAP[HEAP[__PyThreadState_Current] + 12] = HEAP[HEAP[__PyThreadState_Current] + 12] + 1;
+}
diff --git a/tools/eliminator/eliminator-test.js b/tools/eliminator/eliminator-test.js
index 68d9fdf5..88ea409c 100644
--- a/tools/eliminator/eliminator-test.js
+++ b/tools/eliminator/eliminator-test.js
@@ -1,12 +1,11 @@
 function f() {
-  var __label__;
+  var unused;
   var x = GLOB[1];
   var y = x + 1;
   var z = y / 2;
   HEAP[123] = z;
 }
 var g = function (a1, a2) {
-  var __label__;
   var a = 1;
   var b = a * 2;
   var c = b - 1;
@@ -16,13 +15,15 @@ var g = function (a1, a2) {
   var ww = 1, www, zzz = 2;
   foo(zzz);
   for (var i = 0; i < 5; i++) {
-    var q = {a:1} + [2,3];
+    var q = {
+      a: 1
+    } + [ 2, 3 ];
   }
   for (var iterator in SOME_GLOBAL) {
     quux(iterator);
   }
   var $0 = HEAP[5];
-  HEAP[myglobal] = 123;
+  MAYBE_HEAP[myglobal] = 123;
   var $1 = $0 < 0;
   if ($1) {
     __label__ = 1;
@@ -38,4 +39,45 @@ var g = function (a1, a2) {
     unquoted: 3,
     4: 5
   };
+};
+function h() {
+  var out;
+  bar(hello);
+  var hello = 5;
+  if (0) {
+    var sb1 = 21;
+  }
+  out = sb1;
+  if (0) {
+    var sb2 = 23;
+  } else {
+    out = sb2;
+  }
+  if (0) {
+    out = sb3;
+  } else {
+    var sb3 = 23;
+  }
+  for (var it = 0; it < 5; it++) {
+    x = y ? x + 1 : 7;
+    var x = -5;
+  }
+  return out;
+}
+function strtok_part(b, j, f) {
+  var a;
+  for (;;) {
+    h = a == 13 ? h : 0;
+    a = HEAP[d + h];
+    if (a == g != 0) break;
+    var h = h + 1;
+    if (a != 0) a = 13;
+  }
+}
+function py() {
+  var $4 = HEAP[__PyThreadState_Current];
+  var $5 = $4 + 12;
+  var $7 = HEAP[$5] + 1;
+  var $8 = $4 + 12;
+  HEAP[$8] = $7;
 }
diff --git a/tools/eliminator/eliminator.coffee b/tools/eliminator/eliminator.coffee
index 242394b7..08670096 100644
--- a/tools/eliminator/eliminator.coffee
+++ b/tools/eliminator/eliminator.coffee
@@ -5,17 +5,12 @@
 
   Single-def
     Uses only side-effect-free nodes
-      Single-use
-        Uses only local, single-def names
-          *
-        Uses non-local or non-single-def names
-          No flow-controlling statements between def and use
-            No references to any deps between def and use
-              No indirect accesses (subscript, dot notation) between def and use
-                *
-      Multi-use
-        Uses only local, single-def names
-          *
+      Unused
+        *
+      Has at most MAX_USES uses
+        No mutations to any dependencies between def and last use
+          No global dependencies or no indirect accesses between def and use
+            *
 
   TODO(max99x): Eliminate single-def undefined-initialized vars with no uses
                 between declaration and definition.
@@ -42,14 +37,17 @@ NODES_WITHOUT_SIDE_EFFECTS =
   binary: true
   sub: true
 
-# Nodes which may alter control flow.
+# Nodes which may break control flow. Moving a variable beyond them may have
+# side effects.
 CONTROL_FLOW_NODES =
   return: true
   break: true
   continue: true
   new: true
+  throw: true
   call: true
   label: true
+  debugger: true
 
 # Traverses a JavaScript syntax tree rooted at the given node calling the given
 # callback for each node.
@@ -62,7 +60,7 @@ CONTROL_FLOW_NODES =
 #     was stopped, false. Otherwise undefined.
 traverse = (node, callback) ->
   type = node[0]
-  if type
+  if typeof type == 'string'
     result = callback node, type
     if result? then return result
 
@@ -85,6 +83,8 @@ class Eliminator
     @body = func[3]
 
     # Identifier stats. Each of these objects is indexed by the identifier name.
+    # Whether the identifier is a local variable.
+    @isLocal = {}
     # Whether the identifier is never modified after initialization.
     @isSingleDef = {}
     # How many times the identifier is used.
@@ -92,9 +92,8 @@ class Eliminator
     # Whether the initial value of a single-def identifier uses only nodes
     # evaluating which has no side effects.
     @usesOnlySimpleNodes = {}
-    # Whether the initial value of a single-def identifier uses only other
-    # local single-def identifiers and/or literals.
-    @usesOnlySingleDefs = {}
+    # Whether the identifier depends on any non-local name, perhaps indirectly.
+    @dependsOnAGlobal = {}
     # Whether the dependencies of the single-def identifier may be mutated
     # within its live range.
     @depsMutatedInLiveRange = {}
@@ -133,7 +132,7 @@ class Eliminator
     closureFound = false
 
     traverse @body, (node, type) ->
-      if type in ['defun', 'function']
+      if type in ['defun', 'function', 'with']
         closureFound = true
         return false
       return undefined
@@ -141,6 +140,7 @@ class Eliminator
     return closureFound
 
   # Runs the basic variable scan pass. Fills the following member variables:
+  #   isLocal
   #   isSingleDef
   #   useCount
   #   initialValue
@@ -148,13 +148,15 @@ class Eliminator
     traverse @body, (node, type) =>
       if type is 'var'
         for [varName, varValue] in node[1]
+          @isLocal[varName] = true
           if not varValue? then varValue = ['name', 'undefined']
           @isSingleDef[varName] = not @isSingleDef.hasOwnProperty varName
           @initialValue[varName] = varValue
           @useCount[varName] = 0
       else if type is 'name'
         varName = node[1]
-        if varName of @useCount then @useCount[varName]++
+        if @useCount.hasOwnProperty varName then @useCount[varName]++
+        else @isSingleDef[varName] = false
       else if type in ['assign', 'unary-prefix', 'unary-postfix']
         varName = node[2][1]
         if @isSingleDef[varName] then @isSingleDef[varName] = false
@@ -164,13 +166,12 @@ class Eliminator
   # Analyzes the initial values of single-def variables. Requires basic variable
   # stats to have been calculated. Fills the following member variables:
   #   dependsOn
+  #   dependsOnAGlobal
   #   usesOnlySimpleNodes
-  #   usesOnlySingleDefs
   analyzeInitialValues: ->
     for varName of @isSingleDef
       if not @isSingleDef[varName] then continue
       @usesOnlySimpleNodes[varName] = true
-      @usesOnlySingleDefs[varName] = true
       traverse @initialValue[varName], (node, type) =>
         if type not of NODES_WITHOUT_SIDE_EFFECTS
           @usesOnlySimpleNodes[varName] = false
@@ -178,13 +179,13 @@ class Eliminator
           reference = node[1]
           if reference != 'undefined'
             if not @dependsOn[reference]? then @dependsOn[reference] = {}
+            if not @isLocal[reference] then @dependsOnAGlobal[varName] = true
             @dependsOn[reference][varName] = true
-            if not @isSingleDef[reference]
-              @usesOnlySingleDefs[varName] = false
         return undefined
     return undefined
 
-  # Updates the dependency graph (@dependsOn) to its transitive closure.
+  # Updates the dependency graph (@dependsOn) to its transitive closure and 
+  # synchronizes @dependsOnAGlobal to the new dependencies.
   calculateTransitiveDependencies: ->
     incomplete = true
     while incomplete
@@ -193,58 +194,76 @@ class Eliminator
         for source of sources
           for source2 of @dependsOn[source]
             if not @dependsOn[target][source2]
-              if not @isSingleDef[target]
-                @usesOnlySingleDefs[source2] = false
+              if not @isLocal[target] then @dependsOnAGlobal[source2] = true
               @dependsOn[target][source2] = true
               incomplete = true
     return undefined
 
-  # Analyzes the live ranges of single-def single-use variables. Requires
-  # dependencies to have been calculated. Fills the following member variables:
+  # Analyzes the live ranges of single-def variables. Requires dependencies to
+  # have been calculated. Fills the following member variables:
   #   depsMutatedInLiveRange
   analyzeLiveRanges: ->
     isLive = {}
+    isDead = {}
 
+    # Checks if a given note may mutate any of the currently live variables, and
+    # if so, adds them to isDead.
     checkForMutations = (node, type) =>
+      usedInThisStatement = {}
+      if type in ['assign', 'call']
+        traverse node.slice(2, 4), (node, type) =>
+          if type is 'name' then usedInThisStatement[node[1]] = true
+          return undefined
+
+      if type in ['assign', 'unary-prefix', 'unary-postfix']
+        if type is 'assign' or node[1] in ['--', '++']
+          reference = node[2]
+          while reference[0] != 'name'
+            reference = reference[1]
+          reference = reference[1]
+          if @dependsOn[reference]?
+            for varName of @dependsOn[reference]
+              if isLive[varName] and not usedInThisStatement[varName]
+                isDead[varName] = true
+
       if type of CONTROL_FLOW_NODES
         for varName of isLive
-          @depsMutatedInLiveRange[varName] = true
-        isLive = {}
+          if @dependsOnAGlobal[varName] or not usedInThisStatement[varName]
+            isDead[varName] = true
+      else if type is 'assign'
+        for varName of isLive
+          if @dependsOnAGlobal[varName] and not usedInThisStatement[varName]
+            isDead[varName] = true
       else if type is 'name'
         reference = node[1]
-        if @dependsOn[reference]?
-          for varName of @dependsOn[reference]
-            if isLive[varName]
-              @depsMutatedInLiveRange[varName] = true
-        if isLive[reference]
-          delete isLive[reference]
+        if @isSingleDef[reference]
+          if isDead[reference] or not isLive[reference]
+            @depsMutatedInLiveRange[reference] = true
       return undefined
 
-    traverse @body, (node, type) =>
-      if type is 'var'
+    # Analyzes a block and all its children for variable ranges. Makes sure to
+    # account for the worst case of possible mutations.
+    analyzeBlock = (node, type) =>
+      if type in ['if', 'do', 'while', 'for', 'for-in', 'try']
+        for child in node
+          if typeof child == 'object' and child?.length
+            savedLive = {}
+            for name of isLive then savedLive[name] = true
+            traverse child, analyzeBlock
+            isLive = savedLive
+        return node
+      else if type is 'var'
         for [varName, varValue] in node[1]
           if varValue? then traverse varValue, checkForMutations
-          if @isSingleDef[varName] and @useCount[varName] == 1
+          if @isSingleDef[varName]
             isLive[varName] = true
         return node
-      else if type is 'stat'
-        usedInThisStatement = {}
-        hasIndirectAccess = false
-        traverse node, (node, type) =>
-          if type is 'name'
-            usedInThisStatement[node[1]] = true
-          else if type in ['sub', 'dot']
-            hasIndirectAccess = true
-          return undefined
-        if hasIndirectAccess
-          for varName of isLive
-            if not usedInThisStatement[varName]
-              @depsMutatedInLiveRange[varName] = true
-              delete isLive[varName]
       else
         checkForMutations node, type
       return undefined
 
+    traverse @body, analyzeBlock
+
     return undefined
 
   # Determines whether a given variable can be safely eliminated. Requires all
@@ -253,11 +272,8 @@ class Eliminator
     if @isSingleDef[varName] and @usesOnlySimpleNodes[varName]
       if @useCount[varName] == 0
         return true
-      else if @useCount[varName] == 1
-        return (@usesOnlySingleDefs[varName] or
-                not @depsMutatedInLiveRange[varName])
       else if @useCount[varName] <= MAX_USES
-        return @usesOnlySingleDefs[varName]
+        return not @depsMutatedInLiveRange[varName]
     return false
 
   # Removes all var declarations for the specified variables.
@@ -265,7 +281,7 @@ class Eliminator
   removeDeclarations: (toRemove) ->
     traverse @body, (node, type) ->
       if type is 'var'
-        intactVars = (i for i in node[1] when i[0] not of toRemove)
+        intactVars = (i for i in node[1] when not toRemove.hasOwnProperty i[0])
         if intactVars.length
           node[1] = intactVars
           return node
@@ -283,7 +299,7 @@ class Eliminator
       incomplete = false
       for varName, varValue of values
         result = traverse varValue, (node, type) ->
-          if type == 'name' and node[1] of values and node[1] != varName
+          if type == 'name' and values.hasOwnProperty(node[1]) and node[1] != varName
             incomplete = true
             return values[node[1]]
           return undefined
@@ -295,7 +311,7 @@ class Eliminator
   #   @arg replacements: A map from variable names to AST expressions.
   updateUses: (replacements) ->
     traverse @body, (node, type) ->
-      if type is 'name' and node[1] of replacements
+      if type is 'name' and replacements.hasOwnProperty node[1]
         return replacements[node[1]]
       return undefined
     return undefined