Re: [patch][vect]: fix loop exit profiles with early break [PR118407]
Richard Biener <[email protected]> Wed, 5 Aug 2026 14:56:45 +0200 (CEST)
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
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..7169ede3cda7108ce6628c147d014dd03c5d57bf 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..8c20f39d2a467e636cfec71acacb2da654a49d67 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..309f06d2d386769f152c97c70b41f43a43181a79 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?).
It's also a bit odd to scale for the main exit separately?
> + /* 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)