Merged revisions 184777,184779,184812,184842,184848,184853,184861,184871,184878,184895,184909,184921,184931,184950-184951,184954,184956,184970,184991-184992,185001,185023,185034,185063,185077,185087,185102,185119,185151,185164,185170,185180,185185,185189,185206,185209,185234,185237,185239,185243,185248,185275,185359-185360,185364,185366,185370,185383,185402,185405,185432,185440,185450,185457,185480,185497,185506,185513,185551,185592,185606,185626,185630-185674,185679,185681-185683,185685-185686,185690,185696-185697,185704-185706,185708,185710-185711,185713-185714,185717,185720,185723,185726,185733,185738,185740,185743,185747,185749,185755,185759-185760,185763,185766,185771,185781,185785,185794,185805,185828,185864,185877,185879,185896,185901,185905,185908-185909,185911,185916,185918,185920,185926,185929,185932,185934,185936,185939,185942,185947,185961,185964,185967,185969,185972,185979,185984,185987,185989,185991,186014,186021-186022,186025,186027,186030,186033,186036-186037,186039,186046,186048,186053,186061,186089,186096,186103,186105,186107-186108,186113,186115,186121,186124,186127,186141,186145,186152,186173,186178,186180,186188,186195-186197,186207,186214-186215,186218,186221,186232,186236,186238,186242,186249,186255,186262,186264,186266,186296,186300,186359-186360,186367,186370,186376-186377,186392,186394,186401,186404,186409,186412,186417,186424-186425,186430,186435-186436,186443,186459,186461,186473,186477,186481,186489,186500,186510,186512,186515,186517,186531-186533,186543-186544,186556,186573,186583,186589,186603,186606,186608,186611,186630,186632,186634,186636,186638,186641,186643,186648,186650-186651,186656,186661,186671,186677,186679,186684,186686,186691,186695,186698-186699,186713,186716-186717,186723,186728,186733,186740,186743,186745,186765,186767,186770,186773,186775,186779,186782,186785,186787,186792,186802,186804,186809-186810,186841-186842,186848-186849,186853,186858 via svnmerge from

svn+ssh://gcc.gnu.org/svn/gcc/branches/gcc-4_7-branch


