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.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
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.
---
gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-117.c | 50 +++++++++++++++++++++
gcc/tree-ssa-alias.cc | 36 +++++++++++++--
2 files changed, 82 insertions(+), 4 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-117.c
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 00000000000..62bc1bddf28
--- /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 c1e5added30..de13ba3bcb6 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;
--
2.51.0
