c++: fewer allocator temps [PR105838]

In this PR, initializing the array of std::string to pass to the vector
initializer_list constructor gets very confusing to the optimizers as the
number of elements increases, primarily because of all the std::allocator
temporaries passed to all the string constructors.  Instead of creating one
for each string, let's share an allocator between all the strings; we can do
this safely because we know that std::allocator is stateless and that string
doesn't care about the object identity of its allocator parameter.

	PR c++/105838

gcc/cp/ChangeLog:

	* cp-tree.h (is_std_allocator): Declare.
	* constexpr.cc (is_std_allocator): Split out  from...
	(is_std_allocator_allocate): ...here.
	* init.cc (find_temps_r): New.
	(find_allocator_temp): New.
	(build_vec_init): Use it.

gcc/testsuite/ChangeLog:

	* g++.dg/tree-ssa/allocator-opt1.C: New test.

3 files changed, 76 insertions, 11 deletions

diff --git a/gcc/cp/constexpr.cc b/gcc/cp/constexpr.cc
index 23a27a96..e43d928 100644
--- a/gcc/cp/constexpr.cc
+++ b/gcc/cp/constexpr.cc
@@ -2214,28 +2214,35 @@ is_std_construct_at (const constexpr_call *call)
 	  && is_std_construct_at (call->fundef->decl));
 }
 
-/* Return true if FNDECL is std::allocator<T>::{,de}allocate.  */
+/* True if CTX is an instance of std::allocator.  */
 
-static inline bool
-is_std_allocator_allocate (tree fndecl)
+bool
+is_std_allocator (tree ctx)
 {
-  tree name = DECL_NAME (fndecl);
-  if (name == NULL_TREE
-      || !(id_equal (name, "allocate") || id_equal (name, "deallocate")))
-    return false;
-
-  tree ctx = DECL_CONTEXT (fndecl);
   if (ctx == NULL_TREE || !CLASS_TYPE_P (ctx) || !TYPE_MAIN_DECL (ctx))
     return false;
 
   tree decl = TYPE_MAIN_DECL (ctx);
-  name = DECL_NAME (decl);
+  tree name = DECL_NAME (decl);
   if (name == NULL_TREE || !id_equal (name, "allocator"))
     return false;
 
   return decl_in_std_namespace_p (decl);
 }
 
+/* Return true if FNDECL is std::allocator<T>::{,de}allocate.  */
+
+static inline bool
+is_std_allocator_allocate (tree fndecl)
+{
+  tree name = DECL_NAME (fndecl);
+  if (name == NULL_TREE
+      || !(id_equal (name, "allocate") || id_equal (name, "deallocate")))
+    return false;
+
+  return is_std_allocator (DECL_CONTEXT (fndecl));
+}
+
 /* Overload for the above taking constexpr_call*.  */
 
 static inline bool
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index addd26e..581ac2b 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -8472,6 +8472,7 @@ extern bool is_rvalue_constant_expression (tree);
 extern bool is_nondependent_constant_expression (tree);
 extern bool is_nondependent_static_init_expression (tree);
 extern bool is_static_init_expression    (tree);
+extern bool is_std_allocator (tree);
 extern bool potential_rvalue_constant_expression (tree);
 extern bool require_potential_constant_expression (tree);
 extern bool require_constant_expression (tree);
diff --git a/gcc/cp/init.cc b/gcc/cp/init.cc
index 2fff4ad..428fac5 100644
--- a/gcc/cp/init.cc
+++ b/gcc/cp/init.cc
@@ -4308,6 +4308,51 @@ finish_length_check (tree atype, tree iterator, tree obase, unsigned n)
     }
 }
 
+/* walk_tree callback to collect temporaries in an expression.  */
+
+tree
+find_temps_r (tree *tp, int *walk_subtrees, void *data)
+{
+  vec<tree*> &temps = *static_cast<auto_vec<tree*> *>(data);
+  tree t = *tp;
+  if (TREE_CODE (t) == TARGET_EXPR
+      && !TARGET_EXPR_ELIDING_P (t))
+    temps.safe_push (tp);
+  else if (TYPE_P (t))
+    *walk_subtrees = 0;
+
+  return NULL_TREE;
+}
+
+/* If INIT initializes a standard library class, and involves a temporary
+   std::allocator<T>, return a pointer to the temp.
+
+   Used by build_vec_init when initializing an array of e.g. strings to reuse
+   the same temporary allocator for all of the strings.  We can do this because
+   std::allocator has no data and the standard library doesn't care about the
+   address of allocator objects.
+
+   ??? Add an attribute to allow users to assert the same property for other
+   classes, i.e. one object of the type is interchangeable with any other?  */
+
+static tree*
+find_allocator_temp (tree init)
+{
+  if (TREE_CODE (init) == EXPR_STMT)
+    init = EXPR_STMT_EXPR (init);
+  if (TREE_CODE (init) == CONVERT_EXPR)
+    init = TREE_OPERAND (init, 0);
+  tree type = TREE_TYPE (init);
+  if (!CLASS_TYPE_P (type) || !decl_in_std_namespace_p (TYPE_NAME (type)))
+    return NULL;
+  auto_vec<tree*> temps;
+  cp_walk_tree_without_duplicates (&init, find_temps_r, &temps);
+  for (tree *p : temps)
+    if (is_std_allocator (TREE_TYPE (*p)))
+      return p;
+  return NULL;
+}
+
 /* `build_vec_init' returns tree structure that performs
    initialization of a vector of aggregate types.
 
@@ -4589,6 +4634,8 @@ build_vec_init (tree base, tree maxindex, tree init,
       if (try_const)
 	vec_alloc (const_vec, CONSTRUCTOR_NELTS (init));
 
+      tree alloc_obj = NULL_TREE;
+
       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), idx, field, elt)
 	{
 	  tree baseref = build1 (INDIRECT_REF, type, base);
@@ -4638,7 +4685,17 @@ build_vec_init (tree base, tree maxindex, tree init,
 	    }
 
 	  if (one_init)
-	    finish_expr_stmt (one_init);
+	    {
+	      /* Only create one std::allocator temporary.  */
+	      if (tree *this_alloc = find_allocator_temp (one_init))
+		{
+		  if (alloc_obj)
+		    *this_alloc = alloc_obj;
+		  else
+		    alloc_obj = TARGET_EXPR_SLOT (*this_alloc);
+		}
+	      finish_expr_stmt (one_init);
+	    }
 
 	  one_init = cp_build_unary_op (PREINCREMENT_EXPR, base, false,
 					complain);