refactoring escape analysis

9 files changed, 488 insertions, 16 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 155612f0f2d..a9c188e6e03 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1399,6 +1399,7 @@ OBJS = \
 	incpath.o \
 	init-regs.o \
 	internal-fn.o \
+	ipa-hello-world.o \
 	ipa-type-collector.o \
 	compare-types.o \
 	collect-types.o \
diff --git a/gcc/collect-types.c b/gcc/collect-types.c
index 0ce6cccb025..200e5f16e98 100644
--- a/gcc/collect-types.c
+++ b/gcc/collect-types.c
@@ -222,7 +222,8 @@ collect_types_from_record_or_union_type(const_tree type, ptrset_t &types)
   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;
+  const bool is_qual_union = QUAL_UNION_TYPE == code;
+  const bool is_valid_input = is_record || is_union || is_qual_union;
   gcc_assert(is_valid_input);
 
   for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field))
diff --git a/gcc/collect-types.h b/gcc/collect-types.h
index 883c08d36dc..24d06c6b411 100644
--- a/gcc/collect-types.h
+++ b/gcc/collect-types.h
@@ -3,6 +3,7 @@
 #include "tree.h"
 #include <set>
 
+
 typedef std::set<const_tree> typeset;
 struct points_to_record_sets_s {
   typeset universe;  
diff --git a/gcc/common.opt b/gcc/common.opt
index 6a1ddeec87d..8de1d64dffe 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -3418,4 +3418,7 @@ Common Joined Report Var(flag_tp_types_compared) Init(0)
 ftp-comparison-functions=
 Common Joined Report Var(flag_tp_comparison_functions) Init(0)
 
+fipa-hello-world
+Common Report Var(flag_ipa_hello_world) Optimization
+TBD
 ; This comment is to ensure we retain the blank line above.
diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
new file mode 100644
index 00000000000..e35fdf01145
--- /dev/null
+++ b/gcc/ipa-hello-world.c
@@ -0,0 +1,449 @@
+#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 "gimple.h"
+#include "cfg.h" // needed for gimple-iterator.h
+#include "gimple-iterator.h"
+#include <stdbool.h>
+
+
+#include "types-inlines.h"
+#include "ipa-type-collector.h"
+#include "ipa-hello-world.h"
+#include <map>
+
+//#define OPTIMIZED
+#define SANITY_CHECKS
+
+typedef std::set<const_tree> undefset;
+
+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;
+}
+
+typedef std::map<const_tree, Reason> typemap;
+
+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_typemap(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  gcc_assert(type);
+  assert_type_is_in_universe(type, types);
+  assert_type_is_in_ptrset(type, types);
+  const bool already_in_typemap = calc.find(type) != calc.end();
+  already_in_typemap ? calc[type] |= reason : calc[type] = reason;
+}
+
+static void update_escape_info( const_tree type, ptrset_t &types, Reason reason, typemap &calc);
+
+static void
+update_escape_info_wrapper(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  gcc_assert(type);
+  update_typemap(type, types, reason, calc);
+  const_tree inner_type = TREE_TYPE(type);
+  update_escape_info(inner_type, types, reason, calc);
+}
+
+static void
+update_escape_info_array(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  assert_is_type(type, ARRAY_TYPE);
+  update_escape_info_wrapper(type, types, reason, calc);
+}
+
+static void
+update_escape_info_pointer(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  assert_is_type(type, POINTER_TYPE);
+  update_escape_info_wrapper(type, types, reason, calc);
+}
+
+static void
+update_escape_info_reference(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  assert_is_type(type, REFERENCE_TYPE);
+  update_escape_info_wrapper(type, types, reason, calc);
+}
+
+static void
+update_escape_info_record(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  assert_is_type(type, RECORD_TYPE);
+  update_typemap(type, types, reason, calc);
+  for (tree field = TYPE_FIELDS(type); field; field = DECL_CHAIN(field))
+  {
+    const_tree field_type = TREE_TYPE(field);
+    gcc_assert(field_type);
+    update_escape_info(field_type, types, reason, calc);
+  }
+}
+
+static void
+update_escape_info_union(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  assert_is_type(type, UNION_TYPE);
+  Reason inner_reason {};
+  inner_reason.type_is_in_union = true;
+  inner_reason.is_escaping = true;
+  inner_reason |= reason;
+
+  update_typemap(type, types, reason, calc);
+  for (tree field = TYPE_FIELDS(type); field; field = DECL_CHAIN(field))
+  {
+    const_tree field_type = TREE_TYPE(field);
+    gcc_assert(field_type);
+    // We cannot change type that are on the surface level
+    // of unions. (This is a type of casting).
+    // But we might be able to change the types which 
+    // are pointed by these types.
+    update_typemap(field_type, types, inner_reason, calc);
+    update_escape_info(field_type, types, reason, calc);
+  }
+}
+
+static void
+update_escape_info_qual_union(const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+  assert_is_type(type, QUAL_UNION_TYPE);
+  update_escape_info_union(type, types, reason, calc);
+}
+
+static void
+update_escape_info( const_tree type, ptrset_t &types, Reason reason, typemap &calc)
+{
+#ifdef OPTIMIZED
+  // if (!reason.is_escaping) return;
+  // Above not necessarily true, since we might point to a union
+  // and unions are illegal?
+  // instead use the following
+  const bool in_set = calc.find(type) != calc.end(type);
+  const bool will_not_escape = in_set && !reason.is_escaping;
+  if (will_not_escape) return;
+
+  const bool already_escaping = in_set && calc[type].is_escaping;
+  if (already_escaping) return;
+#endif
+
+  assert_type_is_in_universe(type, types);
+
+  bool is_interesting = types.in_points_to_record(type);
+  if (!is_interesting) return;
+
+  gcc_assert(type);
+  const enum tree_code code = TREE_CODE(type);
+  switch (code)
+  {
+    case ARRAY_TYPE:
+      update_escape_info_array(type, types, reason, calc);
+    break;
+    case RECORD_TYPE:
+      update_escape_info_record(type, types, reason, calc);
+    break;
+    case UNION_TYPE:
+      update_escape_info_union(type, types, reason, calc);
+    break;
+    case QUAL_UNION_TYPE:
+      update_escape_info_qual_union(type, types, reason, calc);
+    break;
+    case REFERENCE_TYPE:
+      update_escape_info_reference(type, types, reason, calc);
+    break;
+    case POINTER_TYPE:
+      update_escape_info_pointer(type, types, reason, calc);
+    break;
+    // I want to see if we see these and what it means for the code
+    case FUNCTION_TYPE:
+    // I think I can just pass the type here from cnode...
+    // and it should work fine?
+    case METHOD_TYPE:
+    default:
+    gcc_unreachable();
+    break;
+  }
+}
+
+
+static bool
+is_variable_escaping(varpool_node *vnode)
+{
+  gcc_assert(vnode);
+  return vnode->externally_visible;
+}
+
+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);
+    if (!is_escaping) return;
+
+    const_tree decl = vnode->decl;
+    gcc_assert(decl);
+    const_tree type = TREE_TYPE(decl);
+    gcc_assert(type);
+    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 (type, types, reason, calc);
+  }
+}
+
+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 *name = node->name();
+  // TODO: we want memset here...
+  // but we can't until we fix the sizeof tree...
+  gcc_assert(name);
+  filter |= strcmp(_free, name) == 0;
+  filter |= strcmp(_malloc, name) == 0;
+  filter |= strcmp(_realloc, name) == 0;
+  filter |= strcmp(_calloc, name) == 0;
+  return filter;
+}
+
+static bool 
+is_function_escaping(cgraph_node *cnode)
+{
+  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
+
+  function_args_iterator iter;
+  tree arg_type = NULL;
+  const_tree function_type = TREE_TYPE(decl);
+  gcc_assert(function_type);
+  FOREACH_FUNCTION_ARGS(function_type, arg_type, iter)
+  {
+    update_escape_info(arg_type, types, reason, calc);
+  }
+}
+
+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_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);
+  }
+}
+
+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_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);
+  }
+
+  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 unsigned int
+iphw_execute()
+{
+  ptrset_t types;
+  collect_types(types);
+
+  typemap eacalc; // Escape Analysis Calculation
+  // Intermediate results
+  // Do not read escape analysis results from here
+  calculate_escaping_types(types, eacalc);
+  fprintf(dump_file, "Hello world!");
+  return 0;
+}
+
+namespace {
+const pass_data pass_data_ipa_hello_world =
+{
+  SIMPLE_IPA_PASS,
+  "hello-world",
+  OPTGROUP_NONE,
+  TV_NONE,
+  (PROP_cfg | PROP_ssa),
+  0,
+  0,
+  0,
+  0,
+};
+
+class pass_ipa_hello_world : public simple_ipa_opt_pass
+{
+public:
+  pass_ipa_hello_world (gcc::context *ctx)
+    : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
+  {}
+
+  virtual bool gate(function*) { return flag_ipa_hello_world; }
+  virtual unsigned execute (function*) { return iphw_execute(); }
+};
+} // anon namespace
+
+simple_ipa_opt_pass*
+make_pass_ipa_hello_world (gcc::context *ctx)
+{
+  return new pass_ipa_hello_world (ctx);
+}
diff --git a/gcc/ipa-hello-world.h b/gcc/ipa-hello-world.h
new file mode 100644
index 00000000000..8c9ee83d14b
--- /dev/null
+++ b/gcc/ipa-hello-world.h
@@ -0,0 +1,14 @@
+#pragma once
+
+struct Reason {
+  bool is_escaping : 1;
+  bool global_is_visible : 1;
+  bool parameter_is_visible : 1;
+  bool return_is_visible : 1;
+  bool type_is_casted : 1;
+  bool type_is_volatile : 1;
+  bool type_is_in_union : 1;
+  Reason operator|(const Reason &); 
+  Reason& operator|=(const Reason &);
+  Reason() {};
+};
diff --git a/gcc/ipa-type-collector.c b/gcc/ipa-type-collector.c
index 69a3abac95a..2d3a74198c6 100644
--- a/gcc/ipa-type-collector.c
+++ b/gcc/ipa-type-collector.c
@@ -772,6 +772,21 @@ filter_out_types_in_set(ptrset_t &types)
 
 }
 
