[PATCH][RFC] Improve get_qualified_type linear list walk

[Jeff Law]

On 4/16/19 6:55 AM, Richard Biener wrote:
> 
> 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  <rguenther@suse.de>
> 
> 	* tree.c (get_qualified_type): Put found type variants at the
> 	head of the variant list.
Seems quite reasonable to me.   I just hope we don't find a case where
this is the exact worst case behavior ;-)

jeff