Merge branch 'incoming'

6 files changed, 237 insertions, 176 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 161ed59c..3a6d70bc 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -1743,6 +1743,36 @@ function getStackBumpSize(ast) {
   return node ? node[3][2][3][1] : 0;
 }
 
+// Name minification
+
+var RESERVED = set('do', 'if', 'in', 'for', 'new', 'try', 'var', 'env', 'let');
+var VALID_MIN_INITS = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$';
+var VALID_MIN_LATERS = VALID_MIN_INITS + '0123456789';
+
+var minifiedNames = [];
+var minifiedState = [0];
+
+function ensureMinifiedNames(n) { // make sure the nth index in minifiedNames exists. done 100% deterministically
+  while (minifiedNames.length < n+1) {
+    // generate the current name
+    var name = VALID_MIN_INITS[minifiedState[0]];
+    for (var i = 1; i < minifiedState.length; i++) {
+      name += VALID_MIN_LATERS[minifiedState[i]];
+    }
+    if (!(name in RESERVED)) minifiedNames.push(name);
+    // increment the state
+    var i = 0;
+    while (1) {
+      minifiedState[i]++;
+      if (minifiedState[i] < (i === 0 ? VALID_MIN_INITS : VALID_MIN_LATERS).length) break;
+      // overflow
+      minifiedState[i] = 0;
+      i++;
+      if (i === minifiedState.length) minifiedState.push(-1); // will become 0 after increment in next loop head
+    }
+  }
+}
+
 // Very simple 'registerization', coalescing of variables into a smaller number,
 // as part of minification. Globals-level minification began in a previous pass,
 // we receive extraInfo which tells us how to rename globals. (Only in asm.js.)
@@ -1853,14 +1883,14 @@ function registerize(ast) {
         return ret;
       }
       // find the next free minified name that is not used by a global that shows up in this function
-      while (nextRegName < extraInfo.names.length) {
-        var ret = extraInfo.names[nextRegName++];
+      while (1) {
+        ensureMinifiedNames(nextRegName);
+        var ret = minifiedNames[nextRegName++];
         if (!usedGlobals[ret]) {
           regTypes[ret] = type;
           return ret;
         }
       }
-      assert('ran out of names');
     }
     // Find the # of uses of each variable.
     // While doing so, check if all a variable's uses are dominated in a simple