+static void
+sanity_check_ptr_xor_complement(ptrset_t &types)
+{
+  for (auto i = types.points_to_record.cbegin(); i != types.points_to_record.cend(); ++i)
+  {
+    for (auto j = types.complement.cbegin(); j != types.complement.cend(); ++j)
+    {
+       const_tree type_ptr = *i;
+       const_tree type_com = *j;
+       const bool valid_sets = !eq_type_compare(type_ptr, type_com);
+       gcc_assert(valid_sets);
+    }
+  }
+}
+
 void
 collect_types(ptrset_t &types)
 {
@@ -785,22 +800,9 @@ collect_types(ptrset_t &types)
     // We still need to collect types from
     // the function signatures of functions without gimple bodies...
   }
+  sanity_check_ptr_xor_complement(types);
 }
 
-static void
-sanity_check_ptr_xor_complement(ptrset_t &types)
-{
-  for (auto i = types.points_to_record.cbegin(); i != types.points_to_record.cend(); ++i)
-  {
-    for (auto j = types.complement.cbegin(); j != types.complement.cend(); ++j)
-    {
-       const_tree type_ptr = *i;
-       const_tree type_com = *j;
-       const bool valid_sets = !eq_type_compare(type_ptr, type_com);
-       gcc_assert(valid_sets);
-    }
-  }
-}
 
 static unsigned int
 iphw_execute()
@@ -809,7 +811,6 @@ iphw_execute()
   //test_naming_types::run_tests();
   ptrset_t types;
   collect_types(types);
-  sanity_check_ptr_xor_complement(types);
   filter_out_types_in_set(types);
   compare_types_in_set(types);
   return 0;
diff --git a/gcc/passes.def b/gcc/passes.def
index fe3f1c8ef35..fc9cc715148 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -150,6 +150,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_ipa_icf);
   NEXT_PASS (pass_ipa_devirt);
   NEXT_PASS (pass_ipa_type_collector);
+  NEXT_PASS (pass_ipa_hello_world);
   NEXT_PASS (pass_ipa_cp);
   NEXT_PASS (pass_ipa_sra);
   NEXT_PASS (pass_ipa_cdtor_merge);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index d36372993bb..4e142e357e0 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -502,6 +502,7 @@ extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
 extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context *ctxt);
 extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary (gcc::context *ctxt);
 extern simple_ipa_opt_pass *make_pass_ipa_type_collector (gcc::context *ctxt);
+extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
 extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
 extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
 extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);