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

[Tamar Christina]

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.

The last review had some concern about the complexity. I'd note that if
I outline the code to a helper, it does become easier to read as it
replaces the nested conditionals with just early outs.

I can do that if preferred?

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.tcc (_M_dfs_next): Inline consume matches
	on _S_opcode_repeat.

---
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index b1a87da5afee4d854708207906d119f4b5b151b4..e0835049de7e7790b7065f035b732b23d4d4d52d 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -400,7 +400,24 @@ namespace __detail
 				   _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)
+	    if (__next != _S_invalid_state_id)
+	      {
+		const auto& __alt_state = _M_nfa[__next];
+		if (__alt_state._M_opcode() == _S_opcode_match
+		    && __alt_state._M_next == __i)
+		  {
+		    if (_M_current != _M_end
+			&& __alt_state._M_matches(*_M_current))
+		      {
+			++_M_current;
+			return __i;
+		      }
+		    return _S_invalid_state_id;
+		  }
+	      }
+	  return __next;
 	}
       else // Non-greedy mode
 	{


-- 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rb20703.patch
Type: text/x-diff
Size: 1034 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260729/f641f947/attachment.bin>