text: // Copyright 2011 The Emscripten Authors.  All rights reserved.
  // Emscripten is available under two separate licenses, the MIT license and the
  // University of Illinois/NCSA Open Source License.  Both these licenses can be
  // found in the LICENSE file.
  //
  // Optimizer tool. This is meant to be run after the emscripten compiler has
  // finished generating code. These optimizations are done on the generated
  // code to further improve it.
  //
  // Be aware that this is *not* a general JS optimizer. It assumes that the
  // input is valid asm.js and makes strong assumptions based on this. It may do
  // anything from crashing to optimizing incorrectly if the input is not valid!
  //
  // TODO: Optimize traverse to modify a node we want to replace, in-place,
  //       instead of returning it to the previous call frame where we check?
  // TODO: Share EMPTY_NODE instead of emptyNode that constructs?
  
  if (!Math.fround) {
    var froundBuffer = new Float32Array(1);
    Math.fround = function(x) { froundBuffer[0] = x; return froundBuffer[0] };
  }
  
  // *** Environment setup code ***
  var arguments_ = [];
  var debug = false;
  
  var ENVIRONMENT_IS_NODE = typeof process === 'object';
  var ENVIRONMENT_IS_WEB = typeof window === 'object';
  var ENVIRONMENT_IS_WORKER = typeof importScripts === 'function';
  var ENVIRONMENT_IS_SHELL = !ENVIRONMENT_IS_WEB && !ENVIRONMENT_IS_NODE && !ENVIRONMENT_IS_WORKER;
  
  if (ENVIRONMENT_IS_NODE) {
    // Expose functionality in the same simple way that the shells work
    // Note that we pollute the global namespace here, otherwise we break in node
    print = function(x) {
      process['stdout'].write(x + '\n');
    };
    printErr = function(x) {
      process['stderr'].write(x + '\n');
    };
  
    var nodeFS = require('fs');
    var nodePath = require('path');
  
    if (!nodeFS.existsSync) {
      nodeFS.existsSync = function(path) {
        try {
          return !!nodeFS.readFileSync(path);
        } catch(e) {
          return false;
        }
      }
    }
  
    function find(filename) {
      var prefixes = [nodePath.join(__dirname, '..', 'src'), process.cwd()];
      for (var i = 0; i < prefixes.length; ++i) {
        var combined = nodePath.join(prefixes[i], filename);
        if (nodeFS.existsSync(combined)) {
          return combined;
        }
      }
      return filename;
    }
  
    read = function(filename) {
      var absolute = find(filename);
      return nodeFS['readFileSync'](absolute).toString();
    };
  
    load = function(f) {
      globalEval(read(f));
    };
  
    arguments_ = process['argv'].slice(2);
  
  } else if (ENVIRONMENT_IS_SHELL) {
    // Polyfill over SpiderMonkey/V8 differences
    if (!this['read']) {
      this['read'] = function(f) { snarf(f) };
    }
  
    if (typeof scriptArgs != 'undefined') {
      arguments_ = scriptArgs;
    } else if (typeof arguments != 'undefined') {
      arguments_ = arguments;
    }
  
  } else if (ENVIRONMENT_IS_WEB) {
    this['print'] = printErr = function(x) {
      console.log(x);
    };
  
    this['read'] = function(url) {
      var xhr = new XMLHttpRequest();
      xhr.open('GET', url, false);
      xhr.send(null);
      return xhr.responseText;
    };
  
    if (this['arguments']) {
      arguments_ = arguments;
    }
  } else if (ENVIRONMENT_IS_WORKER) {
    // We can do very little here...
  
    this['load'] = importScripts;
  
  } else {
    throw 'Unknown runtime environment. Where are we?';
  }
  
  function globalEval(x) {
    eval.call(null, x);
  }
  
  if (typeof load === 'undefined' && typeof read != 'undefined') {
    this['load'] = function(f) {
      globalEval(read(f));
    };
  }
  
  if (typeof printErr === 'undefined') {
    this['printErr'] = function(){};
  }
  
  if (typeof print === 'undefined') {
    this['print'] = printErr;
  }
  // *** Environment setup code ***
  
  var uglify = require('../third_party/uglify-js');
  var fs = require('fs');
  var path = require('path');
  
  // Load some modules
  
  load('utility.js');
  
  // Utilities
  
  var LOOP = set('do', 'while', 'for');
  var LOOP_FLOW = set('break', 'continue');
  var CONTROL_FLOW = set('do', 'while', 'for', 'if', 'switch');
  var NAME_OR_NUM = set('name', 'num');
  var ASSOCIATIVE_BINARIES = set('+', '*', '|', '&', '^');
  var ALTER_FLOW = set('break', 'continue', 'return');
  var BITWISE = set('|', '&', '^');
  
  var BREAK_CAPTURERS = set('do', 'while', 'for', 'switch');
  var CONTINUE_CAPTURERS = LOOP;
  
  var COMMABLE = set('assign', 'binary', 'unary-prefix', 'unary-postfix', 'name', 'num', 'call', 'seq', 'conditional', 'sub');
  
  var CONDITION_CHECKERS = set('if', 'do', 'while', 'switch');
  var BOOLEAN_RECEIVERS = set('if', 'do', 'while', 'conditional');
  
  var FUNCTIONS_THAT_ALWAYS_THROW = set('abort', '___resumeException', '___cxa_throw', '___cxa_rethrow');
  
  var UNDEFINED_NODE = ['unary-prefix', 'void', ['num', 0]];
  
  var GENERATED_FUNCTIONS_MARKER = '// EMSCRIPTEN_GENERATED_FUNCTIONS';
  var generatedFunctions = false; // whether we have received only generated functions
  
  var extraInfo = null;
  
  function srcToAst(src) {
    return uglify.parser.parse(src, false, debug);
  }
  
  function astToSrc(ast, minifyWhitespace) {
    return uglify.uglify.gen_code(ast, {
      debug: debug,
      ascii_only: true,
      beautify: !minifyWhitespace,
      indent_level: 1
    });
  }
  
  function srcToStat(src) {
    return srcToAst(src)[1][0]; // look into toplevel
  }
  
  function srcToExp(src) {
    return srcToStat(src)[1];
  }
  
  // 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) {
    if (node[0] === 'var') {
      // don't traverse the names, just the values
      var children = node[1];
      if (!Array.isArray(children)) return;
      for (var i = 0; i < children.length; i++) {
        var subnode = children[i];
        if (subnode.length === 2) {
          var value = subnode[1];
          if (Array.isArray(value)) {
            var subresult = traverse(value, pre, post);
            if (subresult === true) return true;
            if (subresult !== null && typeof subresult === 'object') subnode[1] = subresult;
          }
        }
      }
    } else if (node[0] === 'object') {
      // don't traverse the names, just the values
      var children = node[1];
      if (!Array.isArray(children)) return;
      for (var i = 0; i < children.length; i++) {
        var subnode = children[i];
        var value = subnode[1];
        if (Array.isArray(value)) {
          var subresult = traverse(value, pre, post);
          if (subresult === true) return true;
          if (subresult !== null && typeof subresult === 'object') subnode[1] = subresult;
        }
      }
    } else {
      // generic traversal
      for (var i = 0; i < node.length; i++) {
        var subnode = node[i];
        if (Array.isArray(subnode)) {
          var subresult = traverse(subnode, pre, post);
          if (subresult === true) return true;
          if (subresult !== null && typeof subresult === 'object') node[i] = subresult;
        }
      }
    }
  }
  
  // Traverses a JavaScript syntax tree rooted at the given node calling the given
  // callback for each node.
  //   @arg node: The root of the AST.
  //   @arg pre: The pre to call for each node. This will be called with
  //     the node as the first argument and its type as the second. If true is
  //     returned, the traversal is stopped. If an object is returned,
  //     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.
  //   @returns: If the root node was replaced, the new root node. If the traversal
  //     was stopped, true. Otherwise undefined.
  function traverse(node, pre, post) {
    var type = node[0], result, len;
    var relevant = typeof type === 'string';
    if (relevant) {
      var result = pre(node, type);
      if (result === true) return true;
      if (result && result !== null) node = result; // Continue processing on this node
    }
    if (result !== null) {
      if (traverseChildren(node, traverse, pre, post) === true) return true;
    }
    if (relevant) {
      if (post) {
        var postResult = post(node, type);
        result = result || postResult;
      }
    }
    return result;
  }
  
  // Only walk through the generated functions
  function traverseGeneratedFunctions(ast, callback) {
    assert(generatedFunctions);
    if (ast[0] === 'toplevel') {
      var stats = ast[1];
      for (var i = 0; i < stats.length; i++) {
        var curr = stats[i];
        if (curr[0] === 'defun') callback(curr);
      }
    } else if (ast[0] === 'defun') {
      callback(ast);
    }
  }
  
  function traverseGenerated(ast, pre, post) {
    traverseGeneratedFunctions(ast, function(func) {
      traverse(func, pre, post);
    });
  }
  
  function deStat(node) {
    if (node[0] === 'stat') return node[1];
    return node;
  }
  
  function emptyNode() { // XXX do we need to create new nodes here? can't we reuse?
    return ['toplevel', []]
  }
  
  function isEmptyNode(node) {
    return node.length === 2 && node[0] === 'toplevel' && node[1].length === 0;
  }
  
  function clearEmptyNodes(list) {
    for (var i = 0; i < list.length;) {
      if (isEmptyNode(list[i]) || (list[i][0] === 'stat' && isEmptyNode(list[i][1]))) {
        list.splice(i, 1);
      } else {
        i++;
      }
    }
  }
  
  function filterEmptyNodes(list) { // creates a copy and returns it
    return list.filter(function(node) {
      return !(isEmptyNode(node) || (node[0] === 'stat' && isEmptyNode(node[1])));
    });
  }
  
  function removeEmptySubNodes(node) {
    if (node[0] === 'defun') {
      node[3] = filterEmptyNodes(node[3]);
    } else if (node[0] === 'block' && node[1]) {
      node[1] = filterEmptyNodes(node[1]);
    } else if (node[0] === 'seq' && isEmptyNode(node[1])) {
      return node[2];
    }
  /*
    var stats = getStatements(node);
    if (stats) clearEmptyNodes(stats);
  */
  }
  
  function removeAllEmptySubNodes(ast) {
    traverse(ast, removeEmptySubNodes);
  }
  
  function astCompare(x, y) {
    if (!Array.isArray(x)) return x === y;
    if (!Array.isArray(y)) return false;
    if (x.length !== y.length) return false;
    for (var i = 0; i < x.length; i++) {
      if (!astCompare(x[i], y[i])) return false;
    }
    return true;
  }
  
  // calls definitely on child nodes that will be called, in order, and calls maybe on nodes that might be called.
  // a(); if (b) c(); d(); will call definitely(a, arg), maybe(c, arg), definitely(d, arg)
  function traverseChildrenInExecutionOrder(node, definitely, maybe, arg) {
    switch (node[0]) {
      default: throw '!' + node[0];
      case 'num': case 'var': case 'name': case 'toplevel': case 'string':
      case 'break': case 'continue': break; // nodes with no interesting children; they themselves have already been definitely or maybe'd
      case 'assign': case 'binary': {
        definitely(node[2], arg);
        definitely(node[3], arg);
        break;
      }
      case 'sub': case 'seq': {
        definitely(node[1], arg);
        definitely(node[2], arg);
        break;
      }
      case 'while': {
        definitely(node[1], arg);
        maybe(node[2], arg); // may never enter the loop
        maybe(node[1], arg); // may enter the loop a second time
        maybe(node[2], arg);
        break;
      }
      case 'do': {
        definitely(node[2], arg);
        maybe(node[1], arg); // may never reach the condition if we break
        maybe(node[2], arg);
        maybe(node[1], arg);
        break;
      }
      case 'binary': {
        definitely(node[2], arg);
        definitely(node[3], arg);
        break;
      }
      case 'dot': {
        definitely(node[1], arg);
        break;
      }
      case 'unary-prefix': case 'label': {
        definitely(node[2], arg);
        break;
      }
      case 'call': {
        definitely(node[1], arg);
        var args = node[2];
        for (var i = 0; i < args.length; i++) {
          definitely(args[i], arg);
        }
        break;
      }
      case 'if': case 'conditional': {
        definitely(node[1], arg);
        maybe(node[2], arg);
        if (node[3]) { maybe(node[3], arg); }
        break;
      }
      case 'defun': case 'func': case 'block': {
        var stats = getStatements(node);
        if (!stats || stats.length === 0) break;
        for (var i = 0; i < stats.length; i++) {
          definitely(stats[i], arg);
          // check if we might break, if we have more to do
          if (i === stats.length - 1) break;
          var labels = {};
          var breakCaptured = 0;
          var mightBreak = false;
          traverse(stats[i], function(node, type) {
            if (type === 'label') labels[node[1]] = true;
            else if (type in BREAK_CAPTURERS) {
              breakCaptured++;
            } else if (type === 'break') {
              if (node[1]) {
                // labeled break
                if (!(node[1] in labels)) mightBreak = true;
              } else {
                if (!breakCaptured) mightBreak = true;
              }
            }
          }, function(node, type) {
            if (type === 'label') delete labels[node[1]];
            else if (type in BREAK_CAPTURERS) {
              breakCaptured--;
            }
          });
          if (mightBreak) {
            // all the rest are in one big maybe
            return maybe(['block', stats.slice(i+1)], arg);
          }
        }
        break;
      }
      case 'stat': case 'return': {
        definitely(node[1], arg);
        break;
      }
      case 'switch': {
        definitely(node[1], arg);
        var cases = node[2];
        for (var i = 0; i < cases.length; i++) {
          var c = cases[i];
          var stats = c[1];
          var temp = ['block', stats];
          maybe(temp, arg);
        }
      }
    }
  }
  
  // Passes
  
  // Dump the AST. Useful for debugging. For example,
  //  node tools/js-optimizer.js ABSOLUTE_PATH_TO_FILE dumpAst
  function dumpAst(ast) {
    printErr(JSON.stringify(ast, null, '  '));
  }
  
  function dumpSrc(ast) {
    printErr(astToSrc(ast));
  }
  
  function overwrite(x, y) {
    for (var i = 0; i < y.length; i++) x[i] = y[i];
    x.length = y.length;
  }
  
  var STACK_ALIGN = 16;
  
  function stackAlign(x) {
    if (x % STACK_ALIGN) x += STACK_ALIGN - (x % STACK_ALIGN);
    return x;
  }
  
  // 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
  // undefined being assigned. So we can simply remove those assignments.
  //
  // Note: An inlined function that kept a large value referenced, may
  //       keep that references when inlined, if we remove the setting to
  //       undefined. This is not dangerous in compiled code, but might be
  //       in supporting code (for example, holding on to the HEAP when copying).
  //
  // This pass assumes that unGlobalize has been run, so undefined
  // is now explicit.
  function removeAssignsToUndefined(ast) {
    traverse(ast, function(node, type) {
      if (type === 'assign' && jsonCompare(node[3], ['unary-prefix', 'void', ['num', 0]])) {
        return emptyNode();
      } else if (type === 'var') {
        node[1] = node[1].map(function(varItem, j) {
          var ident = varItem[0];
          var value = varItem[1];
          if (jsonCompare(value, UNDEFINED_NODE)) return [ident];
          return [ident, value];
        });
      }
    });
    // cleanup (|x = y = void 0| leaves |x = ;| right now)
    var modified = true;
    while (modified) {
      modified = false;
      traverse(ast, function(node, type) {
        if (type === 'assign' && jsonCompare(node[3], emptyNode())) {
          modified = true;
          return emptyNode();
        } else if (type === 'var') {
          node[1] = node[1].map(function(varItem, j) {
            var ident = varItem[0];
            var value = varItem[1];
            if (value && jsonCompare(value, emptyNode())) return [ident];
            return [ident, value];
          });
        }
      });
    }
  }
  
  // XXX This is an invalid optimization
  // We sometimes leave some settings to label that are not needed, if later in
  // the relooper we realize that we have a single entry, so no checks on label
  // are actually necessary. It's easy to clean those up now.
  function removeUnneededLabelSettings(ast) {
    traverse(ast, function(node, type) {
      if (type === 'defun') { // all of our compiled code is in defun nodes
        // Find all checks
        var checked = {};
        traverse(node, function(node, type) {
          if (type === 'binary' && node[1] === '==' && node[2][0] === 'name' && node[2][1] === 'label') {
            assert(node[3][0] === 'num');
            checked[node[3][1]] = 1;
          }
        });
        // Remove unneeded sets
        traverse(node, function(node, type) {
          if (type === 'assign' && node[2][0] === 'name' && node[2][1] === 'label') {
            assert(node[3][0] === 'num');
            if (!(node[3][1] in checked)) return emptyNode();
          }
        });
      }
    });
  }
  
  // Various expression simplifications. Happens after elimination, which opens up many of these simplification opportunities.
  
  function makeTempParseHeap() {
    return { unsigned: false, float: false, bits: 0, type: 0 };
  }
  
  var parseHeapTemp = makeTempParseHeap();
  
  function parseHeap(name, out) { // XXX this uses parseHeapTemp by default, which is global! If between your call and your use, something else can call - that is bad
    out = out || parseHeapTemp;
    if (name.substr(0, 4) != 'HEAP') return false;
    out.unsigned = name[4] === 'U';
    out.float = name[4] === 'F';
    out.bits = parseInt(name.substr(out.unsigned || out.float ? 5 : 4));
    out.type = !out.float ? ASM_INT : (out.bits === 64 ? ASM_DOUBLE : ASM_FLOAT);
    return true;
  }
  
  var USEFUL_BINARY_OPS = set('<<', '>>', '|', '&', '^');
  var COMPARE_OPS = set('<', '<=', '>', '>=', '==', '===', '!=', '!==');
  
  function isFunctionTable(name) {
    return /^FUNCTION_TABLE.*/.test(name);
  }
  
  function simplifyExpressions(ast) {
    // Simplify common expressions used to perform integer conversion operations
    // in cases where no conversion is needed.
    function simplifyIntegerConversions(ast) {
      traverse(ast, function(node, type) {
        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]) {
          // Transform (x&A)<<B>>B to X&A.
          var innerNode = node[2][2];
          var shifts = node[3][1];
          if (innerNode[0] === 'binary' && innerNode[1] === '&' && innerNode[3][0] === 'num') {
            var mask = innerNode[3][1];
            if (mask << shifts >> shifts === mask) {
              return innerNode;
            }
          }
        } else if (type === 'binary' && (node[1] in BITWISE)) {
          for (var i = 2; i <= 3; i++) {
            var subNode = node[i];
            if (subNode[0] === 'binary' && subNode[1] === '&' && subNode[3][0] === 'num' && subNode[3][1] == 1) {
              // Rewrite (X < Y) & 1 to X < Y , when it is going into a bitwise operator. We could
              // remove even more (just replace &1 with |0, then subsequent passes could remove the |0)
              // but v8 issue #2513 means the code would then run very slowly in chrome.
              var input = subNode[2];
              if (input[0] === 'binary' && (input[1] in COMPARE_OPS)) {
                node[i] = input;
              }
            }
          }
        }
      });
    }
  
    // When there is a bunch of math like (((8+5)|0)+12)|0, only the external |0 is needed, one correction is enough.
    // At each node, ((X|0)+Y)|0 can be transformed into (X+Y): The inner corrections are not needed
    // TODO: Is the same is true for 0xff, 0xffff?
    // Likewise, if we have |0 inside a block that will be >>'d, then the |0 is unnecessary because some
    // 'useful' mathops already |0 anyhow.
  
    function simplifyOps(ast) {
      var SAFE_BINARY_OPS;
      if (asm) {
        SAFE_BINARY_OPS = set('+', '-'); // division is unsafe as it creates non-ints in JS; mod is unsafe as signs matter so we can't remove |0's; mul does not nest with +,- in asm
      } else {
        SAFE_BINARY_OPS = set('+', '-', '*');
      }
      var COERCION_REQUIRING_OPS = set('sub', 'unary-prefix'); // ops that in asm must be coerced right away
      var COERCION_REQUIRING_BINARIES = set('*', '/', '%'); // binary ops that in asm must be coerced
      var ZERO = ['num', 0];
  
      function removeMultipleOrZero() {
        var rerun = true;
        while (rerun) {
          rerun = false;
          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;
              if (jsonCompare(node[2], ZERO)) {
                // canonicalize order
                var temp = node[3];
                node[3] = node[2];
                node[2] = temp;
                go = true;
              } else if (jsonCompare(node[3], ZERO)) {
                go = true;
              }
              if (!go) {
                stack.push(1);
                return;
              }
              // We might be able to remove this correction
              for (var i = stack.length-1; i >= 0; i--) {
                if (stack[i] >= 1) {
                  if (asm) {
                    if (stack[stack.length-1] < 2 && node[2][0] === 'call') break; // we can only remove multiple |0s on these
                    if (stack[stack.length-1] < 1 && (node[2][0] in COERCION_REQUIRING_OPS ||
                                                      (node[2][0] === 'binary' && node[2][1] in COERCION_REQUIRING_BINARIES))) break; // we can remove |0 or >>2
                  }
                  // we will replace ourselves with the non-zero side. Recursively process that node.
                  var result = jsonCompare(node[2], ZERO) ? node[3] : node[2], other;
                  // replace node in-place
                  node.length = result.length;
                  for (var j = 0; j < result.length; j++) {
                    node[j] = result[j];
                  }
                  rerun = true;
                  return process(result, result[0]);
                } else if (stack[i] === -1) {
                  break; // Too bad, we can't
                }
              }
              stack.push(2); // From here on up, no need for this kind of correction, it's done at the top
                             // (Add this at the end, so it is only added if we did not remove it)
            } else if (type === 'binary' && node[1] in USEFUL_BINARY_OPS) {
              stack.push(1);
            } else if ((type === 'binary' && node[1] in SAFE_BINARY_OPS) || type === 'num' || type === 'name') {
              stack.push(0); // This node is safe in that it does not interfere with this optimization
            } else if (type === 'unary-prefix' && node[1] === '~') {
              stack.push(1);
            } else {
              stack.push(-1); // This node is dangerous! Give up if you see this before you see '1'
            }
          }, function() {
            stack.pop();
          });
        }
      }
  
      removeMultipleOrZero();
  
      // & and heap-related optimizations
  
      var hasTempDoublePtr = false, rerunOrZeroPass = false;
  
      traverse(ast, function(node, type) {
        // The "pre" visitor. Useful for detecting trees which should not
        // be simplified.
        if (type == 'sub' && node[1][0] == 'name' && isFunctionTable(node[1][1])) {
          return null; // do not traverse subchildren here, we should not collapse 55 & 126.
        }
      }, function(node, type) {
        // The "post" visitor. The simplifications are done in this visitor so
        // that we simplify a node's operands before the node itself. This allows
        // optimizations to cascade.
        if (type === 'name') {
          if (node[1] === 'tempDoublePtr') hasTempDoublePtr = true;
        } else if (type === 'binary' && node[1] === '&' && node[3][0] === 'num') {
          if (node[2][0] === 'num') return ['num', node[2][1] & node[3][1]];
          var input = node[2];
          var amount = node[3][1];
          if (input[0] === 'binary' && input[1] === '&' && input[3][0] === 'num') {
            // Collapse X & 255 & 1
            node[3][1] = amount & input[3][1];
            node[2] = input[2];
          } else if (input[0] === 'sub' && input[1][0] === 'name') {
            // HEAP8[..] & 255 => HEAPU8[..]
            var name = input[1][1];
            if (parseHeap(name)) {
              if (amount === Math.pow(2, parseHeapTemp.bits)-1) {
                if (!parseHeapTemp.unsigned) {
                  input[1][1] = 'HEAPU' + parseHeapTemp.bits; // make unsigned
                }
                if (asm) {
                  // we cannot return HEAPU8 without a coercion, but at least we do HEAP8 & 255 => HEAPU8 | 0
                  node[1] = '|';
                  node[3][1] = 0;
                  return node;
                }
                return input;
              }
            }
          } else if (input[0] === 'binary' && input[1] === '>>' &&
                     input[2][0] === 'binary' && input[2][1] === '<<' &&
                     input[2][3][0] === 'num' && input[3][0] === 'num' &&
                     input[2][3][1] === input[3][1] &&
                     (~(-1 >>> input[3][1]) & amount) == 0) {
              // x << 24 >> 24 & 255 => x & 255
              return ['binary', '&', input[2][2], node[3]];
          }
        } else if (type === 'binary' && node[1] === '^') {
          // LLVM represents bitwise not as xor with -1. Translate it back to an actual bitwise not.
          if (node[3][0] === 'unary-prefix' && node[3][1] === '-' && node[3][2][0] === 'num' &&
              node[3][2][1] === 1 &&
              !(node[2][0] == 'unary-prefix' && node[2][1] == '~')) { // avoid creating ~~~ which is confusing for asm given the role of ~~
              return ['unary-prefix', '~', node[2]];
          }
        } else if (type       === 'binary' && node[1]    === '>>' && node[3][0]    === 'num' &&
                   node[2][0] === 'binary' && node[2][1] === '<<' && node[2][3][0] === 'num' &&
                   node[2][2][0] === 'sub' && node[2][2][1][0] === 'name') {
          // collapse HEAPU?8[..] << 24 >> 24 etc. into HEAP8[..] | 0
          var amount = node[3][1];
          var name = node[2][2][1][1];
          if (amount === node[2][3][1] && parseHeap(name)) {
            if (parseHeapTemp.bits === 32 - amount) {
              node[2][2][1][1] = 'HEAP' + parseHeapTemp.bits;
              node[1] = '|';
              node[2] = node[2][2];
              node[3][1] = 0;
              rerunOrZeroPass = true;
              return node;
            }
          }
        } else if (type === 'assign') {
          // optimizations for assigning into HEAP32 specifically
          if (node[1] === true && node[2][0] === 'sub' && node[2][1][0] === 'name') {
            if (node[2][1][1] === 'HEAP32') {
              // HEAP32[..] = x | 0 does not need the | 0 (unless it is a mandatory |0 of a call)
              if (node[3][0] === 'binary' && node[3][1] === '|') {
                if (node[3][2][0] === 'num' && node[3][2][1] === 0 && node[3][3][0] != 'call') {
                  node[3] = node[3][3];
                } else if (node[3][3][0] === 'num' && node[3][3][1] === 0 && node[3][2][0] != 'call') {
                  node[3] = node[3][2];
                }
              }
            } else if (node[2][1][1] === 'HEAP8') {
              // HEAP8[..] = x & 0xff does not need the & 0xff
              if (node[3][0] === 'binary' && node[3][1] === '&' && node[3][3][0] == 'num' && node[3][3][1] == 0xff) {
                node[3] = node[3][2];
              }
            } else if (node[2][1][1] === 'HEAP16') {
              // HEAP16[..] = x & 0xffff does not need the & 0xffff
              if (node[3][0] === 'binary' && node[3][1] === '&' && node[3][3][0] == 'num' && node[3][3][1] == 0xffff) {
                node[3] = node[3][2];
              }
            }
          }
          var value = node[3];
          if (value[0] === 'binary' && value[1] === '|') {
            // canonicalize order of |0 to end
            if (value[2][0] === 'num' && value[2][1] === 0) {
              var temp = value[2];
              value[2] = value[3];
              value[3] = temp;
            }
            // if a seq ends in an |0, remove an external |0
            // note that it is only safe to do this in assigns, like we are doing here (return (x, y|0); is not valid)
            if (value[2][0] === 'seq' && value[2][2][0] === 'binary' && value[2][2][1] in USEFUL_BINARY_OPS) {
              node[3] = value[2];
            }
          }
        } else if (type === 'binary' && node[1] === '>>' && node[2][0] === 'num' && node[3][0] === 'num') {
          // optimize num >> num, in asm we need this since we do not optimize shifts in asm.js
          node[0] = 'num';
          node[1] = node[2][1] >> node[3][1];
          node.length = 2;
          return node;
        } else if (type === 'binary' && node[1] === '+') {
          // The most common mathop is addition, e.g. in getelementptr done repeatedly. We can join all of those,
          // by doing (num+num) ==> newnum.
          if (node[2][0] === 'num' && node[3][0] === 'num') {
            node[2][1] += node[3][1];
            return node[2];
          }
        }
      });
  
      if (rerunOrZeroPass) removeMultipleOrZero();
  
      if (asm) {
        if (hasTempDoublePtr) {
          var asmData = normalizeAsm(ast);
          traverse(ast, function(node, type) {
            if (type === 'assign') {
              if (node[1] === true && node[2][0] === 'sub' && node[2][1][0] === 'name' && node[2][1][1] === 'HEAP32') {
                // remove bitcasts that are now obviously pointless, e.g.
                // HEAP32[$45 >> 2] = HEAPF32[tempDoublePtr >> 2] = ($14 < $28 ? $14 : $28) - $42, HEAP32[tempDoublePtr >> 2] | 0;
                var value = node[3];
                if (value[0] === 'seq' && value[1][0] === 'assign' && value[1][2][0] === 'sub' && value[1][2][1][0] === 'name' && value[1][2][1][1] === 'HEAPF32' &&
                    value[1][2][2][0] === 'binary' && value[1][2][2][2][0] === 'name' && value[1][2][2][2][1] === 'tempDoublePtr') {
                  // transform to HEAPF32[$45 >> 2] = ($14 < $28 ? $14 : $28) - $42;
                  node[2][1][1] = 'HEAPF32';
                  node[3] = value[1][3];
                }
              }
            } else if (type === 'seq') {
              // (HEAP32[tempDoublePtr >> 2] = HEAP32[$37 >> 2], +HEAPF32[tempDoublePtr >> 2])
              //   ==>
              // +HEAPF32[$37 >> 2]
              if (node[0] === 'seq' && node[1][0] === 'assign' && node[1][2][0] === 'sub' && node[1][2][1][0] === 'name' &&
                  (node[1][2][1][1] === 'HEAP32' || node[1][2][1][1] === 'HEAPF32') &&
                  node[1][2][2][0] === 'binary' && node[1][2][2][2][0] === 'name' && node[1][2][2][2][1] === 'tempDoublePtr' &&
                  node[1][3][0] === 'sub' && node[1][3][1][0] === 'name' && (node[1][3][1][1] === 'HEAP32' || node[1][3][1][1] === 'HEAPF32') &&
                  node[2][0] !== 'seq') { // avoid (x, y, z) which can be used for tempDoublePtr on doubles for alignment fixes
                if (node[1][2][1][1] === 'HEAP32') {
                  node[1][3][1][1] = 'HEAPF32';
                  return makeAsmCoercion(node[1][3], detectType(node[2]));
                } else {
                  node[1][3][1][1] = 'HEAP32';
                  return ['binary', '|', node[1][3], ['num', 0]];
                }
              }
            }
          });
  
          // finally, wipe out remaining ones by finding cases where all assignments to X are bitcasts, and all uses are writes to
          // the other heap type, then eliminate the bitcast
          var bitcastVars = {};
          traverse(ast, function(node, type) {
            if (type === 'assign' && node[1] === true && node[2][0] === 'name') {
              var value = node[3];
              if (value[0] === 'seq' && value[1][0] === 'assign' && value[1][2][0] === 'sub' && value[1][2][1][0] === 'name' &&
                  (value[1][2][1][1] === 'HEAP32' || value[1][2][1][1] === 'HEAPF32') &&
                  value[1][2][2][0] === 'binary' && value[1][2][2][2][0] === 'name' && value[1][2][2][2][1] === 'tempDoublePtr') {
                var name = node[2][1];
                if (!bitcastVars[name]) bitcastVars[name] = {
                  define_HEAP32: 0, define_HEAPF32: 0, use_HEAP32: 0, use_HEAPF32: 0, bad: false, namings: 0, defines: [], uses: []
                };
                bitcastVars[name]['define_' + value[1][2][1][1]]++;
                bitcastVars[name].defines.push(node);
              }
            }
          });
          traverse(ast, function(node, type) {
            if (type === 'name' && bitcastVars[node[1]]) {
              bitcastVars[node[1]].namings++;
            } else if (type === 'assign' && node[1] === true) {
              var value = node[3];
              if (value[0] === 'name') {
                var name = value[1];
                if (bitcastVars[name]) {
                  var target = node[2];
                  if (target[0] === 'sub' && target[1][0] === 'name' && (target[1][1] === 'HEAP32' || target[1][1] === 'HEAPF32')) {
                    bitcastVars[name]['use_' + target[1][1]]++;
                    bitcastVars[name].uses.push(node);
                  }
                }
              }
            }
          });
          for (var v in bitcastVars) {
            var info = bitcastVars[v];
            // good variables define only one type, use only one type, have definitions and uses, and define as a different type than they use
            if (info.define_HEAP32*info.define_HEAPF32 === 0 && info.use_HEAP32*info.use_HEAPF32 === 0 &&
                info.define_HEAP32+info.define_HEAPF32 > 0  && info.use_HEAP32+info.use_HEAPF32 > 0 &&
                info.define_HEAP32*info.use_HEAP32 === 0 && info.define_HEAPF32*info.use_HEAPF32 === 0 &&
                v in asmData.vars && info.namings === info.define_HEAP32+info.define_HEAPF32+info.use_HEAP32+info.use_HEAPF32) {
              var correct = info.use_HEAP32 ? 'HEAPF32' : 'HEAP32';
              info.defines.forEach(function(define) {
                define[3] = define[3][1][3];
                if (correct === 'HEAP32') {
                  define[3] = ['binary', '|', define[3], ['num', 0]];
                } else {
                  define[3] = makeAsmCoercion(define[3], asmPreciseF32 ? ASM_FLOAT : ASM_DOUBLE);
                }
                // do we want a simplifybitops on the new values here?
              });
              info.uses.forEach(function(use) {
                use[2][1][1] = correct;
              });
              var correctType;
              switch(asmData.vars[v]) {
                case ASM_INT: correctType = asmPreciseF32 ? ASM_FLOAT : ASM_DOUBLE; break;
                case ASM_FLOAT: case ASM_DOUBLE: correctType = ASM_INT; break;
              }
              asmData.vars[v] = correctType;
            }
          }
          denormalizeAsm(ast, asmData);
        }
      }
    }
  
    function emitsBoolean(node) {
      if (node[0] === 'num') {
        return node[1] === 0 || node[1] === 1;
      }
      if (node[0] === 'binary') return node[1] in COMPARE_OPS;
      if (node[0] === 'unary-prefix') return node[1] === '!';
      if (node[0] === 'conditional') return emitsBoolean(node[2]) && emitsBoolean(node[3]);
      return false;
    }
  
    //   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 = 7;
      traverse(ast, function(node, type) {
        if (node[0] === 'binary' && (node[1] === '|' || node[1] === '&') && node[3][0] !== 'num' && node[2][0] !== 'num') {
          // logical operator on two non-numerical values
          var left = node[2];
          var right = node[3];
          if (!emitsBoolean(left) || !emitsBoolean(right)) return;
          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
          var ret;
          if (node[1] === '|') {
            ret = ['conditional', left, ['num', 1], right];
          } else { // &
            ret = ['conditional', left, right, ['num', 0]];
          }
          if (left[0] === 'unary-prefix' && left[1] === '!') {
            ret[1] = flipCondition(left);
            var temp = ret[2];
            ret[2] = ret[3];
            ret[3] = temp;
          }
          return ret;
        }
      });
    }
  
    function simplifyNotZero(ast) {
      traverse(ast, function(node, type) {
        if (node[0] in BOOLEAN_RECEIVERS) {
          var boolean = node[1];
          if (boolean[0] === 'binary' && boolean[1] === '!=' && boolean[3][0] === 'num' && boolean[3][1] === 0) {
            node[1] = boolean[2];
          }
        }
      });
    }
  
    traverseGeneratedFunctions(ast, function(func) {
      simplifyIntegerConversions(func);
      simplifyOps(func);
      simplifyNotComps(func);
      conditionalize(func);
      simplifyNotZero(func);
    });
  }
  
  // Checks if a coercion is necessary for asm.js, and cannot be
  // removed. Receives the node, and the expression stack, which
  // includes the node at the end.
  function isNecessaryCoercion(node, stack) {
    assert(stack[stack.length - 1] === node);
    var parent = stack[stack.length - 2];
    if (!parent) return false;
    if (parent[0] === 'sub') {
      // We are x & mask in FUNCTION_TABLE[x & mask], and the mask
      // is necessary.
      return true;
    }
    return false;
  }
  
  function localCSE(ast) {
    // very simple CSE/GVN type optimization, factor out common expressions in a single basic block
    assert(asm);
    var MIN_COST = 3;
    traverseGeneratedFunctions(ast, function(func) {
      var asmData = normalizeAsm(func);
      var counter = 0;
      var optimized = false;
      traverse(func, function(node, type) {
        var stats = getStatements(node);
        if (!stats) return;
        var exps = {}; // JSON'd expression => [i it first appears on, original node, replacement var, type, sign]
        var deps = {}; // dependency (local name, or 'memory' or 'global')
        function invalidate(what) {
          var list = deps[what];
          if (!list) return;
          for (var i = 0; i < list.length; i++) {
            delete exps[list[i]];
          }
          delete deps[what];
        }
        function doInvalidations(curr) {
          return traverse(curr, function(node, type) {
            if (type in CONTROL_FLOW) {
              exps = {};
              deps = {};
              return true; // abort everything
            }
            if (type === 'assign') {
              var target = node[2];
              if (target[0] === 'name') {
                var name = target[1];
                if (name in asmData.params || name in asmData.vars) {
                  invalidate(name);
                } else {
                  invalidate('<global>');
                }
              } else {
                assert(target[0] === 'sub');
                invalidate('<memory>');
              }
            }
            if (type === 'call') {
              invalidate('<global>');
              invalidate('<memory>');
            }
          });
        }
        for (var i = 0; i < stats.length; i++) {
          var curr = stats[i];
          // first, look at the entire line and invalidate what we need to
          if (doInvalidations(curr) === true) {
            continue; // we saw control flow
          }
          // next, process the line and try to find useful expressions
          var skips = [];
  
          var stack = [];
          traverse(curr, function seekExpressions(node, type) {
            stack.push(node);
            if (type === 'sub' && node[1][0] === 'name' && node[2][0] === 'binary' && node[2][1] === '>>') {
              // skip over the shift, we can't cse that
              skips.push(node[2]);
              return;
            }
            if (type === 'binary' || type === 'unary-prefix') {
              if (type === 'binary' && skips.indexOf(node) >= 0) return;
              if (measureCost(node) < MIN_COST) return;
              if (detectType(node, asmData) === ASM_NONE) return; // if we can't figure it out locally, forget it
              // We cannot CSE out a necessary asm.js coercion
              if (isNecessaryCoercion(node, stack)) return;
              var str = JSON.stringify(node);
              var lookup = exps[str];
              if (!lookup) {
                // add ourselves, and set up our deps
                exps[str] = [i, node, null];
                traverse(node, function(node, type) {
                  var names = [];
                  if (type === 'name') {
                    var name = node[1];
                    if (!(name in asmData.params || name in asmData.vars)) name = '<global>';
                    names.push(name);
                  } else if (type === 'sub') {
                    names.push('<memory>');
                  } else if (type === 'call') {
                    names.push('<memory>');
                    names.push('<global>');
                  }
                  names.forEach(function(name) {
                    if (!deps[name]) deps[name] = [];
                    deps[name].push(str);
                  });
                });
              } else {
                //printErr('CSEing ' + str);
                optimized = true;
                var type, sign;
                // with the original node plus us, this is worth optimizing out
                if (lookup[2] === null) {
                  // this is the first node after the first. generate the saved var, and optimize out the original
                  lookup[2] = 'CSE$' + (counter++);
                  // ensure an asm coercion
                  type = lookup[3] = detectType(node, asmData);
                  sign = detectSign(node);
                  if (sign === ASM_FLEXIBLE) sign = ASM_SIGNED;
                  lookup[4] = sign;
                  asmData.vars[lookup[2]] = type;
                  overwrite(lookup[1], makeSignedAsmCoercion(['name', lookup[2]], type, sign));
                  stats.splice(lookup[0], 0, ['stat', ['assign', true, ['name', lookup[2]], makeSignedAsmCoercion(node, type, sign)]]);
                  // adjust indexes after that splice
                  i++; // i must be after lookup[0]
                  for (var e in exps) {
                    var curr = exps[e];
                    if (curr[2] === null) {
                      if (curr[0] >= lookup[0]) curr[0]++;
                    }
                  }
                } else {
                  type = lookup[3];
                  sign = lookup[4];
                }
                // optimize out ourselves
                return makeSignedAsmCoercion(['name', lookup[2]], type, sign);
              }
            }
          }, function(node, type) { // post-traversal
            stack.pop();
          });
          // finally, repeat invalidation processing, to not be sensitive to inter-line control flow
          doInvalidations(curr);
        }
      });
      denormalizeAsm(func, asmData);
      if (optimized) {
        simplifyExpressions(func); // remove double coercions, etc.
      }
    });
  }
  
  function safeLabelSettingInternal(func, asmData) {
    if ('label' in asmData.vars) {
      var stats = getStatements(func);
      var seenVar = false;
      for (var i = 0; i < stats.length; i++) {
        var curr = stats[i];
        if (curr[0] === 'stat') curr = curr[1];
        if (curr[0] === 'var') {
          seenVar = true;
        } else if (seenVar && curr[0] !== 'var') {
          // first location after the vars
          stats.splice(i, 0, ['stat', ['assign', true, ['name', 'label'], ['num', 0]]]);
          break;
        }
      }
    }
  }
  
  function safeLabelSetting(ast) {
    // Add an assign to label, if it exists, so that even after we minify/registerize variable names, we can tell if any vars use the asm init value of 0 - none will, so it's easy to tell
    assert(asm);
    traverseGeneratedFunctions(ast, function(func) {
      var asmData = normalizeAsm(func);
      safeLabelSettingInternal(func, asmData);
      denormalizeAsm(func, asmData);
    });
  }
  
  function simplifyIfs(ast) {
    traverseGeneratedFunctions(ast, function(func) {
      var simplifiedAnElse = false;
  
      traverse(func, function(node, type) {
        // simplify   if (x) { if (y) { .. } }   to   if (x ? y : 0) { .. }
        if (type === 'if') {
          var body = node[2];
          // recurse to handle chains
          while (body[0] === 'block') {
            var stats = body[1];
            if (stats.length === 0) break;
            var other = stats[stats.length-1];
            if (other[0] !== 'if') {
              // our if block does not end with an if. perhaps if have an else we can flip
              if (node[3] && node[3][0] === 'block') {
                var stats = node[3][1];
                if (stats.length === 0) break;
                var other = stats[stats.length-1];
                if (other[0] === 'if') {
                  // flip node
                  node[1] = flipCondition(node[1]);
                  node[2] = node[3];
                  node[3] = body;
                  body = node[2];
                } else break;
              } else break;
            }
            // we can handle elses, but must be fully identical
            if (node[3] || other[3]) {
              if (!node[3]) break;
              if (!astCompare(node[3], other[3])) {
                // the elses are different, but perhaps if we flipped a condition we can do better
                if (astCompare(node[3], other[2])) {
                  // flip other. note that other may not have had an else! add one if so; we will eliminate such things later
                  if (!other[3]) other[3] = ['block', []];
                  other[1] = flipCondition(other[1]);
                  var temp = other[2];
                  other[2] = other[3];
                  other[3] = temp;
                } else break;
              }
            }
            if (stats.length > 1) {
              // try to commaify - turn everything between the ifs into a comma operator inside the second if
              var ok = true;
              for (var i = 0; i < stats.length-1; i++) {
                var curr = stats[i];
                if (curr[0] === 'stat') curr = curr[1];
                if (!(curr[0] in COMMABLE)) ok = false;
              }
              if (!ok) break;
              for (var i = stats.length-2; i >= 0; i--) {
                var curr = stats[i];
                if (curr[0] === 'stat') curr = curr[1];
                other[1] = ['seq', curr, other[1]];
              }
              stats = body[1] = [other];
            }
            if (stats.length !== 1) break;
            if (node[3]) simplifiedAnElse = true;
            node[1] = ['conditional', node[1], other[1], ['num', 0]];
            body = node[2] = other[2];
          }
        }
      });
  
      if (simplifiedAnElse) {
        // there may be fusing opportunities
  
        // we can only fuse if we remove all uses of the label. if there are
        // other ones - if the label check can be reached from elsewhere -
        // we must leave it
        var abort = false;
  
        var labelAssigns = {};
        traverse(func, function(node, type) {
          if (type === 'assign' && node[2][0] === 'name' && node[2][1] === 'label') {
            if (node[3][0] === 'num') {
              var value = node[3][1];
              labelAssigns[value] = (labelAssigns[value] || 0) + 1;
            } else {
              // label is assigned a dynamic value (like from indirectbr), we cannot do anything
              abort = true;
            }
          }
        });
        if (abort) return;
  
        var labelChecks = {};
        traverse(func, function(node, type) {
          if (type === 'binary' && node[1] === '==' && node[2][0] === 'binary' && node[2][1] === '|' &&
              node[2][2][0] === 'name' && node[2][2][1] === 'label') {
            if (node[3][0] === 'num') {
              var value = node[3][1];
              labelChecks[value] = (labelChecks[value] || 0) + 1;
            } else {
              // label is checked vs a dynamic value (like from indirectbr), we cannot do anything
              abort = true;
            }
          }
        });
        if (abort) return;
  
        var inLoop = 0; // when in a loop, we do not emit   label = 0;   in the relooper as there is no need
        traverse(func, function(node, type) {
          if (type === 'while') inLoop++;
          var stats = getStatements(node);
          if (stats) {
            for (var i = 0; i < stats.length-1; i++) {
              var pre = stats[i];
              var post = stats[i+1];
              if (pre[0] === 'if' && pre[3] && post[0] === 'if' && !post[3]) {
                var postCond = post[1];
                if (postCond[0] === 'binary' && postCond[1] === '==' &&
                    postCond[2][0] === 'binary' && postCond[2][1] === '|' &&
                    postCond[2][2][0] === 'name' && postCond[2][2][1] === 'label' &&
                    postCond[2][3][0] === 'num' && postCond[2][3][1] === 0 &&
                    postCond[3][0] === 'num') {
                  var postValue = postCond[3][1];
                  var preElse = pre[3];
                  if (labelAssigns[postValue] === 1 && labelChecks[postValue] === 1 && preElse[0] === 'block' && preElse[1] && preElse[1].length === 1) {
                    var preStat = preElse[1][0];
                    if (preStat[0] === 'stat' && preStat[1][0] === 'assign' &&
                        preStat[1][1] === true && preStat[1][2][0] === 'name' && preStat[1][2][1] === 'label' &&
                        preStat[1][3][0] === 'num' && preStat[1][3][1] === postValue) {
                      // Conditions match, just need to make sure the post clears label
                      if (post[2][0] === 'block' && post[2][1] && post[2][1].length > 0) {
                        var postStat = post[2][1][0];
                        var haveClear =
                          postStat[0] === 'stat' && postStat[1][0] === 'assign' &&
                          postStat[1][1] === true && postStat[1][2][0] === 'name' && postStat[1][2][1] === 'label' &&
                          postStat[1][3][0] === 'num' && postStat[1][3][1] === 0;
                        if (!inLoop || haveClear) {
                          // Everything lines up, do it
                          pre[3] = post[2];
                          if (haveClear) pre[3][1].splice(0, 1); // remove the label clearing
                          stats.splice(i+1, 1); // remove the post entirely
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }, function(node, type) {
          if (type === 'while') inLoop--;
        });
      }
    });
  }
  
  // We often have branchings that are simplified so one end vanishes, and
  // we then get
  //   if (!(x < 5))
  // or such. Simplifying these saves space and time.
  function simplifyNotCompsDirect(node) {
    if (node[0] === 'unary-prefix' && node[1] === '!') {
      // de-morgan's laws do not work on floats, due to nans >:(
      if (node[2][0] === 'binary' && (!asm || (detectType(node[2][2]) === ASM_INT && detectType(node[2][3]) === ASM_INT))) {
        switch(node[2][1]) {
          case '<': return ['binary', '>=', node[2][2], node[2][3]];
          case '>': return ['binary', '<=', node[2][2], node[2][3]];
          case '<=': return ['binary', '>', node[2][2], node[2][3]];
          case '>=': return ['binary', '<', node[2][2], node[2][3]];
          case '==': return ['binary', '!=', node[2][2], node[2][3]];
          case '!=': return ['binary', '==', node[2][2], node[2][3]];
          case '===': return ['binary', '!==', node[2][2], node[2][3]];
          case '!==': return ['binary', '===', node[2][2], node[2][3]];
        }
      } else if (node[2][0] === 'unary-prefix' && node[2][1] === '!') {
        return node[2][2];
      }
    }
    if (!simplifyNotCompsPass) return node;
  }
  
  var SAFE_TO_DROP_COERCION = set('unary-prefix', 'name', 'num');
  
  function canDropCoercion(node) {
    if (node[0] in SAFE_TO_DROP_COERCION) return true;
    if (node[0] === 'binary') {
      switch (node[1]) {
        case '>>': case '>>>': case '<<': case '|': case '^': case '&': return true;
      }
    }
    return false;
  }
  
  function simplifyCondition(node) {
    node = simplifyNotCompsDirect(node);
    // on integers, if (x == 0) is the same as if (x), and if (x != 0) as if (!x)
    if (node[0] === 'binary' && (node[1] === '==' || node[1] === '!=')) {
      var target = null;
      if (detectType(node[2]) === ASM_INT && node[3][0] === 'num' && node[3][1] === 0) {
        target = node[2];
      } else if (detectType(node[3]) === ASM_INT && node[2][0] === 'num' && node[2][1] === 0) {
        target = node[3];
      }
      if (target) {
        if (target[0] === 'binary' && (target[1] === '|' || target[1] === '>>>') && target[3][0] === 'num' && target[3][1] === 0 &&
            canDropCoercion(target[2])) {
          target = target[2]; // drop the coercion, in a condition it is ok to do if (x)
        }
        if (node[1] === '==') {
          return ['unary-prefix', '!', target];
        } else {
          return target;
        }
      }
    }
    return node;
  }
  
  function flipCondition(cond) {
    return simplifyNotCompsDirect(['unary-prefix', '!', cond]);
  }
  
  var simplifyNotCompsPass = false;
  
  function simplifyNotComps(ast) {
    simplifyNotCompsPass = true;
    traverse(ast, simplifyNotCompsDirect);
    simplifyNotCompsPass = false;
  }
  
  function isMathFunc(name) {
    return /^Math_/.test(name);
  }
  
  function callHasSideEffects(node) { // checks if the call itself (not the args) has side effects (or is not statically known)
    return !(node[1][0] === 'name' && isMathFunc(node[1][1]));
  }
  
  function hasSideEffects(node) { // this is 99% incomplete!
    switch (node[0]) {
      case 'num': case 'name': case 'string': return false;
      case 'unary-prefix': return hasSideEffects(node[2]);
      case 'binary': return hasSideEffects(node[2]) || hasSideEffects(node[3]);
      case 'sub': return hasSideEffects(node[1]) || hasSideEffects(node[2]);
      case 'call': {
        if (callHasSideEffects(node)) return true;
        // This is a statically known call, with no side effects. only args can side effect us
        var args = node[2];
        var num = args.length;
        for (var i = 0; i < num; i++) {
          if (hasSideEffects(args[i])) return true;
        }
        return false;
      }
      case 'conditional': return hasSideEffects(node[1]) || hasSideEffects(node[2]) || hasSideEffects(node[3]);
      case 'function': case 'defun': return false;
      case 'object': {
        var children = node[1];
        if (!Array.isArray(children)) return false;
        for (var i = 0; i < children.length; i++) {
          if (hasSideEffects(children[i][1])) return true;
        }
        return false;
      }
      case 'array': {
        var children = node[1];
        if (!Array.isArray(children)) return false;
        for (var i = 0; i < children.length; i++) {
          if (hasSideEffects(children[i])) return true;
        }
        return false;
      }
      case 'dot': {
        // In theory any property access in JS can have side effects, but not in
        // objects we assume are static.
        if (node[1][0] === 'name') {
          var name = node[1][1];
          if (name === 'Math') return false;
        }
        return true;
      }
      default: return true;
    }
  }
  
  // checks if a node has just basic operations, nothing with side effects nor that can notice side effects, which
  // implies we can move it around in the code
  function triviallySafeToMove(node, asmData) {
    var ok = true;
    traverse(node, function(node, type) {
      switch (type) {
        case 'stat': case 'binary': case 'unary-prefix': case 'assign': case 'num':
          break;
        case 'name':
          if (!(node[1] in asmData.vars) && !(node[1] in asmData.params)) ok = false;
          break;
        case 'call':
          if (callHasSideEffects(node)) ok = false;
          break;
        default:
          ok = false;
      }
    });
    return ok;
  }
  
  // Clear out empty ifs and blocks, and redundant blocks/stats and so forth
  // Operates on generated functions only
  function vacuum(ast) {
    function isEmpty(node) {
      if (!node) return true;
      if (node[0] === 'toplevel' && (!node[1] || node[1].length === 0)) return true;
      if (node[0] === 'block' && (!node[1] || (typeof node[1] != 'object') || node[1].length === 0 || (node[1].length === 1 && isEmpty(node[1])))) return true;
      return false;
    }
    function simplifyList(node, si) {
      var changed = false;
      // Merge block items into this list, thus removing unneeded |{ .. }|'s
      var statements = node[si];
      var i = 0;
      while (i < statements.length) {
        var subNode = statements[i];
        if (subNode[0] === 'block') {
          statements.splice.apply(statements, [i, 1].concat(subNode[1] || []));
          changed = true;
        } else {
          i++;
        }
      }
      // Remove empty items
      var pre = node[si].length;
      node[si] = node[si].filter(function(node) { return !isEmpty(node) });
      if (node[si].length < pre) changed = true;
      if (changed) {
        return node;
      }
    }
    function vacuumInternal(node) {
      traverseChildren(node, vacuumInternal);
      var ret;
      switch(node[0]) {
        case 'block': {
          if (node[1] && node[1].length === 1 && node[1][0][0] === 'block') {
            return node[1][0];
          } else if (typeof node[1] === 'object') {
            ret = simplifyList(node, 1);
            if (ret) return ret;
          }
        } break;
        case 'stat': {
          if (node[1][0] === 'block') {
            return node[1];
          } else if (!hasSideEffects(node[1])) {
            return emptyNode();
          }
        } break;
        case 'defun': {
          if (node[3].length === 1 && node[3][0][0] === 'block') {
            node[3] = node[3][0][1];
            return node;
          } else {
            ret = simplifyList(node, 3);
            if (ret) return ret;
          }
        } break;
        case 'do': {
          if (node[1][0] === 'num' && node[2][0] === 'toplevel' && (!node[2][1] || node[2][1].length === 0)) {
            return emptyNode();
          } else if (isEmpty(node[2]) && !hasSideEffects(node[1])) {
            return emptyNode();
          }
        } break;
        case 'label': {
          if (node[2] && node[2][0] === 'toplevel' && (!node[2][1] || node[2][1].length === 0)) {
            return emptyNode();
          }
        } break;
        case 'if': {
          var empty2 = isEmpty(node[2]), empty3 = isEmpty(node[3]), has3 = node.length === 4;
          if (!empty2 && empty3 && has3) { // empty else clauses
            return node.slice(0, 3);
          } else if (empty2 && !empty3) { // empty if blocks
            return ['if', ['unary-prefix', '!', node[1]], node[3]];
          } else if (empty2 && empty3) {
            if (hasSideEffects(node[1])) {
              return ['stat', node[1]];
            } else {
              return emptyNode();
            }
          }
        } break;
      }
    }
    traverseGeneratedFunctions(ast, function(node) {
      vacuumInternal(node);
      simplifyNotComps(node);
      removeEmptySubNodes(node);
    });
  }
  
  function getStatements(node) {
    if (node[0] === 'defun') {
      return node[3];
    } else if (node[0] === 'block') {
      return node[1];
    } else {
      return null;
    }
  }
  
  // Multiple blocks from the relooper are, in general, implemented by
  //   if (label === x) { } else if ..
  // and branching into them by
  //   if (condition) { label === x } else ..
  // We can hoist the multiple block into the condition, thus removing code and one 'if' check
  function hoistMultiples(ast) {
    traverseGeneratedFunctions(ast, function(node) {
      traverse(node, function(node, type) {
        var statements = getStatements(node);
        if (!statements) return;
        var modified = false;
        for (var i = 0; i < statements.length-1; i++) {
          var modifiedI = false;
          var pre = statements[i];
          if (pre[0] != 'if') continue;
          var post = statements[i+1];
          // Look into some block types. shell() will then recreate the shell that we looked into
          var postInner = post;
          var shellLabel = false, shellDo = false;
          while (true) {
            if (postInner[0] === 'label') {
              shellLabel = postInner[1];
              postInner = postInner[2];
            } else if (postInner[0] === 'do') {
              shellDo = postInner[1];
              postInner = postInner[2][1][0];
            } else {
              break; // give up
            }
          }
          if (postInner[0] != 'if') continue;
          // Look into this if, and its elseifs
          while (postInner && postInner[0] === 'if') {
            var cond = postInner[1];
            if (cond[0] === 'binary' && cond[1] === '==' && cond[2][0] === 'name' && cond[2][1] === 'label') {
              assert(cond[3][0] === 'num');
              // We have a valid Multiple check here. Try to hoist it, look for the source in |pre| and its else's
              var labelNum = cond[3][1];
              var labelBlock = postInner[2];
              assert(labelBlock[0] === 'block');
              var found = false;
              traverse(pre, function(preNode, preType) {
                if (!found && preType === 'assign' && preNode[2][0] === 'name' && preNode[2][1] === 'label') {
                  assert(preNode[3][0] === 'num');
                  if (preNode[3][1] === labelNum) {
                    // That's it! Hoist away. We can also throw away the label setting as its goal has already been achieved
                    found = true;
                    modifiedI = true;
                    postInner[2] = ['block', []];
                    return labelBlock;
                  }
                }
              });
            }
            postInner = postInner[3]; // Proceed to look in the else clause
          }
          if (modifiedI) {
            if (shellDo) {
              statements[i] = ['do', shellDo, ['block', [statements[i]]]];
            }
            if (shellLabel) {
              statements[i] = ['label', shellLabel, statements[i]];
            }
          }
        }
        if (modified) return node;
      });
  
      // After hoisting in this function, it is safe to remove { label = x; } blocks, because
      // if they were leading to the next code right after them, they would be hoisted, and if they
      // are going to some other place entirely, they would break or continue. The only risky
      // situation is if the code after us is a multiple, in which case we might be checking for
      // this label inside it (or in a later multiple, even)
      function tryEliminate(node) {
        if (node[0] === 'if') {
          var replaced;
          if (replaced = tryEliminate(node[2])) node[2] = replaced;
          if (node[3] && (replaced = tryEliminate(node[3]))) node[3] = replaced;
        } else {
          if (node[0] === 'block' && node[1] && node[1].length > 0) {
            var subNode = node[1][node[1].length-1];
            if (subNode[0] === 'stat' && subNode[1][0] === 'assign' && subNode[1][2][0] === 'name' &&
                subNode[1][2][1] === 'label' && subNode[1][3][0] === 'num') {
              if (node[1].length === 1) {
                return emptyNode();
              } else {
                node[1].splice(node[1].length-1, 1);
                return node;
              }
            }
          }
        }
        return false;
      }
      function getActualStatement(node) { // find the actual active statement, ignoring a label and one-time do loop
        if (node[0] === 'label') node = node[2];
        if (node[0] === 'do') node = node[2];
        if (node[0] === 'block' && node[1].length === 1) node = node[1][0];
        return node;
      }
      vacuum(node);
      traverse(node, function(node, type) {
        var statements = getStatements(node);
        if (!statements) return;
        for (var i = 0; i < statements.length-1; i++) {
          var curr = getActualStatement(statements[i]);
          var next = statements[i+1];
          if (curr[0] === 'if' && next[0] != 'if' && next[0] != 'label' && next[0] != 'do' && next[0] != 'while') {
            tryEliminate(curr);
          }
        }
      });
    });
  
    vacuum(ast);
  
    // Afterpass: Reduce
    //    if (..) { .. break|continue } else { .. }
    // to
    //    if (..) { .. break|continue } ..
    traverseGenerated(ast, function(container, type) {
      var statements = getStatements(container);
      if (!statements) return;
      for (var i = 0; i < statements.length; i++) {
        var node = statements[i];
        if (node[0] === 'if' && node[2][0] === 'block' && node[3] && node[3][0] === 'block') {
          var stat1 = node[2][1], stat2 = node[3][1];
          // If break|continue in the latter and not the former, reverse them
          if (!(stat1[stat1.length-1][0] in LOOP_FLOW) && (stat2[stat2.length-1][0] in LOOP_FLOW)) {
            var temp = node[3];
            node[3] = node[2];
            node[2] = temp;
            node[1] = flipCondition(node[1]);
            stat1 = node[2][1];
            stat2 = node[3][1];
          }
          if (stat1[stat1.length-1][0] in LOOP_FLOW) {
            statements.splice.apply(statements, [i+1, 0].concat(stat2));
            node[3] = null;
          }
        }
      }
    });
  }
  
  // Simplifies loops
  // WARNING: This assumes all loops and breaks/continues are labelled
  function loopOptimizer(ast) {
    // Remove unneeded labels and one-time (do while(0)) loops. It is convenient to do these both at once.
    function passTwo(ast) {
      var neededDos = [];
      // 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) {
          // 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]; // there may not be a label ident if this is a simple break; or continue;
          var plus = '+' + ident;
          if (lastLabel && ident && (ident === lastLabel[1] || plus === lastLabel[1])) {
            // If this is a 'do' loop, this break means we actually need it.
            neededDos.push(lastLoop);
            // We don't need the control flow command to have a label - it's referring to the current loop
            return [node[0]];
          } else {
            if (!ident) {
              // No label on the break/continue, so keep the last loop alive (no need for its label though)
              neededDos.push(lastLoop);
            } 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, []);
      // We return whether another pass is necessary
      var more = false;
      // Remove unneeded labels
      traverseGenerated(ast, function(node, type) {
        if (type === 'label' && node[1][0] === '+') {
          more = true;
          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
        }
      });
      // Remove unneeded one-time loops. We need such loops if (1) they have a label, or (2) they have a direct break so they are in neededDos.
      // First, add all labeled loops of this nature to neededDos
      traverseGenerated(ast, function(node, type) {
        if (type === 'label' && node[2][0] === 'do') {
          neededDos.push(node[2]);
        }
      });
      // Remove unneeded dos, we know who they are now
      traverseGenerated(ast, function(node, type) {
        if (type === 'do' && neededDos.indexOf(node) < 0) {
          assert(jsonCompare(node[1], ['num', 0]), 'Trying to remove a one-time do loop that is not one of our generated ones.;');
          more = true;
          return node[2];
        }
      });
      return more;
    }
  
    // Go
  
    // TODO: pass 1: Removal of unneeded continues, breaks if they get us to where we are already going. That will
    //               help the next pass.
  
    // Multiple pass two runs may be needed, as we remove one-time loops and so forth
    do {
      var more = passTwo(ast);
      vacuum(ast);
    } while (more);
  
    vacuum(ast);
  }
  
  function unVarify(vars, ret) { // transform var x=1, y=2 etc. into (x=1, y=2), i.e., the same assigns, but without a var definition
    ret = ret || [];
    ret[0] = 'stat';
    if (vars.length === 1) {
      ret[1] = ['assign', true, ['name', vars[0][0]], vars[0][1]];
    } else {
      ret[1] = [];
      var curr = ret[1];
      for (var i = 0; i < vars.length-1; i++) {
        curr[0] = 'seq';
        curr[1] = ['assign', true, ['name', vars[i][0]], vars[i][1]];
        if (i != vars.length-2) curr = curr[2] = [];
      }
      curr[2] = ['assign', true, ['name', vars[vars.length-1][0]], vars[vars.length-1][1]];
    }
    return ret;
  }
  
  // asm.js support code - normalize (convert asm.js code to 'normal' JS, without
  // annotations, plus explicit metadata) and denormalize (vice versa)
  var ASM_INT = 0;
  var ASM_DOUBLE = 1;
  var ASM_FLOAT = 2;
  var ASM_FLOAT32X4 = 3;
  var ASM_FLOAT64X2 = 4;
  var ASM_INT8X16 = 5;
  var ASM_INT16X8 = 6;
  var ASM_INT32X4 = 7;
  var ASM_BOOL8X16 = 8;
  var ASM_BOOL16X8 = 9;
  var ASM_BOOL32X4 = 10;
  var ASM_BOOL64X2 = 11;
  var ASM_NONE = 12;
  
  var ASM_SIG = {
    0: 'i',
    1: 'd',
    2: 'f',
    3: 'F',
    4: 'D',
    5: 'B',
    6: 'S',
    7: 'I',
    8: 'Z', // For Bool SIMD.js types, arbitrarily use consecutive letters ZXCV.
    9: 'X',
    10: 'C',
    11: 'V',
    12: 'v'
  };
  
  var ASM_FLOAT_ZERO = null; // TODO: share the entire node?
  
  function detectType(node, asmInfo, inVarDef) {
    // for params, +x vs x|0, for vars, 0.0 vs 0
    switch (node[0]) {
      case 'num': {
        if (node[1].toString().indexOf('.') >= 0) return ASM_DOUBLE;
        return ASM_INT;
      }
      case 'unary-prefix': {
        switch (node[1]) {
          case '+': return ASM_DOUBLE;
          case '-': return detectType(node[2], asmInfo, inVarDef);
          case '!': case '~': return ASM_INT;
        }
        break;
      }
      case 'call': {
        if (node[1][0] === 'name') {
          switch (node[1][1]) {
            case 'Math_fround':          return ASM_FLOAT;
            case 'SIMD_Float32x4':
            case 'SIMD_Float32x4_check': return ASM_FLOAT32X4;
            case 'SIMD_Float64x2':
            case 'SIMD_Float64x2_check': return ASM_FLOAT64X2;
            case 'SIMD_Int8x16':
            case 'SIMD_Int8x16_check':   return ASM_INT8X16;
            case 'SIMD_Int16x8':
            case 'SIMD_Int16x8_check':   return ASM_INT16X8;
            case 'SIMD_Int32x4':
            case 'SIMD_Int32x4_check':   return ASM_INT32X4;
            case 'SIMD_Bool8x16':
            case 'SIMD_Bool8x16_check':  return ASM_BOOL8X16;
            case 'SIMD_Bool16x8':
            case 'SIMD_Bool16x8_check':  return ASM_BOOL16X8;
            case 'SIMD_Bool32x4':
            case 'SIMD_Bool32x4_check':  return ASM_BOOL32X4;
            case 'SIMD_Bool64x2':
            case 'SIMD_Bool64x2_check':  return ASM_BOOL64X2;
            default: break;
          }
        }
        return ASM_NONE;
      }
      case 'name': {
        if (asmInfo) {
          var ret = getAsmType(node[1], asmInfo);
          if (ret !== ASM_NONE) return ret;
        }
        if (!inVarDef) {
          if (ASM_FLOAT_ZERO && ASM_FLOAT_ZERO === node[1]) return ASM_FLOAT;
          switch (node[1]) {
            case 'inf': case 'nan': return ASM_DOUBLE; // TODO: when minified
            case 'tempRet0': return ASM_INT;
          }
          return ASM_NONE;
        }
        // We are in a variable definition, where Math_fround(0) optimized into a global constant becomes f0 = Math_fround(0)
        if (!ASM_FLOAT_ZERO) ASM_FLOAT_ZERO = node[1];
        else assert(ASM_FLOAT_ZERO === node[1]);
        return ASM_FLOAT;
      }
      case 'binary': {
        switch (node[1]) {
          case '+': case '-':
          case '*': case '/': case '%': {
            var ret = detectType(node[2], asmInfo, inVarDef);
            if (ret !== ASM_NONE) return ret;
            return detectType(node[3], asmInfo, inVarDef)
          }
          case '|': case '&': case '^': case '<<': case '>>': case '>>>':
          case '==': case '!=': case '<': case '<=': case '>': case '>=': {
            return ASM_INT;
          }
        }
        break;
      }
      case 'conditional': case 'seq': {
        return detectType(node[2], asmInfo, inVarDef);
      }
      case 'sub': {
        assert(node[1][0] === 'name');
        if (!parseHeap(node[1][1])) return ASM_NONE;
        return parseHeapTemp.float ? ASM_DOUBLE : ASM_INT; // XXX ASM_FLOAT?
      }
      case 'stat': return ASM_NONE;
    }
    assert(0 , 'horrible ' + JSON.stringify(node));
  }
  
  function isAsmCoercion(node) {
    if (node[0] === 'binary' && ((node[1] === '|' && node[3][0] === 'num' && node[3][1] === 0) ||
                                 (node[1] === '>>>' && node[3][0] === 'num' && node[3][1] === 0))) return true;
    if (node[0] === 'unary-prefix' && (node[1] === '+' || (node[1] === '~' && node[2][0] === 'unary-prefix' && node[2][1] === '~'))) return true;
    return false;
  }
  
  function makeAsmCoercion(node, type) {
    switch (type) {
      case ASM_INT:       return ['binary', '|', node, ['num', 0]];
      case ASM_DOUBLE:    return ['unary-prefix', '+', node];
      case ASM_FLOAT:     return ['call', ['name', 'Math_fround'], [node]];
      case ASM_FLOAT32X4: return ['call', ['name', 'SIMD_Float32x4_check'], [node]];
      case ASM_FLOAT64X2: return ['call', ['name', 'SIMD_Float64x2_check'], [node]];
      case ASM_INT8X16:   return ['call', ['name', 'SIMD_Int8x16_check'],   [node]];
      case ASM_INT16X8:   return ['call', ['name', 'SIMD_Int16x8_check'],   [node]];
      case ASM_INT32X4:   return ['call', ['name', 'SIMD_Int32x4_check'],   [node]];
      case ASM_BOOL8X16:  return ['call', ['name', 'SIMD_Bool8x16_check'],  [node]];
      case ASM_BOOL16X8:  return ['call', ['name', 'SIMD_Bool16x8_check'],  [node]];
      case ASM_BOOL32X4:  return ['call', ['name', 'SIMD_Bool32x4_check'],  [node]];
      case ASM_BOOL64X2:  return ['call', ['name', 'SIMD_Bool64x2_check'],  [node]];
      case ASM_NONE:
      default: return node; // non-validating code, emit nothing XXX this is dangerous, we should only allow this when we know we are not validating
    }
  }
  
  function makeSignedAsmCoercion(node, type, sign) {
    if (type !== ASM_INT || sign === ASM_SIGNED) return makeAsmCoercion(node, type);
    if (sign === ASM_UNSIGNED) return ['binary', '>>>', node, ['num', 0]];
    assert(0);
  }
  
  function makeAsmCoercedZero(type) {
    switch (type) {
      case ASM_INT: return ['num', 0];
      case ASM_DOUBLE: return ['unary-prefix', '+', ['num', 0]];
      case ASM_FLOAT: {
        if (ASM_FLOAT_ZERO) {
          return ['name', ASM_FLOAT_ZERO];
        } else {
          return ['call', ['name', 'Math_fround'], [['num', 0]]];
        }
      }
      case ASM_FLOAT32X4: {
        return ['call', ['name', 'SIMD_Float32x4'], [['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_FLOAT64X2: {
        return ['call', ['name', 'SIMD_Float64x2'], [['num', 0], ['num', 0]]];
      }
      case ASM_INT8X16: {
        return ['call', ['name', 'SIMD_Int8x16'], [['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_INT16X8: {
        return ['call', ['name', 'SIMD_Int16x8'], [['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_INT32X4: {
        return ['call', ['name', 'SIMD_Int32x4'], [['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_BOOL8X16: {
        return ['call', ['name', 'SIMD_Bool8x16'], [['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_BOOL16X8: {
        return ['call', ['name', 'SIMD_Bool16x8'], [['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_BOOL32X4: {
        return ['call', ['name', 'SIMD_Bool32x4'], [['num', 0], ['num', 0], ['num', 0], ['num', 0]]];
      }
      case ASM_BOOL64X2: {
        return ['call', ['name', 'SIMD_Bool64x2'], [['num', 0], ['num', 0]]];
      }
      default: throw 'wha? ' + JSON.stringify(type) + new Error().stack;
    }
  }
  
  function makeAsmVarDef(v, type) {
    return [v, makeAsmCoercedZero(type)];
  }
  
  function getAsmType(name, asmInfo) {
    if (name in asmInfo.vars) return asmInfo.vars[name];
    if (name in asmInfo.params) return asmInfo.params[name];
    return ASM_NONE;
  }
  
  function getCombinedType(node1, node2, asmData, hint) {
    var type1 = detectType(node1, asmData);
    var type2 = detectType(node2, asmData);
    if (type1 === ASM_NONE && type2 === ASM_NONE) {
      assert(hint !== undefined);
      return hint;
    }
    if (type1 === ASM_NONE) {
      assert(type2 != ASM_NONE);
      return type2;
    } else if (type2 === ASM_NONE) {
      assert(type1 != ASM_NONE);
      return type1;
    }
    if (type1 !== type2) {
      if (type1 === hint || type2 === hint) return hint;
      assert(0, "can't figure it out " + JSON.stringify([node1, '....', node2, '     ', type1, type2, hint], null, '  '));
    }
    return type1;
  }
  
  var ASM_FLEXIBLE = 0; // small constants can be signed or unsigned, variables are also flexible
  var ASM_SIGNED = 1;
  var ASM_UNSIGNED = 2;
  var ASM_NONSIGNED = 3;
  
  function detectSign(node) {
    switch (node[0]) {
      case 'binary': {
        switch(node[1]) {
          case '|': case '&': case '^': case '<<': case '>>': return ASM_SIGNED;
          case '>>>': return ASM_UNSIGNED;
          case '+': case '-': return ASM_FLEXIBLE;
          case '*': {
            // a double, unless one is a small int and the other is an int, in
            // which case one is a num. that can't be a double, since then it
            // would be a +num.
            if (node[2][0] === 'num' || node[3][0] === 'num') return ASM_FLEXIBLE;
            return ASM_NONSIGNED;
          }
          case '/': case '%': return ASM_NONSIGNED; // without a coercion, this is double
          case '==': case '!=': case '<': case '<=': case '>': case '>=': return ASM_SIGNED;
          default: throw 'yikes ' + node[1];
        }
        break;
      }
      case 'unary-prefix': {
        switch(node[1]) {
          case '-': return ASM_FLEXIBLE;
          case '+': return ASM_NONSIGNED; // XXX double
          case '~': return ASM_SIGNED;
          case '!': return ASM_FLEXIBLE;
          default: throw 'yikes ' + node[1];
        }
        break;
      }
      case 'num': {
        var value = node[1];
        if (value < 0) return ASM_SIGNED;
        if (value > (-1>>>0) || value % 1 !== 0) return ASM_NONSIGNED;
        if (value === (value | 0)) return ASM_FLEXIBLE;
        return ASM_UNSIGNED;
      }
      case 'name': return ASM_FLEXIBLE;
      case 'conditional': case 'seq': {
        return detectSign(node[2]);
      }
      case 'call': {
        if (node[1][0] === 'name') {
          switch (node[1][1]) {
            case 'Math_fround': return ASM_NONSIGNED
            default: break;
          }
        }
      }
    }
    assert(0 , 'badd ' + JSON.stringify(node));
  }
  
  function getCombinedSign(node1, node2, hint) {
    var sign1 = detectSign(node1);
    var sign2 = detectSign(node2);
    if (sign1 === ASM_FLEXIBLE && sign2 === ASM_FLEXIBLE) {
      return ASM_FLEXIBLE;
    }
    if (sign1 === ASM_FLEXIBLE) {
      assert(sign2 != ASM_FLEXIBLE);
      return sign2;
    } else if (sign2 === ASM_FLEXIBLE) {
      assert(sign1 != ASM_FLEXIBLE);
      return sign1;
    }
    if (sign1 === sign2) return sign1;
    if (sign1 === hint || sign2 === hint) return hint;
    if ((sign1 === ASM_SIGNED && sign2 === ASM_UNSIGNED) ||
        (sign1 === ASM_UNSIGNED && sign2 === ASM_SIGNED)) {
      return ASM_FLEXIBLE;
    }
    assert(0, JSON.stringify([node1, '      ', node2, sign1, sign2, hint]));
  }
  
  function getSignature(func, asmData) {
    var ret = asmData.ret >= 0 ? ASM_SIG[asmData.ret] : 'v';
    for (var i = 0; i < func[2].length; i++) {
      ret += ASM_SIG[asmData.params[func[2][i]]];
    }
    return ret;
  }
  
  function normalizeAsm(func) {
    //printErr('pre-normalize \n\n' + astToSrc(func) + '\n\n');
    var data = {
      params: {}, // ident => ASM_* type
      vars: {}, // ident => ASM_* type
      inlines: [], // list of inline assembly copies
      ret: undefined,
    };
    // process initial params
    var stats = func[3];
    var i = 0;
    while (i < stats.length) {
      var node = stats[i];
      if (node[0] != 'stat' || node[1][0] != 'assign' || node[1][2][0] != 'name') break;
      node = node[1];
      var name = node[2][1];
      if (func[2] && func[2].indexOf(name) < 0) break; // not an assign into a parameter, but a global
      if (name in data.params) break; // already done that param, must be starting function body
      data.params[name] = detectType(node[3]);
      stats[i] = emptyNode();
      i++;
    }
    // process initial variable definitions
    outer:
    while (i < stats.length) {
      var node = stats[i];
      if (node[0] != 'var') break;
      for (var j = 0; j < node[1].length; j++) {
        var v = node[1][j];
        var name = v[0];
        var value = v[1];
        if (!(name in data.vars)) {
          data.vars[name] = detectType(value, null, true);
          v.length = 1; // make an un-assigning var
        } else {
          assert(j === 0, 'cannot break in the middle');
          break outer;
        }
      }
      i++;
    }
    // look for other var definitions and collect them
    while (i < stats.length) {
      traverse(stats[i], function(node, type) {
        if (type === 'var') {
          assert(0, 'should be no vars to fix! ' + func[1] + ' : ' + JSON.stringify(node));
        } else if (type === 'call' && node[1][0] === 'function') {
          assert(!node[1][1]); // anonymous functions only
          data.inlines.push(node[1]);
          node[1] = ['name', 'inlinejs']; // empty out body, leave arguments, so they are eliminated/minified properly
        }
      });
      i++;
    }
    // look for final 'return' statement to get return type.
    var retStmt = stats[stats.length - 1];
    if (retStmt && retStmt[0] === 'return' && retStmt[1]) {
      data.ret = detectType(retStmt[1]);
    }
    //printErr('normalized \n\n' + astToSrc(func) + '\n\nwith: ' + JSON.stringify(data));
    return data;
  }
  
  function denormalizeAsm(func, data) {
    //printErr('pre-denormalize \n\n' + astToSrc(func) + '\n\nwith: ' + JSON.stringify(data));
    var stats = func[3];
    // Remove var definitions, if any
    for (var i = 0; i < stats.length; i++) {
      if (stats[i][0] === 'var') {
        stats[i] = emptyNode();
      } else {
        if (!isEmptyNode(stats[i])) break;
      }
    }
    // calculate variable definitions
    var varDefs = [];
    for (var v in data.vars) {
      varDefs.push(makeAsmVarDef(v, data.vars[v]));
    }
    // each param needs a line; reuse emptyNodes as much as we can
    var numParams = 0;
    for (var i in data.params) numParams++;
    var emptyNodes = 0;
    while (emptyNodes < stats.length) {
      if (!isEmptyNode(stats[emptyNodes])) break;
      emptyNodes++;
    }
    var neededEmptyNodes = numParams + (varDefs.length ? 1 : 0); // params plus one big var if there are vars
    if (neededEmptyNodes > emptyNodes) {
      var args = [0, 0];
      for (var i = 0; i < neededEmptyNodes - emptyNodes; i++) args[i+2] = 0;
      stats.splice.apply(stats, args);
    } else if (neededEmptyNodes < emptyNodes) {
      stats.splice(0, emptyNodes - neededEmptyNodes);
    }
    // add param coercions
    var next = 0;
    func[2].forEach(function(param) {
      stats[next++] = ['stat', ['assign', true, ['name', param], makeAsmCoercion(['name', param], data.params[param])]];
    });
    if (varDefs.length) {
      stats[next] = ['var', varDefs];
    }
    if (data.inlines.length > 0) {
      var i = 0;
      traverse(func, function(node, type) {
        if (type === 'call' && node[1][0] === 'name' && node[1][1] === 'inlinejs') {
          node[1] = data.inlines[i++]; // swap back in the body
        }
      });
    }
    // ensure that there's a final 'return' statement if needed.
    if (data.ret !== undefined) {
      var retStmt = stats[stats.length - 1];
      if (!retStmt || retStmt[0] !== 'return') {
        stats.push(['return', makeAsmCoercedZero(data.ret)]);
      }
    }
    //printErr('denormalized \n\n' + astToSrc(func) + '\n\n');
  }
  
  function getFirstIndexInNormalized(func, data) {
    // In a normalized asm function, return the index of the first element that is not not defs or annotation
    var stats = func[3];
    var i = stats.length-1;
    while (i >= 0) {
      var stat = stats[i];
      if (stat[0] == 'var') break;
      i--;
    }
    return i+1;
  }
  
  function getStackBumpNode(ast) {
    var found = null;
    traverse(ast, function(node, type) {
      if (type === 'assign' && node[2][0] === 'name' && node[2][1] === 'STACKTOP') {
        var value = node[3];
        if (value[0] === 'name') return true;
        if (value[0] == 'binary' && value[1] == '&') return; // this is an alignment fix, ignore
        assert(value[0] == 'binary' && value[1] == '|' && value[2][0] == 'binary' && value[2][1] == '+' && value[2][2][0] == 'name' && value[2][2][1] == 'STACKTOP');
        if (value[2][3][0] !== 'num') return; // non-constant bump, ignore
        found = node;
        return true;
      }
    });
    return found;
  }
  
  function getStackBumpSize(ast) {
    var node = getStackBumpNode(ast);
    return node ? node[3][2][3][1] : 0;
  }
  
  // Name minification
  
  var RESERVED = set('do', 'if', 'in', 'for', 'new', 'try', 'var', 'env', 'let', 'case', 'else', 'enum', 'void', 'this', 'void', 'with');
  var VALID_MIN_INITS = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$';
  var VALID_MIN_LATERS = VALID_MIN_INITS + '0123456789';
  
  var minifiedNames = [];
  var minifiedState = [0];
  
  function ensureMinifiedNames(n) { // make sure the nth index in minifiedNames exists. done 100% deterministically
    while (minifiedNames.length < n+1) {
      // generate the current name
      var name = VALID_MIN_INITS[minifiedState[0]];
      for (var i = 1; i < minifiedState.length; i++) {
        name += VALID_MIN_LATERS[minifiedState[i]];
      }
      if (!(name in RESERVED)) minifiedNames.push(name);
      // increment the state
      var i = 0;
      while (1) {
        minifiedState[i]++;
        if (minifiedState[i] < (i === 0 ? VALID_MIN_INITS : VALID_MIN_LATERS).length) break;
        // overflow
        minifiedState[i] = 0;
        i++;
        if (i === minifiedState.length) minifiedState.push(-1); // will become 0 after increment in next loop head
      }
    }
  }
  
  // Very simple 'registerization', coalescing of variables into a smaller number.
  //
  // We do not optimize when there are switches, so this pass only makes sense with
  // relooping.
  // TODO: Consider how this fits in with the rest of the optimization toolchain. Do
  //       we still need the eliminator? Closure? And in what order? Perhaps just
  //       closure simple?
  function registerize(ast) {
    traverseGeneratedFunctions(ast, function(fun) {
      if (asm) var asmData = normalizeAsm(fun);
      if (!asm) {
        var hasFunction = false;
        traverse(fun, function(node, type) {
          if (type === 'function') hasFunction = true;
        });
        if (hasFunction) {
          return; // inline assembly, and not asm (where we protect it in normalize/denormalize), so abort registerize pass
        }
      }
      // Add parameters as a first (fake) var (with assignment), so they get taken into consideration
      var params = {}; // note: params are special, they can never share a register between them (see later)
      if (fun[2] && fun[2].length) {
        var assign = ['num', 0];
        fun[3].unshift(['var', fun[2].map(function(param) {
          params[param] = 1;
          return [param, assign];
        })]);
      }
      if (asm) {
        // copy params into vars
        for (var p in asmData.params) asmData.vars[p] = asmData.params[p];
        //printErr('fake params: \n\n' + astToSrc(fun) + '\n\n');
      }
      // Replace all var definitions with assignments; we will add var definitions at the top after we registerize
      // We also mark local variables - i.e., having a var definition
      var localVars = {};
      var allVars = {};
      var hasSwitch = false; // we cannot optimize variables if there is a switch, unless in asm mode
      traverse(fun, function(node, type) {
        if (type === 'var') {
          node[1].forEach(function(defined) { localVars[defined[0]] = 1 });
          var vars = node[1].filter(function(varr) { return varr[1] });
          if (vars.length >= 1) {
            return unVarify(vars);
          } else {
            return emptyNode();
          }
        } else if (type === 'switch') {
          hasSwitch = true;
        } else if (type === 'name') {
          allVars[node[1]] = 1;
        }
      });
      vacuum(fun);
      var regTypes = {};
      function getNewRegName(num, name) {
        var ret;
        if (!asm) {
          ret = 'r' + num;
        } else {
          var type = asmData.vars[name];
          switch (type) {
            case ASM_INT:       ret = 'i'; break;
            case ASM_DOUBLE:    ret = 'd'; break;
            case ASM_FLOAT:     ret = 'f'; break;
            case ASM_FLOAT32X4: ret = 'F4'; break;
            case ASM_FLOAT64X2: ret = 'F2'; break;
            case ASM_INT8X16:   ret = 'I16'; break;
            case ASM_INT16X8:   ret = 'I8'; break;
            case ASM_INT32X4:   ret = 'I4'; break;
            case ASM_BOOL8X16:  ret = 'B16'; break;
            case ASM_BOOL16X8:  ret = 'B8'; break;
            case ASM_BOOL32X4:  ret = 'B4'; break;
            case ASM_BOOL64X2:  ret = 'B2'; break;
            case ASM_NONE:      ret = 'Z'; break;
            default: assert(false, 'type ' + type + ' doesn\'t have a name yet');
          }
          ret += num;
          regTypes[ret] = type;
        }
        if (ret in allVars) {
          assert(ret in localVars, 'register shadows non-local name');
        }
        return ret;
      }
      // Find the # of uses of each variable.
      // While doing so, check if all a variable's uses are dominated in a simple
      // way by a simple assign, if so, then we can assign its register to it
      // just for its definition to its last use, and not to the entire toplevel loop,
      // we call such variables "optimizable"
      var varUses = {};
      var level = 1;
      var levelDominations = {};
      var varLevels = {};
      var possibles = {};
      var unoptimizables = {};
      function purgeLevel() {
        // Invalidate all dominating on this level, further users make it unoptimizable
        for (var name in levelDominations[level]) {
          varLevels[name] = 0;
        }
        levelDominations[level] = null;
        level--;
      }
      traverse(fun, function possibilifier(node, type) {
        if (type === 'name') {
          var name = node[1];
          if (localVars[name]) {
            if (!varUses[name]) varUses[name] = 0;
            varUses[name]++;
            if (possibles[name] && !varLevels[name]) unoptimizables[name] = 1; // used outside of simple domination
          }
        } else if (type === 'assign' && typeof node[1] != 'string') {
          if (node[2] && node[2][0] === 'name') {
            var name = node[2][1];
            // if local and not yet used, this might be optimizable if we dominate
            // all other uses
            if (localVars[name] && !varUses[name] && !varLevels[name]) {
              possibles[name] = 1;
              varLevels[name] = level;
              if (!levelDominations[level]) levelDominations[level] = {};
              levelDominations[level][name] = 1;
            }
          }
        } else if (type in CONTROL_FLOW) {
          // recurse children, in the context of a loop
          switch(type) {
            case 'while': case 'do': {
              traverse(node[1], possibilifier);
              level++;
              traverse(node[2], possibilifier);
              purgeLevel();
              break;
            }
            case 'for': {
              traverse(node[1], possibilifier);
              for (var i = 2; i <= 4; i++) {
                level++;
                traverse(node[i], possibilifier);
                purgeLevel();
              }
              break;
            }
            case 'if': {
              traverse(node[1], possibilifier);
              level++;
              traverse(node[2], possibilifier);
              purgeLevel();
              if (node[3]) {
                level++;
                traverse(node[3], possibilifier);
                purgeLevel();
              }
              break;
            }
            case 'switch': {
              traverse(node[1], possibilifier);
              var cases = node[2];
              for (var i = 0; i < cases.length; i++) {
                level++;
                traverse(cases[i][1], possibilifier);
                purgeLevel();
              }
              break;
            }
            default: throw dumpAst(node);
          }
          return null; // prevent recursion into children, which we already did
        }
      });
      var optimizables = {};
      if (!hasSwitch || asm) {
        for (var possible in possibles) {
          if (!unoptimizables[possible]) optimizables[possible] = 1;
        }
      }
  
      //printErr('optimizables: ' + JSON.stringify(optimizables));
      //printErr('unoptimizables: ' + JSON.stringify(unoptimizables));
  
      // Go through the function's code, assigning 'registers'.
      // The only tricky bit is to keep variables locked on a register through loops,
      // since they can potentially be returned to. Optimizable variables lock onto
      // loops that they enter, unoptimizable variables lock in a conservative way
      // into the topmost loop.
      // Note that we cannot lock onto a variable in a loop if it was used and free'd
      // before! (then they could overwrite us in the early part of the loop). For now
      // we just use a fresh register to make sure we avoid this, but it could be
      // optimized to check for safe registers (free, and not used in this loop level).
      var varRegs = {}; // maps variables to the register they will use all their life
      var freeRegsClasses = asm ? [[], [], [], [], [], [], [], [], [], [], [], [], []] : []; // two classes for asm, one otherwise XXX - hardcoded length
      var nextReg = 1;
      var fullNames = {};
      var loopRegs = {}; // for each loop nesting level, the list of bound variables
      var loops = 0; // 0 is toplevel, 1 is first loop, etc
      var saved = 0;
      var activeOptimizables = {};
      var optimizableLoops = {};
      var paramRegs = {}; // true if the register is used by a parameter (and so needs no def at start of function; also cannot
                          // be shared with another param, each needs its own)
      function decUse(name) {
        if (!varUses[name]) return false; // no uses left, or not a relevant variable
        if (optimizables[name]) activeOptimizables[name] = 1;
        var reg = varRegs[name];
        if (asm) assert(name in asmData.vars, name);
        var freeRegs = asm ? freeRegsClasses[asmData.vars[name]] : freeRegsClasses;
        if (!reg) {
          // acquire register
          if (optimizables[name] && freeRegs.length > 0 &&
              !(params[name] && paramRegs[freeRegs[freeRegs.length-1]])) { // do not share registers between parameters
            reg = freeRegs.pop();
            saved++;
          } else {
            reg = nextReg++;
            fullNames[reg] = getNewRegName(reg, name);
            if (params[name]) paramRegs[reg] = 1;
          }
          varRegs[name] = reg;
        }
        varUses[name]--;
        assert(varUses[name] >= 0);
        if (varUses[name] === 0) {
          if (optimizables[name]) delete activeOptimizables[name];
          // If we are not in a loop, or we are optimizable and not bound to a loop
          // (we might have been in one but left it), we can free the register now.
          if (loops === 0 || (optimizables[name] && !optimizableLoops[name])) {
            // free register
            freeRegs.push(reg);
          } else {
            // when the relevant loop is exited, we will free the register
            var releventLoop = optimizables[name] ? (optimizableLoops[name] || 1) : 1;
            if (!loopRegs[releventLoop]) loopRegs[releventLoop] = [];
            loopRegs[releventLoop].push(reg);
          }
        }
        return true;
      }
      traverse(fun, function(node, type) { // XXX we rely on traversal order being the same as execution order here
        if (type === 'name') {
          var name = node[1];
          if (decUse(name)) {
            node[1] = fullNames[varRegs[name]];
          }
        } else if (type in LOOP) {
          loops++;
          // Active optimizables lock onto this loop, if not locked onto one that encloses this one
          for (var name in activeOptimizables) {
            if (!optimizableLoops[name]) {
              optimizableLoops[name] = loops;
            }
          }
        }
      }, function(node, type) {
        if (type in LOOP) {
          // Free registers that were locked to this loop
          if (loopRegs[loops]) {
            if (asm) {
              loopRegs[loops].forEach(function(loopReg) {
                freeRegsClasses[regTypes[fullNames[loopReg]]].push(loopReg);
              });
            } else {
              freeRegsClasses = freeRegsClasses.concat(loopRegs[loops]);
            }
            loopRegs[loops].length = 0;
          }
          loops--;
        }
      });
      if (fun[2] && fun[2].length) {
        fun[2].length = 0; // clear params, we will fill with registers
        fun[3].shift(); // remove fake initial var
      }
      //printErr('var regs: ' + JSON.stringify(varRegs) + '\n\nparam regs: ' + JSON.stringify(paramRegs));
      if (!asm) {
        if (nextReg > 1) {
          var vars = [];
          for (var i = 1; i < nextReg; i++) {
            var reg = fullNames[i];
            if (!paramRegs[i]) {
              vars.push([reg]);
            } else {
              fun[2].push(reg);
            }
          }
          if (vars.length > 0) getStatements(fun).unshift(['var', vars]);
        }
      } else {
        //printErr('unfake params: \n\n' + astToSrc(fun) + '\n\n');
        var finalAsmData = {
          params: {},
          vars: {},
          inlines: asmData.inlines,
          ret: asmData.ret,
        };
        for (var i = 1; i < nextReg; i++) {
          var reg = fullNames[i];
          var type = regTypes[reg];
          if (!paramRegs[i]) {
            finalAsmData.vars[reg] = type;
          } else {
            finalAsmData.params[reg] = type;
            fun[2].push(reg);
          }
        }
        denormalizeAsm(fun, finalAsmData);
      }
    });
  }
  
  
  // Assign variables to 'registers', coalescing them onto a smaller number of shared
  // variables.
  //
  // This does the same job as 'registerize' above, but burns a lot more cycles trying
  // to reduce the total number of register variables.  Key points about the operation:
  //
  //   * we decompose the AST into a flow graph and perform a full liveness
  //     analysis, to determine which variables are live at each point.
  //
  //   * variables that are live concurrently are assigned to different registers.
  //
  //   * variables that are linked via 'x=y' style statements are assigned the same
  //     register if possible, so that the redundant assignment can be removed.
  //     (e.g. assignments used to pass state around through loops).
  //
  //   * any code that cannot be reached through the flow-graph is removed.
  //     (e.g. redundant break statements like 'break L123; break;').
  //
  //   * any assignments that we can prove are not subsequently used are removed.
  //     (e.g. unnecessary assignments to the 'label' variable).
  //
  function registerizeHarder(ast) {
    assert(asm);
  
    traverseGeneratedFunctions(ast, function(fun) {
  
      // Do not try to process non-validating methods, like the heap replacer
      var abort = false;
      traverse(fun, function(node, type) {
        if (type === 'new') abort = true;
      });
      if (abort) return;
  
      // Do not process the dceable helper function for wasm, which declares
      // types, we need to alive for asm2wasm
      if (fun[1] == '__emscripten_dceable_type_decls') return;
  
      var asmData = normalizeAsm(fun);
  
      var localVars = asmData.vars;
      for (var name in asmData.params) {
        localVars[name] = asmData.params[name];
      }
  
      // Utilities for allocating register variables.
      // We need distinct register pools for each type of variable.
  
      var allRegsByType = [{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}]; // XXX - hardcoded length
      var regPrefixByType = ['i', 'd', 'f', 'F4', 'F2', 'I16', 'I8', 'I4', 'B16', 'B8', 'B4', 'B2', 'n'];
      var nextReg = 1;
  
      function createReg(forName) {
        // Create a new register of type suitable for the given variable name.
        var allRegs = allRegsByType[localVars[forName]];
        var reg = nextReg++;
        allRegs[reg] = regPrefixByType[localVars[forName]] + reg;
        return reg;
      }
  
      // Traverse the tree in execution order and synthesize a basic flow-graph.
      // It's convenient to build a kind of "dual" graph where the nodes identify
      // the junctions between blocks at which control-flow may branch, and each
      // basic block is an edge connecting two such junctions.
      // For each junction we store:
      //    * set of blocks that originate at the junction
      //    * set of blocks that terminate at the junction
      // For each block we store:
      //    * a single entry junction
      //    * a single exit junction
      //    * a 'use' and 'kill' set of names for the block
      //    * full sequence of 'name' and 'assign' nodes in the block
      //    * whether each such node appears as part of a larger expression
      //      (and therefore cannot be safely eliminated)
      //    * set of labels that can be used to jump to this block
  
      var junctions = [];
      var blocks = [];
      var currEntryJunction = null;
      var nextBasicBlock = null;
      var isInExpr = 0;
      var activeLabels = [{}];
      var nextLoopLabel = null;
  
      var ENTRY_JUNCTION = 0;
      var EXIT_JUNCTION = 1;
      var ENTRY_BLOCK = 0;
  
      function addJunction() {
        // Create a new junction, without inserting it into the graph.
        // This is useful for e.g. pre-allocating an exit node.
        var id = junctions.length;
        junctions[id] = {id: id, inblocks: {}, outblocks: {}};
        return id;
      }
  
      function markJunction(id) {
        // Mark current traversal location as a junction.
        // This makes a new basic block exiting at this position.
        if (id === undefined || id === null) {
          id = addJunction();
        }
        joinJunction(id, true);
        return id;
      }
  
      function setJunction(id, force) {
        // Set the next entry junction to the given id.
        // This can be used to enter at a previously-declared point.
        // You can't return to a junction with no incoming blocks
        // unless the 'force' parameter is specified.
        assert(nextBasicBlock.nodes.length === 0, 'refusing to abandon an in-progress basic block')
        if (force || setSize(junctions[id].inblocks) > 0) {
          currEntryJunction = id;
        } else {
          currEntryJunction = null;
        }
      }
  
      function joinJunction(id, force) {
        // Complete the pending basic block by exiting at this position.
        // This can be used to exit at a previously-declared point.
        if (currEntryJunction !== null) {
          nextBasicBlock.id = blocks.length;
          nextBasicBlock.entry = currEntryJunction;
          nextBasicBlock.exit = id;
          junctions[currEntryJunction].outblocks[nextBasicBlock.id] = 1;
          junctions[id].inblocks[nextBasicBlock.id] = 1;
          blocks.push(nextBasicBlock);
        }
        nextBasicBlock = { id: null, entry: null, exit: null, labels: {}, nodes: [], isexpr: [], use: {}, kill: {} };
        setJunction(id, force);
        return id;
      }
  
      function pushActiveLabels(onContinue, onBreak) {
        // Push the target junctions for continuing/breaking a loop.
        // This should be called before traversing into a loop.
        var prevLabels = activeLabels[activeLabels.length-1];
        var newLabels = copy(prevLabels);
        newLabels[null] = [onContinue, onBreak];
        if (nextLoopLabel) {
          newLabels[nextLoopLabel] = [onContinue, onBreak];
          nextLoopLabel = null;
        }
        // An unlabelled 'continue' should jump to innermost loop,
        // ignoring any nested 'switch' statements.
        if (onContinue === null && prevLabels[null]) {
          newLabels[null][0] = prevLabels[null][0];
        }
        activeLabels.push(newLabels);
      }
  
      function popActiveLabels() {
        // Pop the target junctions for continuing/breaking a loop.
        // This should be called after traversing into a loop.
        activeLabels.pop();
      }
  
      function markNonLocalJump(type, label) {
        // Complete a block via 'return', 'break' or 'continue'.
        // This joins the targetted junction and then sets the current junction to null.
        // Any code traversed before we get back to an existing junction is dead code.
        if (type === 'return') {
          joinJunction(EXIT_JUNCTION);
        } else {
          label = label ? label : null;
          var targets = activeLabels[activeLabels.length-1][label];
          assert(targets, 'jump to unknown label');
          if (type === 'continue') {
            joinJunction(targets[0]);
          } else if (type === 'break') {
            joinJunction(targets[1]);
          } else {
            assert(false, 'unknown jump node type');
          }
        }
        currEntryJunction = null;
      }
  
      function addUseNode(node) {
        // Mark a use of the given name node in the current basic block.
        assert(node[0] === 'name', 'not a use node');
        var name = node[1];
        if (name in localVars) {
          nextBasicBlock.nodes.push(node);
          nextBasicBlock.isexpr.push(isInExpr);
          if (!nextBasicBlock.kill[name]) {
            nextBasicBlock.use[name] = 1;
          }
        }
      }
  
      function addKillNode(node) {
        // Mark an assignment to the given name node in the current basic block.
        assert(node[0] === 'assign', 'not a kill node');
        assert(node[1] === true, 'not a kill node');
        assert(node[2][0] === 'name', 'not a kill node');
        var name = node[2][1];
        if (name in localVars) {
          nextBasicBlock.nodes.push(node);
          nextBasicBlock.isexpr.push(isInExpr);
          nextBasicBlock.kill[name] = 1;
        }
      }
  
      function lookThroughCasts(node) {
        // Look through value-preserving casts, like "x | 0" => "x"
        if (node[0] === 'binary' && node[1] === '|') {
          if (node[3][0] === 'num' && node[3][1] === 0) {
            return lookThroughCasts(node[2]);
          }
        }
        return node;
      }
  
      function addBlockLabel(node) {
        assert(nextBasicBlock.nodes.length === 0, 'cant add label to an in-progress basic block')
        if (node[0] === 'num') {
          nextBasicBlock.labels[node[1]] = 1;
        }
      }
  
      function isTrueNode(node) {
        // Check if the given node is statically truthy.
        return (node[0] === 'num' && node[1] != 0);
      }
  
      function isFalseNode(node) {
        // Check if the given node is statically falsy.
        return (node[0] === 'num' && node[1] == 0);
      }
  
      function morphNode(node, newNode) {
        // In-place morph a node into some other type of node.
        var i = 0;
        while (i < node.length && i < newNode.length) {
          node[i] = newNode[i];
          i++;
        }
        while (i < newNode.length) {
          node.push(newNode[i]);
          i++;
        }
        if (node.length > newNode.length) {
          node.length = newNode.length;
        }
      }
  
      function buildFlowGraph(node) {
        // Recursive function to build up the flow-graph.
        // It walks the tree in execution order, calling the above state-management
        // functions at appropriate points in the traversal.
        var type = node[0];
  
        // Any code traversed without an active entry junction must be dead,
        // as the resulting block could never be entered. Let's remove it.
        if (currEntryJunction === null && junctions.length > 0) {
          morphNode(node, ['block', []]);
          return;
        }
  
        // Traverse each node type according to its particular control-flow semantics.
        switch (type) {
          case 'defun':
            var jEntry = markJunction();
            assert(jEntry === ENTRY_JUNCTION);
            var jExit = addJunction();
            assert(jExit === EXIT_JUNCTION);
            for (var i = 0; i < node[3].length; i++) {
              buildFlowGraph(node[3][i]);
            }
            joinJunction(jExit);
            break;
          case 'if':
            isInExpr++;
            buildFlowGraph(node[1]);
            isInExpr--;
            var jEnter = markJunction();
            var jExit = addJunction();
            if (node[2]) {
              // Detect and mark "if (label == N) { <labelled block> }".
              if (node[1][0] === 'binary' && node[1][1] === '==') {
                var lhs = lookThroughCasts(node[1][2]);
                if (lhs[0] === 'name' && lhs[1] === 'label') {
                  addBlockLabel(lookThroughCasts(node[1][3]));
                }
              }
              buildFlowGraph(node[2]);
            }
            joinJunction(jExit);
            setJunction(jEnter);
            if (node[3]) {
              buildFlowGraph(node[3]);
            }
            joinJunction(jExit);
            break;
          case 'conditional':
            isInExpr++;
            // If the conditional has no side-effects, we can treat it as a single
            // block, which might open up opportunities to remove it entirely.
            if (!hasSideEffects(node)) {
              buildFlowGraph(node[1]);
              if (node[2]) {
                buildFlowGraph(node[2]);
              }
              if (node[3]) {
                buildFlowGraph(node[3]);
              }
            } else {
              buildFlowGraph(node[1]);
              var jEnter = markJunction();
              var jExit = addJunction();
              if (node[2]) {
                buildFlowGraph(node[2]);
              }
              joinJunction(jExit);
              setJunction(jEnter);
              if (node[3]) {
                buildFlowGraph(node[3]);
              }
              joinJunction(jExit);
            }
            isInExpr--;
            break;
          case 'while':
            // Special-case "while (1) {}" to use fewer junctions,
            // since emscripten generates a lot of these.
            if (isTrueNode(node[1])) {
              var jLoop = markJunction();
              var jExit = addJunction();
              pushActiveLabels(jLoop, jExit);
              buildFlowGraph(node[2]);
              popActiveLabels();
              joinJunction(jLoop);
              setJunction(jExit);
            } else {
              var jCond = markJunction();
              var jLoop = addJunction();
              var jExit = addJunction();
              isInExpr++;
              buildFlowGraph(node[1]);
              isInExpr--;
              joinJunction(jLoop);
              pushActiveLabels(jCond, jExit);
              buildFlowGraph(node[2]);
              popActiveLabels();
              joinJunction(jCond);
              // An empty basic-block linking condition exit to loop exit.
              setJunction(jLoop);
              joinJunction(jExit);
            }
            break;
          case 'do':
            // Special-case "do {} while (1)" and "do {} while (0)" to use
            // fewer junctions, since emscripten generates a lot of these.
            if (isFalseNode(node[1])) {
              var jExit = addJunction();
              pushActiveLabels(jExit, jExit);
              buildFlowGraph(node[2]);
              popActiveLabels();
              joinJunction(jExit);
            } else if (isTrueNode(node[1])) {
              var jLoop = markJunction();
              var jExit = addJunction();
              pushActiveLabels(jLoop, jExit);
              buildFlowGraph(node[2]);
              popActiveLabels();
              joinJunction(jLoop);
              setJunction(jExit);
            } else {
              var jLoop = markJunction();
              var jCond = addJunction();
              var jCondExit = addJunction();
              var jExit = addJunction();
              pushActiveLabels(jCond, jExit);
              buildFlowGraph(node[2]);
              popActiveLabels();
              joinJunction(jCond);
              isInExpr++;
              buildFlowGraph(node[1]);
              isInExpr--;
              joinJunction(jCondExit);
              joinJunction(jLoop);
              setJunction(jCondExit);
              joinJunction(jExit);
            }
            break;
          case 'for':
            var jTest = addJunction();
            var jBody = addJunction();
            var jStep = addJunction();
            var jExit = addJunction();
            buildFlowGraph(node[1]);
            joinJunction(jTest);
            isInExpr++;
            buildFlowGraph(node[2]);
            isInExpr--;
            joinJunction(jBody);
            pushActiveLabels(jStep, jExit);
            buildFlowGraph(node[4]);
            popActiveLabels();
            joinJunction(jStep);
            buildFlowGraph(node[3]);
            joinJunction(jTest);
            setJunction(jBody);
            joinJunction(jExit);
            break;
          case 'label':
            assert(node[2][0] in BREAK_CAPTURERS, 'label on non-loop, non-switch statement')
            nextLoopLabel = node[1];
            buildFlowGraph(node[2]);
            break;
          case 'switch':
            // Emscripten generates switch statements of a very limited
            // form: all case clauses are numeric literals, and all
            // case bodies end with a (maybe implicit) break.  So it's
            // basically equivalent to a multi-way 'if' statement.
            isInExpr++;
            buildFlowGraph(node[1]);
            isInExpr--;
            var condition = lookThroughCasts(node[1]);
            var jCheckExit = markJunction();
            var jExit = addJunction();
            pushActiveLabels(null, jExit);
            var hasDefault = false;
            for (var i=0; i<node[2].length; i++) {
              setJunction(jCheckExit);
              // All case clauses are either 'default' or a numeric literal.
              if (!node[2][i][0]) {
                hasDefault = true;
              } else {
                // Detect switches dispatching to labelled blocks.
                if (condition[0] === 'name' && condition[1] === 'label') {
                  addBlockLabel(lookThroughCasts(node[2][i][0]));
                }
              }
              for (var j = 0; j < node[2][i][1].length; j++) {
                buildFlowGraph(node[2][i][1][j]);
              }
              // Control flow will never actually reach the end of the case body.
              // If there's live code here, assume it jumps to case exit.
              if (currEntryJunction !== null && nextBasicBlock.nodes.length > 0) {
                if (node[2][i][0]) {
                  markNonLocalJump('return');
                } else {
                  joinJunction(jExit);
                }
              }
            }
            // If there was no default case, we also need an empty block
            // linking straight from the test evaluation to the exit.
            if (!hasDefault) {
              setJunction(jCheckExit);
            }
            joinJunction(jExit);
            popActiveLabels();
            break;
          case 'return':
            if (node[1]) {
              isInExpr++;
              buildFlowGraph(node[1]);
              isInExpr--;
            }
            markNonLocalJump(type);
            break;
          case 'break':
          case 'continue':
            markNonLocalJump(type, node[1]);
            break;
          case 'assign':
            isInExpr++;
            buildFlowGraph(node[3]);
            isInExpr--;
            if (node[1] === true && node[2][0] === 'name') {
              addKillNode(node);
            } else {
              buildFlowGraph(node[2]);
            }
            break;
          case 'name':
            addUseNode(node);
            break;
          case 'block':
          case 'toplevel':
            if (node[1]) {
              for (var i = 0; i < node[1].length; i++) {
                buildFlowGraph(node[1][i]);
              }
            }
            break;
          case 'stat':
            buildFlowGraph(node[1]);
            break;
          case 'unary-prefix':
          case 'unary-postfix':
            isInExpr++;
            buildFlowGraph(node[2]);
            isInExpr--;
            break;
          case 'binary':
            isInExpr++;
            buildFlowGraph(node[2]);
            buildFlowGraph(node[3]);
            isInExpr--;
            break;
          case 'call':
            isInExpr++;
            buildFlowGraph(node[1]);
            if (node[2]) {
              for (var i = 0; i < node[2].length; i++) {
                buildFlowGraph(node[2][i]);
              }
            }
            isInExpr--;
            // If the call is statically known to throw,
            // treat it as a jump to function exit.
            if (!isInExpr && node[1][0] === 'name') {
              if (node[1][1] in FUNCTIONS_THAT_ALWAYS_THROW) {
                markNonLocalJump('return');
              }
            }
            break;
          case 'seq':
          case 'sub':
            isInExpr++;
            buildFlowGraph(node[1]);
            buildFlowGraph(node[2]);
            isInExpr--;
            break;
          case 'dot':
          case 'throw':
            isInExpr++;
            buildFlowGraph(node[1]);
            isInExpr--;
            break;
          case 'num':
          case 'string':
          case 'var':
            break;
          default:
            printErr(JSON.stringify(node));
            assert(false, 'unsupported node type: ' + type);
        }
      }
      buildFlowGraph(fun);
  
      assert(setSize(junctions[ENTRY_JUNCTION].inblocks) === 0, 'function entry must have no incoming blocks');
      assert(setSize(junctions[EXIT_JUNCTION].outblocks) === 0, 'function exit must have no outgoing blocks');
      assert(blocks[ENTRY_BLOCK].entry === ENTRY_JUNCTION, 'block zero must be the initial block');
  
      // Fix up implicit jumps done by assigning to the 'label' variable.
      // If a block ends with an assignment to 'label' and there's another block
      // with that value of 'label' as precondition, we tweak the flow graph so
      // that the former jumps straight to the later.
  
      var labelledBlocks = {};
      var labelledJumps = [];
      FINDLABELLEDBLOCKS:
      for (var i = 0; i < blocks.length; i++) {
        var block = blocks[i];
        // Does it have any labels as preconditions to its entry?
        for (var labelVal in block.labels) {
          // If there are multiple blocks with the same label, all bets are off.
          // This seems to happen sometimes for short blocks that end with a return.
          // TODO: it should be safe to merge the duplicates if they're identical.
          if (labelVal in labelledBlocks) {
            labelledBlocks = {};
            labelledJumps = [];
            break FINDLABELLEDBLOCKS;
          }
          labelledBlocks[labelVal] = block;
        }
        // Does it assign a specific label value at exit?
        if ('label' in block.kill) {
          var finalNode = block.nodes[block.nodes.length - 1];
          if (finalNode[0] === 'assign' && finalNode[2][1] === 'label') {
            // If labels are computed dynamically then all bets are off.
            // This can happen due to indirect branching in llvm output.
            if (finalNode[3][0] !== 'num') {
              labelledBlocks = {};
              labelledJumps = [];
              break FINDLABELLEDBLOCKS;
            }
            labelledJumps.push([finalNode[3][1], block]);
          } else {
            // If label is assigned a non-zero value elsewhere in the block
            // then all bets are off.  This can happen e.g. due to outlining
            // saving/restoring label to the stack.
            for (var j = 0; j < block.nodes.length - 1; j++) {
              if (block.nodes[j][0] === 'assign' && block.nodes[j][2][1] === 'label') {
                if (block.nodes[j][3][0] !== 'num' || block.nodes[j][3][1] !== 0) {
                  labelledBlocks = {};
                  labelledJumps = [];
                  break FINDLABELLEDBLOCKS;
                }
              }
            }
          }
        }
      }
      for (var labelVal in labelledBlocks) {
        var block = labelledBlocks[labelVal];
        // Disconnect it from the graph, and create a
        // new junction for jumps targetting this label.
        delete junctions[block.entry].outblocks[block.id];
        block.entry = addJunction();
        junctions[block.entry].outblocks[block.id] = 1;
        // Add a fake use of 'label' to keep it alive in predecessor.
        block.use['label'] = 1;
        block.nodes.unshift(['name', 'label']);
        block.isexpr.unshift(1);
      }
      for (var i = 0; i < labelledJumps.length; i++) {
        var labelVal = labelledJumps[i][0];
        var block = labelledJumps[i][1];
        var targetBlock = labelledBlocks[labelVal];
        if (targetBlock) {
          // Redirect its exit to entry of the target block.
          delete junctions[block.exit].inblocks[block.id];
          block.exit = targetBlock.entry;
          junctions[block.exit].inblocks[block.id] = 1;
        }
      }
      labelledBlocks = null;
      labelledJumps = null;
  
      // Do a backwards data-flow analysis to determine the set of live
      // variables at each junction, and to use this information to eliminate
      // any unused assignments.
      // We run two nested phases.  The inner phase builds the live set for each
      // junction.  The outer phase uses this to try to eliminate redundant
      // stores in each basic block, which might in turn affect liveness info.
  
      function analyzeJunction(junc) {
        // Update the live set for this junction.
        var live = {};
        for (var b in junc.outblocks) {
          var block = blocks[b];
          var liveSucc = junctions[block.exit].live || {};
          for (var name in liveSucc) {
            if (!(name in block.kill)) {
              live[name] = 1;
            }
          }
          for (var name in block.use) {
            live[name] = 1;
          }
        }
        junc.live = live;
      }
  
      function analyzeBlock(block) {
        // Update information about the behaviour of the block.
        // This includes the standard 'use' and 'kill' information,
        // plus a 'link' set naming values that flow through from entry
        // to exit, possibly changing names via simple 'x=y' assignments.
        // As we go, we eliminate assignments if the variable is not
        // subsequently used.
        var live = copy(junctions[block.exit].live);
        var use = {};
        var kill = {};
        var link = {};
        var lastUseLoc = {};
        var firstDeadLoc = {};
        var firstKillLoc = {};
        var lastKillLoc = {};
        for (var name in live) {
          link[name] = name;
          lastUseLoc[name] = block.nodes.length;
          firstDeadLoc[name] = block.nodes.length;
        }
        for (var j = block.nodes.length - 1; j >=0 ; j--) {
          var node = block.nodes[j];
          if (node[0] === 'name') {
            var name = node[1];
            live[name] = 1;
            use[name] = j;
            if (lastUseLoc[name] === undefined) {
              lastUseLoc[name] = j;
              firstDeadLoc[name] = j;
            }
          } else {
            var name = node[2][1];
            // We only keep assignments if they will be subsequently used.
            if (name in live) {
              kill[name] = 1;
              delete use[name];
              delete live[name];
              firstDeadLoc[name] = j;
              firstKillLoc[name] = j;
              if (lastUseLoc[name] === undefined) {
                lastUseLoc[name] = j;
              }
              if (lastKillLoc[name] === undefined) {
                lastKillLoc[name] = j;
              }
              // If it's an "x=y" and "y" is not live, then we can create a
              // flow-through link from "y" to "x".  If not then there's no
              // flow-through link for "x".
              var oldLink = link[name];
              if (oldLink) {
                delete link[name];
                if (node[3][0] === 'name') {
                  if (node[3][1] in localVars) {
                    link[node[3][1]] = oldLink;
                  }
                }
              }
            } else {
              // The result of this assignment is never used, so delete it.
              // We may need to keep the RHS for its value or its side-effects.
              function removeUnusedNodes(j, n) {
                for (var name in lastUseLoc) {
                  lastUseLoc[name] -= n;
                }
                for (var name in firstKillLoc) {
                  firstKillLoc[name] -= n;
                }
                for (var name in lastKillLoc) {
                  lastKillLoc[name] -= n;
                }
                for (var name in firstDeadLoc) {
                  firstDeadLoc[name] -= n;
                }
                block.nodes.splice(j, n);
                block.isexpr.splice(j, n);
              }
              if (block.isexpr[j] || hasSideEffects(node[3])) {
                morphNode(node, node[3]);
                removeUnusedNodes(j, 1);
              } else {
                var numUsesInExpr = 0;
                traverse(node[3], function(node, type) {
                  if (type === 'name' && node[1] in localVars) {
                    numUsesInExpr++;
                  }
                });
                morphNode(node, ['block', []]);
                j = j - numUsesInExpr;
                removeUnusedNodes(j, 1 + numUsesInExpr);
              }
            }
          }
        }
        block.use = use;
        block.kill = kill;
        block.link = link;
        block.lastUseLoc = lastUseLoc;
        block.firstDeadLoc = firstDeadLoc;
        block.firstKillLoc = firstKillLoc;
        block.lastKillLoc = lastKillLoc;
      }
  
      var jWorklistMap = { EXIT_JUNCTION: 1 };
      var jWorklist = [EXIT_JUNCTION];
      var bWorklistMap = {};
      var bWorklist = [];
  
      // Be sure to visit every junction at least once.
      // This avoids missing some vars because we disconnected them
      // when processing the labelled jumps.
      for (var i = junctions.length - 1; i >= EXIT_JUNCTION; i--) {
        jWorklistMap[i] = 1;
        jWorklist.push(i);
      }
  
      while (jWorklist.length > 0) {
        // Iterate on just the junctions until we get stable live sets.
        // The first run of this loop will grow the live sets to their maximal size.
        // Subsequent runs will shrink them based on eliminated in-block uses.
        while (jWorklist.length > 0) {
          var junc = junctions[jWorklist.pop()];
          delete jWorklistMap[junc.id];
          var oldLive = junc.live || null;
          analyzeJunction(junc);
          if (!sortedJsonCompare(oldLive, junc.live)) {
            // Live set changed, updated predecessor blocks and junctions.
            for (var b in junc.inblocks) {
              if (!(b in bWorklistMap)) {
                bWorklistMap[b] = 1;
                bWorklist.push(b);
              }
              var jPred = blocks[b].entry;
              if (!(jPred in jWorklistMap)) {
                jWorklistMap[jPred] = 1;
                jWorklist.push(jPred);
              }
            }
          }
        }
        // Now update the blocks based on the calculated live sets.
        while (bWorklist.length > 0) {
          var block = blocks[bWorklist.pop()];
          delete bWorklistMap[block.id];
          var oldUse = block.use;
          analyzeBlock(block);
          if (!sortedJsonCompare(oldUse, block.use)) {
            // The use set changed, re-process the entry junction.
            if (!(block.entry in jWorklistMap)) {
              jWorklistMap[block.entry] = 1;
              jWorklist.push(block.entry);
            }
          }
        }
      }
  
      // Insist that all function parameters are alive at function entry.
      // This ensures they will be assigned independent registers, even
      // if they happen to be unused.
  
      for (var name in asmData.params) {
        junctions[ENTRY_JUNCTION].live[name] = 1;
      }
  
      // For variables that are live at one or more junctions, we assign them
      // a consistent register for the entire scope of the function.  Find pairs
      // of variable that cannot use the same register (the "conflicts") as well
      // as pairs of variables that we'd like to have share the same register
      // (the "links").
  
      var junctionVariables = {};
  
      function initializeJunctionVariable(name) {
        junctionVariables[name] = { conf: {}, link: {}, excl: {}, reg: null };
      }
  
      for (var i = 0; i < junctions.length; i++) {
        var junc = junctions[i];
        for (var name in junc.live) {
          if (!junctionVariables[name]) initializeJunctionVariable(name);
          // It conflicts with all other names live at this junction.
          for (var otherName in junc.live) {
            if (otherName == name) continue;
            junctionVariables[name].conf[otherName] = 1;
          }
          for (var b in junc.outblocks) {
            // It conflicts with any output vars of successor blocks,
            // if they're assigned before it goes dead in that block.
            var block = blocks[b];
            var jSucc = junctions[block.exit];
            for (var otherName in jSucc.live) {
              if (junc.live[otherName]) continue;
              if (block.lastKillLoc[otherName] < block.firstDeadLoc[name]) {
                if (!junctionVariables[otherName]) initializeJunctionVariable(otherName);
                junctionVariables[name].conf[otherName] = 1;
                junctionVariables[otherName].conf[name] = 1;
              }
            }
            // It links with any linkages in the outgoing blocks.
            var linkName = block.link[name];
            if (linkName && linkName !== name) {
              if (!junctionVariables[linkName]) initializeJunctionVariable(linkName);
              junctionVariables[name].link[linkName] = 1;
              junctionVariables[linkName].link[name] = 1;
            }
          }
        }
      }
  
      // Attempt to sort the junction variables to heuristically reduce conflicts.
      // Simple starting point: handle the most-conflicted variables first.
      // This seems to work pretty well.
  
      var sortedJunctionVariables = keys(junctionVariables);
      sortedJunctionVariables.sort(function(name1, name2) {
        var jv1 = junctionVariables[name1];
        var jv2 = junctionVariables[name2];
        if (jv1.numConfs === undefined) {
          jv1.numConfs = setSize(jv1.conf);
        }
        if (jv2.numConfs === undefined) {
          jv2.numConfs = setSize(jv2.conf);
        }
        return jv2.numConfs - jv1.numConfs;
      });
  
      // We can now assign a register to each junction variable.
      // Process them in order, trying available registers until we find
      // one that works, and propagating the choice to linked/conflicted
      // variables as we go.
  
      function tryAssignRegister(name, reg) {
        // Try to assign the given register to the given variable,
        // and propagate that choice throughout the graph.
        // Returns true if successful, false if there was a conflict.
        var jv = junctionVariables[name];
        if (jv.reg !== null) {
          return jv.reg === reg;
        }
        if (jv.excl[reg]) {
          return false;
        }
        jv.reg = reg;
        // Exclude use of this register at all conflicting variables.
        for (var confName in jv.conf) {
          junctionVariables[confName].excl[reg] = 1;
        }
        // Try to propagate it into linked variables.
        // It's not an error if we can't.
        for (var linkName in jv.link) {
          tryAssignRegister(linkName, reg);
        }
        return true;
      }
  
      NEXTVARIABLE:
      for (var i = 0; i < sortedJunctionVariables.length; i++) {
        var name = sortedJunctionVariables[i];
        // It may already be assigned due to linked-variable propagation.
        if (junctionVariables[name].reg !== null) {
          continue NEXTVARIABLE;
        }
        // Try to use existing registers first.
        var allRegs = allRegsByType[localVars[name]];
        for (var reg in allRegs) {
          if (tryAssignRegister(name, reg)) {
            continue NEXTVARIABLE;
          }
        }
        // They're all taken, create a new one.
        tryAssignRegister(name, createReg(name));
      }
  
      // Each basic block can now be processed in turn.
      // There may be internal-use-only variables that still need a register
      // assigned, but they can be treated just for this block.  We know
      // that all inter-block variables are in a good state thanks to
      // junction variable consistency.
  
      for (var i = 0; i < blocks.length; i++) {
        var block = blocks[i];
        if (block.nodes.length === 0) continue;
        var jEnter = junctions[block.entry];
        var jExit = junctions[block.exit];
        // Mark the point at which each input reg becomes dead.
        // Variables alive before this point must not be assigned
        // to that register.
        var inputVars = {};
        var inputDeadLoc = {};
        var inputVarsByReg = {};
        for (var name in jExit.live) {
          if (!(name in block.kill)) {
            inputVars[name] = 1;
            var reg = junctionVariables[name].reg;
            assert(reg !== null, 'input variable doesnt have a register');
            inputDeadLoc[reg] = block.firstDeadLoc[name];
            inputVarsByReg[reg] = name;
          }
        }
        for (var name in block.use) {
          if (!(name in inputVars)) {
            inputVars[name] = 1;
            var reg = junctionVariables[name].reg;
            assert(reg !== null, 'input variable doesnt have a register');
            inputDeadLoc[reg] = block.firstDeadLoc[name];
            inputVarsByReg[reg] = name;
          }
        }
        assert(setSize(setSub(inputVars, jEnter.live)) == 0);
        // Scan through backwards, allocating registers on demand.
        // Be careful to avoid conflicts with the input registers.
        // We consume free registers in last-used order, which helps to
        // eliminate "x=y" assignments that are the last use of "y".
        var assignedRegs = {};
        var freeRegsByType = copy(allRegsByType);
        // Begin with all live vars assigned per the exit junction.
        for (var name in jExit.live) {
          var reg = junctionVariables[name].reg;
          assert(reg !== null, 'output variable doesnt have a register');
          assignedRegs[name] = reg;
          delete freeRegsByType[localVars[name]][reg];
        }
        for (var j = 0; j < freeRegsByType.length; j++) {
          freeRegsByType[j] = keys(freeRegsByType[j]);
        }
        // Scan through the nodes in sequence, modifying each node in-place
        // and grabbing/freeing registers as needed.
        var maybeRemoveNodes = [];
        for (var j = block.nodes.length - 1; j >= 0; j--) {
          var node = block.nodes[j];
          var name = node[0] === 'assign' ? node[2][1] : node[1];
          var allRegs = allRegsByType[localVars[name]];
          var freeRegs = freeRegsByType[localVars[name]];
          var reg = assignedRegs[name];
          if (node[0] === 'name') {
            // A use.  Grab a register if it doesn't have one.
            if (!reg) {
              if (name in inputVars && j <= block.firstDeadLoc[name]) {
                // Assignment to an input variable, must use pre-assigned reg.
                reg = junctionVariables[name].reg;
                assignedRegs[name] = reg;
                for (var k = freeRegs.length - 1; k >= 0; k--) {
                  if (freeRegs[k] === reg) {
                    freeRegs.splice(k, 1);
                    break;
                  }
                }
              } else {
                // Try to use one of the existing free registers.
                // It must not conflict with an input register.
                for (var k = freeRegs.length - 1; k >= 0; k--) {
                  reg = freeRegs[k];
                  // Check for conflict with input registers.
                  if (block.firstKillLoc[name] <= inputDeadLoc[reg]) {
                    if (name !== inputVarsByReg[reg]) {
                      continue;
                    }
                  }
                  // Found one!
                  assignedRegs[name] = reg;
                  freeRegs.splice(k, 1);
                  break;
                }
                // If we didn't find a suitable register, create a new one.
                if (!assignedRegs[name]) {
                  reg = createReg(name);
                  assignedRegs[name] = reg;
                }
              }
            }
            node[1] = allRegs[reg];
          } else {
            // A kill. This frees the assigned register.
            assert(reg, 'live variable doesnt have a reg?')
            node[2][1] = allRegs[reg];
            freeRegs.push(reg);
            delete assignedRegs[name];
            if (node[3][0] === 'name' && node[3][1] in localVars) {
              maybeRemoveNodes.push([j, node]);
            }
          }
        }
        // If we managed to create any "x=x" assignments, remove them.
        for (var j = 0; j < maybeRemoveNodes.length; j++) {
          var node = maybeRemoveNodes[j][1];
          if (node[2][1] === node[3][1]) {
            if (block.isexpr[maybeRemoveNodes[j][0]]) {
              morphNode(node, node[2]);
            } else {
              morphNode(node, ['block', []]);
            }
          }
        }
      }
  
      // Assign registers to function params based on entry junction
  
      var paramRegs = {};
      if (fun[2]) {
        for (var i = 0; i < fun[2].length; i++) {
          var allRegs = allRegsByType[localVars[fun[2][i]]];
          fun[2][i] = allRegs[junctionVariables[fun[2][i]].reg];
          paramRegs[fun[2][i]] = 1;
        }
      }
  
      // That's it!
      // Re-construct the function with appropriate variable definitions.
  
      var finalAsmData = {
        params: {},
        vars: {},
        inlines: asmData.inlines,
        ret: asmData.ret,
      };
      for (var i = 1; i < nextReg; i++) {
        var reg;
        for (var type=0; type<allRegsByType.length; type++) {
          reg = allRegsByType[type][i];
          if (reg) break;
        }
        if (!paramRegs[reg]) {
          finalAsmData.vars[reg] = type;
        } else {
          finalAsmData.params[reg] = type;
        }
      }
      denormalizeAsm(fun, finalAsmData);
  
      vacuum(fun);
  
    });
  }
  
  
  // Eliminator aka Expressionizer
  //
  // The goal of this pass is to eliminate unneeded variables (which represent one of the infinite registers in the LLVM
  // model) and thus to generate complex expressions where possible, for example
  //
  //  var x = a(10);
  //  var y = HEAP[20];
  //  print(x+y);
  //
  // can be transformed into
  //
  //  print(a(10)+HEAP[20]);
  //
  // The basic principle is to scan along the code in the order of parsing/execution, and keep a list of tracked
  // variables that are current contenders for elimination. We must untrack when we see something that we cannot
  // cross, for example, a write to memory means we must invalidate variables that depend on reading from
  // memory, since if we change the order then we do not preserve the computation.
  //
  // We rely on some assumptions about emscripten-generated code here, which means we can do a lot more than
  // a general JS optimization can. For example, we assume that 'sub' nodes (indexing like HEAP[..]) are
  // memory accesses or FUNCTION_TABLE accesses, and in both cases that the symbol cannot be replaced although
  // the contents can. So we assume FUNCTION_TABLE might have its contents changed but not be pointed to
  // a different object, which allows
  //
  //  var x = f();
  //  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', 'label', 'switch', 'binary', 'unary-prefix'); // do is checked carefully, however
  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', '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)
  var HEAP_NAMES = set('HEAP8', 'HEAP16', 'HEAP32', 'HEAPU8', 'HEAPU16', 'HEAPU32', 'HEAPF32', 'HEAPF64');
  
  function isTempDoublePtrAccess(node) { // these are used in bitcasts; they are not really affecting memory, and should cause no invalidation
    assert(node[0] === 'sub');
    return (node[2][0] === 'name' && node[2][1] === 'tempDoublePtr') ||
           (node[2][0] === 'binary' && ((node[2][2][0] === 'name' && node[2][2][1] === 'tempDoublePtr') ||
                                       (node[2][3][0] === 'name' && node[2][3][1] === 'tempDoublePtr')));
  }
  
  function eliminate(ast, memSafe) {
    // Find variables that have a single use, and if they can be eliminated, do so
    traverseGeneratedFunctions(ast, function(func, type) {
      if (asm) var asmData = normalizeAsm(func);
      //printErr('eliminate in ' + func[1]);
  
      // First, find the potentially eliminatable functions: that have one definition and one use
      var definitions = {};
      var uses = {};
      var namings = {};
      var values = {};
      var locals = {};
      var varsToRemove = {}; // variables being removed, that we can eliminate all 'var x;' of (this refers to 'var' nodes we should remove)
                             // 1 means we should remove it, 2 means we successfully removed it
      var varsToTryToRemove = {}; // variables that have 0 uses, but have side effects - when we scan we can try to remove them
      // add arguments as locals
      if (func[2]) {
        for (var i = 0; i < func[2].length; i++) {
          locals[func[2][i]] = true;
        }
      }
      // examine body and note locals
      var hasSwitch = false;
      traverse(func, function(node, type) {
        if (type === 'var') {
          var node1 = node[1];
          for (var i = 0; i < node1.length; i++) {
            var node1i = node1[i];
            var name = node1i[0];
            var value = node1i[1];
            if (value) {
              if (!(name in definitions)) definitions[name] = 0;
              definitions[name]++;
              if (!values[name]) values[name] = value;
            }
            if (!uses[name]) uses[name] = 0;
            locals[name] = true;
          }
        } else if (type === 'name') {
          var name = node[1];
          if (!uses[name]) uses[name] = 0;
          uses[name]++;
        } else if (type === 'assign') {
          var target = node[2];
          if (target[0] === 'name') {
            var name = target[1];
            if (!(name in definitions)) definitions[name] = 0;
            definitions[name]++;
            if (!uses[name]) uses[name] = 0;
            if (!values[name]) values[name] = node[3];
            if (node[1] === true) { // not +=, -= etc., just =
              uses[name]--; // because the name node will show up by itself in the previous case
              if (!namings[name]) namings[name] = 0;
              namings[name]++; // offset it here, this tracks the total times we are named
            }
          }
        } else if (type === 'switch') {
          hasSwitch = true;
        }
      });
  
      for (var used in uses) {
        namings[used] = (namings[used] || 0) + uses[used];
      }
  
      // we cannot eliminate variables if there is a switch
      if (hasSwitch && !asm) return;
  
      var potentials = {}; // local variables with 1 definition and 1 use
      var sideEffectFree = {}; // whether a local variable has no side effects in its definition. Only relevant when there are no uses
  
      function unprocessVariable(name) {
        if (name in potentials) delete potentials[name];
        if (name in varsToRemove) delete varsToRemove[name];
        if (name in sideEffectFree) delete sideEffectFree[name];
        if (name in varsToTryToRemove) delete varsToTryToRemove[name];
      }
      function processVariable(name) {
        if (definitions[name] === 1 && uses[name] === 1) {
          potentials[name] = 1;
        } else if (uses[name] === 0 && (!definitions[name] || definitions[name] <= 1)) { // no uses, no def or 1 def (cannot operate on phis, and the llvm optimizer will remove unneeded phis anyhow) (no definition means it is a function parameter, or a local with just |var x;| but no defining assignment)
          var sideEffects = false;
          var value = values[name];
          if (value) {
            // TODO: merge with other side effect code
            // First, pattern-match
            //  (HEAP32[((tempDoublePtr)>>2)]=((HEAP32[(($_sroa_0_0__idx1)>>2)])|0),HEAP32[(((tempDoublePtr)+(4))>>2)]=((HEAP32[((($_sroa_0_0__idx1)+(4))>>2)])|0),(+(HEAPF64[(tempDoublePtr)>>3])))
            // which has no side effects and is the special form of converting double to i64.
            if (!(value[0] === 'seq' && value[1][0] === 'assign' && value[1][2][0] === 'sub' && value[1][2][2][0] === 'binary' && value[1][2][2][1] === '>>' &&
                  value[1][2][2][2][0] === 'name' && value[1][2][2][2][1] === 'tempDoublePtr')) {
              // If not that, then traverse and scan normally.
              sideEffects = hasSideEffects(value);
            }
          }
          if (!sideEffects) {
            varsToRemove[name] = !definitions[name] ? 2 : 1; // remove it normally
            sideEffectFree[name] = true;
            // Each time we remove a variable with 0 uses, if its value has no
            // side effects and vanishes too, then we can remove a use from variables
            // appearing in it, and possibly eliminate again
            if (value) {
              traverse(value, function(node, type) {
                if (type === 'name') {
                  var name = node[1];
                  node[1] = ''; // we can remove this - it will never be shown, and should not be left to confuse us as we traverse
                  if (name in locals) {
                    uses[name]--; // cannot be infinite recursion since we descend an energy function
                    assert(uses[name] >= 0);
                    unprocessVariable(name);
                    processVariable(name);
                  }
                }
              });
            }
          } else {
            varsToTryToRemove[name] = 1; // try to remove it later during scanning
          }
        }
      }
      for (var name in locals) {
        processVariable(name);
      }
  
      //printErr('defs: ' + JSON.stringify(definitions));
      //printErr('uses: ' + JSON.stringify(uses));
      //printErr('values: ' + JSON.stringify(values));
      //printErr('locals: ' + JSON.stringify(locals));
      //printErr('varsToRemove: ' + JSON.stringify(varsToRemove));
      //printErr('varsToTryToRemove: ' + JSON.stringify(varsToTryToRemove));
      values = null;
      //printErr('potentials: ' + JSON.stringify(potentials));
      // We can now proceed through the function. In each list of statements, we try to eliminate
      var tracked = {};
      var globalsInvalidated = false; // do not repeat invalidations, until we track something new
      var memoryInvalidated = false;
      var callsInvalidated = false;
      function track(name, value, defNode) { // add a potential that has just been defined to the tracked list, we hope to eliminate it
        var usesGlobals = false, usesMemory = false, deps = {}, doesCall = false, hasDeps = false;
        var ignoreName = false; // one-time ignorings of names, as first op in sub and call
        traverse(value, function(node, type) {
          if (type === 'name') {
            if (!ignoreName) {
              var name = node[1];
              if (!(name in locals)) {
                usesGlobals = true;
              }
              if (!(name in potentials)) { // deps do not matter for potentials - they are defined once, so no complexity
                deps[name] = 1;
                hasDeps = true;
              }
            } else {
              ignoreName = false;
            }
          } else if (type === 'sub') {
            usesMemory = true;
            ignoreName = true;
          } else if (type === 'call') {
            usesGlobals = true;
            usesMemory = true;
            doesCall = true;
            ignoreName = true;
          } else {
            ignoreName = false;
          }
        });
        tracked[name] = {
          usesGlobals: usesGlobals,
          usesMemory: usesMemory,
          defNode: defNode,
          deps: deps,
          hasDeps: hasDeps,
          doesCall: doesCall
        };
        globalsInvalidated = false;
        memoryInvalidated = false;
        callsInvalidated = false;
        //printErr('track ' + [name, JSON.stringify(tracked[name])]);
      }
      var temp = [];
      // TODO: invalidate using a sequence number for each type (if you were tracked before the last invalidation, you are cancelled). remove for.in loops
      function invalidateGlobals() {
        //printErr('invalidate globals');
        temp.length = 0;
        for (var name in tracked) {
          var info = tracked[name];
          if (info.usesGlobals) {
            temp.push(name);
          }
        }
        for (var i = 0; i < temp.length; i++) {
          delete tracked[temp[i]];
        }
      }
      function invalidateMemory() {
        //printErr('invalidate memory');
        temp.length = 0;
        for (var name in tracked) {
          var info = tracked[name];
          if (info.usesMemory) {
            temp.push(name);
          }
        }
        for (var i = 0; i < temp.length; i++) {
          delete tracked[temp[i]];
        }
      }
      function invalidateByDep(dep) {
        //printErr('invalidate by dep ' + dep);
        temp.length = 0;
        for (var name in tracked) {
          var info = tracked[name];
          if (info.deps[dep]) {
            temp.push(name);
          }
        }
        for (var i = 0; i < temp.length; i++) {
          delete tracked[temp[i]];
        }
      }
      function invalidateCalls() {
        //printErr('invalidate calls');
        temp.length = 0;
        for (var name in tracked) {
          var info = tracked[name];
          if (info.doesCall) {
            temp.push(name);
          }
        }
        for (var i = 0; i < temp.length; i++) {
          delete tracked[temp[i]];
        }
      }
  
      // Generate the sequence of execution. This determines what is executed before what, so we know what can be reordered. Using
      // that, performs invalidations and eliminations
      function scan(node) {
        //printErr('scan: ' + JSON.stringify(node).substr(0, 50) + ' : ' + keys(tracked));
        var abort = false;
        var allowTracking = true; // false inside an if; also prevents recursing in an if
        //var nesting = 1; // printErr-related
        function traverseInOrder(node, ignoreSub, ignoreName) {
          if (abort) return;
          //nesting++; // printErr-related
          //printErr(JSON.stringify(node).substr(0, 50) + ' : ' + keys(tracked) + ' : ' + [allowTracking, ignoreSub, ignoreName]);
          var type = node[0];
          if (type === 'assign') {
            var target = node[2];
            var value = node[3];
            var nameTarget = target[0] === 'name';
            traverseInOrder(target, true, nameTarget); // evaluate left
            traverseInOrder(value); // evaluate right
            // do the actual assignment
            if (nameTarget) {
              var name = target[1];
              if (!(name in potentials)) {
                if (!(name in varsToTryToRemove)) {
                  // expensive check for invalidating specific tracked vars. This list is generally quite short though, because of
                  // how we just eliminate in short spans and abort when control flow happens TODO: history numbers instead
                  invalidateByDep(name); // can happen more than once per dep..
                  if (!(name in locals) && !globalsInvalidated) {
                    invalidateGlobals();
                    globalsInvalidated = true;
                  }
                  // if we can track this name (that we assign into), and it has 0 uses and we want to remove its 'var'
                  // definition - then remove it right now, there is no later chance
                  if (allowTracking && (name in varsToRemove) && uses[name] === 0) {
                    track(name, node[3], node);
                    doEliminate(name, node);
                  }
                } else {
                  // replace it in-place
                  node.length = value.length;
                  for (var i = 0; i < value.length; i++) {
                    node[i] = value[i];
                  }
                  varsToRemove[name] = 2;
                }
              } else {
                if (allowTracking) track(name, node[3], node);
              }
            } else if (target[0] === 'sub') {
              if (isTempDoublePtrAccess(target)) {
                if (!globalsInvalidated) {
                  invalidateGlobals();
                  globalsInvalidated = true;
                }
              } else if (!memoryInvalidated) {
                invalidateMemory();
                memoryInvalidated = true;
              }
            }
          } else if (type === 'sub') {
            traverseInOrder(node[1], false, !memSafe); // evaluate inner
            traverseInOrder(node[2]); // evaluate outer
            // ignoreSub means we are a write (happening later), not a read
            if (!ignoreSub && !isTempDoublePtrAccess(node)) {
              // do the memory access
              if (!callsInvalidated) {
                invalidateCalls();
                callsInvalidated = true;
              }
            }
          } else if (type === 'var') {
            var vars = node[1];
            for (var i = 0; i < vars.length; i++) {
              var name = vars[i][0];
              var value = vars[i][1];
              if (value) {
                traverseInOrder(value);
                if (name in potentials && allowTracking) {
                  track(name, value, node);
                } else {
                  invalidateByDep(name);
                }
                if (vars.length === 1 && name in varsToTryToRemove && value) {
                  // replace it in-place
                  value = ['stat', value];
                  node.length = value.length;
                  for (var i = 0; i < value.length; i++) {
                    node[i] = value[i];
                  }
                  varsToRemove[name] = 2;
                }
              }
            }
          } else if (type === 'binary') {
            var flipped = false;
            if (node[1] in ASSOCIATIVE_BINARIES && !(node[2][0] in NAME_OR_NUM) && node[3][0] in NAME_OR_NUM) { // TODO recurse here?
              // associatives like + and * can be reordered in the simple case of one of the sides being a name, since we assume they are all just numbers
              var temp = node[2];
              node[2] = node[3];
              node[3] = temp;
              flipped = true;
            }
            traverseInOrder(node[2]);
            traverseInOrder(node[3]);
            if (flipped && node[2][0] in NAME_OR_NUM) { // dunno if we optimized, but safe to flip back - and keeps the code closer to the original and more readable
              var temp = node[2];
              node[2] = node[3];
              node[3] = temp;
            }
          } else if (type === 'name') {
            if (!ignoreName) { // ignoreName means we are the name of something like a call or a sub - irrelevant for us
              var name = node[1];
              if (name in tracked) {
                doEliminate(name, node);
              } else if (!(name in locals) && !callsInvalidated && (memSafe || !(name in HEAP_NAMES))) { // ignore HEAP8 etc when not memory safe, these are ok to
                                                                                                         // access, e.g. SIMD_Int32x4_load(HEAP8, ...)
                invalidateCalls();
                callsInvalidated = true;
              }
            }
          } else if (type === 'unary-prefix' || type === 'unary-postfix') {
            traverseInOrder(node[2]);
          } else if (type in IGNORABLE_ELIMINATOR_SCAN_NODES) {
          } else if (type === 'call') {
            traverseInOrder(node[1], false, true);
            var args = node[2];
            for (var i = 0; i < args.length; i++) {
              traverseInOrder(args[i]);
            }
            if (callHasSideEffects(node)) {
              // these two invalidations will also invalidate calls
              if (!globalsInvalidated) {
                invalidateGlobals();
                globalsInvalidated = true;
              }
              if (!memoryInvalidated) {
                invalidateMemory();
                memoryInvalidated = true;
              }
            }
          } else if (type === 'if') {
            if (allowTracking) {
              traverseInOrder(node[1]); // can eliminate into condition, but nowhere else
              if (!callsInvalidated) { // invalidate calls, since we cannot eliminate them into an if that may not execute!
                invalidateCalls();
                callsInvalidated = true;
              }
  
              allowTracking = false;
              traverseInOrder(node[2]); // 2 and 3 could be 'parallel', really..
              if (node[3]) traverseInOrder(node[3]);
              allowTracking = true;
  
            } else {
              tracked = {};
            }
          } else if (type === 'block') {
            var stats = node[1];
            if (stats) {
              for (var i = 0; i < stats.length; i++) {
                traverseInOrder(stats[i]);
              }
            }
          } else if (type === 'stat') {
            traverseInOrder(node[1]);
          } else if (type === 'label') {
            traverseInOrder(node[2]);
          } else if (type === 'seq') {
            traverseInOrder(node[1]);
            traverseInOrder(node[2]);
          } else if (type === 'do') {
            if (node[1][0] === 'num' && node[1][1] === 0) { // one-time loop
              traverseInOrder(node[2]);
            } else {
              tracked = {};
            }
          } else if (type === 'return') {
            if (node[1]) traverseInOrder(node[1]);
          } else if (type === 'conditional') {
            if (!callsInvalidated) { // invalidate calls, since we cannot eliminate them into a branch of an LLVM select/JS conditional that does not execute
              invalidateCalls();
              callsInvalidated = true;
            }
            traverseInOrder(node[1]);
            traverseInOrder(node[2]);
            traverseInOrder(node[3]);
          } else if (type === 'switch') {
            traverseInOrder(node[1]);
            var originalTracked = {};
            for (var o in tracked) originalTracked[o] = 1;
            var cases = node[2];
            for (var i = 0; i < cases.length; i++) {
              var c = cases[i];
              assert(c[0] === null || c[0][0] === 'num' || (c[0][0] === 'unary-prefix' && c[0][2][0] === 'num'));
              var stats = c[1];
              for (var j = 0; j < stats.length; j++) {
                traverseInOrder(stats[j]);
              }
              // We cannot track from one switch case into another if there are external dependencies, undo all new trackings
              // Otherwise we can track, e.g. a var used in a case before assignment in another case is UB in asm.js, so no need for the assignment
              // TODO: general framework here, use in if-else as well
              for (var t in tracked) {
                if (!(t in originalTracked)) {
                  var info = tracked[t];
                  if (info.usesGlobals || info.usesMemory || info.hasDeps) {
                    delete tracked[t];
                  }
                }
              }
            }
            tracked = {}; // do not track from inside the switch to outside
          } else {
            if (!(type in ABORTING_ELIMINATOR_SCAN_NODES)) {
              printErr('unfamiliar eliminator scan node: ' + JSON.stringify(node));
            }
            tracked = {};
            abort = true;
          }
          //nesting--; // printErr-related
        }
        traverseInOrder(node);
      }
      //var eliminationLimit = 0; // used to debugging purposes
      function doEliminate(name, node) {
        //if (eliminationLimit === 0) return;
        //eliminationLimit--;
        //printErr('elim!!!!! ' + name);
        // yes, eliminate!
        varsToRemove[name] = 2; // both assign and var definitions can have other vars we must clean up
        var info = tracked[name];
        delete tracked[name];
        var defNode = info.defNode;
        var value;
        if (!sideEffectFree[name]) {
          if (defNode[0] === 'var') {
            defNode[1].forEach(function(pair) {
              if (pair[0] === name) {
                value = pair[1];
              }
            });
            assert(value);
          } else { // assign
            value = defNode[3];
            // wipe out the assign
            defNode[0] = 'toplevel';
            defNode[1] = [];
            defNode.length = 2;
          }
          // replace this node in-place
          node.length = 0;
          for (var i = 0; i < value.length; i++) {
            node[i] = value[i];
          }
        } else {
          // This has no side effects and no uses, empty it out in-place
          node.length = 0;
          node[0] = 'toplevel';
          node[1] = [];
        }
      }
      traverse(func, function(block) {
        // Look for statements, including while-switch pattern
        var stats = getStatements(block) || (block[0] === 'while' && block[2][0] === 'switch' ? [block[2]] : stats);
        if (!stats) return;
        //printErr('Stats: ' + JSON.stringify(stats).substr(0,100));
        tracked = {};
        //printErr('new StatBlock');
        for (var i = 0; i < stats.length; i++) {
          var node = stats[i];
          //printErr('StatBlock[' + i + '] => ' + JSON.stringify(node).substr(0,100));
          var type = node[0];
          if (type === 'stat') {
            node = node[1];
            type = node[0];
          } else if (type == 'return' && i < stats.length-1) {
            stats.length = i+1; // remove any code after a return
          }
          // Check for things that affect elimination
          if (type in ELIMINATION_SAFE_NODES) {
            scan(node);
          } else {
            tracked = {}; // not a var or assign, break all potential elimination so far
          }
        }
        //printErr('delete StatBlock');
      });
  
      var seenUses = {}, helperReplacements = {}; // for looper-helper optimization
  
      // clean up vars, and loop variable elimination
      traverse(func, function(node, type) {
        // pre
        if (type === 'var') {
          node[1] = node[1].filter(function(pair) { return !varsToRemove[pair[0]] });
          if (node[1].length === 0) {
            // wipe out an empty |var;|
            node[0] = 'toplevel';
            node[1] = [];
          }
        } else if (type === 'assign' && node[1] === true && node[2][0] === 'name' && node[3][0] === 'name' && node[2][1] === node[3][1]) {
          // elimination led to X = X, which we can just remove
          return emptyNode();
        }
      }, function(node, type) {
        // post
        if (type === 'name') {
          var name = node[1];
          if (name in helperReplacements) {
            node[1] = helperReplacements[name];
            return; // no need to track this anymore, we can't loop-optimize more than once
          }
          // track how many uses we saw. we need to know when a variable is no longer used (hence we run this in the post)
          if (!(name in seenUses)) {
            seenUses[name] = 1;
          } else {
            seenUses[name]++;
          }
        } else if (type === 'while') {
          if (!asm) return;
          // try to remove loop helper variables specifically
          var stats = node[2][1];
          var last = stats[stats.length-1];
          if (last && last[0] === 'if' && last[2][0] === 'block' && last[3] && last[3][0] === 'block') {
            var ifTrue = last[2];
            var ifFalse = last[3];
            clearEmptyNodes(ifTrue[1]);
            clearEmptyNodes(ifFalse[1]);
            var flip = false;
            if (ifFalse[1][0] && ifFalse[1][ifFalse[1].length-1][0] === 'break') { // canonicalize break in the if-true
              var temp = ifFalse;
              ifFalse = ifTrue;
              ifTrue = temp;
              flip = true;
            }
            if (ifTrue[1][0] && ifTrue[1][ifTrue[1].length-1][0] === 'break') {
              var assigns = ifFalse[1];
              clearEmptyNodes(assigns);
              var loopers = [], helpers = [];
              for (var i = 0; i < assigns.length; i++) {
                if (assigns[i][0] === 'stat' && assigns[i][1][0] === 'assign') {
                  var assign = assigns[i][1];
                  if (assign[1] === true && assign[2][0] === 'name' && assign[3][0] === 'name') {
                    var looper = assign[2][1];
                    var helper = assign[3][1];
                    if (definitions[helper] === 1 && seenUses[looper] === namings[looper] &&
                        !helperReplacements[helper] && !helperReplacements[looper]) {
                      loopers.push(looper);
                      helpers.push(helper);
                    }
                  }
                }
              }
              // remove loop vars that are used in the rest of the else
              for (var i = 0; i < assigns.length; i++) {
                if (assigns[i][0] === 'stat' && assigns[i][1][0] === 'assign') {
                  var assign = assigns[i][1];
                  if (!(assign[1] === true && assign[2][0] === 'name' && assign[3][0] === 'name') || loopers.indexOf(assign[2][1]) < 0) {
                    // this is not one of the loop assigns
                    traverse(assign, function(node, type) {
                      if (type === 'name') {
                        var index = loopers.indexOf(node[1]);
                        if (index < 0) index = helpers.indexOf(node[1]);
                        if (index >= 0) {
                          loopers.splice(index, 1);
                          helpers.splice(index, 1);
                        }
                      }
                    });
                  }
                }
              }
              // remove loop vars that are used in the if
              traverse(ifTrue, function(node, type) {
                if (type === 'name') {
                  var index = loopers.indexOf(node[1]);
                  if (index < 0) index = helpers.indexOf(node[1]);
                  if (index >= 0) {
                    loopers.splice(index, 1);
                    helpers.splice(index, 1);
                  }
                }
              });
              if (loopers.length === 0) return;
              for (var l = 0; l < loopers.length; l++) {
                var looper = loopers[l];
                var helper = helpers[l];
                // the remaining issue is whether loopers are used after the assignment to helper and before the last line (where we assign to it)
                var found = -1;
                for (var i = stats.length-2; i >= 0; i--) {
                  var curr = stats[i];
                  if (curr[0] === 'stat' && curr[1][0] === 'assign') {
                    var currAssign = curr[1];
                    if (currAssign[1] === true && currAssign[2][0] === 'name') {
                      var to = currAssign[2][1];
                      if (to === helper) {
                        found = i;
                        break;
                      }
                    }
                  }
                }
                if (found < 0) return;
                // if a loop variable is used after we assigned to the helper, we must save its value and use that.
                // (note that this can happen due to elimination, if we eliminate an expression containing the
                // loop var far down, past the assignment!)
                // first, see if the looper and helpers overlap. Note that we check for this looper, compared to
                // *ALL* the helpers. Helpers will be replaced by loopers as we eliminate them, potentially
                // causing conflicts, so any helper is a concern.
                var firstLooperUsage = -1;
                var lastLooperUsage = -1;
                var firstHelperUsage = -1;
                for (var i = found+1; i < stats.length; i++) {
                  var curr = i < stats.length-1 ? stats[i] : last[1]; // on the last line, just look in the condition
                  traverse(curr, function(node, type) {
                    if (type === 'name') {
                      if (node[1] === looper) {
                        if (firstLooperUsage < 0) firstLooperUsage = i;
                        lastLooperUsage = i;
                      } else if (helpers.indexOf(node[1]) >= 0) {
                        if (firstHelperUsage < 0) firstHelperUsage = i;
                      }
                    }
                  });
                }
                if (firstLooperUsage >= 0) {
                  // the looper is used, we cannot simply merge the two variables
                  if ((firstHelperUsage < 0 || firstHelperUsage > lastLooperUsage) && lastLooperUsage+1 < stats.length && triviallySafeToMove(stats[found], asmData) &&
                      seenUses[helper] === namings[helper]) {
                    // the helper is not used, or it is used after the last use of the looper, so they do not overlap,
                    // and the last looper usage is not on the last line (where we could not append after it), and the
                    // helper is not used outside of the loop.
                    // just move the looper definition to after the looper's last use
                    stats.splice(lastLooperUsage+1, 0, stats[found]);
                    stats.splice(found, 1);
                  } else {
                    // they overlap, we can still proceed with the loop optimization, but we must introduce a
                    // loop temp helper variable
                    var temp = looper + '$looptemp';
                    assert(!(temp in asmData.vars));
                    for (var i = firstLooperUsage; i <= lastLooperUsage; i++) {
                      var curr = i < stats.length-1 ? stats[i] : last[1]; // on the last line, just look in the condition
                      traverse(curr, function looperToLooptemp(node, type) {
                        if (type === 'name') {
                          if (node[1] === looper) {
                            node[1] = temp;
                          }
                        } else if (type === 'assign' && node[2][0] === 'name') {
                          // do not traverse the assignment target, phi assignments to the loop variable must remain
                          traverse(node[3], looperToLooptemp);
                          return null;
                        }
                      });
                    }
                    asmData.vars[temp] = asmData.vars[looper];
                    stats.splice(found, 0, ['stat', ['assign', true, ['name', temp], ['name', looper]]]);
                  }
                }
              }
              for (var l = 0; l < helpers.length; l++) {
                for (var k = 0; k < helpers.length; k++) {
                  if (l != k && helpers[l] === helpers[k]) return; // it is complicated to handle a shared helper, abort
                }
              }
              // hurrah! this is safe to do
              //printErr("ELIM LOOP VAR " + JSON.stringify(loopers) + ' :: ' + JSON.stringify(helpers));
              for (var l = 0; l < loopers.length; l++) {
                var looper = loopers[l];
                var helper = helpers[l];
                varsToRemove[helper] = 2;
                traverse(node, function(node, type) { // replace all appearances of helper with looper
                  if (type === 'name' && node[1] === helper) node[1] = looper;
                });
                helperReplacements[helper] = looper; // replace all future appearances of helper with looper
                helperReplacements[looper] = looper; // avoid any further attempts to optimize looper in this manner (seenUses is wrong anyhow, too)
              }
              // simplify the if. we remove the if branch, leaving only the else
              if (flip) {
                last[1] = simplifyNotCompsDirect(['unary-prefix', '!', last[1]]);
                var temp = last[2];
                last[2] = last[3];
                last[3] = temp;
              }
              if (loopers.length === assigns.length) {
                last.pop();
              } else {
                var elseStats = getStatements(last[3]);
                for (var i = 0; i < elseStats.length; i++) {
                  var stat = elseStats[i];
                  if (stat[0] === 'stat') stat = stat[1];
                  if (stat[0] === 'assign' && stat[2][0] === 'name') {
                    if (loopers.indexOf(stat[2][1]) >= 0) {
                      elseStats[i] = emptyNode();
                    }
                  }
                }
              }
            }
          }
        }
      });
  
      if (asm) {
        for (var v in varsToRemove) {
          if (varsToRemove[v] === 2) delete asmData.vars[v];
        }
        denormalizeAsm(func, asmData);
      }
    });
  
    if (!asm) { // TODO: deprecate in non-asm too
      // A class for optimizing expressions. We know that it is legitimate to collapse
      // 5+7 in the generated code, as it will always be numerical, for example. XXX do we need this? here?
      function ExpressionOptimizer(node) {
        this.node = node;
  
        this.run = function() {
          traverse(this.node, function(node, type) {
            if (type === 'binary' && node[1] === '+') {
              var names = [];
              var num = 0;
              var has_num = false;
              var fail = false;
              traverse(node, function(subNode, subType) {
                if (subType === 'binary') {
                  if (subNode[1] !== '+') {
                    fail = true;
                    return false;
                  }
                } else if (subType === 'name') {
                  names.push(subNode[1]);
                  return;
                } else if (subType === 'num') {
                  num += subNode[1];
                  has_num = true;
                  return;
                } else {
                  fail = true;
                  return false;
                }
              });
              if (!fail && has_num) {
                var ret = ['num', num];
                for (var i = 0; i < names.length; i++) {
                  ret = ['binary', '+', ['name', names[i]], ret];
                }
                return ret;
              }
            }
          });
        };
      }
      new ExpressionOptimizer(ast).run();
    }
  
    removeAllEmptySubNodes(ast);
  }
  
  function eliminateMemSafe(ast) {
    eliminate(ast, true);
  }
  
  function minifyGlobals(ast) {
    var minified = {};
    var next = 0;
    function getMinified(name) {
      if (minified[name]) return minified[name];
      ensureMinifiedNames(next);
      return minified[name] = minifiedNames[next++];
    }
    var first = true; // do not minify initial 'var asm ='
    // find the globals
    traverse(ast, function(node, type) {
      if (type === 'var' || type === 'const') {
        if (first) {
          first = false;
          return;
        }
        var vars = node[1];
        for (var i = 0; i < vars.length; i++) {
          var name = vars[i][0];
          vars[i][0] = getMinified(name);
        }
      } else if (type === 'defun') {
        var name = node[1];
        node[1] = getMinified(name);
      }
    });
    // add all globals in function chunks, i.e. not here but passed to us
    for (var i = 0; i < extraInfo.globals.length; i++) {
      name = extraInfo.globals[i];
      minified[name] = getMinified(name);
    }
    // apply minification
    traverse(ast, function(node, type) {
      if (type === 'name') {
        var name = node[1];
        if (name in minified) {
          node[1] = minified[name];
        }
      }
    });
    suffix = '// EXTRA_INFO:' + JSON.stringify(minified);
  }
  
  
  function minifyLocals(ast) {
    assert(extraInfo && extraInfo.globals);
  
    traverseGeneratedFunctions(ast, function(fun, type) {
      // Find the list of local names, including params.
      if (asm) {
        // TODO: we can avoid modifying at all here - we just need a list of local vars+params
        var asmData = normalizeAsm(fun);
        denormalizeAsm(fun, asmData);
      } else {
        // non-asm.js code - scan the whole function, which is inefficient
        var localNames = {};
        for (var param of fun[2]) {
          localNames[param] = 1;
        }
        traverse(fun, function(node, type) {
          if (type === 'var') {
            node[1].forEach(function(defn) {
              var name = defn[0];
              localNames[name] = 1;
            });
          }
        });
      }
  
      var newNames = {};
      var usedNames = {};
  
      // Find all the globals that we need to minify using
      // pre-assigned names.  Don't actually minify them yet
      // as that might interfere with local variable names.
      function isLocalName(name) {
        if (asm) {
          return name in asmData.vars || name in asmData.params;
        } else {
          return Object.prototype.hasOwnProperty.call(localNames, name);
        }
      }
      traverse(fun, function(node, type) {
        if (type === 'name') {
          var name = node[1];
          if (!isLocalName(name)) {
            var minified = extraInfo.globals[name];
            if (minified){
              newNames[name] = minified;
              usedNames[minified] = 1;
            }
          }
        } else if (type === 'call') {
          // We should never call a local name, as in asm.js-style code our
          // locals are just numbers, not functions; functions are all declared
          // in the outer scope. If a local is called, that is a bug.
          if (node[1][0] === 'name') {
            var name = node[1][1];
            assert(!isLocalName(name), 'cannot call a local');
          }
        }
      });
  
      // The first time we encounter a local name, we assign it a
      // minified name that's not currently in use.  Allocating on
      // demand means they're processed in a predictable order,
      // which is very handy for testing/debugging purposes.
      var nextMinifiedName = 0;
      function getNextMinifiedName() {
        var minified;
        while (1) {
          ensureMinifiedNames(nextMinifiedName);
          minified = minifiedNames[nextMinifiedName++];
          // TODO: we can probably remove !isLocalName here
          if (!usedNames[minified] && !isLocalName(minified)) {
            return minified;
          }
        }
      }
  
      // We can also minify loop labels, using a separate namespace
      // to the variable declarations.
      var newLabels = {};
      var nextMinifiedLabel = 0;
      function getNextMinifiedLabel() {
        ensureMinifiedNames(nextMinifiedLabel);
        return minifiedNames[nextMinifiedLabel++];
      }
  
      // Traverse and minify all names.
      if (fun[1] in extraInfo.globals) {
        fun[1] = extraInfo.globals[fun[1]];
        assert(fun[1]);
      }
      if (fun[2]) {
        for (var i = 0; i < fun[2].length; i++) {
          var minified = getNextMinifiedName();
          newNames[fun[2][i]] = minified;
          fun[2][i] = minified;
        }
      }
      traverse(fun[3], function(node, type) {
        if (type === 'name') {
          var name = node[1];
          var minified = newNames[name];
          if (minified) {
            node[1] = minified;
          } else if (isLocalName(name)) {
            minified = getNextMinifiedName();
            newNames[name] = minified;
            node[1] = minified;
          }
        } else if (type === 'var') {
          node[1].forEach(function(defn) {
            var name = defn[0];
            if (!(name in newNames)) {
              newNames[name] = getNextMinifiedName();
            }
            defn[0] = newNames[name];
          });
        } else if (type === 'label') {
          if (!newLabels[node[1]]) {
            newLabels[node[1]] = getNextMinifiedLabel();
          }
          node[1] = newLabels[node[1]];
        } else if (type === 'break' || type === 'continue') {
          if (node[1]) {
            node[1] = newLabels[node[1]];
          }
        }
      });
  
    });
  }
  
  // Relocation pass for a shared module (for the functions part of the module)
  //
  // 1. Replace function names with alternate names as defined (to avoid colliding with
  // names in the main module we are being linked to)
  // 2. Hardcode function table offsets from F_BASE+x to const+x if x is a variable, or
  //    the constant sum of the base + offset
  // 3. Hardcode heap offsets from H_BASE as well
  function relocate(ast) {
    assert(asm); // we also assume we are normalized
  
    var replacements = extraInfo.replacements;
    var fBases = extraInfo.fBases;
    var hBase = extraInfo.hBase;
    var m;
  
    traverse(ast, function(node, type) {
      switch(type) {
        case 'name': case 'defun': {
          var rep = replacements[node[1]];
          if (rep) node[1] = rep;
          break;
        }
        case 'binary': {
          if (node[1] == '+' && node[2][0] == 'name') {
            var base = null;
            if (node[2][1] == 'H_BASE') {
              base = hBase;
            } else if (m = /^F_BASE_(\w+)$/.exec(node[2][1])) {
              base = fBases[m[1]] || 0; // 0 if the parent has no function table for this, but the child does. so no relocation needed
            }
            if (base !== null) {
              var other = node[3];
              if (base === 0) return other;
              if (other[0] == 'num') {
                other[1] = (other[1] + base)|0;
                return other;
              } else {
                node[2] = ['num', base];
              }
            }
          }
          break;
        }
        case 'var': {
          var vars = node[1];
          for (var i = 0; i < vars.length; i++) {
            var name = vars[i][0];
            assert(!(name in replacements)); // cannot shadow functions we are replacing TODO: fix that
          }
          break;
        }
      }
    });
  }
  
  // Break up very large functions
  
  var NODES_WITHOUT_ELIMINATION_SENSITIVITY = set('name', 'num', 'binary', 'unary-prefix');
  var FAST_ELIMINATION_BINARIES = setUnion(setUnion(USEFUL_BINARY_OPS, COMPARE_OPS), set('+'));
  
  function measureSize(ast) {
    var size = 0;
    traverse(ast, function(node, type) {
      // FIXME backwards compatibility: measure var internal node too.
      if (type === 'var') {
        size += node[1].length;
      }
      size++;
    });
    return size;
  }
  
  function measureCost(ast) {
    var size = 0;
    traverse(ast, function(node, type) {
      if (type === 'num' || type === 'unary-prefix') size--;
      else if (type === 'binary') {
        if (node[3][0] === 'num' && node[3][1] === 0) size--;
        else if (node[1] === '/' || node[1] === '%') size += 2;
      }
      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
    // we use it when outlining.
    // Specifically, this finds 'trivial' variables: ones with 1 definition, and that definition is not sensitive to any changes: it
    // only depends on constants and local variables that are themselves trivial. We can unquestionably eliminate
    // such variables in a trivial manner.
  
    var assignments = {};
    var appearances = {};
    var defs = {};
    var considered = {};
  
    traverse(func, function(node, type) {
      if (type == 'assign' && node[2][0] == 'name') {
        var name = node[2][1];
        if (name in asmData.vars) {
          assignments[name] = (assignments[name] || 0) + 1;
          appearances[name] = (appearances[name] || 0) - 1; // this appearance is a definition, offset the counting later
          defs[name] = node;
        } else {
          if (name in asmData.params) {
            assignments[name] = (assignments[name] || 1) + 1; // init to 1 for initial parameter assignment
            considered[name] = true; // this parameter is not ssa, it must be in a hand-optimized function, so it is not trivial
          }
        }
      } else if (type == 'name') {
        var name = node[1];
        if (name in asmData.vars) {
          appearances[name] = (appearances[name] || 0) + 1;
        }
      }
    });
  
    var allTrivials = {}; // key of a trivial var => size of its (expanded) value, at least 1
  
    // three levels of variables:
    // 1. trivial: 1 def (or less), uses nothing sensitive, can be eliminated
    // 2. safe: 1 def (or less), can be used in a trivial, but cannot itself be eliminated
    // 3. sensitive: uses a global or memory or something else that prevents trivial elimination.
  
    function assessTriviality(name) {
      // only care about vars with 0-1 assignments of (0 for parameters), and can ignore label (which is not explicitly initialized, but cannot be eliminated ever anyhow)
      if (assignments[name] > 1 || (!(name in asmData.vars) && !(name in asmData.params)) || name == 'label') return false;
      if (considered[name]) return allTrivials[name];
      considered[name] = true;
      var sensitive = false;
      var size = 0, originalSize = 0;
      var def = defs[name];
      if (def) {
        var value = def[3];
        originalSize = measureSize(value);
        if (value) {
          traverse(value, function recurseValue(node, type) {
            var one = node[1];
            if (!(type in NODES_WITHOUT_ELIMINATION_SENSITIVITY)) { // || (type == 'binary' && !(one in FAST_ELIMINATION_BINARIES))) {
              sensitive = true;
              return true;
            }
            if (type == 'name' && !assessTriviality(one)) {
              if (assignments[one] > 1 || (!(one in asmData.vars) && !(one in asmData.params))) {
                sensitive = true; // directly using something sensitive
                return true;
              } // otherwise, not trivial, but at least safe.
            }
            // if this is a name, it must be a trivial variable (or a safe one) and we know its size
            size += ((type == 'name') ? allTrivials[one] : 1) || 1;
          });
        }
      }
      if (!sensitive) {
        size = size || 1;
        originalSize = originalSize || 1;
        var factor = ((appearances[name] - 1) || 0) * (size - originalSize); // If no size change or just one appearance, always ok to trivially eliminate. otherwise, tradeoff
        if (factor <= 12) {
          allTrivials[name] = size; // trivial!
          return true;
        }
      }
      return false;
    }
    for (var name in asmData.vars) {
      assessTriviality(name);
    }
    var trivials = {};
  
    for (var name in allTrivials) { // from now on, ignore parameters
      if (name in asmData.vars) trivials[name] = true;
    }
  
    allTrivials = {};
  
    var values = {}, recursives = {};
  
    function evaluate(name) {
      var node = values[name];
      if (node) return node;
      values[name] = null; // prevent infinite recursion
      var def = defs[name];
      if (def) {
        node = def[3];
        if (node[0] == 'name') {
          var name2 = node[1];
          assert(name2 !== name);
          if (name2 in trivials) {
            node = evaluate(name2);
          }
        } else {
          traverse(node, function(node, type) {
            if (type == 'name') {
              var name2 = node[1];
              if (name2 === name) {
                recursives[name] = 1;
                return false;
              }
              if (name2 in trivials) {
                return evaluate(name2);
              }
            }
          });
        }
        values[name] = node;
      }
      // 'def' is non-null only if the variable was explicitly re-assigned after its definition.
      // If it wasn't, the initial value should be used, which is supposed to always be zero.
      else if (name in asmData.vars) {
        values[name] = makeAsmCoercedZero(asmData.vars[name])
      }
      return node;
    }
  
    for (var name in trivials) {
      evaluate(name);
    }
    for (var name in recursives) {
      delete trivials[name];
    }
  
    for (var name in trivials) {
      var def = defs[name];
      if (def) {
        def.length = 0;
        def[0] = 'toplevel';
        def[1] = [];
      }
      delete asmData.vars[name];
    }
  
    // Perform replacements TODO: save list of uses objects before, replace directly, avoid extra traverse
    traverse(func, function(node, type) {
      if (type == 'name') {
        var name = node[1];
        if (name in trivials) {
          var value = values[name];
          if (value) return copy(value); // must copy, or else the same object can be used multiple times
          else return emptyNode();
        }
      }
    });
  
    removeAllEmptySubNodes(func);
  }
  
  function aggressiveVariableElimination(ast) {
    assert(asm, 'need ASM_JS for aggressive variable elimination');
    traverseGeneratedFunctions(ast, function(func, type) {
      var asmData = normalizeAsm(func);
      aggressiveVariableEliminationInternal(func, asmData);
      denormalizeAsm(func, asmData);
    });
  }
  
  function fixPtr(ptr, heap) {
    switch (heap) {
      case 'HEAP8':   case 'HEAPU8': break;
      case 'HEAP16':  case 'HEAPU16': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 1) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 2]]; // was unshifted, convert to absolute address
        }
        break;
      }
      case 'HEAP32':  case 'HEAPU32': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 2) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 4]]; // was unshifted, convert to absolute address
        }
        break;
      }
      case 'HEAPF32': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 2) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 4]]; // was unshifted, convert to absolute address
        }
        break;
      }
      case 'HEAPF64': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 3) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 8]]; // was unshifted, convert to absolute address
        }
        break;
      }
      default: {
        return ptr; // unchanged
      }
    }
    ptr = ['binary', '|', ptr, ['num', 0]];
    return ptr;
  }
  
  function safeHeap(ast) {
    var SAFE_HEAP_FUNCS = set('SAFE_HEAP_LOAD', 'SAFE_HEAP_LOAD_D', 'SAFE_HEAP_STORE', 'SAFE_HEAP_STORE_D', 'SAFE_FT_MASK');
    traverseGeneratedFunctions(ast, function(func) {
      if (func[1] in SAFE_HEAP_FUNCS) return null;
      traverseGenerated(func, function(node, type) {
        var heap, ptr;
        if (type === 'assign') {
          if (node[1] === true && node[2][0] === 'sub') {
            heap = node[2][1][1];
            ptr = fixPtr(node[2][2], heap);
            var value = node[3];
            // SAFE_HEAP_STORE(ptr, value, bytes, isFloat)
            switch (heap) {
              case 'HEAP8':   case 'HEAPU8': {
                return ['call', ['name', 'SAFE_HEAP_STORE'], [ptr, makeAsmCoercion(value, ASM_INT), ['num', 1]]];
              }
              case 'HEAP16':  case 'HEAPU16': {
                return ['call', ['name', 'SAFE_HEAP_STORE'], [ptr, makeAsmCoercion(value, ASM_INT), ['num', 2]]];
              }
              case 'HEAP32':  case 'HEAPU32': {
                return ['call', ['name', 'SAFE_HEAP_STORE'], [ptr, makeAsmCoercion(value, ASM_INT), ['num', 4]]];
              }
              case 'HEAPF32': {
                return ['call', ['name', 'SAFE_HEAP_STORE_D'], [ptr, makeAsmCoercion(value, ASM_DOUBLE), ['num', 4]]];
              }
              case 'HEAPF64': {
                return ['call', ['name', 'SAFE_HEAP_STORE_D'], [ptr, makeAsmCoercion(value, ASM_DOUBLE), ['num', 8]]];
              }
              default: throw 'bad heap ' + heap;
            }
          }
        } else if (type === 'sub') {
          var target = node[1][1];
          if (target[0] === 'H') {
            // heap access
            heap = target;
            ptr = fixPtr(node[2], heap);
            // SAFE_HEAP_LOAD(ptr, bytes, isFloat)
            switch (heap) {
              case 'HEAP8': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 1], ['num', 0]]], ASM_INT);
              }
              case 'HEAPU8': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 1], ['num', 1]]], ASM_INT);
              }
              case 'HEAP16': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 2], ['num', 0]]], ASM_INT);
              }
              case 'HEAPU16': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 2], ['num', 1]]], ASM_INT);
              }
              case 'HEAP32': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', 0]]], ASM_INT);
              }
              case 'HEAPU32': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD'], [ptr, ['num', 4], ['num', 1]]], ASM_INT);
              }
              case 'HEAPF32': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD_D'], [ptr, ['num', 4]]], ASM_DOUBLE);
              }
              case 'HEAPF64': {
                return makeAsmCoercion(['call', ['name', 'SAFE_HEAP_LOAD_D'], [ptr, ['num', 8]]], ASM_DOUBLE);
              }
              default: throw 'bad heap ' + heap;
            }
          } else {
            assert(target[0] == 'F');
            // function table indexing mask
            assert(node[2][0] === 'binary' && node[2][1] === '&');
            node[2][2] = makeAsmCoercion(['call', ['name', 'SAFE_FT_MASK'], [makeAsmCoercion(node[2][2], ASM_INT), makeAsmCoercion(node[2][3], ASM_INT)]], ASM_INT);
          }
        }
      });
    });
  }
  
  function fixPtrSlim(ptr, heap, shell) {
    switch (heap) {
      case 'HEAP8':   case 'HEAPU8': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 0) {
          ptr = ['binary', '|', ptr[2], ['num', 0]]; // smaller
        }
        break;
      }
      case 'HEAP16':  case 'HEAPU16': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 1) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 2]]; // was unshifted, convert to absolute address
        }
        break;
      }
      case 'HEAP32':  case 'HEAPU32': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 2) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 4]]; // was unshifted, convert to absolute address
        }
        break;
      }
      case 'HEAPF32': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 2) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 4]]; // was unshifted, convert to absolute address
        }
        break;
      }
      case 'HEAPF64': {
        if (ptr[0] === 'binary' && ptr[1] === '>>' && ptr[3][0] === 'num' && ptr[3][1] === 3) {
          ptr = ptr[2]; // skip the shift
        } else {
          ptr = ['binary', '*', ptr, ['num', 8]]; // was unshifted, convert to absolute address
        }
        break;
      }
      default: {
        if (!shell) throw 'bad heap ' + heap;
        return ptr; // unchanged
      }
    }
    return ptr;
  }
  
  function splitMemory(ast, shell) {
    traverse(ast, function(node, type) {
      var heap, ptr;
      if (type === 'assign') {
        if (node[2][0] === 'sub' && node[2][1][0] === 'name') {
          heap = node[2][1][1];
          if (parseHeap(heap)) {
            if (node[1] !== true) assert(0, 'bad assign, split memory cannot handle ' + JSON.stringify(node) + '= to a HEAP');
            ptr = fixPtrSlim(node[2][2], heap, shell);
            var value = node[3];
            switch (heap) {
              case 'HEAP8': return ['call', ['name', 'set8'], [ptr, value]];
              case 'HEAP16': return ['call', ['name', 'set16'], [ptr, value]];
              case 'HEAP32': return ['call', ['name', 'set32'], [ptr, value]];
              case 'HEAPU8': return ['call', ['name', 'setU8'], [ptr, value]];
              case 'HEAPU16': return ['call', ['name', 'setU16'], [ptr, value]];
              case 'HEAPU32': return ['call', ['name', 'setU32'], [ptr, value]];
              case 'HEAPF32': return ['call', ['name', 'setF32'], [ptr, value]];
              case 'HEAPF64': return ['call', ['name', 'setF64'], [ptr, value]];
              default: if (!shell) throw 'bad heap ' + heap;
            }
          }
        }
      } else if (type === 'sub') {
        var target = node[1][1];
        if (target[0] === 'H') {
          // heap access
          heap = target;
          ptr = fixPtrSlim(node[2], heap, shell);
          switch (heap) {
            case 'HEAP8': return ['call', ['name', 'get8'], [ptr]];
            case 'HEAP16': return ['call', ['name', 'get16'], [ptr]];
            case 'HEAP32': return ['call', ['name', 'get32'], [ptr]];
            case 'HEAPU8': return ['call', ['name', 'getU8'], [ptr]];
            case 'HEAPU16': return ['call', ['name', 'getU16'], [ptr]];
            case 'HEAPU32': return ['call', ['name', 'getU32'], [ptr]];
            case 'HEAPF32': return ['call', ['name', 'getF32'], [ptr]];
            case 'HEAPF64': return ['call', ['name', 'getF64'], [ptr]];
            default: if (!shell) throw 'bad heap ' + heap;
          }
        }
      }
    });
    var SPLIT_GETS = set('get8', 'get16', 'get32', 'getU8', 'getU16', 'getU32', 'getF32', 'getF64');
    traverse(ast, function(node, type) {
      if (type === 'binary' && node[1] === '|' && node[2][0] === 'call' && node[2][1][0] === 'name' && node[2][1][1] in SPLIT_GETS && node[3][0] === 'num' && node[3][1] === 0) {
        return node[2];
      } else if (type === 'unary-prefix' && node[1] === '+' && node[2][0] === 'call' && node[2][1][0] === 'name' && node[2][1][1] in SPLIT_GETS) {
        return node[2];
      }
    });
  }
  
  function splitMemoryShell(ast) {
    splitMemory(ast, true);
  }
  
  function optimizeFrounds(ast) {
    // collapse fround(fround(..)), which can happen due to elimination
    // also emit f0 instead of fround(0) (except in returns)
    var inReturn = false;
    function fix(node) {
      if (node[0] === 'return') inReturn = true;
      traverseChildren(node, fix);
      if (node[0] === 'return') inReturn = false;
      if (node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'Math_fround') {
        var arg = node[2][0];
        if (arg[0] === 'num') {
          if (!inReturn && arg[1] === 0) return ['name', 'f0'];
        } else if (arg[0] === 'call' && arg[1][0] === 'name' && arg[1][1] === 'Math_fround') {
          return arg;
        }
      }
    }
    traverseChildren(ast, fix);
  }
  
  // Ensures that if label exists, it is assigned an initial value (to not assume the asm declaration has an effect, which we normally do not)
  function ensureLabelSet(ast) {
    assert(asm);
    traverseGeneratedFunctions(ast, function(func) {
      var asmData = normalizeAsm(func);
      if ('label' in asmData.vars) {
        var stats = getStatements(func);
        for (var i = 0; i < stats.length; i++) {
          var node = stats[i];
          if (node[0] === 'stat') node = node[1];
          if (node[0] === 'assign' && node[2][0] === 'name' && node[2][1] === 'label') {
            break; // all good
          }
          if (node[0] === 'label' || (node[0] in CONTROL_FLOW)) {
            // we haven't seen an assign, and we hit control flow. add an assign
            stats.splice(i, 0, ['stat', ['assign', true, ['name', 'label'], ['num', 0]]]);
            break;
          }
        }
      }
      denormalizeAsm(func, asmData);
    });
  }
  
  // finds vars that may not be assigned to. misses out on vars that are assigned to in all branches of an if etc. TODO: optimize
  function findUninitializedVars(func, asmData) {
    var bad = {};
    function definitely(node, uninitialized) {
      if (!node) return;
      if (node[0] === 'assign' && node[2][0] === 'name') {
        var name = node[2][1];
        if (name in uninitialized) {
          delete uninitialized[name]; // this one is now ok
        }
      } else if (node[0] === 'name') {
        var name = node[1];
        if (name in uninitialized) {
          bad[name] = 1;
          delete uninitialized[name]; // this one is now bad, ignore it
        }
      }
      traverseChildrenInExecutionOrder(node, definitely, maybe, uninitialized);
    }
    function maybe(node, uninitialized) {
      uninitialized = copy(uninitialized); // copy it; changes here will not propagate
      traverseChildrenInExecutionOrder(node, definitely, maybe, uninitialized);
    }
    traverseChildrenInExecutionOrder(func, definitely, maybe, copy(asmData.vars));
    return bad;
  }
  
  function trample(x, y) { // x = y, by trampling it
    for (var i = 0; i < y.length; i++) {
      x[i] = y[i];
    }
    x.length = y.length;
  }
  
  function ilog2(x) {
    x = Math.round(x);
    if (x === 1) return 0;
    if (x === 2) return 1;
    if (x === 4) return 2;
    if (x === 8) return 3;
    throw 'ilog2 is not smart enough for ' + x;
  }
  
  // emits which functions are directly reachable, except for some that are
  // ignored
  function findReachable(ast) {
    var IGNORED = set(extraInfo.ignored);
    var reachable = {};
    traverseGeneratedFunctions(ast, function(func) {
      if (func[1] in IGNORED) return;
      traverse(func, function(node, type) {
        if (type === 'call' && node[1][0] === 'name') {
          reachable[node[1][1]] = 1;
        }
      });
    });
    print('// REACHABLE ' + JSON.stringify(keys(reachable)));
  }
  
  // emits call graph information
  function dumpCallGraph(ast) {
    traverseGeneratedFunctions(ast, function(func) {
      var reachable = {};
      traverse(func, function(node, type) {
        if (type === 'call') {
          if (node[1][0] === 'name') {
            reachable[node[1][1]] = 1;
          } else {
            // (FUNCTION_TABLE[..])(..)
            assert(node[1][0] === 'sub')
            assert(node[1][1][0] === 'name');
            reachable[node[1][1][1]] = 1;
          }
        }
      });
      print('// REACHABLE ' + JSON.stringify([func[1], ' => ', keys(reachable)]));
    });
  }
  
  // Last pass utilities
  
  // Change +5 to DOT$ZERO(5). We then textually change 5 to 5.0 (uglify's ast cannot differentiate between 5 and 5.0 directly)
  function prepDotZero(ast) {
    traverse(ast, function(node, type) {
      if (type === 'unary-prefix' && node[1] === '+') {
        if (node[2][0] === 'num' ||
            (node[2][0] === 'unary-prefix' && node[2][1] === '-' && node[2][2][0] === 'num')) {
          return ['call', ['name', 'DOT$ZERO'], [node[2]]];
        }
      }
    });
  }
  function fixDotZero(js) {
    return js.replace(/-DOT\$ZERO\(-/g, '- DOT$ZERO(-') // avoid x - (-y.0) turning into x--y.0 when minified
             .replace(/DOT\$ZERO\(([-+]?(0x)?[0-9a-f]*\.?[0-9]*([eE][-+]?[0-9]+)?)\)/g, function(m, num) {
      if (num.substr(0, 2) === '0x' || num.substr(0, 3) === '-0x') {
        var ret = eval(num).toString();
        if (ret.indexOf('.') < 0) return ret + '.0';
        return ret;
      }
      if (num.indexOf('.') >= 0) return num;
      var e = num.indexOf('e');
      if (e < 0) return num + '.0';
      return num.substr(0, e) + '.0' + num.substr(e);
    });
  }
  
  function asmLastOpts(ast) {
    var statsStack = [];
    traverseGeneratedFunctions(ast, function(fun) {
      traverse(fun, function(node, type) {
        var stats = getStatements(node);
        if (stats) statsStack.push(stats);
        if (type in CONDITION_CHECKERS) {
          node[1] = simplifyCondition(node[1]);
        }
        if (type === 'while' && node[1][0] === 'num' && node[1][1] === 1 && node[2][0] === 'block' && node[2].length == 2) {
          // This is at the end of the pipeline, we can assume all other optimizations are done, and we modify loops
          // into shapes that might confuse other passes
  
          // while (1) { .. if (..) { break } } ==> do { .. } while(..)
          var stats = node[2][1];
          var last = stats[stats.length-1];
          if (last && last[0] === 'if' && !last[3] && last[2][0] === 'block' && last[2][1][0]) {
            var lastStats = last[2][1];
            var lastNum = lastStats.length;
            var lastLast = lastStats[lastNum-1];
            if (!(lastLast[0] === 'break' && !lastLast[1])) return;// if not a simple break, dangerous
            for (var i = 0; i < lastNum; i++) {
              if (lastStats[i][0] !== 'stat' && lastStats[i][0] !== 'break') return; // something dangerous
            }
            // ok, a bunch of statements ending in a break
            var abort = false;
            var stack = 0;
            var breaks = 0;
            traverse(stats, function(node, type) {
              if (type === 'continue') {
                if (stack === 0 || node[1]) { // abort if labeled (we do not analyze labels here yet), or a continue directly on us
                  abort = true;
                  return true;
                }
              } else if (type === 'break') {
                if (stack === 0 || node[1]) { // relevant if labeled (we do not analyze labels here yet), or a break directly on us
                  breaks++;
                }
              } else if (type in LOOP) {
                stack++;
              }
            }, function(node, type) {
              if (type in LOOP) {
                stack--;
              }
            });
            if (abort) return;
            assert(breaks > 0);
            if (lastStats.length > 1 && breaks !== 1) return; // if we have code aside from the break, we can only move it out if there is just one break
            // start to optimize
            if (lastStats.length > 1) {
              var parent = statsStack[statsStack.length-1];
              var me = parent.indexOf(node);
              if (me < 0) return; // not always directly on a stats, could be in a label for example
              parent.splice.apply(parent, [me+1, 0].concat(lastStats.slice(0, lastStats.length-1)));
            }
            var conditionToBreak = last[1];
            stats.pop();
            node[0] = 'do';
            node[1] = simplifyNotCompsDirect(['unary-prefix', '!', conditionToBreak]);
            return node;
          }
        } else if (type === 'binary') {
          if (node[1] === '&') {
            if (node[3][0] === 'unary-prefix' && node[3][1] === '-' && node[3][2][0] === 'num' && node[3][2][1] === 1) {
              // Change &-1 into |0, at this point the hint is no longer needed
              node[1] = '|';
              node[3] = node[3][2];
              node[3][1] = 0;
            }
          } else if (node[1] === '-' && node[3][0] === 'unary-prefix') {
            // avoid X - (-Y) because some minifiers buggily emit X--Y which is invalid as -- can be a unary. Transform to
            //        X + Y
            if (node[3][1] === '-') { // integer
              node[1] = '+';
              node[3] = node[3][2];
            } else if (node[3][1] === '+') { // float
              if (node[3][2][0] === 'unary-prefix' && node[3][2][1] === '-') {
                node[1] = '+';
                node[3][2] = node[3][2][2];
              }
            }
          }
        }
      }, function(node, type) {
        var stats = getStatements(node);
        if (stats) statsStack.pop();
      });
      if (!debug) { // dangerous in debug mode, as without braces things can end up on the same line, together with comments
        // convert  { singleton }  into  singleton
        traverse(fun, function(node, type) {
          if (type === 'block' && node[1] && node[1].length === 1) {
            return node[1][0];
          }
        });
      }
    });
  }
  
  // Contrary to the name this does not eliminate actual dead functions, only
  // those marked as such with DEAD_FUNCTIONS
  function eliminateDeadFuncs(ast) {
    assert(asm);
    assert(extraInfo && extraInfo.dead_functions);
    var deadFunctions = set(extraInfo.dead_functions);
    traverseGeneratedFunctions(ast, function (fun, type) {
      if (!(fun[1] in deadFunctions)) {
        return;
      }
      var asmData = normalizeAsm(fun);
      fun[3] = [['stat', ['call', ['name', 'abort'], [['num', -1]]]]];
      asmData.vars = {};
      denormalizeAsm(fun, asmData);
    });
  }
  
  // Cleans up globals in an asm.js module that are not used. Assumes it
  // receives a full asm.js module, as from the side file in --separate-asm
  function eliminateDeadGlobals(ast) {
    traverse(ast, function(func, type) {
      if (type !== 'function') return;
      // find all symbols used by name that are not locals, so they must be globals
      var stats = func[3];
      var used = {};
      for (var i = 0; i < stats.length; i++) {
        var asmFunc = stats[i];
        if (asmFunc[0] === 'defun') {
          // the memory growth function does not contain valid asm.js, and can be ignored
          var isAsmJS = asmFunc[1] !== '_emscripten_replace_memory';
          if (isAsmJS) {
            var asmData = normalizeAsm(asmFunc);
          }
          traverse(asmFunc, function(node, type) {
            if (type == 'name') {
              var name = node[1];
              if (!isAsmJS || !(name in asmData.params || name in asmData.vars)) {
                used[name] = 1;
              }
            }
          });
          if (isAsmJS) {
            denormalizeAsm(asmFunc, asmData);
          }
        } else {
          traverse(asmFunc, function(node, type) {
            if (type == 'name') {
              var name = node[1];
              used[name] = 1;
            }
          });
        }
      }
      for (var i = 0; i < stats.length; i++) {
        var node = stats[i];
        if (node[0] === 'var') {
          for (var j = 0; j < node[1].length; j++) {
            var v = node[1][j];
            var name = v[0];
            var value = v[1];
            if (!(name in used)) {
              node[1].splice(j, 1);
              j--;
              if (node[1].length == 0) {
                // remove the whole var
                stats[i] = emptyNode();
              }
            }
          }
        } else if (node[0] === 'defun') {
          if (!(node[1] in used)) {
            stats[i] = emptyNode();
          }
        }
      }
      removeEmptySubNodes(func);
    });
  }
  
  function isAsmLibraryArgAssign(node) {
    return node[0] === 'var' && node[1][0] && node[1][0][0] == 'asmLibraryArg';
  }
  
  function asmLibraryArgs(node) {
    return node[1][0][1];
  }
  
  function isAsmUse(node) {
    return node[0] === 'sub' &&
           ((node[1][0] === 'name' && node[1][1] === 'asm') || // asm['X']
            (node[1][0] === 'sub' && node[1][1][0] === 'name' && node[1][1][1] === 'Module' && node[1][2][0] === 'string' && node[1][2][1] === 'asm')) && // Module
           node[2][0] === 'string';
  }
  
  function getAsmUseName(node) {
    return node[2][1];
  }
  
  function isModuleUse(node) {
    return node[0] === 'sub' &&
           node[1][0] === 'name' && node[1][1] === 'Module' && // Module['X']
           node[2][0] === 'string';
  }
  
  function getModuleUseName(node) {
    return node[2][1];
  }
  
  function isModuleAsmUse(node) { // Module["asm"][..string..]
    return node[0] === 'sub' &&
           node[1][0] === 'sub' && node[1][1][0] === 'name' && node[1][1][1] === 'Module' && node[1][2][0] === 'string' && node[1][2][1] === 'asm' &&
           node[2][0] === 'string';
  }
  
  // A static dyncall is dynCall('vii', ..), which is actually static even
  // though we call dynCall() - we see the string signature statically.
  function isStaticDynCall(node) {
    return node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'dynCall' && node[2][0][0] === 'string';
  }
  
  function getStaticDynCallName(node) {
    return 'dynCall_' + node[2][0][1];
  }
  
  // a dynamic dyncall is one in which all we know is *some* dynCall may
  // be called, but not who. This can be either
  //   dynCall(*not a string*, ..)
  // or, to be conservative,
  //   "dynCall_"
  // as that prefix means we may be constructing a dynamic dyncall name
  // (dynCall and embind's requireFunction do this internally).
  function isDynamicDynCall(node) {
    return (node[0] === 'call' && node[1][0] === 'name' && node[1][1] === 'dynCall' && node[2][0][0] !== 'string') ||
           (node[0] === 'string' && node[1] === 'dynCall_');
  }
  
  function removeFuncs(ast) {
    assert(ast[0] === 'toplevel');
    var keep = set(extraInfo.keep);
    ast[1] = ast[1].filter(function(node) {
      assert(node[0] === 'defun');
      return node[1] in keep;
    });
  }
  
  // Passes table
  
  var minifyWhitespace = false, printMetadata = true, asm = false,
      asmPreciseF32 = false, emitJSON = false, last = false,
      emitAst = true;
  
  var passes = {
    // passes
    dumpAst: dumpAst,
    dumpSrc: dumpSrc,
    removeAssignsToUndefined: removeAssignsToUndefined,
    //removeUnneededLabelSettings: removeUnneededLabelSettings,
    simplifyExpressions: simplifyExpressions,
    localCSE: localCSE,
    safeLabelSetting: safeLabelSetting,
    simplifyIfs: simplifyIfs,
    hoistMultiples: hoistMultiples,
    loopOptimizer: loopOptimizer,
    registerize: registerize,
    registerizeHarder: registerizeHarder,
    eliminateDeadFuncs: eliminateDeadFuncs,
    eliminateDeadGlobals: eliminateDeadGlobals,
    eliminate: eliminate,
    eliminateMemSafe: eliminateMemSafe,
    aggressiveVariableElimination: aggressiveVariableElimination,
    minifyGlobals: minifyGlobals,
    minifyLocals: minifyLocals,
    relocate: relocate,
    safeHeap: safeHeap,
    splitMemory: splitMemory,
    splitMemoryShell: splitMemoryShell,
    optimizeFrounds: optimizeFrounds,
    ensureLabelSet: ensureLabelSet,
    findReachable: findReachable,
    dumpCallGraph: dumpCallGraph,
    asmLastOpts: asmLastOpts,
    removeFuncs: removeFuncs,
    noop: function() {},
  
    // flags
    minifyWhitespace: function() { minifyWhitespace = true },
    noPrintMetadata: function() { printMetadata = false },
    asm: function() { asm = true },
    asmPreciseF32: function() { asmPreciseF32 = true },
    emitJSON: function() { emitJSON = true },
    receiveJSON: function() { }, // handled in a special way, before passes are run
    last: function() { last = true },
    noEmitAst: function() { emitAst = false },
  };
  
  // Main
  
  var suffix = '';
  
  arguments_ = arguments_.filter(function (arg) {
    if (!/^--/.test(arg)) return true;
  
    if (arg === '--debug') debug = true;
    else throw new Error('Unrecognized flag: ' + arg);
  });
  
  
  var src = read(arguments_[0]);
  generatedFunctions = src.lastIndexOf(GENERATED_FUNCTIONS_MARKER) >= 0;
  var extraInfoStart = src.lastIndexOf('// EXTRA_INFO:')
  if (extraInfoStart > 0) extraInfo = JSON.parse(src.substr(extraInfoStart + 14));
  //printErr(JSON.stringify(extraInfo));
  
  var ast;
  if (arguments_.indexOf('receiveJSON') < 0) {
    ast = srcToAst(src);
  } else {
    var commentStart = src.indexOf('//');
    if (commentStart >= 0) {
      src = src.substr(0, commentStart); // JSON.parse will error on a trailing comment
    }
    ast = JSON.parse(src);
  }
  //printErr('ast: ' + JSON.stringify(ast));
  
  arguments_.slice(1).forEach(function(arg) {
    passes[arg](ast);
  });
  if (asm && last) {
    prepDotZero(ast);
  }
  
  if (emitAst) {
    if (!emitJSON) {
      var js = astToSrc(ast, minifyWhitespace), old;
      if (asm && last) {
        js = fixDotZero(js);
      }
      // remove unneeded newlines+spaces, and print
      do {
        old = js;
        js = js.replace(/\n *\n/g, '\n');
      } while (js != old);
      print(js);
      print('\n');
      print(suffix);
    } else {
      print(JSON.stringify(ast));
    }
  }
  