equalities

6 files changed, 310 insertions, 3 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f6333d1b3cc..20492cc1be2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1417,6 +1417,8 @@ OBJS = \
 	expr-collector.o \
 	gimple-collector.o \
 	type-escaper.o \
+	type-structural-equality.o \
+	type-structural-main-variant.o \
 	expr-escaper.o \
 	gimple-escaper.o \
 	type-stringifier.o \
diff --git a/gcc/ipa-prototype.c b/gcc/ipa-prototype.c
index 96d19760949..9c35a483213 100644
--- a/gcc/ipa-prototype.c
+++ b/gcc/ipa-prototype.c
@@ -41,6 +41,7 @@
 #include "gimple-walker.hpp"
 #include "gimple-collector.hpp"
 #include "gimple-escaper.hpp"
+#include "type-structural-equality.hpp"
 
 //#define OPTIMIZED
 #define SANITY_CHECKS
@@ -240,6 +241,26 @@ print_escaping_types_in_set(ptrset_t &types)
 
 }
 
+static void
+print_sequal_types(ptrset_t &types)
+{
+  std::vector<const_tree> fixes;
+  TypeStructuralEquality structuralEquality;
+  TypeStringifier stringifier;
+  for (auto i = types.universe.cbegin(), e = types.universe.cend(); i != e; ++i)
+  {
+    for (auto j = types.universe.cbegin(), e = types.universe.cend(); j != e; ++j)
+    {
+      const_tree t_i = *i;
+      const_tree t_j = *j;
+      const bool eq = structuralEquality.equal(t_i, t_j);
+      std::string n_i = stringifier.stringify(t_i);
+      std::string n_j = stringifier.stringify(t_j);
+      log("%s = %s == %s\n", eq ? "t" : "f", n_i.c_str(), n_j.c_str());
+    }
+  }
+}
+
 
 static unsigned int
 iphw_execute()
@@ -256,6 +277,7 @@ iphw_execute()
   // Intermediate results
   // Do not read escape analysis results from here
   //calculate_escaping_types(types, eacalc);
+  print_sequal_types(types);
   place_escaping_types_in_set(types, gimpleEscaper.exprEscaper.typeEscaper.calc);
   fix_escaping_types_in_set(types);
   // -fipa-protytpe -fdump-ipa-prototype
