Created attachment 54873 [details]
invalid_reduction.ii

meh, the reduction cvise just finished with is invalid, but it does trigger the ICE still. I'll include it and try refine it now.

command line that in the end needed to reproduce with the original non-reduced testcase:
-std=c++14  -march=znver3 -O2 -fno-strict-aliasing -Wall

Note you need all of those options to get the ICE.

I almost want to say there is some GC issue going on with the original testcase.
When I tried to use topformflat with the source (with all the "^# " lines removed), it no longer ICEs. But then again I did get a note about -flarge-source-files which might causing a warning not to be tried which is exposing the ICE.

Anyways I am trying to reduce this using delta with a script which tests if it passes no options (except -Wfatal-errors to speed up the testing); that should reduce it to a valid testcase I hope.

>'g++-13 -O2 -Wall -c ArithmeticSubtermGeneralization.ii' is enough to reproduce.

Interesting because it was not for me, but I noticed that removing all of the lines that begin with "#" is able to reproduce without any options only. Anyways my current reproducing script is:
```
if !(~/upstream-gcc/libexec/gcc/x86_64-pc-linux-gnu/13.0.1/cc1plus -std=c++14 -fno-checking -quiet -Wfatal-errors $1 >& file1.out); then
  exit 1
fi
if !(~/upstream-gcc/libexec/gcc/x86_64-pc-linux-gnu/13.0.1/cc1plus -std=c++14 -quiet -Wfatal-errors $1 >& file.out); then
  if grep "hashtab_chk_error" file.out >&/dev/null; then
    exit 0
  fi
  exit 1
fi
if !(~/upstream-gcc/libexec/gcc/x86_64-pc-linux-gnu/13.0.1/cc1plus -std=c++14  -march=znver3 -O2 -fno-strict-aliasing -Wall -quiet -Wfatal-errors $1 >& file1.out); then
  if grep "hashtab_chk_error" file1.out >&/dev/null; then
    exit 0
  fi
  exit 1
fi
```

Yes it is more complex than a standard one would be because I want to reduce it to be a valid testcase (the first run of cc1plus) and then I noticed sometimes it reproduces with slightly different options so test with those.
Hopefully the -fno-checking is enough to force not checking hashtable checking ...

(In reply to Andrew Pinski from comment #5)
> >'g++-13 -O2 -Wall -c ArithmeticSubtermGeneralization.ii' is enough to reproduce.
> 
> Interesting because it was not for me, but I noticed that removing all of
> the lines that begin with "#" is able to reproduce without any options only.
> Anyways my current reproducing script is:
> ```
> if !(~/upstream-gcc/libexec/gcc/x86_64-pc-linux-gnu/13.0.1/cc1plus
> -std=c++14 -fno-checking -quiet -Wfatal-errors $1 >& file1.out); then
>   exit 1
> fi
> if !(~/upstream-gcc/libexec/gcc/x86_64-pc-linux-gnu/13.0.1/cc1plus
> -std=c++14 -quiet -Wfatal-errors $1 >& file.out); then
>   if grep "hashtab_chk_error" file.out >&/dev/null; then
>     exit 0
>   fi
>   exit 1
> fi
> if !(~/upstream-gcc/libexec/gcc/x86_64-pc-linux-gnu/13.0.1/cc1plus
> -std=c++14  -march=znver3 -O2 -fno-strict-aliasing -Wall -quiet
> -Wfatal-errors $1 >& file1.out); then
>   if grep "hashtab_chk_error" file1.out >&/dev/null; then
>     exit 0
>   fi
>   exit 1
> fi
> ```
> 
> Yes it is more complex than a standard one would be because I want to reduce
> it to be a valid testcase (the first run of cc1plus) and then I noticed
> sometimes it reproduces with slightly different options so test with those.
> Hopefully the -fno-checking is enough to force not checking hashtable
> checking ...

You can achieve result with the following command with C-Vise:
cvise -c 'timeout 5 g++ -std=c++14  -march=znver3 -O2 -fno-strict-aliasing -Wall ArithmeticSubtermGeneralization.ii -w -Wfatal-errors 2>&1 | grep hashtab_chk_error && timeout 5 g++-13 ArithmeticSubtermGeneralization.ii -c -Wfatal-errors -w' ArithmeticSubtermGeneralization.ii

I'm currently reducing that right now..

(In reply to Martin Liška from comment #6)
> You can achieve result with the following command with C-Vise:
> cvise -c 'timeout 5 g++ -std=c++14  -march=znver3 -O2 -fno-strict-aliasing
> -Wall ArithmeticSubtermGeneralization.ii -w -Wfatal-errors 2>&1 | grep
> hashtab_chk_error && timeout 5 g++-13 ArithmeticSubtermGeneralization.ii -c
> -Wfatal-errors -w' ArithmeticSubtermGeneralization.ii
> 
> I'm currently reducing that right now..

No that is different because it only says if it reproduces with those specific options which it does not have to.

timeout 5 g++ -std=c++14 -w -Wfatal-errors -fno-checking && (( timeout 5 g++ -std=c++14 ArithmeticSubtermGeneralization.ii -w -Wfatal-errors 2>&1 | grep  hashtab_chk_error) || (timeout 5 g++ -std=c++14  -march=znver3 -O2 -fno-strict-aliasing -Wall ArithmeticSubtermGeneralization.ii -w -Wfatal-errors 2>&1 | grep  hashtab_chk_error))

is the more correct way of reducing it similar to my script :).

> is the more correct way of reducing it similar to my script :).