Bugs fixed (http://gcc.gnu.org/bugzilla)

Optimizers
  52592

C
  52577, 52682, 52862, 53060

C++
  52521, 52582, 52671, 52433, 52487, 52540, 52746, 52743, 52759,
  52685, 52718, 52672, 52799, 52796, 52596, 52476, 52591, 52924,
  52942, 52822, 52824, 52699, 52465, 52292, 52380, 52689, 50303,
  50830, 38543, 53003, 52839, 53027, 53067


Fortran
  52452, 52758, 52668, 52893,

Optimizers/Codegen
  52545, 52547, 52640, 52720, 51893, 52750, 52691, 52693, 52835,
  52493, 52678, 52701, 52754, 52580, 52406, 52894, 52943, 52969,
  52939, 52891,

PPC
  50310, 52775

x86
  52736, 52698, 52932, 53020,


Other notable changes

C++
  Mangling fixes: revs 185606, 185704
  	gcc/cp/
  	* mangle.c (write_type): Handle 'auto'.
  	* init.c (build_new): Don't do auto deduction where it might
  	affect template mangling.
  	libiberty/
  	* cp-demangle.c (cplus_demangle_type): Handle 'auto'.

  	* cp-demangle.c (cplus_demangle_operators): Add li.
  	(d_unqualified_name): Handle it specially.

  C++11 changes (LWG 1310): rev 186404
  	* include/bits/forward_list.h (splice_after(const_iterator,
  	forward_list&), splice_after(const_iterator, forward_list&,
  	consst_iterator), splice_after(const_iterator, forward_list&,
  	const_iterator, const_iterator), merge(forward_list&),
  	merge(forward_list&, _Comp)): Add per C++11 as published (and
  	LWG 1310).
  	* include/debug/forward_list: Adjust.
  
  	* include/bits/forward_list.h (splice_after(const_iterator,
  	forward_list&&, const_iterator)): Only declare.
  	(_M_transfer_after): Remove.
  	(_M_splice_after(const_iterator, forward_list&&)): Change signature.
  	(splice_after(const_iterator, forward_list&&, const_iterator,
  	const_iterator)): Use the latter.
  	* include/bits/forward_list.tcc (splice_after(const_iterator,
  	forward_list&&, const_iterator)): Define here.
  	(_M_splice_after): Define, use throughout.
  
  	* include/bits/forward_list.h (insert_after(const_iterator,
  	std::initializer_list<_Tp>)): Forward to insert_after(const_iterator,
  	_InputIterator, _InputIterator).
  	* include/bits/forward_list.tcc: Remove definition.
  
  	* testsuite/23_containers/forward_list/modifiers/6.cc: New.
  	* testsuite/23_containers/forward_list/operations/1.cc: Adjust.
  
  	* testsuite/23_containers/forward_list/requirements/dr438/
  	assign_neg.cc: Adjust dg-error line number.
  	* testsuite/23_containers/forward_list/requirements/dr438/
  	insert_neg.cc: Likewise.
  	* testsuite/23_containers/forward_list/requirements/dr438/
  	constructor_1_neg.cc: Likewise.
  	* testsuite/23_containers/forward_list/requirements/dr438/
  	constructor_2_neg.cc: Likewise.



git-svn-id: https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_7-integration@186906 138bc75d-0d04-0410-961f-82ee72b054a4

24 files changed, 561 insertions, 221 deletions

diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 3d3959d58a9..0bd7d5cf305 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -1,7 +1,7 @@
 ## Makefile for the include subdirectory of the GNU C++ Standard library.
 ##
 ## Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
-## 2011
+## 2011, 2012
 ## Free Software Foundation, Inc.
 ##
 ## This file is part of the libstdc++ version 3 distribution.
@@ -1106,7 +1106,7 @@ ${host_builddir}/c++config.h: ${CONFIG_HEADER} \
 	sed -e "s,define __GLIBCXX__,define __GLIBCXX__ $$date," \
 	-e "s,define _GLIBCXX_INLINE_VERSION, define _GLIBCXX_INLINE_VERSION $$ns_version," \
 	-e "s,define _GLIBCXX_HAVE_ATTRIBUTE_VISIBILITY, define _GLIBCXX_HAVE_ATTRIBUTE_VISIBILITY $$visibility," \
-	-e "s,define _GLIBCXX_EXTERN_TEMPLATE, define _GLIBCXX_EXTERN_TEMPLATE $$externtemplate," \
+	-e "s,define _GLIBCXX_EXTERN_TEMPLATE$$, define _GLIBCXX_EXTERN_TEMPLATE $$externtemplate," \
 	-e "$$ldbl_compat" \
 	    < ${glibcxx_srcdir}/include/bits/c++config > $@ ;\
 	sed -e 's/HAVE_/_GLIBCXX_HAVE_/g' \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index ab7efdc011e..23caf106192 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -1498,7 +1498,7 @@ ${host_builddir}/c++config.h: ${CONFIG_HEADER} \
 	sed -e "s,define __GLIBCXX__,define __GLIBCXX__ $$date," \
 	-e "s,define _GLIBCXX_INLINE_VERSION, define _GLIBCXX_INLINE_VERSION $$ns_version," \
 	-e "s,define _GLIBCXX_HAVE_ATTRIBUTE_VISIBILITY, define _GLIBCXX_HAVE_ATTRIBUTE_VISIBILITY $$visibility," \
-	-e "s,define _GLIBCXX_EXTERN_TEMPLATE, define _GLIBCXX_EXTERN_TEMPLATE $$externtemplate," \
+	-e "s,define _GLIBCXX_EXTERN_TEMPLATE$$, define _GLIBCXX_EXTERN_TEMPLATE $$externtemplate," \
 	-e "$$ldbl_compat" \
 	    < ${glibcxx_srcdir}/include/bits/c++config > $@ ;\
 	sed -e 's/HAVE_/_GLIBCXX_HAVE_/g' \
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 5b56875b493..fcece60c8bb 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1,7 +1,7 @@
 // Deque implementation (out of line) -*- C++ -*-
 
 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
-// 2009, 2010, 2011
+// 2009, 2010, 2011, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -175,12 +175,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       {
 	if (__position._M_cur == this->_M_impl._M_start._M_cur)
 	  {
-	    push_front(std::forward<_Args>(__args)...);
+	    emplace_front(std::forward<_Args>(__args)...);
 	    return this->_M_impl._M_start;
 	  }
 	else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 	  {
-	    push_back(std::forward<_Args>(__args)...);
+	    emplace_back(std::forward<_Args>(__args)...);
 	    iterator __tmp = this->_M_impl._M_finish;
 	    --__tmp;
 	    return __tmp;
diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h
index 0fc8323767b..6d62f1e2278 100644
--- a/libstdc++-v3/include/bits/forward_list.h
+++ b/libstdc++-v3/include/bits/forward_list.h
@@ -1,6 +1,6 @@
 // <forward_list.h> -*- C++ -*-
 
-// Copyright (C) 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2008, 2009, 2010, 2011, 2012 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
@@ -53,15 +53,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _Fwd_list_node_base* _M_next;
 
     _Fwd_list_node_base*
-    _M_transfer_after(_Fwd_list_node_base* __begin)
-    {
-      _Fwd_list_node_base* __end = __begin;
-      while (__end && __end->_M_next)
-	__end = __end->_M_next;
-      return _M_transfer_after(__begin, __end);
-    }
-
-    _Fwd_list_node_base*
     _M_transfer_after(_Fwd_list_node_base* __begin,
 		      _Fwd_list_node_base* __end)
     {
@@ -606,8 +597,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  in the range [@a __first,@a __last).
        *
        *  Note that the assignment completely changes the %forward_list and
-       *  that the resulting %forward_list's size is the same as the number
-       *  of elements assigned.  Old data may be lost.
+       *  that the number of elements of the resulting %forward_list's is the
+       *  same as the number of elements assigned.  Old data is lost.
        */
       template<typename _InputIterator>
         void
@@ -622,10 +613,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @param  __n  Number of elements to be assigned.
        *  @param  __val  Value to be assigned.
        *
-       *  This function fills a %forward_list with @a __n copies of the given
-       *  value.  Note that the assignment completely changes the
-       *  %forward_list and that the resulting %forward_list's size is the
-       *  same as the number of elements assigned.  Old data may be lost.
+       *  This function fills a %forward_list with @a __n copies of the
+       *  given value.  Note that the assignment completely changes the
+       *  %forward_list, and that the resulting %forward_list has __n
+       *  elements.  Old data is lost.
        */
       void
       assign(size_type __n, const _Tp& __val)
@@ -744,7 +735,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return this->_M_impl._M_head._M_next == 0; }
 
       /**
-       *  Returns the largest possible size of %forward_list.
+       *  Returns the largest possible number of elements of %forward_list.
        */
       size_type
       max_size() const noexcept
@@ -926,7 +917,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  does not invalidate iterators and references.
        */
       iterator
-      insert_after(const_iterator __pos, std::initializer_list<_Tp> __il);
+      insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
+      { return insert_after(__pos, __il.begin(), __il.end()); }
 
       /**
        *  @brief  Removes the element pointed to by the iterator following
@@ -997,9 +989,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *
        *  This function will %resize the %forward_list to the specified
        *  number of elements.  If the number is smaller than the
-       *  %forward_list's current size the %forward_list is truncated,
-       *  otherwise the %forward_list is extended and the new elements
-       *  are default constructed.
+       *  %forward_list's current number of elements the %forward_list
+       *  is truncated, otherwise the %forward_list is extended and the
+       *  new elements are default constructed.
        */
       void
       resize(size_type __sz);
@@ -1012,9 +1004,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *
        *  This function will %resize the %forward_list to the specified
        *  number of elements.  If the number is smaller than the
-       *  %forward_list's current size the %forward_list is truncated,
-       *  otherwise the %forward_list is extended and new elements are
-       *  populated with given data.
+       *  %forward_list's current number of elements the %forward_list
+       *  is truncated, otherwise the %forward_list is extended and new
+       *  elements are populated with given data.
        */
       void
       resize(size_type __sz, const value_type& __val);
@@ -1048,9 +1040,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       splice_after(const_iterator __pos, forward_list&& __list)
       {
 	if (!__list.empty())
-	  _M_splice_after(__pos, std::move(__list));
+	  _M_splice_after(__pos, __list.before_begin(), __list.end());
       }
 
+      void
+      splice_after(const_iterator __pos, forward_list& __list)
+      { splice_after(__pos, std::move(__list)); }
+
       /**
        *  @brief  Insert element from another %forward_list.
        *  @param  __pos  Iterator referencing the element to insert after.
@@ -1063,15 +1059,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       splice_after(const_iterator __pos, forward_list&& __list,
-                   const_iterator __i)
-      {
-	const_iterator __j = __i;
-	++__j;
-	if (__pos == __i || __pos == __j)
-	  return;
+                   const_iterator __i);
 
-	splice_after(__pos, std::move(__list), __i, __j);
-      }
+      void
+      splice_after(const_iterator __pos, forward_list& __list,
+                   const_iterator __i)
+      { splice_after(__pos, std::move(__list), __i); }
 
       /**
        *  @brief  Insert range from another %forward_list.
@@ -1087,8 +1080,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  Undefined if @a __pos is in (__before,__last).
        */
       void
-      splice_after(const_iterator __pos, forward_list&& __list,
-                   const_iterator __before, const_iterator __last);
+      splice_after(const_iterator __pos, forward_list&&,
+                   const_iterator __before, const_iterator __last)
+      { _M_splice_after(__pos, __before, __last); }
+
+      void
+      splice_after(const_iterator __pos, forward_list&,
+                   const_iterator __before, const_iterator __last)
+      { _M_splice_after(__pos, __before, __last); }
 
       /**
        *  @brief  Remove all elements equal to value.
@@ -1131,7 +1130,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       unique()
-      { this->unique(std::equal_to<_Tp>()); }
+      { unique(std::equal_to<_Tp>()); }
 
       /**
        *  @brief  Remove consecutive elements satisfying a predicate.
@@ -1160,7 +1159,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       merge(forward_list&& __list)
-      { this->merge(std::move(__list), std::less<_Tp>()); }
+      { merge(std::move(__list), std::less<_Tp>()); }
+
+      void
+      merge(forward_list& __list)
+      { merge(std::move(__list)); }
 
       /**
        *  @brief  Merge sorted lists according to comparison function.
@@ -1177,6 +1180,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         void
         merge(forward_list&& __list, _Comp __comp);
 
+      template<typename _Comp>
+        void
+        merge(forward_list& __list, _Comp __comp)
+        { merge(std::move(__list), __comp); }
+
       /**
        *  @brief  Sort the elements of the list.
        *
@@ -1185,7 +1193,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       sort()
-      { this->sort(std::less<_Tp>()); }
+      { sort(std::less<_Tp>()); }
 
       /**
        *  @brief  Sort the forward_list using a comparison function.
@@ -1225,7 +1233,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       // Called by splice_after and insert_after.
       iterator
-      _M_splice_after(const_iterator __pos, forward_list&& __list);
+      _M_splice_after(const_iterator __pos, const_iterator __before,
+		      const_iterator __last);
 
       // Called by forward_list(n).
       void
@@ -1240,11 +1249,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    *  @brief  Forward list equality comparison.
    *  @param  __lx  A %forward_list
    *  @param  __ly  A %forward_list of the same type as @a __lx.
-   *  @return  True iff the size and elements of the forward lists are equal.
+   *  @return  True iff the elements of the forward lists are equal.
    *
-   *  This is an equivalence relation.  It is linear in the size of the
-   *  forward lists.  Deques are considered equivalent if corresponding
-   *  elements compare equal.
+   *  This is an equivalence relation.  It is linear in the number of 
+   *  elements of the forward lists.  Deques are considered equivalent
+   *  if corresponding elements compare equal.
    */
   template<typename _Tp, typename _Alloc>
     bool
@@ -1257,8 +1266,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    *  @param  __ly  A %forward_list of the same type as @a __lx.
    *  @return  True iff @a __lx is lexicographically less than @a __ly.
    *
-   *  This is a total ordering relation.  It is linear in the size of the
-   *  forward lists.  The elements must be comparable with @c <.
+   *  This is a total ordering relation.  It is linear in the number of 
+   *  elements of the forward lists.  The elements must be comparable
+   *  with @c <.
    *
    *  See std::lexicographical_compare() for how the determination is made.
    */
diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 83f32c4e299..e70e74a222d 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -225,22 +225,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   template<typename _Tp, typename _Alloc>
     typename forward_list<_Tp, _Alloc>::iterator
     forward_list<_Tp, _Alloc>::
-    _M_splice_after(const_iterator __pos, forward_list&& __list)
+    _M_splice_after(const_iterator __pos,
+		    const_iterator __before, const_iterator __last)
     {
       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
-      iterator __before = __list.before_begin();
-      return iterator(__tmp->_M_transfer_after(__before._M_node));
+      _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
+      _Node_base* __end = __b;
+
+      while (__end && __end->_M_next != __last._M_node)
+	__end = __end->_M_next;
+
+      if (__b != __end)
+	return iterator(__tmp->_M_transfer_after(__b, __end));      
+      else
+	return iterator(__tmp);
     }
 
   template<typename _Tp, typename _Alloc>
     void
     forward_list<_Tp, _Alloc>::
     splice_after(const_iterator __pos, forward_list&&,
-                 const_iterator __before, const_iterator __last)
+		 const_iterator __i)
     {
+      const_iterator __j = __i;
+      ++__j;
+
+      if (__pos == __i || __pos == __j)
+	return;
+
       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
-      __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
-                               const_cast<_Node_base*>(__last._M_node));
+      __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
+			       const_cast<_Node_base*>(__j._M_node));
     }
 
   template<typename _Tp, typename _Alloc>
