Ping
> -----Original Message-----
> From: Tamar Christina
> Sent: Friday, January 24, 2025 9:18 AM
> To: Alex Coplan <alex.cop...@arm.com>; gcc-patches@gcc.gnu.org
> Cc: Richard Biener <rguent...@suse.de>; Jan Hubicka <hubi...@ucw.cz>
> Subject: RE: [PATCH 2/4] cfgloopmanip: Add infrastructure for scaling of
> multi-exit
> loops [PR117790]
>
> ping
>
> > -----Original Message-----
> > From: Tamar Christina
> > Sent: Wednesday, January 15, 2025 2:08 PM
> > To: Alex Coplan <alex.cop...@arm.com>; gcc-patches@gcc.gnu.org
> > Cc: Richard Biener <rguent...@suse.de>; Jan Hubicka <hubi...@ucw.cz>
> > Subject: RE: [PATCH 2/4] cfgloopmanip: Add infrastructure for scaling of
> > multi-
> exit
> > loops [PR117790]
> >
> > Ping
> >
> > > -----Original Message-----
> > > From: Alex Coplan <alex.cop...@arm.com>
> > > Sent: Monday, January 6, 2025 11:35 AM
> > > To: gcc-patches@gcc.gnu.org
> > > Cc: Richard Biener <rguent...@suse.de>; Jan Hubicka <hubi...@ucw.cz>;
> Tamar
> > > Christina <tamar.christ...@arm.com>
> > > Subject: [PATCH 2/4] cfgloopmanip: Add infrastructure for scaling of
> > > multi-exit
> > > loops [PR117790]
> > >
> > > As it stands, scale_loop_profile doesn't correctly handle loops with
> > > multiple exits. In particular, in the case where the expected niters
> > > exceeds iteration_bound, scale_loop_profile attempts to reduce the
> > > number of iterations with a call to scale_loop_frequencies, which
> > > multiplies the count of each BB by a given probability. This
> > > transformation preserves the relationships between the counts of the BBs
> > > within the loop (and thus the edge probabilities stay the same) but this
> > > cannot possibly work for loops with multiple exits, since in order for
> > > the expected niters to reduce (and counts along exit edges to remain the
> > > same), the exit edge probabilities must increase, thus decreasing the
> > > probabilities of the internal edges, meaning that the ratios of the
> > > counts of the BBs inside the loop must change. So we need a different
> > > approach (not a straightforward multiplicative scaling) to adjust the
> > > expected niters of a loop with multiple exits.
> > >
> > > This patch introduces a new helper, flow_scale_loop_freqs, which can be
> > > used to correctly scale the profile of a loop with multiple exits. It
> > > is parameterized by a probability (with which to scale the header and
> > > therefore the expected niters) and a lambda which gives the desired
> > > counts for the exit edges. In this patch, to make things simpler,
> > > flow_scale_loop_freqs only handles loop shapes without internal control
> > > flow, and we introduce a predicate can_flow_scale_loop_freqs_p to test
> > > whether a given loop meets these criteria. This restriction is
> > > reasonable since this patch is motivated by fixing the profile
> > > consistency for early break vectorization, and we don't currently
> > > vectorize loops with internal control flow. We also fall back to a
> > > multiplicative scaling (the status quo) for loops that
> > > flow_scale_loop_freqs can't handle, so the patch should be a net
> > > improvement.
> > >
> > > We wrap the call to flow_scale_loop_freqs in a helper
> > > scale_loop_freqs_with_exit_counts which handles the above-mentioned
> > > fallback. This wrapper is still generic in that it accepts a lambda to
> > > allow overriding the desired exit edge counts. We specialize this with
> > > another wrapper, scale_loop_freqs_hold_exit_counts (keeping the
> > > counts along exit edges fixed), which is then used to implement the
> > > niters-scaling case of scale_loop_profile, thus fixing this path through
> > > the function for loops with multiple exits.
> > >
> > > Finally, we expose two new wrapper functions in cfgloopmanip.h for use
> > > in subsequent vectorizer patches. scale_loop_profile_hold_exit_counts
> > > is a variant of scale_loop_profile which assumes we want to keep the
> > > counts along exit edges of the loop fixed through both parts of the
> > > transformation (including the initial probability scale).
> > > scale_loop_freqs_with_new_exit_count is intended to be used in a
> > > subsequent patch when adding a skip edge around the epilog, where the
> > > reduction of count entering the loop is mirrored by a reduced count
> > > along a given exit edge.
> > >
> > > Bootstrapped/regtested as a series on aarch64-linux-gnu,
> > > x86_64-linux-gnu, and arm-linux-gnueabihf. OK for trunk?
> > >
> > > Thanks,
> > > Alex
> > >
> > > gcc/ChangeLog:
> > >
> > > PR tree-optimization/117790
> > > * cfgloopmanip.cc (can_flow_scale_loop_freqs_p): New.
> > > (flow_scale_loop_freqs): New.
> > > (scale_loop_freqs_with_exit_counts): New.
> > > (scale_loop_freqs_hold_exit_counts): New.
> > > (scale_loop_profile): Refactor to use the newly-added
> > > scale_loop_profile_1, and use scale_loop_freqs_hold_exit_counts to
> > > correctly handle reducing the expected niters for loops with multiple
> > > exits.
> > > (scale_loop_freqs_with_new_exit_count): New.
> > > (scale_loop_profile_1): New.
> > > (scale_loop_profile_hold_exit_counts): New.
> > > * cfgloopmanip.h (scale_loop_profile_hold_exit_counts): New.
> > > (scale_loop_freqs_with_new_exit_count): New.
> > > ---
> > > gcc/cfgloopmanip.cc | 309
> > ++++++++++++++++++++++++++++++++++++++++--
> > > --
> > > gcc/cfgloopmanip.h | 7 +
> > > 2 files changed, 294 insertions(+), 22 deletions(-)