Sure, this is better not to rely on specific options.

Anyway, reduced to:

$ cat ArithmeticSubtermGeneralization.ii
template <class> using no_ref_t = int *;
template <class Arr, template <class> class ref_t>
struct ArrayishObjectIterator {
  typedef ref_t<typename Arr::_ElementType> _ElementType;
};
struct MappingIterator {
  typedef int *_ElementType;
};
template <class Iter> struct IterTraits {
  IterTraits<MappingIterator> map() {}
  template <template <class> class Container>
  Container<typename Iter::_ElementType> collect();
};
struct Clause {
  typedef int _ElementType;
};
IterTraits<ArrayishObjectIterator<Clause, no_ref_t>> __trans_tmp_3;

$ g++ ArithmeticSubtermGeneralization.ii -c -w
hash table checking failed: equal operator returns true for a pair of values with a different hash value
ArithmeticSubtermGeneralization.ii: In instantiation of ‘struct IterTraits<ArrayishObjectIterator<Clause, no_ref_t> >’:
ArithmeticSubtermGeneralization.ii:17:54:   required from here
ArithmeticSubtermGeneralization.ii:12:42: internal compiler error: in hashtab_chk_error, at hash-table.cc:137
   12 |   Container<typename Iter::_ElementType> collect();
      |                                          ^~~~~~~
0x92d1bd hashtab_chk_error()
	/home/marxin/Programming/gcc/gcc/hash-table.cc:137
0xb668b2 hash_table<ctp_hasher, false, xcallocator>::verify(tree_node* const&, unsigned int)
	/home/marxin/Programming/gcc/gcc/hash-table.h:1118
0xb668b2 hash_table<ctp_hasher, false, xcallocator>::find_slot_with_hash(tree_node* const&, unsigned int, insert_option)
	/home/marxin/Programming/gcc/gcc/hash-table.h:1046
0xb1ede9 hash_table<ctp_hasher, false, xcallocator>::find_slot(tree_node* const&, insert_option)
	/home/marxin/Programming/gcc/gcc/hash-table.h:435
0xb1ede9 canonical_type_parameter(tree_node*)
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:4536
0xb2e141 tsubst(tree_node*, tree_node*, int, tree_node*)
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:16298
0xb33018 tsubst_function_type
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:15649
0xb2cb3b tsubst(tree_node*, tree_node*, int, tree_node*)
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:16468
0xb4e3b9 tsubst_function_decl
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:14419
0xb51060 tsubst_template_decl
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:14730
0xb2faba tsubst_decl
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:14892
0xb5e566 instantiate_class_template(tree_node*)
	/home/marxin/Programming/gcc/gcc/cp/pt.cc:12338
0xbb0be8 complete_type(tree_node*)
	/home/marxin/Programming/gcc/gcc/cp/typeck.cc:138
0x9d5494 start_decl_1(tree_node*, bool)
	/home/marxin/Programming/gcc/gcc/cp/decl.cc:6002
0x9d5494 start_decl_1(tree_node*, bool)
	/home/marxin/Programming/gcc/gcc/cp/decl.cc:5981
0x9f5507 start_decl(cp_declarator const*, cp_decl_specifier_seq*, int, tree_node*, tree_node*, tree_node**)
	/home/marxin/Programming/gcc/gcc/cp/decl.cc:5968
0xaf8431 cp_parser_init_declarator
	/home/marxin/Programming/gcc/gcc/cp/parser.cc:22910
0xacf278 cp_parser_simple_declaration
	/home/marxin/Programming/gcc/gcc/cp/parser.cc:15403
0xb03bf3 cp_parser_declaration
	/home/marxin/Programming/gcc/gcc/cp/parser.cc:15089