@@ -251,7 +266,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       if (__n)
 	{
 	  forward_list __tmp(__n, __val, get_allocator());
-	  return _M_splice_after(__pos, std::move(__tmp));
+	  return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
 	}
       else
 	return iterator(const_cast<_Node_base*>(__pos._M_node));
@@ -266,26 +281,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       {
 	forward_list __tmp(__first, __last, get_allocator());
 	if (!__tmp.empty())
-	  return _M_splice_after(__pos, std::move(__tmp));
+	  return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
 	else
 	  return iterator(const_cast<_Node_base*>(__pos._M_node));
       }
 
   template<typename _Tp, typename _Alloc>
-    typename forward_list<_Tp, _Alloc>::iterator
-    forward_list<_Tp, _Alloc>::
-    insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
-    {
-      if (__il.size())
-	{
-	  forward_list __tmp(__il, get_allocator());
-	  return _M_splice_after(__pos, std::move(__tmp));
-	}
-      else
-	return iterator(const_cast<_Node_base*>(__pos._M_node));
-    }
-
-  template<typename _Tp, typename _Alloc>
     void
     forward_list<_Tp, _Alloc>::
     remove(const _Tp& __val)
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index d4f2aedfccd..41418a8a509 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -596,6 +596,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // reserve, if present, comes from _Rehash_base.
 
     private:
+      // Helper rehash method used when keys are unique.
+      void _M_rehash_aux(size_type __n, std::true_type);
+
+      // Helper rehash method used when keys can be non-unique.
+      void _M_rehash_aux(size_type __n, std::false_type);
+
       // Unconditionally change size of bucket array to n, restore hash policy
       // state to __state on exception.
       void _M_rehash(size_type __n, const _RehashPolicyState& __state);
