remove stack parameter from js optimizer traverse(), to avoid overhead when not needed

1 files changed, 15 insertions, 432 deletions

diff --git a/tools/js-optimizer.js b/tools/js-optimizer.js
index a4c05b70..086ed30e 100644
--- a/tools/js-optimizer.js
+++ b/tools/js-optimizer.js
@@ -169,11 +169,11 @@ function astToSrc(ast, minifyWhitespace) {
 
 // Traverses the children of a node. If the traverse function returns an object,
 // replaces the child. If it returns true, stop the traversal and return true.
-function traverseChildren(node, traverse, pre, post, stack) {
+function traverseChildren(node, traverse, pre, post) {
   for (var i = 0; i < node.length; i++) {
     var subnode = node[i];
     if (Array.isArray(subnode)) {
-      var subresult = traverse(subnode, pre, post, stack);
+      var subresult = traverse(subnode, pre, post);
       if (subresult === true) return true;
       if (subresult !== null && typeof subresult === 'object') node[i] = subresult;
     }
@@ -189,30 +189,24 @@ function traverseChildren(node, traverse, pre, post, stack) {
 //     it replaces the passed node in the tree. If null is returned, we stop
 //     traversing the subelements (but continue otherwise).
 //   @arg post: A callback to call after traversing all children.
-//   @arg stack: If true, a stack will be implemented: If pre does not push on
-//               the stack, we push a 0. We pop when we leave the node. The
-//               stack is passed as a third parameter to the callbacks.
 //   @returns: If the root node was replaced, the new root node. If the traversal
 //     was stopped, true. Otherwise undefined.
-function traverse(node, pre, post, stack) {
+function traverse(node, pre, post) {
   var type = node[0], result, len;
   var relevant = typeof type === 'string';
   if (relevant) {
-    if (stack) len = stack.length;
-    var result = pre(node, type, stack);
+    var result = pre(node, type);
     if (result === true) return true;
     if (result && result !== null) node = result; // Continue processing on this node
-    if (stack && len === stack.length) stack.push(0);
   }
   if (result !== null) {
-    if (traverseChildren(node, traverse, pre, post, stack) === true) return true;
+    if (traverseChildren(node, traverse, pre, post) === true) return true;
   }
   if (relevant) {
     if (post) {
-      var postResult = post(node, type, stack);
+      var postResult = post(node, type);
       result = result || postResult;
     }
-    if (stack) stack.pop();
   }
   return result;
 }
@@ -231,38 +225,12 @@ function traverseGeneratedFunctions(ast, callback) {
   }
 }
 
-function traverseGenerated(ast, pre, post, stack) {
+function traverseGenerated(ast, pre, post) {
   traverseGeneratedFunctions(ast, function(func) {
-    traverse(func, pre, post, stack);
+    traverse(func, pre, post);
   });
 }
 
-// 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) {
-    if (type in FUNCTION) {
-      stack.push({ type: 'function', vars: node[2] });
-    } else if (type === 'var') {
-      // Find our function, add our vars
-      var func = stack[stack.length-1];
-      if (func) {
-        func.vars = func.vars.concat(node[1].map(function(varItem) { return varItem[0] }));
-      }
-    }
-  }, function(node, type, stack) {
-    if (type === 'toplevel' || type in FUNCTION) {
-      // We know all of the variables that are seen here, proceed to do relevant replacements
-      var allVars = stack.map(function(item) { return item ? item.vars : [] }).reduce(concatenator, []); // FIXME dictionary for speed?
-      traverse(node, function(node2, type2, stack2) {
-        // Be careful not to look into our inner functions. They have already been processed.
-        if (sum(stack2) > 1 || (type === 'toplevel' && sum(stack2) === 1)) return;
-        if (type2 in FUNCTION) stack2.push(1);
-        return callback(node2, type2, allVars);
-      }, null, []);
-    }
-  }, []);
-}
-
 function emptyNode() { // XXX do we need to create new nodes here? can't we reuse?
   return ['toplevel', []]
 }
@@ -327,58 +295,6 @@ function dumpSrc(ast) {
   printErr(astToSrc(ast));
 }
 
-// Undos closure's creation of global variables with values true, false,
-// undefined, null. These cut down on size, but do not affect gzip size
-// and make JS engine's lives slightly harder (?)
-function unGlobalize(ast) {
-
-  throw 'this is deprecated!'; // and does not work with parallel compilation
-
-  assert(ast[0] === 'toplevel');
-  var values = {};
-  // Find global renamings of the relevant values
-  ast[1].forEach(function(node, i) {
-    if (node[0] != 'var') return;
-    node[1] = node[1].filter(function(varItem, j) {
-      var ident = varItem[0];
-      var value = varItem[1];
-      if (!value) return true;
-      var possible = false;
-      if (jsonCompare(value, NULL_NODE) ||
-          jsonCompare(value, UNDEFINED_NODE) ||
-          jsonCompare(value, TRUE_NODE) ||
-          jsonCompare(value, FALSE_NODE)) {
-        possible = true;
-      }
-      if (!possible) return true;
-      // Make sure there are no assignments to this variable. (This isn't fast, we traverse many times..)
-      ast[1][i][1][j] = emptyNode();
-      var assigned = false;
-      traverseWithVariables(ast, function(node, type, allVars) {
-        if (type === 'assign' && node[2][0] === 'name' && node[2][1] === ident) assigned = true;
-      });
-      ast[1][i][1][j] = [ident, value];
-      if (!assigned) {
-        values[ident] = value;
-        return false;
-      }
-      return true;
-    });
-
-    if (node[1].length === 0) {
-      ast[1][i] = emptyNode();
-    }
-  });
-  traverseWithVariables(ast, function(node, type, allVars) {
-    if (type === 'name') {
-      var ident = node[1];
-      if (ident in values && allVars.indexOf(ident) < 0) {
-        return copy(values[ident]);
-      }
-    }
-  });
-}
-
 // Closure compiler, when inlining, will insert assignments to
 // undefined for the shared variables. However, in compiled code
 // - and in library/shell code too! - we should never rely on
@@ -505,10 +421,12 @@ function simplifyExpressions(ast) {
       var rerun = true;
       while (rerun) {
         rerun = false;
-        traverse(ast, function process(node, type, stack) {
+        var stack = [];
+        traverse(ast, function process(node, type) {
           if (type === 'binary' && node[1] === '|') {
             if (node[2][0] === 'num' && node[3][0] === 'num') {
               node[2][1] |= node[3][1];
+              stack.push(0);
               return node[2];
             }
             var go = false;
@@ -541,7 +459,7 @@ function simplifyExpressions(ast) {
                   node[j] = result[j];
                 }
                 rerun = true;
-                return process(result, result[0], stack);
+                return process(result, result[0]);
               } else if (stack[i] === -1) {
                 break; // Too bad, we can't
               }
@@ -557,7 +475,9 @@ function simplifyExpressions(ast) {
           } else {
             stack.push(-1); // This node is dangerous! Give up if you see this before you see '1'
           }
-        }, null, []);
+        }, function() {
+          stack.pop();
+        });
       }
     }
 
@@ -992,340 +912,6 @@ function simplifyIfs(ast) {
   });
 }
 
-
-// In typed arrays mode 2, we can have
-//  HEAP[x >> 2]
-// very often. We can in some cases do the shift on the variable itself when it is set,
-// to greatly reduce the number of shift operations.
-// XXX this optimization is deprecated and currently invalid: does not handle overflows
-//     or non-aligned (round numbers, x >> 2 is a multiple of 4). Both are ok to assume
-//     for pointers (undefined behavior otherwise), but invalid in general, and we do
-//     no sufficiently-well distinguish the cases.
-function optimizeShiftsInternal(ast, conservative) {
-  var MAX_SHIFTS = 3;
-  traverseGeneratedFunctions(ast, function(fun) {
-    var funMore = true;
-    var funFinished = {};
-    while (funMore) {
-      funMore = false;
-      // Recognize variables and parameters
-      var vars = {};
-      function newVar(name, param, addUse) {
-        if (!vars[name]) {
-          vars[name] = {
-            param: param,
-            defs: addUse ? 1 : 0,
-            uses: 0,
-            timesShifted: [0, 0, 0, 0], // zero shifts of size 0, 1, 2, 3
-            benefit: 0,
-            primaryShift: -1
-          };
-        }
-      }
-      // params
-      if (fun[2]) {
-        fun[2].forEach(function(arg) {
-          newVar(arg, true, true);
-        });
-      }
-      // vars
-      // XXX if var has >>=, ignore it here? That means a previous pass already optimized it
-      var hasSwitch = traverse(fun, function(node, type) {
-        if (type === 'var') {
-          node[1].forEach(function(arg) {
-            newVar(arg[0], false, arg[1]);
-          });
-        } else if (type === 'switch') {
-          // The relooper can't always optimize functions, and we currently don't work with
-          // switch statements when optimizing shifts. Bail.
-          return true;
-        }
-      });
-      if (hasSwitch) {
-        break;
-      }
-      // uses and defs TODO: weight uses by being inside a loop (powers). without that, we
-      // optimize for code size, not speed.
-      traverse(fun, function(node, type, stack) {
-        stack.push(node);
-        if (type === 'name' && vars[node[1]] && stack[stack.length-2][0] != 'assign') {
-          vars[node[1]].uses++;
-        } else if (type === 'assign' && node[2][0] === 'name' && vars[node[2][1]]) {
-          vars[node[2][1]].defs++;
-        }
-      }, null, []);
-      // First, break up elements inside a shift. This lets us see clearly what to do next.
-      traverse(fun, function(node, type) {
-        if (type === 'binary' && node[1] === '>>' && node[3][0] === 'num') {
-          var shifts = node[3][1];
-          if (shifts <= MAX_SHIFTS) {
-            // Push the >> inside the value elements
-            function addShift(subNode) {
-              if (subNode[0] === 'binary' && subNode[1] === '+') {
-                subNode[2] = addShift(subNode[2]);
-                subNode[3] = addShift(subNode[3]);
-                return subNode;
-              }
-              if (subNode[0] === 'name' && !subNode[2]) { // names are returned with a shift, but we also note their being shifted
-                var name = subNode[1];
-                if (vars[name]) {
-                  vars[name].timesShifted[shifts]++;
-                  subNode[2] = true;
-                }
-              }
-              return ['binary', '>>', subNode, ['num', shifts]];
-            }
-            return addShift(node[2]);
-          }
-        }
-      });
-      traverse(fun, function(node, type) {
-        if (node[0] === 'name' && node[2]) {
-          return node.slice(0, 2); // clean up our notes
-        }
-      });
-      // At this point, shifted expressions are split up, and we know who the vars are and their info, so we can decide
-      // TODO: vars that depend on other vars
-      for (var name in vars) {
-        var data = vars[name];
-        var totalTimesShifted = sum(data.timesShifted);
-        if (totalTimesShifted === 0) {
-          continue;
-        }
-        if (totalTimesShifted != Math.max.apply(null, data.timesShifted)) {
-          // TODO: Handle multiple different shifts
-          continue;
-        }
-        if (funFinished[name]) continue;
-        // We have one shift size (and possible unshifted uses). Consider replacing this variable with a shifted clone. If
-        // the estimated benefit is >0, we will do it
-        if (data.defs === 1) {
-          data.benefit = totalTimesShifted - 2*(data.defs + (data.param ? 1 : 0));
-        }
-        if (conservative) data.benefit = 0;
-        if (data.benefit > 0) {
-          funMore = true; // We will reprocess this function
-          for (var i = 0; i < 4; i++) {
-            if (data.timesShifted[i]) {
-              data.primaryShift = i;
-            }
-          }
-        }
-      }
-      //printErr(JSON.stringify(vars));
-      function cleanNotes() { // We need to mark 'name' nodes as 'processed' in some passes here; this cleans the notes up
-        traverse(fun, function(node, type) {
-          if (node[0] === 'name' && node[2]) {
-            return node.slice(0, 2);
-          }
-        });
-      }
-      cleanNotes();
-      // Apply changes
-      function needsShift(name) {
-        return vars[name] && vars[name].primaryShift >= 0;
-      }
-      for (var name in vars) { // add shifts for params and var's for all new variables
-        var data = vars[name];
-        if (needsShift(name)) {
-          if (data.param) {
-            fun[3].unshift(['var', [[name + '$s' + data.primaryShift, ['binary', '>>', ['name', name], ['num', data.primaryShift]]]]]);
-          } else {
-            fun[3].unshift(['var', [[name + '$s' + data.primaryShift]]]);
-          }
-        }
-      }
-      traverse(fun, function(node, type, stack) { // add shift to assignments
-        stack.push(node);
-        if (node[0] === 'assign' && node[1] === true && node[2][0] === 'name' && needsShift(node[2][1]) && !node[2][2]) {
-          var name = node[2][1];
-          var data = vars[name];
-          var parent = stack[stack.length-3];
-          var statements = getStatements(parent);
-          assert(statements, 'Invalid parent for assign-shift: ' + dump(parent));
-          var i = statements.indexOf(stack[stack.length-2]);
-          statements.splice(i+1, 0, ['stat', ['assign', true, ['name', name + '$s' + data.primaryShift], ['binary', '>>', ['name', name, true], ['num', data.primaryShift]]]]);
-        } else if (node[0] === 'var') {
-          var args = node[1];
-          for (var i = 0; i < args.length; i++) {
-            var arg = args[i];
-            var name = arg[0];
-            var data = vars[name];
-            if (arg[1] && needsShift(name)) {
-              args.splice(i+1, 0, [name + '$s' + data.primaryShift, ['binary', '>>', ['name', name, true], ['num', data.primaryShift]]]);
-            }
-          }
-          return node;
-        }
-      }, null, []);
-      cleanNotes();
-      traverse(fun, function(node, type, stack) { // replace shifted name with new variable
-        stack.push(node);
-        if (node[0] === 'binary' && node[1] === '>>' && node[2][0] === 'name' && needsShift(node[2][1]) && node[3][0] === 'num') {
-          var name = node[2][1];
-          var data = vars[name];
-          var parent = stack[stack.length-2];
-          // Don't modify in |x$sN = x >> 2|, in normal assigns and in var assigns
-          if (parent[0] === 'assign' && parent[2][0] === 'name' && parent[2][1] === name + '$s' + data.primaryShift) return;
-          if (parent[0] === name + '$s' + data.primaryShift) return;
-          if (node[3][1] === data.primaryShift) {
-            return ['name', name + '$s' + data.primaryShift];
-          }
-        }
-      }, null, []);
-      cleanNotes();
-      var SIMPLE_SHIFTS = set('<<', '>>');
-      var more = true;
-      while (more) { // combine shifts in the same direction as an optimization
-        more = false;
-        traverse(fun, function(node, type) {
-          if (node[0] === 'binary' && node[1] in SIMPLE_SHIFTS && node[2][0] === 'binary' && node[2][1] === node[1] &&
-              node[3][0] === 'num' && node[2][3][0] === 'num') { // do not turn a << b << c into a << b + c; while logically identical, it is slower
-            more = true;
-            return ['binary', node[1], node[2][2], ['num', node[3][1] + node[2][3][1]]];
-          }
-        });
-      }
-      // Before recombining, do some additional optimizations
-      traverse(fun, function(node, type) {
-        // Apply constant shifts onto constants
-        if (type === 'binary' && node[1] === '>>' && node[2][0] === 'num' && node[3][0] === 'num' && node[3][1] <= MAX_SHIFTS) {
-          var subNode = node[2];
-          var shifts = node[3][1];
-          var result = subNode[1] / Math.pow(2, shifts);
-          if (result % 1 === 0) {
-            subNode[1] = result;
-            return subNode;
-          }
-        }
-        // 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];
-          if (mulNode[2][0] === 'num') {
-            var temp = mulNode[2];
-            mulNode[2] = mulNode[3];
-            mulNode[3] = temp;
-          }
-          if (mulNode[3][0] === 'num') {
-            if (node[1] === '<<') {
-              mulNode[3][1] *= Math.pow(2, node[3][1]);
-              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]);
-                node[1] = '|';
-                node[3][1] = 0;
-                return node;
-              }
-            }
-          }
-        }
-        /* XXX - theoretically useful optimization(s), but commented out as not helpful in practice
-        // Transform (x << 2) >> 2 into x & mask or something even simpler
-        if (type === 'binary'       && node[1]    === '>>' && node[3][0] === 'num' &&
-            node[2][0] === 'binary' && node[2][1] === '<<' && node[2][3][0] === 'num' && node[3][1] === node[2][3][1]) {
-          var subNode = node[2];
-          var shifts = node[3][1];
-          var mask = ((0xffffffff << shifts) >>> shifts) | 0;
-          return ['binary', '&', subNode[2], ['num', mask]];
-          //return ['binary', '|', subNode[2], ['num', 0]];
-          //return subNode[2];
-        }
-        */
-      });
-      // 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] === '+' && (stack[stack.length-2][0] != 'binary' || stack[stack.length-2][1] !== '+')) {
-          // 'Flatten' added items
-          var addedItems = [];
-          function flatten(node) {
-            if (node[0] === 'binary' && node[1] === '+') {
-              flatten(node[2]);
-              flatten(node[3]);
-            } else {
-              addedItems.push(node);
-            }
-          }
-          flatten(node);
-          var originalOrder = addedItems.slice();
-          function key(node) { // a unique value for all relevant shifts for recombining, non-unique for stuff we don't need to bother with
-            function originalOrderKey(item) {
-              return -originalOrder.indexOf(item);
-            }
-            if (node[0] === 'binary' && node[1] in SIMPLE_SHIFTS) {
-              if (node[3][0] === 'num' && node[3][1] <= MAX_SHIFTS) 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++) {
-            if (addedItems[i][0] === 'string') return; // this node is not relevant for us
-          }
-          addedItems.sort(function(node1, node2) {
-            return key(node1) - key(node2);
-          });
-          // Regenerate items, now sorted
-          var i = 0;
-          while (i < addedItems.length-1) { // re-combine inside addedItems
-            var k = key(addedItems[i]), k1 = key(addedItems[i+1]);
-            if (k === k1 && k >= 0 && k1 <= 106) {
-              addedItems[i] = ['binary', addedItems[i][1], ['binary', '+', addedItems[i][2], addedItems[i+1][2]], addedItems[i][3]];
-              addedItems.splice(i+1, 1);
-            } else {
-              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][3][1] <= MAX_SHIFTS) {
-                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()];
-          }
-          return ret;
-        }
-      }, null, []);
-      // Note finished variables
-      for (var name in vars) {
-        funFinished[name] = true;
-      }
-    }
-  });
-}
-
-function optimizeShiftsConservative(ast) {
-  optimizeShiftsInternal(ast, true);
-}
-
-function optimizeShiftsAggressive(ast) {
-  optimizeShiftsInternal(ast, false);
-}
-
 // We often have branchings that are simplified so one end vanishes, and
 // we then get
 //   if (!(x < 5))
@@ -5449,13 +5035,10 @@ var passes = {
   // passes
   dumpAst: dumpAst,
   dumpSrc: dumpSrc,
-  unGlobalize: unGlobalize,
   removeAssignsToUndefined: removeAssignsToUndefined,
   //removeUnneededLabelSettings: removeUnneededLabelSettings,
   simplifyExpressions: simplifyExpressions,
   simplifyIfs: simplifyIfs,
-  optimizeShiftsConservative: optimizeShiftsConservative,
-  optimizeShiftsAggressive: optimizeShiftsAggressive,
   hoistMultiples: hoistMultiples,
   loopOptimizer: loopOptimizer,
   registerize: registerize,