[6/7] Real aggregate contents merge and application of deltas

Index: src/gcc/ipa-prop.c
===================================================================
--- src.orig/gcc/ipa-prop.c
+++ src/gcc/ipa-prop.c
@@ -172,6 +172,10 @@  struct ipa_bb_info
   /* Aggregate contents of tracked references at the beginning of each BB.  */
   vec<ipa_known_agg_contents_list *> begin_agg_cnt;
 
+  /* True if this BB is the designated owner of the corresponding pointer in
+     begin_agg_cnt. */
+  vec<bool> own_begin_agg_cnt;
+
   /* Changes in aggregate contents of tracked references.  */
   vec<ipa_known_agg_contents_list *> agg_deltas;
 
@@ -1993,26 +1997,77 @@  determine_locally_known_aggregate_parts
     }
 }
 
-/* Apply basic block DELTAS to INITial aggregate contents description.  */
+/* Apply basic block DELTAS to INITial aggregate contents description.  FBI
+   describes the current function.  Set *OWN to true if the result is
+   exclusively held and can be modified in place.  */
 
 static struct ipa_known_agg_contents_list *
-apply_agg_contents_deltas (struct ipa_known_agg_contents_list *init,
-			   struct ipa_known_agg_contents_list *deltas)
+apply_agg_contents_deltas (struct func_body_info *fbi,
+			   struct ipa_known_agg_contents_list *init,
+			   struct ipa_known_agg_contents_list *deltas,
+			   bool *own)
 {
-  /* TODO: This over-conservative but should work for Fortran descriptors.
-     Will be replaced in a subsequent patches with real merging.  */
-
-  gcc_assert (init != AGG_CONTENTS_TOP);
-  if (deltas)
-    return deltas;
-  else
-    {
+  gcc_checking_assert (init != AGG_CONTENTS_TOP);
 #ifdef ENABLE_CHECKING
-      for (struct ipa_known_agg_contents_list *p = init; p; p = p->next)
-	gcc_assert (p->only_unescaped);
+  for (struct ipa_known_agg_contents_list *p = init; p; p = p->next)
+    gcc_assert (p->only_unescaped);
 #endif
+
+  if (!init)
+    {
+      *own = false;
+      return deltas;
+    }
+  if (!deltas)
+    {
+      *own = false;
       return init;
     }
+
+  *own = true;
+  struct ipa_known_agg_contents_list *list = NULL, **r = &list;
+  while (init || deltas)
+    {
+      struct ipa_known_agg_contents_list *p = NULL;
+      if (deltas && (!init || deltas->offset < init->offset))
+	{
+	  if (deltas->constant)
+	    p = deltas;
+	  while (init && init->offset < deltas->offset + deltas->size)
+	    init = init->next;
+	  deltas = deltas->next;
+	}
+      else if (init && (!deltas || init->offset < deltas->offset))
+	{
+	  if (init->constant
+	      && (!deltas
+		  || init->offset + init->size >= deltas->offset))
+	    p = init;
+	  init = init->next;
+	}
+      else
+	{
+	  gcc_checking_assert (init->offset == deltas->offset);
+	  if (deltas->constant)
+	    p = deltas;
+	  while (init && init->offset < deltas->offset + deltas->size)
+	    init = init->next;
+	  deltas = deltas->next;
+	}
+
+      if (p)
+	{
+	  *r = (struct ipa_known_agg_contents_list *)
+	    pool_alloc (fbi->agg_contents_pool);
+	  (*r)->offset = p->offset;
+	  (*r)->size = p->size;
+	  (*r)->constant = p->constant;
+	  (*r)->only_unescaped = p->only_unescaped;
+	  (*r)->next = NULL;
+	  r = &(*r)->next;
+	}
+    }
+  return list;
 }
 
 static tree
@@ -2264,9 +2319,10 @@  ipa_compute_jump_functions_for_edge (str
 		  struct ipa_bb_info *bi;
 		  bi = ipa_get_bb_info (fbi, gimple_bb (cs->call_stmt));
 		  struct ipa_known_agg_contents_list *begin, *final, *p;
+		  bool dummy;
 		  begin = bi->begin_agg_cnt[ref_index];
-		  final = apply_agg_contents_deltas (begin, (*dvec)[n]);
-
+		  final = apply_agg_contents_deltas (fbi, begin, (*dvec)[n],
+						     &dummy);
 		  int const_count = 0;
 		  for (p = final; p; p = p->next)
 		    if (p->constant)
@@ -2892,6 +2948,8 @@  ipa_analyze_bb_statements (struct func_b
 	      sizeof (int) * ipa_get_tracked_refs_count (fbi->info));
 
       bi->begin_agg_cnt.safe_grow (ipa_get_tracked_refs_count (fbi->info));
+      bi->own_begin_agg_cnt.safe_grow_cleared
+	(ipa_get_tracked_refs_count (fbi->info));
       for (int i = 0; i < ipa_get_tracked_refs_count (fbi->info); ++i)
 	bi->begin_agg_cnt[i] = AGG_CONTENTS_TOP;
     }
@@ -2982,6 +3040,7 @@  free_ipa_bb_info (struct ipa_bb_info *bi
   bi->cg_edges.release ();
   bi->param_aa_statuses.release ();
   bi->begin_agg_cnt.release ();
+  bi->own_begin_agg_cnt.release ();
   bi->agg_deltas.release ();
 }
 
@@ -3313,31 +3372,123 @@  gather_picked_escapes (struct func_body_
     }
 }
 
