path: root/gcc/compare-types.c

#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;
}

unsigned
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;
}

unsigned
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);

unsigned
eq_pointer(const_tree a, const_tree b)
{
  return a == b;
}

unsigned
eq_identifier(const_tree a, const_tree b)
{
  // TODO: Note, we have had the following miscomparison:
  // comparing 0,0: {} == 0,64:void_type*
  // since at least one of these two types is incomplete
  // and both lack an identifier...
  std::string name_a = get_type_identifier(a);
  std::string name_b = get_type_identifier(b);
  const int length_a = name_a.length();
  const int length_b = name_b.length();
  const bool is_sound_input = length_a > 0 || length_b > 0;
  const bool retval = is_sound_input && name_a.compare(name_b) == 0;
  return retval;
}

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;
}

unsigned
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;
}


unsigned
eq_type_compare(const_tree a, const_tree b)
{
  return eq_types(a, b);
}

unsigned
eq_type_structural(const_tree a, const_tree b)
{
  return eq_types(a, b, true);
}

unsigned
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);


  // Main variant is unreliable when we are comparing builtin types?
  // comparing 0,64: {}* == 0,64:__gcov_info {0,32:integer_type;8,72: {}*;16,48:integer_type;24,88:integer_type*;32,544:void_type(0,64:integer_type*, 0,32:integer_type, 0,0:void_type)*[];96,128:integer_type;104,168:__gcov_fn_info {0,64: {}*;8,40:integer_type;12,44:integer_type;16,48:integer_type;24,280:__gcov_ctr_info {0,32:integer_type;8,72:integer_type*;}[];}**;}*
  if (eq_main_variant(a, b) && eq_structural(a, b)) return true;  

  if (!eq_canonical(a, b)) return false;

  // optimistic...
  // maybe we should have a MAYBE?
  return eq_structural(a, b);
}

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