0xb0473a cp_parser_toplevel_declaration
	/home/marxin/Programming/gcc/gcc/cp/parser.cc:15110
Please submit a full bug report, with preprocessed source (by using -freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

Started with r13-3292-gc2565a31c1622a.

Slightly cleaned up:

template <class>
using A = int *;
template <class T, template <class> class U>
struct B { typedef U <typename T::type> type; };
struct C { typedef int *type; };
template <class T>
struct D {
  D <C> foo () { return D <C> (); }
  template <template <class> class U>
  U <typename T::type> bar ();
};
struct E { typedef int type; };
D <B <E, A>> d;

As no floating point types are involved, I think this had to be latent before.

Better don't reuse U for two different parameters:
template <class>
using A = int *;
template <class T, template <class> class U>
struct B { typedef U <typename T::type> type; };
struct C { typedef int *type; };
template <class T>
struct D {
  D <C> foo () { return D <C> (); }
  template <template <class> class V>
  V <typename T::type> bar ();
};
struct E { typedef int type; };
D <B <E, A>> d;

The ICE is on
(gdb) p debug_tree (*entry)
 <bound_template_template_parm 0x7fffea2f01f8 V type_0 type_6 VOID
    align:8 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea2f01f8
    args <tree_vec 0x7fffea2f10c0 length:1
        elt:0 <pointer_type 0x7fffea2ed1f8 type type <integer_type 0x7fffea14f5e8 int>
            unsigned DI
            size <integer_cst 0x7fffea12cfc0 constant 64>
            unit-size <integer_cst 0x7fffea12cfd8 constant 8>
            align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea157b28>>
   index 0 level 1 orig_level 2
    chain <type_decl 0x7fffea2ebed8 V>>
$14 = void
(gdb) p debug_tree (comparable)
 <bound_template_template_parm 0x7fffea2f8540 V type_0 type_6 VOID
    align:8 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea2eda80
    args <tree_vec 0x7fffea2f16a0 length:1
        elt:0 <pointer_type 0x7fffea2f87e0 type type <integer_type 0x7fffea14f5e8 int>
            unsigned DI
            size <integer_cst 0x7fffea12cfc0 constant 64>
            unit-size <integer_cst 0x7fffea12cfd8 constant 8>
            align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea157b28>>
   index 0 level 1 orig_level 2
    chain <type_decl 0x7fffea2f2850 V>>
$15 = void
Both of these BOUND_TEMPLATE_TEMPLARE_PARMs are created in
#4  0x0000000001462bbc in copy_node (node=<bound_template_template_parm 0x7fffea2eda80 V>) at ../../gcc/tree.cc:1334
#5  0x00000000005d9d68 in copy_type (type=<bound_template_template_parm 0x7fffea2eda80 V>) at ../../gcc/cp/lex.cc:1067
#6  0x0000000000767b5f in tsubst (t=<bound_template_template_parm 0x7fffea2eda80 V>, args=<tree_vec 0x7fffea2cec60>, complain=1, in_decl=<function_decl 0x7fffea2da700 bar>)
    at ../../gcc/cp/pt.cc:16262
#7  0x0000000000765155 in tsubst_function_type (t=<method_type 0x7fffea2edbd0>, args=<tree_vec 0x7fffea2cec60>, complain=1, in_decl=<function_decl 0x7fffea2da700 bar>)
    at ../../gcc/cp/pt.cc:15649
#8  0x00000000007687af in tsubst (t=<method_type 0x7fffea2edbd0>, args=<tree_vec 0x7fffea2cec60>, complain=1, in_decl=<function_decl 0x7fffea2da700 bar>) at ../../gcc/cp/pt.cc:16468
#9  0x000000000075afd2 in tsubst_function_decl (t=<function_decl 0x7fffea2da700 bar>, args=<tree_vec 0x7fffea2cec60>, complain=1, lambda_fntype=<tree 0x0>)
    at ../../gcc/cp/pt.cc:14419
#10 0x000000000075df67 in tsubst_template_decl (t=<template_decl 0x7ffff7ffa700 bar>, args=<tree_vec 0x7fffea2cec60>, complain=1, lambda_fntype=<tree 0x0>)
    at ../../gcc/cp/pt.cc:14730
#11 0x00000000007613a1 in tsubst_decl (t=<template_decl 0x7ffff7ffa700 bar>, args=<tree_vec 0x7fffea2cec60>, complain=1) at ../../gcc/cp/pt.cc:14892
#12 0x0000000000765f8e in tsubst (t=<template_decl 0x7ffff7ffa700 bar>, args=<tree_vec 0x7fffea2cec60>, complain=1, in_decl=<tree 0x0>) at ../../gcc/cp/pt.cc:15933
and
#4  0x0000000001462bbc in copy_node (node=<bound_template_template_parm 0x7fffea2eda80 V>) at ../../gcc/tree.cc:1334
#5  0x00000000005d9d68 in copy_type (type=<bound_template_template_parm 0x7fffea2eda80 V>) at ../../gcc/cp/lex.cc:1067
#6  0x0000000000767b5f in tsubst (t=<bound_template_template_parm 0x7fffea2eda80 V>, args=<tree_vec 0x7fffea2f1400>, complain=1, in_decl=<function_decl 0x7fffea2da700 bar>)
    at ../../gcc/cp/pt.cc:16262
#7  0x0000000000765155 in tsubst_function_type (t=<method_type 0x7fffea2edbd0>, args=<tree_vec 0x7fffea2f1400>, complain=1, in_decl=<function_decl 0x7fffea2da700 bar>)
    at ../../gcc/cp/pt.cc:15649
#8  0x00000000007687af in tsubst (t=<method_type 0x7fffea2edbd0>, args=<tree_vec 0x7fffea2f1400>, complain=1, in_decl=<function_decl 0x7fffea2da700 bar>) at ../../gcc/cp/pt.cc:16468
#9  0x000000000075afd2 in tsubst_function_decl (t=<function_decl 0x7fffea2da700 bar>, args=<tree_vec 0x7fffea2f1400>, complain=1, lambda_fntype=<tree 0x0>)
    at ../../gcc/cp/pt.cc:14419
#10 0x000000000075df67 in tsubst_template_decl (t=<template_decl 0x7ffff7ffa700 bar>, args=<tree_vec 0x7fffea2f1400>, complain=1, lambda_fntype=<tree 0x0>)
    at ../../gcc/cp/pt.cc:14730
#11 0x00000000007613a1 in tsubst_decl (t=<template_decl 0x7ffff7ffa700 bar>, args=<tree_vec 0x7fffea2f1400>, complain=1) at ../../gcc/cp/pt.cc:14892
#12 0x0000000000765f8e in tsubst (t=<template_decl 0x7ffff7ffa700 bar>, args=<tree_vec 0x7fffea2f1400>, complain=1, in_decl=<tree 0x0>) at ../../gcc/cp/pt.cc:15933
The first one being bar instantiation with C arg, the latter with B arg.

When hashing those, the difference is in
    if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
      val = iterative_hash_template_arg (TYPE_TI_ARGS (t), val);
which is a TREE_VEC containing
 <pointer_type 0x7fffea2ed1f8 type
    type <integer_type 0x7fffea14f5e8 int public type_6 SI
        size <integer_cst 0x7fffea151210 constant 32>
        unit-size <integer_cst 0x7fffea151228 constant 4>
        align:32 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea14f5e8 precision:32 min <integer_cst 0x7fffea1511c8 -2147483648> max <integer_cst 0x7fffea1511e0 2147483647>
        pointer_to_this <pointer_type 0x7fffea157b28>>
    unsigned DI
    size <integer_cst 0x7fffea12cfc0 type <integer_type 0x7fffea14f0a8 bitsizetype> constant 64>
    unit-size <integer_cst 0x7fffea12cfd8 type <integer_type 0x7fffea14f000 sizetype> constant 8>
    align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea157b28>
in one case and
 <pointer_type 0x7fffea2f87e0 type
    type <integer_type 0x7fffea14f5e8 int public type_6 SI
        size <integer_cst 0x7fffea151210 constant 32>
        unit-size <integer_cst 0x7fffea151228 constant 4>
        align:32 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea14f5e8 precision:32 min <integer_cst 0x7fffea1511c8 -2147483648> max <integer_cst 0x7fffea1511e0 2147483647>
        pointer_to_this <pointer_type 0x7fffea157b28>>
    unsigned DI
    size <integer_cst 0x7fffea12cfc0 type <integer_type 0x7fffea14f0a8 bitsizetype> constant 64>
    unit-size <integer_cst 0x7fffea12cfd8 type <integer_type 0x7fffea14f000 sizetype> constant 8>
    align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x7fffea157b28>
in another.
In the second case it triggers
      if (tree ats = alias_template_specialization_p (arg, nt_transparent))
        {
          // We want an alias specialization that survived strip_typedefs
          // to hash differently from its TYPE_CANONICAL, to avoid hash
          // collisions that compare as different in template_args_equal.
          // These could be dependent specializations that strip_typedefs
          // left alone, or untouched specializations because
          // coerce_template_parms returns the unconverted template
          // arguments if it sees incomplete argument packs.
          tree ti = TYPE_ALIAS_TEMPLATE_INFO (ats);
          return hash_tmpl_and_args (TI_TEMPLATE (ti), TI_ARGS (ti));
        }
in iterative_hash_template_arg, while in the first case it doesn't and it gets
        default:
          if (tree canonical = TYPE_CANONICAL (arg))
            val = iterative_hash_object (TYPE_HASH (canonical), val);
and so they hash differently.  But apparently structural_comptypes thinks they are equal.

I suppose we're just neglecting to canonicalize a bound ttp's substituted args before determining its canonical type.  Adding a call to coerce_template_parms or canonicalize_type_argument seems to fix it:

diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
index fcc8e0d1d57..5ff91414f69 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -16285,9 +16285,18 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
                      return error_mark_node;
                    tree argvec = tsubst (TI_ARGS (tinfo), args,
                                          complain, in_decl);
+                   // this fixes it
+                   tree tparms = DECL_INNERMOST_TEMPLATE_PARMS (tmpl);
+                   argvec = coerce_template_parms (tparms, argvec,
+                                                   tmpl, complain);
                    if (argvec == error_mark_node)
                      return error_mark_node;
 
+                   // or this
+                   for (tree& arg : tree_vec_range (argvec))
+                     if (TYPE_P (arg))
+                       arg = canonicalize_type_argument (arg, complain);
+
                    TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (r)
                      = build_template_info (tmpl, argvec);
                  }

