conditionalize when it can avoid costly side-effect free code

3 files changed, 184 insertions, 1 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 2914b6e8..678ba0d5 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -749,11 +749,64 @@ function simplifyExpressions(ast) {
     });
   }
 
+  //   expensive | expensive can be turned into expensive ? 1 : expensive, and
+  //   expensive | cheap     can be turned into cheap     ? 1 : expensive,
+  // so that we can avoid the expensive computation, if it has no side effects.
+  function conditionalize(ast) {
+    var MIN_COST = 4;
+    traverse(ast, function(node, type) {
+      if (type === 'if' || type === 'while') {
+        var cond = node[1];
+        if (cond[0] === 'binary' && (cond[1] === '|' || cond[1] === '&') && cond[3][0] !== 'num' && cond[2][0] !== 'num') {
+          // logical operator on two non-numerical values, all inside a condition
+          var left = cond[2];
+          var right = cond[3];
+          var leftEffects = hasSideEffects(left);
+          var rightEffects = hasSideEffects(right);
+          if (leftEffects && rightEffects) return; // both must execute
+          // canonicalize with side effects, if any, happening on the left
+          if (rightEffects) {
+            if (measureCost(left) < MIN_COST) return; // avoidable code is too cheap
+            var temp = left;
+            left = right;
+            right = temp;
+          } else if (leftEffects) {
+            if (measureCost(right) < MIN_COST) return; // avoidable code is too cheap
+          } else {
+            // no side effects, reorder based on cost estimation
+            var leftCost = measureCost(left);
+            var rightCost = measureCost(right);
+            if (Math.max(leftCost, rightCost) < MIN_COST) return; // avoidable code is too cheap
+            // canonicalize with expensive code on the right
+            if (leftCost > rightCost) {
+              var temp = left;
+              left = right;
+              right = temp;
+            }
+          }
+          // worth it, perform conditionalization
+          if (cond[1] === '|') {
+            node[1] = ['conditional', left, ['num', 1], right];
+          } else { // &
+            node[1] = ['conditional', left, right, ['num', 0]];
+          }
+          if (left[0] === 'unary-prefix' && left[1] === '!') {
+            node[1][1] = flipCondition(left);
+            var temp = node[1][2];
+            node[1][2] = node[1][3];
+            node[1][3] = temp;
+          }
+        }
+      }
+    });
+  }
+
   traverseGeneratedFunctions(ast, function(func) {
     simplifyIntegerConversions(func);
     simplifyBitops(func);
     joinAdditions(func);
     simplifyNotComps(func);
+    conditionalize(func);
     // simplifyZeroComp(func); TODO: investigate performance
   });
 }
@@ -3921,6 +3974,18 @@ function measureSize(ast) {
   return size;
 }
 
+function measureCost(ast) {
+  var size = 0;
+  traverse(ast, function(node, type) {
+    if (type === 'num' || type === 'unary-prefix') size--;
+    else if (type === 'binary' && node[3][0] === 'num' && node[3][1] === 0) size--;
+    else if (type === 'call' && !callHasSideEffects(node)) size -= 2;
+    else if (type === 'sub') size++;
+    size++;
+  });
+  return size;
+}
+
 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
diff --git a/tools/test-js-optimizer-asm-pre-output.js b/tools/test-js-optimizer-asm-pre-output.js
index c9746e78..ce45645c 100644
--- a/tools/test-js-optimizer-asm-pre-output.js
+++ b/tools/test-js-optimizer-asm-pre-output.js
@@ -538,4 +538,63 @@ function fcomp() {
  if (5 >= ($b | 0)) return 5;
  if (5 >= 5) return 5;
 }
