This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Fix alignment propagation
- From: Martin Jambor <mjambor at suse dot cz>
- To: Jan Hubicka <hubicka at ucw dot cz>, gcc-patches at gcc dot gnu dot org
- Date: Thu, 21 May 2015 15:59:22 +0200
- Subject: Re: Fix alignment propagation
- Authentication-results: sourceware.org; auth=none
- References: <20150219233929 dot GA21632 at kam dot mff dot cuni dot cz> <20150219234421 dot GD23138 at redhat dot com> <20150220051647 dot GB21632 at kam dot mff dot cuni dot cz> <20150220140809 dot GC21948 at virgil dot suse> <20150220182202 dot GC21632 at kam dot mff dot cuni dot cz> <20150225193825 dot GG20953 at virgil dot suse>
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" } } */