wip

7 files changed, 394 insertions, 301 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 575ab18ff8c..45c9d8a0f2c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1409,6 +1409,7 @@ OBJS = \
 	internal-fn.o \
 	ipa-hello-world.o \
 	compare-types.o \
+	collect-types.o \
 	ipa-cp.o \
 	ipa-sra.o \
 	ipa-devirt.o \
diff --git a/gcc/collect-types.c b/gcc/collect-types.c
new file mode 100644
index 00000000000..18c4ab3ca92
--- /dev/null
+++ b/gcc/collect-types.c
@@ -0,0 +1,192 @@
+#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 <set>
+
+#include "collect-types.h"
+
+static void
+collect_types_from_record_or_union_type(const_tree type, typeset &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);
+    collect_types(field, types);
+  }
+}
+
+static void
+collect_types_from_record_type(const_tree type, typeset &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, typeset &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, typeset &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, typeset &types)
+{
+  assert_is_type(type, POINTER_TYPE);
+  collect_types_from_wrapper_type(type, types);
+}
+
+static void
+collect_types_from_reference_type(const_tree type, typeset &types)
+{
+  assert_is_type(type, REFERENCE_TYPE);
+  collect_types_from_wrapper_type(type, types);
+}
+
+static void
+collect_types_from_array_type(const_tree type, typeset &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, typeset &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);
+
+  for (tree param = TYPE_ARG_TYPES(type); param; param = TREE_CHAIN(param))
+  {
+    const_tree param_type = TREE_TYPE(param);
+    gcc_assert(param_type);
+    collect_types(param_type, types);
+  }
+}
+
+static void
+collect_types_from_function_type(const_tree type, typeset &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, typeset &types)
+{
+  assert_is_type(type, METHOD_TYPE);
+  collect_types_from_function_or_method_type(type, types);
+}
+
+void
+collect_types(const_tree type, typeset &types)
+{
+  if (!type) return;
+
+  const bool in_set = types.find(type) != types.end();
+  // memoized.
+  if (in_set) return;
+
+  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:
+      types.insert(type);
+      return;
+    break;
+    default:
+    break;
+  }
+
+  switch (code)
+  {
+    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:
+      gcc_unreachable();
+    break;
+  }
+
+  types.insert(type);
+}
diff --git a/gcc/collect-types.h b/gcc/collect-types.h
new file mode 100644
index 00000000000..315c19abfd7
--- /dev/null
+++ b/gcc/collect-types.h
@@ -0,0 +1,7 @@
+#pragma once
+
+#include "tree.h"
+#include <set>
+
+typedef std::set<const_tree> typeset;
+extern void collect_types(const_tree type, typeset &types);
diff --git a/gcc/compare-types.c b/gcc/compare-types.c
index 61a43d8c408..641cc1fca90 100644
--- a/gcc/compare-types.c
+++ b/gcc/compare-types.c
@@ -29,6 +29,7 @@
 #include "gimple-ssa.h"
 
 #include "compare-types.h"
+#include "types-inlines.h"
 
 static bool
 eq_main_variant(const_tree a, const_tree b)
@@ -271,3 +272,130 @@ eq_types(const_tree a, const_tree b, const bool force_structural)
   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
diff --git a/gcc/compare-types.h b/gcc/compare-types.h
index ca7251109a6..63474713807 100644
--- a/gcc/compare-types.h
+++ b/gcc/compare-types.h
@@ -1,12 +1,4 @@
 #pragma once
 
-inline
-void assert_is_type(const_tree a, const enum tree_code expected_code)
-{
-  gcc_assert(a);
-  const enum tree_code observed_code = TREE_CODE(a);
-  const bool eq_codes = observed_code == expected_code;
-  gcc_assert(eq_codes);
-}
-
+namespace test_type_equality { void run_tests(); };
 extern bool eq_types(const_tree a, const_tree b, const bool force_structural = false);
diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
index d9af11cfb41..09cf4526780 100644
--- a/gcc/ipa-hello-world.c
+++ b/gcc/ipa-hello-world.c
@@ -29,329 +29,81 @@
 #include "gimple-ssa.h"
 
 #include "compare-types.h"
