[PATCH 1/2] c++: std::variant slow to compile [PR109678]

[PATCH 1/2] c++: std::variant slow to compile [PR109678]

[Jason Merrill]

Tested x86_64-pc-linux-gnu, applying to trunk.

-- 8< --

Here, when dealing with a class with a complex subobject structure, we would
try and fail to find the relevant FIELD_DECL for an empty base before giving
up.  And we would do this at each level, in a combinatorially problematic
way.  Instead, we should check for an empty base first.

	PR c++/109678

gcc/cp/ChangeLog:

	* constexpr.cc (cxx_fold_indirect_ref_1): Handle empty base first.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp1z/variant1.C: New test.
---
 gcc/cp/constexpr.cc                   | 23 +++++++------
 gcc/testsuite/g++.dg/cpp1z/variant1.C | 47 +++++++++++++++++++++++++++
 2 files changed, 60 insertions(+), 10 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp1z/variant1.C

diff --git a/gcc/cp/constexpr.cc b/gcc/cp/constexpr.cc
index d1097764b10..37d1c444c9e 100644
--- a/gcc/cp/constexpr.cc
+++ b/gcc/cp/constexpr.cc
@@ -5446,6 +5446,19 @@ cxx_fold_indirect_ref_1 (const constexpr_ctx *ctx, location_t loc, tree type,
 		  return ret;
 	      }
 	  }
+
+      /* Handle conversion to an empty base class, which is represented with a
+	 NOP_EXPR.  Do this before spelunking into the non-empty subobjects,
+	 which is likely to be a waste of time (109678).  */
+      if (is_empty_class (type)
+	  && CLASS_TYPE_P (optype)
+	  && DERIVED_FROM_P (type, optype))
+	{
+	  if (empty_base)
+	    *empty_base = true;
+	  return op;
+	}
+
       for (tree field = TYPE_FIELDS (optype);
 	   field; field = DECL_CHAIN (field))
 	if (TREE_CODE (field) == FIELD_DECL
@@ -5468,16 +5481,6 @@ cxx_fold_indirect_ref_1 (const constexpr_ctx *ctx, location_t loc, tree type,
 		  return ret;
 	      }
 	  }
-      /* Also handle conversion to an empty base class, which
-	 is represented with a NOP_EXPR.  */
-      if (is_empty_class (type)
-	  && CLASS_TYPE_P (optype)
-	  && DERIVED_FROM_P (type, optype))
-	{
-	  if (empty_base)
-	    *empty_base = true;
-	  return op;
-	}
     }
 
   return NULL_TREE;
diff --git a/gcc/testsuite/g++.dg/cpp1z/variant1.C b/gcc/testsuite/g++.dg/cpp1z/variant1.C
new file mode 100644
index 00000000000..9b18cc233ca
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/variant1.C
@@ -0,0 +1,47 @@
+// PR c++/109678
+// With the bug, compiling this testcase takes more than the typical timeout.
+// { dg-do compile { target c++17 } }
+
+#include <variant>
+
+struct A {};
+struct B {};
+struct C {};
+struct D {};
+struct E {};
+struct F {};
+struct G {};
+struct H {};
+struct I {};
+struct J {};
+struct K {};
+struct L {};
+struct M {};
+struct N {};
+struct O {};
+struct P {};
+struct Q {};
+struct R {};
+struct S {};
+struct T {};
+struct U {};
+struct V {};
+struct W {
+    // gcc13 + compiler explorer = 20000ms 
+    // gcc12.2 + compiler explorer =   400ms
+    int i;
+};
+struct X {};
+struct Y {};
+struct Z {};
+
+using Foo = std::variant<A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z>;
+
+struct Bar {
+    Foo f;
+    static Bar dummy() {
+        // issue is triggered by this initialization
+        return {Z{}};
+        // return {A{}}; // would be very quick
+    }
+};

base-commit: bc24c51c0ccd64617864897ad071c98004ffc0a4
-- 
2.31.1

[PATCH 2/2] c++: look for empty base at specific offset [PR109678]

[Jason Merrill]

Tested x86_64-pc-linux-gnu, applying to trunk.

-- 8< --

While looking at the empty base handling for 109678, it occurred to me that
we ought to be able to look for an empty base at a specific offset, not just
in general.

	PR c++/109678

gcc/cp/ChangeLog:

	* cp-tree.h (lookup_base): Add offset parm.
	* constexpr.cc (cxx_fold_indirect_ref_1): Pass it.
	* search.cc (struct lookup_base_data_s): Add offset.
	(dfs_lookup_base): Handle it.
	(lookup_base): Pass it.
