Re: Fix alignment propagation

[Martin Jambor <mjambor at suse dot cz>]

Hi,

On Fri, Feb 20, 2015 at 07:22:02PM +0100, Jan Hubicka wrote:
> > > +/* Decrease alignment info DEST to be at most CUR.  */
> > > +
> > > +static bool
> > > +decrease_alignment (ipa_alignment *dest, ipa_alignment cur)
> > > +{
> > > +  bool changed = false;
> > > +
> > > +  if (!cur.known)
> > > +    return false;
> > 
> > I really think this should be return set_alignment_to_bottom (dest);
> > 
> > If some known alignment has been already propagated to DEST along a
> > different edge and now along the current edge an unknown alignment is
> > coming in, then the result value of the lattice must be BOTTOM and not
> > the previous alignment this code leaves in place.
> 
> Well, because this is an optimisitic propagation now, !cur.known means TOP
> that is "as good alginment as you can thunk of".
> You have one known alignment in DEST and TOP in other, result is TOP.

It seems to be clear now that the fact that I used the same structure
for the alignment information in the jump function and for the
alignment lattice (and so for example known meant pessimistic
assumptions in the former but optimistic in the latter) was really a
confusing idea.  So, at the risk of proposing a slightly larger patch
at this late stage, let me backtrack and come up with a real lattice,
with bottom and top which are called that way and with a real meet
operation.  Otherwise, the functionality the same as Honza's patch,
with the increase_alignment function ditched, because it would never
be used anyway.  We can revisit that in the next stage1, just as we
can perhaps make the storage more compact.  At this point I wanted to
minimize risk.

The decrease_alignment is now called meet_with and I hope it is now
clear why I requested the changes.

The patch is currently undergoing bootstrap and testing, Honza
promised to test on Firefox, it would be great if people burnt by the
second bug in PR 65028 could run their tests too.

It's likely there will be comments I'll need to incorporate, but I
would like to commit this soon to avoid the confusion the multiple
uses of ipa_alignment structure apparently caused.

Thanks,

Martin


2015-02-25  Martin Jambor  <mjambor@suse.cz>
	    Jan Hubicka  <hubicka@ucw.cz>

	* ipa-cp.c (ipcp_alignment_lattice): New type.
	(ipcp_param_lattices): Use the above to represent alignment.
	(ipcp_alignment_lattice::print): New function.
	(print_all_lattices): Use it to print alignment information.
	(ipcp_alignment_lattice::top_p): New function.
	(ipcp_alignment_lattice::bottom_p): Likewise.
	(ipcp_alignment_lattice::set_to_bottom): Likewise.
	(ipcp_alignment_lattice::meet_with_1): Likewise.
	(ipcp_alignment_lattice::meet_with): Two new overloaded functions.
	(set_all_contains_variable): Use set_to_bottom of alignment lattice.
	(initialize_node_lattices): Likewise.
	(propagate_alignment_accross_jump_function): Work with the new class
	for alignment lattices.
	(propagate_constants_accross_call): Pass only the alignment lattice to
	propagate_alignment_accross_jump_function.
	(ipcp_store_alignment_results): Work with the new class for alignment
	lattices.

testsuite/
	* gcc.dg/ipa/propalign-4.c: New test.
	* gcc.dg/ipa/propalign-5.c: Likewise.

diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index bfe4d97..5ebe04a 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -257,6 +257,36 @@ public:
   struct ipcp_agg_lattice *next;
 };
 
+/* Lattice of pointer alignment.  Unlike the previous types of lattices, this
+   one is only capable of holding one value.  */
+
+class ipcp_alignment_lattice
+{
+public:
+  /* If bottom and top are both false, these two fields hold values as given by
+     ptr_info_def and get_pointer_alignment_1.  */
+  unsigned align;
+  unsigned misalign;
+
+  inline bool bottom_p () const;
+  inline bool top_p () const;
+  inline bool set_to_bottom ();
+  bool meet_with (unsigned new_align, unsigned new_misalign);
+  bool meet_with (const ipcp_alignment_lattice &other, HOST_WIDE_INT offset);
+  void print (FILE * f);
+private:
+  /* If set, this lattice is bottom and all other fields should be
+     disregarded.  */
+  bool bottom;
+  /* If bottom and not_top are false, the lattice is TOP.  If not_top is true,
+     the known alignment is stored in the fields align and misalign.  The field
+     is negated so that memset to zero initializes the lattice to TOP
+     state.  */
+  bool not_top;
+
+  bool meet_with_1 (unsigned new_align, unsigned new_misalign);
+};
+
 /* Structure containing lattices for a parameter itself and for pieces of
    aggregates that are passed in the parameter or by a reference in a parameter
    plus some other useful flags.  */
