path: root/gcc/ipa-prototype.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" // needed for gimple-iterator.h
#include "gimple-iterator.h"
#include "gimple-ssa.h"
#include <stdbool.h>


#include "types-inlines.h"
#include "name-types.h"
#include "compare-types.h"
#include "ipa-type-collector.h"
#include "ipa-prototype.h"
#include "type-collector.hpp"
#include "type-stringifier.hpp"
#include <map>
#include <vector>
#include "type-escaper.hpp"
#include "expr-escaper.hpp"

//#define OPTIMIZED
#define SANITY_CHECKS

typedef std::set<const_tree> undefset;

void
Reason::print() const
{
  if (!this->is_escaping) return;

  log("g=%d p=%d r=%d c=%d v=%d u=%d\n", this->global_is_visible, this->parameter_is_visible, this->return_is_visible, this->type_is_casted, this->type_is_volatile, this->type_is_in_union);
}

Reason
Reason::operator|(const Reason &other)
{
  Reason retval {}; 
  retval.is_escaping = this->is_escaping | other.is_escaping;
  retval.global_is_visible = this->global_is_visible | other.global_is_visible;
  retval.parameter_is_visible = this->parameter_is_visible | other.parameter_is_visible;
  retval.return_is_visible = this->return_is_visible | other.return_is_visible;
  retval.type_is_casted = this->type_is_casted | other.type_is_casted;
  retval.type_is_volatile = this->type_is_volatile | other.type_is_volatile;
  retval.type_is_in_union = this->type_is_in_union | other.type_is_in_union;
  return retval;
}

Reason&
Reason::operator|=(const Reason &other)
{
  this->is_escaping |= other.is_escaping;
  this->global_is_visible |= other.global_is_visible;
  this->parameter_is_visible |= other.parameter_is_visible;
  this->type_is_casted |= other.type_is_casted;
  this->type_is_volatile |= other.type_is_volatile;
  this->type_is_in_union |= other.type_is_in_union;
  return *this;
}


static inline void
assert_type_is_in_universe(const_tree type, ptrset_t &types)
{
#ifdef SANITY_CHECKS
  gcc_assert(types.in_universe(type));
#endif
}

static inline void
assert_type_is_in_ptrset(const_tree type, ptrset_t &types)
{
#ifdef SANITY_CHECKS
  gcc_assert(types.in_points_to_record(type));
#endif
}


static void update_escape_info( const_tree type, ptrset_t &types, Reason reason, typemap &calc);

static bool
is_variable_escaping(varpool_node *vnode)
{
  gcc_assert(vnode);
  return vnode->externally_visible;
}

static void update_escape_info_expr(ptrset_t &types, typemap &calc, const_tree expr, Reason reason);

static void
calculate_escaping_types_globals(ptrset_t &types, typemap &calc)
{
  varpool_node *vnode = NULL;
  FOR_EACH_VARIABLE(vnode)
  {
    bool is_escaping = is_variable_escaping(vnode);

#ifdef OPTIMIZED
    if (!is_escaping) continue;
#endif

    Reason reason {};  // Not sure why {} works but () doesn't... It believes it is a function?
    reason.is_escaping = is_escaping;
    reason.global_is_visible = is_escaping;
    update_escape_info_expr (types, calc, vnode->decl, reason);
  }
}

static bool 
filter_known_function(cgraph_node *node)
{
  gcc_assert(node);
  bool filter = false;
  const char *_free = "free";
  const char *_malloc = "malloc";
  const char *_realloc = "realloc";
  const char *_calloc = "calloc";
  const char *_memset = "memset";
  const char *name = node->name();
  gcc_assert(name);
  filter |= strcmp(_free, name) == 0;
  filter |= strcmp(_malloc, name) == 0;
  filter |= strcmp(_realloc, name) == 0;
  filter |= strcmp(_memset, name) == 0;
  filter |= strcmp(_calloc, name) == 0;
  return filter;
}