@@ -1592,41 +1598,145 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __try
 	{
-	  _Bucket* __new_buckets = _M_allocate_buckets(__n);
-	  _Node* __p = _M_begin();
-	  _M_before_begin._M_nxt = nullptr;
-	  std::size_t __cur_bbegin_bkt;
-	  while (__p)
+	  _M_rehash_aux(__n, integral_constant<bool, __uk>());
+	}
+      __catch(...)
+	{
+	  // A failure here means that buckets allocation failed.  We only
+	  // have to restore hash policy previous state.
+	  _M_rehash_policy._M_reset(__state);
+	  __throw_exception_again;
+	}
+    }
+
+  // Rehash when there is no equivalent elements.
+  template<typename _Key, typename _Value,
+	   typename _Allocator, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   bool __chc, bool __cit, bool __uk>
+    void
+    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
+    _M_rehash_aux(size_type __n, std::true_type)
+    {
+      _Bucket* __new_buckets = _M_allocate_buckets(__n);
+      _Node* __p = _M_begin();
+      _M_before_begin._M_nxt = nullptr;
+      std::size_t __bbegin_bkt;
+      while (__p)
+	{
+	  _Node* __next = __p->_M_next();
+	  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
+	  if (!__new_buckets[__bkt])
 	    {
-	      _Node* __next = __p->_M_next();
-	      std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
-	      if (!__new_buckets[__new_index])
+	      __p->_M_nxt = _M_before_begin._M_nxt;
+	      _M_before_begin._M_nxt = __p;
+	      __new_buckets[__bkt] = &_M_before_begin;
+	      if (__p->_M_nxt)
+		__new_buckets[__bbegin_bkt] = __p;
+	      __bbegin_bkt = __bkt;
+	    }
+	  else
+	    {
+	      __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
+	      __new_buckets[__bkt]->_M_nxt = __p;
+	    }
+	  __p = __next;
+	}
+      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      _M_bucket_count = __n;
+      _M_buckets = __new_buckets;
+    }
+
+  // Rehash when there can be equivalent elements, preserve their relative
+  // order.
+  template<typename _Key, typename _Value,
+	   typename _Allocator, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   bool __chc, bool __cit, bool __uk>
+    void
+    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
+    _M_rehash_aux(size_type __n, std::false_type)
+    {
+      _Bucket* __new_buckets = _M_allocate_buckets(__n);
+
+      _Node* __p = _M_begin();
+      _M_before_begin._M_nxt = nullptr;
+      std::size_t __bbegin_bkt;
+      std::size_t __prev_bkt;
+      _Node* __prev_p = nullptr;
+      bool __check_bucket = false;
+
+      while (__p)
+	{
+	  bool __check_now = true;
+	  _Node* __next = __p->_M_next();
+	  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
+
+	  if (!__new_buckets[__bkt])
+	    {
+	      __p->_M_nxt = _M_before_begin._M_nxt;
+	      _M_before_begin._M_nxt = __p;
+	      __new_buckets[__bkt] = &_M_before_begin;
+	      if (__p->_M_nxt)
+		__new_buckets[__bbegin_bkt] = __p;
+	      __bbegin_bkt = __bkt;
+	    }
+	  else
+	    {
+	      if (__prev_p && __prev_bkt == __bkt)
 		{
-		  __p->_M_nxt = _M_before_begin._M_nxt;
-		  _M_before_begin._M_nxt = __p;
-		  __new_buckets[__new_index] = &_M_before_begin;
-		  if (__p->_M_nxt)
-		    __new_buckets[__cur_bbegin_bkt] = __p;
-		  __cur_bbegin_bkt = __new_index;
+		  // Previous insert was already in this bucket, we insert after
+		  // the previously inserted one to preserve equivalent elements
+		  // relative order.
+		  __p->_M_nxt = __prev_p->_M_nxt;
+		  __prev_p->_M_nxt = __p;
+
+		  // Inserting after a node in a bucket require to check that we
+		  // haven't change the bucket last node, in this case next
+		  // bucket containing its before begin node must be updated. We
+		  // schedule a check as soon as we move out of the sequence of
+		  // equivalent nodes to limit the number of checks.
+		  __check_bucket = true;
+		  __check_now = false;
 		}
 	      else
 		{
-		  __p->_M_nxt = __new_buckets[__new_index]->_M_nxt;
-		  __new_buckets[__new_index]->_M_nxt = __p;
+		  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
+		  __new_buckets[__bkt]->_M_nxt = __p;
 		}
-	      __p = __next;
 	    }
-	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
-	  _M_bucket_count = __n;
-	  _M_buckets = __new_buckets;
+	  
+	  if (__check_now && __check_bucket)
+	    {
+	      // Check if we shall update the next bucket because of insertions
+	      // into __prev_bkt bucket.
+	      if (__prev_p->_M_nxt)
+		{
+		  std::size_t __next_bkt
+		    = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+		  if (__next_bkt != __prev_bkt)
+		    __new_buckets[__next_bkt] = __prev_p;
+		}
+	      __check_bucket = false;
+	    }
+	  __prev_p = __p;
+	  __prev_bkt = __bkt;
+	  __p = __next;
 	}
-      __catch(...)
+
+      if (__check_bucket && __prev_p->_M_nxt)
 	{
-	  // A failure here means that buckets allocation failed.  We only
-	  // have to restore hash policy previous state.
-	  _M_rehash_policy._M_reset(__state);
-	  __throw_exception_again;
+	  std::size_t __next_bkt
+	    = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+	  if (__next_bkt != __prev_bkt)
+	    __new_buckets[__next_bkt] = __prev_p;
 	}
+
+      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      _M_bucket_count = __n;
+      _M_buckets = __new_buckets;
     }
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index b585d23a970..ab1be6d01fe 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -533,7 +533,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   // Specialization using EBO.
   template<int _Nm, typename _Tp>
