[patch][vect]: fix loop exit profiles with early break [PR118407]
Tamar Christina <[email protected]> Wed, 5 Aug 2026 12:06:15 +0100
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
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..7169ede3cda7108ce6628c147d014dd03c5d57bf 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..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..309f06d2d386769f152c97c70b41f43a43181a79 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);
+
+ /* 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);
--
rb20755.patch
(text/x-diff, 5.3 KB)
diff --git a/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c b/gcc/testsuite/gcc.target/aarch64/sve/noeffect2.c
index 5bb1badde3c4e07d06ba68b2c73ba591e031f611..7169ede3cda7108ce6628c147d014dd03c5d57bf 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..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..309f06d2d386769f152c97c70b41f43a43181a79 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);
+
+ /* 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);