The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:2245459c85a3f4cde3d33bf3e4edaff08f3b2404

commit r14-11-g2245459c85a3f4cde3d33bf3e4edaff08f3b2404
Author: Patrick Palka <ppalka@redhat.com>
Date:   Mon Apr 17 18:52:07 2023 -0400

    c++: bound ttp level lowering [PR109531]
    
    Here when level lowering the bound ttp TT<typename T::type> via the
    substitution T=C, we're neglecting to canonicalize (and thereby strip
    of simple typedefs) the substituted template arguments {A<int>} before
    determining the new canonical type via hash table lookup.  This leads to
    a hash mismatch ICE for the two equivalent types TT<int> and TT<A<int>>
    since iterative_hash_template_arg assumes type arguments are already
    canonicalized.
    
    We can fix this by canonicalizing or coercing the substituted arguments
    directly, but seeing as creation and ordinary substitution of bound ttps
    both go through lookup_template_class, which in turn performs the desired
    coercion/canonicalization, it seems preferable to make this code path go
    through lookup_template_class as well.
    
            PR c++/109531
    
    gcc/cp/ChangeLog:
    
            * pt.cc (tsubst) <case BOUND_TEMPLATE_TEMPLATE_PARM>:
            In the level-lowering case just use lookup_template_class
            to rebuild the bound ttp.
    
    gcc/testsuite/ChangeLog:
    
            * g++.dg/template/canon-type-20.C: New test.
            * g++.dg/template/ttp36.C: New test.

