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

> -----Original Message-----
> From: Richard Biener <[email protected]>
> Sent: 06 August 2026 11:55
> To: Tamar Christina <[email protected]>
> Cc: [email protected]; nd <[email protected]>; [email protected];
> [email protected]
> Subject: Re: [patch v2][vect]: fix loop exit profiles with early break [PR118407]
> 
> On Thu, 6 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/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..c2b04149bf05a1a7def6f
> a41331dc53674d38e51 100644
> > --- a/gcc/tree-vect-loop.cc
> > +++ b/gcc/tree-vect-loop.cc
> > @@ -10890,14 +10890,94 @@ 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});
> > +    }
> > +
> > +  /* 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.  */
> 
> Note that get_loop_exit_edges () returns exits unsorted, so with multiple
> exits it isn't guaranteed that you visit earlier exits first.
> 

Yeah comment was only trying to say that we need to save e->count ()
since we need to be able to calculate the difference and rescale would
of course change it.  Probably a useless comment.

> > +  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;
> 
> Doesn't this result in profile mismatches outside of the loop?  I'd
> have expected exit->dest->count to be unchanged, since the number
> of times we exit a loop should be unchanged.  So don't you have to
> adjust the in-loop counts instead keeping that in mind?
> 

Hmm yeah. I think the only thing we need to handle here is the continuation
edge block.  I didn't notice anything off with the counts for the testcase I
looked at, but it looks like this code was a no-op for it.

set_edge_probability_and_rescale_others adjust the probabilities of the
continuation edge, but the in loop continuation blocks still need adjusting.

The example testcase didn't trigger this because with only one early exit
the continuation block is the main exit one and is adjusted by other code.

So I'll need a two early exit testcase.

Thanks for spotting this.  I can simplify this code a lot more.

Thanks,
Tamar


> > +    }
> > +
> > +  for (auto update : updates)
> > +    for (edge e : update.first->src->succs)
> > +      if (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)
> > @@ -10927,14 +11007,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 +11640,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)