@@ -270,9 +300,8 @@ public:
   ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
   /* Lattices describing aggregate parts.  */
   ipcp_agg_lattice *aggs;
-  /* Alignment information.  Very basic one value lattice where !known means
-     TOP and zero alignment bottom.  */
-  ipa_alignment alignment;
+  /* Lattice describing known alignment.  */
+  ipcp_alignment_lattice alignment;
   /* Number of aggregate lattices */
   int aggs_count;
   /* True if aggregate data were passed by reference (as opposed to by
@@ -430,6 +459,19 @@ ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
     fprintf (f, "\n");
 }
 
+/* Print alignment lattice to F.  */
+
+void
+ipcp_alignment_lattice::print (FILE * f)
+{
+  if (top_p ())
+    fprintf (f, "         Alignment unknown (TOP)\n");
+  else if (bottom_p ())
+    fprintf (f, "         Alignment unusable (BOTTOM)\n");
+  else
+    fprintf (f, "         Alignment %u, misalignment %u\n", align, misalign);
+}
+
 /* Print all ipcp_lattices of all functions to F.  */
 
 static void
@@ -455,13 +497,7 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
 	  plats->itself.print (f, dump_sources, dump_benefits);
 	  fprintf (f, "         ctxs: ");
 	  plats->ctxlat.print (f, dump_sources, dump_benefits);
-	  if (plats->alignment.known && plats->alignment.align > 0)
-	    fprintf (f, "         Alignment %u, misalignment %u\n",
-		     plats->alignment.align, plats->alignment.misalign);
-	  else if (plats->alignment.known)
-	    fprintf (f, "         Alignment unusable\n");
-	  else
-	    fprintf (f, "         Alignment unknown\n");
+	  plats->alignment.print (f);
 	  if (plats->virt_call)
 	    fprintf (f, "        virt_call flag set\n");
 
@@ -776,27 +812,111 @@ set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
   return ret;
 }
 
-/* Return true if alignment information in PLATS is known to be unusable.  */
+/* Return true if alignment information in the lattice is yet unknown.  */
 
-static inline bool
-alignment_bottom_p (ipcp_param_lattices *plats)
+bool
+ipcp_alignment_lattice::top_p () const
 {
-  return plats->alignment.known && (plats->alignment.align == 0);
+  return !bottom && !not_top;
 }
 
-/* Set alignment information in PLATS to unusable.  Return true if it
-   previously was usable or unknown.  */
+/* Return true if alignment information in the lattice is known to be
+   unusable.  */
 
-static inline bool
-set_alignment_to_bottom (ipcp_param_lattices *plats)
+bool
+ipcp_alignment_lattice::bottom_p () const
+{
+  return bottom;
+}
+
+/* Set alignment information in the lattice to bottom.  Return true if it
+   previously was in a different state.  */
+
+bool
+ipcp_alignment_lattice::set_to_bottom ()
 {
-  if (alignment_bottom_p (plats))
+  if (bottom_p ())
     return false;
-  plats->alignment.known = true;
-  plats->alignment.align = 0;
+  bottom = true;
   return true;
 }
 
