In GCC 16 the commit r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
caused a big regression in performance of regex in libstdc++.
This and other patches were tested using the CPP version of the benchmarks
at https://github.com/mariomka/regex-benchmark/
The benchmark uses regex_token_iterator over the input text with these patterns:
- email: [\w.+-]+@[\w.-]+\.[\w.-]+
- URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
- IPv4:
(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])
Where it tests various types of regexpr. "email" has no backtracking so it's the
simplest NFA possible which we should be able to handle quickly.
"uri" has optional matches and some non capturing groups and "ipv4" adds some
alternative matching to the equation.
The input string is a 6.52 mb test file "input-text.txt"
The regressions of each type of regexpr compared to GCC 15 are:
email: 118.9%
URI: 124.8%
IPv4: 139.8%
So most matches became > 2x slower.
This patch series addresses the regressions and gets the new code to be
ultimately faster than the GCC 15 implementation.
Currently the _Executor class implements both a DFS and a BFS traveral mode
for the regex matching. It has a parameter _M_search_mode which it uses
inside the _Executor functions to separate out the implementations.
However this parameter is rather opague to IPA and so for each implementation
the other branch is always dead but they haven't been folded away.
This increases the number of dynamic instructions and branches being executed
and the branches seem to be often mispredicted.
The patch fixes it by moving _Search_mode out of the class and making it a
template parameter instead so we can at compile time fold away the two
implementations. This removes all the extra compare and branches from the
hot functions.
These changes improve the benchmarks compared with previous patch in series
at -O2:
email: +11.1%
URI: +10.3%
IPv4 +7.3%
at -O3:
email: +8.6%,
URI: +7.9%
IPv4: +3.6%
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 (_Search_mode): Move to top level.
(_M_handle_repeat, _M_handle_match, _M_handle_accept, _M_node, _M_dfs):
Add template parameter.
(_M_visited): Add inline keyword.
* include/bits/regex_executor.tcc (_M_handle_repeat, _M_handle_match,
_M_handle_accept, _M_node, _M_dfs): Use template parameter.
---
diff --git a/libstdc++-v3/include/bits/regex_executor.h
b/libstdc++-v3/include/bits/regex_executor.h
index
c2d1d5f0bfeee279fbd1fb138c58f45f9cdbe60e..2a9c87af59489f5202554d1052ec8355b7c5646b
100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -51,10 +51,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the function parameter %__search_mode.
*/
+ enum class _Search_mode : unsigned char { _Bfs = 0, _Dfs = 1 };
+
template<typename _BiIter, typename _Alloc, typename _TraitsT>
class _Executor
{
- enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
enum class _Match_mode : unsigned char { _Exact, _Prefix };
public:
@@ -82,12 +83,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_M_start(_M_nfa._M_start()),
_M_visited_states(nullptr),
_M_flags(__flags),
- _M_search_mode(__use_dfs ? _Search_mode::_DFS : _Search_mode::_BFS)
+ _M_search_mode(__use_dfs ? _Search_mode::_Dfs : _Search_mode::_Bfs)
{
using namespace regex_constants;
if (__flags & match_prev_avail) // ignore not_bol and not_bow
_M_flags &= ~(match_not_bol | match_not_bow);
- if (_M_search_mode == _Search_mode::_BFS)
+ if (_M_search_mode == _Search_mode::_Bfs)
_M_visited_states = new bool[_M_nfa.size()];
}
@@ -117,13 +118,16 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_StateIdT
_M_rep_once_more(_Match_mode __match_mode, _StateIdT);
+ template<_Search_mode __search_mode>
_StateIdT
_M_handle_repeat(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_subexpr_begin(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_subexpr_end(_Match_mode, _StateIdT);
_StateIdT
@@ -138,28 +142,32 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_StateIdT
_M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_match(_Match_mode, _StateIdT);
_StateIdT
_M_handle_backref(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_accept(_Match_mode, _StateIdT);
_StateIdT
_M_handle_alternative(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_node(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_dfs(_Match_mode __match_mode, _StateIdT __start);
bool
_M_main(_Match_mode __match_mode)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if (_M_search_mode == _Search_mode::_Dfs)
return _M_main_dfs(__match_mode);
else
return _M_main_bfs(__match_mode);
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc
b/libstdc++-v3/include/bits/regex_executor.tcc
index
87d5ac68685c22bbedcf9e67f96b50b61392a701..6e4c2a238cf8e393c8ae561edb88f94bf35331c0
100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -166,7 +166,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_M_has_sol = false;
*_M_get_sol_pos() = _BiIter();
_M_cur_results = _M_results;
- _M_dfs(__match_mode, _M_start);
+ _M_dfs<_Search_mode::_Dfs>(__match_mode, _M_start);
return _M_has_sol;
}
@@ -209,7 +209,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
for (auto& __task : __old_queue)
{
_M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
- _M_dfs(__match_mode, __task.first);
+ _M_dfs<_Search_mode::_Bfs>(__match_mode, __task.first);
}
if (__match_mode == _Match_mode::_Prefix)
__ret |= _M_has_sol;
@@ -289,6 +289,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
// mean the same thing, and we need to choose the correct order under
// given greedy mode.
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -299,7 +300,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
// Greedy.
if (!__state._M_neg)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
// If it's DFS executor and already accepted, we're done.
_M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next,
_M_current);
@@ -309,7 +310,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
else // Non-greedy mode
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
{
// vice-versa.
_M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i,
@@ -335,6 +336,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -345,7 +347,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
auto& __res = _M_cur_results[__state._M_subexpr];
if (_M_nfa._M_has_backref
|| __state._M_subexpr != 0
- || _M_search_mode != _Search_mode::_DFS)
+ || __search_mode != _Search_mode::_Dfs)
_M_frames.emplace_back(_S_fopcode_restore_cur_results,
static_cast<_StateIdT>(__state._M_subexpr),
__res.first);
@@ -354,6 +356,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -364,7 +367,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
auto& __res = _M_cur_results[__state._M_subexpr];
if (_M_nfa._M_has_backref
|| __state._M_subexpr != 0
- || _M_search_mode != _Search_mode::_DFS)
+ || __search_mode != _Search_mode::_Dfs)
{
_M_frames.emplace_back(_S_fopcode_restore_cur_results,
static_cast<_StateIdT>(__state._M_subexpr),
@@ -421,6 +424,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -430,7 +434,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
const auto& __state = _M_nfa[__i];
if (_M_current == _M_end)
return _S_invalid_state_id;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
{
if (__state._M_matches(*_M_current))
{
@@ -501,7 +505,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_backref(_Match_mode, _StateIdT __i)
{
- __glibcxx_assert(_M_search_mode == _Search_mode::_DFS);
+ __glibcxx_assert(_M_search_mode == _Search_mode::_Dfs);
const auto& __state = _M_nfa[__i];
auto& __submatch = _M_cur_results[__state._M_backref_index];
@@ -525,13 +529,14 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#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)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
{
__glibcxx_assert(!_M_has_sol);
if (__match_mode == _Match_mode::_Exact)
@@ -607,6 +612,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -615,7 +621,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
{
// 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 constexpr (__search_mode == _Search_mode::_Bfs)
if (_M_visited(__i))
return _S_invalid_state_id;
@@ -623,12 +629,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
switch (_M_nfa[__i]._M_opcode())
{
case _S_opcode_repeat:
- __next = _M_handle_repeat(__match_mode, __i); break;
+ __next = _M_handle_repeat<__search_mode>(__match_mode, __i); break;
case _S_opcode_subexpr_begin:
- __next = _M_handle_subexpr_begin(__match_mode, __i);
+ __next = _M_handle_subexpr_begin<__search_mode>(__match_mode, __i);
break;
case _S_opcode_subexpr_end:
- __next = _M_handle_subexpr_end(__match_mode, __i);
+ __next = _M_handle_subexpr_end<__search_mode>(__match_mode, __i);
break;
case _S_opcode_line_begin_assertion:
__next = _M_handle_line_begin_assertion(__match_mode, __i); break;
@@ -639,15 +645,15 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_opcode_subexpr_lookahead:
__next = _M_handle_subexpr_lookahead(__match_mode, __i); break;
case _S_opcode_match:
- __next = _M_handle_match(__match_mode, __i); break;
+ __next = _M_handle_match<__search_mode>(__match_mode, __i); break;
case _S_opcode_backref:
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
__next = _M_handle_backref(__match_mode, __i);
else
__builtin_unreachable();
break;
case _S_opcode_accept:
- __next = _M_handle_accept(__match_mode, __i); break;
+ __next = _M_handle_accept<__search_mode>(__match_mode, __i); break;
case _S_opcode_alternative:
__next = _M_handle_alternative(__match_mode, __i); break;
default:
@@ -657,6 +663,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_dfs(_Match_mode __match_mode, _StateIdT __start)
{
@@ -668,7 +675,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
// 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);
+ __next = _M_node<__search_mode>(__match_mode, __next);
if (_M_frames.empty())
break;
@@ -681,7 +688,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_fopcode_fallback_next:
if (_M_has_sol)
break;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_next:
@@ -691,7 +698,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_fopcode_fallback_rep_once_more:
if (_M_has_sol)
break;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_rep_once_more:
@@ -701,7 +708,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_fopcode_posix_alternative:
_M_frames.emplace_back(_S_fopcode_merge_sol, 0, _M_has_sol);
__next = __frame._M_state_id;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
_M_current = __frame._M_pos;
_M_has_sol = false;
break;
--
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c2d1d5f0bfeee279fbd1fb138c58f45f9cdbe60e..2a9c87af59489f5202554d1052ec8355b7c5646b 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -51,10 +51,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the function parameter %__search_mode.
*/
+ enum class _Search_mode : unsigned char { _Bfs = 0, _Dfs = 1 };
+
template<typename _BiIter, typename _Alloc, typename _TraitsT>
class _Executor
{
- enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
enum class _Match_mode : unsigned char { _Exact, _Prefix };
public:
@@ -82,12 +83,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_M_start(_M_nfa._M_start()),
_M_visited_states(nullptr),
_M_flags(__flags),
- _M_search_mode(__use_dfs ? _Search_mode::_DFS : _Search_mode::_BFS)
+ _M_search_mode(__use_dfs ? _Search_mode::_Dfs : _Search_mode::_Bfs)
{
using namespace regex_constants;
if (__flags & match_prev_avail) // ignore not_bol and not_bow
_M_flags &= ~(match_not_bol | match_not_bow);
- if (_M_search_mode == _Search_mode::_BFS)
+ if (_M_search_mode == _Search_mode::_Bfs)
_M_visited_states = new bool[_M_nfa.size()];
}
@@ -117,13 +118,16 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_StateIdT
_M_rep_once_more(_Match_mode __match_mode, _StateIdT);
+ template<_Search_mode __search_mode>
_StateIdT
_M_handle_repeat(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_subexpr_begin(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_subexpr_end(_Match_mode, _StateIdT);
_StateIdT
@@ -138,28 +142,32 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_StateIdT
_M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_match(_Match_mode, _StateIdT);
_StateIdT
_M_handle_backref(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_handle_accept(_Match_mode, _StateIdT);
_StateIdT
_M_handle_alternative(_Match_mode, _StateIdT);
- _StateIdT
+ template<_Search_mode __search_mode>
+ _StateIdT
_M_node(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_dfs(_Match_mode __match_mode, _StateIdT __start);
bool
_M_main(_Match_mode __match_mode)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if (_M_search_mode == _Search_mode::_Dfs)
return _M_main_dfs(__match_mode);
else
return _M_main_bfs(__match_mode);
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 87d5ac68685c22bbedcf9e67f96b50b61392a701..6e4c2a238cf8e393c8ae561edb88f94bf35331c0 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -166,7 +166,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_M_has_sol = false;
*_M_get_sol_pos() = _BiIter();
_M_cur_results = _M_results;
- _M_dfs(__match_mode, _M_start);
+ _M_dfs<_Search_mode::_Dfs>(__match_mode, _M_start);
return _M_has_sol;
}
@@ -209,7 +209,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
for (auto& __task : __old_queue)
{
_M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
- _M_dfs(__match_mode, __task.first);
+ _M_dfs<_Search_mode::_Bfs>(__match_mode, __task.first);
}
if (__match_mode == _Match_mode::_Prefix)
__ret |= _M_has_sol;
@@ -289,6 +289,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
// mean the same thing, and we need to choose the correct order under
// given greedy mode.
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -299,7 +300,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
// Greedy.
if (!__state._M_neg)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
// If it's DFS executor and already accepted, we're done.
_M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next,
_M_current);
@@ -309,7 +310,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
else // Non-greedy mode
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
{
// vice-versa.
_M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i,
@@ -335,6 +336,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -345,7 +347,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
auto& __res = _M_cur_results[__state._M_subexpr];
if (_M_nfa._M_has_backref
|| __state._M_subexpr != 0
- || _M_search_mode != _Search_mode::_DFS)
+ || __search_mode != _Search_mode::_Dfs)
_M_frames.emplace_back(_S_fopcode_restore_cur_results,
static_cast<_StateIdT>(__state._M_subexpr),
__res.first);
@@ -354,6 +356,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -364,7 +367,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
auto& __res = _M_cur_results[__state._M_subexpr];
if (_M_nfa._M_has_backref
|| __state._M_subexpr != 0
- || _M_search_mode != _Search_mode::_DFS)
+ || __search_mode != _Search_mode::_Dfs)
{
_M_frames.emplace_back(_S_fopcode_restore_cur_results,
static_cast<_StateIdT>(__state._M_subexpr),
@@ -421,6 +424,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -430,7 +434,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
const auto& __state = _M_nfa[__i];
if (_M_current == _M_end)
return _S_invalid_state_id;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
{
if (__state._M_matches(*_M_current))
{
@@ -501,7 +505,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_backref(_Match_mode, _StateIdT __i)
{
- __glibcxx_assert(_M_search_mode == _Search_mode::_DFS);
+ __glibcxx_assert(_M_search_mode == _Search_mode::_Dfs);
const auto& __state = _M_nfa[__i];
auto& __submatch = _M_cur_results[__state._M_backref_index];
@@ -525,13 +529,14 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#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)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
{
__glibcxx_assert(!_M_has_sol);
if (__match_mode == _Match_mode::_Exact)
@@ -607,6 +612,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
@@ -615,7 +621,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
{
// 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 constexpr (__search_mode == _Search_mode::_Bfs)
if (_M_visited(__i))
return _S_invalid_state_id;
@@ -623,12 +629,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
switch (_M_nfa[__i]._M_opcode())
{
case _S_opcode_repeat:
- __next = _M_handle_repeat(__match_mode, __i); break;
+ __next = _M_handle_repeat<__search_mode>(__match_mode, __i); break;
case _S_opcode_subexpr_begin:
- __next = _M_handle_subexpr_begin(__match_mode, __i);
+ __next = _M_handle_subexpr_begin<__search_mode>(__match_mode, __i);
break;
case _S_opcode_subexpr_end:
- __next = _M_handle_subexpr_end(__match_mode, __i);
+ __next = _M_handle_subexpr_end<__search_mode>(__match_mode, __i);
break;
case _S_opcode_line_begin_assertion:
__next = _M_handle_line_begin_assertion(__match_mode, __i); break;
@@ -639,15 +645,15 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_opcode_subexpr_lookahead:
__next = _M_handle_subexpr_lookahead(__match_mode, __i); break;
case _S_opcode_match:
- __next = _M_handle_match(__match_mode, __i); break;
+ __next = _M_handle_match<__search_mode>(__match_mode, __i); break;
case _S_opcode_backref:
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
__next = _M_handle_backref(__match_mode, __i);
else
__builtin_unreachable();
break;
case _S_opcode_accept:
- __next = _M_handle_accept(__match_mode, __i); break;
+ __next = _M_handle_accept<__search_mode>(__match_mode, __i); break;
case _S_opcode_alternative:
__next = _M_handle_alternative(__match_mode, __i); break;
default:
@@ -657,6 +663,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_dfs(_Match_mode __match_mode, _StateIdT __start)
{
@@ -668,7 +675,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
// 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);
+ __next = _M_node<__search_mode>(__match_mode, __next);
if (_M_frames.empty())
break;
@@ -681,7 +688,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_fopcode_fallback_next:
if (_M_has_sol)
break;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_next:
@@ -691,7 +698,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_fopcode_fallback_rep_once_more:
if (_M_has_sol)
break;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_rep_once_more:
@@ -701,7 +708,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
case _S_fopcode_posix_alternative:
_M_frames.emplace_back(_S_fopcode_merge_sol, 0, _M_has_sol);
__next = __frame._M_state_id;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_Dfs)
_M_current = __frame._M_pos;
_M_has_sol = false;
break;
