← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tools/js-optimizer.js

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-06-11 15:45:24 UTC
  • mfrom: (1.2.1) (2.1.1 experimental)
  • Revision ID: package-import@ubuntu.com-20130611154524-rppb3w6tixlegv4n
Tags: 1.4.7~20130611~a1eb425-1
* New snapshot release
* Upload to unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/js-optimizer.js
403
403
// Various expression simplifications. Pre run before closure (where we still have metadata), Post run after.
404
404
 
405
405
function simplifyExpressionsPre(ast) {
 
406
  // Look for (x&A)<<B>>B and replace it with X&A if possible.
 
407
  function simplifySignExtends(ast) {
 
408
    traverseGenerated(ast, function(node, type) {
 
409
      if (type == 'binary'       && node[1]    == '>>' && node[3][0] == 'num' &&
 
410
          node[2][0] == 'binary' && node[2][1] == '<<' && node[2][3][0] == 'num' && node[3][1] == node[2][3][1]) {
 
411
        var innerNode = node[2][2];
 
412
        var shifts = node[3][1];
 
413
        if (innerNode[0] == 'binary' && innerNode[1] == '&' && innerNode[3][0] == 'num') {
 
414
          var mask = innerNode[3][1];
 
415
          if (mask << shifts >> shifts == mask) {
 
416
            return innerNode;
 
417
          }
 
418
        }
 
419
      }
 
420
    });
 
421
  }
 
422
 
406
423
  // When there is a bunch of math like (((8+5)|0)+12)|0, only the external |0 is needed, one correction is enough.
407
424
  // At each node, ((X|0)+Y)|0 can be transformed into (X+Y): The inner corrections are not needed
408
425
  // TODO: Is the same is true for 0xff, 0xffff?
592
609
    });
593
610
  }
594
611
 
 
612
  simplifySignExtends(ast);
595
613
  simplifyBitops(ast);
596
614
  joinAdditions(ast);
597
615
  // simplifyZeroComp(ast); TODO: investigate performance
1392
1410
          var name = v[0];
1393
1411
          var value = v[1];
1394
1412
          if (!(name in data.vars)) {
1395
 
            data.vars[name] = detectAsmCoercion(value);
 
1413
            if (value[0] != 'name') {
 
1414
              data.vars[name] = detectAsmCoercion(value); // detect by coercion
 
1415
            } else {
 
1416
              var origin = value[1];
 
1417
              data.vars[name] = data.vars[origin] || ASM_INT; // detect by origin variable, or assume int for non-locals
 
1418
            }
1396
1419
          }
1397
1420
        }
1398
1421
        unVarify(node[1], node);
1482
1505
    // Replace all var definitions with assignments; we will add var definitions at the top after we registerize
1483
1506
    // We also mark local variables - i.e., having a var definition
1484
1507
    var localVars = {};
1485
 
    var hasSwitch = false; // we cannot optimize variables if there is a switch
 
1508
    var hasSwitch = false; // we cannot optimize variables if there is a switch, unless in asm mode
