[Outlining] Adding more tests (#6117)

Checking a couple of testing TODOs off and adding more tests of the outlining pass for outlining:
- a sequence at the beginning of an existing function
- a sequence that is outlined into a function that takes no arguments
- multiple sequences from the same source function into different outlined functions

2 files changed, 45 insertions, 13 deletions

diff --git a/src/passes/Outlining.cpp b/src/passes/Outlining.cpp
index 4bb883187..c7644c339 100644
--- a/src/passes/Outlining.cpp
+++ b/src/passes/Outlining.cpp
@@ -1,3 +1,19 @@
+/*
+ * Copyright 2023 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 #include "ir/names.h"
 #include "ir/utils.h"
 #include "pass.h"
@@ -246,6 +262,9 @@ struct Outlining : public Pass {
     // relative to the entire program.
     auto sequences = makeSequences(module, substrings, stringify);
     outline(module, sequences);
+    // Position the outlined functions first in the functions vector to make
+    // the outlining lit tests far more readable.
+    moveOutlinedFunctions(module, substrings.size());
   }
 
   Name addOutlinedFunction(Module* module,
@@ -253,17 +272,16 @@ struct Outlining : public Pass {
                            const std::vector<Expression*>& exprs) {
     auto startIdx = substring.StartIndices[0];
     // The outlined functions can be named anything.
-    Name outlinedFunc =
-      Names::getValidFunctionName(*module, std::string("outline$"));
+    Name func = Names::getValidFunctionName(*module, std::string("outline$"));
     // Calculate the function signature for the outlined sequence.
     StackSignature sig;
     for (uint32_t exprIdx = startIdx; exprIdx < startIdx + substring.Length;
          exprIdx++) {
       sig += StackSignature(exprs[exprIdx]);
     }
-    module->addFunction(Builder::makeFunction(
-      outlinedFunc, Signature(sig.params, sig.results), {}));
-    return outlinedFunc;
+    module->addFunction(
+      Builder::makeFunction(func, Signature(sig.params, sig.results), {}));
+    return func;
   }
 
   using Sequences =
@@ -278,15 +296,14 @@ struct Outlining : public Pass {
                           const HashStringifyWalker& stringify) {
     Sequences seqByFunc;
     for (auto& substring : substrings) {
-      Name outlinedFunc =
-        addOutlinedFunction(module, substring, stringify.exprs);
+      auto func = addOutlinedFunction(module, substring, stringify.exprs);
       for (auto seqIdx : substring.StartIndices) {
         // seqIdx is relative to the entire program; making the idx of the
         // sequence relative to its function is better for outlining because we
         // walk functions.
         auto [relativeIdx, existingFunc] = stringify.makeRelative(seqIdx);
-        auto seq = OutliningSequence(
-          relativeIdx, relativeIdx + substring.Length, outlinedFunc);
+        auto seq =
+          OutliningSequence(relativeIdx, relativeIdx + substring.Length, func);
         seqByFunc[existingFunc].push_back(seq);
       }
     }
@@ -307,6 +324,23 @@ struct Outlining : public Pass {
     }
   }
 
+  void moveOutlinedFunctions(Module* module, uint32_t outlinedCount) {
+    // Rearrange outlined functions to the beginning of the functions vector by
+    // using std::make_move_iterator to avoid making copies. A temp vector is
+    // created to avoid iterator invalidation.
+    auto count = module->functions.size();
+    std::vector<std::unique_ptr<Function>> temp(
+      std::make_move_iterator(module->functions.end() - outlinedCount),
+      std::make_move_iterator(module->functions.end()));
+    module->functions.insert(module->functions.begin(),
+                             std::make_move_iterator(temp.begin()),
+                             std::make_move_iterator(temp.end()));
+    module->functions.resize(count);
+    // After the functions vector is directly manipulated, we need to call
+    // updateFunctionsMap().
+    module->updateFunctionsMap();
+  }
+
 #if OUTLINING_DEBUG
   void printHashString(const std::vector<uint32_t>& hashString,
                        const std::vector<Expression*>& exprs) {
diff --git a/src/passes/hash-stringify-walker.cpp b/src/passes/hash-stringify-walker.cpp
index 5afd50ef4..c9173c6a5 100644
--- a/src/passes/hash-stringify-walker.cpp
+++ b/src/passes/hash-stringify-walker.cpp
@@ -86,11 +86,9 @@ std::vector<SuffixTree::RepeatedSubstring>
 StringifyProcessor::repeatSubstrings(std::vector<uint32_t>& hashString) {
   SuffixTree st(hashString);
   std::vector<SuffixTree::RepeatedSubstring> substrings(st.begin(), st.end());
-  for (auto substring : substrings) {
+  for (auto& substring : substrings) {
     // Sort by increasing start index to ensure determinism.
-    std::sort(substring.StartIndices.begin(),
-              substring.StartIndices.end(),
-              [](uint32_t a, uint32_t b) { return a < b; });
+    std::sort(substring.StartIndices.begin(), substring.StartIndices.end());
   }
   // Substrings are sorted so that the longest substring that repeats the most
   // times is ordered first. This is done so that we can assume the most