+/* Meet the current value of the lattice with alignment described by NEW_ALIGN
+   and NEW_MISALIGN, assuming that we know the current value is neither TOP nor
+   BOTTOM.  Return true if the value of lattice has changed.  */
+
+bool
+ipcp_alignment_lattice::meet_with_1 (unsigned new_align, unsigned new_misalign)
+{
+  gcc_checking_assert (new_align != 0);
+  if (align == new_align && misalign == new_misalign)
+    return false;
+
+  bool changed = false;
+  if (align > new_align)
+    {
+      align = new_align;
+      misalign = misalign % new_align;
+      changed = true;
+    }
+  if (misalign != (new_misalign % align))
+    {
+      int diff = abs (misalign - (new_misalign % align));
+      align = MIN (align, (unsigned) diff & -diff);
+      if (align)
+	misalign = misalign % align;
+      else
+	set_to_bottom ();
+      changed = true;
+    }
+  gcc_checking_assert (bottom_p () || align != 0);
+  return changed;
+}
+
+/* Meet the current value of the lattice with alignment described by NEW_ALIGN
+   and NEW_MISALIGN.  Return true if the value of lattice has changed.  */
+
+bool
+ipcp_alignment_lattice::meet_with (unsigned new_align, unsigned new_misalign)
+{
+  gcc_assert (new_align != 0);
+  if (bottom_p ())
+    return false;
+  if (top_p ())
+    {
+      not_top = true;
+      align = new_align;
+      misalign = new_misalign;
+      return true;
+    }
+  return meet_with_1 (new_align, new_misalign);
+}
+
+/* Meet the current value of the lattice with OTHER, taking into account that
+   OFFSET has been added to the pointer value.  Return true if the value of
+   lattice has changed.  */
+
+bool
+ipcp_alignment_lattice::meet_with (const ipcp_alignment_lattice &other,
+				   HOST_WIDE_INT offset)
+{
+  if (other.bottom_p ())
+    return set_to_bottom ();
+  if (bottom_p () || other.top_p ())
+    return false;
+
+  unsigned adjusted_misalign = (other.misalign + offset) % other.align;
+  if (top_p ())
+    {
+      not_top = true;
+      align = other.align;
+      misalign = adjusted_misalign;
+      return true;
+    }
+
+  return meet_with_1 (other.align, adjusted_misalign);
+}
+
 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
    return true is any of them has not been marked as such so far.  */
 
@@ -807,7 +927,7 @@ set_all_contains_variable (struct ipcp_param_lattices *plats)
   ret = plats->itself.set_contains_variable ();
   ret |= plats->ctxlat.set_contains_variable ();
   ret |= set_agg_lats_contain_variable (plats);
-  ret |= set_alignment_to_bottom (plats);
+  ret |= plats->alignment.set_to_bottom ();
   return ret;
 }
 
@@ -844,7 +964,7 @@ initialize_node_lattices (struct cgraph_node *node)
 	      plats->itself.set_to_bottom ();
 	      plats->ctxlat.set_to_bottom ();
 	      set_agg_lats_to_bottom (plats);
-	      set_alignment_to_bottom (plats);
+	      plats->alignment.set_to_bottom ();
 	    }
 	  else
 	    set_all_contains_variable (plats);