diff --git a/gcc/type-structural-equality.c b/gcc/type-structural-equality.c
new file mode 100644
index 00000000000..95daf04f7aa
--- /dev/null
+++ b/gcc/type-structural-equality.c
@@ -0,0 +1,197 @@
+#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 "type-structural-equality.hpp"
+
+bool
+TypeStructuralEquality::equal(const_tree l, const_tree r)
+{
+  return _equal(l, r);
+}
+
+bool
+TypeStructuralEquality::_equal(const_tree l, const_tree r)
+{
+  bool valid_inputs = l && r;
+  if (!valid_inputs) return l == r;
+
+  bool equal_codes = _equal_code(l, r);
+  if (!equal_codes) return equal_codes;
+
+  bool recurse_l = set_l.find(l) != set_l.end();
+  bool recurse_r = set_r.find(r) != set_r.end();
+  bool recurse = recurse_l || recurse_r;
+  if (recurse) return recurse;
+
+  set_l.insert(l);
+  set_r.insert(r);
+  const enum tree_code code = TREE_CODE(l);
+  bool equal_children = false;
+  switch(code)
+  {
+#define TSE_CASE(code) \
+    case code: \
+      equal_children = _walk_ ## code (l, r); \
+    break
+
+    TSE_CASE(VOID_TYPE);
+    TSE_CASE(INTEGER_TYPE);
+    TSE_CASE(REAL_TYPE);
+    TSE_CASE(FIXED_POINT_TYPE);
+    TSE_CASE(COMPLEX_TYPE);
+    TSE_CASE(ENUMERAL_TYPE);
+    TSE_CASE(BOOLEAN_TYPE);
+    TSE_CASE(OFFSET_TYPE);
+    TSE_CASE(RECORD_TYPE);
+    TSE_CASE(POINTER_TYPE);
+    TSE_CASE(REFERENCE_TYPE);
+    TSE_CASE(ARRAY_TYPE);
+    TSE_CASE(UNION_TYPE);
+    TSE_CASE(FUNCTION_TYPE);
+    TSE_CASE(METHOD_TYPE);
+    default:
+    gcc_unreachable();
+    break;
+  }
+
+  set_l.erase(l);
+  set_r.erase(r);
+  return equal_children;
+  
+}
+
+bool
+TypeStructuralEquality::_equal_code(const_tree l, const_tree r)
+{
+  const enum tree_code code_l = TREE_CODE(l);
+  const enum tree_code code_r = TREE_CODE(r);
+  const bool equal = code_l == code_r;
+  return equal;
+}
+
+#define TSE_FUNC_DEF_SIMPLE(code) \
+bool \
+TypeStructuralEquality::_walk_ ## code (const_tree l, const_tree r) \
+{ \
+  return _equal_code(l, r); \
+}
+
+TSE_FUNC_DEF_SIMPLE(VOID_TYPE)
+TSE_FUNC_DEF_SIMPLE(INTEGER_TYPE)
+TSE_FUNC_DEF_SIMPLE(REAL_TYPE)
+TSE_FUNC_DEF_SIMPLE(FIXED_POINT_TYPE)
+TSE_FUNC_DEF_SIMPLE(ENUMERAL_TYPE)
+TSE_FUNC_DEF_SIMPLE(BOOLEAN_TYPE)
+TSE_FUNC_DEF_SIMPLE(OFFSET_TYPE)
+TSE_FUNC_DEF_SIMPLE(COMPLEX_TYPE)
+
+bool
+TypeStructuralEquality::_equal_wrapper(const_tree l, const_tree r)
+{
+  const_tree inner_l = TREE_TYPE(l);
+  const_tree inner_r = TREE_TYPE(r);
+  return _equal(inner_l, inner_r);
+}
+
+#define TSE_FUNC_DEF_WRAPPER(code) \
+bool \
+TypeStructuralEquality::_walk_ ## code (const_tree l, const_tree r) \
+{ \
+  return _equal_wrapper(l, r); \
+}
+
+TSE_FUNC_DEF_WRAPPER(REFERENCE_TYPE)
+TSE_FUNC_DEF_WRAPPER(ARRAY_TYPE)
+TSE_FUNC_DEF_WRAPPER(POINTER_TYPE)
+
+#define TSE_FUNC_DEF_CONTAINER(code) \
+bool \
+TypeStructuralEquality::_walk_ ## code (const_tree l, const_tree r) \
+{ \
+  const_tree field_l = TYPE_FIELDS(l); \
+  const_tree field_r = TYPE_FIELDS(r); \
+  bool efield_l = field_l; \
+  bool efield_r = field_r; \
+  bool still_equal = efield_l == efield_r; \
+  if (!still_equal) return still_equal; \
+	\
+  while (field_l && field_r && still_equal) \
+  { \
+    const_tree tfield_l = TREE_TYPE(field_l); \
+    const_tree tfield_r = TREE_TYPE(field_r); \
+    still_equal &= _equal(tfield_l, tfield_r); \
+    field_l = DECL_CHAIN(field_l); \
+    field_r = DECL_CHAIN(field_r); \
+    efield_l = field_l; \
+    efield_r = field_r; \
+    still_equal &= efield_l == efield_r; \
+  } \
+  return still_equal; \
+}
+
+TSE_FUNC_DEF_CONTAINER(RECORD_TYPE)
+TSE_FUNC_DEF_CONTAINER(UNION_TYPE)
+
+#define TSE_FUNC_DEF_FUNC(code) \
+bool \
+TypeStructuralEquality::_walk_ ## code (const_tree l, const_tree r) \
+{ \
+  const_tree tret_l = TREE_TYPE(l); \
+  const_tree tret_r = TREE_TYPE(r); \
+  bool still_equal = _equal(tret_l, tret_r); \
+  if (!still_equal) return still_equal; \
+  \
+  const_tree arg_l = TYPE_ARG_TYPES(l); \
+  const_tree arg_r = TYPE_ARG_TYPES(r); \
+  bool earg_l = arg_l; \
+  bool earg_r = arg_r; \
+  still_equal &= earg_l == earg_r; \
+  while (arg_l && arg_r && still_equal) \
+  { \
+    const_tree targ_l = TREE_VALUE(arg_l); \
+    const_tree targ_r = TREE_VALUE(arg_r); \
+    still_equal &= _equal(targ_l, targ_r); \
+    arg_l = TREE_CHAIN(arg_l); \
+    arg_r = TREE_CHAIN(arg_r); \
+    earg_l = arg_l; \
+    earg_r = arg_r; \
+    still_equal &= earg_l == earg_r; \
+  } \
+  return still_equal; \
+}
+
+TSE_FUNC_DEF_FUNC(FUNCTION_TYPE)
+TSE_FUNC_DEF_FUNC(METHOD_TYPE)
+
+
+
diff --git a/gcc/type-structural-equality.hpp b/gcc/type-structural-equality.hpp
index 66f2023c2ab..b5f1944bd31 100644
--- a/gcc/type-structural-equality.hpp
+++ b/gcc/type-structural-equality.hpp
@@ -1,12 +1,38 @@
 #pragma once
 
