initial hacking

1 files changed, 4 insertions, 369 deletions

diff --git a/src/analyzer.js b/src/analyzer.js
index a6a37400..71f795a8 100644
--- a/src/analyzer.js
+++ b/src/analyzer.js
@@ -1490,388 +1490,23 @@ function analyzer(data, sidePass) {
   // ReLooper - reconstruct nice loops, as much as possible
   substrate.addActor('Relooper', {
     processItem: function(item) {
-      var that = this;
       function finish() {
-        that.forwardItem(item, 'LoopOptimizer');
-      }
-
-      // Tools
-
-      function calcLabelBranchingData(labels, labelsDict) {
-        labels.forEach(function(label) {
-          label.outLabels = [];
-          label.inLabels = [];
-          label.hasReturn = false;
-          label.hasBreak = false;
-        });
-        // Find direct branchings
-        labels.forEach(function(label) {
-          var line = label.lines[label.lines.length-1];
-          operateOnLabels(line, function process(item, id) {
-            if (item[id][0] == 'B') { // BREAK, BCONT, BNOPP, BJSET
-              label.hasBreak = true;
-            } else {
-              label.outLabels.push(item[id]);
-              labelsDict[item[id]].inLabels.push(label.ident);
-            }
-          });
-          label.hasReturn |= line.intertype == 'return';
-        });
-        // Find all incoming and all outgoing - recursively
-        labels.forEach(function(label) {
-          label.allInLabels = [];
-          label.allOutLabels = [];
-        });
-
-        // First, find allInLabels. TODO: use typed arrays here to optimize this for memory and speed
-        var more = true, nextModified, modified = set(getLabelIds(labels));
-        while (more) {
-          more = false;
-          nextModified = {};
-          for (var labelId in modified) {
-            var label = labelsDict[labelId];
-            var temp = label.inLabels;
-            label.inLabels.forEach(function(label2Id) {
-              temp = temp.concat(labelsDict[label2Id].allInLabels);
-            });
-            temp = dedup(temp);
-            if (temp.length > label.allInLabels.length) {
-              label.allInLabels = temp;
-              for (var i = 0; i < label.outLabels.length; i++) {
-                nextModified[label.outLabels[i]] = true;
-              }
-              more = true;
-            }
-          }
-          modified = nextModified;
-        }
-
-        // Infer allOutLabels from allInLabels, they are mirror images
-        labels.forEach(function(label) {
-          label.allInLabels.forEach(function(inLabelId) {
-            labelsDict[inLabelId].allOutLabels.push(label.ident);
-          });
-        });
-
-        labels.forEach(function(label) {
-          if (dcheck('relooping')) {
-            dprint('// label: ' + label.ident + ' :out      : ' + JSON.stringify(label.outLabels));
-            dprint('//        ' + label.ident + ' :in       : ' + JSON.stringify(label.inLabels));
-            dprint('//        ' + label.ident + ' :ALL out  : ' + JSON.stringify(label.allOutLabels));
-            dprint('//        ' + label.ident + ' :ALL in   : ' + JSON.stringify(label.allInLabels));
-          }
-
-          // Convert to set, for speed (we mainly do lookups here) and code clarity (x in Xlabels)
-          // Also removes duplicates (which we can get in llvm switches)
-          // TODO do we need all these?
-          label.outLabels = set(label.outLabels);
-          label.inLabels = set(label.inLabels);
-          label.allOutLabels = set(label.allOutLabels);
-          label.allInLabels = set(label.allInLabels);
-        });
-      }
-
-      var idCounter = 0;
-      function makeBlockId(entries) {
-        idCounter++;
-        return '$_$' + idCounter;
+        item.__finalResult__ = true;
+        return [item];
       }
-
-      // There are X main kinds of blocks:
-      //
-      //----------------------------------------------------------------------------------------
-      //
-      //  'emulated': A soup of labels, implemented as a barbaric switch in a loop. Any
-      //              label can get to any label. No block follows this.
-      //
-      //  'reloop': That is a block of the following shape:
-      //
-      //       loopX: while(1) {
-      //         // internal labels, etc. Labels are internal to the current one, if
-      //         // they can return to it.
-      //         //
-      //         // Such labels can either do |continue loopX| to get back to the entry label,
-      //         // or set __label__ and do |break loopX| to get to any of the external entries
-      //         // they need to get to. External labels, of course, are those that cannot
-      //         // get to the entry
-      //       }
-      //       // external labels
-      //
-      //  'multiple': A block that branches into multiple subblocks, each independent,
-      //              finally leading outside into another block afterwards
-      //              For now, we do this in a loop, so we can break out of it easily to get
-      //              to the labels afterwards. TODO: Optimize that out
-      //
       function makeBlock(labels, entries, labelsDict, forceEmulated) {
         if (labels.length == 0) return null;
         dprint('relooping', 'prelooping: ' + entries + ',' + labels.length + ' labels');
         assert(entries && entries[0]); // need at least 1 entry
 
-        var blockId = makeBlockId(entries);
-
         var emulated = {
           type: 'emulated',
-          id: blockId,
+          id: 'B',
           labels: labels,
           entries: entries.slice(0)
         };
-        if (!RELOOP || forceEmulated) return emulated;
-
-        calcLabelBranchingData(labels, labelsDict);
-
-        var s_entries = set(entries);
-        dprint('relooping', 'makeBlock: ' + entries + ',' + labels.length + ' labels');
-
-        var entryLabels = entries.map(function(entry) { return labelsDict[entry] });
-        assert(entryLabels[0]);
-
-        var canReturn = false, mustReturn = true;
-        entryLabels.forEach(function(entryLabel) {
-          var curr = values(entryLabel.inLabels).length > 0;
-          canReturn = canReturn || curr;
-          mustReturn = mustReturn && curr;
-        });
-
-        // Remove unreachables
-        allOutLabels = {};
-        entryLabels.forEach(function(entryLabel) {
-          mergeInto(allOutLabels, entryLabel.allOutLabels);
-        });
-        labels = labels.filter(function(label) { return label.ident in s_entries || label.ident in allOutLabels });
-
-        // === (simple) 'emulated' ===
-
-        if (entries.length == 1 && !canReturn) {
-          var entry = entries[0];
-          var entryLabel = entryLabels[0];
-          var others = labels.filter(function(label) { return label.ident != entry });
-
-          var nextEntries = keys(entryLabel.outLabels);
-          dprint('relooping', '   Creating simple emulated, outlabels: ' + nextEntries);
-          nextEntries.forEach(function(nextEntry) {
-            replaceLabelLabels([entryLabel], set(nextEntry), 'BJSET|' + nextEntry); // Just SET __label__ - no break or continue or whatnot
-          });
-          return {
-            type: 'emulated',
-            id: blockId,
-            labels: [entryLabel],
-            entries: entries,
-            next: makeBlock(others, keys(entryLabel.outLabels), labelsDict)
-          };
-        }
-
-        // === 'reloop' away a loop, if we need to ===
-
-        function makeLoop() {
-          var ret = {
-            type: 'reloop',
-            id: blockId,
-            needBlockId: true,
-            entries: entries,
-            labels: labels
-          };
-
-          // Find internal and external labels
-          var split_ = splitter(labels, function(label) {
-            // External labels are those that are (1) not an entry, and (2) cannot reach an entry. In other words,
-            // the labels inside the loop are the entries and those that can return to the entries.
-            return !(label.ident in s_entries) && values(setIntersect(s_entries, label.allOutLabels)).length == 0;
-          });
-          var externals = split_.splitOut;
-          var internals = split_.leftIn;
-          var externalsLabels = set(getLabelIds(externals));
-
-          if (dcheck('relooping')) dprint('   Creating reloop: Inner: ' + dump(getLabelIds(internals)) + ', Exxer: ' + dump(externalsLabels));
-
-          if (ASSERTIONS) {
-            // Verify that no external can reach an internal
-            var inLabels = set(getLabelIds(internals));
-            externals.forEach(function(external) {
-              if (values(setIntersect(external.outLabels, inLabels)).length > 0) {
-                dprint('relooping', 'Found an external that wants to reach an internal, fallback to emulated?');
-                throw "Spaghetti label flow";
-              }
-            });
-          }
-
-          // We will be in a loop, |continue| gets us back to the entry
-          var pattern = 'BCONT|' + blockId;
-          if (entries.length == 1) {
-            // We are returning to a loop that has one entry, so we don't need to set __label__
-            pattern = 'BCNOL|' + blockId;
-          }
-          entries.forEach(function(entry) {
-            replaceLabelLabels(internals, set(entries), pattern);
-          });
-
-          // Find the entries of the external labels
-          var externalsEntries = {};
-          internals.forEach(function(internal) {
-            mergeInto(externalsEntries, setIntersect(internal.outLabels, externalsLabels));
-          });
-          externalsEntries = keys(externalsEntries);
-
-          // We also want to include additional labels inside the loop. If the loop has just one exit label,
-          // then that is fine - keep the loop small by having the next code outside, and do not set __label__ in
-          // that break. If there is more than one, though, we can avoid __label__ checks in a multiple outside
-          // by hoisting labels into the loop.
-          if (externalsEntries.length > 1) {
-            (function() {
-              // If an external entry would make the loop too big, don't hoist
-              var maxHoist = Infinity; //sum(internals.map(function(internal) { return internal.lines.length }));
-              var avoid = externalsEntries.map(function(l) { return labelsDict[l] });
-              var totalNewEntries = {};
-              for (var i = 0; i < externalsEntries.length; i++) {
-                var exitLabel = labelsDict[externalsEntries[i]];
-                // Check if hoisting this external entry is worthwhile. We first do a dry run, aborting on
-                // loops (which we never hoist, to avoid over-nesting) or on seeing too many labels would be hoisted
-                // (to avoid enlarging loops too much). If the dry run succeeded, it will stop when it reaches
-                // places where we rejoin other external entries.
-                var seen, newEntries;
-                function prepare() {
-                  seen = {};
-                  newEntries = {};
-                }
-                function hoist(label, dryRun) { // returns false if aborting
-                  if (seen[label.ident]) return true;
-                  seen[label.ident] = true;
-                  if (label.ident in label.allInLabels) return false; // loop, abort
-                  if (isReachable(label, avoid, exitLabel)) {
-                    // We rejoined, so this is a new external entry
-                    newEntries[label.ident] = true;
-                    return true;
-                  }
-                  // Hoistable.
-                  if (!dryRun) {
-                    dprint('relooping', 'Hoisting into loop: ' + label.ident);
-                    internals.push(label);
-                    externals = externals.filter(function(l) { return l != label }); // not very efficient at all TODO: optimize
-                  }
-                  for (var outLabelId in label.outLabels) {
-                    var outLabel = labelsDict[outLabelId];
-                    if (!hoist(outLabel, dryRun)) return false;
-                  }
-                  return true;
-                }
-                prepare();
-                if (hoist(exitLabel, true)) {
-                  var seenList = unset(seen);
-                  var num = sum(seenList.map(function(seen) { return labelsDict[seen].lines.length }));
-                  // Only hoist if the sizes make sense
-                  if (seenList.length >= 1 && num <= maxHoist) { // && unset(newEntries).length <= 1) {
-                    prepare();
-                    hoist(exitLabel);
-                    mergeInto(totalNewEntries, newEntries);
-                    externalsEntries.splice(i, 1);
-                    i--;
-                  }
-                }
-              }
-              externalsLabels = set(getLabelIds(externals));
-              externalsEntries = keys(set(externalsEntries.concat(unset(totalNewEntries))));
-              assert(externalsEntries.length > 0 || externals.length == 0);
-            })();
-          }
-
-          // To get to any of our (not our parents') exit labels, we will break.
-          if (dcheck('relooping')) dprint('for exit purposes, Replacing: ' + dump(externalsLabels));
-          if (externals.length > 0) {
-            assert(externalsEntries.length > 0);
-            var pattern = 'BREAK|' + blockId;
-            if (externalsEntries.length == 1) {
-              // We are breaking out of a loop and have one entry after it, so we don't need to set __label__ 
-              pattern = 'BRNOL|' + blockId;
-            }
-            replaceLabelLabels(internals, externalsLabels, pattern);
-            if (dcheck('relooping')) dprint('externalsEntries: ' + dump(externalsEntries));
-          }
-
-          // inner
-          ret.inner = makeBlock(internals, entries, labelsDict);
-
-          if (externals.length > 0) {
-            // outer
-            ret.next = makeBlock(externals, externalsEntries, labelsDict);
-          }
-
-          return ret;
-        }
-
-        // XXX change this logic?
-        if (entries.length === 1 && canReturn) return makeLoop();
-
-        // === handle multiple branches from the entry with a 'multiple' ===
-        //
-        // For each entry, try to 'build it out' as much as possible. Add labels, until
-        //    * hit a post label
-        //    * hit a label reachable by another actual entry
-
-        dprint('relooping', 'trying multiple...');
-
-        var shouldNotReach = entryLabels;
-        var handlingNow = [];
-        var actualEntryLabels = [];
-        var postEntryLabels = {};
-        entryLabels.forEach(function(entryLabel) {
-          entryLabel.blockChildren = [];
-          var visited = {};
-          function tryAdd(label) {
-            if (label.ident in visited) return;
-            visited[label.ident] = true;
-            if (!isReachable(label, shouldNotReach, entryLabel)) {
-              entryLabel.blockChildren.push(label);
-              handlingNow.push(label);
-              keys(label.outLabels).forEach(function(outLabelId) { tryAdd(labelsDict[outLabelId]) });
-            } else {
-              postEntryLabels[label.ident] = true; // This will be an entry in the next block
-            }
-          }
-          tryAdd(entryLabel);
-          if (entryLabel.blockChildren.length > 0) {
-            dprint('relooping', '  Considering multiple, found a valid entry, ' + entryLabel.ident);
-            actualEntryLabels.push(entryLabel);
-          }
-        });
-
-        if (dcheck('relooping')) dprint('  Considering multiple, canHandle: ' + getLabelIds(handlingNow));
-
-        if (handlingNow.length > 0) {
-          // This is a 'multiple'
-
-          var actualEntries = getLabelIds(actualEntryLabels);
-          if (dcheck('relooping')) dprint('   Creating multiple, with entries: ' + actualEntries + ', post entries: ' + dump(postEntryLabels));
-          actualEntryLabels.forEach(function(actualEntryLabel) {
-            if (dcheck('relooping')) dprint('      creating sub-block in multiple for ' + actualEntryLabel.ident + ' : ' + getLabelIds(actualEntryLabel.blockChildren) + ' ::: ' + actualEntryLabel.blockChildren.length);
-
-            var pattern = 'BREAK|' + blockId;
-            if (keys(postEntryLabels).length == 1) {
-              // We are breaking out of a multiple and have one entry after it, so we don't need to set __label__
-              pattern = 'BRNOL|' + blockId;
-            }
-            keys(postEntryLabels).forEach(function(post) {
-              replaceLabelLabels(actualEntryLabel.blockChildren, set(post), pattern);
-            });
-
-            // Create child block
-            actualEntryLabel.block = makeBlock(actualEntryLabel.blockChildren, [actualEntryLabel.blockChildren[0].ident], labelsDict);
-          });
-          return {
-            type: 'multiple',
-            id: blockId,
-            needBlockId: true,
-            entries: actualEntries,
-            entryLabels: actualEntryLabels,
-            labels: handlingNow,
-            next: makeBlock(labels.filter(function(label) { return handlingNow.indexOf(label) == -1 }), keys(postEntryLabels), labelsDict)
-          };
-        }
-
-        assert(canReturn, 'If not a multiple, must be able to create a loop');
-
-        return makeLoop();
+        return emulated;
       }
-
-      // TODO: each of these can be run in parallel
       item.functions.forEach(function(func) {
         dprint('relooping', "// relooping function: " + func.ident);
         func.block = makeBlock(func.labels, [toNiceIdent(func.labels[0].ident)], func.labelsDict, func.forceEmulated);