make shift optimizer output more similar to normal output

3 files changed, 62 insertions, 19 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index 1764f4b7..3bfa3c8b 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -543,8 +543,8 @@ function optimizeShifts(ast) {
         }
       }, null, []);
       cleanNotes();
-      var more = true;
       var SIMPLE_SHIFTS = set('<<', '>>');
+      var more = true;
       while (more) { // collapse shifts and unshifts, completing the optimization
         more = false;
         traverse(fun, function(node, type) {
@@ -590,7 +590,7 @@ function optimizeShifts(ast) {
             return subNode;
           }
         }
-        // Optimize the case of ($a*80)>>2
+        // Optimize the case of ($a*80)>>2 into ($a*20)|0
         if (type == 'binary' && node[1] in SIMPLE_SHIFTS &&
             node[2][0] == 'binary' && node[2][1] == '*') {
           var mulNode = node[2];
@@ -602,11 +602,15 @@ function optimizeShifts(ast) {
           if (mulNode[3][0] == 'num') {
             if (node[1] == '<<') {
               mulNode[3][1] *= Math.pow(2, node[3][1]);
-              return mulNode;
+              node[1] = '|';
+              node[3][1] = 0;
+              return node;
             } else {
               if (mulNode[3][1] % Math.pow(2, node[3][1]) == 0) {
                 mulNode[3][1] /= Math.pow(2, node[3][1]);
-                return mulNode;
+                node[1] = '|';
+                node[3][1] = 0;
+                return node;
               }
             }
           }
@@ -615,7 +619,7 @@ function optimizeShifts(ast) {
       // Re-combine remaining shifts, to undo the breaking up we did before. may require reordering inside +'s
       traverse(fun, function(node, type, stack) {
         stack.push(node);
-        if (type == 'binary' && node[1] == '+') {
+        if (type == 'binary' && node[1] == '+' && (stack[stack.length-2][0] != 'binary' || stack[stack.length-2][1] != '+')) {
           // 'Flatten' added items
           var addedItems = [];
           function flatten(node) {
@@ -636,6 +640,7 @@ function optimizeShifts(ast) {
               if (node[3][0] == 'num' && node[3][1] >= 0 && node[3][1] <= 3) return 2*node[3][1] + (node[1] == '>>' ? 100 : 0); // 0-106
               return (node[1] == '>>' ? 20000 : 10000) + originalOrderKey(node);
             }
+            if (node[0] == 'num') return -20000 + node[1];
             return -10000 + originalOrderKey(node); // Don't modify the original order if we don't modify anything
           }
           for (var i = 0; i < addedItems.length; i++) {
@@ -655,6 +660,29 @@ function optimizeShifts(ast) {
               i++;
             }
           }
+          var num = 0;
+          for (i = 0; i < addedItems.length; i++) { // combine all numbers into one
+            if (addedItems[i][0] == 'num') {
+              num += addedItems[i][1];
+              addedItems.splice(i, 1);
+              i--;
+            }
+          }
+          if (num != 0) { // add the numbers into an existing shift, we 
+                          // prefer (x+5)>>7 over (x>>7)+5 , since >>'s result is known to be 32-bit and is more easily optimized.
+                          // Also, in the former we can avoid the parentheses, which saves a little space (the number will be bigger,
+                          // so it might take more space, but normally at most one more digit).
+            var added = false;
+            for (i = 0; i < addedItems.length; i++) {
+              if (addedItems[i][0] == 'binary' && addedItems[i][1] == '>>' && addedItems[i][3][0] == 'num') {
+                addedItems[i] = ['binary', '>>', ['binary', '+', addedItems[i][2], ['num', num << addedItems[i][3][1]]], addedItems[i][3]];
+                added = true;
+              }
+            }
+            if (!added) {
+              addedItems.unshift(['num', num]);
+            }
+          }
           var ret = addedItems.pop();
           while (addedItems.length > 0) { // re-create AST from addedItems
             ret = ['binary', '+', ret, addedItems.pop()];
diff --git a/tools/test-js-optimizer-t2-output.js b/tools/test-js-optimizer-t2-output.js
index ea384e07..7a676fbe 100644
--- a/tools/test-js-optimizer-t2-output.js
+++ b/tools/test-js-optimizer-t2-output.js
@@ -24,9 +24,9 @@ function shifty($id) {
   q($id3);
   pause(0);
   var _idents = get("abc") >> 2;
-  q(HEAP32[(HEAP32[_idents] >> 2) + 2]);
-  q(HEAP32[(HEAP32[_idents] >> 2) + 2]);
-  q(HEAP32[(HEAP32[_idents] >> 2) + 2]);
+  q(HEAP32[HEAP32[_idents] + 8 >> 2]);
+  q(HEAP32[HEAP32[_idents] + 8 >> 2]);
+  q(HEAP32[HEAP32[_idents] + 8 >> 2]);
   pause(1);
   var $sn_addr = get(12), $a_addr = get(999), $a_addr$s2 = $a_addr >> 2;
   var $i = get(112233);
@@ -40,24 +40,24 @@ function shifty($id) {
   pause(2);
   var $level = HEAP[get(322) >> 2];
   var _dwt_norms_real = get("a") >> 2, $orient = get("cheez");
-  q(HEAP32[($level << 1) + _dwt_norms_real + $orient * 20]);
-  q(HEAP32[($level << 1) + _dwt_norms_real + $orient * 20 + 1]);
-  q(HEAP32[($level << 1) + _dwt_norms_real + $orient * 20 + 2]);
+  q(HEAP32[($level << 1) + _dwt_norms_real + ($orient * 20 | 0)]);
+  q(HEAP32[($level << 1) + _dwt_norms_real + ($orient * 20 | 0) + 1]);
+  q(HEAP32[($level << 1) + _dwt_norms_real + ($orient * 20 | 0) + 2]);
   pause(3);
   var $wavelet38 = get(38) >> 2;
   $k = $a_addr;
-  q(HEAPF32[(HEAP32[$wavelet38] >> 2) + ($k << 2) + 2]);
-  q(HEAPF32[(HEAP32[$wavelet38] >> 2) + ($k << 2) + 3]);
-  q(HEAPF32[(HEAP32[$wavelet38] >> 2) + ($k << 2) + 100]);
+  q(HEAPF32[(HEAP32[$wavelet38] + 8 >> 2) + ($k << 2)]);
+  q(HEAPF32[(HEAP32[$wavelet38] + 12 >> 2) + ($k << 2)]);
+  q(HEAPF32[(HEAP32[$wavelet38] + 400 >> 2) + ($k << 2)]);
   pause(4);
   var $p = $k, $parameters_addr = get("burger") >> 2;
-  q(HEAP32[$parameters_addr + 1406 + $p]);
-  q(HEAP32[$parameters_addr + 1411 + $p]);
-  q(HEAP32[$parameters_addr + 1416 + $p]);
+  q(HEAP32[$parameters_addr + $p + 1406]);
+  q(HEAP32[$parameters_addr + $p + 1411]);
+  q(HEAP32[$parameters_addr + $p + 1416]);
   pause(5);
   var $res_spec242 = get($real), $cp = get("b"), $tileno = arguments[2];
-  q(HEAP32[$parameters_addr + 1406 + ($res_spec242 - 1)]);
-  q(HEAP32[(HEAP32[($cp >> 2) + 27] >> 2) + $tileno * 1397 + 105]);
+  q(HEAP32[$parameters_addr + ($res_spec242 - 1) + 1406]);
+  q(HEAP32[(HEAP32[$cp + 108 >> 2] + 420 >> 2) + ($tileno * 1397 | 0)]);
   pause(6);
   q($idx << 3);
   q(1 << $idx << 1);
@@ -76,5 +76,12 @@ function shifty($id) {
   q(go());
   q(go() >> 8 << 8);
   q(go() + 2 >> 2);
+  pause(7.5);
+  q($13 + 8 >> 2);
+  q($13 + 28 >> 2);
+  q($13 + 60 >> 2);
+  q($13 + $15 + 12 >> 2);
+  q(HEAPF32[($output + 4 >> 2) + ($j37 << 2)]);
+  q($13 + 13 << 2);
 }
 // EMSCRIPTEN_GENERATED_FUNCTIONS: ["shifty"]
diff --git a/tools/test-js-optimizer-t2.js b/tools/test-js-optimizer-t2.js
index f7bda9ea..167c1f47 100644
--- a/tools/test-js-optimizer-t2.js
+++ b/tools/test-js-optimizer-t2.js
@@ -82,5 +82,13 @@ function shifty($id) {
   q(go() >> 1 << 1);
   q(go() >> 8 << 8);
   q((go() + 2) >> 2); // the 2 >> 2 can't be simplified
+  pause(7.5);
+  // We prefer to do additions then shifts, so the shift happens last, because the shift output is known to be 32-bit. So these should not change
+  q($13 + 8 >> 2);
+  q(28 + $13 >> 2);
+  q(48 + $13 + 12 >> 2);
+  q($13 + $15 + 12 >> 2);
+  q(HEAPF32[$output + ($j37 << 4) + 4 >> 2]);
+  q(5 + $13 + 8 << 2);
 }
 // EMSCRIPTEN_GENERATED_FUNCTIONS: ["shifty"]