Re: Fix alignment propagation

[Martin Jambor <mjambor at suse dot cz>]

Hi,

I have not managed to ping this, get it approved and commit it in time
for gcc 5 but it is a useful cleanup that clarifies a number of things
and something I'd like to base further cleanups on.  It still applies
cleanly and I have re-tested and re-bootstrapped the patch on
x86_64-linux without any issues.

So, OK for trunk now?

Thanks,

Martin


On Wed, Feb 25, 2015 at 08:38:26PM +0100, Martin Jambor wrote:
> 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" } } */