On Fri, Aug 28, 2026 at 03:45:14PM +0200, Richard Biener wrote: > On Fri, Aug 28, 2026 at 8:35 AM Aldy Hernandez <[email protected]> wrote: > > > > On Wed, Aug 26, 2026 at 04:13:46PM +0200, Richard Biener wrote: > > > > > So I think we should maybe adjust copy_bbs then, for example > > > either by providing a hook to post-process new_bbs[] after > > > copying but before redirecting edges, or by more tailored, specify > > > a BB as exit implicitly by the exit edge that should prevail. I'll > > > note that copy_bbs > > > is a bit generic here, we have a SEME region. > > > > > > That said, adding a "prevailing_exit" argument, and if set, > > > have edges outgoing from prevailing_exit->src copy that are > > > not going to prevailing_exit->dest removed rather than redirected > > > would be sound? > > > > OMG, you just _had_ to make it more complicated :). I knew there was > > a reason I'd never touched that code in all these years. > > > > How about the attached? > > Hmm. So I was somehow expecting that changing > > FOR_EACH_EDGE (e, ei, new_bb->succs) > { > if (!(e->dest->flags & BB_DUPLICATED)) > continue; > redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); > } > > to > > FOR_EACH_EDGE (e, ei, new_bb->succs) > { > if (prevailing_exit && bb == prevailing_exit->src && > prevailing_exit->dest != e->dest) > { > remove_edge (e); > continue; > } > if (!(e->dest->flags & BB_DUPLICATED)) > continue; > redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); > } > > would have been enough? That is, prevailing_exit->dest should of course > not be in the set of duplicated blocks. Meaning I don't understand > > + /* ...but be careful with kept edges into the copied region, > + because their destinations are the originals (marked > + BB_DUPLICATED) so edge creation skipped growing their PHI > + arguments. Any other such edge eventually has its PHI > + bookkeeping done by whatever redirects or removes it. > Since > + a kept edge is neither redirected nor removed, nothing > + will ever grow its destination's arguments. Keep track of > + it to grow them at the end of this function. */ > + if (e->dest->flags & BB_DUPLICATED) > + kept.safe_push (e); > > this would mean you call this with an exit that isn't an exit which makes > it an awkward interface (and then sorry for misleading if this is what you > actuall need).
My bad, I think I was overthinking this. The PHI bookkeeping was for a case where the prevailing edge jumps back into the copied region. Trunk doesn't handle this currently, so there's no regression in not bending over backwards to handle this. However, ordinary paths commonly thread back into themselves, and those must keep working — refusing an exit that reenters the path regresses various tests. See current patch. Ughh, clearly I don't know what I'm doing here. How about this version? Aldy
>From 4f52e3237bb5272cc237eceb02ab420b9ac5d7c1 Mon Sep 17 00:00:00 2001 From: Aldy Hernandez <[email protected]> Date: Wed, 26 Aug 2026 14:56:08 +0000 Subject: [PATCH] Add a prevailing exit edge to copy_bbs [PR126906] Teach the generic copier that one edge out of the region prevails, so the backwards threader can handle abnormal edges out of a path. Tested on ppc64le Linux. PR tree-optimization/126906 gcc/ChangeLog: * cfghooks.h (can_copy_bbs_p): Add prevailing_exit argument. (copy_bbs): Likewise. * cfghooks.cc (can_copy_bbs_p): Exempt prevailing_exit->src from the abnormal successor edge refusal; refuse a prevailing_exit->dest inside the region. (copy_bbs): Prune the non-prevailing edges of prevailing_exit->src's copy instead of redirecting them. Assert the prevailing exit leaves the region. * tree-ssa-threadupdate.cc (back_jt_path_registry::duplicate_thread_path): Pass EXIT to can_copy_bbs_p and copy_bbs when the path ends in abnormal edges. Assert the region ends in EXIT's source. Remove write-only exit_copy. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-thread-25.c: New test. * gcc.dg/tree-ssa/ssa-thread-26.c: New test. --- gcc/cfghooks.cc | 69 ++++++++++++++----- gcc/cfghooks.h | 4 +- gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c | 31 +++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-26.c | 26 +++++++ gcc/tree-ssa-threadupdate.cc | 25 +++++-- 5 files changed, 133 insertions(+), 22 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-26.c diff --git a/gcc/cfghooks.cc b/gcc/cfghooks.cc index 9e20c824752..85311a28284 100644 --- a/gcc/cfghooks.cc +++ b/gcc/cfghooks.cc @@ -1377,9 +1377,13 @@ lv_add_condition_to_bb (basic_block first, basic_block second, cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond); } -/* Checks whether all N blocks in BBS array can be copied. */ +/* Checks whether all N blocks in BBS array can be copied. + + PREVAILING_EXIT is as in copy_bbs. If non-NULL, the copy of its source + keeps only the prevailing edge, so the abnormal successor edges of that + block do not require redirection. */ bool -can_copy_bbs_p (basic_block *bbs, unsigned n) +can_copy_bbs_p (basic_block *bbs, unsigned n, edge prevailing_exit) { unsigned i; edge e; @@ -1388,17 +1392,28 @@ can_copy_bbs_p (basic_block *bbs, unsigned n) for (i = 0; i < n; i++) bbs[i]->flags |= BB_DUPLICATED; + /* A prevailing edge jumping back into the region is not supported: + its copy would have to keep targeting the original block. */ + if (prevailing_exit && (prevailing_exit->dest->flags & BB_DUPLICATED)) + { + ret = false; + goto end; + } + for (i = 0; i < n; i++) { - /* In case we should redirect abnormal edge during duplication, fail. */ + /* In case we should redirect abnormal edge during duplication, fail. + However, the copy of PREVAILING_EXIT->src is exempt as its outgoing + edges are removed or left in place rather than redirected. */ edge_iterator ei; - FOR_EACH_EDGE (e, ei, bbs[i]->succs) - if ((e->flags & EDGE_ABNORMAL) - && (e->dest->flags & BB_DUPLICATED)) - { - ret = false; - goto end; - } + if (!(prevailing_exit && bbs[i] == prevailing_exit->src)) + FOR_EACH_EDGE (e, ei, bbs[i]->succs) + if ((e->flags & EDGE_ABNORMAL) + && (e->dest->flags & BB_DUPLICATED)) + { + ret = false; + goto end; + } if (!can_duplicate_block_p (bbs[i])) { @@ -1435,12 +1450,21 @@ end: also in the same order. Newly created basic blocks are put after the basic block AFTER in the - instruction stream, and the order of the blocks in BBS array is preserved. */ + instruction stream, and the order of the blocks in BBS array is preserved. + + If PREVAILING_EXIT is non-NULL, its source must be in BBS, and its + destination must not be: the copy of that block keeps only its edges to + PREVAILING_EXIT->dest, and the rest of its outgoing edges are removed. None + of its edges are redirected, which allows copying a region whose exit block + has abnormal successor edges into the region. It is the caller's + responsibility to remove or rewrite the copied block's control + statement. */ void copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, edge *edges, unsigned num_edges, edge *new_edges, - class loop *base, basic_block after, bool update_dominance) + class loop *base, basic_block after, bool update_dominance, + edge prevailing_exit) { unsigned i, j; basic_block bb, new_bb, dom_bb; @@ -1453,6 +1477,11 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, for (i = 0; i < n; i++) bbs[i]->flags |= BB_DUPLICATED; + /* A prevailing edge into the region would be redirected like any + other. We refuse this in can_copy_bbs_p. */ + gcc_checking_assert (!prevailing_exit + || !(prevailing_exit->dest->flags & BB_DUPLICATED)); + /* Duplicate bbs, update dominators, assign bbs to loops. */ for (i = 0; i < n; i++) { @@ -1495,11 +1524,19 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, new_bb = new_bbs[i]; bb = bbs[i]; - FOR_EACH_EDGE (e, ei, new_bb->succs) + for (ei = ei_start (new_bb->succs); (e = ei_safe_edge (ei)); ) { - if (!(e->dest->flags & BB_DUPLICATED)) - continue; - redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); + /* Remove the edges that do not prevail instead of + redirecting them. */ + if (prevailing_exit && bb == prevailing_exit->src + && e->dest != prevailing_exit->dest) + { + remove_edge (e); + continue; + } + if (e->dest->flags & BB_DUPLICATED) + redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); + ei_next (&ei); } } for (j = 0; j < num_edges; j++) diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h index 8d7cb2dd4bc..b342b2d4f23 100644 --- a/gcc/cfghooks.h +++ b/gcc/cfghooks.h @@ -275,10 +275,10 @@ extern void lv_adjust_loop_header_phi (basic_block, basic_block, basic_block, extern void lv_add_condition_to_bb (basic_block, basic_block, basic_block, void *); -extern bool can_copy_bbs_p (basic_block *, unsigned); +extern bool can_copy_bbs_p (basic_block *, unsigned, edge = NULL); extern void copy_bbs (basic_block *, unsigned, basic_block *, edge *, unsigned, edge *, class loop *, - basic_block, bool); + basic_block, bool, edge = NULL); void profile_record_check_consistency (profile_record *); void profile_record_account_profile (profile_record *); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c new file mode 100644 index 00000000000..7dce45771a4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c @@ -0,0 +1,31 @@ +/* PR tree-optimization/126906 */ +/* { dg-do compile } */ +/* { dg-options "-O2 --param=dom-jump-threading=0 -fdump-tree-ethread-details" } */ +/* { dg-require-effective-target label_values } */ + +/* The computed goto lives in the same block as the address-taken + label lab2, so the goto's untaken abnormal edge to lab2 points + back into the block itself. Threading the resolved paths must + copy that block. */ + +void *sink; + +void +foo (int b) +{ + void *x; + sink = &&lab2; + if (b) + x = &&lab; + else + x = &&done; +lab2: + goto *x; +lab: + sink = 0; +done: + return; +} + +/* { dg-final { scan-tree-dump-times "Registering jump thread" 2 "ethread" } } */ +/* { dg-final { scan-tree-dump-not "Cancelling" "ethread" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-26.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-26.c new file mode 100644 index 00000000000..998198147c6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-26.c @@ -0,0 +1,26 @@ +/* PR tree-optimization/126906 */ +/* { dg-do compile } */ +/* { dg-options "-O2 --param=dom-jump-threading=0 -fdump-tree-threadfull1-details" } */ +/* { dg-require-effective-target label_values } */ + +/* The path to the computed goto resolves it to lab. It is the + address-taken label lab2 that is targeted by the goto's own untaken + abnormal edge back into the region being copied. */ + +void +foo (int b, int c) +{ + void *x = &&lab; + if (b) + { +lab: + return; + } +lab2: + if (c) + x = &&lab2; + goto *x; +} + +/* { dg-final { scan-tree-dump-times "Registering jump thread" 1 "threadfull1" } } */ +/* { dg-final { scan-tree-dump-not "Cancelling" "threadfull1" } } */ diff --git a/gcc/tree-ssa-threadupdate.cc b/gcc/tree-ssa-threadupdate.cc index 54d2c419423..da572c3c183 100644 --- a/gcc/tree-ssa-threadupdate.cc +++ b/gcc/tree-ssa-threadupdate.cc @@ -2395,11 +2395,28 @@ back_jt_path_registry::duplicate_thread_path (edge entry, { unsigned i; class loop *loop = entry->dest->loop_father; - edge exit_copy; edge redirected; profile_count curr_count; - if (!can_copy_bbs_p (region, n_region)) + gcc_checking_assert (n_region && region[n_region - 1] == exit->src); + + /* Let EXIT prevail only when its source ends in abnormal edges, which cannot + be redirected. Ordinary paths commonly thread back into themselves, which + the prevailing exit does not support as its copy would have to jump back + into the original region. An abnormal exit reentering the region is + refused by can_copy_bbs_p either way. */ + edge prevailing_exit = NULL; + for (edge e : exit->src->succs) + if (e->flags & EDGE_ABNORMAL) + { + prevailing_exit = exit; + break; + } + /* Abnormal successors imply a computed goto, whose successors are + all abnormal, EXIT included. */ + gcc_checking_assert (!prevailing_exit || (exit->flags & EDGE_ABNORMAL)); + + if (!can_copy_bbs_p (region, n_region, prevailing_exit)) { *failure_reason = "Cannot copy the blocks in the path"; return false; @@ -2432,8 +2449,8 @@ back_jt_path_registry::duplicate_thread_path (edge entry, set_loop_copy (loop, loop); basic_block *region_copy = XNEWVEC (basic_block, n_region); - copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, - split_edge_bb_loc (entry), false); + copy_bbs (region, n_region, region_copy, NULL, 0, NULL, loop, + split_edge_bb_loc (entry), false, prevailing_exit); /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The following code ensures that all the edges exiting the jump-thread path are -- 2.47.3
