https://gcc.gnu.org/g:3a4787033e4b5dea2d1f7a6b30d4c85a00b7b91d
commit r17-4886-g3a4787033e4b5dea2d1f7a6b30d4c85a00b7b91d Author: Richard Biener <[email protected]> Date: Mon Oct 5 08:50:07 2026 +0200 tree-optimization/127693 - missed FRE in loop #2 This is another aspect of the PR127693 showed missed FRE in loops when there was a ref translation. When get_continuation_for_phi is entered with abort_on_visited true because we're in the process of walking a backedge with a translated ref it is important to not call maybe_skip_until for the same virtual operand multiple times as that will surely trip abort_on_visited. But that safety is for detecting whether we already visited the place prior to get_continuation_for_phi. The fix is to avoid doing duplicate work (which is good in any case). Use a sorted vector of PHI arguments for this. PR tree-optimization/127693 * tree-ssa-alias.cc (cmp_intpair): New qsort helper. (get_continuation_for_phi): Sort the PHI args and avoid processing duplicates. * gcc.dg/tree-ssa/ssa-fre-117.c: New testcase. Diff: --- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-117.c | 50 +++++++++++++++++++++++++++++ gcc/tree-ssa-alias.cc | 36 ++++++++++++++++++--- 2 files changed, 82 insertions(+), 4 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-117.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-117.c new file mode 100644 index 000000000000..62bc1bddf28c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-117.c @@ -0,0 +1,50 @@ +/* PR127693 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-fre3" } */ + +typedef struct { long size; const short *data; } SV; +typedef struct { SV given; } Scanner; +long findString(SV h, long from, SV n); +const short *strchr16(const short *b, const short *e, short c); + +static inline long findChar(SV h, long from, short c) +{ + if ((unsigned long)from < (unsigned long)h.size) { + const short *n = strchr16(h.data + from, h.data + h.size, c); + if (n != h.data + h.size) + return n - h.data; + } + return -1; +} + +static inline long indexOf(const SV *h, SV n, long from) +{ + if (__builtin_constant_p(n.size) && n.size == 1) + return findChar(*h, from, n.data[0]); + return findString(*h, from, n); +} + +static int scanForToken(Scanner *s, SV sought) +{ + long n = sought.size; + long idx = -n; + int count = 0; + while ((idx = indexOf(&s->given, sought, idx + n)) >= 0) + ++count; + return count; +} + +__attribute__((noinline)) int scanForSigns(Scanner *s) +{ + static const short minus[] = { 0x2212 }; + SV m = { 1, minus }; + return scanForToken(s, m); +} + +int f(SV h) +{ + Scanner s = { h }; + return scanForSigns(&s); +} + +/* { dg-final { scan-tree-dump-not "unreachable" "fre3" } } */ diff --git a/gcc/tree-ssa-alias.cc b/gcc/tree-ssa-alias.cc index c1e5added30e..de13ba3bcb6f 100644 --- a/gcc/tree-ssa-alias.cc +++ b/gcc/tree-ssa-alias.cc @@ -3841,6 +3841,18 @@ maybe_skip_until (gimple *phi, tree &target, basic_block target_bb, return true; } +/* qsort comparator for a pair of int and bool. For same int sort + true before false. */ + +static int +cmp_intpair (const void *a_, const void *b_) +{ + auto a = (const std::pair<int, bool> *)a_; + auto b = (const std::pair<int, bool> *)b_; + if (a->first == b->first) + return (int)b->second - (int)a->second; + return a->first - b->first; +} /* Starting from a PHI node for the virtual operand of the memory reference REF find a continuation virtual operand that allows to continue walking @@ -3890,21 +3902,37 @@ get_continuation_for_phi (gphi *phi, ao_ref *ref, bool tbaa_p, do that for us. */ basic_block dom = get_immediate_dominator (CDI_DOMINATORS, phi_bb); + /* Sort the PHI arguments so we can quickly avoid walking duplicates. + Keep pairs of PHI arg and edge backedge state, sorting the backedge + case first which is the conservative walk kind in case we have + a duplicate PHI arg reachable both via a forward and a backward + edge. */ + auto_vec<std::pair<int, bool>, 10> args; + for (i = 0; i < nargs; ++i) + args.safe_push (std::make_pair (SSA_NAME_VERSION (PHI_ARG_DEF (phi, i)), + (!is_backedge + || is_backedge + (gimple_phi_arg_edge (phi, i), + data)))); + args.qsort (cmp_intpair); + /* Then check against the (to be) found candidate. */ for (i = 0; i < nargs; ++i) { - arg1 = PHI_ARG_DEF (phi, i); + arg1 = ssa_name (args[i].first); if (arg1 == arg0) ; + else if (i > 0 && args[i].first == args[i-1].first) + /* Already visited paths can be skipped - we otherwise falsely + abort_on_visited. */ + ; else if (! maybe_skip_until (phi, arg0, dom, ref, arg1, tbaa_p, limit, visited, abort_on_visited, translate, is_backedge, /* Do not valueize when walking over backedges. */ - (is_backedge - && !is_backedge - (gimple_phi_arg_edge (phi, i), data)) + !args[i].second ? disambiguate_only : TR_DISAMBIGUATE, data)) return NULL_TREE;