-    struct _Hashtable_ebo_helper<_Nm, _Tp, true> : private _Tp
+    struct _Hashtable_ebo_helper<_Nm, _Tp, true>
+    // See PR53067.
+    : public _Tp
     {
       _Hashtable_ebo_helper() = default;
       _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
@@ -595,8 +597,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Key, typename _Value, typename _ExtractKey, 
 	   typename _H1, typename _H2, typename _Hash>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
-    : private _Hashtable_ebo_helper<0, _ExtractKey>,
-      private _Hashtable_ebo_helper<1, _Hash>
+    // See PR53067.
+    : public  _Hashtable_ebo_helper<0, _ExtractKey>,
+      public  _Hashtable_ebo_helper<1, _Hash>
     {
     private:
       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
@@ -669,9 +672,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
 			   _Default_ranged_hash, false>
-    : private _Hashtable_ebo_helper<0, _ExtractKey>,
-      private _Hashtable_ebo_helper<1, _H1>,
-      private _Hashtable_ebo_helper<2, _H2>
+    // See PR53067.
+    : public  _Hashtable_ebo_helper<0, _ExtractKey>,
+      public  _Hashtable_ebo_helper<1, _H1>,
+      public  _Hashtable_ebo_helper<2, _H2>
     {
     private:
       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
@@ -748,9 +752,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
 			   _Default_ranged_hash, true>
-    : private _Hashtable_ebo_helper<0, _ExtractKey>,
-      private _Hashtable_ebo_helper<1, _H1>,
-      private _Hashtable_ebo_helper<2, _H2>
+    // See PR53067.
+    : public  _Hashtable_ebo_helper<0, _ExtractKey>,
+      public  _Hashtable_ebo_helper<1, _H1>,
+      public  _Hashtable_ebo_helper<2, _H2>
     {
     private:
       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
@@ -853,9 +858,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2, typename _Hash,
 	   bool __cache_hash_code>
   struct _Hashtable_base
+  // See PR53067.
   : public  _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
 			    __cache_hash_code>,
-    private _Hashtable_ebo_helper<0, _Equal>
+    public _Hashtable_ebo_helper<0, _Equal>
   {
   private:
     typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual;
@@ -906,7 +912,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
 				_H1, _H2, _Hash, true>
-      : private _H2
+    // See PR53067.
+    : public _H2
     {
       _Local_iterator_base() = default;
       _Local_iterator_base(_Hash_node<_Value, true>* __p,
@@ -937,8 +944,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
 				_H1, _H2, _Hash, false>
-      : private _Hash_code_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, false>
+    // See PR53067.
+    : public _Hash_code_base<_Key, _Value, _ExtractKey,
+			     _H1, _H2, _Hash, false>
     {
       _Local_iterator_base() = default;
       _Local_iterator_base(_Hash_node<_Value, false>* __p,
diff --git a/libstdc++-v3/include/bits/ptr_traits.h b/libstdc++-v3/include/bits/ptr_traits.h
index 7f120b1f8ac..bba9b49bfc6 100644
--- a/libstdc++-v3/include/bits/ptr_traits.h
+++ b/libstdc++-v3/include/bits/ptr_traits.h
@@ -140,14 +140,8 @@ _GLIBCXX_HAS_NESTED_TYPE(difference_type)
       /// Type used to represent the difference between two pointers
       typedef typename __ptrtr_diff_type<_Ptr>::__type  difference_type;
 
-    private:
       template<typename _Up>
         using rebind = typename __ptrtr_rebind<_Ptr, _Up>::__type;
-
-      // allocator_traits needs to use __rebind
-      template<typename> friend struct allocator_traits;
-      template<typename> friend struct pointer_traits;
-      template<typename, typename> friend class __ptrtr_rebind_helper2;
     };
 
   /**
diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index d55b51838b8..5da353f8bd4 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -730,40 +730,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     independent_bits_engine<_RandomNumberEngine, __w, _UIntType>::
     operator()()
     {
-      const long double __r = static_cast<long double>(_M_b.max())
-			    - static_cast<long double>(_M_b.min()) + 1.0L;
-      const result_type __m = std::log(__r) / std::log(2.0L);
-      result_type __n, __n0, __y0, __y1, __s0, __s1;
+      typedef typename _RandomNumberEngine::result_type _Eresult_type;
+      const _Eresult_type __r
+	= (_M_b.max() - _M_b.min() < std::numeric_limits<_Eresult_type>::max()
+	   ? _M_b.max() - _M_b.min() + 1 : 0);
+      const unsigned __edig = std::numeric_limits<_Eresult_type>::digits;
+      const unsigned __m = __r ? std::__lg(__r) : __edig;
+
+      typedef typename std::common_type<_Eresult_type, result_type>::type
+	__ctype;
+      const unsigned __cdig = std::numeric_limits<__ctype>::digits;
+
+      unsigned __n, __n0;
+      __ctype __s0, __s1, __y0, __y1;
+
       for (size_t __i = 0; __i < 2; ++__i)
 	{
 	  __n = (__w + __m - 1) / __m + __i;
 	  __n0 = __n - __w % __n;
-	  const result_type __w0 = __w / __n;
-	  const result_type __w1 = __w0 + 1;
-	  __s0 = result_type(1) << __w0;
-	  __s1 = result_type(1) << __w1;
-	  __y0 = __s0 * (__r / __s0);
-	  __y1 = __s1 * (__r / __s1);
-	  if (__r - __y0 <= __y0 / __n)
+	  const unsigned __w0 = __w / __n;  // __w0 <= __m
+
+	  __s0 = 0;
+	  __s1 = 0;
+	  if (__w0 < __cdig)
+	    {
+	      __s0 = __ctype(1) << __w0;
+	      __s1 = __s0 << 1;
+	    }
+
+	  __y0 = 0;
+	  __y1 = 0;
+	  if (__r)
+	    {
+	      __y0 = __s0 * (__r / __s0);
+	      if (__s1)
+		__y1 = __s1 * (__r / __s1);
+
+	      if (__r - __y0 <= __y0 / __n)
+		break;
+	    }
+	  else
 	    break;
 	}
 
       result_type __sum = 0;
       for (size_t __k = 0; __k < __n0; ++__k)
 	{
-	  result_type __u;
+	  __ctype __u;
 	  do
 	    __u = _M_b() - _M_b.min();
-	  while (__u >= __y0);
-	  __sum = __s0 * __sum + __u % __s0;
+	  while (__y0 && __u >= __y0);
+	  __sum = __s0 * __sum + (__s0 ? __u % __s0 : __u);
 	}
       for (size_t __k = __n0; __k < __n; ++__k)
 	{
-	  result_type __u;
+	  __ctype __u;
 	  do
 	    __u = _M_b() - _M_b.min();
-	  while (__u >= __y1);
-	  __sum = __s1 * __sum + __u % __s1;
+	  while (__y1 && __u >= __y1);
+	  __sum = __s1 * __sum + (__s1 ? __u % __s1 : __u);
 	}
       return __sum;
     }
@@ -840,12 +865,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       operator()(_UniformRandomNumberGenerator& __urng,
 		 const param_type& __param)
       {
-	typedef typename std::make_unsigned<typename
-	  _UniformRandomNumberGenerator::result_type>::type __urngtype;
+	typedef typename _UniformRandomNumberGenerator::result_type
+	  _Gresult_type;
 	typedef typename std::make_unsigned<result_type>::type __utype;
-	typedef typename std::conditional<(sizeof(__urngtype)
-					   > sizeof(__utype)),
-	  __urngtype, __utype>::type __uctype;
+	typedef typename std::common_type<_Gresult_type, __utype>::type
+	  __uctype;
 
 	const __uctype __urngmin = __urng.min();
 	const __uctype __urngmax = __urng.max();
diff --git a/libstdc++-v3/include/bits/shared_ptr_base.h b/libstdc++-v3/include/bits/shared_ptr_base.h
index c48c18eaee9..39449f1b4bb 100644
--- a/libstdc++-v3/include/bits/shared_ptr_base.h
+++ b/libstdc++-v3/include/bits/shared_ptr_base.h
@@ -343,6 +343,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc& __a)
       : _M_ptr(__p), _M_del(__d, __a) { }
 
+      ~_Sp_counted_deleter() noexcept { }
+
       virtual void
       _M_dispose() noexcept
       { _M_del._M_del(_M_ptr); }
@@ -401,6 +403,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      std::forward<_Args>(__args)...); // might throw
 	}
 
+      ~_Sp_counted_ptr_inplace() noexcept { }
+
       virtual void
       _M_dispose() noexcept
       { allocator_traits<_Alloc>::destroy(_M_impl, _M_impl._M_ptr); }
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index d6b1bf1eb89..8fb385d7293 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -244,7 +244,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }
 
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
   /// This is an overload used by find_if_not() for the Input Iterator case.
   template<typename _InputIterator, typename _Predicate>
     inline _InputIterator
@@ -303,7 +302,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return __last;
 	}
     }
-#endif
+
+  /// Provided for stable_partition to use.
+  template<typename _InputIterator, typename _Predicate>
+    inline _InputIterator
+    __find_if_not(_InputIterator __first, _InputIterator __last,
+		  _Predicate __pred)
+    {
+      return std::__find_if_not(__first, __last, __pred,
+				std::__iterator_category(__first));
+    }
+
+  /// Like find_if_not(), but uses and updates a count of the
+  /// remaining range length instead of comparing against an end
+  /// iterator.
+  template<typename _InputIterator, typename _Predicate, typename _Distance>
+    _InputIterator
+    __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
+    {
+      for (; __len; --__len, ++__first)
+	if (!bool(__pred(*__first)))
+	  break;
+      return __first;
+    }
 
   // set_difference
   // set_intersection
@@ -822,8 +843,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 	      typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
-      return std::__find_if_not(__first, __last, __pred,
-				std::__iterator_category(__first));
+      return std::__find_if_not(__first, __last, __pred);
     }
 
   /**
@@ -1817,30 +1837,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // partition
 
   /// This is a helper function...
+  /// Requires __len != 0 and !__pred(*__first),
+  /// same as __stable_partition_adaptive.
   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
     _ForwardIterator
     __inplace_stable_partition(_ForwardIterator __first,
-			       _ForwardIterator __last,
 			       _Predicate __pred, _Distance __len)
     {
       if (__len == 1)
-	return __pred(*__first) ? __last : __first;
+	return __first;
       _ForwardIterator __middle = __first;
       std::advance(__middle, __len / 2);
-      _ForwardIterator __begin = std::__inplace_stable_partition(__first,
-								 __middle,
-								 __pred,
-								 __len / 2);
-      _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
-							       __pred,
-							       __len
-							       - __len / 2);
-      std::rotate(__begin, __middle, __end);
-      std::advance(__begin, std::distance(__middle, __end));
-      return __begin;
+      _ForwardIterator __left_split =
+	std::__inplace_stable_partition(__first, __pred, __len / 2);
+      // Advance past true-predicate values to satisfy this
+      // function's preconditions.
+      _Distance __right_len = __len - __len / 2;
+      _ForwardIterator __right_split =
+	std::__find_if_not_n(__middle, __right_len, __pred);
+      if (__right_len)
+	__right_split = std::__inplace_stable_partition(__middle,
+							__pred,
+							__right_len);
+      std::rotate(__left_split, __middle, __right_split);
+      std::advance(__left_split, std::distance(__middle, __right_split));
+      return __left_split;
     }
 
   /// This is a helper function...
+  /// Requires __first != __last and !__pred(*__first)
+  /// and __len == distance(__first, __last).
+  ///
+  /// !__pred(*__first) allows us to guarantee that we don't
+  /// move-assign an element onto itself.
   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
 	   typename _Distance>
     _ForwardIterator
@@ -1854,6 +1883,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  _ForwardIterator __result1 = __first;
 	  _Pointer __result2 = __buffer;
+	  // The precondition guarantees that !__pred(*__first), so
+	  // move that element to the buffer before starting the loop.
+	  // This ensures that we only call __pred once per element.
+	  *__result2 = _GLIBCXX_MOVE(*__first);
+	  ++__result2;
+	  ++__first;
 	  for (; __first != __last; ++__first)
 	    if (__pred(*__first))
 	      {
@@ -1872,17 +1907,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  _ForwardIterator __middle = __first;
 	  std::advance(__middle, __len / 2);
-	  _ForwardIterator __begin =
+	  _ForwardIterator __left_split =
 	    std::__stable_partition_adaptive(__first, __middle, __pred,
 					     __len / 2, __buffer,
 					     __buffer_size);
-	  _ForwardIterator __end =
-	    std::__stable_partition_adaptive(__middle, __last, __pred,
-					     __len - __len / 2,
-					     __buffer, __buffer_size);
-	  std::rotate(__begin, __middle, __end);
-	  std::advance(__begin, std::distance(__middle, __end));
-	  return __begin;
+	  // Advance past true-predicate values to satisfy this
+	  // function's preconditions.
+	  _Distance __right_len = __len - __len / 2;
+	  _ForwardIterator __right_split =
+	    std::__find_if_not_n(__middle, __right_len, __pred);
+	  if (__right_len)
+	    __right_split =
+	      std::__stable_partition_adaptive(__right_split, __last, __pred,
+					       __right_len,
+					       __buffer, __buffer_size);
+	  std::rotate(__left_split, __middle, __right_split);
+	  std::advance(__left_split, std::distance(__middle, __right_split));
+	  return __left_split;
 	}
     }
 
@@ -1915,6 +1956,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
 
+      __first = std::__find_if_not(__first, __last, __pred);
+
       if (__first == __last)
 	return __first;
       else
@@ -1934,7 +1977,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					  _DistanceType(__buf.size()));
 	else
 	  return
-	    std::__inplace_stable_partition(__first, __last, __pred,
+	    std::__inplace_stable_partition(__first, __pred,
 					 _DistanceType(__buf.requested_size()));
 	}
     }
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index a002461ae98..5cee10ac016 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -982,14 +982,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   __lg(int __n)
   { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
 
+  inline unsigned
+  __lg(unsigned __n)
+  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
+
   inline long
   __lg(long __n)
   { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
 
+  inline unsigned long
+  __lg(unsigned long __n)
+  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
+
   inline long long
   __lg(long long __n)
   { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
 
+  inline unsigned long long
+  __lg(unsigned long long __n)
+  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 
 _GLIBCXX_BEGIN_NAMESPACE_ALGO
diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h
index 88655fc55c3..33d5e709628 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -1,6 +1,7 @@
 // Functor implementations -*- C++ -*-
 
-// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011
+// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010,
+// 2011, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -471,7 +472,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /** @}  */
 
   template<typename _Tp>
-    struct _Identity : public unary_function<_Tp,_Tp>
+    struct _Identity
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+    // unary_function itself is deprecated in C++11 and deriving from
+    // it can even be a nuisance (see PR 52942).
+    : public unary_function<_Tp,_Tp>
+#endif
     {
       _Tp&
       operator()(_Tp& __x) const
@@ -483,8 +489,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
   template<typename _Pair>
-    struct _Select1st : public unary_function<_Pair,
-					      typename _Pair::first_type>
+    struct _Select1st
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+    : public unary_function<_Pair, typename _Pair::first_type>
+#endif
     {
       typename _Pair::first_type&
       operator()(_Pair& __x) const
@@ -508,8 +516,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
   template<typename _Pair>
-    struct _Select2nd : public unary_function<_Pair,
-					      typename _Pair::second_type>
+    struct _Select2nd
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+    : public unary_function<_Pair, typename _Pair::second_type>
+#endif
     {
       typename _Pair::second_type&
       operator()(_Pair& __x) const
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index f0bf4917b66..c5cf0498410 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -429,36 +429,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  %Vector move assignment operator.
        *  @param  __x  A %vector of identical element and allocator types.
        *
-       *  The contents of @a __x are moved into this %vector (without copying).
+       *  The contents of @a __x are moved into this %vector (without copying,
+       *  if the allocators permit it).
        *  @a __x is a valid, but unspecified %vector.
        */
       vector&
       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	if (_Alloc_traits::_S_propagate_on_move_assign())
-	  {
-	    // We're moving the rvalue's allocator so can move the data too.
-	    const vector __tmp(std::move(*this));     // discard existing data
-	    this->_M_impl._M_swap_data(__x._M_impl);
-	    std::__alloc_on_move(_M_get_Tp_allocator(),
-				 __x._M_get_Tp_allocator());
-	  }
-	else if (_Alloc_traits::_S_always_equal()
-	         || __x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
-	  {
-	    // The rvalue's allocator can free our storage and vice versa,
-	    // so can swap the data storage after destroying our contents.
-	    this->clear();
-	    this->_M_impl._M_swap_data(__x._M_impl);
-	  }
-	else
-	  {
-	    // The rvalue's allocator cannot be moved, or is not equal,
-	    // so we need to individually move each element.
-	    this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
-			 std::__make_move_if_noexcept_iterator(__x.end()));
-	    __x.clear();
-	  }
+        constexpr bool __move_storage =
+          _Alloc_traits::_S_propagate_on_move_assign()
+          || _Alloc_traits::_S_always_equal();
+        _M_move_assign(std::move(__x),
+                       integral_constant<bool, __move_storage>());
 	return *this;
       }
 
@@ -1408,6 +1390,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
 	this->_M_impl._M_finish = __pos;
       }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    private:
+      // Constant-time move assignment when source object's memory can be
+      // moved, either because the source's allocator will move too
+      // or because the allocators are equal.
+      void
+      _M_move_assign(vector&& __x, std::true_type) noexcept
+      {
+	const vector __tmp(std::move(*this));
+	this->_M_impl._M_swap_data(__x._M_impl);
+	if (_Alloc_traits::_S_propagate_on_move_assign())
+	  std::__alloc_on_move(_M_get_Tp_allocator(),
+			       __x._M_get_Tp_allocator());
+      }
+
+      // Do move assignment when it might not be possible to move source
+      // object's memory, resulting in a linear-time operation.
+      void
+      _M_move_assign(vector&& __x, std::false_type)
+      {
+	if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
+	  _M_move_assign(std::move(__x), std::true_type());
+	else
+	  {
+	    // The rvalue's allocator cannot be moved and is not equal,
+	    // so we need to individually move each element.
+	    this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
+			 std::__make_move_if_noexcept_iterator(__x.end()));
+	    __x.clear();
+	  }
+      }
+#endif
     };
 
 
diff --git a/libstdc++-v3/include/c_global/cstdio b/libstdc++-v3/include/c_global/cstdio
index d11743a349d..e6484759d5b 100644
--- a/libstdc++-v3/include/c_global/cstdio
+++ b/libstdc++-v3/include/c_global/cstdio
@@ -47,7 +47,7 @@
 #define _GLIBCXX_CSTDIO 1
 
 #ifndef _GLIBCXX_HAVE_GETS
-extern "C" extern char* gets (char* __s) __attribute__((deprecated));
+extern "C" char* gets (char* __s) __attribute__((deprecated));
 #endif
 
 // Get rid of those macros defined in <stdio.h> in lieu of real functions.
diff --git a/libstdc++-v3/include/c_std/cstdio b/libstdc++-v3/include/c_std/cstdio
index 1588fc9e55b..d4f473252e9 100644
--- a/libstdc++-v3/include/c_std/cstdio
+++ b/libstdc++-v3/include/c_std/cstdio
@@ -46,7 +46,7 @@
 #include <stdio.h>
 
 #ifndef _GLIBCXX_HAVE_GETS
-extern "C" extern char* gets (char* __s) __attribute__((deprecated));
+extern "C" char* gets (char* __s) __attribute__((deprecated));
 #endif
 
 // Get rid of those macros defined in <stdio.h> in lieu of real functions.
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index b74b38a02bc..be9c7925876 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -414,6 +414,10 @@ namespace __debug
       }
 
       void
+      splice_after(const_iterator __pos, forward_list& __list)
+      { splice_after(__pos, std::move(__list)); }
+
+      void
       splice_after(const_iterator __pos, forward_list&& __list,
 		   const_iterator __i)
       {
@@ -436,6 +440,11 @@ namespace __debug
       }
 
       void
+      splice_after(const_iterator __pos, forward_list& __list,
+		   const_iterator __i)
+      { splice_after(__pos, std::move(__list), __i); }
+
+      void
       splice_after(const_iterator __pos, forward_list&& __list,
 		   const_iterator __before, const_iterator __last)
       {
@@ -481,6 +490,11 @@ namespace __debug
       }
 
       void
+      splice_after(const_iterator __pos, forward_list& __list,
+		   const_iterator __before, const_iterator __last)
+      { splice_after(__pos, std::move(__list), __before, __last); }
+
+      void
       remove(const _Tp& __val)
       {
 	_Base_iterator __x = _Base::before_begin();
@@ -561,6 +575,10 @@ namespace __debug
 	}
       }
 
+      void
+      merge(forward_list& __list)
+      { merge(std::move(__list)); }
+
       template<typename _Comp>
         void
         merge(forward_list&& __list, _Comp __comp)
@@ -580,6 +598,11 @@ namespace __debug
 	  }
 	}
 
+      template<typename _Comp>
+        void
+        merge(forward_list& __list, _Comp __comp)
+        { merge(std::move(__list), __comp); }
+
       using _Base::sort;
       using _Base::reverse;
 
@@ -733,8 +756,12 @@ namespace __gnu_debug
       typedef typename _It::iterator_type _BaseIt;
 
       static bool
-      _M_Is(_BaseIt __it, const _Sequence* __seq)
+      _S_Is(_BaseIt __it, const _Sequence* __seq)
       { return __it == __seq->_M_base().cbefore_begin(); }
+
+      static bool
+      _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq)
+      { return _S_Is(__it, __seq); }
     };
 }
 
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index e7cfe9c9d53..b16cdeaa4dd 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -1,6 +1,6 @@
 // Safe iterator implementation  -*- C++ -*-
 