static bool 
is_function_escaping(cgraph_node *cnode)
{
  const bool filter = filter_known_function(cnode);
  if (filter) return false;

  gcc_assert(cnode);
  return cnode->externally_visible;
}

static void
mark_escaping_parameters(ptrset_t &types, typemap &calc, cgraph_node *cnode, Reason reason)
{
  gcc_assert(cnode);
  const_tree decl = cnode->decl;
  gcc_assert(decl);
  assert_is_type(decl, FUNCTION_DECL);
#ifdef OPTIMIZED
  if (!reason.is_escaping) return;
#endif

  update_escape_info_expr(types, calc, decl, reason);
}

static void
mark_escaping_return_type(ptrset_t &types, typemap &calc, cgraph_node *cnode, Reason reason)
{
  gcc_assert(cnode);
  const_tree decl = cnode->decl;
  gcc_assert(decl);
  assert_is_type(decl, FUNCTION_DECL);
#ifdef OPTIMIZED
  if (!reason.is_escaping) return;
#endif

  const_tree func_type = TREE_TYPE(decl);
  assert_is_type(func_type, FUNCTION_TYPE);
  const_tree ret_type = TREE_TYPE(func_type);
  gcc_assert(ret_type);
  update_escape_info(ret_type, types, reason, calc);
}

static void
mark_escaping_function(ptrset_t &types, typemap &calc, cgraph_node *cnode)
{
  gcc_assert(cnode);
  const bool is_escaping = is_function_escaping(cnode);
#ifdef OPTIMIZED
  if (!is_escaping) return;
#endif

  Reason reason1 {};
  reason1.is_escaping = is_escaping;
  reason1.parameter_is_visible = is_escaping;
  mark_escaping_parameters(types, calc, cnode, reason1);

  Reason reason2 {};
  reason2.is_escaping = is_escaping;
  reason2.return_is_visible = is_escaping;
  mark_escaping_return_type(types, calc, cnode, reason2);
}

static void
calculate_escaping_types_from_cast(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_ASSIGN);
  const_tree lhs = gimple_assign_lhs(stmt);
  gcc_assert(lhs);
  const_tree rhs = gimple_assign_rhs1(stmt);
  gcc_assert(rhs);
}

static void
calculate_escaping_types_from_assign_lhs(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_ASSIGN);
  const_tree lhs = gimple_assign_lhs(stmt);
  gcc_assert(lhs);
  Reason reason {};
  update_escape_info_expr(types, calc, lhs, reason);
}

static void
calculate_escaping_types_from_assign_rhs3(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_rhs_class(stmt, GIMPLE_TERNARY_RHS);
  const_tree rhs = gimple_assign_rhs3(stmt);
  gcc_assert(rhs);
  Reason reason {};
  update_escape_info_expr(types, calc, rhs, reason);
}

static void
calculate_escaping_types_from_assign_rhs2(ptrset_t &types, typemap &calc, gimple *stmt)
{
  const_tree rhs = gimple_assign_rhs2(stmt);
  gcc_assert(rhs);
  Reason reason {};
  update_escape_info_expr(types, calc, rhs, reason);
}

static void
calculate_escaping_types_from_assign_rhs1(ptrset_t &types, typemap &calc, gimple *stmt)
{
  const_tree rhs = gimple_assign_rhs1(stmt);
  gcc_assert(rhs);
  Reason reason {};
  update_escape_info_expr(types, calc, rhs, reason);
}

static void
calculate_escaping_types_from_assign(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_ASSIGN);
  calculate_escaping_types_from_assign_lhs(types, calc, stmt);
  // If it is a cast, we must look at the lhs and the rhs...
  const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt);
  switch(gclass)
  {
    case GIMPLE_TERNARY_RHS:
      calculate_escaping_types_from_assign_rhs3(types, calc, stmt);
    /* fall-through */
    case GIMPLE_BINARY_RHS:
      calculate_escaping_types_from_assign_rhs2(types, calc, stmt);
    /* fall-through */
    case GIMPLE_UNARY_RHS:
    case GIMPLE_SINGLE_RHS:
      calculate_escaping_types_from_assign_rhs1(types, calc, stmt);
      calculate_escaping_types_from_cast(types, calc, stmt);
    break;
    default:
    gcc_unreachable();
    break;
  }
}

