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? Aldy
>From 5ba91905820896cb80daa368e1b3e8685adc8843 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. Note that copy_bbs skips reserving PHI argument slots for new edges into the region, because those edges normally get redirected right after, and the slots appear then. Since the kept edge never gets touched, nobody ever gives it its slots. If its destination has a PHI we ICE later (see ssa-thread-29.c test). Thus, reserve them at the end of copy_bbs. Let me know if there's a cleaner way of doing this. 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. (copy_bbs): Prune the non-prevailing edges of prevailing_exit->src's copy instead of redirecting them; reserve PHI argument slots for kept in-region prevailing edges after unmarking. * tree-ssa-threadupdate.cc (bb_in_bbs): Remove. (back_jt_path_registry::duplicate_thread_path): Pass EXIT to can_copy_bbs_p and copy_bbs; remove the now-dead last-block redirect fixup. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-thread-25.c: New test. * gcc.dg/tree-ssa/ssa-thread-28.c: New test. * gcc.dg/tree-ssa/ssa-thread-29.c: New test. --- gcc/cfghooks.cc | 69 +++++++++++++++---- gcc/cfghooks.h | 4 +- gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c | 30 ++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-28.c | 26 +++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-29.c | 30 ++++++++ gcc/tree-ssa-threadupdate.cc | 34 ++------- 6 files changed, 151 insertions(+), 42 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-28.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-29.c diff --git a/gcc/cfghooks.cc b/gcc/cfghooks.cc index 9e20c824752..1d2ecc2fe1d 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; @@ -1390,15 +1394,18 @@ can_copy_bbs_p (basic_block *bbs, unsigned n) 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 +1442,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 one of BBS and the copy + of that block keeps only its edges to PREVAILING_EXIT->dest, left on the + original destination. The rest of PREVAILING_EXIT->src's 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; @@ -1489,12 +1505,37 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, } /* Redirect edges. */ + auto_vec<edge, 2> kept; for (i = 0; i < n; i++) { edge_iterator ei; new_bb = new_bbs[i]; bb = bbs[i]; + if (prevailing_exit && bb == prevailing_exit->src) + { + /* Remove the edges that do not prevail instead of redirecting + them... */ + for (ei = ei_start (new_bb->succs); (e = ei_safe_edge (ei)); ) + if (e->dest != prevailing_exit->dest) + remove_edge (e); + else + { + /* ...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); + ei_next (&ei); + } + continue; + } + FOR_EACH_EDGE (e, ei, new_bb->succs) { if (!(e->dest->flags & BB_DUPLICATED)) @@ -1521,6 +1562,10 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, /* Clear information about duplicates. */ for (i = 0; i < n; i++) bbs[i]->flags &= ~BB_DUPLICATED; + + /* Grow the PHI arguments the kept prevailing edges may be missing. */ + for (edge ke : kept) + execute_on_growing_pred (ke); } /* Return true if BB contains only labels or non-executable 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..bcb5a058069 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-25.c @@ -0,0 +1,30 @@ +/* PR tree-optimization/126906 */ +/* { dg-do compile } */ +/* { dg-options "-O2 --param=dom-jump-threading=0 -fdump-tree-ethread-details" } */ + +/* The computed goto lives in the same block as the address-taken + label lab2, so the goto's 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-28.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-28.c new file mode 100644 index 00000000000..bdca0de214c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-28.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 lab2, whose address-taken label + is targeted by the goto's own 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/testsuite/gcc.dg/tree-ssa/ssa-thread-29.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-29.c new file mode 100644 index 00000000000..2b1270a7081 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-29.c @@ -0,0 +1,30 @@ +/* PR tree-optimization/126906 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */ +/* { dg-require-effective-target label_values } */ + +/* The resolved thread keeps an exit edge back into the copied region, and its + destination (L2) carries a PHI for i. Make sure the PHI gets enough + slots. */ + +int g; + +void +h (int a) +{ + void *q; + int i = 0; + if (a) + q = &&L0; + else + q = &&L2; +L2: + i++; + g = i; + goto *q; +L0: + return; +} + +/* { dg-final { scan-tree-dump-times "Registering jump thread" 2 "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..5e36c3d79cf 100644 --- a/gcc/tree-ssa-threadupdate.cc +++ b/gcc/tree-ssa-threadupdate.cc @@ -2203,18 +2203,6 @@ verify_jump_thread (basic_block *region, unsigned n_region) gcc_assert (EDGE_COUNT (region[i]->preds) <= 1); } -/* Return true when BB is one of the first N items in BBS. */ - -static inline bool -bb_in_bbs (basic_block bb, basic_block *bbs, int n) -{ - for (int i = 0; i < n; i++) - if (bb == bbs[i]) - return true; - - return false; -} - void jt_path_registry::debug_path (FILE *dump_file, int pathno) { @@ -2395,11 +2383,10 @@ 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)) + if (!can_copy_bbs_p (region, n_region, exit)) { *failure_reason = "Cannot copy the blocks in the path"; return false; @@ -2432,8 +2419,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, 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 @@ -2482,19 +2469,10 @@ back_jt_path_registry::duplicate_thread_path (edge entry, continue; } - /* Special case the last block on the path: make sure that it does not - jump back on the copied path, including back to itself. */ + /* Nothing to redirect, as the last block on the path kept only the + prevailing exit edges. */ if (i + 1 == n_region) - { - FOR_EACH_EDGE (e, ei, bb->succs) - if (bb_in_bbs (e->dest, region_copy, n_region)) - { - basic_block orig = get_bb_original (e->dest); - if (orig) - redirect_edge_and_branch_force (e, orig); - } - continue; - } + continue; /* Redirect all other edges jumping to non-adjacent blocks back to the original code. */ -- 2.47.3
