Re: [patch v3][vect]: fix loop exit profiles with early break [PR118407]
Richard Biener <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
On Fri, 7 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.
>
> For counted loops we need to exclude the main exit from the calculations
> as for those the main exit is counted and so does not have this per-lane
> probability. For uncounted loops, all exits are based on vector compare,
> i.e. none of the exits are counted and we have a different loop control.
> That means for uncounted loops all exits should be using the per-lane
> probability and we should skip the counted exit adjustments in
> scale_profile_for_vect_loop.
>
> 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.
> (scale_profile_for_vect_loop): Use it and pass loop_vinfo.
> (vect_transform_loop): Pass loop_vinfo to scale_profile_for_vect_loop.
>
> 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/noeffect2.c b/gcc/testsuite/gcc.target/aarch64/noeffect2.c
> index 08c531fb18c817b018776a88db4f62eb03b001cb..f0720862f9ced1a8308cbedc1ecfa32d128e011b 100644
> --- a/gcc/testsuite/gcc.target/aarch64/noeffect2.c
> +++ b/gcc/testsuite/gcc.target/aarch64/noeffect2.c
> @@ -15,10 +15,11 @@ int b[N] = {0};
> ** cmgt v[0-9]+\.4s, v[0-9]+\.4s, v[0-9]+\.4s
> ** umaxp v[0-9]+\.4s, v[0-9]+\.4s, v[0-9]+\.4s
> ** fmov x[0-9]+, d[0-9]+
> -** cbz x[0-9]+, \.L[0-9]+
> -** mov w0, 1
> +** cbn?z x[0-9]+, \.L[0-9]+
> +** ...
> +** mov w0, [01]
> ** ret
> -** mov w0, 0
> +** mov w0, [01]
> ** ret
> */
> __attribute__ ((noipa, noinline))
> diff --git a/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c b/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> index 5bb1badde3c4e07d06ba68b2c73ba591e031f611..04b7eb993e36fbae27ff3849957b2e7e25595c9c 100644
> --- a/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
> @@ -9,16 +9,21 @@ 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\.none \.L[0-9]+
> -** mov w0, 1
> -** ret
> +** b\.any \.L[0-9]+
> +** ...
> +** incw x[0-9]+
> +** whilelo p[0-9]+\.s, w[0-9]+, w[0-9]+
> +** b\.any \.L[0-9]+
> ** mov w0, 0
> ** ret
> +** ...
> +** mov w0, 1
> +** ret
> */
> __attribute__ ((noipa, noinline))
> int foo (void)
> 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..fbd410544122b2e2fde73764573d78da3293df0a 100644
> --- a/gcc/tree-vect-loop.cc
> +++ b/gcc/tree-vect-loop.cc
> @@ -10890,14 +10890,88 @@ vect_gen_loop_len_mask (loop_vec_info loop_vinfo, gimple_stmt_iterator *gsi,
> return len_mask;
> }
>
> +/* 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)
> + && !LOOP_VINFO_NITERS_UNCOUNTED_P (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});
> + }
> +
> + /* First update the edge counts. */
> + for (auto update : updates)
> + set_edge_probability_and_rescale_others (update.first, update.second);
So this still adusts only edge probabilities. We do expect the counts
on exit->dest to remain as they are, right?
> +
> + /* And then only update the in loop BBs, i.e. the fall through block for
> + the early exits. */
> + for (auto update : updates)
> + for (edge e : update.first->src->succs)
> + if (!loop_exit_edge_p (loop, e) && single_pred_p (e->dest))
> + e->dest->count = e->count ();
Does this then update the in-loop counts correctly, given the order
of exits and thus the order of 'updates' isn't necessarily
dominator order?
I also hope Honza will chime in to tell us whether this is the canonical
way to update a profile.
> +}
> +
> /* Scale profiling counters by estimation for LOOP which is vectorized
> by factor VF.
> If FLAT is true, the loop we started with had unrealistically flat
> profile. */
>
> static void
> -scale_profile_for_vect_loop (class loop *loop, edge exit_e, unsigned vf, bool flat)
> +scale_profile_for_vect_loop (loop_vec_info loop_vinfo,
> + class loop *loop, edge exit_e, unsigned vf,
> + bool flat)
> {
> + /* First scale any early exits. */
> + vect_update_early_break_profiles (loop_vinfo);
> +
> /* For flat profiles do not scale down proportionally by VF and only
> cap by known iteration count bounds. */
> if (flat)
> @@ -10927,14 +11001,19 @@ scale_profile_for_vect_loop (class loop *loop, edge exit_e, unsigned vf, bool fl
> vf /= 2;
> }
>
> - if (entry_count.nonzero_p ())
> - set_edge_probability_and_rescale_others
> + if (!LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo))
> + {
> + if (entry_count.nonzero_p ())
> + set_edge_probability_and_rescale_others
> (exit_e,
> entry_count.probability_in (loop->header->count / vf));
> - /* Avoid producing very large exit probability when we do not have
> - sensible profile. */
> - else if (exit_e->probability < profile_probability::always () / (vf * 2))
> - set_edge_probability_and_rescale_others (exit_e, exit_e->probability * vf);
> + /* Avoid producing very large exit probability when we do not have
> + sensible profile. */
> + else if (exit_e->probability < profile_probability::always () / (vf * 2))
> + set_edge_probability_and_rescale_others (exit_e,
> + exit_e->probability * vf);
> + }
> +
> loop->latch->count = single_pred_edge (loop->latch)->count ();
>
> scale_loop_profile (loop, profile_probability::always () / vf,
> @@ -11555,8 +11634,9 @@ vect_transform_loop (loop_vec_info loop_vinfo, gimple *loop_vectorized_call)
> assumed_vf) - 1
> : wi::udiv_floor (loop->nb_iterations_estimate + bias_for_assumed,
> assumed_vf) - 1);
> - scale_profile_for_vect_loop (loop, LOOP_VINFO_MAIN_EXIT (loop_vinfo),
> - assumed_vf, flat);
> + scale_profile_for_vect_loop (loop_vinfo, loop,
> + LOOP_VINFO_MAIN_EXIT (loop_vinfo), assumed_vf,
> + flat);
>
> if (dump_enabled_p ())
> {
>
>
>
--
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)