c23: aliasing of compatible tagged types

Tell the backend which types are equivalent by setting
TYPE_CANONICAL to one struct in the set of equivalent
structs.  Structs are considered equivalent by ignoring
all sizes of arrays nested in types below field level.

The following two structs are incompatible and lvalues
with these types can be assumed not to alias:

 struct foo { int a[3]; };
 struct foo { int a[4]; };

The following two structs are also incompatible, but
will get the same TYPE_CANONICAL and it is then not
exploited that lvalues with those types can not alias:

 struct bar { int (*p)[3]; };
 struct bar { int (*p)[4]; };

The reason is that both are compatible to

 struct bar { int (*p)[]; };

and therefore are in the same equivalence class.  For
the same reason all enums with the same underyling type
are in the same equivalence class.  Tests are added
for the expected aliasing behavior with optimization.

gcc/c:
	* c-decl.cc (c_struct_hasher): Hash stable for struct
	types.
	(c_struct_hasher::hash, c_struct_hasher::equal): New
	functions.
	(finish_struct): Set TYPE_CANONICAL to first struct in
	equivalence class.
	* c-objc-common.cc (c_get_alias_set): Let structs or
	unions with variable size alias anything.
	* c-tree.h (comptypes_equiv): New prototype.
	* c-typeck.cc (comptypes_equiv): New function.
	(comptypes_internal): Implement equivalence mode.
	(tagged_types_tu_compatible): Implement equivalence mode.

gcc/testsuite:
	* gcc.dg/c23-tag-2.c: Activate.
	* gcc.dg/c23-tag-5.c: Activate.
	* gcc.dg/c23-tag-alias-1.c: New test.
	* gcc.dg/c23-tag-alias-2.c: New test.
	* gcc.dg/c23-tag-alias-3.c: New test.
	* gcc.dg/c23-tag-alias-4.c: New test.
	* gcc.dg/c23-tag-alias-5.c: New test.
	* gcc.dg/gnu23-tag-alias-1.c: New test.
	* gcc.dg/gnu23-tag-alias-2.c: New test.
	* gcc.dg/gnu23-tag-alias-3.c: New test.
	* gcc.dg/gnu23-tag-alias-4.c: New test.
	* gcc.dg/gnu23-tag-alias-5.c: New test.
	* gcc.dg/gnu23-tag-alias-6.c: New test.
	* gcc.dg/gnu23-tag-alias-7.c: New test.

4 files changed, 87 insertions, 1 deletions

diff --git a/gcc/c/c-decl.cc b/gcc/c/c-decl.cc
index 26188aa..6639ec3 100644
--- a/gcc/c/c-decl.cc
+++ b/gcc/c/c-decl.cc
@@ -634,6 +634,36 @@ public:
   auto_vec<tree> typedefs_seen;
 };
 
+
+/* Hash table for structs and unions.  */
+struct c_struct_hasher : ggc_ptr_hash<tree_node>
+{
+  static hashval_t hash (tree t);
+  static bool equal (tree, tree);
+};
+
+/* Hash an RECORD OR UNION.  */
+hashval_t
+c_struct_hasher::hash (tree type)
+{
+  inchash::hash hstate;
+
+  hstate.add_int (TREE_CODE (type));
+  hstate.add_object (TYPE_NAME (type));
+
+  return hstate.end ();
+}
+
+/* Compare two RECORD or UNION types.  */
+bool
+c_struct_hasher::equal (tree t1,  tree t2)
+{
+  return comptypes_equiv_p (t1, t2);
+}
+
+/* All tagged typed so that TYPE_CANONICAL can be set correctly.  */
+static GTY (()) hash_table<c_struct_hasher> *c_struct_htab;
+
 /* Information for the struct or union currently being parsed, or
    NULL if not parsing a struct or union.  */
 static class c_struct_parse_info *struct_parse_info;
