which fields can be deleted

14 files changed, 265 insertions, 14 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index bf0623be999..ee8d20cad29 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1410,6 +1410,7 @@ OBJS = \
 	ipa-prototype.o \
 	ipa-type-escape-analysis.o \
 	type-walker.o \
+	type-field-deleter.o \
 	expr-walker.o \
 	gimple-walker.o \
 	gimple-accesser.o \
diff --git a/gcc/expr-accessor.hpp b/gcc/expr-accessor.hpp
index c3a0b4ecef7..242f6b2e268 100644
--- a/gcc/expr-accessor.hpp
+++ b/gcc/expr-accessor.hpp
@@ -20,6 +20,7 @@ public:
   ExprAccessor() {};
   void update(const_tree e, unsigned a);
   void print_accesses();
+  record_field_map_t get_map() { return record_field_map; };
 private:
   unsigned _access;
   record_field_map_t record_field_map;
diff --git a/gcc/expr-escaper.c b/gcc/expr-escaper.c
index 651cfe9c666..d2a81d13493 100644
--- a/gcc/expr-escaper.c
+++ b/gcc/expr-escaper.c
@@ -34,6 +34,7 @@
 #include "type-escaper.hpp"
 #include "expr-escaper.hpp"
 
+
 void
 ExprEscaper::update(const_tree t, Reason r)
 {
diff --git a/gcc/expr-escaper.hpp b/gcc/expr-escaper.hpp
index bcadbe77782..b82645c4ada 100644
--- a/gcc/expr-escaper.hpp
+++ b/gcc/expr-escaper.hpp
@@ -12,6 +12,7 @@ public:
   ExprEscaper(ptrset_t &types) : typeEscaper(types) {};
   ptrset_t get_sets() { return typeEscaper.get_sets(); };
   void update(const_tree t, Reason r);
+  void update_single_level(const_tree t, Reason r) { typeEscaper.update_single_level(TREE_TYPE(t), r); };
   void print_reasons() { typeEscaper.print_reasons(); };
 private:
   Reason _r;
diff --git a/gcc/gimple-accesser.hpp b/gcc/gimple-accesser.hpp
index 69bed4839a2..81228724daa 100644
--- a/gcc/gimple-accesser.hpp
+++ b/gcc/gimple-accesser.hpp
@@ -13,6 +13,7 @@ class GimpleAccesser : public GimpleWalker
 public:
   GimpleAccesser() : GimpleWalker() {};
   void print_accesses() { exprAccessor.print_accesses(); };
+  record_field_map_t get_map() { return exprAccessor.get_map(); };
 private:
   ExprAccessor exprAccessor;
   virtual void _walk_pre(gcall *s) final;
diff --git a/gcc/gimple-caster.c b/gcc/gimple-caster.c
index 299bbf6abfb..3452c552baa 100644
--- a/gcc/gimple-caster.c
+++ b/gcc/gimple-caster.c
@@ -22,11 +22,31 @@ GimpleCaster::_walk_pre(gassign *s)
   const_tree t_lhs = TREE_TYPE(lhs);
   const_tree t_rhs = TREE_TYPE(rhs);
   gcc_assert(t_lhs && t_rhs);
-  const bool is_cast = !equality.equal(t_lhs, t_rhs);
+  bool is_cast = !equality.equal(t_lhs, t_rhs);
+  TypeStringifier stringifier;
+  const std::string name_l = stringifier.stringify(t_lhs);
+  const std::string name_r = stringifier.stringify(t_rhs);
+  // If it is cast, we might need to look at the definition of rhs
+  // If the definition comes from a known function... then we are good...
+  bool is_ssa = TREE_CODE(rhs) == SSA_NAME;
+  while (is_ssa) {
+    gimple *def_for_rhs = SSA_NAME_DEF_STMT(rhs);
+    gcall *is_call = dyn_cast<gcall*>(def_for_rhs);
+    if (!is_call) break;
+
+    const_tree fn = gimple_call_fndecl(is_call);
+    if (!fn) break;
+
+    cgraph_node *node = cgraph_node::get(fn);
+    bool known_function = GimpleEscaper::filter_known_function(node);
+    is_cast = !known_function;
+
+    is_ssa = false;
+  }
   reason.is_escaping = is_cast;
   reason.type_is_casted = is_cast;
-  exprEscaper.update(lhs, reason);
-  exprEscaper.update(rhs, reason);
+  exprEscaper.update_single_level(lhs, reason);
+  exprEscaper.update_single_level(rhs, reason);
   // TODO: 
   // I think this will re-do the work... But it might be necessary?
   GimpleEscaper::_walk_pre(s);
@@ -38,7 +58,15 @@ GimpleCaster::_walk_pre(gcall *s)
   GimpleEscaper::_walk_pre(s);
 
   const_tree fn = gimple_call_fndecl(s);
-  cgraph_node *node = cgraph_node::get(fn);
+  // gcc_assert(fn)
+  // The above will not always be true
+  if (!fn)
+  {
+    //TODO: We should at least assert that the types are already
+    //marked as escaping?
+    return;
+  }
+  cgraph_node *node = fn ? cgraph_node::get(fn) : NULL;
   const bool known_function = GimpleEscaper::filter_known_function(node);
   if (known_function) return;
 
@@ -58,11 +86,10 @@ GimpleCaster::_walk_pre(gcall *s)
     const bool is_casted = !equality.equal(formal_t, real_t);
     const std::string name_r = stringifier.stringify(real_t);
     const std::string name_f = stringifier.stringify(formal_t);
-    log("looking at casted argument %s == %s ? %s\n", name_r.c_str(), name_f.c_str(), is_casted ? "t" : "f");
     Reason arg_reason;
     arg_reason.is_escaping = is_casted;
     arg_reason.type_is_casted = is_casted;
-    exprEscaper.update(real, arg_reason);
+    exprEscaper.update_single_level(real, arg_reason);
     i++;
   }
 