+#include "types-inlines.h"
 #include <set>
 
-void inline
-log(const char* const fmt, ...)
-{
-  if (!dump_file) return;
-  
-  va_list args;
-  va_start(args, fmt);
-  vfprintf(dump_file, fmt, args);
-  va_end(args);
-}
-
-typedef std::set<const_tree> typeset;
-
-static const bool contains_record_types(const_tree type);
-
-static const bool
-inner_type_contains_record_types(const_tree type)
-{
-  gcc_assert(type);
-  const_tree inner = TREE_TYPE(type);
-  return contains_record_types(inner);
-}
-
-static const bool
-pointer_contains_record_types(const_tree type)
-{
-  assert_is_type(type, POINTER_TYPE);
-  return inner_type_contains_record_types(type);
-}
-
-static const bool
-reference_contains_record_types(const_tree type)
-{
-  assert_is_type(type, REFERENCE_TYPE);
-  return inner_type_contains_record_types(type);
-}
-
-static const bool
-array_contains_record_types(const_tree type)
-{
-  assert_is_type(type, ARRAY_TYPE);
-  return inner_type_contains_record_types(type);
-}
+#include "collect-types.h"
 
-static const bool
-union_contains_record_types(const_tree type)
-{
-  assert_is_type(type, UNION_TYPE);
-  tree field = TYPE_FIELDS(type);
-  while (field)
-  {
-    const_tree field_type = TREE_TYPE(field);
-    gcc_assert(field_type);
-    const bool contains_record = contains_record_types(field_type);
-    if (contains_record) return true;
-
-    field = DECL_CHAIN(field);
-  }
-
-  return false;
-}
 
-static const bool
-function_or_method_contains_record_types(const_tree type)
-{
-  gcc_assert(type);
-  const_tree ret_type = TREE_TYPE(type);
-  const bool return_type_contains_record = contains_record_types(ret_type);
-  if (return_type_contains_record) return true;
-
-  tree parm = TYPE_ARG_TYPES(type);
-
-  while (parm)
-  {
-    const_tree parm_type = TREE_TYPE(parm);
-    const bool parm_type_contains_record = contains_record_types(parm_type);
-    if (parm_type) return true;
-
-    parm = TREE_CHAIN(parm);
-  }
-
-  return false;
-}
-
-static const bool
-function_contains_record_types(const_tree type)
-{
-  assert_is_type(type, FUNCTION_TYPE); 
-  return function_or_method_contains_record_types(type);
-}
-
-static const bool
-method_contains_record_types(const_tree type)
-{
-  assert_is_type(type, FUNCTION_TYPE); 
-  const_tree base_type = TYPE_METHOD_BASETYPE(type);
-  const bool base_type_contains_record_types = contains_record_types(base_type);
-  return base_type_contains_record_types && function_or_method_contains_record_types(type);
-}
-
-static const bool
-contains_record_types(const_tree type)
+static void
+collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types)
 {
-  gcc_assert(type);
-  const enum tree_code code = TREE_CODE(type);
-  if (code == RECORD_TYPE) return true;
-
-  switch (code)
-  {
-    case VOID_TYPE:
-    case INTEGER_TYPE:
-    case REAL_TYPE:
-    case FIXED_POINT_TYPE:
-    case ENUMERAL_TYPE:
-    case BOOLEAN_TYPE:
-    case OFFSET_TYPE:
-      return false;
-    break;
-    default:
-    break;
-  }
-
-  switch (code)
-  {
-    case POINTER_TYPE:
-      return pointer_contains_record_types(type);
-    break;
-    case REFERENCE_TYPE:
-      return reference_contains_record_types(type);
-    break;
-    case ARRAY_TYPE:
-      return array_contains_record_types(type);
-    break;
-    case UNION_TYPE:
-      return union_contains_record_types(type);
-    break;
-    case FUNCTION_TYPE:
-      return function_contains_record_types(type);
-    break;
-    case METHOD_TYPE:
-      return method_contains_record_types(type);
-    break;
-    case QUAL_UNION_TYPE:
-    case LANG_TYPE:
-    default:
-      gcc_unreachable();
-    break;
-  }
-
-  gcc_unreachable();
-  return false;
+  gcc_assert(cnode);
+  const_tree decl = cnode->decl;
+  gcc_assert(decl);
+  const_tree decl_type = TREE_TYPE(decl);
+  gcc_assert(decl_type);
+  // This will collect return, arguments and decl_type itself
+  collect_types(decl_type, types);
 }
 
 static void
