make aggressiveVariableElimination usable through a setting

4 files changed, 152 insertions, 135 deletions

diff --git a/emcc b/emcc
index bad118cd..f1b7dc5d 100755
--- a/emcc
+++ b/emcc
@@ -1916,6 +1916,9 @@ try:
 
     js_optimizer_queue += [get_eliminate()]
 
+    if shared.Settings.AGGRESSIVE_VARIABLE_ELIMINATION:
+      js_optimizer_queue += ['aggressiveVariableElimination']
+
     if opt_level >= 2:
       js_optimizer_queue += ['simplifyExpressions']
 
diff --git a/src/settings.js b/src/settings.js
index 753e2367..04b2cc79 100644
--- a/src/settings.js
+++ b/src/settings.js
@@ -156,6 +156,8 @@ var OUTLINING_LIMIT = 0; // A function size above which we try to automatically
                          // with, but something around 20,000 to 100,000 might make sense.
                          // (The unit size is number of AST nodes.)
 
+var AGGRESSIVE_VARIABLE_ELIMINATION = 0; // Run aggressiveVariableElimination in js-optimizer.js
+
 // Generated code debugging options
 var SAFE_HEAP = 0; // Check each write to the heap, for example, this will give a clear
                    // error on what would be segfaults in a native build (like deferencing
diff --git a/tests/test_benchmark.py b/tests/test_benchmark.py
index 1296e477..21a47178 100644
--- a/tests/test_benchmark.py
+++ b/tests/test_benchmark.py
@@ -128,6 +128,7 @@ try:
     #NativeBenchmarker('clang-3.4', os.path.join(LLVM_3_4, 'clang'), os.path.join(LLVM_3_4, 'clang++')),
     #NativeBenchmarker('gcc', 'gcc', 'g++'),
     JSBenchmarker('sm-f32', SPIDERMONKEY_ENGINE, ['-s', 'PRECISE_F32=2']),