-#include "type-walker.hpp"
+#include <set>
 
 class TypeStructuralEquality {
 public:
   TypeStructuralEquality() {};
   bool equal(const_tree a, const_tree b);
+protected:
+  virtual bool _equal(const_tree a, const_tree b);
 private:
-  bool are_equal;
+  typedef std::set<const_tree> tset_t;
+
+  tset_t set_l;
+  tset_t set_r;
+  bool _equal_code(const_tree a, const_tree b);
+  bool _equal_wrapper(const_tree a, const_tree b);
+
+#define TSE_FUNC_DECL(code) \
+  virtual bool _walk_ ## code (const_tree l, const_tree r)
+  TSE_FUNC_DECL(VOID_TYPE);
+  TSE_FUNC_DECL(COMPLEX_TYPE);
+  TSE_FUNC_DECL(INTEGER_TYPE);
+  TSE_FUNC_DECL(REAL_TYPE);
+  TSE_FUNC_DECL(FIXED_POINT_TYPE);
+  TSE_FUNC_DECL(POINTER_TYPE);
+  TSE_FUNC_DECL(ENUMERAL_TYPE);
+  TSE_FUNC_DECL(BOOLEAN_TYPE);
+  TSE_FUNC_DECL(OFFSET_TYPE);
+  TSE_FUNC_DECL(RECORD_TYPE);
+  TSE_FUNC_DECL(REFERENCE_TYPE);
+  TSE_FUNC_DECL(ARRAY_TYPE);
+  TSE_FUNC_DECL(UNION_TYPE);
+  TSE_FUNC_DECL(FUNCTION_TYPE);
+  TSE_FUNC_DECL(METHOD_TYPE);
+
   const_tree left;
-}
+};
diff --git a/gcc/type-structural-main-variant.c b/gcc/type-structural-main-variant.c
new file mode 100644
index 00000000000..9cc95d5ec63
--- /dev/null
+++ b/gcc/type-structural-main-variant.c
@@ -0,0 +1,49 @@
+#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 "type-structural-equality.hpp"
+#include "type-structural-main-variant.hpp"
+
+bool
+TypeStructuralEqualityMainVariant::_equal(const_tree l, const_tree r)
+{
+  bool valid_inputs = l && r;
+  if (!valid_inputs) return l == r;
+
+  const_tree mv_l = TYPE_MAIN_VARIANT(l);
+  const_tree mv_r = TYPE_MAIN_VARIANT(r);
+  const bool mv_equal = mv_l == mv_r;
+  if (mv_equal) return mv_equal;
+
+  return TypeStructuralEquality::_equal(l, r);
+}
diff --git a/gcc/type-structural-main-variant.hpp b/gcc/type-structural-main-variant.hpp
new file mode 100644
index 00000000000..dda6eadcd59
--- /dev/null
+++ b/gcc/type-structural-main-variant.hpp
@@ -0,0 +1,11 @@
+#pragma once
+
+#include "type-structural-equality.hpp"
+
+class TypeStructuralEqualityMainVariant : public TypeStructuralEquality {
+public:
+  TypeStructuralEqualityMainVariant() {};
+private:
+
+  virtual bool _equal(const_tree l, const_tree r);
+};