@@ -1413,22 +1533,17 @@ propagate_context_accross_jump_function (cgraph_edge *cs,
    edge CS and update DEST_LAT accordingly.  */
 
 static bool
-propagate_alignment_accross_jump_function (struct cgraph_edge *cs,
-					   struct ipa_jump_func *jfunc,
-					   struct ipcp_param_lattices *dest_lat)
+propagate_alignment_accross_jump_function (cgraph_edge *cs,
+					   ipa_jump_func *jfunc,
+					   ipcp_alignment_lattice *dest_lat)
 {
-  if (alignment_bottom_p (dest_lat))
+  if (dest_lat->bottom_p ())
     return false;
 
-  ipa_alignment cur;
-  cur.known = false;
-  if (jfunc->alignment.known)
-    cur = jfunc->alignment;
-  else if (jfunc->type == IPA_JF_PASS_THROUGH
+  if (jfunc->type == IPA_JF_PASS_THROUGH
 	   || jfunc->type == IPA_JF_ANCESTOR)
     {
       struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
-      struct ipcp_param_lattices *src_lats;
       HOST_WIDE_INT offset = 0;
       int src_idx;
 
@@ -1439,10 +1554,10 @@ propagate_alignment_accross_jump_function (struct cgraph_edge *cs,
 	    {
 	      if (op != POINTER_PLUS_EXPR
 		  && op != PLUS_EXPR)
-		goto prop_fail;
+		return dest_lat->set_to_bottom ();
 	      tree operand = ipa_get_jf_pass_through_operand (jfunc);
 	      if (!tree_fits_shwi_p (operand))
-		goto prop_fail;
+		return dest_lat->set_to_bottom ();
 	      offset = tree_to_shwi (operand);
 	    }
 	  src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
@@ -1450,33 +1565,21 @@ propagate_alignment_accross_jump_function (struct cgraph_edge *cs,
       else
 	{
 	  src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
-	  offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;;
+	  offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
 	}
 
+      struct ipcp_param_lattices *src_lats;
       src_lats = ipa_get_parm_lattices (caller_info, src_idx);
-      if (!src_lats->alignment.known
-	  || alignment_bottom_p (src_lats))
-	goto prop_fail;
-
-      cur = src_lats->alignment;
-      cur.misalign = (cur.misalign + offset) % cur.align;
+      return dest_lat->meet_with (src_lats->alignment, offset);
     }
-
-  if (cur.known)
+  else
     {
-      if (!dest_lat->alignment.known)
-	{
-	  dest_lat->alignment = cur;
-	  return true;
-	}
-      else if (dest_lat->alignment.align == cur.align
-	       && dest_lat->alignment.misalign == cur.misalign)
-	return false;
+      if (jfunc->alignment.known)
+	return dest_lat->meet_with (jfunc->alignment.align,
+				    jfunc->alignment.misalign);
+      else
+	return dest_lat->set_to_bottom ();
     }
-
- prop_fail:
-  set_alignment_to_bottom (dest_lat);
-  return true;
 }
 
 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
@@ -1816,7 +1919,7 @@ propagate_constants_accross_call (struct cgraph_edge *cs)
 	  ret |= propagate_context_accross_jump_function (cs, jump_func, i,
 							  &dest_plats->ctxlat);
 	  ret |= propagate_alignment_accross_jump_function (cs, jump_func,
-							    dest_plats);
+							 &dest_plats->alignment);
 	  ret |= propagate_aggs_accross_jump_function (cs, jump_func,
 						       dest_plats);
 	}
@@ -4338,9 +4441,10 @@ ipcp_store_alignment_results (void)
    for (unsigned i = 0; i < count ; i++)
      {
        ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
-       if (plats->alignment.known
-	   && plats->alignment.align > 0)
+       if (!plats->alignment.bottom_p ()
+	   && !plats->alignment.top_p ())
 	 {
+	   gcc_checking_assert (plats->alignment.align > 0);
 	   found_useful_result = true;
 	   break;
 	 }
@@ -4348,19 +4452,27 @@ ipcp_store_alignment_results (void)
    if (!found_useful_result)
      continue;
 
-  ipcp_grow_transformations_if_necessary ();
+   ipcp_grow_transformations_if_necessary ();
    ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
    vec_safe_reserve_exact (ts->alignments, count);
 
    for (unsigned i = 0; i < count ; i++)
      {
        ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
+       ipa_alignment al;
 
-       if (plats->alignment.align == 0)
-	 plats->alignment.known = false;
+       if (!plats->alignment.bottom_p ()
+	   && !plats->alignment.top_p ())
+	 {
+	   al.known = true;
+	   al.align = plats->alignment.align;
+	   al.misalign = plats->alignment.misalign;
+	 }
+       else
+	 al.known = false;
 
-       ts->alignments->quick_push (plats->alignment);
-       if (!dump_file || !plats->alignment.known)
+       ts->alignments->quick_push (al);
+       if (!dump_file || !al.known)
 	 continue;
        if (!dumped_sth)
 	 {
@@ -4369,7 +4481,7 @@ ipcp_store_alignment_results (void)
 	   dumped_sth = true;
 	 }
        fprintf (dump_file, "  param %i: align: %u, misalign: %u\n",
-		i, plats->alignment.align, plats->alignment.misalign);
+		i, al.align, al.misalign);
      }
   }
 }
diff --git a/gcc/testsuite/gcc.dg/ipa/propalign-4.c b/gcc/testsuite/gcc.dg/ipa/propalign-4.c
new file mode 100644
index 0000000..0dbbcf1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/propalign-4.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-cp"  } */
+int n;
+
+static void
+__attribute__ ((noinline))
+test(void *a)
+{
+  __builtin_memset (a,0,n);
+}
+
+static __attribute__ ((aligned(16))) int aa[10];
+
+int
+main()
+{
+  test (&aa[1]);
+  test (&aa[3]);
+  return 0;
+}
+/* { dg-final { scan-ipa-dump "Alignment 8, misalignment 4"  "cp"  } } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/propalign-5.c b/gcc/testsuite/gcc.dg/ipa/propalign-5.c
new file mode 100644
index 0000000..b1ec4d4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/propalign-5.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-cp"  } */
+int n;
+
+static void
+__attribute__ ((noinline))
+test(void *a)
+{
+  __builtin_memset (a,0,n);
+}
+
+int
+main()
+{
+  int aa;
+  short bb;
+  test (&aa);
+  test (&bb);
+  return 0;
+}
+/* { dg-final { scan-ipa-dump "Alignment 2"  "cp"  } } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */