Adds compare types

2 files changed, 285 insertions, 0 deletions

diff --git a/gcc/compare-types.c b/gcc/compare-types.c
new file mode 100644
index 00000000000..61a43d8c408
--- /dev/null
+++ b/gcc/compare-types.c
@@ -0,0 +1,273 @@
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple-expr.h"
+#include "predict.h"
+#include "alloc-pool.h"
+#include "tree-pass.h"
+#include "cgraph.h"
+#include "diagnostic.h"
+#include "fold-const.h"
+#include "gimple-fold.h"
+#include "symbol-summary.h"
+#include "tree-vrp.h"
+#include "ipa-prop.h"
+#include "tree-pretty-print.h"
+#include "tree-inline.h"
+#include "ipa-fnsummary.h"
+#include "ipa-utils.h"
+#include "tree-ssa-ccp.h"
+#include "stringpool.h"
+#include "attribs.h"
+#include "tree-ssa-alias.h"
+#include "tree-ssanames.h"
+#include "gimple.h"
+#include "cfg.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+
+#include "compare-types.h"
+
+static bool
+eq_main_variant(const_tree a, const_tree b)
+{
+  gcc_assert(a && b);
+  const_tree main_variant_a = TYPE_MAIN_VARIANT(a);
+  const_tree main_variant_b = TYPE_MAIN_VARIANT(b);
+  gcc_assert(main_variant_a && main_variant_b);
+  const bool are_equal = main_variant_a == main_variant_b;
+  return are_equal;
+}
+
+static bool
+eq_canonical_internal(const_tree a, const_tree b)
+{
+  gcc_assert(a && b);
+  const_tree canonical_a = TYPE_CANONICAL(a);
+  const_tree canonical_b = TYPE_CANONICAL(b);
+  gcc_assert(canonical_a && canonical_b);
+  const bool are_equal = canonical_a == canonical_b;
+  return are_equal;
+}
+
+static bool
+eq_record_or_union_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+
+  tree field_a = TYPE_FIELDS(a);
+  tree field_b = TYPE_FIELDS(b);
+  while (field_a || field_b)
+  {
+    const bool different_lengths = (bool)field_a != (bool)field_b;
+    if (different_lengths) return false;
+
+    const_tree field_type_a = TREE_TYPE(field_a);
+    const_tree field_type_b = TREE_TYPE(field_b);
+    gcc_assert(field_type_a && field_type_b);
+    const bool same_field_types = eq_types(field_type_a, field_type_b, force_structural);
+    if (!same_field_types) return false;
+
+    field_a = DECL_CHAIN(field_a);
+    field_b = DECL_CHAIN(field_b);
+  }
+
+  return true;
+}
+
+static bool
+eq_record_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, RECORD_TYPE);
+  assert_is_type(b, RECORD_TYPE);
+  return eq_record_or_union_types(a, b, force_structural);
+}
+
+static bool
+eq_union_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, UNION_TYPE);
+  assert_is_type(b, UNION_TYPE);
+  return eq_record_or_union_types(a, b, force_structural);
+}
+
+static bool
+eq_wrapper_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  const_tree inner_type_a = TREE_TYPE(a);
+  const_tree inner_type_b = TREE_TYPE(b);
+  gcc_assert(inner_type_a && inner_type_b);
+  return eq_types(inner_type_a, inner_type_b, force_structural);
+}
+
+static bool
+eq_pointer_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, POINTER_TYPE);
+  assert_is_type(b, POINTER_TYPE);
+  return eq_wrapper_types(a, b, force_structural);
+}
+
+static bool
+eq_reference_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, REFERENCE_TYPE);
+  assert_is_type(b, REFERENCE_TYPE);
+  return eq_wrapper_types(a, b, force_structural);
+}
+
+static bool
+eq_array_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, ARRAY_TYPE);
+  assert_is_type(b, ARRAY_TYPE);
+  return eq_wrapper_types(a, b, force_structural);
+}
+
+static bool
+eq_function_or_method_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  const_tree return_type_a = TREE_TYPE(a);
+  const_tree return_type_b = TREE_TYPE(b);
+  const bool is_return_equal = eq_types(return_type_a, return_type_b, force_structural);
+  if (!is_return_equal) return false;
+
+  tree parm_a = TYPE_ARG_TYPES(a);
+  tree parm_b = TYPE_ARG_TYPES(b);
+
+  while (parm_a || parm_b)
+  {
+    const bool different_lengths = (bool)parm_a != (bool)parm_b;
+    if (different_lengths) return false;
+
+    const_tree parm_type_a = TREE_TYPE(parm_a);
+    const_tree parm_type_b = TREE_TYPE(parm_b);
+    gcc_assert(parm_type_a && parm_type_b);
+    const bool same_field_types = eq_types(parm_type_a, parm_type_b, force_structural);
+    if (!same_field_types) return false;
+
+    parm_a = TREE_CHAIN(parm_a);
+    parm_b = TREE_CHAIN(parm_b);
+  }
+
+  return true;
+}
+
+static bool
+eq_function_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, FUNCTION_TYPE);
+  assert_is_type(b, FUNCTION_TYPE);
+  return eq_function_or_method_types(a, b, force_structural);
+}
+
+static bool
+eq_method_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  assert_is_type(a, METHOD_TYPE);
+  assert_is_type(b, METHOD_TYPE);
+
+  const_tree base_type_a = TYPE_METHOD_BASETYPE(a);
+  const_tree base_type_b = TYPE_METHOD_BASETYPE(b);
+  const bool eq_base_types = eq_types(base_type_a, base_type_b, force_structural);
+  return eq_base_types && eq_function_or_method_types(a, b, force_structural);
+}
+
+static bool eq_structural(const_tree a, const_tree b, const bool force_structural = false);
+
+static bool
+eq_structural(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  const enum tree_code code_a = TREE_CODE(a);
+  const enum tree_code code_b = TREE_CODE(b);
+  const bool equal_code = code_a == code_b;
+  if (!equal_code) return false;
+
+  const enum tree_code code = code_a;
+  switch (code)
+  {
+    case VOID_TYPE: 
+    case INTEGER_TYPE: 
+    case REAL_TYPE: 
+    case FIXED_POINT_TYPE:
+    case COMPLEX_TYPE:
+    case ENUMERAL_TYPE:
+    case BOOLEAN_TYPE:
+    case OFFSET_TYPE:
+      return true;
+    break;
+    default:
+    break;
+  }
+
+  switch (code)
+  {
+    case RECORD_TYPE:
+      return eq_record_types(a, b, force_structural);
+    break;
+    case POINTER_TYPE:
+      return eq_pointer_types(a, b, force_structural);
+    break;
+    case REFERENCE_TYPE:
+      return eq_reference_types(a, b, force_structural);
+    break;
+    case ARRAY_TYPE:
+      return eq_array_types(a, b, force_structural);
+    break;
+    case UNION_TYPE:
+      return eq_union_types(a, b, force_structural);
+    break;
+    case FUNCTION_TYPE:
+      return eq_function_types(a, b, force_structural);
+    break;
+    case METHOD_TYPE:
+      return eq_method_types(a, b, force_structural);
+    break;
+    case QUAL_UNION_TYPE:
+    case LANG_TYPE:
+    default:
+      // Unimplemented
+      gcc_unreachable();
+    break;
+  }
+
+  gcc_unreachable();
+  return false;
+}
+
+static bool
+eq_canonical(const_tree a, const_tree b)
+{
+  gcc_assert(a && b);
+  const bool struct_eq_a = TYPE_STRUCTURAL_EQUALITY_P(a);
+  const bool struct_eq_b = TYPE_STRUCTURAL_EQUALITY_P(b);
+  const bool use_structural_equality = struct_eq_a || struct_eq_b;
+  const bool are_equal = use_structural_equality ? eq_structural(a, b) : eq_canonical_internal(a, b);
+  return are_equal;
+}
+
+bool
+eq_types(const_tree a, const_tree b, const bool force_structural)
+{
+  gcc_assert(a && b);
+  if (force_structural) return eq_structural(a, b, force_structural);
+
+  if (eq_main_variant(a, b)) return true;  
+  if (!eq_canonical(a, b)) return false;
+
+  // optimistic...
+  gcc_unreachable();
+  return false;
+}
diff --git a/gcc/compare-types.h b/gcc/compare-types.h
new file mode 100644
index 00000000000..ca7251109a6
--- /dev/null
+++ b/gcc/compare-types.h
@@ -0,0 +1,12 @@
+#pragma once
+
+inline
+void assert_is_type(const_tree a, const enum tree_code expected_code)
+{
+  gcc_assert(a);
+  const enum tree_code observed_code = TREE_CODE(a);
+  const bool eq_codes = observed_code == expected_code;
+  gcc_assert(eq_codes);
+}
+
+extern bool eq_types(const_tree a, const_tree b, const bool force_structural = false);