-// Copyright (C) 2003, 2004, 2005, 2006, 2009, 2010, 2011
+// Copyright (C) 2003, 2004, 2005, 2006, 2009, 2010, 2011, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -50,8 +50,12 @@ namespace __gnu_debug
       typedef typename _It::iterator_type _BaseIt;
 
       static bool
-      _M_Is(_BaseIt __it, const _Sequence* __seq)
+      _S_Is(_BaseIt, const _Sequence*)
       { return false; }
+
+      static bool
+      _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq)
+      { return __it == __seq->_M_base().begin(); }
     };
 
   /** Iterators that derive from _Safe_iterator_base but that aren't
@@ -169,6 +173,24 @@ namespace __gnu_debug
 			      ._M_iterator(__x, "other"));
       }
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      /**
+       * @brief Move construction.
+       * @post __x is singular and unattached
+       */
+      _Safe_iterator(_Safe_iterator&& __x) : _M_current()
+      {
+	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
+			      || __x._M_current == _Iterator(),
+			      _M_message(__msg_init_copy_singular)
+			      ._M_iterator(*this, "this")
+			      ._M_iterator(__x, "other"));
+	std::swap(_M_current, __x._M_current);
+	this->_M_attach(__x._M_sequence);
+	__x._M_detach();
+      }
+#endif
+
       /**
        *  @brief Converting constructor from a mutable iterator to a
        *  constant iterator.
@@ -208,6 +230,27 @@ namespace __gnu_debug
 	return *this;
       }
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      /**
+       * @brief Move assignment.
+       * @post __x is singular and unattached
+       */
+      _Safe_iterator&
+      operator=(_Safe_iterator&& __x)
+      {
+	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
+			      || __x._M_current == _Iterator(),
+			      _M_message(__msg_copy_singular)
+			      ._M_iterator(*this, "this")
+			      ._M_iterator(__x, "other"));
+	_M_current = __x._M_current;
+	_M_attach(__x._M_sequence);
+	__x._M_detach();
+	__x._M_current = _Iterator();
+	return *this;
+      }
+#endif
+
       /**
        *  @brief Iterator dereference.
        *  @pre iterator is dereferenceable
@@ -422,7 +465,17 @@ namespace __gnu_debug
       /// Is this iterator equal to the sequence's before_begin() iterator if
       /// any?
       bool _M_is_before_begin() const
-      { return _BeforeBeginHelper<_Sequence>::_M_Is(base(), _M_get_sequence()); }
+      {
+	return _BeforeBeginHelper<_Sequence>::_S_Is(base(), _M_get_sequence());
+      }
+
+      /// Is this iterator equal to the sequence's before_begin() iterator if
+      /// any or begin() otherwise?
+      bool _M_is_beginnest() const
+      {
+	return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(base(),
+							  _M_get_sequence());
+      }
     };
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 777a707e7f3..f01252bf6c2 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -1,6 +1,6 @@
 // Debugging iterator implementation (out of line) -*- C++ -*-
 
-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -91,10 +91,11 @@ namespace __gnu_debug
 	/* We can only test for equality, but check if one of the
 	   iterators is at an extreme. */
 	/* Optim for classic [begin, it) or [it, end) ranges, limit checks
-	 * when code is valid. */
-	if (_M_is_begin() || __rhs._M_is_end())
+	 * when code is valid.  Note, for the special case of forward_list,
+	 * before_begin replaces the role of begin.  */ 
+	if (_M_is_beginnest() || __rhs._M_is_end())
 	  return true;