The releases/gcc-13 branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:c895eb11c8c95aa5714fa4043194b1001336567e

commit r13-7208-gc895eb11c8c95aa5714fa4043194b1001336567e
Author: Patrick Palka <ppalka@redhat.com>
Date:   Mon Apr 17 18:52:07 2023 -0400

    c++: bound ttp level lowering [PR109531]
    
    Here when level lowering the bound ttp TT<typename T::type> via the
    substitution T=C, we're neglecting to canonicalize (and thereby strip
    of simple typedefs) the substituted template arguments {A<int>} before
    determining the new canonical type via hash table lookup.  This leads to
    a hash mismatch ICE for the two equivalent types TT<int> and TT<A<int>>
    since iterative_hash_template_arg assumes type arguments are already
    canonicalized.
    
    We can fix this by canonicalizing or coercing the substituted arguments
    directly, but seeing as creation and ordinary substitution of bound ttps
    both go through lookup_template_class, which in turn performs the desired
    coercion/canonicalization, it seems preferable to make this code path go
    through lookup_template_class as well.
    
            PR c++/109531
    
    gcc/cp/ChangeLog:
    
            * pt.cc (tsubst) <case BOUND_TEMPLATE_TEMPLATE_PARM>:
            In the level-lowering case just use lookup_template_class
            to rebuild the bound ttp.
    
    gcc/testsuite/ChangeLog:
    
            * g++.dg/template/canon-type-20.C: New test.
            * g++.dg/template/ttp36.C: New test.
    
    (cherry picked from commit 2245459c85a3f4cde3d33bf3e4edaff08f3b2404)

Fixed for GCC 13.