-get_non_escaping_locals(const cgraph_node *cnode, typeset &escaping_types, typeset &non_escaping_types)
+collect_types_from_cnode_locals(cgraph_node *cnode, typeset &types)
 {
   gcc_assert(cnode);
-  function *func = DECL_STRUCT_FUNCTION (cnode->decl);
+  const_tree decl = cnode->decl;
+  gcc_assert(decl);
+  function *func = DECL_STRUCT_FUNCTION (decl);
+  gcc_assert(func);
   int i = 0;
   tree var_decl = NULL;
   FOR_EACH_LOCAL_DECL(func, i, var_decl)
   {
-    
+    gcc_assert(var_decl);
+    const_tree var_decl_type = TREE_TYPE(var_decl);
+    collect_types(var_decl_type, types);
   }
 }
 
 static void
-get_non_escaping_types(const cgraph_node *cnode, typeset &escaping_types, typeset &non_escaping_types)
+collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types)
 {
   gcc_assert(cnode);
-  get_non_escaping_locals(cnode, escaping_types, non_escaping_types);
-}
-
-// So, have a set with TYPE_MAIN_VARIANTS...
-typeset
-get_non_escaping_types()
-{
-  cgraph_node *cnode = NULL;
-  typeset non_escaping_types;
-  typeset escaping_types;
-  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(cnode)
+  const_tree decl = cnode->decl;
+  gcc_assert(decl);
+  function *func = DECL_STRUCT_FUNCTION (decl);
+  push_cfun(func);
+  size_t i = 0;
+  tree ssa_name = NULL;
+  FOR_EACH_SSA_NAME(i, ssa_name, cfun)
   {
-    cnode->get_untransformed_body();
-    get_non_escaping_types(cnode, escaping_types, non_escaping_types);
+     gcc_assert(ssa_name);
+     const_tree ssa_name_type = TREE_TYPE(ssa_name);
+     collect_types(ssa_name, types);
   }
-  return non_escaping_types;
-}
-
-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);
+  pop_cfun();
 }
 
 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()
+collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &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);
-}
-
-static void
-run_tests()
-{
-  log("running tests...\n");
-  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();
-
+  gcc_assert(cnode);
+  collect_types_from_cnode_decl(cnode, types);
+  collect_types_from_cnode_locals(cnode, types);
+  collect_types_from_cnode_ssa_names(cnode, types);
 }
-} // test_type_equality
 
 static unsigned int
 iphw_execute()
 {
-  //test_type_equality::run_tests();
-  typeset non_escaping = get_non_escaping_types();
+  test_type_equality::run_tests();
+  cgraph_node *node = NULL;
+  typeset types;
+  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
+  {
+    node->get_untransformed_body();
+    collect_types_from_functions_with_gimple_body(node, types);
+  }
   return 0;
 }
 
diff --git a/gcc/types-inlines.h b/gcc/types-inlines.h
new file mode 100644
index 00000000000..9d91bc050d2
--- /dev/null
+++ b/gcc/types-inlines.h
@@ -0,0 +1,21 @@
+#pragma once
+
+inline void
+assert_is_type(const_tree a, const enum tree_code expected_code)
+{
+  gcc_assert(a);
+  const enum tree_code observed_code = TREE_CODE(a);
+  const bool eq_codes = observed_code == expected_code;
+  gcc_assert(eq_codes);
+}
+
+inline void
+log(const char* const fmt, ...)
+{
+  if (!dump_file) return;
+  
+  va_list args;
+  va_start(args, fmt);
+  vfprintf(dump_file, fmt, args);
+  va_end(args);
+}