remove all unneeded loop labels

4 files changed, 172 insertions, 8 deletions

diff --git a/tests/runner.py b/tests/runner.py
index 2eaf65aa..a3f9f0ce 100644
--- a/tests/runner.py
+++ b/tests/runner.py
@@ -4482,7 +4482,8 @@ TT = %s
     def test_js_optimizer(self):
       input = open(path_from_root('tools', 'test-js-optimizer.js')).read()
       expected = open(path_from_root('tools', 'test-js-optimizer-output.js')).read()
-      output = Popen([NODE_JS, JS_OPTIMIZER, 'unGlobalize', 'removeAssignsToUndefined', 'simplifyNotComps'], stdin=PIPE, stdout=PIPE).communicate(input)[0]
+      output = Popen([NODE_JS, JS_OPTIMIZER, 'unGlobalize', 'removeAssignsToUndefined', 'simplifyNotComps', 'loopOptimizer'],
+                     stdin=PIPE, stdout=PIPE).communicate(input)[0]
       self.assertIdentical(expected, output.replace('\n\n', '\n'))
 
 else:
@@ -4520,7 +4521,7 @@ else:
   #JS_ENGINE = V8_ENGINE
 
   Building.COMPILER_TEST_OPTS = []
-  POST_OPTIMIZATIONS = ['eliminator', 'closure', ['js-optimizer', 'unGlobalize', 'removeAssignsToUndefined', 'simplifyNotComps']]
+  POST_OPTIMIZATIONS = [['js-optimizer', 'loopOptimizer'], 'eliminator', 'closure', ['js-optimizer', 'unGlobalize', 'removeAssignsToUndefined', 'simplifyNotComps']]
 
   TEST_REPS = 10
   TOTAL_TESTS = 6
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 7f613e5f..d1078471 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -13,6 +13,9 @@ var fs = require('fs');
 function print(text) {
   process.stdout.write(text + '\n');
 }
+function printErr(text) {
+  process.stderr.write(text + '\n');
+}
 function read(filename) {
   if (filename[0] != '/') filename = __dirname.split('/').slice(0, -1).join('/') + '/src/' + filename;
   return fs.readFileSync(filename).toString();
@@ -26,6 +29,8 @@ eval(read('utility.js'));
 // Utilities
 
 var FUNCTION = set('defun', 'function');
+var LOOP = set('do', 'while', 'for');
+var LOOP_FLOW = set('break', 'continue');
 
 var NULL_NODE = ['name', 'null'];
 var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]];
@@ -33,7 +38,10 @@ var TRUE_NODE = ['unary-prefix', '!', ['num', 0]];
 var FALSE_NODE = ['unary-prefix', '!', ['num', 1]];
 
 var GENERATED_FUNCTIONS_MARKER = '// EMSCRIPTEN_GENERATED_FUNCTIONS:';
-var generatedFunctions = {};
+var generatedFunctions = null;
+function setGeneratedFunctions(metadata) {
+  generatedFunctions = set(eval(metadata.replace(GENERATED_FUNCTIONS_MARKER, '')));
+}
 function isGenerated(ident) {
   return ident in generatedFunctions;
 }
@@ -78,6 +86,15 @@ function traverse(node, pre, post, stack) {
   return result;
 }
 