@@ -85,5 +112,5 @@ GimpleCaster::_walk_pre(gcall *s)
   Reason ret_reason;
   ret_reason.is_escaping = is_casted;
   ret_reason.type_is_casted = is_casted;
-  exprEscaper.update(lhs, ret_reason);
+  exprEscaper.update_single_level(lhs, ret_reason);
 }
diff --git a/gcc/gimple-escaper.c b/gcc/gimple-escaper.c
index 3f80d6cd868..fef93bffdbb 100644
--- a/gcc/gimple-escaper.c
+++ b/gcc/gimple-escaper.c
@@ -99,6 +99,7 @@ GimpleEscaper::filter_known_function(cgraph_node *node)
   const char *_realloc = "realloc";
   const char *_calloc = "calloc";
   const char *_memset = "memset";
+  const char *_specqsort= "spec_qsort";
   const char *name = node->name();
   gcc_assert(name);
   filter |= strcmp(_free, name) == 0;
@@ -106,6 +107,7 @@ GimpleEscaper::filter_known_function(cgraph_node *node)
   filter |= strcmp(_realloc, name) == 0;
   filter |= strcmp(_memset, name) == 0;
   filter |= strcmp(_calloc, name) == 0;
+  filter |= strcmp(_specqsort, name) == 0;
   return filter;
 }
 
