non-overlapping intervals

src/passes/Outlining.cpp

diff --git a/src/passes/Outlining.cpp b/src/passes/Outlining.cpp
index 68c3d03..b91cbcb 100644
--- a/src/passes/Outlining.cpp
+++ b/src/passes/Outlining.cpp
@@ -264,6 +264,77 @@
 };
 
 struct Outlining : public Pass {
+  std::vector<SuffixTree::RepeatedSubstring>
+  blah(const std::vector<SuffixTree::RepeatedSubstring>& substrings) {
+
+    struct Interval {
+      unsigned startIdx;
+      unsigned endIdx;
+      unsigned idxOfRepeatedSubstring;
+      unsigned score;
+
+      Interval(unsigned startIdx,
+               unsigned endIdx,
+               unsigned idxOfRepeatedSubstring,
+               unsigned score)
+        : startIdx(startIdx), endIdx(endIdx),
+          idxOfRepeatedSubstring(idxOfRepeatedSubstring), score(score) {}
+    };
+
+    std::vector<Interval> intervals;
+
+    // Make a construct we can use for finding intervals
+    for (Index i = 0; i < substrings.size(); i++) {
+      auto substring = substrings[i];
+      for (auto startIdx : substring.StartIndices) {
+        intervals.emplace_back(startIdx,
+                               startIdx + substring.Length,
+                               i,
+                               substring.Length *
+                                 substring.StartIndices.size());
+      }
+    }
+
+    // Sort construct
+    std::sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) {
+      return a.startIdx < b.startIdx;
+    });
+
+    // Add overlaps with lower scores to doNotInclude set
+    std::set<uint32_t> doNotInclude;
+    auto& ref_interval = intervals[0];
+    for (Index i = 1; i < intervals.size(); i++) {
+      auto& interval = intervals[i];
+      if (ref_interval.endIdx < interval.startIdx) {
+        ref_interval = interval;
+        continue;
+      }
+
+      // Keep the Interval with the higher score
+      // Update the ref_interval if its the one we're not keeping
+      if (interval.score > ref_interval.score) {
+        doNotInclude.insert(ref_interval.idxOfRepeatedSubstring);
+        ref_interval = interval;
+      } else {
+        doNotInclude.insert(interval.idxOfRepeatedSubstring);
+      }
+    }
+
+    std::vector<SuffixTree::RepeatedSubstring> result;
+
+    // Only include non-overlapping substrings
+    for (Index i = 0; i < substrings.size(); i++) {
+      if (doNotInclude.find(i) != doNotInclude.end()) {
+        continue;
+      }
+
+      auto substring = substrings[i];
+      result.push_back(substring);
+    }
+
+    return result;
+  }
+
   void run(Module* module) {
     HashStringifyWalker stringify;
     // Walk the module and create a "string representation" of the program.
@@ -275,6 +346,9 @@
     DBG(printHashString(stringify.hashString, stringify.exprs));
     // Remove substrings that are substrings of longer repeat substrings.
     substrings = StringifyProcessor::dedupe(substrings);
+    ODBG(std::cerr << "\nSubstrings before blah: " << substrings.size());
+    substrings = blah(substrings);
+    ODBG(std::cerr << "\nSubstrings after blah: " << substrings.size());
     // Remove substrings with branch and return instructions until an analysis
     // is performed to see if the intended destination of the branch is included
     // in the substring to be outlined.
@@ -353,6 +427,11 @@
                    keys.begin(),
                    [](auto pair) { return pair.first; });
     for (auto func : keys) {
+      std::sort(seqByFunc[func].begin(),
+                seqByFunc[func].end(),
+                [](OutliningSequence a, OutliningSequence b) {
+                  return a.startIdx < b.startIdx;
+                });
       reconstruct.sequences = std::move(seqByFunc[func]);
       reconstruct.doWalkFunction(module->getFunction(func));
     }

test/gtest/stringify.cpp

diff --git a/test/gtest/stringify.cpp b/test/gtest/stringify.cpp
index c38c29d..0ef3d8c 100644
--- a/test/gtest/stringify.cpp
+++ b/test/gtest/stringify.cpp
@@ -288,21 +288,27 @@
       SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{23, 34})}}));
 }
 
+// Tests that local.set instructions inside of control flow are filtered
+// from being candidates for outlining
 TEST_F(StringifyTest, FilterLocalSets) {
   static auto localSetModuleText = R"wasm(
   (module
     (func $a (result i32)
         (local $x i32)
-        (local.set $x
-          (i32.const 1)
+        (block (result i32)
+          (local.set $x
+            (i32.const 1)
+          )
         )
       (i32.const 0)
       (i32.const 1)
     )
     (func $b (result i32)
         (local $x i32)
-        (local.set $x
-          (i32.const 1)
+        (block (result i32)
+          (local.set $x
+            (i32.const 1)
+          )
         )
       (i32.const 5)
       (i32.const 0)