[PATCH][Bug libstdc++/70303] Value-initialized debug iterators

2021-01-31 Thread François Dumont via Gcc-patches 
After the debug issue has been fixed in PR 98466 the problem was not in 
the debug iterator implementation itself but in the deque iterator 
operator- implementation.


    libstdc++: Make deque iterator operator- usable with value-init 
iterators


    N3644 implies that operator- can be used on value-init iterators. 
We now return
    0 if both iterators are value initialized. If only one is value 
initialized we
    keep the UB by returning the result of a normal computation which 
is an unexpected

    value.

    libstdc++/ChangeLog:

    PR libstdc++/70303
    * include/bits/stl_deque.h 
(std::deque<>::operator-(iterator, iterator)):

    Return 0 if both iterators are value-initialized.
    * testsuite/23_containers/deque/70303.cc: New test.
    * testsuite/23_containers/vector/70303.cc: New test.

Tested under Linux x86_64, ok to commit ?

François

diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index d41c27717a3..04b70b77621 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -352,9 +352,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   friend difference_type
   operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
   {
-	return difference_type(_S_buffer_size())
-	  * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-	  + (__y._M_last - __y._M_cur);
+	if (__builtin_expect(__x._M_node || __y._M_node, true))
+	  return difference_type(_S_buffer_size())
+	* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
+	+ (__y._M_last - __y._M_cur);
+
+	return 0;
   }
 
   // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -366,9 +369,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	operator-(const _Self& __x,
 		  const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
 	{
-	  return difference_type(_S_buffer_size())
-	* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-	+ (__y._M_last - __y._M_cur);
+	  if (__builtin_expect(__x._M_node || __y._M_node, true))
+	return difference_type(_S_buffer_size())
+	  * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
+	  + (__y._M_last - __y._M_cur);
+
+	  return 0;
 	}
 
   friend _Self