-	if (_M_is_end() || __rhs._M_is_begin())
+	if (_M_is_end() || __rhs._M_is_beginnest())
 	  return false;
 
 	// Assume that this is a valid range; we can't check anything else
diff --git a/libstdc++-v3/include/ext/functional b/libstdc++-v3/include/ext/functional
index 85b944bf61d..f8402c16dc6 100644
--- a/libstdc++-v3/include/ext/functional
+++ b/libstdc++-v3/include/ext/functional
@@ -1,6 +1,6 @@
 // Functional extensions -*- C++ -*-
 
-// Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010
+// Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -183,7 +183,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @addtogroup SGIextensions
    */
   template <class _Tp>
-    struct identity : public std::_Identity<_Tp> {};
+    struct identity
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    : public std::unary_function<_Tp,_Tp>,
+      public std::_Identity<_Tp> {};
+#else
+    : public std::_Identity<_Tp> {};
+#endif
 
   /** @c select1st and @c select2nd are extensions provided by SGI.  Their
    *  @c operator()s
@@ -197,11 +203,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    */
   /// An \link SGIextensions SGI extension \endlink.
   template <class _Pair>
-    struct select1st : public std::_Select1st<_Pair> {};
+    struct select1st
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    : public std::unary_function<_Pair, typename _Pair::first_type>,
+      public std::_Select1st<_Pair> {};
+#else
+    : public std::_Select1st<_Pair> {};
+#endif
 
   /// An \link SGIextensions SGI extension \endlink.
   template <class _Pair>
