path: root/gcc/collect-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"
#include <set>

#include "collect-types.h"

static bool filter_boring_types(const_tree type, ptrset_t &);

static bool
filter_boring_types_wrapper(const_tree type, ptrset_t &types)
{
  gcc_assert(type);
  const_tree inner_type = TREE_TYPE(type);
  gcc_assert(inner_type);
  return filter_boring_types(inner_type, types);
}

static bool
filter_boring_types_array(const_tree type, ptrset_t &types)
{
  assert_is_type(type, ARRAY_TYPE);
  return filter_boring_types_wrapper(type, types);
}

static bool
filter_boring_types_reference(const_tree type, ptrset_t &types)
{
  assert_is_type(type, REFERENCE_TYPE);
  return filter_boring_types_wrapper(type, types);
}

static bool
filter_boring_types_pointer(const_tree type, ptrset_t &types)
{
  assert_is_type(type, POINTER_TYPE);
  return filter_boring_types_wrapper(type, types);
}

static bool
filter_boring_types_record(const_tree type, ptrset_t &types)
{
  assert_is_type(type, RECORD_TYPE);
  return false;
}

static bool
filter_boring_types_unions(const_tree type, ptrset_t &types)
{
  const enum tree_code code = TREE_CODE(type);
  const bool is_union = UNION_TYPE == code;
  const bool is_qual_union = QUAL_UNION_TYPE == code;
  const bool is_valid_input = is_union || is_qual_union;
  gcc_assert(is_valid_input);

  for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field))
  {
    const_tree field_type = TREE_TYPE(field);
    gcc_assert(field_type);
    const bool is_boring = filter_boring_types(field_type, types);
    if (!is_boring) return is_boring;
  }

  return true;
}

static bool
filter_boring_types_union(const_tree type, ptrset_t &types)
{
  assert_is_type(type, UNION_TYPE);
  return filter_boring_types_unions(type, types);
}

static bool
filter_boring_types_qual_union(const_tree type, ptrset_t &types)
{
  assert_is_type(type, QUAL_UNION_TYPE);
  return filter_boring_types_unions(type, types);
}

static bool
filter_boring_types_function_or_method(const_tree type, ptrset_t &types)
{
  const enum tree_code code = TREE_CODE(type);
  const bool is_function = FUNCTION_TYPE == code;
  const bool is_method = METHOD_TYPE == code;
  const bool is_valid_input = is_function || is_method;
  gcc_assert(is_valid_input);

  const_tree ret_type = TREE_TYPE(type);
  gcc_assert(ret_type);
  const bool retval_is_boring = filter_boring_types(ret_type, types);
  if (!retval_is_boring) return retval_is_boring;

  tree arg_node = TYPE_ARG_TYPES(type);
  while (NULL_TREE != arg_node)
  {
     tree arg_node_type = TREE_VALUE(arg_node);
     gcc_assert(arg_node_type);
     const bool arg_is_boring = filter_boring_types(arg_node_type, types);
     arg_node = TREE_CHAIN(arg_node);
     if (!arg_is_boring) return arg_is_boring;
  }

  return true;
}

static bool
filter_boring_types_function(const_tree type, ptrset_t &types)
{
  assert_is_type(type, FUNCTION_TYPE);
  return filter_boring_types_function_or_method(type, types);
}

static bool
filter_boring_types_method(const_tree type, ptrset_t &types)
{
  assert_is_type(type, METHOD_TYPE);
  return filter_boring_types_function_or_method(type, types);
}

static bool
filter_boring_types(const_tree type, ptrset_t &types)
{
  // boring types are those that do not point to
  // a struct
  gcc_assert(type);
  
  // Optimization to speed up the filter.
  // Memoization
  const bool seen_before = types.in_universe(type);
  if (seen_before)
  {
     const bool in_points_to_record = types.in_points_to_record(type);
     const bool in_complement = types.in_complement(type);
     const bool _xor = in_points_to_record != in_complement;
     gcc_assert(_xor);
     return in_complement;
  }


  bool is_boring = true;
  enum tree_code code = TREE_CODE(type);
  switch (code)
  {
    case ARRAY_TYPE:
      is_boring = filter_boring_types_array(type, types);
    break;
    case RECORD_TYPE:
      is_boring = filter_boring_types_record(type, types);
    break;
    case UNION_TYPE:
      is_boring = filter_boring_types_union(type, types);
    break;
    case QUAL_UNION_TYPE:
      is_boring = filter_boring_types_qual_union(type, types);
    break;
    case REFERENCE_TYPE:
      is_boring = filter_boring_types_reference(type, types);
    break;
    case POINTER_TYPE:
      is_boring = filter_boring_types_pointer(type, types);
    break;
    case FUNCTION_TYPE:
      is_boring = filter_boring_types_function(type, types);
    break;
    case METHOD_TYPE:
      is_boring = filter_boring_types_method(type, types);
    break;
    default:
      // I will probably need to fuzz.
    break;
  }

  // This should be one the two only times we call insert!
  types.insert(type, !is_boring);

  return is_boring;
}

static const unsigned filter_buffer_size = 1;
typedef bool (*filter_t)(const_tree, ptrset_t&);
const extern filter_t filter[filter_buffer_size] =
{
  filter_boring_types,
};