1486
1509
    traverse(fun, function(node, type) {
1487
1510
      if (type == 'var') {
1488
1511
        node[1].forEach(function(defined) { localVars[defined[0]] = 1 });
1573
1596
    var varLevels = {};
1574
1597
    var possibles = {};
1575
1598
    var unoptimizables = {};
1576
 
    traverse(fun, function(node, type) {
 
1599
    function purgeLevel() {
 
1600
      // Invalidate all dominating on this level, further users make it unoptimizable
 
1601
      for (var name in levelDominations[level]) {
 
1602
        varLevels[name] = 0;
 
1603
      }
 
1604
      levelDominations[level] = null;
 
1605
      level--;
 
1606
    }
 
1607
    traverse(fun, function possibilifier(node, type) {
1577
1608
      if (type == 'name') {
1578
1609
        var name = node[1];
1579
1610
        if (localVars[name]) {
1594
1625
          }
1595
1626
        }
1596
1627
      } else if (type in CONTROL_FLOW) {
1597
 
        level++;
1598
 
      }
1599
 
    }, function(node, type) {
1600
 
      if (type in CONTROL_FLOW) {
1601
 
        // Invalidate all dominating on this level, further users make it unoptimizable
1602
 
        for (var name in levelDominations[level]) {
1603
 
          varLevels[name] = 0;
 
1628
        // recurse children, in the context of a loop
 
1629
        switch(type) {
 
1630
          case 'while': case 'do': {
 
1631
            traverse(node[1], possibilifier);
 
1632
            level++;
 
1633
            traverse(node[2], possibilifier);
 
1634
            purgeLevel();
 
1635
            break;
 
1636
          }
 
1637
          case 'for': {
 
1638
            traverse(node[1], possibilifier);
 
1639
            for (var i = 2; i <= 4; i++) {
 
1640
              level++;
 
1641
              traverse(node[i], possibilifier);
 
1642
              purgeLevel();
 
1643
            }
 
1644
            break;
 
1645
          }
 
1646
          case 'if': {
 
1647
            traverse(node[1], possibilifier);
 
1648
            level++;
 
1649
            traverse(node[2], possibilifier);
 
1650
            purgeLevel();
 
1651
            if (node[3]) {
 
1652
              level++;
 
1653
              traverse(node[3], possibilifier);
 
1654
              purgeLevel();
 
1655
            }
 
1656
            break;
 
1657
          }
 
1658
          case 'switch': {
 
1659
            traverse(node[1], possibilifier);
 
1660
            var cases = node[2];
 
1661
            for (var i = 0; i < cases.length; i++) {
 
1662
              level++;
 
1663
              traverse(cases[i][1], possibilifier);
 
1664
              purgeLevel();
 
1665
            }
 
1666
            break;
 
1667
          }
 
1668
          default: throw dumpAst(node);
1604
1669
        }
1605
 
        levelDominations[level] = null;
1606
 
        level--;
 
1670
        return null; // prevent recursion into children, which we already did
1607
1671
      }
1608
1672
    });
1609
1673
    var optimizables = {};
1610
 
    if (!hasSwitch) {
 
1674
    if (!hasSwitch || asm) {
1611
1675
      for (var possible in possibles) {
1612
1676
        if (!unoptimizables[possible]) optimizables[possible] = 1;
1613
1677
      }
1614
1678
    }
 
1679
 
 
1680
    //printErr('optimizables: ' + JSON.stringify(optimizables));
 
1681
    //printErr('unoptimizables: ' + JSON.stringify(unoptimizables));
 
1682
 
1615
1683
    // Go through the function's code, assigning 'registers'.
1616
1684
    // The only tricky bit is to keep variables locked on a register through loops,
1617
1685
    // since they can potentially be returned to. Optimizable variables lock onto
1771
1839
// In memSafe mode, we are more careful and assume functions can replace HEAP and FUNCTION_TABLE, which
1772
1840
// can happen in ALLOW_MEMORY_GROWTH mode
1773
1841
 
1774
 
var ELIMINATION_SAFE_NODES = set('var', 'assign', 'call', 'if', 'toplevel', 'do', 'return', 'label'); // do is checked carefully, however
 
1842
var ELIMINATION_SAFE_NODES = set('var', 'assign', 'call', 'if', 'toplevel', 'do', 'return', 'label', 'switch'); // do is checked carefully, however
1775
1843
var NODES_WITHOUT_ELIMINATION_SIDE_EFFECTS = set('name', 'num', 'string', 'binary', 'sub', 'unary-prefix');
1776
1844
var IGNORABLE_ELIMINATOR_SCAN_NODES = set('num', 'toplevel', 'string', 'break', 'continue', 'dot'); // dot can only be STRING_TABLE.*
1777
 
var ABORTING_ELIMINATOR_SCAN_NODES = set('new', 'object', 'function', 'defun', 'switch', 'for', 'while', 'array', 'throw'); // we could handle some of these, TODO, but nontrivial (e.g. for while, the condition is hit multiple times after the body)
 
1845
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)
1778
1846
 
1779
1847
function eliminate(ast, memSafe) {
1780
1848
  // Find variables that have a single use, and if they can be eliminated, do so
1797
1865
      }
1798
1866
    }
1799
1867
    // examine body and note locals
 
1868
    var hasSwitch = false;
1800
1869
    traverse(func, function(node, type) {
1801
1870
      if (type === 'var') {
1802
1871
        var node1 = node[1];
1828
1897
            uses[name]--; // because the name node will show up by itself in the previous case
1829
1898
          }
1830
1899
        }
 
1900
      } else if (type == 'switch') {
 
1901
        hasSwitch = true;
1831
1902
      }
1832
1903
    });
 
1904
 
 
1905
    // we cannot eliminate variables if there is a switch
 
1906
    if (hasSwitch && !asm) return;
 
1907
 
1833
1908
    var potentials = {}; // local variables with 1 definition and 1 use
1834
1909
    var sideEffectFree = {}; // whether a local variable has no side effects in its definition
1835
 
    for (var name in locals) {
 
1910
 
 
1911
    function unprocessVariable(name) {
 
1912
      if (name in potentials) delete potentials[name];
 
1913
      if (name in varsToRemove) delete varsToRemove[name];
 
1914
      if (name in sideEffectFree) delete sideEffectFree[name];
 
1915
      if (name in varsToTryToRemove) delete varsToTryToRemove[name];
 
1916
    }
 
1917
    function processVariable(name) {
1836
1918
      if (definitions[name] == 1 && uses[name] == 1) {
1837
1919
        potentials[name] = 1;
1838
1920
      } 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)
1839
1921
        var hasSideEffects = false;
1840
 
        if (values[name]) {
1841
 
          traverse(values[name], function(node, type) {
1842
 
            if (!(type in NODES_WITHOUT_ELIMINATION_SIDE_EFFECTS)) {
1843
 
              hasSideEffects = true; // cannot remove this unused variable, constructing it has side effects
1844
 
              return true;
1845
 
            }
1846
 
          });
 
1922
        var value = values[name];
 
1923
        if (value) {
 
1924
          // TODO: merge with other side effect code
 
1925
          // First, pattern-match
 
1926
          //  (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])))
 
1927
          // which has no side effects and is the special form of converting double to i64.
 
1928
          if (!(value[0] == 'seq' && value[1][0] == 'assign' && value[1][2][0] == 'sub' && value[1][2][2][0] == 'binary' && value[1][2][2][1] == '>>' &&
 
1929
                value[1][2][2][2][0] == 'name' && value[1][2][2][2][1] == 'tempDoublePtr')) {
 
1930
            // If not that, then traverse and scan normally.
 
1931
            traverse(value, function(node, type) {
 
1932
              if (!(type in NODES_WITHOUT_ELIMINATION_SIDE_EFFECTS)) {
 
1933
                hasSideEffects = true; // cannot remove this unused variable, constructing it has side effects
 
1934
                return true;
 
1935
              }
 
1936
            });
 
1937
          }
1847
1938
        }
1848
1939
        if (!hasSideEffects) {
1849
1940
          varsToRemove[name] = !definitions[name] ? 2 : 1; // remove it normally
1850
1941
          sideEffectFree[name] = true;
 
1942
          // Each time we remove a variable with 0 uses, if its value has no
 
1943
          // side effects and vanishes too, then we can remove a use from variables
 
1944
          // appearing in it, and possibly eliminate again
 
1945
          if (value) {
 
1946
            traverse(value, function(node, type) {
 
1947
              if (type == 'name') {
 
1948
                var name = node[1];
 
1949
                node[1] = ''; // we can remove this - it will never be shown, and should not be left to confuse us as we traverse
 
1950
                if (name in locals) {
 
1951
                  uses[name]--; // cannot be infinite recursion since we descend an energy function
 
1952
                  assert(uses[name] >= 0);
 
1953
                  unprocessVariable(name);
 
1954
                  processVariable(name);
 
1955
                }
 
1956
              }
 
1957
            });
 
1958
          }
1851
1959
        } else {
1852
1960
          varsToTryToRemove[name] = 1; // try to remove it later during scanning
1853
1961
        }
1854
1962
      }
1855
1963
    }
 
1964
    for (var name in locals) {
 
1965
      processVariable(name);
 
1966
    }
 
1967
 
1856
1968
    //printErr('defs: ' + JSON.stringify(definitions));
1857
1969
    //printErr('uses: ' + JSON.stringify(uses));
1858
1970
    //printErr('values: ' + JSON.stringify(values));
2098
2210
              invalidateCalls();
2099
2211
              callsInvalidated = true;
2100
2212
            }
 
2213
 
2101
2214
            allowTracking = false;
2102
2215
            traverseInOrder(node[2]); // 2 and 3 could be 'parallel', really..
2103
2216
            if (node[3]) traverseInOrder(node[3]);
2104
2217
            allowTracking = true;
 
2218
 
2105
2219
          } else {
2106
2220
            tracked = {};
2107
 
            abort = true;
2108
2221
          }
2109
2222
        } else if (type == 'block') {
2110
2223
          var stats = node[1];
2125
2238
            traverseInOrder(node[2]);
2126
2239
          } else {
2127
2240
            tracked = {};
2128
 
            abort = true;
2129
2241
          }
2130
2242
        } else if (type == 'return') {
2131
2243
          if (node[1]) traverseInOrder(node[1]);
2133
2245
          traverseInOrder(node[1]);
2134
2246
          traverseInOrder(node[2]);
2135
2247
          traverseInOrder(node[3]);
 
2248
        } else if (type == 'switch') {
 
2249
          traverseInOrder(node[1]);
 
2250
          var cases = node[2];
 
2251
          for (var i = 0; i < cases.length; i++) {
 
2252
            var c = cases[i];
 
2253
            assert(c[0] === null || c[0][0] == 'num' || (c[0][0] == 'unary-prefix' && c[0][2][0] == 'num'));
 
2254
            var stats = c[1];
 
2255
            for (var j = 0; j < stats.length; j++) {
 
2256
              traverseInOrder(stats[j]);
 
2257
            }
 
2258
          }
2136
2259
        } else {
2137
2260
          if (!(type in ABORTING_ELIMINATOR_SCAN_NODES)) {
2138
2261
            printErr('unfamiliar eliminator scan node: ' + JSON.stringify(node));
2179
2302
      }
2180
2303
    }
