RE: [patch][vect]: fix loop exit profiles with early break [PR118407]

> -----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)