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 Mon, 10 Aug 2026, Tamar Christina wrote: > > -----Original Message----- > > From: Richard Biener <[email protected]> > > Sent: 10 August 2026 10:51 > > To: Tamar Christina <[email protected]> > > Cc: [email protected]; nd <[email protected]>; [email protected] > > Subject: Re: [patch v3][vect]: fix loop exit profiles with early break [PR118407] > > > > 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..f0720862f9ced1a8308cb > > edc1ecfa32d128e011b 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..04b7eb993e36fbae27ff3 > > 849957b2e7e25595c9c 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..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..fbd410544122b2e2fde73 > > 764573d78da3293df0a 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? > > > > Yes, since updating that would make it inconsistent with that block's children. > So it seemed more logical that counts for the blocks after vect don't change. > > This is especially true when we no longer need the scalar loop to perform > side effects. > > > > + > > > + /* 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 don't think the order matters since unlike edge counts which are > computed, BB counts aren't. So by now the edge counts are all > correct and so the order we set the BB counts in don't matter. Yes, but for /\ \ A /\ \ B when you update the count of B, A->B e->count depends on the count of A, so you have to update A first? That said, the loop->header count will have to be updated as well, from the last exit count? > > > > I also hope Honza will chime in to tell us whether this is the canonical > > way to update a profile. > > Hopefully. I also realized I accidentally dropped him from CC of the new > Version so added now. > > Thanks, > Tamar > > > > > +} > > > + > > > /* 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) > -- 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)