---
 gcc/cp/cp-tree.h    |  3 ++-
 gcc/cp/constexpr.cc |  2 +-
 gcc/cp/search.cc    | 25 ++++++++++++++++++++++---
 3 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index c9c4cd6f32f..406a5508ce7 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -7515,7 +7515,8 @@ extern tree build_if_nonnull			(tree, tree, tsubst_flags_t);
 extern tree get_parent_with_private_access 	(tree decl, tree binfo);
 extern bool accessible_base_p			(tree, tree, bool);
 extern tree lookup_base                         (tree, tree, base_access,
-						 base_kind *, tsubst_flags_t);
+						 base_kind *, tsubst_flags_t,
+						 HOST_WIDE_INT = -1);
 extern tree dcast_base_hint			(tree, tree);
 extern int accessible_p				(tree, tree, bool);
 extern int accessible_in_template_p		(tree, tree);
diff --git a/gcc/cp/constexpr.cc b/gcc/cp/constexpr.cc
index 37d1c444c9e..70dd6cf4d90 100644
--- a/gcc/cp/constexpr.cc
+++ b/gcc/cp/constexpr.cc
@@ -5452,7 +5452,7 @@ cxx_fold_indirect_ref_1 (const constexpr_ctx *ctx, location_t loc, tree type,
 	 which is likely to be a waste of time (109678).  */
       if (is_empty_class (type)
 	  && CLASS_TYPE_P (optype)
-	  && DERIVED_FROM_P (type, optype))
+	  && lookup_base (optype, type, ba_any, NULL, tf_none, off))
 	{
 	  if (empty_base)
 	    *empty_base = true;
diff --git a/gcc/cp/search.cc b/gcc/cp/search.cc
index 3f521b3bd72..cd80f285ac9 100644
--- a/gcc/cp/search.cc
+++ b/gcc/cp/search.cc
@@ -56,6 +56,7 @@ static tree dfs_get_pure_virtuals (tree, void *);
 
 struct lookup_base_data_s
 {
+  HOST_WIDE_INT offset; /* Offset we want, or -1 if any.  */
   tree t;		/* type being searched.  */
   tree base;		/* The base type we're looking for.  */
   tree binfo;		/* Found binfo.  */
@@ -74,6 +75,22 @@ dfs_lookup_base (tree binfo, void *data_)
 {
   struct lookup_base_data_s *data = (struct lookup_base_data_s *) data_;
 
+  if (data->offset != -1)
+    {
+      /* We're looking for the type at a particular offset.  */
+      int comp = compare_tree_int (BINFO_OFFSET (binfo), data->offset);
+      if (comp > 0)
+	/* Don't bother looking into bases laid out later; even if they
+	   do virtually inherit from the base we want, we can get there
+	   by another path.  */
+	return dfs_skip_bases;
+      else if (comp != 0
+	       && SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), data->base))
+	/* Right type, wrong offset.  */
+	return dfs_skip_bases;
+      /* Fall through.  */
+    }
+
   if (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), data->base))
     {
       if (!data->binfo)
@@ -190,7 +207,7 @@ accessible_base_p (tree t, tree base, bool consider_local_p)
 /* Lookup BASE in the hierarchy dominated by T.  Do access checking as
    ACCESS specifies.  Return the binfo we discover.  If KIND_PTR is
    non-NULL, fill with information about what kind of base we
-   discovered.
+   discovered.  If OFFSET is other than -1, only match at that offset.
 
    If the base is inaccessible, or ambiguous, then error_mark_node is
    returned.  If the tf_error bit of COMPLAIN is not set, no error
@@ -198,7 +215,8 @@ accessible_base_p (tree t, tree base, bool consider_local_p)
 
 tree
 lookup_base (tree t, tree base, base_access access,
-	     base_kind *kind_ptr, tsubst_flags_t complain)
+	     base_kind *kind_ptr, tsubst_flags_t complain,
+	     HOST_WIDE_INT offset /* = -1 */)
 {
   tree binfo;
   tree t_binfo;
@@ -246,8 +264,9 @@ lookup_base (tree t, tree base, base_access access,
       data.base = base;
       data.binfo = NULL_TREE;
       data.ambiguous = data.via_virtual = false;
-      data.repeated_base = CLASSTYPE_REPEATED_BASE_P (t);
+      data.repeated_base = (offset == -1) && CLASSTYPE_REPEATED_BASE_P (t);
       data.want_any = access == ba_any;
+      data.offset = offset;
 
       dfs_walk_once (t_binfo, dfs_lookup_base, NULL, &data);
       binfo = data.binfo;
-- 
2.31.1