https://gcc.gnu.org/g:cf99490e7ebcf72e3478454448dc265a32723240
commit r17-4704-gcf99490e7ebcf72e3478454448dc265a32723240 Author: Tamar Christina <[email protected]> Date: Sun Sep 27 23:00:01 2026 +0100 vect: fix loop exit profiles with early break [PR118407] 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 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. gcc/ChangeLog: PR tree-optimization/118407 * tree-vect-loop.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/noeffect2.c: Update tests. * gcc.target/aarch64/sve/noeffect2.c: Update test. * gcc.target/aarch64/sve/noeffect3.c: Likewise. Diff: --- gcc/testsuite/gcc.target/aarch64/noeffect2.c | 7 +- gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c | 13 +++- gcc/testsuite/gcc.target/aarch64/sve/noeffect3.c | 5 +- gcc/tree-vect-loop.cc | 98 +++++++++++++++++++++--- 4 files changed, 106 insertions(+), 17 deletions(-) diff --git a/gcc/testsuite/gcc.target/aarch64/noeffect2.c b/gcc/testsuite/gcc.target/aarch64/noeffect2.c index 08c531fb18c8..f0720862f9ce 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 5bb1badde3c4..04b7eb993e36 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 c5f81bb0d303..8c20f39d2a46 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 f692ead2bacc..9b2afad6034a 100644 --- a/gcc/tree-vect-loop.cc +++ b/gcc/tree-vect-loop.cc @@ -10879,14 +10879,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); + + /* 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 (); +} + /* 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) @@ -10916,14 +10990,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, @@ -11545,8 +11624,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 ()) {
