[libstdc++] Improve M_check_len

[Jan Hubicka <hubicka@ucw.cz>]

Hi,
_M_check_len is used in vector reallocations. It computes __n + __s but does
checking for case that (__n + __s) * sizeof (Tp) would overflow ptrdiff_t.
Since we know that __s is a size of already allocated memory block if __n is
not too large, this will never happen on 64bit systems since memory is not that
large.  This patch adds __builtin_constant_p checks for this case.  This size
of fully inlined push_back function that is critical for loops that are
controlled by std::vector based stack.

With the patch to optimize std::max and to handle SRA candidates, we
fully now inline push_back with -O3 (not with -O2), however there are still
quite few silly things for example:

  //  _78 is original size of the allocated vector.

  _76 = stack$_M_end_of_storage_177 - _142;
  _77 = _76 /[ex] 8; 
  _78 = (long unsigned int) _77;
  _79 = MAX_EXPR <_78, 1>;   
  _80 = _78 + _79; // this is result of _M_check_len doubling the allocated vector size.
  if (_80 != 0)    // result will always be non-zero.  
    goto <bb 7>; [54.67%]
  else
    goto <bb 13>; [45.33%]
  
  <bb 7> [local count: 30795011]:
  if (_80 > 1152921504606846975)  // doubling succesfully allocated memmory will never get so large.
    goto <bb 8>; [10.00%]
  else
    goto <bb 11>; [90.00%]
  
  <bb 8> [local count: 3079501]:
  if (_80 > 2305843009213693951)  // I wonder if we really want to have two different throws
    goto <bb 9>; [50.00%]
  else 
    goto <bb 10>; [50.00%]
  
  <bb 9> [local count: 1539750]:
  std::__throw_bad_array_new_length ();
  
  <bb 10> [local count: 1539750]:
  std::__throw_bad_alloc ();
  
  <bb 11> [local count: 27715510]:
  _108 = _80 * 8;
  _109 = operator new (_108);

Maybe we want to add assumption that result of the function is never
greater than max_size to get rid of the two checks above.  However this
will still be recongized only after inlining and will continue confusing
inliner heuristics.

Bootstrapped/regtested x86_64-linux.  I am not too familiar with libstdc++ internals,
so would welcome comments and ideas.

libstdc++-v3/ChangeLog:

	PR tree-optimization/110287
	* include/bits/stl_vector.h: Optimize _M_check_len for constantly sized
	types and allocations.

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 70ced3d101f..3ad59fe3e2b 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1895,11 +1895,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       size_type
       _M_check_len(size_type __n, const char* __s) const
       {
-	if (max_size() - size() < __n)
-	  __throw_length_error(__N(__s));
+	// On 64bit systems vectors of small sizes can not
+	// reach overflow by growing by small sizes; before
+	// this happens, we will run out of memory.
+	if (__builtin_constant_p (sizeof (_Tp))
+	    && __builtin_constant_p (__n)
+	    && sizeof (ptrdiff_t) >= 8
+	    && __n < max_size () / 2)
+	  return size() + (std::max)(size(), __n);
+	else
+	  {
+	    if (max_size() - size() < __n)
+	      __throw_length_error(__N(__s));
 
-	const size_type __len = size() + (std::max)(size(), __n);
-	return (__len < size() || __len > max_size()) ? max_size() : __len;
+	    const size_type __len = size() + (std::max)(size(), __n);
+	    return (__len < size() || __len > max_size()) ? max_size() : __len;
+	  }
       }
 
       // Called by constructors to check initial size.