> -----Original Message-----
> From: Richard Biener <[email protected]>
> Sent: 05 August 2026 13:57
> To: Tamar Christina <[email protected]>
> Cc: [email protected]; nd <[email protected]>; [email protected]; Jan
> Hubicka <[email protected]>
> Subject: Re: [patch][vect]: fix loop exit profiles with early break [PR118407]
>
> On Wed, 5 Aug 2026, Tamar Christina wrote:
>
> > It's been a few years since the patches for PR118407 but have been stuck on
> a
> > review.
> >
> > Those patches attempted to make an framework for supporting early break
> profiles
> > in not just the vectorizer but in other passes as well.
> >
> > This patch takes a different approach. We know that the vectorizer is the
> > one
> > introducing the inaccurate profile information, so have it fix it up.
> > There are
> > other places in the vectorizer where this happens for non-early break too.
> >
> > As an example this loop
> >
> > #ifndef N
> > #define N 800
> > #endif
> > unsigned vect_a[N];
> > unsigned vect_b[N];
> >
> > unsigned test4(unsigned x)
> > {
> > unsigned ret = 0;
> > for (int i = 0; i < N; i++)
> > {
> > vect_b[i] = x + i;
> > if (vect_a[i]*2 != x)
> > break;
> > vect_a[i] = x;
> >
> > }
> > return ret;
> > }
> >
> > generates with -O3 -march=armv9-a the following loop:
> >
> > test4:
> > cntw x1
> > cmp w1, 799
> > bhi .L7
> > adrp x4, .LANCHOR0
> > add x3, x4, :lo12:.LANCHOR0
> > ptrue p7.b, all
> > add x5, x3, 3200
> > mov w1, 0
> > mov z30.s, w0
> > mov w6, 800
> > index z29.s, #0, #1
> > b .L4
> > .L3:
> > st1w z28.s, p7, [x5, x1, lsl 2]
> > st1w z30.s, p7, [x3, x1, lsl 2]
> > incw z29.s
> > incw x1
> > whilelo p7.s, w1, w6
> > b.none .L5
> > .L4:
> > ld1w z31.s, p7/z, [x3, x1, lsl 2]
> > add z28.s, z29.s, z30.s
> > add z31.s, z31.s, z31.s
> > cmpne p15.s, p7/z, z31.s, z30.s
> > b.none .L3
> > mov w5, 800
> > mov w2, w1
> > sub w5, w5, w1
> > .L2:
> >
> > notice the pointless indirect branch to L4, and the commonly taken branch of
> .L3
> > has to do a branch back to the latch instead of a fall through. The CFG
> > becomes increasingly branchy as the number of exits increase.
> >
> > With this patch we generate:
> >
> > test4:
> > cntw x1
> > cmp w1, 799
> > bhi .L7
> > adrp x3, .LANCHOR0
> > add x3, x3, :lo12:.LANCHOR0
> > ptrue p7.b, all
> > add x4, x3, 3200
> > mov w1, 0
> > mov z30.s, w0
> > mov w5, 800
> > index z29.s, #0, #1
> > .p2align 5,,15
> > .L4:
> > ld1w z31.s, p7/z, [x3, x1, lsl 2]
> > add z28.s, z29.s, z30.s
> > add z31.s, z31.s, z31.s
> > cmpne p15.s, p7/z, z31.s, z30.s
> > b.any .L12
> > st1w z28.s, p7, [x4, x1, lsl 2]
> > st1w z30.s, p7, [x3, x1, lsl 2]
> > incw z29.s
> > incw x1
> > whilelo p7.s, w1, w5
> > b.any .L4
> > .L5:
> > mov w0, 0
> > ret
> >
> > which is a more natural layout because it now knows the exit is unlikely
> > since
> > they have been scaled correctly.
> >
> > The scaling is done by:
> >
> > let P be the scalar probability that one iteration takes an early exit edge.
> > 1 - P is then the probabiliy that the exit is not taken.
> >
> > Since every vector iteration handles VF scalar iterations, the early exit
> > branch can be taken when any of the lanes are true.
> >
> > We invert this and first calculate the probablity that you reach the latch,
> > i.e. the probability that the vector code does not exit is the probability
> > Q that none of the lanes are true.
> >
> > Q = (1 - P) * (1 - P) * ... * (1 - P)
> > = (1 - P) ^ VF
> >
> > and so the probability that at least one lane breaks is 1 - Q,
> > or rather 1 - (i - P) ^ VF.
> >
> > For example, if the scalar break probability is 10% and VF is 4:
> >
> > P = 0.1
> > 1 - P = 0.9
> > (1 - P) ^ VF = 0.9 ^ 4 = 0.6561
> > 1 - (1 - p) ^ VF = 1 - 0.6561 = 0.3439
> >
> > So a scalar early-exit edge that is taken 10% of the time becomes a vector
> > early-exit edge that is taken about 34.4% of the time, because each vector
> > iteration gives the break condition four chances to trigger.
> >
> > NOTE: This does not fully fix PR118407 but only fixes part of the issue.
> > there are other adjustments needed but this is the most glaring one.
> >
> > Bootstrapped Regtested on aarch64-none-linux-gnu,
> > arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
> > -m32, -m64 and no issues.
> >
> > Any comments?
> >
> > Thanks,
> > Tamar
> >
> > gcc/ChangeLog:
> >
> > PR tree-optimization/118407
> > * tree-vect-stmts.cc (vect_update_early_break_profiles): New.
> > (vect_update_ivs_after_vectorizer_for_early_breaks): Use it.
> >
> > gcc/testsuite/ChangeLog:
> >
> > PR tree-optimization/118407
> > * gcc.target/aarch64/sve/noeffect2.c: Update test.
> > * gcc.target/aarch64/sve/noeffect3.c: Likewise.
> >
> > ---
> > diff --git a/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> b/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> > index
> 5bb1badde3c4e07d06ba68b2c73ba591e031f611..7169ede3cda7108ce662
> 8c147d014dd03c5d57bf 100644
> > --- a/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> > +++ b/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> > @@ -9,14 +9,19 @@ int b[N] = {0};
> > /*
> > ** foo:
> > ** ...
> > +** ptrue p[0-9]+\.b, all
> > +** ...
> > ** whilelo p[0-9]+\.s, w[0-9]+, w[0-9]+
> > +** b\.none \.L[0-9]+
> > ** ...
> > ** ld1w z[0-9]+\.s, p[0-9]+/z, \[x[0-9]+, x[0-9]+, lsl 2\]
> > ** ld1w z[0-9]+\.s, p[0-9]+/z, \[x[0-9]+, x[0-9]+, lsl 2\]
> > ** cmpgt p[0-9]+\.s, p[0-9]+/z, z[0-9]+\.s, z[0-9]+\.s
> > ** b\.none \.L[0-9]+
> > +** ...
> > ** mov w0, 1
> > ** ret
> > +** ...
> > ** mov w0, 0
> > ** ret
> > */
> > diff --git a/gcc/testsuite/gcc.target/aarch64/sve/noeffect3.c
> b/gcc/testsuite/gcc.target/aarch64/sve/noeffect3.c
> > index
> c5f81bb0d303a070b482ec40d2921f6e6236ce67..8c20f39d2a467e636cfec
> 71acacb2da654a49d67 100644
> > --- a/gcc/testsuite/gcc.target/aarch64/sve/noeffect3.c
> > +++ b/gcc/testsuite/gcc.target/aarch64/sve/noeffect3.c
> > @@ -9,11 +9,14 @@ int b[N] = {0};
> > /*
> > ** foo:
> > ** ...
> > -** whilelo p[0-9]+\.s, w[0-9]+, w[0-9]+
> > +** ptrue p[0-9]+\.b, all
> > ** ...
> > ** ld1w z[0-9]+\.s, p[0-9]+/z, \[x[0-9]+, x[0-9]+, lsl 2\]
> > ** ld1w z[0-9]+\.s, p[0-9]+/z, \[x[0-9]+, x[0-9]+, lsl 2\]
> > ** cmpgt p[0-9]+\.s, p[0-9]+/z, z[0-9]+\.s, z[0-9]+\.s
> > +** b\.any \.L[0-9]+
> > +** ...
> > +** whilelo p[0-9]+\.s, w[0-9]+, w[0-9]+
> > ** ...
> > ** ldr w[0-9]+, \[x[0-9]+, x[0-9]+, lsl 2\]
> > ** ldr w[0-9]+, \[x[0-9]+, x[0-9]+, lsl 2\]
> > diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
> > index
> 31de29c036be5da2a94173e98dccc40a092099be..309f06d2d386769f152c
> 97c70b41f43a43181a79 100644
> > --- a/gcc/tree-vect-loop.cc
> > +++ b/gcc/tree-vect-loop.cc
> > @@ -11113,6 +11113,80 @@ move_early_exit_stmts (loop_vec_info
> loop_vinfo)
> > SET_PHI_ARG_DEF_ON_EDGE (phi, e, last_seen_vuse);
> > }
> >
> > +/* Update the exit profile counts scaling them from scalar to vector
> > counts.
> > +
> > + The calculations are as follows.
> > +
> > + let P be the scalar probability that one iteration takes an early exit
> > edge.
> > + 1 - P is then the probabiliy that the exit is not taken.
> > +
> > + Since every vector iteration handles VF scalar iterations, the early
> > exit
> > + branch can be taken when any of the lanes are true.
> > +
> > + We invert this and first calculate the probablity that you reach the
> > latch,
> > + i.e. the probability that the vector code does not exit is the
> > probability
> > + Q that none of the lanes are true.
> > +
> > + Q = (1 - P) * (1 - P) * ... * (1 - P)
> > + = (1 - P) ^ VF
> > +
> > + and so the probability that at least one lane breaks is 1 - Q,
> > + or rather 1 - (i - P) ^ VF.
> > +
> > + For example, if the scalar break probability is 10% and VF is 4:
> > +
> > + P = 0.1
> > + 1 - P = 0.9
> > + (1 - P) ^ VF = 0.9 ^ 4 = 0.6561
> > + 1 - (1 - p) ^ VF = 1 - 0.6561 = 0.3439
> > +
> > + So a scalar early-exit edge that is taken 10% of the time becomes a
> > vector
> > + early-exit edge that is taken about 34.4% of the time, because each
> > vector
> > + iteration gives the break condition four chances to trigger. */
> > +
> > +static void
> > +vect_update_early_break_profiles (loop_vec_info loop_vinfo)
> > +{
> > + if (!LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
> > + return;
> > +
> > + class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
> > + unsigned int vf = vect_vf_for_cost (loop_vinfo);
> > +
> > + auto_vec<std::pair<edge, profile_probability>, 8> updates;
> > + for (edge e : get_loop_exit_edges (loop))
> > + {
> > + if (e == LOOP_VINFO_MAIN_EXIT (loop_vinfo)
> > + || !e->probability.initialized_p ())
> > + continue;
> > +
> > + /* For any early break exits, the probablity of exiting are based on
> > if
> > + any lane is true, and so are tied to VF since you have VF chances.
> > + As such scale the scalar profile by VF to the the probability for the
> > + vector edges using 1 - (1 - p) ^ VF. */
> > + profile_probability probability
> > + = profile_probability::always () - e->probability.invert ().pow (vf);
> > + updates.safe_push ({e, probability});
> > + }
> > +
> > + /* Save all old scalar probabilities before changing any edges. Then
> > apply
> > + all probability updates before changing successor counts, since
> > earlier
> > + count changes can affect the source counts used by later early exits.
> > */
> > + for (auto update : updates)
> > + {
> > + edge e = update.first;
> > + profile_probability probability = update.second;
> > + profile_count old_count = e->count ();
> > + set_edge_probability_and_rescale_others (e, probability);
> > + e->dest->count += e->count () - old_count;
> > + }
> > +
> > + for (auto update : updates)
> > + for (edge e : update.first->src->succs)
> > + if (single_pred_p (e->dest))
> > + e->dest->count = e->count ();
> > +}
> > +
> > /* Generate adjustment code for early break scalar IVs filling in the value
> > we created earlier on for LOOP_VINFO_EARLY_BRK_NITERS_VAR. */
> >
> > @@ -11121,9 +11195,13 @@
> vect_update_ivs_after_vectorizer_for_early_breaks (loop_vec_info loop_vinfo)
> > {
> > DUMP_VECT_SCOPE
> ("vect_update_ivs_after_vectorizer_for_early_breaks");
> >
> > - if (!LOOP_VINFO_EARLY_BREAKS (loop_vinfo)
> > - /* If no peeling was done then we have no IV to update. */
> > - || !LOOP_VINFO_EARLY_BRK_NITERS_VAR (loop_vinfo))
> > + if (!LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
> > + return;
> > +
> > + vect_update_early_break_profiles (loop_vinfo);
> > +
>
> My comment would be that we should do this in the caller,
> where we already apply some scaling to the main vector loop
> (the argument for the main exit would be similar, no?).
I've moved it to scale_profile_for_vect_loop. Will send v2 in a bit.
> It's also a bit odd to scale for the main exit separately?
No because the main exit is a counted exit, it's probabilities are not
influenced by the lanes of a comparison, since it's usually just checking
the counter value.
That said, uncounted loops likely need all exit calculated this way.
I'll need to double check. Today since get_likely_max_loop_iterations_int
would return -1 you'd just get just basic loop scaling.
PEELED loops are handled correctly with this patch (and I've tested by
looking at the peeled*.c testcases)
So I think for !uncounted loops this is correct, for uncounted loops it's
slightly better than before and likely needs
if ((!LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo)
&& e == LOOP_VINFO_MAIN_EXIT (loop_vinfo))
|| !e->probability.initialized_p ())
continue;
to be correct, and in scale_profile_for_vect_loop we should not scale
the main exit for uncounted loops.
Let me respin.
Thanks,
Tamar
>
> > + /* If no peeling was done then we have no IV to update. */
> > + if (!LOOP_VINFO_EARLY_BRK_NITERS_VAR (loop_vinfo))
> > return;
> >
> > tree phi_var = LOOP_VINFO_EARLY_BRK_NITERS_VAR (loop_vinfo);
> >
> >
> >
>
> --
> Richard Biener <[email protected]>
> SUSE Software Solutions Germany GmbH,
> Frankenstrasse 146, 90461 Nuernberg, Germany;
> GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG
> Nuernberg)