@@ -176,9 +178,18 @@ void
 GimpleEscaper::_walk_pre(gcall *s)
 {
   const_tree fn = gimple_call_fndecl(s);
-  cgraph_node *node = cgraph_node::get(fn);
-  const bool _is_function_escaping = is_function_escaping(node);
-  const bool is_undefined = undefined.find(fn) != undefined.end();
+  // gcc_assert(fn);
+  // The above will not always be true
+  if (!fn)
+  {
+    log("TODO: we have a gimple_call_fndecl(s) == NULL in GimpleEscaper\n");
+  }
+  cgraph_node *node = fn ? cgraph_node::get(fn) : NULL;
+  // TODO:
+  // This is not safe... But we need to have false.
+  // Which functions do not have a declaration?
+  const bool _is_function_escaping = node ? is_function_escaping(node) : false;
+  const bool is_undefined = node ? undefined.find(fn) != undefined.end() : false;
   const bool _is_escaping = is_undefined || _is_function_escaping;
   Reason function_type_reason;
   function_type_reason.is_escaping = _is_escaping;
diff --git a/gcc/gimple-walker.c b/gcc/gimple-walker.c
index e61b49f0a98..350db82d23f 100644
--- a/gcc/gimple-walker.c
+++ b/gcc/gimple-walker.c
@@ -60,7 +60,7 @@ GimpleWalker::walk()
   cgraph_node *node = NULL;
   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
   {
-    print_function(node);
+    //print_function(node);
     node->get_untransformed_body();
     _walk_cnode(node);
   }
diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c
index a88602054db..3709fd2858c 100644
--- a/gcc/ipa-type-escape-analysis.c
+++ b/gcc/ipa-type-escape-analysis.c
@@ -26,6 +26,10 @@
 #include "gimple-escaper.hpp"
 #include "gimple-caster.hpp"
 #include "gimple-accesser.hpp"
+#include "type-field-deleter.hpp"
+#include "type-stringifier.hpp"
+#include "type-incomplete-equality.hpp"
+#include <vector>
 
 
 static unsigned int iphw_execute();
@@ -96,12 +100,64 @@ iphw_execute()
 }
 
 static void