@@ -8713,7 +8743,8 @@ parser_xref_tag (location_t loc, enum tree_code code, tree name,
   ref = lookup_tag (code, name, has_enum_type_specifier, &refloc);
 
   /* If the visble type is still being defined, see if there is
-     an earlier definition (which may be complete).  */
+     an earlier definition (which may be complete).  We do not
+     have to loop because nested redefinitions are not allowed.  */
   if (flag_isoc23 && ref && C_TYPE_BEING_DEFINED (ref))
     {
       tree vis = previous_tag (ref);
@@ -9661,6 +9692,24 @@ finish_struct (location_t loc, tree t, tree fieldlist, tree attributes,
 
   C_TYPE_BEING_DEFINED (t) = 0;
 
+  /* Set type canonical based on equivalence class.  */
+  if (flag_isoc23)
+    {
+      if (NULL == c_struct_htab)
+	c_struct_htab = hash_table<c_struct_hasher>::create_ggc (61);
+
+      hashval_t hash = c_struct_hasher::hash (t);
+
+      tree *e = c_struct_htab->find_slot_with_hash (t, hash, INSERT);
+      if (*e)
+	TYPE_CANONICAL (t) = *e;
+      else
+	{
+	  TYPE_CANONICAL (t) = t;
+	  *e = t;
+	}
+    }
+
   tree incomplete_vars = C_TYPE_INCOMPLETE_VARS (TYPE_MAIN_VARIANT (t));
   for (x = TYPE_MAIN_VARIANT (t); x; x = TYPE_NEXT_VARIANT (x))
     {
diff --git a/gcc/c/c-objc-common.cc b/gcc/c/c-objc-common.cc
index 53eda7f..a394627 100644
--- a/gcc/c/c-objc-common.cc
+++ b/gcc/c/c-objc-common.cc
@@ -422,6 +422,11 @@ c_get_alias_set (tree t)
   if (TREE_CODE (t) == ENUMERAL_TYPE)
     return get_alias_set (ENUM_UNDERLYING_TYPE (t));
 
+  /* Structs with variable size can alias different incompatible
+     structs.  Let them alias anything.   */
+  if (RECORD_OR_UNION_TYPE_P (t) && C_TYPE_VARIABLE_SIZE (t))
+    return 0;
+
   return c_common_get_alias_set (t);
 }
 
diff --git a/gcc/c/c-tree.h b/gcc/c/c-tree.h
index 54f1353..02a09e5 100644
--- a/gcc/c/c-tree.h
+++ b/gcc/c/c-tree.h
@@ -759,6 +759,7 @@ extern tree require_complete_type (location_t, tree);
 extern bool same_translation_unit_p (const_tree, const_tree);
 extern int comptypes (tree, tree);
 extern bool comptypes_same_p (tree, tree);
+extern bool comptypes_equiv_p (tree, tree);
 extern int comptypes_check_different_types (tree, tree, bool *);
 extern int comptypes_check_enum_int (tree, tree, bool *);
 extern bool c_mark_addressable (tree, bool = false);
diff --git a/gcc/c/c-typeck.cc b/gcc/c/c-typeck.cc
index 0dbb0b4..1c81729 100644
--- a/gcc/c/c-typeck.cc
+++ b/gcc/c/c-typeck.cc
@@ -1063,6 +1063,7 @@ struct comptypes_data {
   bool different_types_p;
   bool warning_needed;
   bool anon_field;
+  bool equiv;
 
   const struct tagged_tu_seen_cache* cache;
 };
@@ -1123,6 +1124,21 @@ comptypes_check_different_types (tree type1, tree type2,
 
   return ret ? (data.warning_needed ? 2 : 1) : 0;
 }
+
+
+/* Like comptypes, but if it returns nonzero for struct and union
+   types considered equivalent for aliasing purposes.  */
+
+bool
+comptypes_equiv_p (tree type1, tree type2)
+{
+  struct comptypes_data data = { };
+  data.equiv = true;
+  bool ret = comptypes_internal (type1, type2, &data);
+
+  return ret;
+}
+
 
 /* Return true if TYPE1 and TYPE2 are compatible types for assignment
    or various other operations.  If they are compatible but a warning may
@@ -1250,6 +1266,9 @@ comptypes_internal (const_tree type1, const_tree type2,
 
 	if ((d1 == NULL_TREE) != (d2 == NULL_TREE))
 	  data->different_types_p = true;
+	/* Ignore size mismatches.  */
+	if (data->equiv)
+	  return true;
 	/* Sizes must match unless one is missing or variable.  */
 	if (d1 == NULL_TREE || d2 == NULL_TREE || d1 == d2)
 	  return true;
@@ -1467,6 +1486,9 @@ tagged_types_tu_compatible_p (const_tree t1, const_tree t2,
 	if (list_length (TYPE_FIELDS (t1)) != list_length (TYPE_FIELDS (t2)))
 	  return false;
 
+	if (data->equiv && (C_TYPE_VARIABLE_SIZE (t1) || C_TYPE_VARIABLE_SIZE (t2)))
+	  return false;
+
 	for (s1 = TYPE_FIELDS (t1), s2 = TYPE_FIELDS (t2);
 	     s1 && s2;
 	     s1 = DECL_CHAIN (s1), s2 = DECL_CHAIN (s2))
@@ -1486,6 +1508,15 @@ tagged_types_tu_compatible_p (const_tree t1, const_tree t2,
 		&& simple_cst_equal (DECL_FIELD_BIT_OFFSET (s1),
 				     DECL_FIELD_BIT_OFFSET (s2)) != 1)
 	      return false;
+
+	    tree st1 = TYPE_SIZE (TREE_TYPE (s1));
+	    tree st2 = TYPE_SIZE (TREE_TYPE (s2));
+
+	    if (data->equiv
+		&& st1 && TREE_CODE (st1) == INTEGER_CST
+		&& st2 && TREE_CODE (st2) == INTEGER_CST
+		&& !tree_int_cst_equal (st1, st2))
+	     return false;
 	  }
 	return true;