libstdc++: Improve fully dynamic extents in mdspan.

In mdspan related code, for extents with no static extents, i.e. only
dynamic extents, the following simplifications can be made:

  - The array of dynamic extents has size rank.
  - The two arrays dynamic-index and dynamic-index-inv become
  trivial, e.g. k[i] == i.
  - All elements of the arrays __{fwd,rev}_partial_prods are 1.

This commits eliminates the arrays for dynamic-index, dynamic-index-inv
and __{fwd,rev}_partial_prods. It also removes the indirection k[i] == i
from the source code, which isn't as relevant because the optimizer is
(often) capable of eliminating the indirection.

To check if it's working we look at:

  using E2 = std::extents<int, dyn, dyn, dyn, dyn>;

  int stride_left_E2(const std::layout_left::mapping<E2>& m, size_t r)
  { return m.stride(r); }

which generates the following

  0000000000000190 <stride_left_E2>:
  190:  48 c1 e6 02            shl    rsi,0x2
  194:  74 22                  je     1b8 <stride_left_E2+0x28>
  196:  48 01 fe               add    rsi,rdi
  199:  b8 01 00 00 00         mov    eax,0x1
  19e:  66 90                  xchg   ax,ax
  1a0:  48 63 17               movsxd rdx,DWORD PTR [rdi]
  1a3:  48 83 c7 04            add    rdi,0x4
  1a7:  48 0f af c2            imul   rax,rdx
  1ab:  48 39 fe               cmp    rsi,rdi
  1ae:  75 f0                  jne    1a0 <stride_left_E2+0x10>
  1b0:  c3                     ret
  1b1:  0f 1f 80 00 00 00 00   nop    DWORD PTR [rax+0x0]
  1b8:  b8 01 00 00 00         mov    eax,0x1
  1bd:  c3                     ret

We see that:

  - There's no code to load the partial product of static extents.
  - There's no indirection D[k[i]], it's just D[i] (as before).

On a test file which computes both mapping::stride(r) and
mapping::required_span_size, we check for static storage with

  objdump -h

we don't see the NTTP _Extents, anything (anymore) related to
_StaticExtents, __fwd_partial_prods or __rev_partial_prods. We also
check that the size of the reference object file (described three
commits prior) reduced by a few percent from 41.9kB to 39.4kB.

libstdc++-v3/ChangeLog:

	* include/std/mdspan (__mdspan::__all_dynamic): New function.
	(__mdspan::_StaticExtents::_S_dynamic_index): Convert to method.
	(__mdspan::_StaticExtents::_S_dynamic_index_inv): Ditto.
	(__mdspan::_StaticExtents): New specialization for fully dynamic
	extents.
	(__mdspan::__fwd_prod): New constexpr if branch to avoid
	instantiating __fwd_partial_prods.
	(__mdspan::__rev_prod): Ditto.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>

1 files changed, 53 insertions, 10 deletions

diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan
index 3cbf922..d98b91d 100644
--- a/libstdc++-v3/include/std/mdspan
+++ b/libstdc++-v3/include/std/mdspan
@@ -49,6 +49,15 @@ namespace std _GLIBCXX_VISIBILITY(default)
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
   namespace __mdspan
   {
+    consteval bool
+    __all_dynamic(std::span<const size_t> __extents)
+    {
+      for(auto __ext : __extents)
+	if (__ext != dynamic_extent)
+	  return false;
+      return true;
+    }
+
     template<array _Extents>
       class _StaticExtents
       {
@@ -59,13 +68,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	static constexpr size_t _S_rank = _Extents.size();
 
-	// For __r in [0, _S_rank], _S_dynamic_index[__r] is the number
+	// For __r in [0, _S_rank], _S_dynamic_index(__r) is the number
 	// of dynamic extents up to (and not including) __r.
 	//
 	// If __r is the index of a dynamic extent, then
 	// _S_dynamic_index[__r] is the index of that extent in
 	// _M_dyn_exts.
-	static constexpr auto _S_dynamic_index = [] consteval
+	static constexpr size_t
+	_S_dynamic_index(size_t __r) noexcept
+	{ return _S_dynamic_index_data[__r]; }
+
+	static constexpr auto _S_dynamic_index_data = [] consteval
 	{
 	  array<size_t, _S_rank+1> __ret;
 	  size_t __dyn = 0;
@@ -78,11 +91,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return __ret;
 	}();
 
-	static constexpr size_t _S_rank_dynamic = _S_dynamic_index[_S_rank];
+	static constexpr size_t _S_rank_dynamic = _S_dynamic_index(_S_rank);
 
-	// For __r in [0, _S_rank_dynamic), _S_dynamic_index_inv[__r] is the
+	// For __r in [0, _S_rank_dynamic), _S_dynamic_index_inv(__r) is the
 	// index of the __r-th dynamic extent in _Extents.
-	static constexpr auto _S_dynamic_index_inv = [] consteval
+	static constexpr size_t
+	_S_dynamic_index_inv(size_t __r) noexcept
+	{ return _S_dynamic_index_inv_data[__r]; }
+
+	static constexpr auto _S_dynamic_index_inv_data = [] consteval
 	{
 	  array<size_t, _S_rank_dynamic> __ret;
 	  for (size_t __i = 0, __r = 0; __i < _S_rank; ++__i)
@@ -96,6 +113,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{ return _Extents[__r]; }
       };
 
+    template<array _Extents>
+      requires (__all_dynamic<_Extents>())
+      class _StaticExtents<_Extents>
+      {
+      public:
+	static constexpr size_t _S_rank = _Extents.size();
+
+	static constexpr size_t
+	_S_dynamic_index(size_t __r) noexcept
+	{ return __r; }
+
+	static constexpr size_t _S_rank_dynamic = _S_rank;
+
+	static constexpr size_t
+	_S_dynamic_index_inv(size_t __k) noexcept
+	{ return __k; }
+
+	static constexpr size_t
+	_S_static_extent(size_t) noexcept
+	{ return dynamic_extent; }
+      };
+
     template<typename _IndexType, array _Extents>
       class _ExtentsStorage : public _StaticExtents<_Extents>
       {
@@ -107,6 +146,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	using _S_base::_S_rank_dynamic;
 	using _S_base::_S_dynamic_index;
 	using _S_base::_S_dynamic_index_inv;
+	using _S_base::_S_static_extent;
 
 	template<typename _OIndexType>
 	  static constexpr _IndexType
@@ -118,7 +158,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  auto __se = _Extents[__r];
 	  if (__se == dynamic_extent)
-	    return _M_dyn_exts[_S_dynamic_index[__r]];
+	    return _M_dyn_exts[_S_dynamic_index(__r)];
 	  else
 	    return __se;
 	}
@@ -144,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      {
 		size_t __di = __i;
 		if constexpr (_OtherRank != _S_rank_dynamic)
-		  __di = _S_dynamic_index_inv[__i];
+		  __di = _S_dynamic_index_inv(__i);
 		_M_dyn_exts[__i] = _S_int_cast(__get_extent(__di));
 	      }
 	  }
@@ -178,8 +218,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_dynamic_extents(size_t __begin, size_t __end) const noexcept
 	requires (_Extents.size() > 0)
 	{
-	  return {_M_dyn_exts + _S_dynamic_index[__begin],
-		  _M_dyn_exts + _S_dynamic_index[__end]};
+	  return {_M_dyn_exts + _S_dynamic_index(__begin),
+		  _M_dyn_exts + _S_dynamic_index(__end)};
 	}
 
       private:
@@ -252,7 +292,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static_assert(
 	  (__mdspan::__valid_static_extent<_Extents, _IndexType> && ...),
 	  "Extents must either be dynamic or representable as IndexType");
-
     public:
       using index_type = _IndexType;
       using size_type = make_unsigned_t<index_type>;
@@ -430,6 +469,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return 1;
 	else if constexpr (__rank == 2)
 	  return __r == 0 ? 1 : __exts.extent(0);
+	else if constexpr (__all_dynamic(__sta_exts))
+	  return __extents_prod(__exts, 1, 0, __r);
 	else
 	  {
 	    size_t __sta_prod = __fwd_partial_prods<__sta_exts>[__r];
@@ -448,6 +489,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return 1;
 	else if constexpr (__rank == 2)
 	  return __r == 0 ? __exts.extent(1) : 1;
+	else if constexpr (__all_dynamic(__sta_exts))
+	  return __extents_prod(__exts, 1, __r + 1, __rank);
 	else
 	  {
 	    size_t __sta_prod = __rev_partial_prods<__sta_exts>[__r];