static void
collect_types_from_record_or_union_type(const_tree type, ptrset_t &types)
{
  gcc_assert(type);
  const enum tree_code code = TREE_CODE(type);
  const bool is_union = UNION_TYPE == code;
  const bool is_record = RECORD_TYPE == code;
  const bool is_valid_input = is_union || is_record;
  gcc_assert(is_valid_input);

  for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field))
  {
    const_tree field_type = TREE_TYPE(field);
    gcc_assert(field_type);
    collect_types(field_type, types);
  }
}

static void
collect_types_from_record_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, RECORD_TYPE);
  collect_types_from_record_or_union_type(type, types);
}

static void
collect_types_from_union_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, UNION_TYPE);
  collect_types_from_record_or_union_type(type, types);
}

static void
collect_types_from_wrapper_type(const_tree type, ptrset_t &types)
{
  gcc_assert(type);
  const_tree inner_type = TREE_TYPE(type);
  gcc_assert(inner_type);
  collect_types(inner_type, types);
}

static void
collect_types_from_pointer_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, POINTER_TYPE);
  collect_types_from_wrapper_type(type, types);
}

static void
collect_types_from_reference_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, REFERENCE_TYPE);
  collect_types_from_wrapper_type(type, types);
}

static void
collect_types_from_array_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, ARRAY_TYPE);
  collect_types_from_wrapper_type(type, types);
}

static void
collect_types_from_function_or_method_type(const_tree type, ptrset_t &types)
{
  gcc_assert(type);
  const enum tree_code code = TREE_CODE(type);
  const bool is_function = FUNCTION_TYPE == code;
  const bool is_method = METHOD_TYPE == code;
  const bool is_valid_input = is_function || is_method;
  gcc_assert(is_valid_input);

  const_tree ret_type = TREE_TYPE(type);
  gcc_assert(ret_type);
  collect_types(ret_type, types);

  tree arg_node = TYPE_ARG_TYPES(type);
  while (NULL_TREE != arg_node)
  {
     tree arg_node_type = TREE_VALUE(arg_node);
     gcc_assert(arg_node_type);
     collect_types(arg_node_type, types);
     arg_node = TREE_CHAIN(arg_node);
  }
}

static void
collect_types_from_function_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, FUNCTION_TYPE);
  collect_types_from_function_or_method_type(type, types);
}

static void
collect_types_from_method_type(const_tree type, ptrset_t &types)
{
  assert_is_type(type, METHOD_TYPE);
  collect_types_from_function_or_method_type(type, types);
}

void
points_to_record_sets_s::insert(const_tree type, bool in_points_to_record)
{
  gcc_assert(type);
  this->universe.insert(type);
  in_points_to_record ? this->points_to_record.insert(type) : this->complement.insert(type);
  // let's just double check...
  const bool in_points_to_set = this->in_points_to_record(type);
  const bool in_complement = this->in_complement(type);
  const bool _xor = in_points_to_set != in_complement;
  gcc_assert(_xor);
}

bool
points_to_record_sets_s::in_universe(const_tree type) const
{
  gcc_assert(type);
  const bool seen_before = this->universe.find(type) != this->universe.end();
  return seen_before;
}

bool
points_to_record_sets_s::in_points_to_record(const_tree type) const
{
  gcc_assert(type);
  const bool seen_before = this->points_to_record.find(type) != this->points_to_record.end();
  return seen_before;
}

bool
points_to_record_sets_s::in_complement(const_tree type) const
{
  gcc_assert(type);
  const bool seen_before = this->complement.find(type) != this->complement.end();
  return seen_before;
}

void
collect_types(const_tree type, ptrset_t &types)
{
  if (!type) return;

  // This should be the only case we call to find if
  // we have seen the type before!
  const bool in_set = types.in_universe(type);
  // memoized.
  if (in_set) return;

  // we should have filters here
  // such that if we are processing a type
  // which we know somehow that it is not a type we are interested
  // then we just return immediately.
  // maybe even add it to a set of blacklisted types so that we
  // memoize and do things faster...
  bool is_boring = false;
  for (unsigned i = 0; i < filter_buffer_size; i++)
  {
    is_boring |= filter[i](type, types);
  }

  const enum tree_code code = TREE_CODE(type);
  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:
       // simple cases and we want to allow them
    break;
    case RECORD_TYPE:
       collect_types_from_record_type(type, types);
    break;
    case POINTER_TYPE:
       collect_types_from_pointer_type(type, types);
    break;
    case REFERENCE_TYPE:
       collect_types_from_reference_type(type, types);
    break;
    case ARRAY_TYPE:
       collect_types_from_array_type(type, types);
    break;
    case UNION_TYPE:
       collect_types_from_union_type(type, types);
    break;
    case FUNCTION_TYPE:
       collect_types_from_function_type(type, types);
    break;
    case METHOD_TYPE:
       collect_types_from_method_type(type, types);
    break;
    case QUAL_UNION_TYPE:
    case LANG_TYPE:
    default:
      log("%s\n", get_tree_code_name(code));
      gcc_unreachable();
    break;
  }

  // This should be one the two only times we call insert!
  types.insert(type, !is_boring);
}