-    struct select2nd : public std::_Select2nd<_Pair> {};
+    struct select2nd
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    : public std::unary_function<_Pair, typename _Pair::second_type>,
+      public std::_Select2nd<_Pair> {};
+#else
+    : public std::_Select2nd<_Pair> {};
+#endif
   /** @}  */
 
   // extension documented next
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
index 8370a2ec885..c5748ecd674 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
@@ -1,6 +1,6 @@
  // -*- C++ -*-
 
-// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
+// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -188,7 +188,11 @@ recursive_copy_node(node_const_pointer p_ncp)
   __try
     {
       while (child_it != p_icp->end())
-	a_p_children[child_i++] = recursive_copy_node(*(child_it++));
+	{
+	  a_p_children[child_i] = recursive_copy_node(*(child_it));
+	  child_i++;
+	  child_it++;
+	}
       p_ret = s_inode_allocator.allocate(1);
     }
   __catch(...)
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
index b7eb024c07f..0a763b56ada 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2009, 2011, 2012 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
@@ -50,7 +50,11 @@ namespace __gnu_pbds
     /// Base type for PATRICIA trees.
     struct pat_trie_base
     {
-      /// Three types of nodes.
+      /**
+       *  @brief  Three types of nodes.
+       *
+       *  i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head.
+       */
       enum node_type
 	{
 	  i_node,
diff --git a/libstdc++-v3/include/std/array b/libstdc++-v3/include/std/array
index ae7445d0b21..8cd53880820 100644
--- a/libstdc++-v3/include/std/array
+++ b/libstdc++-v3/include/std/array
@@ -1,6 +1,7 @@
 // <array> -*- C++ -*-
 
-// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
+// 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
@@ -174,8 +175,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const_reference
       at(size_type __n) const
       {
-	return __n < _Nm ?
-	       _M_instance[__n] : __throw_out_of_range(__N("array::at"));
+	if (__n >= _Nm)
+	  std::__throw_out_of_range(__N("array::at"));
+	return _M_instance[__n];
       }
 #endif
 
diff --git a/libstdc++-v3/include/std/scoped_allocator b/libstdc++-v3/include/std/scoped_allocator
index edace9840d1..fc2db7cbd66 100644
--- a/libstdc++-v3/include/std/scoped_allocator
+++ b/libstdc++-v3/include/std/scoped_allocator
@@ -1,6 +1,6 @@
 // <scoped_allocator> -*- C++ -*-
 
-// Copyright (C) 2011 Free Software Foundation, Inc.
+// Copyright (C) 2011, 2012 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
@@ -77,7 +77,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   
   template<typename _Alloc>
     inline auto
-    __do_outermost(_Alloc& __a, _Alloc&) -> decltype(__a.outer_allocator())
+    __do_outermost(_Alloc& __a, _Alloc*) -> decltype(__a.outer_allocator())
     { return __a.outer_allocator(); }
 
   template<typename _Alloc>
@@ -87,8 +87,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _Alloc>
     inline auto
-    __outermost(_Alloc& __a) -> decltype(__do_outermost(__a, __a))
-    { return __do_outermost(__a, __a); }
+    __outermost(_Alloc& __a) -> decltype(__do_outermost(__a, &__a))
+    { return __do_outermost(__a, &__a); }
 
   template<typename _OuterAlloc, typename... _InnerAllocs>
     class scoped_allocator_adaptor;