@@ -2847,16 +2877,16 @@ function minifyGlobals(ast) {
       var vars = node[1];
       for (var i = 0; i < vars.length; i++) {
         var name = vars[i][0];
-        assert(next < extraInfo.names.length);
-        vars[i][0] = minified[name] = extraInfo.names[next++];
+        ensureMinifiedNames(next);
+        vars[i][0] = minified[name] = minifiedNames[next++];
       }
     }
   });
   // add all globals in function chunks, i.e. not here but passed to us
   for (var i = 0; i < extraInfo.globals.length; i++) {
     name = extraInfo.globals[i];
-    assert(next < extraInfo.names.length);
-    minified[name] = extraInfo.names[next++];
+    ensureMinifiedNames(next);
+    minified[name] = minifiedNames[next++];
   }
   // apply minification
   traverse(ast, function(node, type) {
@@ -2930,162 +2960,180 @@ 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 = {}, recursives = {};
 
-    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[name] = null; // prevent infinite recursion
+    var def = defs[name];
+    if (def) {
+      node = def[3];
+      if (node[0] == 'name') {
+        var name2 = node[1];
+        assert(name2 !== name);
+        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 === name) {
+              recursives[name] = 1;
+              return false;
+            }
+            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 recursives) {
+    delete trivials[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) return copy(value); // must copy, or else the same object can be used multiple times
+        else return emptyNode();
       }
-      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 +3788,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 +3969,7 @@ var passes = {
   registerize: registerize,
   eliminate: eliminate,
   eliminateMemSafe: eliminateMemSafe,
+  aggressiveVariableElimination: aggressiveVariableElimination,
   minifyGlobals: minifyGlobals,
   relocate: relocate,
   outline: outline,
diff --git a/tools/js_optimizer.py b/tools/js_optimizer.py
index dcc9cd5f..71b6f377 100644
--- a/tools/js_optimizer.py
+++ b/tools/js_optimizer.py
@@ -24,41 +24,16 @@ import_sig = re.compile('var ([_\w$]+) *=[^;]+;')
 
 class Minifier:
   '''
-    asm.js minification support. We calculate possible names and minification of
+    asm.js minification support. We calculate minification of
     globals here, then pass that into the parallel js-optimizer.js runners which
     during registerize perform minification of locals.
   '''
 
-  def __init__(self, js, js_engine, MAX_NAMES):
+  def __init__(self, js, js_engine):
     self.js = js
     self.js_engine = js_engine
-    MAX_NAMES = min(MAX_NAMES, 120000)
-
-    # Create list of valid short names
-
-    INVALID_2 = set(['do', 'if', 'in'])
-    INVALID_3 = set(['for', 'new', 'try', 'var', 'env', 'let'])
-
-    self.names = []
-    init_possibles = string.ascii_letters + '_$'
-    later_possibles = init_possibles + string.digits
-    for a in init_possibles:
-      if len(self.names) >= MAX_NAMES: break
-      self.names.append(a)
-    for a in init_possibles:
-      for b in later_possibles:
-        if len(self.names) >= MAX_NAMES: break
-        curr = a + b
-        if curr not in INVALID_2: self.names.append(curr)
-    for a in init_possibles:
-      for b in later_possibles:
-        for c in later_possibles:
-          if len(self.names) >= MAX_NAMES: break
-          curr = a + b + c
-          if curr not in INVALID_3: self.names.append(curr)
 
   def minify_shell(self, shell, minify_whitespace, source_map=False):
-    #print >> sys.stderr, "MINIFY SHELL 1111111111", shell, "\n222222222222222"
     # Run through js-optimizer.js to find and minify the global symbols
     # We send it the globals, which it parses at the proper time. JS decides how
     # to minify all global names, we receive a dictionary back, which is then
@@ -91,7 +66,6 @@ class Minifier:
 
   def serialize(self):
     return {
-      'names': self.names,
       'globals': self.globs
     }
 
@@ -187,7 +161,7 @@ EMSCRIPTEN_FUNCS();
       js = js[start_funcs + len(start_funcs_marker):end_funcs]
 
       # we assume there is a maximum of one new name per line
-      minifier = Minifier(js, js_engine, js.count('\n') + asm_shell.count('\n'))
+      minifier = Minifier(js, js_engine)
       asm_shell_pre, asm_shell_post = minifier.minify_shell(asm_shell, 'minifyWhitespace' in passes, source_map).split('EMSCRIPTEN_FUNCS();');
       asm_shell_post = asm_shell_post.replace('});', '})');
       pre += asm_shell_pre + '\n' + start_funcs_marker
@@ -368,6 +342,7 @@ EMSCRIPTEN_FUNCS();
   return filename
 
 def run(filename, passes, js_engine=shared.NODE_JS, jcache=False, source_map=False, extra_info=None):
+  js_engine = shared.listify(js_engine)
   return temp_files.run_and_clean(lambda: run_on_js(filename, passes, js_engine, jcache, source_map, extra_info))
 
 if __name__ == '__main__':
diff --git a/tools/nativize_llvm.py b/tools/nativize_llvm.py
index 413c8d14..b327bdfc 100755
--- a/tools/nativize_llvm.py
+++ b/tools/nativize_llvm.py
@@ -23,7 +23,7 @@ libs = sys.argv[2:] # e.g.: dl for dlopen/dlclose, util for openpty/forkpty
 print 'bc => clean bc'
 Popen([LLVM_OPT, filename, '-strip-debug', '-o', filename + '.clean.bc']).communicate()[0]
 print 'bc => s'
-for params in [[], ['-march=x86-64']]: # try x86, then x86-64 FIXME
+for params in [['-march=x86'], ['-march=x86-64']]: # try x86, then x86-64 FIXME
   print 'params', params
   Popen([LLVM_COMPILER] + params + [filename + '.clean.bc', '-o', filename + '.s']).communicate()[0]
   print 's => o'
diff --git a/tools/shared.py b/tools/shared.py
index 5b02fa4c..2ae37f91 100644
--- a/tools/shared.py
+++ b/tools/shared.py
@@ -272,9 +272,17 @@ if EM_POPEN_WORKAROUND and os.name == 'nt':
 
 EXPECTED_LLVM_VERSION = (3,2)
 
+actual_clang_version = None
+
+def get_clang_version():
+  global actual_clang_version
+  if actual_clang_version is None:
+    actual_clang_version = Popen([CLANG, '-v'], stderr=PIPE).communicate()[1].split('\n')[0].split(' ')[2]
+  return actual_clang_version
+
 def check_clang_version():
-  expected = 'clang version ' + '.'.join(map(str, EXPECTED_LLVM_VERSION))
-  actual = Popen([CLANG, '-v'], stderr=PIPE).communicate()[1].split('\n')[0]
+  expected = '.'.join(map(str, EXPECTED_LLVM_VERSION))
+  actual = get_clang_version()
   if expected in actual:
     return True
   logging.warning('LLVM version appears incorrect (seeing "%s", expected "%s")' % (actual, expected))
@@ -337,10 +345,10 @@ def find_temp_directory():
 # we re-check sanity when the settings are changed)
 # We also re-check sanity and clear the cache when the version changes
 
-EMSCRIPTEN_VERSION = '1.8.2'
+EMSCRIPTEN_VERSION = '1.9.0'
 
 def generate_sanity():
-  return EMSCRIPTEN_VERSION + '|' + get_llvm_target() + '|' + LLVM_ROOT
+  return EMSCRIPTEN_VERSION + '|' + get_llvm_target() + '|' + LLVM_ROOT + '|' + get_clang_version()
 
 def check_sanity(force=False):
   try:
@@ -1163,6 +1171,8 @@ class Building:
     if type(opts) is int:
       opts = Building.pick_llvm_opts(opts)
     #opts += ['-debug-pass=Arguments']
+    if get_clang_version() == '3.4' and not Settings.SIMD:
+      opts += ['-disable-loop-vectorization', '-disable-slp-vectorization'] # llvm 3.4 has these on by default
     logging.debug('emcc: LLVM opts: ' + str(opts))
     target = out or (filename + '.opt.bc')
     output = Popen([LLVM_OPT, filename] + opts + ['-o', target], stdout=PIPE).communicate()[0]
@@ -1404,6 +1414,8 @@ class Building:
     if not os.path.exists(CLOSURE_COMPILER):
       raise Exception('Closure compiler appears to be missing, looked at: ' + str(CLOSURE_COMPILER))
 
+    CLOSURE_EXTERNS = path_from_root('src', 'closure-externs.js')
+
     # Something like this (adjust memory as needed):
     #   java -Xmx1024m -jar CLOSURE_COMPILER --compilation_level ADVANCED_OPTIMIZATIONS --variable_map_output_file src.cpp.o.js.vars --js src.cpp.o.js --js_output_file src.cpp.o.cc.js
     args = [JAVA,
@@ -1411,6 +1423,7 @@ class Building:
             '-jar', CLOSURE_COMPILER,
             '--compilation_level', 'ADVANCED_OPTIMIZATIONS',
             '--language_in', 'ECMASCRIPT5',
+            '--externs', CLOSURE_EXTERNS,
             #'--variable_map_output_file', filename + '.vars',
             '--js', filename, '--js_output_file', filename + '.cc.js']
     if pretty: args += ['--formatting', 'PRETTY_PRINT']
diff --git a/tools/test-js-optimizer-shiftsAggressive-output.js b/tools/test-js-optimizer-shiftsAggressive-output.js
new file mode 100644
index 00000000..5b429786
--- /dev/null
+++ b/tools/test-js-optimizer-shiftsAggressive-output.js
@@ -0,0 +1,11 @@
+function __ZNSt3__111__call_onceERVmPvPFvS2_E($flag, $arg, $func) {
+ $flag = $flag | 0;
+ $arg = $arg | 0;
+ $func = $func | 0;
+ var $2 = 0;
+ $2 = cheez();
+ whee1($flag + 1 | 0);
+ whee2($flag + 1 | 0);
+ whee3($flag + 1 | 0);
+}
+
diff --git a/tools/test-js-optimizer-shiftsAggressive.js b/tools/test-js-optimizer-shiftsAggressive.js
new file mode 100644
index 00000000..4218d04c
--- /dev/null
+++ b/tools/test-js-optimizer-shiftsAggressive.js
@@ -0,0 +1,13 @@
+function __ZNSt3__111__call_onceERVmPvPFvS2_E($flag,$arg,$func){
+ $flag=($flag)|0;
+ $arg=($arg)|0;
+ $func=($func)|0;
+ var $1=0,$2=0,$3=0;
+ $1;
+ $2 = cheez();
+ $3 = $flag + 1 | 0;
+ whee1($3);
+ whee2($3);
+ whee3($3);
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["__ZNSt3__111__call_onceERVmPvPFvS2_E"]