2181
2304
    traverse(func, function(block) {
2182
 
      var stats = getStatements(block);
 
2305
      // Look for statements, including while-switch pattern
 
2306
      var stats = getStatements(block) || (block[0] == 'while' && block[2][0] == 'switch' ? [block[2]] : stats);
2183
2307
      if (!stats) return;
 
2308
      //printErr('Stats: ' + JSON.stringify(stats).substr(0,100));
2184
2309
      tracked = {};
2185
2310
      //printErr('new StatBlock');
2186
2311
      for (var i = 0; i < stats.length; i++) {
2187
2312
        var node = stats[i];
2188
 
        //printErr('StatBlock[' + i + '] => ' + JSON.stringify(node));
 
2313
        //printErr('StatBlock[' + i + '] => ' + JSON.stringify(node).substr(0,100));
2189
2314
        var type = node[0];
2190
2315
        if (type == 'stat') {
2191
2316
          node = node[1];
2353
2478
  compress: function() { compress = true },
2354
2479
  noPrintMetadata: function() { printMetadata = false },
2355
2480
  asm: function() { asm = true },
2356
 
  last: function() { last = true }
 
2481
  last: function() { last = true },
 
2482
  closure: function(){} // handled in python
2357
2483
};
2358
2484
 
2359
2485
// Main