+function conditionalizeMe() {
+ if (x > 1 ? x + y + z + w > 12 : 0) {
+  b();
+ }
+ if (a() > 1 ? x + y + z + w > 12 : 0) {
+  b();
+ }
+ if (x > 1 & x + y + z + k() > 12) {
+  b();
+ }
+ if (a() > 1 & x + y + z + k() > 12) {
+  b();
+ }
+ if (x > 1 ? 1 : x + y + z + w > 12) {
+  b();
+ }
+ if (a() > 1 ? 1 : x + y + z + w > 12) {
+  b();
+ }
+ if (x > 1 | x + y + z + k() > 12) {
+  b();
+ }
+ if (a() > 1 | x + y + z + k() > 12) {
+  b();
+ }
+ if (x > 1 ? 1 : x + y + z + w > 12) {
+  b();
+ }
+ if (a() > 1 ? 1 : x + y + z + w > 12) {
+  b();
+ }
+ if (x + y + z + k() > 12 | x > 1) {
+  b();
+ }
+ if (x + y + z + k() > 12 | a() > 1) {
+  b();
+ }
+ while (x > 1 ? x + y + z + w > 12 : 0) {
+  b();
+ }
+ while (a() > 1 ? x + y + z + w > 12 : 0) {
+  b();
+ }
+ while (x > 1 & x + y + z + k() > 12) {
+  b();
+ }
+ while (a() > 1 & x + y + z + k() > 12) {
+  b();
+ }
+ if (!($sub$i480 >= Math_fround(+0)) | !($sub4$i483 >= Math_fround(+0))) {
+  b();
+ }
+ if ($sub$i480 >= Math_fround(+0) ? !($sub4$i483 >= Math_fround(HEAPF32[x + y | 0])) : 1) {
+  b();
+ }
+ if (x > 10 ? 1 : HEAP[20] > 5) {
+  b();
+ }
+}
 
diff --git a/tools/test-js-optimizer-asm-pre.js b/tools/test-js-optimizer-asm-pre.js
index 00ebd7d7..b9773bb5 100644
--- a/tools/test-js-optimizer-asm-pre.js
+++ b/tools/test-js-optimizer-asm-pre.js
@@ -550,4 +550,63 @@ function fcomp() {
  if (!(5 < ($b|0))) return 5;
  if (!(5 < 5)) return 5;
 }
-// EMSCRIPTEN_GENERATED_FUNCTIONS: ["a", "b", "rett", "ret2t", "retf", "i32_8", "tempDoublePtr", "boxx", "_main", "badf", "badf2", "fcomp"]
+function conditionalizeMe() {
+ if ((x > 1) & (x+y+z+w > 12)) {
+  b();
+ }
+ if ((a() > 1) & (x+y+z+w > 12)) {
+  b();
+ }
+ if ((x > 1) & (x+y+z+k() > 12)) {
+  b();
+ }
+ if ((a() > 1) & (x+y+z+k() > 12)) {
+  b();
+ }
+ if ((x > 1) | (x+y+z+w > 12)) {
+  b();
+ }
+ if ((a() > 1) | (x+y+z+w > 12)) {
+  b();
+ }
+ if ((x > 1) | (x+y+z+k() > 12)) {
+  b();
+ }
+ if ((a() > 1) | (x+y+z+k() > 12)) {
+  b();
+ }
+ if ((x+y+z+w > 12) | (x > 1)) {
+  b();
+ }
+ if ((x+y+z+w > 12) | (a() > 1)) {
+  b();
+ }
+ if ((x+y+z+k() > 12) | (x > 1)) {
+  b();
+ }
+ if ((x+y+z+k() > 12) | (a() > 1)) {
+  b();
+ }
+ while ((x > 1) & (x+y+z+w > 12)) {
+  b();
+ }
+ while ((a() > 1) & (x+y+z+w > 12)) {
+  b();
+ }
+ while ((x > 1) & (x+y+z+k() > 12)) {
+  b();
+ }
+ while ((a() > 1) & (x+y+z+k() > 12)) {
+  b();
+ }
+ if (!($sub$i480 >= Math_fround(+0)) | !($sub4$i483 >= Math_fround(+0))) {
+  b();
+ }
+ if (!($sub$i480 >= Math_fround(+0)) | !($sub4$i483 >= Math_fround(HEAPF32[x+y|0]))) {
+  b();
+ }
+ if (x > 10 | HEAP[20] > 5) {
+  b();
+ }
+}
+// EMSCRIPTEN_GENERATED_FUNCTIONS: ["a", "b", "rett", "ret2t", "retf", "i32_8", "tempDoublePtr", "boxx", "_main", "badf", "badf2", "fcomp", "conditionalizeMe"]