+    #JSBenchmarker('sm-f32-aggro', SPIDERMONKEY_ENGINE, ['-s', 'PRECISE_F32=2', '-s', 'AGGRESSIVE_VARIABLE_ELIMINATION=1']),
     #JSBenchmarker('sm-f32-3.2', SPIDERMONKEY_ENGINE, ['-s', 'PRECISE_F32=2'], env={ 'LLVM': LLVM_3_2 }),
     #JSBenchmarker('sm-f32-3.3', SPIDERMONKEY_ENGINE, ['-s', 'PRECISE_F32=2'], env={ 'LLVM': LLVM_3_3 }),
     #JSBenchmarker('sm-f32-3.4', SPIDERMONKEY_ENGINE, ['-s', 'PRECISE_F32=2'], env={ 'LLVM': LLVM_3_4 }),
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 161ed59c..7b1c6bd1 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -2930,162 +2930,172 @@ function relocate(ast) {
 var NODES_WITHOUT_ELIMINATION_SENSITIVITY = set('name', 'num', 'binary', 'unary-prefix');
 var FAST_ELIMINATION_BINARIES = setUnion(setUnion(USEFUL_BINARY_OPS, COMPARE_OPS), set('+'));
 
-function outline(ast) {
-  function measureSize(ast) {
-    var size = 0;
-    traverse(ast, function() {
-      size++;
-    });
-    return size;
-  }
-
-  function aggressiveVariableElimination(func, asmData) {
-    // This removes as many variables as possible. This is often not the best thing because it increases
-    // code size, but it is far preferable to the risk of split functions needing to do more spilling. Specifically,
-    // it finds 'trivial' variables: ones with 1 definition, and that definition is not sensitive to any changes: it
-    // only depends on constants and local variables that are themselves trivial. We can unquestionably eliminate
-    // such variables in a trivial manner.
-
-    var assignments = {};
-    var appearances = {};
-    var defs = {};
-    var considered = {};
+function measureSize(ast) {
+  var size = 0;
+  traverse(ast, function() {
+    size++;
+  });
+  return size;
+}
 
-    traverse(func, function(node, type) {
-      if (type == 'assign' && node[2][0] == 'name') {
-        var name = node[2][1];
-        if (name in asmData.vars) {
-          assignments[name] = (assignments[name] || 0) + 1;
-          appearances[name] = (appearances[name] || 0) - 1; // this appearance is a definition, offset the counting later
-          defs[name] = node;
-        } else {
-          if (name in asmData.params) {
-            assignments[name] = (assignments[name] || 1) + 1; // init to 1 for initial parameter assignment
-            considered[name] = true; // this parameter is not ssa, it must be in a hand-optimized function, so it is not trivial
-          }
-        }
-      } else if (type == 'name') {
-        var name = node[1];
-        if (name in asmData.vars) {
-          appearances[name] = (appearances[name] || 0) + 1;
+function aggressiveVariableEliminationInternal(func, asmData) {
+  // This removes as many variables as possible. This is often not the best thing because it increases
+  // code size, but it is far preferable to the risk of split functions needing to do more spilling, so
+  // we use it when outlining.
+  // Specifically, this finds 'trivial' variables: ones with 1 definition, and that definition is not sensitive to any changes: it
+  // only depends on constants and local variables that are themselves trivial. We can unquestionably eliminate
+  // such variables in a trivial manner.
+
+  var assignments = {};
+  var appearances = {};
+  var defs = {};
+  var considered = {};
+
+  traverse(func, function(node, type) {
+    if (type == 'assign' && node[2][0] == 'name') {
+      var name = node[2][1];
+      if (name in asmData.vars) {
+        assignments[name] = (assignments[name] || 0) + 1;
+        appearances[name] = (appearances[name] || 0) - 1; // this appearance is a definition, offset the counting later
+        defs[name] = node;
+      } else {
+        if (name in asmData.params) {
+          assignments[name] = (assignments[name] || 1) + 1; // init to 1 for initial parameter assignment
+          considered[name] = true; // this parameter is not ssa, it must be in a hand-optimized function, so it is not trivial
         }
       }
-    });
+    } else if (type == 'name') {
+      var name = node[1];
+      if (name in asmData.vars) {
+        appearances[name] = (appearances[name] || 0) + 1;
+      }
+    }
+  });
 
-    var allTrivials = {}; // key of a trivial var => size of its (expanded) value, at least 1
-
-    // three levels of variables:
-    // 1. trivial: 1 def (or less), uses nothing sensitive, can be eliminated
-    // 2. safe: 1 def (or less), can be used in a trivial, but cannot itself be eliminated
-    // 3. sensitive: uses a global or memory or something else that prevents trivial elimination.
-
-    function assessTriviality(name) {
-      // only care about vars with 0-1 assignments of (0 for parameters), and can ignore label (which is not explicitly initialized, but cannot be eliminated ever anyhow)
-      if (assignments[name] > 1 || (!(name in asmData.vars) && !(name in asmData.params)) || name == 'label') return false;
-      if (considered[name]) return allTrivials[name];
-      considered[name] = true;
-      var sensitive = false;
-      var size = 0, originalSize = 0;
-      var def = defs[name];
-      if (def) {
-        var value = def[3];
-        originalSize = measureSize(value);
-        if (value) {
-          traverse(value, function recurseValue(node, type) {
-            var one = node[1];
-            if (!(type in NODES_WITHOUT_ELIMINATION_SENSITIVITY)) { // || (type == 'binary' && !(one in FAST_ELIMINATION_BINARIES))) {
-              sensitive = true;
+  var allTrivials = {}; // key of a trivial var => size of its (expanded) value, at least 1
+
+  // three levels of variables:
+  // 1. trivial: 1 def (or less), uses nothing sensitive, can be eliminated
+  // 2. safe: 1 def (or less), can be used in a trivial, but cannot itself be eliminated
+  // 3. sensitive: uses a global or memory or something else that prevents trivial elimination.
+
+  function assessTriviality(name) {
+    // only care about vars with 0-1 assignments of (0 for parameters), and can ignore label (which is not explicitly initialized, but cannot be eliminated ever anyhow)
+    if (assignments[name] > 1 || (!(name in asmData.vars) && !(name in asmData.params)) || name == 'label') return false;
+    if (considered[name]) return allTrivials[name];
+    considered[name] = true;
+    var sensitive = false;
+    var size = 0, originalSize = 0;
+    var def = defs[name];
+    if (def) {
+      var value = def[3];
+      originalSize = measureSize(value);
+      if (value) {
+        traverse(value, function recurseValue(node, type) {
+          var one = node[1];
+          if (!(type in NODES_WITHOUT_ELIMINATION_SENSITIVITY)) { // || (type == 'binary' && !(one in FAST_ELIMINATION_BINARIES))) {
+            sensitive = true;
+            return true;
+          }
+          if (type == 'name' && !assessTriviality(one)) {
+            if (assignments[one] > 1 || (!(one in asmData.vars) && !(one in asmData.params))) {
+              sensitive = true; // directly using something sensitive
               return true;
-            }
-            if (type == 'name' && !assessTriviality(one)) {
-              if (assignments[one] > 1 || (!(one in asmData.vars) && !(one in asmData.params))) {
-                sensitive = true; // directly using something sensitive
-                return true;
-              } // otherwise, not trivial, but at least safe.
-            }
-            // if this is a name, it must be a trivial variable (or a safe one) and we know its size
-            size += ((type == 'name') ? allTrivials[one] : 1) || 1;
-          });
-        }
-      }
-      if (!sensitive) {
-        size = size || 1;
-        originalSize = originalSize || 1;
-        var factor = ((appearances[name] - 1) || 0) * (size - originalSize); // If no size change or just one appearance, always ok to trivially eliminate. otherwise, tradeoff
-        if (factor <= 12) {
-          allTrivials[name] = size; // trivial!
-          return true;
-        }
+            } // otherwise, not trivial, but at least safe.
+          }
+          // if this is a name, it must be a trivial variable (or a safe one) and we know its size
+          size += ((type == 'name') ? allTrivials[one] : 1) || 1;
+        });
       }
-      return false;
     }
-    for (var name in asmData.vars) {
-      assessTriviality(name);
+    if (!sensitive) {
+      size = size || 1;
+      originalSize = originalSize || 1;
+      var factor = ((appearances[name] - 1) || 0) * (size - originalSize); // If no size change or just one appearance, always ok to trivially eliminate. otherwise, tradeoff
+      if (factor <= 12) {
+        allTrivials[name] = size; // trivial!
+        return true;
+      }
     }
-    var trivials = {};
+    return false;
+  }
+  for (var name in asmData.vars) {
+    assessTriviality(name);
+  }
+  var trivials = {};
 
-    for (var name in allTrivials) { // from now on, ignore parameters
-      if (name in asmData.vars) trivials[name] = true;
-    }
+  for (var name in allTrivials) { // from now on, ignore parameters
+    if (name in asmData.vars) trivials[name] = true;
+  }
 
-    allTrivials = {};
+  allTrivials = {};
 
-    var values = {};
+  var values = {};
 
-    function evaluate(name) {
-      var node = values[name];
-      if (node) return node;
-      values[node] = null; // prevent infinite recursion
-      var def = defs[name];
-      if (def) {
-        node = def[3];
-        if (node[0] == 'name') {
-          var name2 = node[1];
-          if (name2 in trivials) {
-            node = evaluate(name2);
-          }
-        } else {
-          traverse(node, function(node, type) {
-            if (type == 'name') {
-              var name2 = node[1];
-              if (name2 in trivials) {
-                return evaluate(name2);
-              }
-            }
-          });
+  function evaluate(name) {
+    var node = values[name];
+    if (node) return node;
+    values[node] = null; // prevent infinite recursion
+    var def = defs[name];
+    if (def) {
+      node = def[3];
+      if (node[0] == 'name') {
+        var name2 = node[1];
+        if (name2 in trivials) {
+          node = evaluate(name2);
         }
-        values[name] = node;
+      } else {
+        traverse(node, function(node, type) {
+          if (type == 'name') {
+            var name2 = node[1];
+            if (name2 in trivials) {
+              return evaluate(name2);
+            }
+          }
+        });
       }
-      return node;
+      values[name] = node;
     }
+    return node;
+  }
 
-    for (var name in trivials) {
-      evaluate(name);
+  for (var name in trivials) {
+    evaluate(name);
+  }
+
+  for (var name in trivials) {
+    var def = defs[name];
+    if (def) {
+      def.length = 0;
+      def[0] = 'toplevel';
+      def[1] = [];
     }
+    delete asmData.vars[name];
+  }
 
-    for (var name in trivials) {
-      var def = defs[name];
-      if (def) {
-        def.length = 0;
-        def[0] = 'toplevel';
-        def[1] = [];
+  // Perform replacements TODO: save list of uses objects before, replace directly, avoid extra traverse
+  traverse(func, function(node, type) {
+    if (type == 'name') {
+      var name = node[1];
+      if (name in trivials) {
+        var value = values[name];
+        if (!value) throw 'missing value: ' + [func[1], name, values[name]] + ' - faulty reliance on asm zero-init?';
+        return copy(value); // must copy, or else the same object can be used multiple times
       }
-      delete asmData.vars[name];
     }
+  });
+}
 
-    // Perform replacements TODO: save list of uses objects before, replace directly, avoid extra traverse
-    traverse(func, function(node, type) {
-      if (type == 'name') {
-        var name = node[1];
-        if (name in trivials) {
-          var value = values[name];
-          if (!value) throw 'missing value: ' + [func[1], name, values[name]] + ' - faulty reliance on asm zero-init?';
-          return copy(value); // must copy, or else the same object can be used multiple times
-        }
-      }
-    });
-  }
+function aggressiveVariableElimination(ast) {
+  assert(asm, 'need ASM_JS for aggressive variable elimination');
+  traverseGeneratedFunctions(ast, function(func, type) {
+    var asmData = normalizeAsm(func);
+    aggressiveVariableEliminationInternal(func, asmData);
+    denormalizeAsm(func, asmData);
+  });
+}
 
+function outline(ast) {
   // Try to flatten out code as much as possible, to make outlining more feasible.
   function flatten(func, asmData) {
     var minSize = extraInfo.sizeToOutline/4;
@@ -3740,7 +3750,7 @@ function outline(ast) {
       var size = measureSize(func);
       if (size >= extraInfo.sizeToOutline && maxTotalFunctions > 0) {
         maxTotalFunctions--;
-        aggressiveVariableElimination(func, asmData);
+        aggressiveVariableEliminationInternal(func, asmData);
         flatten(func, asmData);
         analyzeFunction(func, asmData);
         calculateThreshold(func, asmData);
@@ -3921,6 +3931,7 @@ var passes = {
   registerize: registerize,
   eliminate: eliminate,
   eliminateMemSafe: eliminateMemSafe,
+  aggressiveVariableElimination: aggressiveVariableElimination,
   minifyGlobals: minifyGlobals,
   relocate: relocate,
   outline: outline,