static void
calculate_escaping_types_from_call_lhs(ptrset_t &types, typemap &calc, undefset &undef, gimple *stmt)
{
  gcall *call = dyn_cast<gcall*>(stmt);
  if (!call) return;

  const_tree lhs = gimple_call_lhs(stmt);
  if (!lhs) return;

  tree fn = gimple_call_fndecl(stmt);
  const bool is_undefined = undef.find(fn) != undef.end();
#ifdef OPTIMIZED
  if (!is_undefined) return;
#endif

  Reason reason {};
  reason.is_escaping = is_undefined;
  reason.return_is_visible = is_undefined;
  update_escape_info_expr(types, calc, lhs, reason);
}

static void
calculate_escaping_types_from_call_rhs(ptrset_t &types, typemap &calc, undefset &undef, gimple *stmt)
{

  tree fn = gimple_call_fndecl(stmt);
  const bool is_undefined = undef.find(fn) != undef.end();
#ifdef OPTIMIZED
  if (!is_undefined) return;
#endif

  //tree decl_name = DECL_NAME(fn);
  //const char* identifier = IDENTIFIER_POINTER(decl_name);
  // What about gcov?

  Reason reason {};
  reason.is_escaping = is_undefined;
  reason.parameter_is_visible = is_undefined;

  unsigned num_args = gimple_call_num_args(stmt);
  for (unsigned i = 0; i < num_args; i++)
  {
    const_tree arg_i = gimple_call_arg(stmt, i);
    gcc_assert(arg_i);
    const_tree type_i = TREE_TYPE(arg_i);
    update_escape_info(type_i, types, reason, calc);
  }
}

static void
calculate_escaping_types_from_call(ptrset_t &types, typemap &calc, undefset &undef, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_CALL);
  gcall *call = dyn_cast<gcall*>(stmt);
  tree fn = gimple_call_fndecl(stmt);

  const bool in_set = undef.find(fn) != undef.end();
#ifdef OPTIMIZED
  if (!in_set) return;
#endif
  
  calculate_escaping_types_from_call_lhs(types, calc, undef, stmt);
  calculate_escaping_types_from_call_rhs(types, calc, undef, stmt);
}

static void
calculate_escaping_types_from_cond_lhs(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_COND);
  const_tree lhs = gimple_cond_lhs(stmt);
  gcc_assert(lhs);
  Reason reason {};
  update_escape_info_expr(types, calc, lhs, reason);
}

static void
calculate_escaping_types_from_cond_rhs(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_COND);
  const_tree rhs = gimple_cond_rhs(stmt);
  Reason reason {};
  update_escape_info_expr(types, calc, rhs, reason);
}

static void
calculate_escaping_types_from_cond(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_COND);
  calculate_escaping_types_from_cond_lhs(types, calc, stmt);
  calculate_escaping_types_from_cond_rhs(types, calc, stmt);
}

static void
calculate_escaping_types_from_return(ptrset_t &types, typemap &calc, gimple *stmt)
{
  is_gimple_code(stmt, GIMPLE_RETURN);
  const_tree retval = gimple_return_retval(stmt);
  if (!retval) return;

  Reason reason {};
  update_escape_info_expr(types, calc, retval, reason);
}

