From: Kyrylo Tkachov <[email protected]>
This is an alternative to
https://gcc.gnu.org/pipermail/gcc-patches/2026-August/728756.html
following Honza's comments at:
https://gcc.gnu.org/pipermail/gcc-patches/2026-August/728898.html
branch_prob () cannot place a counter on an abnormal edge. A computed
goto uses fake edges to represent its possible targets. branch_prob ()
also marks the abnormal edges as ignored. An ignored edge outside the
spanning tree gets neither a counter nor an inferred count.
compute_branch_probabilities () converts the default zero count of such
an edge to a precise never. determine_unlikely_bbs () can then clear
measured counts from a region that is reachable only through these
edges. This can make the hot loop of a threaded interpreter appear
dead. A zero probability also gives later cost models no useful
dispatch target.
For a five-target dispatch, the edge dump changes from
[never] count:0 (precise)
to
[20.0% (guessed)] count:1000 (guessed)
and the measured dispatch count of 5000 survives.
Keep the initial zero probability as a guess while partial-profile
handling runs. After fake edges are removed, subtract the probabilities
of other successors from always and divide the remainder evenly among
ignored off-tree successors of blocks with a nonzero IPA count. Mark
the result as guessed. This gives computed-goto targets a normalized,
usable distribution. If other successors consume all probability, the
ignored edges remain guessed zero and the known distribution stays
unchanged.
Add tests for an all-unknown computed-goto dispatch and a returns-twice
source with both measured and ignored successors.
Evaluated on aarch64 (NVIDIA Vera) with CPython 3.14.5 at -O3. CPython
was configured with --enable-optimizations and --with-lto. In
_PyEval_EvalFrameDefault, the share of basic blocks with a precise zero
count falls from 98.5% to 22.6%. A fixed-work pyperformance-derived
workload takes 1.7% fewer cycles.
Bootstrapped and regression tested on aarch64-none-linux-gnu.
Ok for trunk?
thanks,
Kyrill
gcc/ChangeLog:
* profile.cc (guess_unmeasured_edge_probabilities): New function.
(compute_branch_probabilities): Mark ignored off-tree edge
probabilities as guessed.
(branch_prob): Divide the remaining probability evenly among ignored
off-tree successors.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-prof/comp-goto-2.c: New test.
* gcc.dg/tree-prof/setjmp-2.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/profile.cc | 44 ++++++++++++++
gcc/testsuite/gcc.dg/tree-prof/comp-goto-2.c | 62 ++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-prof/setjmp-2.c | 29 +++++++++
3 files changed, 135 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-prof/comp-goto-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-prof/setjmp-2.c
diff --git a/gcc/profile.cc b/gcc/profile.cc
index 5ae64d4043f..34e797b918b 100644
--- a/gcc/profile.cc
+++ b/gcc/profile.cc
@@ -447,6 +447,38 @@ cmp_stats (const void *ptr1, const void *ptr2)
return 0;
}
+/* Set probabilities of ignored off-tree successors of BB to an even share of
+ the probability not assigned to other successors. Fake edges must have
+ been removed. */
+
+static void
+guess_unmeasured_edge_probabilities (basic_block bb)
+{
+ profile_probability remainder = profile_probability::always ();
+ edge e;
+ edge_iterator ei;
+ unsigned unmeasured = 0;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ gcc_checking_assert (!(e->flags & EDGE_FAKE));
+ if (EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
+ unmeasured++;
+ else
+ {
+ gcc_checking_assert (e->probability.initialized_p ());
+ remainder -= e->probability;
+ }
+ }
+
+ if (!unmeasured)
+ return;
+
+ profile_probability probability = (remainder / unmeasured).guessed ();
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
+ e->probability = probability;
+}
/* Compute the branch probabilities for the various branches.
Annotate them accordingly.
@@ -719,6 +751,12 @@ compute_branch_probabilities (unsigned cfg_checksum,
unsigned lineno_checksum)
bool prev_never = e->probability == profile_probability::never ();
e->probability = profile_probability::probability_in_gcov_type
(edge_gcov_count (e), bb_gcov_count (bb));
+ /* Mark an unmeasured zero as guessed so it does not prove
+ deadness or change other probabilities during partial-profile
+ handling. A guess based on the remaining probability is
+ assigned after fake edges are removed. */
+ if (EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
+ e->probability = e->probability.guessed ();
if (e->probability == profile_probability::never ()
&& !prev_never
&& flag_profile_partial_training)
@@ -1762,6 +1800,12 @@ branch_prob (bool thunk)
remove_fake_edges ();
+ if (flag_branch_probabilities
+ && profile_status_for_fn (cfun) == PROFILE_READ)
+ FOR_EACH_BB_FN (bb, cfun)
+ if (bb->count.ipa ().nonzero_p ())
+ guess_unmeasured_edge_probabilities (bb);
+
if (condition_coverage_flag || path_coverage_flag || profile_arc_flag)
gimple_init_gcov_profiler ();
diff --git a/gcc/testsuite/gcc.dg/tree-prof/comp-goto-2.c
b/gcc/testsuite/gcc.dg/tree-prof/comp-goto-2.c
new file mode 100644
index 00000000000..f3079c938a7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-prof/comp-goto-2.c
@@ -0,0 +1,62 @@
+/* The ignored edges out of a computed goto are outside the spanning tree and
+ have no individual counts. Check that -fprofile-use keeps the measured
+ block counts and assigns a usable guessed distribution to these edges. */
+/* { dg-options "-O2 -fdump-tree-optimized-blocks-details" } */
+/* { dg-require-effective-target indirect_jumps } */
+/* { dg-require-effective-target label_values } */
+
+enum { OP_ADD, OP_SUB, OP_MUL, OP_STORE, OP_HALT, NOPS };
+
+unsigned char code[8];
+long mem[4] = { 1, 2, 3, 4 };
+
+__attribute__((noinline)) long
+interp (const unsigned char *pc)
+{
+ static const void *const tab[NOPS]
+ = { &&L_ADD, &&L_SUB, &&L_MUL, &&L_STORE, &&L_HALT };
+ long acc = 0;
+
+#define DISPATCH() goto *tab[*pc++]
+
+ DISPATCH ();
+L_ADD:
+ acc += mem[*pc++];
+ DISPATCH ();
+L_SUB:
+ acc -= mem[*pc++];
+ DISPATCH ();
+L_MUL:
+ acc *= 3;
+ DISPATCH ();
+L_STORE:
+ mem[*pc++] = acc;
+ DISPATCH ();
+L_HALT:
+ return acc;
+}
+
+int
+main (void)
+{
+ long r = 0;
+ int i;
+
+ code[0] = OP_ADD; code[1] = 1;
+ code[2] = OP_SUB; code[3] = 2;
+ code[4] = OP_MUL;
+ code[5] = OP_STORE; code[6] = 3;
+ code[7] = OP_HALT;
+
+ for (i = 0; i < 1000; i++)
+ r += interp (code);
+
+ return r == 0;
+}
+
+/* No block of the dispatch loop may be left with a precise zero count. */
+/* { dg-final-use-not-autofdo { scan-tree-dump-not "count 0 \\(precise"
"optimized" } } */
+/* Each of the five ignored edges receives 20%. The detailed dump prints each
+ edge in both a successor and predecessor list. */
+/* { dg-final-use-not-autofdo { scan-tree-dump-times "20.0% \\(guessed\\)]
count:1000 \\(guessed" 10 "optimized" } } */
+/* { dg-final-use-not-autofdo { scan-tree-dump-not "Invalid sum of outgoing
probabilities" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-prof/setjmp-2.c
b/gcc/testsuite/gcc.dg/tree-prof/setjmp-2.c
new file mode 100644
index 00000000000..0adee16506b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-prof/setjmp-2.c
@@ -0,0 +1,29 @@
+/* A returns-twice call has a measured fallthrough edge and an ignored
+ abnormal edge. Check that guessing the abnormal edge does not change the
+ measured probability when no probability remains to distribute. */
+/* { dg-options "-O2 -fdump-tree-feedback_fnsplit2-blocks-details" } */
+/* { dg-require-effective-target nonlocal_goto } */
+
+static void *buf[20];
+
+__attribute__((noinline)) static int
+f (void)
+{
+ return __builtin_setjmp (buf) + 1;
+}
+
+int
+main (void)
+{
+ int sum = 0;
+
+ for (int i = 0; i < 1000; ++i)
+ sum += f ();
+
+ return sum != 1000;
+}
+
+/* { dg-final-use-not-autofdo { scan-tree-dump "always]\[^\\n\\r\]*count:1000
\\(precise,\[^\\n\\r\]*\\(FALLTHRU,EXECUTABLE\\)" "feedback_fnsplit2" } } */
+/* { dg-final-use-not-autofdo { scan-tree-dump "never
\\(guessed\\)]\[^\\n\\r\]*\\(ABNORMAL,EXECUTABLE\\)" "feedback_fnsplit2" } } */
+/* { dg-final-use-not-autofdo { scan-tree-dump-not "Invalid sum of outgoing
probabilities" "feedback_fnsplit2" } } */
+/* { dg-final-use-not-autofdo { scan-tree-dump-not "Invalid sum of incoming
counts" "feedback_fnsplit2" } } */
--
2.50.1 (Apple Git-155)
