[PATCH][RFC] Improve get_qualified_type linear list walk

[Richard Biener]

The following makes the C++ FEs heavy use of build_qualified_type
cheaper.  When looking at a tramp3d -fsyntax-only compile you can
see that for 470.000 build_qualified_type calls we end up
with 9.492.205 calls to check_qualified_type (thus we visit around
20 variant type candidates) ending up finding it in all but
15.300 cases that end up in build_variant_type_copy.

That's of course because the FE uses this machinery to do things like

bool
same_type_ignoring_top_level_qualifiers_p (tree type1, tree type2)
{
  if (type1 == error_mark_node || type2 == error_mark_node)
    return false;

  type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
  type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);
  return same_type_p (type1, type2);

but so it be.  The improvement is to re-organize get_qualified_type
to put found type variants on the head of the variant list.  This
improves the number of calls to check_qualified_type to 1.215.030
thus around 2.5 candidates.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Comments?  OK?

Richard.

2019-04-16  Richard Biener  <rguent...@suse.de>

        * tree.c (get_qualified_type): Put found type variants at the
        head of the variant list.

Index: gcc/tree.c
===================================================================
--- gcc/tree.c  (revision 270387)
+++ gcc/tree.c  (working copy)
@@ -6451,17 +6451,28 @@ check_aligned_type (const_tree cand, con
 tree
 get_qualified_type (tree type, int type_quals)
 {
-  tree t;
-
   if (TYPE_QUALS (type) == type_quals)
     return type;
 
+  tree mv = TYPE_MAIN_VARIANT (type);
+  if (check_qualified_type (mv, type, type_quals))
+    return mv;
+
   /* Search the chain of variants to see if there is already one there just
      like the one we need to have.  If so, use that existing one.  We must
      preserve the TYPE_NAME, since there is code that depends on this.  */
-  for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
-    if (check_qualified_type (t, type, type_quals))
-      return t;
+  for (tree *tp = &TYPE_NEXT_VARIANT (mv); *tp; tp = &TYPE_NEXT_VARIANT (*tp))
+    if (check_qualified_type (*tp, type, type_quals))
+      {
+       /* Put the found variant at the head of the variant list so
+          frequently searched variants get found faster.  The C++ FE
+          benefits greatly from this.  */
+       tree t = *tp;
+       *tp = TYPE_NEXT_VARIANT (t);
+       TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (mv);
+       TYPE_NEXT_VARIANT (mv) = t;
+       return t;
+      }
 
   return NULL_TREE;
 }