[patch v3 1/4][libstdc++]: Continue with regex DFS traversals without next frames [PR126274]
Tamar Christina
Tamar.Christina@arm.com
Fri Sep 18 12:06:19 GMT 2026
> -----Original Message-----
> From: Jonathan Wakely <jwakely@redhat.com>
> Sent: 18 September 2026 13:00
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; libstdc++@gcc.gnu.org;
> tkaminsk@redhat.com; ppalka@redhat.com
> Subject: Re: [patch v3 1/4][libstdc++]: Continue with regex DFS traversals
> without next frames [PR126274]
>
> N.B. this mail had exactly the same MessageId as [patch v2 1/4] so my
> download scripts (based on 'b4 mbox') refused to fetch [patch v3 1/4].
>
> The duplicate MessageId is patch-20701-rb-rev-unknown-tamar@arm.com
> which is not very unique.
Ah, thought I had fixed that, but the call failed and it put in "unknown".
Thanks will fix.
>
> On Thu, 20 Aug 2026 at 18:13 +0100, Tamar Christina wrote:
> >The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> changed
> >the recursive implementation with an iterative one using an explicit heap.
> >
> >However one benefit of the previous implementation is that the frame did
> >not have to be saved and popped when the match is supposed to continue.
> >
> >This means that on hot paths we now have additional memory accesses and
> >need additional instructions to calculate the memref addresses.
> >
> >For DFS matching this is clearly suboptimal since when _M_rep_once_more
> >then we push and pop the same state but there is enough other acceses
> >in between the push and pop that we get a lot of cache misses.
> >
> >This makes all the private _m_handle_* methods return a _StateIdT which
> allows
> >the caller to deal with the value, so that for DFS we can avoid pushing the
> >frame if needed.
> >
> >For DFS we try to consume the state immediately until we're told to
> >stop.
> >
> >For this to work the methods have to me marked always inline, because a key
> part
> >of the optimization is to keep the values in registers rather than passing
> >through stack and the function call overheads and AAPCS requirements
> would
> >negate the benefits.
> >
> >The patch also reserves some frames in the initial vector to avoid having
> >resizes on the hot path. To avoid large RSS before matching even starts
> >we provide a cap to the initial reservations. However I have not yet
> addressed
> >
> >Jakub's comment that the cap at 255 is likely to big. I need to do more
> >experiments here to figure out if it's even needed. For now I left it since I
> >am expecting another respin here.
> >
> >The __dfs_mode changes are because the constexpr patch still gave a big
> boost so
> >it prepares to apply it.
> >
> >There is still a regression until the end of the series and each patch
> >will chip away at it.
> >
> >Also note that with none of these changes do I see an increase heap or stack
> >usage that the original fix fixed. RSS stays about the same.
> >
> >PS. thanks for the link to the algorithm in the source, it was useful to
> >understand how the machinery works!
> >
> >Benchmark improvements vs GCC 16:
> >
> > at -O2:
> >
> > email: +36.1%
> > URI: +36.5%
> > IPv4 +33.0%
> >
> > at -O3:
> >
> > email: +45.5%,
> > URI: +44.9%
> > IPv4: +43.0%
> >
> >On Neoverse-V1
> >
> >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 (_Executor): Reserve frame space.
> > (_M_rep_once_more, _M_handle_repeat, _M_handle_subexpr_begin,
> > _M_handle_subexpr_end, _M_handle_line_begin_assertion,
> > _M_handle_line_end_assertion, _M_handle_word_boundary,
> > _M_handle_subexpr_lookahead, _M_handle_match,
> _M_handle_backref,
> > _M_node): return StateIdT.
> > (_M_visited): Mark inline.
> > * include/bits/regex_executor.tcc (_M_rep_once_more,
> _M_handle_repeat,
> > _M_handle_subexpr_begin, _M_handle_subexpr_end,
> > _M_handle_line_begin_assertion, _M_handle_line_end_assertion,
> > _M_handle_word_boundary, _M_handle_subexpr_lookahead,
> _M_handle_match,
> > _M_handle_backref): Return state, mark always inline.
> > (_M_node): Return StateIdT and also decide what to do with the value
> > after return.
> > (_M_dfs): Traverse states iteratively for _S_fopcode_next,
> > _S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more
> > and _S_fopcode_rep_once_more.
> >
> >---
> >diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-
> v3/include/bits/regex.h
> >index
> 0e815ca086eb33975dd3ac66841c6eaf4a54b2ad..dce420251db0817fa05ab
> 79d7ca0838f214fdc33 100644
> >--- a/libstdc++-v3/include/bits/regex.h
> >+++ b/libstdc++-v3/include/bits/regex.h
> >@@ -61,8 +61,10 @@ namespace __detail
> > _RegexExecutorPolicy __policy,
> > bool __match_mode);
> >
> >+_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
> > template<typename, typename, typename>
> > class _Executor;
> >+_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> >
> > template<typename _Tp>
> > struct __is_contiguous_iter : false_type { };
> >diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> v3/include/bits/regex_executor.h
> >index
> 797ad702784b6d1bf07734d91683946d989630f5..c2d1d5f0bfeee279fbd1
> fb138c58f45f9cdbe60e 100644
> >--- a/libstdc++-v3/include/bits/regex_executor.h
> >+++ b/libstdc++-v3/include/bits/regex_executor.h
> >@@ -41,6 +41,7 @@ namespace __detail
> > * @{
> > */
> >
> >+_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
>
> This moves _ExecutorFrame into namespace _V2 as well, but I don't
> think that's necessary, is it? It hasn't changed, so leaving it alone
> results in slightly shorter mangled names, and fewer distinct symbols
> in an executable if you mix old and new instantiations linked
> together.
>
> I think the macro should be moved 3 lines lower in this file.
>
> The macro should be *before* the Doxygen comment block, not between
> the comment and the class template. Otherwise the Doxygen comment
> refers to the inline namespace instead of the class template (in
> practice it won't, because the macro expands to nothing when Doxygen
> preprocesses the header, but in principle the comment should be
> attached directly to the class not a namespace declaration before the
> class).
>
>
> > template<typename _BiIter, bool _Trivial =
> is_trivially_copyable<_BiIter>::value>
> > struct _ExecutorFrame;
> >
> >@@ -113,43 +114,43 @@ namespace __detail
> > _M_search();
> >
> > private:
> >- void
> >+ _StateIdT
> > _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_repeat(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_subexpr_begin(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_subexpr_end(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_line_begin_assertion(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_line_end_assertion(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_word_boundary(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_match(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_backref(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_accept(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_handle_alternative(_Match_mode, _StateIdT);
> >
> >- void
> >+ _StateIdT
> > _M_node(_Match_mode, _StateIdT);
> >
> > void
> >@@ -247,7 +248,7 @@ namespace __detail
> > return (_M_re._M_automaton->_M_options() & __m) == __m;
> > }
> >
> >- bool
> >+ inline bool
> > _M_visited(_StateIdT __i)
> > {
> > if (_M_visited_states)
> >@@ -284,6 +285,7 @@ namespace __detail
> > bool _M_has_sol;
> > };
> >
> >+_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
>
> And please put this one immediately after the closing brace of
> _Executor with a blank line after it, not before it. That makes it a
> bit clearer than it's tied to _Executor.
>
>
> > ///@} regex-detail
> > } // namespace __detail
> > _GLIBCXX_END_NAMESPACE_VERSION
> >diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> v3/include/bits/regex_executor.tcc
> >index
> 167a7a345300868ed5e0852e328569aec47e3d0d..87d5ac68685c22bbedcf
> 9e67f96b50b61392a701 100644
> >--- a/libstdc++-v3/include/bits/regex_executor.tcc
> >+++ b/libstdc++-v3/include/bits/regex_executor.tcc
> >@@ -36,6 +36,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
> > namespace __detail
> > {
> >+_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
>
> I don't think you need the BEGIN and END macros in this file, because
> name lookup for _Executor in the member function definitions will
> automatically find _V2::_Executor because it's an inline namespace.
>
> If the tests still pass with those tweaks to the macro placement, this
> [patch v3 1/4] is OK for trunk.
>
> We want this backported to gcc-16 too, right?
If possible, but I realize It's a big patch so if it's not possible that's OK,
but if we could that would be great.
I'll do the other changes now.
Thanks,
Tamar
>
>
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > bool _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_search()
> >@@ -250,8 +251,14 @@ namespace __detail
> > // infinite loop by refusing to continue when it's already been
> > // visited more than twice. It's `twice` instead of `once` because
> > // we need to spare one more time for potential group capture.
> >+ //
> >+ // If the node cannot be re-entered anymore from the current state then
> return
> >+ // _S_invalid_state_id otherwise return the current state without going
> >+ // through a vector, allowing the caller to decide what to do with the state
> >+ // This is beneficial for DFS since DFS can continue with the next state
> >+ // immediately
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_rep_once_more(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> >@@ -263,7 +270,7 @@ namespace __detail
> > _M_frames.back()._M_count = __rep_count.second;
> > __rep_count.first = _M_current;
> > __rep_count.second = 1;
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >+ return __state._M_alt;
> > }
> > else
> > {
> >@@ -271,9 +278,10 @@ namespace __detail
> > {
> > __rep_count.second++;
> > _M_frames.emplace_back(_S_fopcode_decrement_rep_count,
> __i);
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >+ return __state._M_alt;
> > }
> > }
> >+ return _S_invalid_state_id;
> > }
> >
> > // _M_alt branch is "match once more", while _M_next is "get me out
> >@@ -281,8 +289,11 @@ namespace __detail
> > // mean the same thing, and we need to choose the correct order under
> > // given greedy mode.
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >- _M_handle_repeat(_Match_mode, _StateIdT __i)
> >+#ifdef __OPTIMIZE__
> >+ [[__gnu__::__always_inline__]]
> >+#endif
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ _M_handle_repeat(_Match_mode __match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > // Greedy.
> >@@ -294,7 +305,7 @@ namespace __detail
> > _M_current);
> > else
> > _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >- _M_frames.emplace_back(_S_fopcode_rep_once_more, __i);
> >+ return _M_rep_once_more(__match_mode, __i);
> > }
> > else // Non-greedy mode
> > {
> >@@ -303,7 +314,7 @@ namespace __detail
> > // vice-versa.
> > _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> __i,
> > _M_current);
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> > }
> > else
> > {
> >@@ -316,97 +327,122 @@ namespace __detail
> > // accepted state *must* be better than a solution that
> > // matches a non-greedy quantifier one more time.
> >
> _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i);
> >- _M_frames.emplace_back(_S_fopcode_next,
> __state._M_next);
> >+ return __state._M_next;
> > }
> > }
> > }
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+#ifdef __OPTIMIZE__
> >+ [[__gnu__::__always_inline__]]
> >+#endif
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_subexpr_begin(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > auto& __res = _M_cur_results[__state._M_subexpr];
> >- _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >- static_cast<_StateIdT>(__state._M_subexpr),
> >- __res.first);
> >+ if (_M_nfa._M_has_backref
> >+ || __state._M_subexpr != 0
> >+ || _M_search_mode != _Search_mode::_DFS)
> >+ _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >+ static_cast<_StateIdT>(__state._M_subexpr),
> >+ __res.first);
> > __res.first = _M_current;
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+#ifdef __OPTIMIZE__
> >+ [[__gnu__::__always_inline__]]
> >+#endif
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_subexpr_end(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > auto& __res = _M_cur_results[__state._M_subexpr];
> >- _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >- static_cast<_StateIdT>(__state._M_subexpr),
> >- __res.second);
> >- _M_frames.back()._M_subexpr_end = true;
> >- _M_frames.back()._M_matched = __res.matched;
> >+ if (_M_nfa._M_has_backref
> >+ || __state._M_subexpr != 0
> >+ || _M_search_mode != _Search_mode::_DFS)
> >+ {
> >+ _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >+ static_cast<_StateIdT>(__state._M_subexpr),
> >+ __res.second);
> >+ _M_frames.back()._M_subexpr_end = true;
> >+ _M_frames.back()._M_matched = __res.matched;
> >+ }
> >+
> > __res.second = _M_current;
> > __res.matched = true;
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_line_begin_assertion(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > if (_M_at_begin())
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_line_end_assertion(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > if (_M_at_end())
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_word_boundary(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > if (_M_word_boundary() == !__state._M_neg)
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> >+ return _S_invalid_state_id;
> > }
> >
> > // Here __state._M_alt offers a single start node for a sub-NFA.
> > // We recursively invoke our algorithm to match the sub-NFA.
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_subexpr_lookahead(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > if (_M_lookahead(__state._M_alt) == !__state._M_neg)
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+#ifdef __OPTIMIZE__
> >+ [[__gnu__::__always_inline__]]
> >+#endif
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_match(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> > if (_M_current == _M_end)
> >- return;
> >+ return _S_invalid_state_id;
> > if (_M_search_mode == _Search_mode::_DFS)
> > {
> > if (__state._M_matches(*_M_current))
> > {
> > ++_M_current;
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> > }
> > }
> > else
> > if (__state._M_matches(*_M_current))
> > _M_match_queue.emplace_back(__state._M_next, _M_cur_results);
> >+
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _TraitsT>
> >@@ -462,7 +498,7 @@ namespace __detail
> > // (_M_current, _M_current + (__submatch.second - __submatch.first)).
> > // If matched, keep going; else just return and try another state.
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_backref(_Match_mode, _StateIdT __i)
> > {
> > __glibcxx_assert(_M_search_mode == _Search_mode::_DFS);
> >@@ -470,7 +506,7 @@ namespace __detail
> > const auto& __state = _M_nfa[__i];
> > auto& __submatch = _M_cur_results[__state._M_backref_index];
> > if (!__submatch.matched)
> >- return;
> >+ return _S_invalid_state_id;
> > auto __last = _M_current;
> > for (auto __tmp = __submatch.first;
> > __last != _M_end && __tmp != __submatch.second;
> >@@ -482,12 +518,17 @@ namespace __detail
> > __submatch.first, __submatch.second, _M_current, __last))
> > {
> > _M_current = __last;
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >+ return __state._M_next;
> > }
> >+
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+#ifdef __OPTIMIZE__
> >+ [[__gnu__::__always_inline__]]
> >+#endif
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_accept(_Match_mode __match_mode, _StateIdT)
> > {
> > if (_M_search_mode == _Search_mode::_DFS)
> >@@ -528,7 +569,7 @@ namespace __detail
> > {
> > if (_M_current == _M_begin
> > && (_M_flags & regex_constants::match_not_null))
> >- return;
> >+ return _S_invalid_state_id;
> > if (__match_mode == _Match_mode::_Prefix || _M_current ==
> _M_end)
> > if (!_M_has_sol)
> > {
> >@@ -536,10 +577,14 @@ namespace __detail
> > _M_results = _M_cur_results;
> > }
> > }
> >+ return _S_invalid_state_id;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+#ifdef __OPTIMIZE__
> >+ [[__gnu__::__always_inline__]]
> >+#endif
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_handle_alternative(_Match_mode, _StateIdT __i)
> > {
> > const auto& __state = _M_nfa[__i];
> >@@ -549,7 +594,7 @@ namespace __detail
> > // Pick lhs if it matches. Only try rhs if it doesn't.
> > _M_frames.emplace_back(_S_fopcode_fallback_next,
> __state._M_next,
> > _M_current);
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >+ return __state._M_alt;
> > }
> > else
> > {
> >@@ -557,7 +602,7 @@ namespace __detail
> > // See "case _S_opcode_accept:" handling above.
> > _M_frames.emplace_back(_S_fopcode_posix_alternative,
> __state._M_next,
> > _M_current);
> >- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >+ return __state._M_alt;
> > }
> > }
> >
> >@@ -565,54 +610,69 @@ namespace __detail
> > #ifdef __OPTIMIZE__
> > [[__gnu__::__always_inline__]]
> > #endif
> >- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_node(_Match_mode __match_mode, _StateIdT __i)
> > {
> >- if (_M_visited(__i))
> >- return;
> >+ // DFS has no _M_visited implementation as such don't even have the
> branch
> >+ // or the check in the call graph.
> >+ if (_M_search_mode == _Search_mode::_BFS)
> >+ if (_M_visited(__i))
> >+ return _S_invalid_state_id;
> >
> >+ _StateIdT __next = _S_invalid_state_id;
> > switch (_M_nfa[__i]._M_opcode())
> > {
> > case _S_opcode_repeat:
> >- _M_handle_repeat(__match_mode, __i); break;
> >+ __next = _M_handle_repeat(__match_mode, __i); break;
> > case _S_opcode_subexpr_begin:
> >- _M_handle_subexpr_begin(__match_mode, __i); break;
> >+ __next = _M_handle_subexpr_begin(__match_mode, __i);
> >+ break;
> > case _S_opcode_subexpr_end:
> >- _M_handle_subexpr_end(__match_mode, __i); break;
> >+ __next = _M_handle_subexpr_end(__match_mode, __i);
> >+ break;
> > case _S_opcode_line_begin_assertion:
> >- _M_handle_line_begin_assertion(__match_mode, __i); break;
> >+ __next = _M_handle_line_begin_assertion(__match_mode, __i);
> break;
> > case _S_opcode_line_end_assertion:
> >- _M_handle_line_end_assertion(__match_mode, __i); break;
> >+ __next = _M_handle_line_end_assertion(__match_mode, __i); break;
> > case _S_opcode_word_boundary:
> >- _M_handle_word_boundary(__match_mode, __i); break;
> >+ __next = _M_handle_word_boundary(__match_mode, __i); break;
> > case _S_opcode_subexpr_lookahead:
> >- _M_handle_subexpr_lookahead(__match_mode, __i); break;
> >+ __next = _M_handle_subexpr_lookahead(__match_mode, __i);
> break;
> > case _S_opcode_match:
> >- _M_handle_match(__match_mode, __i); break;
> >+ __next = _M_handle_match(__match_mode, __i); break;
> > case _S_opcode_backref:
> > if (_M_search_mode == _Search_mode::_DFS)
> >- _M_handle_backref(__match_mode, __i);
> >+ __next = _M_handle_backref(__match_mode, __i);
> > else
> > __builtin_unreachable();
> > break;
> > case _S_opcode_accept:
> >- _M_handle_accept(__match_mode, __i); break;
> >+ __next = _M_handle_accept(__match_mode, __i); break;
> > case _S_opcode_alternative:
> >- _M_handle_alternative(__match_mode, __i); break;
> >+ __next = _M_handle_alternative(__match_mode, __i); break;
> > default:
> > __glibcxx_assert(false);
> > }
> >+ return __next;
> > }
> >
> > template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > void _Executor<_BiIter, _Alloc, _TraitsT>::
> > _M_dfs(_Match_mode __match_mode, _StateIdT __start)
> > {
> >- const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
> >- _M_frames.emplace_back(_S_fopcode_next, __start);
> >+ _StateIdT __next = __start;
> >
> >- while (!_M_frames.empty())
> >+ while (true)
> > {
> >+ // Follow immediate successors without re-entering the frame
> >+ // loop until we fail. This avoids the needless state save and
> >+ // restore through memory.
> >+ while (__next != _S_invalid_state_id)
> >+ __next = _M_node(__match_mode, __next);
> >+
> >+ if (_M_frames.empty())
> >+ break;
> >+
> > _ExecutorFrame<_BiIter> __frame = std::move(_M_frames.back());
> > _M_frames.pop_back();
> >
> >@@ -621,27 +681,27 @@ namespace __detail
> > case _S_fopcode_fallback_next:
> > if (_M_has_sol)
> > break;
> >- if (__dfs_mode)
> >+ if (_M_search_mode == _Search_mode::_DFS)
> > _M_current = __frame._M_pos;
> > [[__fallthrough__]];
> > case _S_fopcode_next:
> >- _M_node(__match_mode, __frame._M_state_id);
> >+ __next = __frame._M_state_id;
> > break;
> >
> > case _S_fopcode_fallback_rep_once_more:
> > if (_M_has_sol)
> > break;
> >- if (__dfs_mode)
> >+ if (_M_search_mode == _Search_mode::_DFS)
> > _M_current = __frame._M_pos;
> > [[__fallthrough__]];
> > case _S_fopcode_rep_once_more:
> >- _M_rep_once_more(__match_mode, __frame._M_state_id);
> >+ __next = _M_rep_once_more(__match_mode,
> __frame._M_state_id);
> > break;
> >
> > case _S_fopcode_posix_alternative:
> > _M_frames.emplace_back(_S_fopcode_merge_sol, 0,
> _M_has_sol);
> >- _M_frames.emplace_back(_S_fopcode_next,
> __frame._M_state_id);
> >- if (__dfs_mode)
> >+ __next = __frame._M_state_id;
> >+ if (_M_search_mode == _Search_mode::_DFS)
> > _M_current = __frame._M_pos;
> > _M_has_sol = false;
> > break;
> >@@ -695,6 +755,7 @@ namespace __detail
> >
> > return __left_is_word != __right_is_word;
> > }
> >+_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> > } // namespace __detail
> > #pragma GCC diagnostic pop
> >
> >
> >
> >--
More information about the Libstdc++
mailing list