static void
calculate_escaping_types_from_stmt(ptrset_t &types, typemap &calc, undefset &undef, gimple *stmt)
{
  // Should be the same as ipa-type-collector.c
  // Otherwise, we might be skipping exploring some paths...
  gcc_assert(stmt);
  const enum gimple_code code = gimple_code (stmt);
  switch (code)
  {
    case GIMPLE_ASSIGN:
      calculate_escaping_types_from_assign(types, calc, stmt);
    break;
    case GIMPLE_CALL:
      calculate_escaping_types_from_call(types, calc, undef, stmt);
    break;
    case GIMPLE_COND:
      calculate_escaping_types_from_cond(types, calc, stmt);
    break;
    case GIMPLE_RETURN:
      calculate_escaping_types_from_return(types, calc, stmt);
    break;
    case GIMPLE_LABEL:
    case GIMPLE_PREDICT:
    case GIMPLE_DEBUG:
    case GIMPLE_SWITCH:
#ifdef FUZZ_MODE
    gcc_unreachable();
#endif
    break;
    default:
    {
      const char* name = gimple_code_name[code];
      log("gimple code name %s\n", name);
      gcc_unreachable();
    }
    break;
  }
}

static void
calculate_escaping_types_from_bb(ptrset_t &types, typemap &calc, undefset &undef, basic_block bb)
{
  gcc_assert(bb);
  for (auto gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
  {
    gimple *stmt = gsi_stmt(gsi);
    calculate_escaping_types_from_stmt(types, calc, undef, stmt);
  }
}

static void
calculate_escaping_types_from_cnode(ptrset_t &types, typemap &calc, cgraph_node *cnode, undefset &undef)
{
  gcc_assert(cnode);
  cnode->get_untransformed_body();
  const_tree decl = cnode->decl;
  gcc_assert(decl);
  function *func = DECL_STRUCT_FUNCTION(decl);
  gcc_assert(func);
  basic_block bb = NULL;
  push_cfun(func);
  FOR_EACH_BB_FN(bb, func)
  {
    calculate_escaping_types_from_bb(types, calc, undef, bb);
  }
  pop_cfun();
}

static void
calculate_escaping_ssa_names(ptrset_t &types, typemap &calc, cgraph_node *cnode)
{
  gcc_assert(cnode);
  const_tree decl = cnode->decl;
  gcc_assert(decl);
  function *func = DECL_STRUCT_FUNCTION(decl);
  gcc_assert(func);
  size_t i = 0;
  tree ssa_name = NULL;
  push_cfun(func);
  Reason reason {};
  FOR_EACH_SSA_NAME(i, ssa_name, cfun)
  {
    gcc_assert(ssa_name);
    const_tree ssa_name_type = TREE_TYPE(ssa_name);
    update_escape_info(ssa_name_type, types, reason, calc);
  }
  pop_cfun();
}

static void
calculate_escaping_locals(ptrset_t &types, typemap &calc, cgraph_node *cnode)
{
  gcc_assert(cnode);
  const_tree decl = cnode->decl;
  gcc_assert(decl);
  function *func = DECL_STRUCT_FUNCTION(decl);
  gcc_assert(func);
  Reason reason {};
  const_tree func_type = TREE_TYPE(decl);
  assert_is_type(func_type, FUNCTION_TYPE);
  update_escape_info_expr(types, calc, decl, reason);
  if (types.in_points_to_record(func_type)) update_escape_info(func_type, types, reason, calc);
  int i = 0;
  tree var_decl = NULL;
  FOR_EACH_LOCAL_DECL(func, i, var_decl)
  {
    gcc_assert(var_decl);
    update_escape_info_expr(types, calc, var_decl, reason);
  }
}



static void
calculate_escaping_functions(ptrset_t &types, typemap &calc)
{
  cgraph_node *cnode = NULL;
  undefset undefined_functions;
  FOR_EACH_FUNCTION(cnode)
  {
    gcc_assert(cnode);
    const bool filter = filter_known_function(cnode);
    if (filter) continue;

    const_tree decl = cnode->decl;
    gcc_assert(decl);
    undefined_functions.insert(decl);
  }

  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(cnode)
  {
    gcc_assert(cnode);
    cnode->get_untransformed_body();
    const_tree decl = cnode->decl;
    gcc_assert(decl);
    undefined_functions.erase(decl);
    mark_escaping_function(types, calc, cnode);
    calculate_escaping_locals(types, calc, cnode);
    calculate_escaping_ssa_names(types, calc, cnode);
  }

  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(cnode)
  {
    gcc_assert(cnode);
    calculate_escaping_types_from_cnode(types, calc, cnode, undefined_functions);
  }
}

static void
calculate_escaping_types(ptrset_t &types, typemap &calc)
{
   calculate_escaping_types_globals(types, calc);
   calculate_escaping_functions(types, calc);
}

static void
print_escaping_types(typemap &calc)
{
  for (auto i = calc.cbegin(), e = calc.cend(); i != e; ++i)
  {
    const_tree type = i->first;
    const Reason reason = i->second;
    log ("escaping: %s (or %s) = %s\n", get_type_identifier(type).c_str(), type_to_string(type).c_str(), reason.is_escaping ? "true" : "false");
    reason.print();
  }
}

static void
place_escaping_types_in_set(ptrset_t &types, typemap &calc)
{
  for (auto i = calc.cbegin(), e = calc.cend(); i != e; ++i)
  {
    const_tree type = i->first;
    // We should have seen it before
    assert_type_is_in_universe(type, types);

    // We should only track interesting types
    // Types which are not in points_to_record are the ones
    // that are pointed to by records.
    // I think it is possible to prune them ahead of time...
    if (!types.in_points_to_record(type)) continue;

    const Reason reason = i->second;
    reason.is_escaping ? types.escaping.insert(type) : types.non_escaping.insert(type);
  }
}

static void
sanity_check_escape_xor_not(ptrset_t &types)
{
  for (auto i = types.escaping.cbegin(), e = types.escaping.cend(); i != e; ++i)
  {
    for (auto j = types.non_escaping.cbegin(), f = types.non_escaping.cend(); j != f; ++j)
    {
       const_tree type_esc = *i;
       gcc_assert(type_esc);
       const_tree type_non = *j;
       gcc_assert(type_non);
       //const bool valid_sets = !eq_type_compare(type_esc, type_non);
       //if (valid_sets) continue;
       //log("comparing %s == %s\n", type_to_string(type_esc).c_str(), type_to_string(type_non).c_str());
       //TODO: Remove this comment once we have restricted the "repairing" of sets a bit more.
       //gcc_assert(valid_sets);
    }
  }
}

static void
sanity_check_escape_union_not_equals_ptrset(ptrset_t &types)
{
  typeset _union;
  for (auto i = types.escaping.cbegin(), e = types.escaping.cend(); i != e; ++i)
  {
    const_tree type = *i;
    _union.insert(type);
  }

  for (auto i = types.non_escaping.cbegin(), e = types.non_escaping.cend(); i != e; ++i)
  {
    const_tree type = *i;
    _union.insert(type);
  }


  for (auto i = types.points_to_record.cbegin(), e = types.points_to_record.cend(); i != e; ++i)
  {
    const_tree type = *i;
    const bool in_union = _union.find(type) != _union.end();
    if (in_union) continue;
    //log("this type was not found in union %s\n", type_to_string(type).c_str());
    //TODO: FIXME: This has to be enabled for the sanity check to work
    //But at the moment there's one type which isn't working correctly :(
    gcc_unreachable();
  }

}

static void
fix_escaping_types_in_set(ptrset_t &types)
{
  bool fixed_point_reached = false;
  do {
    std::vector<const_tree> fixes;
    fixed_point_reached = true;
    for (auto i = types.escaping.cbegin(), e = types.escaping.cend(); i != e; ++i)
    {
      for (auto j = types.non_escaping.cbegin(), f = types.non_escaping.cend(); j != f; ++j)
      {
       const_tree type_esc = *i;
       gcc_assert(type_esc);
       const_tree type_non = *j;
       gcc_assert(type_non);
       // There can be cases where incomplete types are marked as non-escaping
       // and complete types counter parts are marked as escaping.
       //const bool interesting_case = eq_type_compare(type_esc, type_non);
       //TODO: We are going to need a different type comparison because this one
       //fails to take into account the recursion...
       const bool interesting_case = type_esc == type_non;
       if (!interesting_case) continue;

       TypeStringifier stringifier;
       std::string type_esc_name = stringifier.stringify(type_esc);
       std::string type_non_name = stringifier.stringify(type_non);
       log("**NOT** checking for incompleteness %s == %s\n", type_esc_name.c_str(), type_non_name.c_str());

       fixed_point_reached = false;
       // Add incomplete to escaping
       // delete incomplete from non_escaping
       // We shouldn't do that inside our iteration loop.
       fixes.push_back(type_non);
      }
    }

    for (auto i = fixes.cbegin(), e = fixes.cend(); i != e; ++i)
    {
      const_tree escaping_type = *i;
      types.escaping.insert(escaping_type);
      types.non_escaping.erase(escaping_type);
    }
  } while (!fixed_point_reached);
}

static void
print_escaping_types_in_set(ptrset_t &types)
{
  std::vector<const_tree> fixes;
  for (auto i = types.non_escaping.cbegin(), e = types.non_escaping.cend(); i != e; ++i)
  {
    const_tree type_non = *i;
    gcc_assert(type_non);
    const enum tree_code code = TREE_CODE(type_non);
    const bool is_function = FUNCTION_TYPE == code;
    // I just don't want to print out functions.
    if (is_function) continue;
    TypeStringifier stringifier;
    std::string name = stringifier.stringify(type_non);
    log("non_escaping: %s \n", name.c_str());
  }

}


ptrset_t *TypeEscaper::types = NULL;
typemap TypeEscaper::calc;
static TypeEscaper _typeEscaper;
static ExprEscaper exprEscaper;
TypeEscaper *ExprEscaper::typeEscaper = NULL;

static void
update_escape_info( const_tree type, ptrset_t &types, Reason reason, typemap &calc)
{
  _typeEscaper.update(type, reason);
}

static void
update_escape_info_expr(ptrset_t &types, typemap &calc, const_tree expr, Reason reason)
{
  exprEscaper.update(expr, reason);
}


static unsigned int
iphw_execute()
{
  ptrset_t types;
  TypeCollector::ptrset = &types;
  TypeEscaper::types = &types;
  ExprEscaper::typeEscaper = &_typeEscaper;
  collect_types(types);

  typemap eacalc; // Escape Analysis Calculation
  // Intermediate results
  // Do not read escape analysis results from here
  calculate_escaping_types(types, eacalc);
  place_escaping_types_in_set(types, _typeEscaper.calc);
  fix_escaping_types_in_set(types);
  print_escaping_types_in_set(types);
  sanity_check_escape_xor_not(types);
  sanity_check_escape_union_not_equals_ptrset(types);
  gcc_unreachable();
  return 0;
}

namespace {
const pass_data pass_data_ipa_prototype =
{
  SIMPLE_IPA_PASS,
  "prototype",
  OPTGROUP_NONE,
  TV_NONE,
  (PROP_cfg | PROP_ssa),
  0,
  0,
  0,
  0,
};

class pass_ipa_prototype : public simple_ipa_opt_pass
{
public:
  pass_ipa_prototype (gcc::context *ctx)
    : simple_ipa_opt_pass(pass_data_ipa_prototype, ctx)
  {}

  virtual bool gate(function*) { return flag_ipa_prototype; }
  virtual unsigned execute (function*) { return iphw_execute(); }
};
} // anon namespace

simple_ipa_opt_pass*
make_pass_ipa_prototype (gcc::context *ctx)
{
  return new pass_ipa_prototype (ctx);
}