partitions

5 files changed, 156 insertions, 85 deletions

diff --git a/gcc/ipa-dfe.c b/gcc/ipa-dfe.c
index 25990504634..b3352a94721 100644
--- a/gcc/ipa-dfe.c
+++ b/gcc/ipa-dfe.c
@@ -131,9 +131,9 @@ along with GCC; see the file COPYING3.  If not see
  */
 std::set<tree>
 get_all_types_pointing_to (record_field_offset_map_t record_field_offset_map,
-			   tpartitions_t casting)
+			   tpartitions2_t casting)
 {
-  const tset_t &non_escaping = casting.non_escaping;
+  tset2_t &non_escaping = casting.non_escaping;
 
   type_stringifier stringifier;
   hash_set<tree> specific_types2;
@@ -162,7 +162,7 @@ get_all_types_pointing_to (record_field_offset_map_t record_field_offset_map,
 
   // SpecificTypeCollector will collect all types which point to the types in
   // the set.
-  for (std::set<tree>::const_iterator i = non_escaping.begin (),
+  for (auto i = non_escaping.begin (),
 					    e = non_escaping.end ();
        i != e; ++i)
     {
diff --git a/gcc/ipa-dfe.h b/gcc/ipa-dfe.h
index 8a57c0d8aa8..74512c6e83f 100644
--- a/gcc/ipa-dfe.h
+++ b/gcc/ipa-dfe.h
@@ -282,7 +282,7 @@ private:
 // Get a set of all types pointing to types in RECORD_FIELD_OFFSET_MAP.
 std::set<tree>
 get_all_types_pointing_to (record_field_offset_map_t record_field_offset_map,
-			   tpartitions_t casting);
+			   tpartitions2_t casting);
 
 typedef std::pair<reorg_record_map_t, reorg_field_map_t> reorg_maps_t;
 
diff --git a/gcc/ipa-field-reorder.c b/gcc/ipa-field-reorder.c
index e4341ca5340..a275f4d3655 100644
--- a/gcc/ipa-field-reorder.c
+++ b/gcc/ipa-field-reorder.c
@@ -605,8 +605,8 @@ lto_fr_execute ()
   // Analysis.
   detected_incompatible_syntax = false;
   hash_map<tree, bool> *whitelisted2 = get_whitelisted_nodes2();
-  tpartitions_t escaping_nonescaping_sets
-    = partition_types_into_escaping_nonescaping (whitelisted2);
+  tpartitions2_t escaping_nonescaping_sets;
+  partition_types_into_escaping_nonescaping (escaping_nonescaping_sets, whitelisted2);
   record_field_map_t record_field_map = find_fields_accessed ();
   record_field_offset_map_t record_field_offset_map
     = obtain_nonescaping_unaccessed_fields (escaping_nonescaping_sets,
diff --git a/gcc/ipa-type-escape-analysis.c b/gcc/ipa-type-escape-analysis.c
index 0c7342e3664..ba1178fe1bc 100644
--- a/gcc/ipa-type-escape-analysis.c
+++ b/gcc/ipa-type-escape-analysis.c
@@ -181,8 +181,8 @@ static unsigned int
 lto_dfe_execute ();
 
 // Partition types into reching record or non reaching record sets.
-static tpartitions_t
-partition_types_into_record_reaching_or_non_record_reaching ();
+static void
+partition_types_into_record_reaching_or_non_record_reaching (tpartitions2_t &p);
 
 // Perform dead field elimination.
 static void
@@ -190,7 +190,7 @@ lto_dead_field_elimination ();
 
 // Fixed point calculating to determine escaping types.
 static void
-fix_escaping_types_in_set (tpartitions_t &types);
+fix_escaping_types_in_set (tpartitions2_t &types);
 
 // Find which fields are accessed.
 static record_field_map_t
@@ -310,7 +310,8 @@ get_whitelisted_nodes2 ()
     cgraph_node *i = worklist.front ();
     worklist.pop ();
     if (dump_file) fprintf (dump_file, "analyzing %s %p\n", i->name (), (void*)i);
-    gimple_white_lister whitelister;
+    tpartitions2_t temp;
+    gimple_white_lister whitelister(temp);
     whitelister._walk_cnode (i);
     bool no_external = whitelister.does_not_call_external_functions2 (i, map);
     bool before_in_map = map->get (i->decl);
@@ -356,8 +357,8 @@ lto_dead_field_elimination ()
   }
   detected_incompatible_syntax = false;
   hash_map<tree, bool> *whitelisted2 = get_whitelisted_nodes2 ();
-  tpartitions_t escaping_nonescaping_sets
-    = partition_types_into_escaping_nonescaping (whitelisted2);
+  tpartitions2_t escaping_nonescaping_sets;
+  partition_types_into_escaping_nonescaping (escaping_nonescaping_sets, whitelisted2);
   if (detected_incompatible_syntax) return;
   record_field_map_t record_field_map = find_fields_accessed ();
   if (detected_incompatible_syntax) return;
@@ -385,33 +386,29 @@ lto_dead_field_elimination ()
  * pointer, array, reference, union, field, etc...).
  * Let's call these trees record_reaching_trees.
  */
-static tpartitions_t
-partition_types_into_record_reaching_or_non_record_reaching ()
+void
+partition_types_into_record_reaching_or_non_record_reaching (tpartitions2_t &partitions)
 {
-  gimple_type_collector collector;
+  gimple_type_collector collector(partitions);
   collector.walk ();
-  tpartitions_t partitions = collector.get_record_reaching_trees ();
-  return partitions;
 }
 
 /* Iterate over all gimple bodies and find out
  * which types are escaping AND are being casted.
  */
-tpartitions_t
-partition_types_into_escaping_nonescaping (hash_map<tree, bool> *whitelisted2)
+void
+partition_types_into_escaping_nonescaping (tpartitions2_t &partitions, hash_map<tree, bool> *whitelisted2)
 {
-  tpartitions_t partitions
-    = partition_types_into_record_reaching_or_non_record_reaching ();
-  if (detected_incompatible_syntax) return partitions;
+  partition_types_into_record_reaching_or_non_record_reaching (partitions);
+  if (detected_incompatible_syntax) return;
   gimple_caster caster (partitions, whitelisted2);
   caster.walk ();
   caster.print_reasons ();
 
-  partitions = caster.get_sets ();
+  caster.fix_sets ();
   // Unify results from different trees representing the same type
   // until a fixed point is reached.
   fix_escaping_types_in_set (partitions);
-  return partitions;
 }
 
 /* Iterate over all gimple bodies and find out
@@ -439,7 +436,7 @@ record_field_map_t static find_fields_accessed ()
  */
 static std::vector<tree>
 find_equivalent_trees (tree r_i, record_field_map_t record_field_map,
-		       tpartitions_t casting)
+		       tpartitions2_t casting)
 {
   type_incomplete_equality equality;
   std::vector<tree> equivalence;
@@ -566,16 +563,16 @@ erase_if_no_fields_can_be_deleted (
 static void
 mark_escaping_types_to_be_deleted (
   record_field_offset_map_t &record_field_offset_map,
-  std::set<tree> &to_erase, tpartitions_t casting)
+  std::set<tree> &to_erase, tpartitions2_t casting)
 {
-  const tset_t &non_escaping = casting.non_escaping;
+  tset2_t &non_escaping = casting.non_escaping;
   for (std::map<tree, field_offsets_t>::iterator i
        = record_field_offset_map.begin (),
        e = record_field_offset_map.end ();
        i != e; ++i)
     {
       tree record = i->first;
-      const bool in_set = non_escaping.find (record) != non_escaping.end ();
+      const bool in_set = non_escaping.contains (record);
       if (in_set)
 	continue;
 
@@ -585,7 +582,7 @@ mark_escaping_types_to_be_deleted (
 
 // Obtain nonescaping unaccessed fields
 record_field_offset_map_t
-obtain_nonescaping_unaccessed_fields (tpartitions_t casting,
+obtain_nonescaping_unaccessed_fields (tpartitions2_t casting,
 				      record_field_map_t record_field_map,
 				      int _warning)
 {
@@ -1630,7 +1627,7 @@ gimple_walker::_walk_gphi (__attribute__((unused)) gphi *g)
 void
 type_collector::collect (tree t)
 {
-  const bool in_set = ptrset.in_universe (t);
+  const bool in_set = ptrset2.in_universe (t);
   // Early memoization...
 
   if (in_set)
@@ -1655,12 +1652,12 @@ type_collector::collect (tree t)
 void
 type_collector::_sanity_check ()
 {
-  for (tset_t::iterator i = ptrset.points_to_record.begin (),
-	    e = ptrset.points_to_record.end ();
+  for (auto i = ptrset2.points_to_record.begin (),
+	    e = ptrset2.points_to_record.end ();
        i != e; ++i)
     {
-      for (tset_t::iterator j = ptrset.complement.begin (),
-	    f = ptrset.complement.end ();
+      for (auto j = ptrset2.complement.begin (),
+	    f = ptrset2.complement.end ();
 	   j != f; ++j)
 	{
 	  tree type_ptr = *i;
@@ -1686,14 +1683,14 @@ bool
 type_collector::is_memoized (tree t)
 {
   /* If we haven't seen it then no.  */
-  const bool in_set = ptrset.in_universe (t);
+  const bool in_set = ptrset2.in_universe (t);
   if (!in_set)
     return false;
 
   // If the memoized type points to a record
   // we must update all types that can refer
   // to memoized type.
-  const bool points_to_record = ptrset.in_points_to_record (t);
+  const bool points_to_record = ptrset2.in_points_to_record (t);
   for (auto i = ptr2.begin (),
 	e = ptr2.end (); i != e; ++i)
     {
@@ -1790,7 +1787,7 @@ void
 type_collector::_collect_simple (tree t)
 {
   // Insert into persistent set.
-  ptrset.insert (t, *ptr2.get(t));
+  ptrset2.insert (t, *ptr2.get(t));
   // erase from current working set.
   ptr2.remove (t);
 }
@@ -1896,14 +1893,14 @@ expr_collector::_walk_pre (tree e)
 
   if (RECORD_TYPE != TREE_CODE (t)) return;
 
-  if (_type_collector.ptrset.records.empty ()) {
-    _type_collector.ptrset.records.insert (TYPE_MAIN_VARIANT (t));
+  if (_type_collector.ptrset2.records.is_empty ()) {
+    _type_collector.ptrset2.records.add (TYPE_MAIN_VARIANT (t));
     return;
   }
 
-  for (std::set<tree>::iterator
-	i = _type_collector.ptrset.records.begin (),
-	e = _type_collector.ptrset.records.end (); i != e; ++i)
+  for (auto
+	i = _type_collector.ptrset2.records.begin (),
+	e = _type_collector.ptrset2.records.end (); i != e; ++i)
   {
     tree r = *i;
     type_incomplete_equality structuralEquality;
@@ -1911,7 +1908,7 @@ expr_collector::_walk_pre (tree e)
     if (is_same) continue;
 
     type_stringifier stringifier;
-    _type_collector.ptrset.records.insert (TYPE_MAIN_VARIANT (t));
+    _type_collector.ptrset2.records.add (TYPE_MAIN_VARIANT (t));
   }
 }
 
@@ -2018,7 +2015,7 @@ gimple_type_collector::_walk_pre_gdebug (gdebug *s)
 void
 gimple_type_collector::print_collected ()
 {
-  tpartitions_t sets = get_record_reaching_trees ();
+  tpartitions2_t sets = get_record_reaching_trees ();
   // TODO: I think previously we were printing info here for tests
 }
 
@@ -2041,13 +2038,14 @@ type_escaper::is_memoized (__attribute__ ((unused)) tree t)
   return false;
 }
 
-tpartitions_t
-type_escaper::get_sets ()
+void
+type_escaper::fix_sets ()
 {
   place_escaping_types_in_set ();
-  return _ptrset;
+  //return _ptrset2;
 }
 
+
 /* From a map of TREE -> BOOL, the key represents a tree type
  * and the value represents whether the tree escapes.
  * Partition this map into sets.
@@ -2064,12 +2062,12 @@ type_escaper::place_escaping_types_in_set ()
       // 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 (!_ptrset.in_points_to_record (type))
+      if (!_ptrset2.in_points_to_record (type))
 	continue;
 
       const Reason reason = (*i).second;
-      reason.is_escaping () ? _ptrset.escaping.insert (type)
-			    : _ptrset.non_escaping.insert (type);
+      reason.is_escaping () ? _ptrset2.escaping.add (type)
+			    : _ptrset2.non_escaping.add (type);
     }
 }
 
@@ -2215,10 +2213,10 @@ type_escaper::print_reasons ()
     }
 }
 
-tpartitions_t
-expr_escaper::get_sets ()
+void
+expr_escaper::fix_sets ()
 {
-  return _type_escaper.get_sets ();
+  _type_escaper.fix_sets ();
 }
 
 void
@@ -2319,11 +2317,11 @@ expr_escaper::_walk_CONSTRUCTOR_pre (tree e)
   _type_escaper.update (t, _r);
 }
 
-tpartitions_t
-gimple_escaper::get_sets ()
+void
+gimple_escaper::fix_sets ()
 {
   _expr_escaper.curr_node = NULL;
-  return _expr_escaper.get_sets ();
+  return _expr_escaper.fix_sets ();
 }
 
 void
@@ -3177,6 +3175,19 @@ type_partitions_s::insert (tree type, bool in_points_to_record)
   gcc_assert (_xor);
 }
 
+void
+type_partitions2_s::insert (tree type, bool in_points_to_record)
+{
+  gcc_assert (type);
+  this->universe.add (type);
+  in_points_to_record ? this->points_to_record.add (type)
+	              : this->complement.add (type);
+  const bool in_points_to_set = this->in_points_to_record(type);
+  const bool in_complement = this->in_complement (type);
+  const bool _xor = in_points_to_set != in_complement;
+  gcc_assert (_xor);
+}
+
 /* Find out whether TYPE is already in universe.  */
 bool
 type_partitions_s::in_universe (tree type) const
@@ -3186,6 +3197,14 @@ type_partitions_s::in_universe (tree type) const
   return seen_before;
 }
 
+bool
+type_partitions2_s::in_universe (tree type)
+{
+  gcc_assert (type);
+  const bool seen_before = this->universe.contains (type);
+  return seen_before;
+}
+
 /* Find out whether TYPE is in points_to_record partition.  */
 bool
 type_partitions_s::in_points_to_record (tree type) const
@@ -3196,6 +3215,14 @@ type_partitions_s::in_points_to_record (tree type) const
   return seen_before;
 }
 
+bool
+type_partitions2_s::in_points_to_record (tree type)
+{
+  gcc_assert (type);
+  const bool seen_before = this->points_to_record.contains (type);
+  return seen_before;
+}
+
 /* Find out whether TYPE is not in points to record partition.  */
 bool
 type_partitions_s::in_complement (tree type) const
@@ -3206,6 +3233,14 @@ type_partitions_s::in_complement (tree type) const
   return seen_before;
 }
 
+bool
+type_partitions2_s::in_complement (tree type)
+{
+  gcc_assert (type);
+  const bool seen_before = this->complement.contains (type);
+  return seen_before;
+}
+
 /* Stringify a type.  */
 std::string
 type_stringifier::stringify (tree t)
@@ -3653,7 +3688,7 @@ type_incomplete_equality::_equal (tree l, tree r)
  * Perform this until a fixed point is reached.
  */
 static void
-fix_escaping_types_in_set (tpartitions_t &types)
+fix_escaping_types_in_set (tpartitions2_t &types)
 {
   bool fixed_point_reached = false;
   type_incomplete_equality structuralEquality;
@@ -3661,11 +3696,11 @@ fix_escaping_types_in_set (tpartitions_t &types)
     {
       vec<tree> fixes2 = vNULL;
       fixed_point_reached = true;
-      for (std::set<tree>::const_iterator i = types.escaping.begin (),
+      for (auto i = types.escaping.begin (),
 						e = types.escaping.end ();
 	   i != e; ++i)
 	{
-	  for (std::set<tree>::const_iterator j
+	  for (auto j
 	       = types.non_escaping.begin (),
 	       f = types.non_escaping.end ();
 	       j != f; ++j)
@@ -3692,8 +3727,8 @@ fix_escaping_types_in_set (tpartitions_t &types)
       for (auto i = fixes2.begin (), e = fixes2.end (); i != e; ++i)
 	{
 	  tree escaping_type = *i;
-	  types.escaping.insert (escaping_type);
-	  types.non_escaping.erase (escaping_type);
+	  types.escaping.add (escaping_type);
+	  types.non_escaping.remove (escaping_type);
 	}
     }
   while (!fixed_point_reached);
diff --git a/gcc/ipa-type-escape-analysis.h b/gcc/ipa-type-escape-analysis.h
index f38b53719df..822a3c03f78 100644
--- a/gcc/ipa-type-escape-analysis.h
+++ b/gcc/ipa-type-escape-analysis.h
@@ -131,7 +131,6 @@ public:
 protected:
 
   /* Typeset holds previously visited nodes.  */
-  tset_t tset;
   tset2_t tset2;
 
   /* Inner walking method, used to recurse.  */
@@ -456,7 +455,41 @@ struct type_partitions_s
   void insert (tree, bool);
 };
 
+struct type_partitions2_s
+{
+  /* The set of all types which have been seen.  */
+  tset2_t universe;
+
+  /* The set of all types which somehow refer to a RECORD_TYPE.  */
+  tset2_t points_to_record;
+
+  /* The complement of points_to_record.  */
+  tset2_t complement;
+
+  /* The set of all escaping types.  */
+  tset2_t escaping;
+
+  /* The set of all non escaping types.  */
+  tset2_t non_escaping;
+
+  /* The set of all records. */
+  tset2_t records;
+
+  /* Determine if we have seen this type before.  */
+  bool in_universe (tree);
+
+  /* Determine if tree points to a record.  */
+  bool in_points_to_record (tree);
+
+  /* Determine if tree does not point to a record.  */
+  bool in_complement (tree);
+
+  /* Insert either in points to record or complement.  */
+  void insert (tree, bool);
+};
+
 typedef struct type_partitions_s tpartitions_t;
+typedef struct type_partitions2_s tpartitions2_t;
 
 /* TypeCollector is a derived class from TypeWalker
  * that collects all types reachable from T into the partitions
@@ -465,17 +498,17 @@ typedef struct type_partitions_s tpartitions_t;
 class type_collector : public type_walker
 {
 public:
-  type_collector ()
+  type_collector (tpartitions2_t &ptrset)
+  : ptrset2(ptrset)
   {};
 
   /* Main interface.  */
   void collect (tree t);
 
   /* Collect the result after walking all trees.  */
-  tpartitions_t get_record_reaching_trees ()
+  tpartitions2_t& get_record_reaching_trees ()
   {
-    _sanity_check ();
-    return ptrset;
+    return ptrset2;
   }
 
 private:
@@ -499,7 +532,7 @@ private:
    * This datastructure persists across calls to collect.
    */
 public:
-  tpartitions_t ptrset;
+  tpartitions2_t& ptrset2;
 
 private:
 
@@ -646,11 +679,12 @@ private:
 class expr_collector : public expr_walker
 {
 public:
-  expr_collector ()
+  expr_collector (tpartitions2_t &p)
+  : _type_collector (p)
   {};
 
   /* Holds the result after collecting from all trees.  */
-  tpartitions_t get_record_reaching_trees ()
+  tpartitions2_t get_record_reaching_trees ()
   {
     return _type_collector.get_record_reaching_trees ();
   }
@@ -670,11 +704,12 @@ private:
 class gimple_type_collector : public gimple_walker
 {
 public:
-  gimple_type_collector ()
+  gimple_type_collector (tpartitions2_t &p)
+  : _expr_collector(p)
   {};
 
   /* This holds the result after walking the whole program.  */
-  tpartitions_t get_record_reaching_trees ()
+  tpartitions2_t get_record_reaching_trees ()
   {
     return _expr_collector.get_record_reaching_trees ();
   }
@@ -710,7 +745,8 @@ private:
 class gimple_white_lister : gimple_type_collector
 {
 public:
-  gimple_white_lister ()
+  gimple_white_lister (tpartitions2_t &t)
+  : gimple_type_collector (t)
   {};
 
   bool _no_external = true;
@@ -730,7 +766,7 @@ public:
     }
 
     unsigned int how_many_records = 
-	    _expr_collector._type_collector.ptrset.records.size ();
+	    _expr_collector._type_collector.ptrset2.records.elements ();
     return how_many_records <= 1;
 
   }
@@ -815,19 +851,19 @@ typedef hash_map<tree, Reason> typemap2;
 class type_escaper : public type_walker
 {
 public:
-  type_escaper (tpartitions_t &p)
-    : _ptrset (p), _inside_union (0), _inside_record (0)
+  type_escaper (tpartitions2_t &p)
+    : _ptrset2 (p), _inside_union (0), _inside_record (0)
   {};
 
   // Hold the partitions for escaping non escaping.
-  tpartitions_t &_ptrset;
+  tpartitions2_t &_ptrset2;
 
   // Have information that matches a tree type with
   // why a type is escaping.
   typemap2 calc2;
 
   // Get partitions after calculating escaping types.
-  tpartitions_t get_sets ();
+  void fix_sets ();
 
   // Print reasons why a type is escaping.
   void print_reasons ();
@@ -883,7 +919,7 @@ private:
 class expr_escaper : public expr_walker
 {
 public:
-  expr_escaper (tpartitions_t &types, hash_map<tree, bool> *whitelisted2) : _type_escaper (types), _whitelisted2(whitelisted2), _stack2(vNULL)
+  expr_escaper (tpartitions2_t &types, hash_map<tree, bool> *whitelisted2) : _type_escaper (types), _whitelisted2(whitelisted2), _stack2(vNULL)
   {};
 
   /* Main interface: T escapes because R.  */
@@ -895,7 +931,7 @@ public:
   hash_map<tree, bool> *_whitelisted2;
 
   /* Holds the end result.  */
-  tpartitions_t get_sets ();
+  void fix_sets ();
 
   /* Print end result.  */
   void print_reasons ();
@@ -1000,7 +1036,7 @@ protected:
 class gimple_escaper : public gimple_walker
 {
 public:
-  gimple_escaper (tpartitions_t &types, hash_map<tree, bool> *whitelisted2) : _expr_escaper (types, whitelisted2)
+  gimple_escaper (tpartitions2_t &types, hash_map<tree, bool> *whitelisted2) : _expr_escaper (types, whitelisted2)
   {
     _init ();
   };
@@ -1009,7 +1045,7 @@ public:
   expr_escaper _expr_escaper;
 
   /* Obtain final result.  */
-  tpartitions_t get_sets ();
+  void fix_sets ();
 
   /* Print final result.  */
   void print_reasons ();
@@ -1066,7 +1102,7 @@ protected:
 class gimple_caster : public gimple_escaper
 {
 public:
-  gimple_caster (tpartitions_t &types, hash_map<tree, bool> *whitelisted2) : gimple_escaper (types, whitelisted2), _whitelisted2(whitelisted2)
+  gimple_caster (tpartitions2_t &types, hash_map<tree, bool> *whitelisted2) : gimple_escaper (types, whitelisted2), _whitelisted2(whitelisted2)
 {};
 
 private:
@@ -1236,12 +1272,12 @@ typedef std::map<tree, field_offsets_t> record_field_offset_map_t;
 typedef hash_map<tree, field_offsets_t> record_field_offset_map2_t;
 
 // Partition types into escaping or non escaping sets.
-tpartitions_t
-partition_types_into_escaping_nonescaping (hash_map<tree, bool>*);
+void
+partition_types_into_escaping_nonescaping (tpartitions2_t &p, hash_map<tree, bool>*);
 
 // Compute set of not escaping unaccessed fields
 record_field_offset_map_t
-obtain_nonescaping_unaccessed_fields (tpartitions_t casting,
+obtain_nonescaping_unaccessed_fields (tpartitions2_t casting,
 				      record_field_map_t record_field_map,
 				      int warning);