add memory-growth safe eliminator mode

3 files changed, 199 insertions, 2 deletions

diff --git a/tools/eliminator/safe-eliminator-test-output.js b/tools/eliminator/safe-eliminator-test-output.js
new file mode 100644
index 00000000..bb3f17e6
--- /dev/null
+++ b/tools/eliminator/safe-eliminator-test-output.js
@@ -0,0 +1,86 @@
+function a($directory) {
+  chak($directory + _strlen($directory) | 0);
+  var $210 = HEAP32[100];
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $210;
+  chak();
+  var $210a = HEAP32[100];
+  something();
+  HEAP32[90] = $210a;
+  chak();
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $hack;
+  chak();
+  var $b = HEAP32[11] + 7 | 0;
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $b;
+  chak();
+  var $bb2 = HEAP32[11];
+  HEAP32[111] = 321;
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $bb2 + 7 | 0;
+  chak();
+  HEAP32[1e3] = HEAP32[100];
+  chak();
+  var $e = func();
+  HEAP32[1e3] = $e;
+  chak();
+  tor(func());
+  chak();
+  tor(HEAP[9]);
+  barrier();
+  var $$210, $$210a, $$b, $$bb2, $$e;
+  $$210 = HEAP32[100];
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$210;
+  chak();
+  $$210a = HEAP32[100];
+  something();
+  HEAP32[90] = $$210a;
+  chak();
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$hack;
+  chak();
+  $$b = HEAP32[11] + 7 | 0;
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$b;
+  chak();
+  $$bb2 = HEAP32[11];
+  HEAP32[111] = 321;
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$bb2 + 7 | 0;
+  chak();
+  HEAP32[1e3] = HEAP32[100];
+  chak();
+  $$e = func();
+  HEAP32[1e3] = $$e;
+  chak();
+  tor(func());
+  chak();
+  tor(HEAP[9]);
+  barrier();
+  var $65, $image, $51$s2, $71;
+  var $71 = HEAP32[$65 >> 2] - _int_ceildiv(HEAP32[$image >> 2], HEAP32[$51$s2]) | 0;
+  HEAP32[$65 >> 2] = _int_ceildivpow2($71, HEAP32[$51$s2 + 10]);
+  barr();
+  var ONCE = sheep();
+  while (ONCE) {
+    work();
+  }
+  var ONCEb = 75;
+  while (ONCEb) {
+    work();
+  }
+  var $26 = __ZL3minIiET_S0_S0_12(4096, 4096 - $16 | 0);
+  print(FUNCTION_TABLE[$22]($18, $16 + ($this + 27) | 0, $26));
+  chak();
+  do {
+    print(10);
+  } while (0);
+  var zzz1 = 10;
+  do {
+    print(zzz1);
+  } while (1);
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["a"]
+
diff --git a/tools/eliminator/safe-eliminator-test.js b/tools/eliminator/safe-eliminator-test.js
new file mode 100644
index 00000000..a181fb8a
--- /dev/null
+++ b/tools/eliminator/safe-eliminator-test.js
@@ -0,0 +1,103 @@
+function a($directory) {
+  var $1 = _strlen($directory);
+  var $p_0 = $directory + $1 | 0;
+  chak($p_0);
+  var $210 = HEAP32[100]; // heaps alias each other! so this cannot be eliminated
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $210;
+  chak();
+  var $210a = HEAP32[100]; // function calls can also modify memory
+  something();
+  HEAP32[90] = $210a;
+  chak();
+  var $a = $hack; // no mem use (just a global), so ok to eliminate
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $a;
+  chak();
+  var $bb = HEAP32[11]; // ok to eliminate
+  var $b = ($bb+7)|0; // ok to eliminate by itself, but not with inlined $bb which is mem-using!
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $b;
+  chak();
+  var $bb2 = HEAP32[11];
+  HEAP32[111] = 321;
+  var $b2 = ($bb2+7)|0;
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $b2;
+  chak();
+  var $d = HEAP32[100]; // alias on next line, but that is where we are consumed - so ok.
+  HEAP32[1e3] = $d;
+  chak();
+  var $e = func();
+  HEAP32[1e3] = $e;
+  chak();
+  var $e2 = func();
+  tor($e2);
+  chak();
+  var $e3 = HEAP[9];
+  tor($e3);
+  barrier(); // same stuff, but with a var on top and assigns as the first and only def
+  var $$210, $$210a, $$a, $$bb, $$b, $$bb2, $$b2, $$d, $$e, $$e2, $$e3;
+  $$210 = HEAP32[100]; // heaps alias each other! so this cannot be eliminated
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$210;
+  chak();
+  $$210a = HEAP32[100]; // function calls can also modify memory
+  something();
+  HEAP32[90] = $$210a;
+  chak();
+  $$a = $$hack; // no mem use, so ok to eliminate
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$a;
+  chak();
+  $$bb = HEAP32[11]; // ok to eliminate
+  $$b = ($$bb+7)|0; // ok to eliminate by itself, but not with inlined $$bb which is mem-using!
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$b;
+  chak();
+  $$bb2 = HEAP32[11];
+  HEAP32[111] = 321;
+  $$b2 = ($$bb2+7)|0;
+  HEAP32[1e3] = HEAP32[5];
+  HEAP32[90] = $$b2;
+  chak();
+  $$d = HEAP32[100]; // alias on next line, but that is where we are consumed - so ok.
+  HEAP32[1e3] = $$d;
+  chak();
+  $$e = func();
+  HEAP32[1e3] = $$e;
+  chak();
+  $$e2 = func();
+  tor($$e2);
+  chak();
+  $$e3 = HEAP[9];
+  tor($$e3);
+  barrier();
+  var $65, $image, $51$s2, $71;
+  var $66 = HEAP32[$65 >> 2];
+  var $71 = $66 - _int_ceildiv(HEAP32[$image >> 2], HEAP32[$51$s2]) | 0;
+  HEAP32[$65 >> 2] = _int_ceildivpow2($71, HEAP32[$51$s2 + 10]);
+  barr();
+  var ONCE = sheep();
+  while (ONCE) {
+    work();
+  }
+  var ONCEb = 75;
+  while (ONCEb) {
+    work();
+  }
+  var $26 = __ZL3minIiET_S0_S0_12(4096, 4096 - $16 | 0); // cannot eliminate this because the call might modify FUNCTION_TABLE
+  var $27 = FUNCTION_TABLE[$22]($18, $this + ($16 + 27) | 0, $26);
+  print($27);
+  chak();
+  var zzz = 10;
+  do {
+    print(zzz);
+  } while (0);
+  var zzz1 = 10;
+  do {
+    print(zzz1);
+  } while (1); // cannot eliminate a do-while that is not one-time
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["a"]
+
diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 222bd0f4..e62402a9 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -1396,13 +1396,16 @@ function registerize(ast) {
 //  FUNCTION_TABLE[x]();
 //
 // to be optimized (f could replace FUNCTION_TABLE, so in general JS eliminating x is not valid).
+//
+// In memSafe mode, we are more careful and assume functions can replace HEAP and FUNCTION_TABLE, which
+// can happen in ALLOW_MEMORY_GROWTH mode
 
 var ELIMINATION_SAFE_NODES = set('var', 'assign', 'call', 'if', 'toplevel', 'do', 'return'); // do is checked carefully, however
 var NODES_WITHOUT_ELIMINATION_SIDE_EFFECTS = set('name', 'num', 'string', 'binary', 'sub', 'unary-prefix');
 var IGNORABLE_ELIMINATOR_SCAN_NODES = set('num', 'toplevel', 'string', 'break', 'continue', 'dot'); // dot can only be STRING_TABLE.*
 var ABORTING_ELIMINATOR_SCAN_NODES = set('new', 'object', 'function', 'defun', 'switch', 'for', 'while', 'array', 'throw'); // we could handle some of these, TODO, but nontrivial (e.g. for while, the condition is hit multiple times after the body)
 
-function eliminate(ast) {
+function eliminate(ast, memSafe) {
   // Find variables that have a single use, and if they can be eliminated, do so
   traverseGeneratedFunctions(ast, function(func, type) {
     //printErr('eliminate in ' + func[1]);
@@ -1613,7 +1616,7 @@ function eliminate(ast) {
             }
           }
         } else if (type == 'sub') {
-          traverseInOrder(node[1], false, true); // evaluate inner
+          traverseInOrder(node[1], false, !memSafe); // evaluate inner
           traverseInOrder(node[2]); // evaluate outer
           if (!ignoreSub) { // ignoreSub means we are a write (happening later), not a read
             // do the memory access
@@ -1834,6 +1837,10 @@ function eliminate(ast) {
   new ExpressionOptimizer(ast).run();
 }
 
+function eliminateMemSafe(ast) {
+  eliminate(ast, true);
+}
+
 // Passes table
 
 var compress = false, printMetadata = true;
@@ -1852,6 +1859,7 @@ var passes = {
   loopOptimizer: loopOptimizer,
   registerize: registerize,
   eliminate: eliminate,
+  eliminateMemSafe: eliminateMemSafe,
   compress: function() { compress = true; },
   noPrintMetadata: function() { printMetadata = false; }
 };