+fix_escaping_types_in_set(ptrset_t &types)
+{
+  bool fixed_point_reached = false;
+  TypeIncompleteEquality structuralEquality;
+  TypeStringifier stringifier;
+  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...
+       TypeStringifier stringifier;
+       std::string type_esc_name = TypeStringifier::get_type_identifier(type_esc);
+       std::string type_non_name = TypeStringifier::get_type_identifier(type_non);
+
+       type_esc_name = stringifier.stringify(type_esc);
+       type_non_name = stringifier.stringify(type_non);
+
+       const bool equal = structuralEquality.equal(type_esc, type_non);
+       if (!equal) continue;
+
+       //log("recalulating %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
 collect_types()
 {
   GimpleTypeCollector collector;
   collector.walk();
   collector.print_collected();
   ptrset_t types = collector.get_pointer_set();
+  // what if we had 2 sets here
+  // points_to_record and not_points_to_record
   GimpleEscaper gimpleEscaper(types);
   gimpleEscaper.walk();
   if (flag_print_escape_analysis) gimpleEscaper.print_reasons();
@@ -109,8 +165,90 @@ collect_types()
   GimpleCaster caster(types);
   caster.walk();
   if (flag_print_cast_analysis) caster.print_reasons();
+  // what if we had other 2 sets here
+  // is_escaping and is_not_escaping
+  // We intersect is_not_escaping and points_to_record
   ptrset_t casting = caster.get_sets();
+  // Here we need to do fixed point...
+  fix_escaping_types_in_set(casting);
   GimpleAccesser accesser;
   accesser.walk();
   if (flag_print_access_analysis) accesser.print_accesses();
+  record_field_map_t record_field_map = accesser.get_map();
+  // here we need something similar...
+  // We need to say that for all records on field_map... if two are equal
+  // then we will need to mark OR the accesses to fields
+  TypeIncompleteEquality equality;
+  typedef std::set<unsigned> field_offsets_t;
+  typedef std::map<const_tree, field_offsets_t> record_field_offset_map_t;
+  record_field_offset_map_t record_field_offset_map;
+  for (auto i = record_field_map.begin(), e = record_field_map.end(); i != e; ++i)
+  {
+    const_tree r_i = i->first;
+    std::vector<const_tree> equivalence;
+    for (auto j = record_field_map.cbegin(), f = record_field_map.cend(); j != f; j++)
+    {
+       const_tree r_j = j->first;
+       const bool pointer_equal = r_i == r_j;
+       if (pointer_equal) continue;
+
+       const bool are_equal = equality.equal(r_i, r_j);
+       if (!are_equal) continue;
+
+       equivalence.push_back(r_j);
+    }
+
+    field_offsets_t field_offset;
+    field_access_map_t original_field_map = record_field_map[r_i];
+    for (auto j = original_field_map.begin(), f = original_field_map.end(); j != f; ++j)
+    {
+	 const_tree f_k = j->first;
+	 unsigned access = j->second;
+	 const bool is_read = access & Read;
+         unsigned f_offset = tree_to_uhwi(DECL_FIELD_OFFSET(f_k));
+         unsigned f_offset_2 = tree_to_uhwi(DECL_FIELD_BIT_OFFSET(f_k));
+	 //log("%s offset %u %u is_read %s\n", TypeStringifier::get_field_identifier(f_k).c_str(), f_offset, f_offset_2, is_read ? "t" :"f");
+	 if (!is_read) continue;
+	field_offset.insert(f_offset * 8 + f_offset_2);
+    }
+    for (auto j = equivalence.begin(), f = equivalence.end(); j != f; j++)
+    {
+      const_tree r_j = *j;
+      field_access_map_t equivalent_field_map = record_field_map[r_j];
+
+      for (auto k = equivalent_field_map.begin(), g = equivalent_field_map.end(); k != g; ++k)
+      {
+	const_tree f_k = k->first;
+	unsigned access = k->second;
+	const bool is_read = access & Read;
+        unsigned f_offset = tree_to_uhwi(DECL_FIELD_OFFSET(f_k));
+        unsigned f_offset_2 = tree_to_uhwi(DECL_FIELD_BIT_OFFSET(f_k));
+	//log("%s offset %u %u is_read %s\n", TypeStringifier::get_field_identifier(f_k).c_str(), f_offset, f_offset_2, is_read ? "t" :"f");
+	if (!is_read) continue;
+	field_offset.insert(f_offset * 8 + f_offset_2);
+      }
+    }
+    record_field_offset_map[r_i] = field_offset;
+  }
+
+
+  const typeset &non_escaping = casting.non_escaping;
+  for (auto i = record_field_offset_map.cbegin(), e = record_field_offset_map.cend(); i != e; ++i)
+  {
+    const_tree record = i->first;
+    const bool in_set = non_escaping.find(record) != non_escaping.end();
+    if (!in_set) continue;
+
+    field_offsets_t field_offset = i->second;
+    for (tree field = TYPE_FIELDS(record); field; field = DECL_CHAIN(field))
+    {
+        unsigned f_offset = tree_to_uhwi(DECL_FIELD_OFFSET(field));
+        unsigned f_offset_2 = tree_to_uhwi(DECL_FIELD_BIT_OFFSET(field));
+	f_offset = f_offset * 8 + f_offset_2;
+	bool in_set2 = field_offset.find(f_offset) != field_offset.end();
+	if (in_set2) continue;
+	log("%s.%s may be deleted\n", TypeStringifier::get_type_identifier(record).c_str(), TypeStringifier::get_field_identifier(field).c_str());
+    }
+  }
+
 }
diff --git a/gcc/type-escaper.c b/gcc/type-escaper.c
index 733e6e2ce6c..e25ee999b0d 100644
--- a/gcc/type-escaper.c
+++ b/gcc/type-escaper.c
@@ -94,6 +94,14 @@ TypeEscaper::update(const_tree t, Reason r)
 }
 
 void