-/* Merge aggregate contents FINAL with those in *TARGET.  Return true if those
-   in *TARGET have changed.  */
+/* Remova all items from the list in *TARGET that are not also in INCOMING.
+   Return true if any was actually removed.  */
 
 static bool
-merge_agg_contents (struct ipa_known_agg_contents_list *final,
+prune_agg_contents (struct ipa_known_agg_contents_list *incoming,
 		    struct ipa_known_agg_contents_list **target)
 {
-  /* TODO: This over-conservative but should work for Fortran descriptors.
-     Will be replaced in a subsequent patches by real merging.  */
+  bool res = false;
+  while (*target && incoming)
+    {
+      if ((*target)->offset > incoming->offset)
+	{
+	  while (*target
+		 && (*target)->offset > incoming->offset
+		 && (*target)->offset < incoming->offset + incoming->size)
+	    {
+	      *target = (*target)->next;
+	      res = true;
+	    }
+
+	  incoming = incoming->next;
+	}
+      else if ((*target)->offset < incoming->offset)
+	{
+	  while (incoming
+		 && (*target)->offset < incoming->offset
+		 && (*target)->offset + (*target)->size > incoming->size)
+	    incoming = incoming->next;
+
+	  *target = (*target)->next;
+	  res = true;
+	}
+      else if ((*target)->size != incoming->size
+	       || !(*target)->constant
+	       || !incoming->constant
+	       || !operand_equal_p ((*target)->constant, incoming->constant, 0))
+	{
+	  *target = (*target)->next;
+	  incoming = incoming->next;
+	  res = true;
+	}
+      else
+	{
+	  gcc_checking_assert ((*target)->only_unescaped);
+	  target = &(*target)->next;
+	  incoming = incoming->next;
+	}
+    }
+
+  res |= *target != NULL;
+  *target = NULL;
+  return res;
+}
+
+/* Merge aggregate contents INCOMING with those in *TARGET.  Return true if
+   those in *TARGET have changed.  FBI describes the current function.  INC_OWN
+   determines whether the INCOMING list is exclusively owned and can be
+   modified in place or not.  TARGET_OWN points to a flag that describes
+   *TARGET in the same way and which may be modified.  */
+
+static bool
+merge_agg_contents (struct func_body_info *fbi,
+		    struct ipa_known_agg_contents_list *incoming, bool inc_own,
+		    struct ipa_known_agg_contents_list **target,
+		    bool *target_own)
+{
   if (*target == AGG_CONTENTS_TOP)
     {
-      *target = final;
+      *target = incoming;
+      *target_own = inc_own;
       return true;
     }
-  else if (*target != final)
+  if (*target == NULL
+      || *target == incoming)
+    return false;
+
+  if (*target_own)
+    return prune_agg_contents (incoming, target);
+
+  /* TODO: This may save some memory but is it worthwile? */
+  for (struct ipa_known_agg_contents_list *p = (*target)->next; p; p = p->next)
+    if (p == incoming)
+      {
+	*target = p;
+	return true;
+      }
+
+  struct ipa_known_agg_contents_list *p = *target, *list = NULL, **r = &list;
+  while (p && incoming)
     {
-      if (*target)
+      if (p->offset > incoming->offset)
+	incoming = incoming->next;
+      else if (p->offset < incoming->offset)
+	p = p->next;
+      else
 	{
-	  *target = NULL;
-	  return true;
+	  if (p->size == incoming->size
+	      && p->constant
+	      && incoming->constant
+	      && operand_equal_p (p->constant, incoming->constant, 0))
+	    {
+	      *r = (struct ipa_known_agg_contents_list *)
+		pool_alloc (fbi->agg_contents_pool);
+	      (*r)->offset = p->offset;
+	      (*r)->size = p->size;
+	      (*r)->constant = p->constant;
+	      (*r)->only_unescaped = true;
+	      (*r)->next = NULL;
+	      r = &(*r)->next;
+	    }
+	  p = p->next;
+	  incoming = incoming->next;
 	}
-      else
-	return false;
     }
-  return false;
+  *target_own = true;
+  *target = list;
+  return true;
 }
 
 /* Apply all computed aggregate deltas for the given BB and merge results into
@@ -3356,7 +3507,10 @@  propagate_agg_cnts_through_bb (struct fu
     else
       deltas = bi->agg_deltas[i];
 
-    final = apply_agg_contents_deltas (bi->begin_agg_cnt[i], deltas);
+    bool fin_own;
+    final = apply_agg_contents_deltas (fbi, bi->begin_agg_cnt[i], deltas,
+				       &fin_own);
+    fin_own = fin_own && single_succ_p (bb);
 
     edge e;
     edge_iterator ei;
@@ -3371,7 +3525,9 @@  propagate_agg_cnts_through_bb (struct fu
 
 	gcc_checking_assert (succ_info->begin_agg_cnt.length ()
 			     >= (unsigned) i);
-	if (merge_agg_contents (final, &succ_info->begin_agg_cnt[i])
+	if (merge_agg_contents (fbi, final, fin_own,
+				&succ_info->begin_agg_cnt[i],
+				&succ_info->own_begin_agg_cnt[i])
 	    && !succ_info->queued)
 	  {
 	    succ_info->queued = true;
Index: src/gcc/testsuite/gcc.dg/ipa/ipcp-agg-15.c
===================================================================
--- /dev/null
+++ src/gcc/testsuite/gcc.dg/ipa/ipcp-agg-15.c
@@ -0,0 +1,45 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -fno-ipa-sra -fdump-ipa-cp-details"  } */
+/* { dg-add-options bind_pic_locally } */
+
+struct S
+{
+  int i,j;
+};
+
+volatile int g;
+int *p;
+
+static int __attribute__ ((noinline, noclone))
+something_unpredictable (void)
+{
+  *p = 6;
+  return 1;
+}
+
+
+static void __attribute__ ((noinline))
+bar (struct S *ps)
+{
+  something_unpredictable ();
+  g = ps->j;
+}
+
+int
+main (int argc, char **argv)
+{
+  struct S s;
+
+  s.i = 2;
+  s.j = 8;
+
+  if (something_unpredictable ())
+    s.i = 6;
+
+  bar (&s);
+
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Creating a specialized node of bar.*for all known contexts" "cp" } } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */