[patch v3 4/4][libstdc++]: Inline simple regex repeating matches in DFS [PR126274]

Optimize the common DFS NFA shape repeat -> match -> repeat, which is produced
by repeated character classes such as [\w]+, [^\s?#]+, and #+.

Since the second patch the DFS continuation already avoids pushing a separate
_S_fopcode_next frame for many states.  This patch adds a small improvement
for greedy repeats.

After creating the same fallback and repeat bookkeeping frames as before, if
the repeated body is a single match state that returns to the repeat state,
consume that match state immediately and continue at the repeat.

Backtracking behavior is unchanged.  _M_rep_once_more still creates the
restore/decrement frames, and the repeat exit fallback is still saved before
trying the body.  If the body match fails, the helper returns
_S_invalid_state_id so the normal frame loop restores repeat state and tries
pending fallbacks.

Benchmarks improvements compared to GCC previous patch in series:

 at -O2:

  email: +4.7%
  URI: +5.1%
  IPv4 -1.1%

 at -O3:

  email: +4.5%,
  URI: +4.1%
  IPv4: -0.2%

And finally gets us better than GCC 15.

I outlined the helper into _M_match_simple_repeat_body since that
looks more readable.

Bootstrapped Regtested on aarch64-none-linux-gnu,
arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
-m32, -m64 and no issues.

Ok for master?

Thanks,
Tamar

libstdc++-v3/ChangeLog:

	PR libstdc++/126274
	* include/bits/regex_executor.h (_M_match_simple_repeat_body): New.
	* include/bits/regex_executor.tcc (_M_dfs_next): Inline consume matches
	on _S_opcode_repeat.
	(_M_match_simple_repeat_body): New.

---
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c2dce4e24d35807b311d5a3273297f72a74cc24d..7b9f86ce315a11c2336aca3e17ca05001f1fc35d 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -140,6 +140,9 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
       _StateIdT
       _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
 
+      _StateIdT
+      _M_match_simple_repeat_body(_StateIdT, _StateIdT);
+
       template<_Search_mode __search_mode>
       _StateIdT
       _M_handle_repeat(_Match_mode, _StateIdT);
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 2c03c6bfe9377ac66bffc0f3d9350d5d5cc35468..6c7255ce6be17d8e2682e41cce67799fb9caf79a 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -379,6 +379,31 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
       return _S_invalid_state_id;
     }
 
+  // Try to consume the common repeat body shape
+  //   repeat -> match -> repeat
+  // without going through the generic state dispatch again.
+  template<typename _BiIter, typename _Alloc, typename _TraitsT>
+#ifdef __OPTIMIZE__
+    [[__gnu__::__always_inline__]]
+#endif
+    inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
+    _M_match_simple_repeat_body(_StateIdT __next, _StateIdT __repeat)
+    {
+      if (__next == _S_invalid_state_id)
+	return _S_invalid_state_id;
+
+      const auto& __state = _M_nfa[__next];
+      if (__state._M_opcode() != _S_opcode_match
+	  || __state._M_next != __repeat)
+	return __next;
+
+      if (_M_current == _M_end || !__state._M_matches(*_M_current))
+	return _S_invalid_state_id;
+
+      ++_M_current;
+      return __repeat;
+    }
+
   // _M_alt branch is "match once more", while _M_next is "get me out
   // of this quantifier". Executing _M_next first or _M_alt first don't
   // mean the same thing, and we need to choose the correct order under
@@ -401,7 +426,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
 				   _M_current);
 	  else
 	    _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
-	  return _M_rep_once_more(__match_mode, __i);
+	  _StateIdT __next = _M_rep_once_more(__match_mode, __i);
+	  if constexpr (__search_mode == _Search_mode::_Dfs)
+	    return _M_match_simple_repeat_body(__next, __i);
+	  else
+	    return __next;
 	}
       else // Non-greedy mode
 	{


--

diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c2dce4e24d35807b311d5a3273297f72a74cc24d..7b9f86ce315a11c2336aca3e17ca05001f1fc35d 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -140,6 +140,9 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
       _StateIdT
       _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
 
+      _StateIdT
+      _M_match_simple_repeat_body(_StateIdT, _StateIdT);
+
       template<_Search_mode __search_mode>
       _StateIdT
       _M_handle_repeat(_Match_mode, _StateIdT);
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 2c03c6bfe9377ac66bffc0f3d9350d5d5cc35468..6c7255ce6be17d8e2682e41cce67799fb9caf79a 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -379,6 +379,31 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
       return _S_invalid_state_id;
     }
 
+  // Try to consume the common repeat body shape
+  //   repeat -> match -> repeat
+  // without going through the generic state dispatch again.
+  template<typename _BiIter, typename _Alloc, typename _TraitsT>
+#ifdef __OPTIMIZE__
+    [[__gnu__::__always_inline__]]
+#endif
+    inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
+    _M_match_simple_repeat_body(_StateIdT __next, _StateIdT __repeat)
+    {
+      if (__next == _S_invalid_state_id)
+	return _S_invalid_state_id;
+
+      const auto& __state = _M_nfa[__next];
+      if (__state._M_opcode() != _S_opcode_match
+	  || __state._M_next != __repeat)
+	return __next;
+
+      if (_M_current == _M_end || !__state._M_matches(*_M_current))
+	return _S_invalid_state_id;
+
+      ++_M_current;
+      return __repeat;
+    }
+
   // _M_alt branch is "match once more", while _M_next is "get me out
   // of this quantifier". Executing _M_next first or _M_alt first don't
   // mean the same thing, and we need to choose the correct order under
@@ -401,7 +426,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
 				   _M_current);
 	  else
 	    _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
-	  return _M_rep_once_more(__match_mode, __i);
+	  _StateIdT __next = _M_rep_once_more(__match_mode, __i);
+	  if constexpr (__search_mode == _Search_mode::_Dfs)
+	    return _M_match_simple_repeat_body(__next, __i);
+	  else
+	    return __next;
 	}
       else // Non-greedy mode
 	{