diff options
Diffstat (limited to 'gcc/compare-types.c')
-rw-r--r-- | gcc/compare-types.c | 457 |
1 files changed, 457 insertions, 0 deletions
diff --git a/gcc/compare-types.c b/gcc/compare-types.c new file mode 100644 index 00000000000..4be9d28151d --- /dev/null +++ b/gcc/compare-types.c @@ -0,0 +1,457 @@ +#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" +#include "types-inlines.h" +#include "name-types.h" + +static bool +is_incomplete_type(const_tree a) +{ + gcc_assert(a); + const_tree type_size = TYPE_SIZE(a); + return NULL_TREE == type_size; +} + +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; +} + +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); + 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_VALUE(parm_a); + const_tree parm_type_b = TREE_VALUE(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); + +bool +eq_pointer(const_tree a, const_tree b) +{ + return a == b; +} + +bool +eq_identifier(const_tree a, const_tree b) +{ + std::string name_a = get_type_identifier(a); + std::string name_b = get_type_identifier(b); + return name_a.compare(name_b) == 0; +} + +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) + { + //FIXME: Just because two codes are the same + //doesn't mean they are the same type + //E.g. short != int + // float != double + // enum a != enum b + 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; +} + +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_type_compare(const_tree a, const_tree b) +{ + return eq_types(a, b); +} + +bool +eq_type_structural(const_tree a, const_tree b) +{ + return eq_types(a, b, true); +} + +bool +eq_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + // This should be before comparing incomplete types. + // This is not enabled by default, and it is used for + // testing structural equality limitations. + if (force_structural) return eq_structural(a, b, force_structural); + + // eq_structural (a-incomplete, a-complete) = false + // eq_main_variant(a-incomplete, a-complete) = false + // eq_canonical (a-incomplete, a-complete) = false + // Fallback to eq_identifier only here. + // This should be the only static call to eq_identifier! + const bool is_a_incomplete = is_incomplete_type(a); + const bool is_b_incomplete = is_incomplete_type(b); + const bool compare_incomplete_types = is_a_incomplete || is_b_incomplete; + if (compare_incomplete_types) return eq_identifier(a, b); + + + if (eq_main_variant(a, b)) return true; + + if (!eq_canonical(a, b)) return false; + + // optimistic... + // maybe we should have a MAYBE? + //gcc_unreachable(); + return false; +} + +namespace test_type_equality { + +static void +test_main_variant() +{ + tree void_a = make_node(VOID_TYPE); + tree void_b = build_variant_type_copy(void_a); + const bool expected = true; + const bool observed = eq_types(void_a, void_b); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_eq() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type; + tree pointer_b = build_variant_type_copy(pointer_a); + const bool expected = true; + const bool observed = eq_types(pointer_a, pointer_b); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_ne() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type_a = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type_a; + tree pointer_b = make_node(POINTER_TYPE); + tree inner_type_b = make_node(VOID_TYPE); + TREE_TYPE(pointer_b) = inner_type_b; + const bool expected = false; + const bool observed = eq_types(pointer_a, pointer_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_eq_structurally() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type_a = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type_a; + tree pointer_b = make_node(POINTER_TYPE); + tree inner_type_b = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_b) = inner_type_b; + const bool expected = true; + const bool observed = eq_types(pointer_a, pointer_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_void_eq() +{ + tree void_a = make_node(VOID_TYPE); + tree void_b = build_variant_type_copy(void_a); + const bool expected = true; + const bool observed = eq_types(void_a, void_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_structural_equality_different_types() +{ + tree type_a = make_node(VOID_TYPE); + tree type_b = make_node(RECORD_TYPE); + const bool expected = false; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_different_record_types() +{ + tree type_a = make_node(RECORD_TYPE); + tree type_b = make_node(RECORD_TYPE); + tree field_a = make_node(FIELD_DECL); + tree field_b = make_node(FIELD_DECL); + tree type_field_a = make_node(VOID_TYPE); + tree type_field_b = make_node(RECORD_TYPE); + TREE_TYPE(field_a) = type_field_a; + TREE_TYPE(field_b) = type_field_b; + TYPE_FIELDS(type_a) = field_a; + TYPE_FIELDS(type_b) = field_b; + const bool expected = false; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_same_record_types() +{ + tree type_a = make_node(RECORD_TYPE); + tree field_a = make_node(FIELD_DECL); + tree type_field_a = make_node(VOID_TYPE); + TREE_TYPE(field_a) = type_field_a; + TYPE_FIELDS(type_a) = field_a; + tree type_b = build_variant_type_copy(type_a); + const bool expected = true; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +void +run_tests() +{ + test_main_variant(); + test_void_eq(); + test_structural_equality_different_types(); + test_different_record_types(); + test_same_record_types(); + test_pointer_types_eq_structurally(); + test_pointer_types_ne(); + test_pointer_types_eq(); + +} +} // test_type_equality |