+// Only walk through the generated functions
+function traverseGenerated(ast, pre, post, stack) {
+  ast[1].forEach(function(node, i) {
+    if (node[0] == 'defun' && isGenerated(node[1])) {
+      traverse(node, pre, post, stack);
+    }
+  });
+}
+
 // Walk the ast in a simple way, with an understanding of which JS variables are defined)
 function traverseWithVariables(ast, callback) {
   traverse(ast, function(node, type, stack) {
@@ -249,23 +266,85 @@ function simplifyNotComps(ast) {
   });
 }
 
+function loopOptimizer(ast) {
+  // We generate loops and one-time loops (do while(0)) with labels. It is often
+  // possible to eliminate those labels.
+  function loopLabelOptimizer(ast) {
+    // Find unneeded labels
+    traverseGenerated(ast, function(node, type, stack) {
+      if (type == 'label' && node[2][0] in LOOP) {
+        // this is a labelled loop. we don't know if it's needed yet. Mark its label for removal for now now.
+        stack.push(node);
+        node[1] = '+' + node[1];
+      } else if (type in LOOP) {
+        stack.push(node);
+      } else if (type in LOOP_FLOW && node[1]) { // only care about break/continue with an explicit label
+        // Find topmost loop, and its label if there is one
+        var lastLabel = null, lastLoop = null, i = stack.length-1;
+        while (i >= 0 && !lastLoop) {
+          if (stack[i][0] in LOOP) lastLoop = stack[i];
+          i--;
+        }
+        assert(lastLoop, 'Cannot break/continue without a Label');
+        while (i >= 0 && !lastLabel) {
+          if (stack[i][0] in LOOP) break; // another loop in the middle - no label for lastLoop
+          if (stack[i][0] == 'label') lastLabel = stack[i];
+          i--;
+        }
+        var ident = node[1];
+        var plus = '+' + ident;
+        if (lastLabel && (ident == lastLabel[1] || plus == lastLabel[1])) {
+          // We don't need the control flow command to have a label - it's referring to the current loop
+          return [node[0]];
+        } else {
+          // Find the label node that needs to stay alive
+          stack.forEach(function(label) {
+            if (!label) return;
+            if (label[1] == plus) label[1] = label[1].substr(1); // Remove '+', marking it as needed
+          });
+        }
+      }
+    }, null, []);
+    // Remove those labels
+    traverseGenerated(ast, function(node, type) {
+      if (type == 'label' && node[1][0] == '+') {
+        var ident = node[1].substr(1);
+        // Remove label from loop flow commands
+        traverse(node[2], function(node2, type) {
+          if (type in LOOP_FLOW && node2[1] == ident) {
+            return [node2[0]];
+          }
+        });
+        return node[2]; // Remove the label itself on the loop
+      }
+    });
+  }
+
+  // Eliminate unneeded breaks and continues, when we would get to that place anyhow
+  function loopMotionOptimizer(ast) {} // TODO
+
+  loopLabelOptimizer(ast);
+  loopMotionOptimizer(ast);
+}
+
 // Passes table
 
 var passes = {
   unGlobalize: unGlobalize,
   removeAssignsToUndefined: removeAssignsToUndefined,
   //removeUnneededLabelSettings: removeUnneededLabelSettings,
-  simplifyNotComps: simplifyNotComps
+  simplifyNotComps: simplifyNotComps,
+  loopOptimizer: loopOptimizer
 };
 
 // Main
 
 var src = fs.readFileSync('/dev/stdin').toString();
 var ast = uglify.parser.parse(src);
-//print(JSON.stringify(ast));
+//printErr(JSON.stringify(ast)); throw 1;
 var metadata = src.split('\n').filter(function(line) { return line.indexOf('EMSCRIPTEN_GENERATED_FUNCTIONS') >= 0 })[0];
 //assert(metadata, 'Must have EMSCRIPTEN_GENERATED_FUNCTIONS metadata');
-//generatedFunctions = set(eval(metadata.replace(GENERATED_FUNCTIONS_MARKER, '')))
+if (metadata) setGeneratedFunctions(metadata);
 
 arguments.forEach(function(arg) {
   passes[arg](ast);
diff --git a/tools/test-js-optimizer-output.js b/tools/test-js-optimizer-output.js
index 73680540..3148fb55 100644
--- a/tools/test-js-optimizer-output.js
+++ b/tools/test-js-optimizer-output.js
@@ -36,4 +36,46 @@ zzz = (function(nada) {
 function expr() {
   if ($0 >= $1) print("hi");
 }
-// EMSCRIPTEN_GENERATED_FUNCTIONS: ["abc", "xyz", "xyz2", "expr"]
+function loopy() {
+  $while_body$2 : while (1) {
+    $ok = 1;
+    while (1) {
+      if ($ok) break;
+      var $inc = $ok + 1;
+      if ($inc == 9999) break $while_body$2;
+    }
+    continue;
+  }
+  next();
+  while (1) {
+    $ok = 1;
+    while (1) {
+      if ($ok) break;
+      var $inc = $ok + 1;
+    }
+    continue;
+  }
+  next();
+  do {
+    if (!$ok) break;
+    something();
+  } while (0);
+  next();
+  b$once : do {
+    while (more()) {
+      if (!$ok) break b$once;
+    }
+    something();
+  } while (0);
+  next();
+  do {
+    something();
+  } while (0);
+}
+function ignoreLoopy() {
+  b$for_cond$4 : while (1) {
+    if ($ok) break b$for_cond$4;
+    var $inc = $ok + 1;
+  }
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["abc", "xyz", "xyz2", "expr", "loopy"]
diff --git a/tools/test-js-optimizer.js b/tools/test-js-optimizer.js
index 75679a3a..6b9bacb7 100644
--- a/tools/test-js-optimizer.js
+++ b/tools/test-js-optimizer.js
@@ -38,5 +38,47 @@ zzz = function(nada) {
 function expr() {
   if (!($0 < $1)) print("hi");
 }
-// EMSCRIPTEN_GENERATED_FUNCTIONS: ["abc", "xyz", "xyz2", "expr"]
+function loopy() {
+  $while_body$2: while(1) { 
+    $ok=1;
+    $for_cond$4: while(1) { 
+      if ($ok) break $for_cond$4;
+      var $inc=$ok+1;
+      if ($inc == 9999) break $while_body$2; // this forces a label to remain on the outer loop
+    }
+    continue $while_body$2;
+  }
+  next();
+  b$while_body$2: while(1) { 
+    $ok=1;
+    b$for_cond$4: while(1) {
+      if ($ok) break b$for_cond$4;
+      var $inc=$ok+1;
+    }
+    continue b$while_body$2;
+  }
+  next();
+  $once: do {
+    if (!$ok) break $once; // forces the entire one-time do to remain (but unlabelled)
+    something();
+  } while(0);
+  next();
+  b$once: do {
+    while (more()) {
+      if (!$ok) break b$once; // forces the entire one-time do to remain, with label
+    }
+    something();
+  } while(0);
+  next();
+  c$once: do {
+    something();
+  } while(0);
+}
+function ignoreLoopy() {
+  b$for_cond$4: while(1) {
+    if ($ok) break b$for_cond$4;
+    var $inc=$ok+1;
+  }
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["abc", "xyz", "xyz2", "expr", "loopy"]