+TypeEscaper::update_single_level(const_tree t, Reason r)
+{
+  gcc_assert(t);
+  const bool already_in_typemap = calc.find(t) != calc.end();
+  already_in_typemap ? calc[t] |= r : calc[t] = r;
+}
+
+void
 TypeEscaper::_update(const_tree t)
 {
   gcc_assert(t);
diff --git a/gcc/type-escaper.hpp b/gcc/type-escaper.hpp
index e4025165237..8f6490fb47e 100644
--- a/gcc/type-escaper.hpp
+++ b/gcc/type-escaper.hpp
@@ -10,6 +10,7 @@ class TypeEscaper : public TypeWalker
 public:
   TypeEscaper(ptrset_t &p) : _ptrset(p), _inside_union(0) {};
   void update(const_tree t, Reason r);
+  void update_single_level(const_tree t, Reason r);
   ptrset_t get_sets();
   ptrset_t &_ptrset;
   typemap calc;
diff --git a/gcc/type-field-deleter.c b/gcc/type-field-deleter.c
new file mode 100644
index 00000000000..769de227c67
--- /dev/null
+++ b/gcc/type-field-deleter.c
@@ -0,0 +1,37 @@
+#include "types-inlines.h"
+#include "type-stringifier.hpp"
+#include <string>
+
+#include "type-field-deleter.hpp"
+
+void
+TypeFieldDeleter::_walk_RECORD_TYPE_pre(const_tree t)
+{
+  // Easy comparison for now
+  TypeStringifier stringifier;
+  _print.push(t == _record);
+  if (!_print.top()) return;
+  const std::string name = stringifier.stringify(t);
+  log ("looking at record %s\n", name.c_str());
+}
+
+void
+TypeFieldDeleter::_walk_RECORD_TYPE_post(const_tree t)
+{
+  _print.pop();
+}
+
+void
+TypeFieldDeleter::_walk_field_pre(const_tree t)
+{
+  if (!_print.top()) return;
+
+  assert_is_type(t, FIELD_DECL);
+  const bool in_set = _accesses.find(t) != _accesses.end();
+  unsigned access = in_set ? _accesses[t] : Empty;
+  const bool is_read = access & Read;
+  if (is_read) return;
+
+  const std::string identifier = TypeStringifier::get_field_identifier(t); 
+  log("will delete field %s\n", identifier.c_str());
+}
diff --git a/gcc/type-field-deleter.hpp b/gcc/type-field-deleter.hpp
new file mode 100644
index 00000000000..7bbfbfd6584
--- /dev/null
+++ b/gcc/type-field-deleter.hpp
@@ -0,0 +1,18 @@
+#pragma once
+
+#include "type-walker.hpp"
+#include "expr-accessor.hpp"
+#include <stack>
+
+class TypeFieldDeleter : public TypeWalker {
+public:
+  TypeFieldDeleter(const_tree record, field_access_map_t accesses) : _record(record), _accesses(accesses) {};
+private:
+  const_tree _record;
+  field_access_map_t _accesses;
+  std::stack<bool> _print;
+  virtual void _walk_RECORD_TYPE_pre(const_tree t);
+  virtual void _walk_RECORD_TYPE_post(const_tree t);
+  virtual void _walk_field_pre(const_tree t);
+};
+
diff --git a/gcc/type-incomplete-equality.c b/gcc/type-incomplete-equality.c
index bf9047a98c7..88072c40022 100644
--- a/gcc/type-incomplete-equality.c
+++ b/gcc/type-incomplete-equality.c
@@ -46,10 +46,16 @@ TypeIncompleteEquality::_equal(const_tree l, const_tree r)
   // if any of these are incomplete, then we can only compare using identifiers...
   const bool complete_l = is_complete(l);
   const bool complete_r = is_complete(r);
-  const bool can_compare_structurally = complete_l && complete_r;
+  bool can_compare_structurally = complete_l && complete_r;
   if (can_compare_structurally) return TypeStructuralEquality::_equal(l, r);
 
-  const std::string n_l = TypeStringifier::get_type_identifier(l);
-  const std::string n_r = TypeStringifier::get_type_identifier(r);
+  const_tree m_l = TYPE_MAIN_VARIANT(l);
+  const_tree m_r = TYPE_MAIN_VARIANT(r);
+  gcc_assert(m_l && m_r);
+  can_compare_structurally = m_l == m_r;
+  if (can_compare_structurally) return true;
+
+  const std::string n_l = TypeStringifier::get_type_identifier(m_l);
+  const std::string n_r = TypeStringifier::get_type_identifier(m_r);
   return n_l.compare(n_r) == 0;
 }