On Tue, 9 Jan 2024, Tamar Christina wrote:
>
>
> > -----Original Message-----
> > From: Richard Biener <rguent...@suse.de>
> > Sent: Tuesday, January 9, 2024 12:26 PM
> > To: Tamar Christina <tamar.christ...@arm.com>
> > Cc: gcc-patches@gcc.gnu.org; nd <n...@arm.com>; j...@ventanamicro.com
> > Subject: RE: [PATCH]middle-end: Fix dominators updates when peeling with
> > multiple exits [PR113144]
> >
> > On Tue, 9 Jan 2024, Tamar Christina wrote:
> >
> > > > This makes it quadratic in the number of vectorized early exit loops
> > > > in a function. The vectorizer CFG manipulation operates in a local
> > > > enough bubble that programmatic updating of dominators should be
> > > > possible (after all we manage to produce correct SSA form!), the
> > > > proposed change gets us too far off to a point where re-computating
> > > > dominance info is likely cheaper (but no, we shouldn't do this either).
> > > >
> > > > Can you instead give manual updating a try again? I think
> > > > versioning should produce up-to-date dominator info, it's only
> > > > when you redirect branches during peeling that you'd need
> > > > adjustments - but IIRC we're never introducing new merges?
> > > >
> > > > IIRC we can't wipe dominators during transform since we query them
> > > > during code generation. We possibly could code generate all
> > > > CFG manipulations of all vectorized loops, recompute all dominators
> > > > and then do code generation of all vectorized loops.
> > > >
> > > > But then we're doing a loop transform and the exits will ultimatively
> > > > end up in the same place, so the CFG and dominator update is bound to
> > > > where the original exits went to.
> > >
> > > Yeah that's a fair point, the issue is specifically with at_exit. So how
> > > about:
> > >
> > > When we peel at_exit we are moving the new loop at the exit of the
> > > previous
> > > loop. This means that the blocks outside the loop dat the previous loop
> > > used to
> > > dominate are no longer being dominated by it.
> >
> > Hmm, indeed. Note this does make the dominator update O(function-size)
> > and when vectorizing multiple loops in a function this becomes
> > quadratic. That's quite unfortunate so I wonder if we can delay the
> > update to the parts we do not need up-to-date dominators during
> > vectorization (of course it gets fragile with having only partly
> > correct dominators).
>
> Fair, I created https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113290 and will
> tackle it when I add SLP support in GCC 15.
>
> I think the problem is, and the reason we do early dominator correction and
> validation is because the same function is used by loop distribution.
>
> But you're right that during vectorization we perform dominators update twice
> now.
We're performing it at least once per multi-exit loop that is vectorized,
covering all downstream blocks.
> So Maybe we should have a parameter to indicate whether dominators should
> be updated?
I think we should possibly try making loop distribution use another
mechanism for its copying ... there's duplicate_loop_body_to_header_edge
that's also used by loop_version, the core parts doing the new
loop creation could be split out and the detail how the final CFG
is set up be retained in two workers.
Richard.
> Thanks,
> Tamar
>
> >
> > > The new dominators however are hard to predict since if the loop has
> > > multiple
> > > exits and all the exits are an "early" one then we always execute the
> > > scalar
> > > loop. In this case the scalar loop can completely dominate the new loop.
> > >
> > > If we later have skip_vector then there's an additional skip edge added
> > > that
> > > might change the dominators.
> > >
> > > The previous patch would force an update of all blocks reachable from the
> > > new
> > > exits. This one updates *only* blocks that we know the scalar exits
> > > dominated.
> > >
> > > For the examples this reduces the blocks to update from 18 to 3.
> > >
> > > Bootstrapped Regtested on aarch64-none-linux-gnu, x86_64-pc-linux-gnu
> > > and no issues normally and with --enable-checking=release --enable-lto
> > > --with-build-config=bootstrap-O3 --enable-checking=yes,rtl,extra.
> > >
> > > Ok for master?
> >
> > See below.
> >
> > > Thanks,
> > > Tamar
> > >
> > > gcc/ChangeLog:
> > >
> > > PR tree-optimization/113144
> > > PR tree-optimization/113145
> > > * tree-vect-loop-manip.cc (slpeel_tree_duplicate_loop_to_edge_cfg):
> > > Update all BB that the original exits dominated.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > > PR tree-optimization/113144
> > > PR tree-optimization/113145
> > > * gcc.dg/vect/vect-early-break_94-pr113144.c: New test.
> > >
> > > --- inline copy of patch ---
> > >
> > > diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_94-pr113144.c
> > b/gcc/testsuite/gcc.dg/vect/vect-early-break_94-pr113144.c
> > > new file mode 100644
> > > index
> > 0000000000000000000000000000000000000000..903fe7be6621e81db6f294
> > 41e4309fa213d027c5
> > > --- /dev/null
> > > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_94-pr113144.c
> > > @@ -0,0 +1,41 @@
> > > +/* { dg-do compile } */
> > > +/* { dg-add-options vect_early_break } */
> > > +/* { dg-require-effective-target vect_early_break } */
> > > +/* { dg-require-effective-target vect_int } */
> > > +
> > > +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
> > > +
> > > +long tar_atol256_max, tar_atol256_size, tar_atosl_min;
> > > +char tar_atol256_s;
> > > +void __errno_location();
> > > +
> > > +
> > > +inline static long tar_atol256(long min) {
> > > + char c;
> > > + int sign;
> > > + c = tar_atol256_s;
> > > + sign = c;
> > > + while (tar_atol256_size) {
> > > + if (c != sign)
> > > + return sign ? min : tar_atol256_max;
> > > + c = tar_atol256_size--;
> > > + }
> > > + if ((c & 128) != (sign & 128))
> > > + return sign ? min : tar_atol256_max;
> > > + return 0;
> > > +}
> > > +
> > > +inline static long tar_atol(long min) {
> > > + return tar_atol256(min);
> > > +}
> > > +
> > > +long tar_atosl() {
> > > + long n = tar_atol(-1);
> > > + if (tar_atosl_min) {
> > > + __errno_location();
> > > + return 0;
> > > + }
> > > + if (n > 0)
> > > + return 0;
> > > + return n;
> > > +}
> > > diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
> > > index
> > 76d4979c0b3b374dcaacf6825a95a8714114a63b..9bacaa182a3919cae1cb99dfc
> > 5ae4923e1f93376 100644
> > > --- a/gcc/tree-vect-loop-manip.cc
> > > +++ b/gcc/tree-vect-loop-manip.cc
> > > @@ -1719,8 +1719,6 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop
> > *loop, edge loop_exit,
> > > /* Now link the alternative exits. */
> > > if (multiple_exits_p)
> > > {
> > > - set_immediate_dominator (CDI_DOMINATORS, new_preheader,
> > > - main_loop_exit_block);
> > > for (auto gsi_from = gsi_start_phis (loop->header),
> > > gsi_to = gsi_start_phis (new_preheader);
> > > !gsi_end_p (gsi_from) && !gsi_end_p (gsi_to);
> > > @@ -1776,7 +1774,14 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop
> > *loop, edge loop_exit,
> > > {
> > > update_loop = new_loop;
> > > for (edge e : get_loop_exit_edges (loop))
> > > - doms.safe_push (e->dest);
> > > + {
> > > + /* Basic blocks that the old loop dominated are now dominated by
> > > + the new loop and so we have to update those. */
> > > + for (auto bb : get_all_dominated_blocks (CDI_DOMINATORS, e->src))
> > > + if (!flow_bb_inside_loop_p (loop, bb))
> > > + doms.safe_push (bb);
> > > + doms.safe_push (e->dest);
> > > + }
> >
> > I think you'll get duplicate blocks that way. Maybe simplify this
> > all by instead doing
> >
> > auto doms = get_all_dominated_blocks (CDI_DOMINATORS,
> > loop->header);
> > for (unsigned i = 0; i < doms.length (); ++i)
> > if (flow_bb_inside_loop_p (loop, doms[i]))
> > doms.unordered_remove (i);
> >
> > ?
> >
> > OK with that change, but really we should see to avoid this
> > quadraticness :/ It's probably not too bad right now given we have
> > quite some restrictions on vectorizing loops with multiple exits,
> > but I suggest you try an artificial testcase with the "same"
> > loop repeated N times to see whether dominance compute creeps up
> > in the profile.
> >
> > Richard.
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
