Add a peephole optimization pass to the regex compiler

1 files changed, 17 insertions, 0 deletions

diff --git a/src/regex_impl.cc b/src/regex_impl.cc
index 28d201f5..8742e19c 100644
--- a/src/regex_impl.cc
+++ b/src/regex_impl.cc
@@ -684,6 +684,7 @@ struct RegexCompiler
         {
             m_program.forward_start_desc = compute_start_desc<RegexMode::Forward>();
             compile_node<RegexMode::Forward>(0);
+            peephole_optimize(0, m_program.instructions.size());
             push_inst(CompiledRegex::Match);
         }
 
@@ -692,6 +693,7 @@ struct RegexCompiler
             m_program.first_backward_inst = m_program.instructions.size();
             m_program.backward_start_desc = compute_start_desc<RegexMode::Backward>();
             compile_node<RegexMode::Backward>(0);
+            peephole_optimize(m_program.first_backward_inst, m_program.instructions.size());
             push_inst(CompiledRegex::Match);
         }
         else
@@ -1019,6 +1021,21 @@ private:
         return std::make_unique<CompiledRegex::StartDesc>(start_desc);
     }
 
+    void peephole_optimize(size_t begin, size_t end)
+    {
+        if (not (m_flags & RegexCompileFlags::Optimize))
+            return;
+
+        // Move saves after all assertions on the same character
+        auto is_assertion = [](CompiledRegex::Op op) { return op >= CompiledRegex::LineStart; };
+        for (auto i = begin, j = begin + 1; j < end; ++i, ++j)
+        {
+            if (m_program.instructions[i].op == CompiledRegex::Save and
+                is_assertion(m_program.instructions[j].op))
+                std::swap(m_program.instructions[i], m_program.instructions[j]);
+        }
+    }
+
     const ParsedRegex::Node& get_node(ParsedRegex::NodeIndex index) const
     {
         return m_parsed_regex.nodes[index];