diff --git a/libstdc++-v3/testsuite/23_containers/deque/70303.cc b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
new file mode 100644
index 000..e0e63694170
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// .
+
+// { dg-do run }
+
+#include 
+#include 
+
+// PR libstdc++/70303
+
+void test01()
+{
+  typedef typename std::deque::iterator It;
+  It it = It();
+  VERIFY(it == it);
+  VERIFY(!(it != it));
+  VERIFY(it - it == 0);
+  VERIFY(!(it < it));
+  VERIFY(!(it > it));
+  VERIFY(it <= it);
+  VERIFY(it >= it);
+
+  typedef typename std::deque::const_iterator CIt;
+  CIt cit = CIt();
+  VERIFY(cit == cit);
+  VERIFY(!(cit != cit));
+  VERIFY(cit - cit == 0);
+  VERIFY(!(cit < cit));
+  VERIFY(!(cit > cit));
+  VERIFY(cit <= cit);
+  VERIFY(cit >= cit);
+
+  VERIFY(it == cit);
+  VERIFY(!(it != cit));
+  VERIFY(cit == it);
+  VERIFY(!(cit != it));
+  VERIFY(it - cit == 0);
+  VERIFY(cit - it == 0);
+  VERIFY(!(it < cit));
+  VERIFY(!(it > cit));
+  VERIFY(it <= cit);
+  VERIFY(it >= cit);
+  VERIFY(!(cit < it));
+  VERIFY(!(cit > it));
+  VERIFY(cit <= it);
+  VERIFY(cit >= it);
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/70303.cc b/libstdc++-v3/testsuite/23_containers/vector/70303.cc
new file mode 100644
index 000..af18a0503d8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/70303.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty o

Re: [PATCH][Bug libstdc++/70303] Value-initialized debug iterators

2021-02-01 Thread Jonathan Wakely via Gcc-patches 

On 31/01/21 16:59 +0100, François Dumont via Libstdc++ wrote:
After the debug issue has been fixed in PR 98466 the problem was not 
in the debug iterator implementation itself but in the deque iterator 
operator- implementation.


    libstdc++: Make deque iterator operator- usable with value-init 
iterators


    N3644 implies that operator- can be used on value-init iterators. 
We now return
    0 if both iterators are value initialized. If only one is value 
initialized we
    keep the UB by returning the result of a normal computation which 
is an unexpected

    value.

    libstdc++/ChangeLog:

    PR libstdc++/70303
    * include/bits/stl_deque.h 
(std::deque<>::operator-(iterator, iterator)):

    Return 0 if both iterators are value-initialized.
    * testsuite/23_containers/deque/70303.cc: New test.
    * testsuite/23_containers/vector/70303.cc: New test.

Tested under Linux x86_64, ok to commit ?


OK.

I don't like adding the branch there though. Even with the
__builtin_expect it causes worse code to be generated than the
original.

This would be branchless, but a bit harder to understand:

return difference_type(__x._S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node == __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

Please commit the fix and we can think about it later.


François




diff --git a/libstdc++-v3/include/bits/stl_deque.h 
b/libstdc++-v3/include/bits/stl_deque.h
index d41c27717a3..04b70b77621 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -352,9 +352,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  friend difference_type
  operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
  {
-   return difference_type(_S_buffer_size())
- * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
- + (__y._M_last - __y._M_cur);
+   if (__builtin_expect(__x._M_node || __y._M_node, true))
+ return difference_type(_S_buffer_size())
+   * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
+   + (__y._M_last - __y._M_cur);
+
+   return 0;
  }

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -366,9 +369,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
operator-(const _Self& __x,
  const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 
_GLIBCXX_NOEXCEPT
{
- return difference_type(_S_buffer_size())
-   * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-   + (__y._M_last - __y._M_cur);
+ if (__builtin_expect(__x._M_node || __y._M_node, true))
+   return difference_type(_S_buffer_size())
+ * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
+ + (__y._M_last - __y._M_cur);
+
+ return 0;
}

  friend _Self
diff --git a/libstdc++-v3/testsuite/23_containers/deque/70303.cc 
b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
new file mode 100644
index 000..e0e63694170
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// .
+
+// { dg-do run }
+
+#include 
+#include 
+
+// PR libstdc++/70303
+
+void test01()
+{
+  typedef typename std::deque::iterator It;
+  It it = It();
+  VERIFY(it == it);
+  VERIFY(!(it != it));
+  VERIFY(it - it == 0);
+  VERIFY(!(it < it));
+  VERIFY(!(it > it));
+  VERIFY(it <= it);
+  VERIFY(it >= it);
+
+  typedef typename std::deque::const_iterator CIt;
+  CIt cit = CIt();
+  VERIFY(cit == cit);
+  VERIFY(!(cit != cit));
+  VERIFY(cit - cit == 0);
+  VERIFY(!(cit < cit));
+  VERIFY(!(cit > cit));
+  VERIFY(cit <= cit);
+  VERIFY(cit >= cit);
+
+  VERIFY(it == cit);
+  VERIFY(!(it != cit));
+  VERIFY(cit == it);
+  VERIFY(!(cit != it));
+  VERIFY(it - cit == 0);
+  VERIFY(cit - it == 0);
+  VERIFY(!(it < cit));
+  VERIFY(!(it > cit));
+  VERIFY(it <= cit);
+  VERIFY(it >= cit);
+  VERIFY(!(cit < it));
+  VERIFY(!(cit > it));
+  VERIFY(cit <= it);
+  VERIFY(cit >= it);
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/70303.cc 
b/libstdc++-v3/testsuite/23_containers/vector/70303.

Re: [PATCH][Bug libstdc++/70303] Value-initialized debug iterators

2021-02-01 Thread François Dumont via Gcc-patches 

On 01/02/21 6:43 pm, Jonathan Wakely wrote:

On 31/01/21 16:59 +0100, François Dumont via Libstdc++ wrote:
After the debug issue has been fixed in PR 98466 the problem was not 
in the debug iterator implementation itself but in the deque iterator 
operator- implementation.


    libstdc++: Make deque iterator operator- usable with value-init 
iterators


    N3644 implies that operator- can be used on value-init iterators. 
We now return
    0 if both iterators are value initialized. If only one is value 
initialized we
    keep the UB by returning the result of a normal computation which 
is an unexpected

    value.

    libstdc++/ChangeLog:

    PR libstdc++/70303
    * include/bits/stl_deque.h 
(std::deque<>::operator-(iterator, iterator)):

    Return 0 if both iterators are value-initialized.
    * testsuite/23_containers/deque/70303.cc: New test.
    * testsuite/23_containers/vector/70303.cc: New test.

Tested under Linux x86_64, ok to commit ?


OK.

I don't like adding the branch there though. Even with the
__builtin_expect it causes worse code to be generated than the
original.

This would be branchless, but a bit harder to understand:

    return difference_type(__x._S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node == __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

Please commit the fix and we can think about it later.


I do not think this work because for value-init iterators we have 
__x._M_node == __y._M_node == nullptr so the diff would give 
-_S_buffer_size().


But I got the idear, I'll prepare the patch.




François



diff --git a/libstdc++-v3/include/bits/stl_deque.h 
b/libstdc++-v3/include/bits/stl_deque.h

index d41c27717a3..04b70b77621 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -352,9 +352,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  friend difference_type
  operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
  {
-    return difference_type(_S_buffer_size())
-  * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-  + (__y._M_last - __y._M_cur);
+    if (__builtin_expect(__x._M_node || __y._M_node, true))
+  return difference_type(_S_buffer_size())
+    * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
+    + (__y._M_last - __y._M_cur);
+
+    return 0;
  }

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -366,9 +369,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
operator-(const _Self& __x,
  const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 
_GLIBCXX_NOEXCEPT

{
-  return difference_type(_S_buffer_size())
-    * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-    + (__y._M_last - __y._M_cur);
+  if (__builtin_expect(__x._M_node || __y._M_node, true))
+    return difference_type(_S_buffer_size())
+  * (__x._M_node - __y._M_node - 1) + (__x._M_cur - 
__x._M_first)

+  + (__y._M_last - __y._M_cur);
+
+  return 0;
}

  friend _Self
diff --git a/libstdc++-v3/testsuite/23_containers/deque/70303.cc 
b/libstdc++-v3/testsuite/23_containers/deque/70303.cc

new file mode 100644
index 000..e0e63694170
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License 
along

+// with this library; see the file COPYING3.  If not see
+// .
+
+// { dg-do run }
+
+#include 
+#include 
+
+// PR libstdc++/70303
+
+void test01()
+{
+  typedef typename std::deque::iterator It;
+  It it = It();
+  VERIFY(it == it);
+  VERIFY(!(it != it));
+  VERIFY(it - it == 0);
+  VERIFY(!(it < it));
+  VERIFY(!(it > it));
+  VERIFY(it <= it);
+  VERIFY(it >= it);
+
+  typedef typename std::deque::const_iterator CIt;
+  CIt cit = CIt();
+  VERIFY(cit == cit);
+  VERIFY(!(cit != cit));
+  VERIFY(cit - cit == 0);
+  VERIFY(!(cit < cit));
+  VERIFY(!(cit > cit));
+  VERIFY(cit <= cit);
+  VERIFY(cit >= cit);
+
+  VERIFY(it == cit);
+  VERIFY(!(it != cit));
+  VERIFY(cit == it);
+  VERIFY(!(cit != it));
+  VERIFY(it - cit == 0);
+  VERIFY(cit - it == 0);
+  VERIFY(!(it < cit));
+  VERIFY(!(it > cit));
+  VERIFY(it <= cit);
+  VERIFY(it >= cit);
+  VERIFY(!(cit < it));
+  VERIFY(!(cit > it));
+  VERIFY(cit <= it);
+  VERIF

Re: [PATCH][Bug libstdc++/70303] Value-initialized debug iterators

2021-02-01 Thread Jonathan Wakely via Gcc-patches 

On 01/02/21 19:30 +0100, François Dumont via Libstdc++ wrote:

On 01/02/21 6:43 pm, Jonathan Wakely wrote:

On 31/01/21 16:59 +0100, François Dumont via Libstdc++ wrote:
After the debug issue has been fixed in PR 98466 the problem was 
not in the debug iterator implementation itself but in the deque 
iterator operator- implementation.


    libstdc++: Make deque iterator operator- usable with 
value-init iterators


    N3644 implies that operator- can be used on value-init 
iterators. We now return
    0 if both iterators are value initialized. If only one is 
value initialized we
    keep the UB by returning the result of a normal computation 
which is an unexpected

    value.

    libstdc++/ChangeLog:

    PR libstdc++/70303
    * include/bits/stl_deque.h 
(std::deque<>::operator-(iterator, iterator)):

    Return 0 if both iterators are value-initialized.
    * testsuite/23_containers/deque/70303.cc: New test.
    * testsuite/23_containers/vector/70303.cc: New test.

Tested under Linux x86_64, ok to commit ?


OK.

I don't like adding the branch there though. Even with the
__builtin_expect it causes worse code to be generated than the
original.

This would be branchless, but a bit harder to understand:

    return difference_type(__x._S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node == __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

Please commit the fix and we can think about it later.


I do not think this work because for value-init iterators we have 
__x._M_node == __y._M_node == nullptr so the diff would give 
-_S_buffer_size().


But I got the idear, I'll prepare the patch.


Yeah, I just came back to the computer to say that it's wrong. But
maybe this:

    return difference_type(_S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node && __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

For value-init'd iterators we'd get _S_buffer_size() * 0 + 0 - 0

We could even just use int(__x._M_node != 0) because if one is null
and the other isn't, it's UB anyway.

Re: [PATCH][Bug libstdc++/70303] Value-initialized debug iterators

2021-02-08 Thread François Dumont via Gcc-patches 

On 01/02/21 8:09 pm, Jonathan Wakely wrote:

On 01/02/21 19:30 +0100, François Dumont via Libstdc++ wrote:

On 01/02/21 6:43 pm, Jonathan Wakely wrote:

On 31/01/21 16:59 +0100, François Dumont via Libstdc++ wrote:
After the debug issue has been fixed in PR 98466 the problem was 
not in the debug iterator implementation itself but in the deque 
iterator operator- implementation.


    libstdc++: Make deque iterator operator- usable with value-init 
iterators


    N3644 implies that operator- can be used on value-init 
iterators. We now return
    0 if both iterators are value initialized. If only one is value 
initialized we
    keep the UB by returning the result of a normal computation 
which is an unexpected

    value.

    libstdc++/ChangeLog:

    PR libstdc++/70303
    * include/bits/stl_deque.h 
(std::deque<>::operator-(iterator, iterator)):

    Return 0 if both iterators are value-initialized.
    * testsuite/23_containers/deque/70303.cc: New test.
    * testsuite/23_containers/vector/70303.cc: New test.

Tested under Linux x86_64, ok to commit ?


OK.

I don't like adding the branch there though. Even with the
__builtin_expect it causes worse code to be generated than the
original.

This would be branchless, but a bit harder to understand:

    return difference_type(__x._S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node == __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

Please commit the fix and we can think about it later.


I do not think this work because for value-init iterators we have 
__x._M_node == __y._M_node == nullptr so the diff would give 
-_S_buffer_size().


But I got the idear, I'll prepare the patch.


Yeah, I just came back to the computer to say that it's wrong. But
maybe this:

    return difference_type(_S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node && __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

For value-init'd iterators we'd get _S_buffer_size() * 0 + 0 - 0

We could even just use int(__x._M_node != 0) because if one is null
and the other isn't, it's UB anyway.


This is what I've tested with success. As it is a recent kind of 
regression you might want to consider it now.


    libstdc++: Remove execution branch in deque iterator operator-

    libstdc++-v3/ChangeLog:

    * include/bits/stl_deque.h
    (std::operator-(deque::iterator, deque::iterator)): Replace 
if/then with

    a null pointer test.

Ok to commit ?

François

diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 04b70b77621..8bba7a3740f 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -352,12 +352,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   friend difference_type
   operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
   {
-	if (__builtin_expect(__x._M_node || __y._M_node, true))
-	  return difference_type(_S_buffer_size())
-	* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-	+ (__y._M_last - __y._M_cur);
-
-	return 0;
+	return difference_type(_S_buffer_size())
+	  * (__x._M_node - __y._M_node - int(__x._M_node != 0))
+	  + (__x._M_cur - __x._M_first)
+	  + (__y._M_last - __y._M_cur);
   }
 
   // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -369,12 +367,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	operator-(const _Self& __x,
 		  const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
 	{
-	  if (__builtin_expect(__x._M_node || __y._M_node, true))
-	return difference_type(_S_buffer_size())
-	  * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-	  + (__y._M_last - __y._M_cur);
-
-	  return 0;
+	  return difference_type(_S_buffer_size())
+	* (__x._M_node - __y._M_node - int(__x._M_node != 0))
+	+ (__x._M_cur - __x._M_first)
+	+ (__y._M_last - __y._M_cur);
 	}
 
   friend _Self

Re: [PATCH][Bug libstdc++/70303] Value-initialized debug iterators

2021-02-09 Thread Jonathan Wakely via Gcc-patches 

On 08/02/21 22:27 +0100, François Dumont wrote:

On 01/02/21 8:09 pm, Jonathan Wakely wrote:

On 01/02/21 19:30 +0100, François Dumont via Libstdc++ wrote:

On 01/02/21 6:43 pm, Jonathan Wakely wrote:

On 31/01/21 16:59 +0100, François Dumont via Libstdc++ wrote:
After the debug issue has been fixed in PR 98466 the problem 
was not in the debug iterator implementation itself but in the 
deque iterator operator- implementation.


    libstdc++: Make deque iterator operator- usable with 
value-init iterators


    N3644 implies that operator- can be used on value-init 
iterators. We now return
    0 if both iterators are value initialized. If only one is 
value initialized we
    keep the UB by returning the result of a normal 
computation which is an unexpected

    value.

    libstdc++/ChangeLog:

    PR libstdc++/70303
    * include/bits/stl_deque.h 
(std::deque<>::operator-(iterator, iterator)):

    Return 0 if both iterators are value-initialized.
    * testsuite/23_containers/deque/70303.cc: New test.
    * testsuite/23_containers/vector/70303.cc: New test.

Tested under Linux x86_64, ok to commit ?


OK.

I don't like adding the branch there though. Even with the
__builtin_expect it causes worse code to be generated than the
original.

This would be branchless, but a bit harder to understand:

    return difference_type(__x._S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node == __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

Please commit the fix and we can think about it later.


I do not think this work because for value-init iterators we have 
__x._M_node == __y._M_node == nullptr so the diff would give 
-_S_buffer_size().


But I got the idear, I'll prepare the patch.


Yeah, I just came back to the computer to say that it's wrong. But
maybe this:

    return difference_type(_S_buffer_size())
  * (__x._M_node - __y._M_node - int(__x._M_node && __y._M_node))
  + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

For value-init'd iterators we'd get _S_buffer_size() * 0 + 0 - 0

We could even just use int(__x._M_node != 0) because if one is null
and the other isn't, it's UB anyway.


This is what I've tested with success. As it is a recent kind of 
regression you might want to consider it now.


    libstdc++: Remove execution branch in deque iterator operator-

    libstdc++-v3/ChangeLog:

    * include/bits/stl_deque.h
    (std::operator-(deque::iterator, deque::iterator)): 
Replace if/then with

    a null pointer test.

Ok to commit ?


OK, thanks!



François




diff --git a/libstdc++-v3/include/bits/stl_deque.h 
b/libstdc++-v3/include/bits/stl_deque.h
index 04b70b77621..8bba7a3740f 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -352,12 +352,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  friend difference_type
  operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
  {
-   if (__builtin_expect(__x._M_node || __y._M_node, true))
- return difference_type(_S_buffer_size())
-   * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
-   + (__y._M_last - __y._M_cur);
-
-   return 0;
+   return difference_type(_S_buffer_size())
+ * (__x._M_node - __y._M_node - int(__x._M_node != 0))
+ + (__x._M_cur - __x._M_first)
+ + (__y._M_last - __y._M_cur);
  }

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -369,12 +367,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
operator-(const _Self& __x,
  const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 
_GLIBCXX_NOEXCEPT
{
- if (__builtin_expect(__x._M_node || __y._M_node, true))
-   return difference_type(_S_buffer_size())
- * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
- + (__y._M_last - __y._M_cur);
-
- return 0;
+ return difference_type(_S_buffer_size())
+   * (__x._M_node - __y._M_node - int(__x._M_node != 0))
+   + (__x._M_cur - __x._M_first)
+   + (__y._M_last - __y._M_cur);
}

  friend _Self