On Mon, Nov 24, 2025 at 2:07 AM Richard Biener
<[email protected]> wrote:
>
> On Sat, Nov 22, 2025 at 11:59 PM Andrew Pinski
> <[email protected]> wrote:
> >
> > This is version based on
> > https://gcc.gnu.org/pipermail/gcc-patches/2025-November/701533.html
> > review. Though the only thing is we still need an extra check for the edge
> > probability
> > like it is done in single_likely_exit because probabilities are still not
> > being tracked
> > correctly it seems.
> >
> > I also added copy-headers-12.c which we fail by duplicating too much. But I
> > think that is ok,
> > as this pattern of being the "correct" part of the loop header leading to a
> > noreturn function does not happen that often and when it does the header
> > would have had a
> > statically figured out conditional which is already being checked.
> >
> > Bootstrapped and tested on x86_64-linux-gnu.
> >
> > PR tree-optimization/122734
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-loop-ch.cc (should_duplicate_loop_header_p): Add new
> > argument,
> > canbe_neverexecuted. When canbe_neverexecuted is true, return if a
> > loop
> > exit is "never executed" like we are doing an invariant conditional.
> > (ch_base::copy_headers): Update call to
> > should_duplicate_loop_header_p.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/20030711-1.c: Update.
> > * gcc.dg/tree-ssa/copy-headers-10.c: New test.
> > * gcc.dg/tree-ssa/copy-headers-11.c: New test.
> > * gcc.dg/tree-ssa/copy-headers-12.c: New test.
> >
> > Signed-off-by: Andrew Pinski <[email protected]>
> > ---
> > gcc/testsuite/gcc.dg/tree-ssa/20030711-1.c | 8 ++--
> > .../gcc.dg/tree-ssa/copy-headers-10.c | 25 +++++++++++
> > .../gcc.dg/tree-ssa/copy-headers-11.c | 25 +++++++++++
> > .../gcc.dg/tree-ssa/copy-headers-12.c | 32 ++++++++++++++
> > gcc/tree-ssa-loop-ch.cc | 42 +++++++++++++++++--
> > 5 files changed, 124 insertions(+), 8 deletions(-)
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/copy-headers-10.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/copy-headers-11.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/copy-headers-12.c
> >
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030711-1.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/20030711-1.c
> > index c3f75eff29e..29e1df7a707 100644
> > --- a/gcc/testsuite/gcc.dg/tree-ssa/20030711-1.c
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/20030711-1.c
> > @@ -44,12 +44,12 @@ record_component_aliases (type)
> > /* The call to blah can not be eliminated. */
> > /* { dg-final { scan-tree-dump-times "blah \\(\\)" 1 "dom2" } } */
> >
> > -/* There should be three IF conditionals. */
> > -/* { dg-final { scan-tree-dump-times "if " 3 "dom2"} } */
> > +/* There should be four IF conditionals. */
> > +/* { dg-final { scan-tree-dump-times "if " 4 "dom2"} } */
> >
> > /* There should be two loads of type.binfo. */
> > /* { dg-final { scan-tree-dump-times "type\\.binfo" 2 "dom2"} } */
> >
> > -/* There should be three loads of vec.length. */
> > -/* { dg-final { scan-tree-dump-times "vec.length" 3 "dom2"} } */
> > +/* There should be four loads of vec.length. */
> > +/* { dg-final { scan-tree-dump-times "vec.length" 4 "dom2"} } */
> >
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-10.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-10.c
> > new file mode 100644
> > index 00000000000..5641a9a1d3a
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-10.c
> > @@ -0,0 +1,25 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O3 -fdump-tree-ch-details -fdump-tree-ldist-details" } */
> > +
> > +/* PR tree-optimization/122734 */
> > +/* We want to duplicate the block after the one containing the condition
> > going to unreachable.
> > + Since later on we will be removing the condition going to unreachable
> > anyways. */
> > +/* So in the end ldist can generate a memset. */
> > +
> > +static inline int size(int *a)
> > +{
> > + int t = *a;
> > + if (t < 0) __builtin_unreachable();
> > + return t;
> > +}
> > +
> > +void f(int *l, short *d)
> > +{
> > + for(int i = 0; i < size(l); i++)
> > + d[i] = 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 1 "ch2" }
> > } */
> > +/* { dg-final { scan-tree-dump-times "Will duplicate bb" 2 "ch2" } } */
> > +/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */
> > +/* { dg-final { scan-tree-dump "generated memset zero" "ldist" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-11.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-11.c
> > new file mode 100644
> > index 00000000000..2223a72f023
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-11.c
> > @@ -0,0 +1,25 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O3 -fdump-tree-ch-details -fdump-tree-ldist-details" } */
> > +
> > +/* PR tree-optimization/122734 */
> > +/* We want to duplicate the block after the one containing the condition
> > going to unreachable.
> > + Since later on we will be removing the condition going to unreachable
> > anyways. */
> > +/* So in the end ldist can generate a memset. */
> > +
> > +static inline int size(int *a)
> > +{
> > + int t = *a;
> > + if (t < 0) __builtin_trap();
> > + return t;
> > +}
> > +
> > +void f(int *l, short *d)
> > +{
> > + for(int i = 0; i < size(l); i++)
> > + d[i] = 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 1 "ch2" }
> > } */
> > +/* { dg-final { scan-tree-dump-times "Will duplicate bb" 2 "ch2" } } */
> > +/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */
> > +/* { dg-final { scan-tree-dump "generated memset zero" "ldist" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-12.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-12.c
> > new file mode 100644
> > index 00000000000..99a8b419a2e
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers-12.c
> > @@ -0,0 +1,32 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O3 -fdump-tree-ch-details" } */
> > +
> > +/* PR tree-optimization/122734 */
> > +/* We want to duplicate the block after the one containing the
> > + condition since it is not the "true" header. */
> > +
> > +static inline int size(int *a)
> > +{
> > + int t = *a;
> > + if (t < 0) __builtin_unreachable();
> > + return t;
> > +}
> > +
> > +void f(int *l, short *d)
> > +{
> > + for(int i = 0; i < size(l); i++)
> > + {
> > + if (d[i] < 0)
> > + return;
> > + d[i]--;
> > + }
> > + __builtin_abort ();
> > +}
> > +
> > +/* Not only we duplicate the true header but also duplicate the condition
> > + `d[i] < 0` but we should not. This structure does not show up enough to
> > + make a difference but we record it just in case we improve the heurstics
> > + some more. */
> > +/* { dg-final { scan-tree-dump-times "Duplicating bb . is a win" 1 "ch2" {
> > xfail *-*-* } } } */
> > +/* { dg-final { scan-tree-dump-times "Will duplicate bb" 2 "ch2" { xfail
> > *-*-* } } } */
> > +/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */
> > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
> > index 91a61dd4e80..feecf91cf70 100644
> > --- a/gcc/tree-ssa-loop-ch.cc
> > +++ b/gcc/tree-ssa-loop-ch.cc
> > @@ -185,19 +185,23 @@ enum ch_decision
> > /* We want to copy. */
> > ch_win,
> > /* We want to copy and we will eliminate loop exit. */
> > - ch_win_invariant_exit
> > + ch_win_invariant_exit,
> > +
> > };
> >
> > /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
> > instructions should be duplicated, limit is decreased by the actual
> > - amount. */
> > + amount. In the case of *CANBE_NEVEREXECUTED, if there is a exit edge
> > + of the HEADER that is most likely never executed then consider that
> > + as invariant and continue. Set *CANBE_NEVEREXECUTED to false otherwise.
> > */
> >
> > static ch_decision
> > should_duplicate_loop_header_p (basic_block header, class loop *loop,
> > gimple_ranger *ranger,
> > int *limit,
> > hash_set <edge> *invariant_exits,
> > - hash_set <edge> *static_exits)
> > + hash_set <edge> *static_exits,
> > + bool *canbe_neverexecuted)
> > {
> > gimple_stmt_iterator bsi;
> >
> > @@ -460,6 +464,34 @@ should_duplicate_loop_header_p (basic_block header,
> > class loop *loop,
> > }
> > return ch_win_invariant_exit;
> > }
> > + if (!static_exit && *canbe_neverexecuted)
> > + {
> > + /* See if one of the edges are an exit edge that is probable
> > + never executed.
> > + If so treat it as invariant exit win. */
> > + edge e;
> > + edge_iterator ei;
> > + bool hasone = false;
> > + FOR_EACH_EDGE (e, ei, header->succs)
> > + if (loop_exit_edge_p (loop, e)
> > + && (probably_never_executed_edge_p (cfun, e)
> > + /* We want to rule out paths to noreturns but not
> > + low probabilities resulting from adjustments
> > + or combining.
> > + FIXME: once we have better quality tracking,
> > + make this more robust. */
> > + || e->probability <= profile_probability::very_unlikely ()))
>
> So in case there is more than one exit we'd want to check if the
> non-exit is an effective fallthru. We don't have the corresponding
> probably_always_executed_edge_p, so with the other one
> we'd like to compute 'allbutone' probably_never_executed_edge_p?
Yes correct. This check/comment comes directly from single_likely_exit
in cfgloopanal.cc.
Which was done in this way in r8-1766-gaf2bbc51d3879b .
>
> Alternatively simplify and only ever consider this code for EDGE_COUNT == 2.
At this point EDGE_COUNT==2 will always be true as bbs where the last
instruction was not a GIMPLE_COND was checked:
```
gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
if (!last)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" Not duplicating bb %i: it does not end by conditional.\n",
header->index);
return ch_impossible;
}
```
The code could be simplified to check just 0/1 but FOR_EACH_EDGE was
used above in the same code as I copied the style there.
>
> Please give Honza the chance to chime in.
Does that mean this is approved since Honza has not chimed in over 2 weeks?
Just want to double check for pushing it.
Thanks,
Andrew
>
> Thanks,
> Richard.
>
> > + {
> > + hasone = true;
> > + if (dump_file && (dump_flags & TDF_DETAILS))
> > + fprintf (dump_file,
> > + " `never executed` exit %i->%i\n",
> > + e->src->index, e->dest->index);
> > + }
> > + if (hasone)
> > + return ch_win_invariant_exit;
> > + }
> > + *canbe_neverexecuted = false;
> >
> > /* If the static exit fully optimize out, it is win to "duplicate"
> > it.
> > @@ -846,10 +878,12 @@ ch_base::copy_headers (function *fun)
> > auto_vec <ch_decision, 32> decision;
> > hash_set <edge> *invariant_exits = new hash_set <edge>;
> > hash_set <edge> *static_exits = new hash_set <edge>;
> > + bool canbe_neverexecuted = true;
> > while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
> > &remaining_limit,
> > invariant_exits,
> > - static_exits))
> > + static_exits,
> > + &canbe_neverexecuted))
> > != ch_impossible)
> > {
> > nheaders++;
> > --
> > 2.43.0
> >
