Re: [PATCH v1] tree-optimization: Merge equality comparisons into memcmp
Richard Biener <[email protected]> Mon, 3 Aug 2026 09:40:11 +0200
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <CAFiYyc3VwWx6ZwW0G-58OkjSriNmy_f5q47PKKp78rSnG4EnOg@mail.gmail.com> |
On Thu, Jul 30, 2026 at 11:57 AM Xuhang Zhou <[email protected]> wrote: > > This continues the work posted at: > > https://gcc.gnu.org/pipermail/gcc-patches/2025-August/693581.html > > Add a tree-SSA pass that recognizes equality comparisons over contiguous bytewise-comparable storage and rewrites them as __builtin_memcmp. The canonical memcmp form gives later middle-end passes and target hooks a simpler representation to optimize. > > The pass handles short-circuited equality chains, such as those produced for C++ operator==, and equality loops over array-like storage. For comparison chains, adjacent byte ranges with the same base objects are merged when byte equality is equivalent to source equality and the widened range stays within the complete object. For loops, the pass recognizes fixed-range indexed loops and fixed-stride pointer loops, including both header-tested and latch-tested forms. > > The transform is conservative. It rejects cases where memcmp could observe bytes not compared by the source program, including padding-sensitive merges, bool and _BitInt comparisons, volatile accesses, unsuitable PHI shapes, and loop comparisons that do not cover the full element range. There is also a narrow special case for the libstdc++ std::equal helper, where the algorithm precondition provides range validity that is not visible inside the helper body. > > Multiple independent comparison chains or loops feeding the same result PHI can be optimized separately when doing so is safe. This should not be a separate pass but integrated with loop distribution which already recognizes strlen and rawmemchr. Richard. > Related LLVM work: > > MergeICmps: https://reviews.llvm.org/D33987 > > Recognize memcmp-like loops: https://github.com/llvm/llvm-project/pull/205885 > > gcc/ > > * Makefile.in (OBJS): Add tree-ssa-eqmerge.o. > > * passes.def: Add pass_eqmerge. > > * timevar.def (TV_TREE_EQMERGE): New timevar. > > * tree-pass.h (make_pass_eqmerge): Declare. > > * tree-ssa-eqmerge.cc: New file. > > gcc/testsuite/ > > * g++.dg/tree-ssa/eqmerge-*.C: New tests. > > * gcc.dg/tree-ssa/eqmerge-negative-bitint.c: New test. > > Testing: make -C /tmp/gcc-eqmerge-build/gcc check-g++ RUNTESTFLAGS='dg.exp=tree-ssa/eqmerge*.C' > Signed-off-by: Xuhang Zhou <[email protected]> > --- > gcc/Makefile.in | 1 + > gcc/passes.def | 1 + > .../g++.dg/tree-ssa/eqmerge-array-2.C | 15 + > gcc/testsuite/g++.dg/tree-ssa/eqmerge-array.C | 11 + > .../g++.dg/tree-ssa/eqmerge-chain-join-phi.C | 29 + > .../g++.dg/tree-ssa/eqmerge-chained-1.C | 12 + > .../g++.dg/tree-ssa/eqmerge-chained-2.C | 9 + > .../g++.dg/tree-ssa/eqmerge-chained-3.C | 20 + > .../tree-ssa/eqmerge-index-loop-chain.C | 17 + > .../tree-ssa/eqmerge-index-loop-join-phi.C | 32 + > .../tree-ssa/eqmerge-index-loop-preheader.C | 24 + > .../tree-ssa/eqmerge-index-loop-struct.C | 22 + > .../g++.dg/tree-ssa/eqmerge-index-loop.C | 92 + > .../g++.dg/tree-ssa/eqmerge-mixed-1.C | 21 + > .../g++.dg/tree-ssa/eqmerge-mixed-2.C | 25 + > .../g++.dg/tree-ssa/eqmerge-mixed-3.C | 22 + > .../g++.dg/tree-ssa/eqmerge-mixed-4.C | 30 + > .../eqmerge-mixed-loops-logic-between.C | 28 + > .../tree-ssa/eqmerge-negative-extra-phi.C | 31 + > .../tree-ssa/eqmerge-negative-extra-use.C | 33 + > .../tree-ssa/eqmerge-negative-index-loop.C | 23 + > .../tree-ssa/eqmerge-negative-neq-loop.C | 31 + > ...eqmerge-negative-nested-std-equal-helper.C | 26 + > .../tree-ssa/eqmerge-negative-padding.C | 12 + > .../tree-ssa/eqmerge-negative-phi-values.C | 22 + > .../eqmerge-negative-pointer-variable-step.C | 24 + > .../eqmerge-negative-shifted-subobject.C | 20 + > .../tree-ssa/eqmerge-negative-volatile.C | 12 + > .../tree-ssa/eqmerge-pointer-loop-dowhile.C | 26 + > .../tree-ssa/eqmerge-pointer-loop-int.C | 20 + > .../tree-ssa/eqmerge-pointer-loop-join-phi.C | 47 + > .../eqmerge-pointer-loop-second-bound.C | 39 + > .../eqmerge-pointer-two-loops-chain.C | 36 + > .../tree-ssa/eqmerge-predict-forwarder.C | 22 + > .../g++.dg/tree-ssa/eqmerge-tuple-1.C | 12 + > .../g++.dg/tree-ssa/eqmerge-tuple-2.C | 12 + > .../gcc.dg/tree-ssa/eqmerge-negative-bitint.c | 35 + > gcc/timevar.def | 1 + > gcc/tree-pass.h | 1 + > gcc/tree-ssa-eqmerge.cc | 3809 +++++++++++++++++ > 40 files changed, 4705 insertions(+) > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-array-2.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-array.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-chain-join-phi.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-1.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-2.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-3.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-chain.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-join-phi.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-preheader.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-struct.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-1.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-2.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-3.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-4.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-loops-logic-between.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-phi.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-use.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-index-loop.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-neq-loop.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-nested-std-equal-helper.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-padding.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-phi-values.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-pointer-variable-step.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-shifted-subobject.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-volatile.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-dowhile.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-int.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-join-phi.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-second-bound.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-two-loops-chain.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-predict-forwarder.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-1.C > create mode 100644 gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-2.C > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/eqmerge-negative-bitint.c > create mode 100644 gcc/tree-ssa-eqmerge.cc > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > index ee2f9022eab..96a6c74a6eb 100644 > --- a/gcc/Makefile.in > +++ b/gcc/Makefile.in > @@ -1829,6 +1829,7 @@ OBJS = \ > tree-ssa-uninit.o \ > tree-ssa.o \ > tree-ssanames.o \ > + tree-ssa-eqmerge.o \ > tree-stdarg.o \ > tree-streamer.o \ > tree-streamer-in.o \ > diff --git a/gcc/passes.def b/gcc/passes.def > index 9095c134f49..d937637e501 100644 > --- a/gcc/passes.def > +++ b/gcc/passes.def > @@ -108,6 +108,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_profile); > NEXT_PASS (pass_local_pure_const); > NEXT_PASS (pass_modref); > + NEXT_PASS (pass_eq_merge); > /* Split functions creates parts that are not run through > early optimizations again. It is thus good idea to do this > late. */ > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-array-2.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-array-2.C > new file mode 100644 > index 00000000000..c2ae8bc1870 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-array-2.C > @@ -0,0 +1,15 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq (const int (&x)[10], const int (&y)[10]) > +{ > + > + for(const int *p1 = x, *p2 = y, *e1 = x + 10; p1 != e1; ++p1, ++p2) > + { > + if (*p1 != *p2) > + return false; > + } > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 40\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-array.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-array.C > new file mode 100644 > index 00000000000..2b6e3209b8e > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-array.C > @@ -0,0 +1,11 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +#include <array> > + > +bool eq (const std::array<int, 5> &x, const std::array<int, 5> &y) > +{ > + return x == y; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chain-join-phi.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chain-join-phi.C > new file mode 100644 > index 00000000000..0ad2deaf6e0 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chain-join-phi.C > @@ -0,0 +1,29 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S { int a, b; }; > + > +bool > +eq_chain_join_phi (const S &x, const S &y, bool flag, int z) > +{ > + int tag; > + if (flag) > + { > + tag = z; > + if (x.a != y.a) > + return false; > + if (x.b != y.b) > + return false; > + } > + else > + tag = z + 1; > + > + /* The comparison chain is non-terminal: its all-equal edge reaches a join > + block with a real PHI for TAG before control reaches the result PHI. */ > + if (tag == 12345) > + __builtin_unreachable (); > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 8\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-1.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-1.C > new file mode 100644 > index 00000000000..5ebf6f31960 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-1.C > @@ -0,0 +1,12 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S { int a, b, c, d; }; > + > +bool eq (const S &x, const S &y) > +{ > + return x.a == y.a && x.b == y.b && x.c == y.c && x.d == y.d; > +} > + > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 16\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-2.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-2.C > new file mode 100644 > index 00000000000..2c82f044fee > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-2.C > @@ -0,0 +1,9 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq (const int (&x)[4], const int (&y)[4]) > +{ > + return x[0] == y[0] && x[1] == y[1] && x[2] == y[2] && x[3] == y[3]; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 16\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-3.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-3.C > new file mode 100644 > index 00000000000..40b8c189bbd > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-chained-3.C > @@ -0,0 +1,20 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S1 > +{ > + long long a; > + int b; > + int unused; > +}; > + > +bool eq (const S1 &x, const S1 &y) > +{ > + if (x.a != y.a) > + return false; > + if (x.b != y.b) > + return false; > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 12\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-chain.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-chain.C > new file mode 100644 > index 00000000000..8b05b0d9916 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-chain.C > @@ -0,0 +1,17 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 0; i < 5; ++i) > + if (x[i] != y[i]) > + return false; > + > + for (int i = 5; i < 10; ++i) > + if (x[i] != y[i]) > + return false; > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-join-phi.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-join-phi.C > new file mode 100644 > index 00000000000..ac92b9c1b0a > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-join-phi.C > @@ -0,0 +1,32 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +extern void sink (int); > + > +bool > +eq_join_phi_between_loops (const int (&x)[10], const int (&y)[10], bool flag) > +{ > + int tag; > + if (flag) > + { > + tag = 1; > + for (int i = 0; i < 5; ++i) > + if (x[i] != y[i]) > + return false; > + } > + else > + tag = 2; > + > + /* The first loop is non-terminal: its all-equal edge reaches a join block > + with a real PHI for TAG before control continues to the second loop. */ > + sink (tag); > + > + for (int i = 5; i < 10; ++i) > + if (x[i] != y[i]) > + return false; > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "sink" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-preheader.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-preheader.C > new file mode 100644 > index 00000000000..e806d0b2c52 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-preheader.C > @@ -0,0 +1,24 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq_preheader (const int (&x)[3], const int (&y)[3], > + const int (*z1)[4], const int (*z2)[4], long offset) > +{ > + for (int i = 0; i < 3; ++i) > + if (x[i] != y[i]) > + return false; > + > + const int (*p)[4] = z1 + offset; > + const int (*q)[4] = z2 + offset; > + for (int i = 0; i < 4; ++i) > + if ((*p)[i] != (*q)[i]) > + return false; > + > + return true; > +} > + > +// The first loop is rewritten in place at its own entry edge into one 16-byte > +// memcmp. The second loop walks a runtime-computed array pointer (z1 + offset) > +// and is left alone; each loop is handled independently. > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 12\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp \\(.*?, .*?, 16\\)" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-struct.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-struct.C > new file mode 100644 > index 00000000000..92ece299847 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop-struct.C > @@ -0,0 +1,22 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S > +{ > + int a, b, c, d; > + bool operator== (const S &o) const > + { > + return a == o.a && b == o.b && c == o.c && d == o.d; > + } > +}; > + > +bool eq_struct_indexed (const S (&x)[10], const S (&y)[10]) > +{ > + for (int i = 0; i < 10; ++i) > + if (!(x[i] == y[i])) > + return false; > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 16\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 160\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop.C > new file mode 100644 > index 00000000000..598124fb35a > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-index-loop.C > @@ -0,0 +1,92 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 0; i < 10; ++i) > + if (x[i] != y[i]) > + return false; > + return true; > +} > + > +bool eq_latch (const int (&x)[10], const int (&y)[10]) > +{ > + int i = 0; > + do > + { > + if (x[i] != y[i]) > + return false; > + ++i; > + } > + while (i != 10); > + return true; > +} > + > + > +bool eq_one_based (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 1; i < 10; ++i) > + if (x[i] != y[i]) > + return false; > + return true; > +} > + > +bool eq_middle_range (const int (&x)[12], const int (&y)[12]) > +{ > + for (int i = 3; i <= 10; ++i) > + if (x[i] != y[i]) > + return false; > + return true; > +} > + > + > +bool eq_decrement (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 9; i >= 0; --i) > + if (x[i] != y[i]) > + return false; > + return true; > +} > + > +bool eq_reverse_middle_range (const int (&x)[12], const int (&y)[12]) > +{ > + for (int i = 10; i > 3; --i) > + if (x[i] != y[i]) > + return false; > + return true; > +} > + > + > +extern void init (int *); > + > +bool eq_local_arrays () > +{ > + int x[30]; > + int y[30]; > + init (x); > + init (y); > + for (int i = 5; i < 20; ++i) > + if (x[i] != y[i]) > + return false; > + return true; > +} > + > +bool eq_two_index_loops (const int (&x)[12], const int (&y)[12]) > +{ > + for (int i = 0; i < 5; ++i) > + if (x[i] != y[i]) > + return false; > + > + for (int i = 6; i <= 10; ++i) > + if (x[i] != y[i]) > + return false; > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 28\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 32\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 36\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 40\\)" 3 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 60\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-1.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-1.C > new file mode 100644 > index 00000000000..e1a120f5d41 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-1.C > @@ -0,0 +1,21 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +#include <array> > + > +struct S > +{ > + int a, b, c, d; > + bool operator== (const S &o) const > + { > + return a == o.a && b == o.b && c == o.c && d == o.d; > + } > +}; > + > +bool eq (const std::array<S, 5> &x, const std::array<S, 5> &y) > +{ > + return x == y; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 16\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 80\\)" 2 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-2.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-2.C > new file mode 100644 > index 00000000000..d28ff825c9a > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-2.C > @@ -0,0 +1,25 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +#include <array> > +#include <utility> > + > +struct S > +{ > + int a, b, c, d; > + bool operator== (const S &o) const > + { > + return a == o.a && b == o.b && c == o.c && d == o.d; > + } > +}; > + > +typedef std::pair<std::array<S, 4>, std::array<S, 4>> P; > + > +bool eq (const P &x, const P &y) > +{ > + return x == y; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 16\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 64\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 128\\)" 2 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-3.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-3.C > new file mode 100644 > index 00000000000..7505a7d3a47 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-3.C > @@ -0,0 +1,22 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S > +{ > + int a, b, c, d; > + bool operator== (const S &o) const > + { > + return a == o.a && b == o.b && c == o.c && d == o.d; > + } > +}; > + > +bool eq (const S (&x)[10], const S (&y)[10]) > +{ > + for (int i = 0; i < 10; ++i) > + if (! (x[i] == y[i])) > + return false; > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 16\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 160\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-4.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-4.C > new file mode 100644 > index 00000000000..8fd3238eb1e > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-4.C > @@ -0,0 +1,30 @@ > +// { dg-do compile { target c++17_only } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +#include <array> > +#include <tuple> > +#include <utility> > + > +struct Block > +{ > + int elems[4]; > + > + bool operator== (const Block &o) const > + { > + for (int i = 0; i < 4; ++i) > + if (elems[i] != o.elems[i]) > + return false; > + return true; > + } > +}; > + > +typedef std::tuple<Block, Block> Pair; > + > +bool eq (const std::array<Pair, 4> &x, const std::array<Pair, 4> &y) > +{ > + return x == y; > +} > + > +// { dg-final { scan-tree-dump "__builtin_memcmp \\(.*?, .*?, 16\\)" "eqmerge" } } > +// { dg-final { scan-tree-dump "__builtin_memcmp \\(.*?, .*?, 32\\)" "eqmerge" } } > +// { dg-final { scan-tree-dump "__builtin_memcmp \\(.*?, .*?, 128\\)" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-loops-logic-between.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-loops-logic-between.C > new file mode 100644 > index 00000000000..89021cd0b64 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-mixed-loops-logic-between.C > @@ -0,0 +1,28 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +extern void side_effect (); > + > +bool eq (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 0; i < 5; ++i) > + if (x[i] != y[i]) > + return false; > + > + side_effect (); > + > + const int *p1 = x + 5, *p2 = y + 5, *e = x + 10; > + while (p1 != e) > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp \\(.*?, .*?, 40\\)" "eqmerge" } } > +// { dg-final { scan-tree-dump-times "side_effect" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-phi.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-phi.C > new file mode 100644 > index 00000000000..e0ec706b88d > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-phi.C > @@ -0,0 +1,31 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S { int x; int y; }; > + > +bool eq_chain_extra_result (const S &a, const S &b, int *mismatch) > +{ > + bool equal; > + int code; > + > + if (a.x != b.x) > + { > + equal = false; > + code = 1; > + } > + else if (a.y != b.y) > + { > + equal = false; > + code = 2; > + } > + else > + { > + equal = true; > + code = 0; > + } > + > + *mismatch = code; > + return equal; > +} > + > +// { dg-final { scan-tree-dump-times "if \\(" 2 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-use.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-use.C > new file mode 100644 > index 00000000000..4a7221e794b > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-extra-use.C > @@ -0,0 +1,33 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct E > +{ > + int value; > +}; > + > +bool eq_ptr_extra_use (const E (&x)[4], const E (&y)[4], const E **out) > +{ > + const E *p1 = x; > + const E *p2 = y; > + const E *end = x + 4; > + bool equal = true; > + > + while (p1 != end) > + { > + if (p1->value != p2->value) > + { > + equal = false; > + break; > + } > + ++p1; > + ++p2; > + } > + > + *out = p1; > + return equal; > +} > + > +// The final iterator escapes the comparison loop and must remain defined. > +// { dg-final { scan-tree-dump-times "if \\(" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > \ No newline at end of file > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-index-loop.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-index-loop.C > new file mode 100644 > index 00000000000..bcaf74ba14a > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-index-loop.C > @@ -0,0 +1,23 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq_step_two (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 0; i < 10; i += 2) > + if (x[i] != y[i]) > + return false; > + return true; > +} > +bool eq_extra_index_use (const int (&x)[10], const int (&y)[10], int *sink) > +{ > + for (int i = 0; i < 10; ++i) > + { > + *sink += i; > + if (x[i] != y[i]) > + return false; > + } > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "if \\(" 4 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > \ No newline at end of file > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-neq-loop.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-neq-loop.C > new file mode 100644 > index 00000000000..836900cb6ca > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-neq-loop.C > @@ -0,0 +1,31 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool > +ne_indexed_loop (const int (&x)[10], const int (&y)[10]) > +{ > + for (int i = 0; i < 10; ++i) > + if (x[i] != y[i]) > + return true; > + > + return false; > +} > + > +bool > +ne_pointer_loop (const int (&x)[10], const int (&y)[10]) > +{ > + const int *p1 = x; > + const int *p2 = y; > + const int *e1 = x + 10; > + while (p1 != e1) > + { > + if (*p1 != *p2) > + return true; > + ++p1; > + ++p2; > + } > + > + return false; > +} > + > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-nested-std-equal-helper.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-nested-std-equal-helper.C > new file mode 100644 > index 00000000000..a50ee374f43 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-nested-std-equal-helper.C > @@ -0,0 +1,26 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +namespace std { namespace __detail { > + > +template <bool> > +struct __equal > +{ > + __attribute__((noipa)) > + static bool equal (const int *first1, const int *last1, const int *first2) > + { > + for (; first1 != last1; ++first1, ++first2) > + if (*first1 != *first2) > + return false; > + return true; > + } > +}; > + > +}} > + > +bool fake_nested_equal (const int *first1, const int *last1, const int *first2) > +{ > + return std::__detail::__equal<false>::equal (first1, last1, first2); > +} > + > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-padding.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-padding.C > new file mode 100644 > index 00000000000..d9f6022b373 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-padding.C > @@ -0,0 +1,12 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S { char a; int b; }; > + > +bool eq (const S &x, const S &y) > +{ > + return x.a == y.a && x.b == y.b; > +} > + > +// { dg-final { scan-tree-dump-times "if \\(" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > \ No newline at end of file > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-phi-values.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-phi-values.C > new file mode 100644 > index 00000000000..edbdae14a3d > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-phi-values.C > @@ -0,0 +1,22 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct Pair > +{ > + int x; > + int y; > +}; > + > +int mismatch_code (const Pair &a, const Pair &b) > +{ > + if (a.x != b.x) > + return 1; > + if (a.y != b.y) > + return 2; > + return 3; > +} > + > +// Distinct mismatch and success values must not be collapsed into one > +// boolean memcmp result. > +// { dg-final { scan-tree-dump-times "if \\(" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > \ No newline at end of file > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-pointer-variable-step.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-pointer-variable-step.C > new file mode 100644 > index 00000000000..3cb447871d0 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-pointer-variable-step.C > @@ -0,0 +1,24 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct E > +{ > + char value; > +}; > + > +bool eq_variable_step (const E *p1, const E *p2, const E *end, > + unsigned long step) > +{ > + while (p1 != end) > + { > + if (p1->value != p2->value) > + return false; > + p1 += step; > + p2 += step; > + } > + return true; > +} > + > +// A runtime byte stride is not a fixed-size memcmp range. > +// { dg-final { scan-tree-dump-times "if \\(" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-shifted-subobject.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-shifted-subobject.C > new file mode 100644 > index 00000000000..e4225321f36 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-shifted-subobject.C > @@ -0,0 +1,20 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S > +{ > + int pad; > + int a; > + int b; > +}; > + > +bool shifted_subobject_memcmp (S (&x)[5], S (&y)[5]) > +{ > + for (int i = 0; i < 4; ++i) > + if (__builtin_memcmp (&x[i].a, &y[i].a, sizeof (S)) != 0) > + return false; > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 12\\)" 1 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp \\(.*?, .*?, 48\\)" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-volatile.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-volatile.C > new file mode 100644 > index 00000000000..2628c637e86 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-negative-volatile.C > @@ -0,0 +1,12 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +struct S { volatile int a, b, c, d; }; > + > +bool eq (const S &x, const S &y) > +{ > + return x.a == y.a && x.b == y.b && x.c == y.c && x.d == y.d; > +} > + > +// { dg-final { scan-tree-dump-times "if \\(" 4 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-dowhile.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-dowhile.C > new file mode 100644 > index 00000000000..c559042de4c > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-dowhile.C > @@ -0,0 +1,26 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +// Pointer-walking equality loop in do-while (latch-tested) form. The > +// iterator PHIs live in the comparison block and the pointer advance is > +// fused with the bound test in the latch block. This mirrors the indexed > +// latch shape handled by parse_indexed_latch and must collapse to one > +// memcmp just like the header-tested form. > +bool eq (const int (&x)[10], const int (&y)[10]) > +{ > + const int *p1 = x; > + const int *p2 = y; > + const int *e1 = x + 10; > + do > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + while (p1 != e1); > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 40\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-int.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-int.C > new file mode 100644 > index 00000000000..f5f124282d8 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-int.C > @@ -0,0 +1,20 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool eq (const int (&x)[10], const int (&y)[10]) > +{ > + const int *p1 = x; > + const int *p2 = y; > + const int *e1 = x + 10; > + while (p1 != e1) > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 40\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-join-phi.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-join-phi.C > new file mode 100644 > index 00000000000..0263ee05d2e > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-join-phi.C > @@ -0,0 +1,47 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +extern void sink (int); > + > +bool > +eq_ptr_join_phi_between_loops (const int (&x)[10], const int (&y)[10], > + bool flag) > +{ > + int tag; > + if (flag) > + { > + tag = 1; > + const int *p1 = x; > + const int *p2 = y; > + const int *e1 = x + 5; > + while (p1 != e1) > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + } > + else > + tag = 2; > + > + /* The first loop is non-terminal: its all-equal edge reaches a join block > + with a real PHI for TAG before control continues to the second loop. */ > + sink (tag); > + > + const int *p1 = x + 5; > + const int *p2 = y + 5; > + const int *e1 = x + 10; > + while (p1 != e1) > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-times "sink" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-second-bound.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-second-bound.C > new file mode 100644 > index 00000000000..d7ebd1a1f67 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-loop-second-bound.C > @@ -0,0 +1,39 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +bool > +eq_header_bound_second (const int (&x)[10], const int (&y)[10]) > +{ > + const int *p1 = x; > + const int *p2 = y; > + const int *e2 = y + 10; > + while (p2 != e2) > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + > + return true; > +} > + > +bool > +eq_latch_bound_second (const int (&x)[10], const int (&y)[10]) > +{ > + const int *p1 = x; > + const int *p2 = y; > + const int *e2 = y + 10; > + do > + { > + if (*p1 != *p2) > + return false; > + ++p1; > + ++p2; > + } > + while (p2 != e2); > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 40\\)" 2 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-two-loops-chain.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-two-loops-chain.C > new file mode 100644 > index 00000000000..e4bac913678 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-pointer-two-loops-chain.C > @@ -0,0 +1,36 @@ > +// { dg-do compile } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +// Two pointer-walking equality loops feeding one result PHI, with all of the > +// second loop's iterator setup hoisted before the first loop so the boundary > +// between the loops is empty. Each loop is rewritten in place at its own entry > +// edge into its own memcmp; the ranges are not merged, so this yields two > +// 20-byte memcmps rather than one 40-byte memcmp. > +struct E { int value; }; > + > +bool eq (const E (&x)[10], const E (&y)[10]) > +{ > + const E *p1 = x, *p2 = y, *e1 = x + 5; > + const E *p3 = x + 5, *p4 = y + 5, *e2 = x + 10; > + > + while (p1 != e1) > + { > + if (p1->value != p2->value) > + return false; > + ++p1; > + ++p2; > + } > + > + while (p3 != e2) > + { > + if (p3->value != p4->value) > + return false; > + ++p3; > + ++p4; > + } > + > + return true; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 20\\)" 2 "eqmerge" } } > +// { dg-final { scan-tree-dump-not "__builtin_memcmp \\(.*?, .*?, 40\\)" "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-predict-forwarder.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-predict-forwarder.C > new file mode 100644 > index 00000000000..d114ab13b1b > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-predict-forwarder.C > @@ -0,0 +1,22 @@ > +// { dg-do compile } > +// { dg-options "-std=c++20 -O2 -fdump-tree-eqmerge" } > + > +struct S > +{ > + int x; > + int y; > +}; > + > +bool > +eq_predict_forwarder (const S &a, const S &b) > +{ > + if (a.x != b.x) [[unlikely]] > + return false; > + if (a.y != b.y) [[unlikely]] > + return false; > + return true; > +} > + > +// [[unlikely]] leaves GIMPLE_PREDICT statements in the mismatch forwarding > +// blocks. Those blocks should be transparent for comparison-chain discovery. > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 8\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-1.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-1.C > new file mode 100644 > index 00000000000..90c4abadafa > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-1.C > @@ -0,0 +1,12 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +#include <tuple> > + > +bool eq_tuple (const std::tuple<int, int> &x, > + const std::tuple<int, int> &y) > +{ > + return x == y; > +} > + > +// { dg-final { scan-tree-dump-times "__builtin_memcmp \\(.*?, .*?, 8\\)" 1 "eqmerge" } } > diff --git a/gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-2.C b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-2.C > new file mode 100644 > index 00000000000..7c83edd35bb > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/eqmerge-tuple-2.C > @@ -0,0 +1,12 @@ > +// { dg-do compile { target c++17 } } > +// { dg-options "-O2 -fdump-tree-eqmerge" } > + > +#include <tuple> > + > +bool eq_tuple_bool (const std::tuple<bool, int> &x, > + const std::tuple<bool, int> &y) > +{ > + return x == y; > +} > + > +// { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/eqmerge-negative-bitint.c b/gcc/testsuite/gcc.dg/tree-ssa/eqmerge-negative-bitint.c > new file mode 100644 > index 00000000000..d28c44c7ba8 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/eqmerge-negative-bitint.c > @@ -0,0 +1,35 @@ > +/* { dg-do compile } */ > +/* { dg-options "-std=c23 -O2 -fdump-tree-eqmerge" } */ > + > +typedef unsigned _BitInt(9) u9; > + > +struct Pair9 > +{ > + u9 x; > + u9 y; > +}; > + > +bool eq_fields (const struct Pair9 *a, const struct Pair9 *b) > +{ > + if (a->x != b->x) > + return false; > + if (a->y != b->y) > + return false; > + return true; > +} > + > +struct Array9 > +{ > + u9 values[4]; > +}; > + > +bool eq_array (const struct Array9 *a, const struct Array9 *b) > +{ > + for (int i = 0; i < 4; ++i) > + if (a->values[i] != b->values[i]) > + return false; > + return true; > +} > + > +/* Padding bits in _BitInt objects are not part of value equality. */ > +/* { dg-final { scan-tree-dump-not "__builtin_memcmp" "eqmerge" } } */ > diff --git a/gcc/timevar.def b/gcc/timevar.def > index fc78600b652..b28f17694b3 100644 > --- a/gcc/timevar.def > +++ b/gcc/timevar.def > @@ -309,6 +309,7 @@ DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking") > DEFTIMEVAR (TV_VAR_TRACKING_DATAFLOW , "var-tracking dataflow") > DEFTIMEVAR (TV_VAR_TRACKING_EMIT , "var-tracking emit") > DEFTIMEVAR (TV_TREE_IFCOMBINE , "tree if-combine") > +DEFTIMEVAR (TV_TREE_EQMERGE , "tree eqmerge") > DEFTIMEVAR (TV_TREE_IF_TO_SWITCH , "if to switch conversion") > DEFTIMEVAR (TV_TREE_UNINIT , "uninit var analysis") > DEFTIMEVAR (TV_PLUGIN_INIT , "plugin initialization") > diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h > index a3b35e009e0..0ba60e0ecf9 100644 > --- a/gcc/tree-pass.h > +++ b/gcc/tree-pass.h > @@ -507,6 +507,7 @@ extern gimple_opt_pass *make_pass_warn_nonnull_compare (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_sprintf_length (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_walloca (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_modref (gcc::context *ctxt); > +extern gimple_opt_pass *make_pass_eq_merge (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_coroutine_lower_builtins (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_coroutine_early_expand_ifns (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_adjust_alignment (gcc::context *ctxt); > diff --git a/gcc/tree-ssa-eqmerge.cc b/gcc/tree-ssa-eqmerge.cc > new file mode 100644 > index 00000000000..79567bacb00 > --- /dev/null > +++ b/gcc/tree-ssa-eqmerge.cc > @@ -0,0 +1,3809 @@ > +/* Merge chained equality comparisons into __builtin_memcmp. > + Copyright (C) 2026 Free Software Foundation, Inc. > + > +This file is part of GCC. > + > +GCC is free software; you can redistribute it and/or modify > +it under the terms of the GNU General Public License as published by > +the Free Software Foundation; either version 3, or (at your option) > +any later version. > + > +GCC is distributed in the hope that it will be useful, > +but WITHOUT ANY WARRANTY; without even the implied warranty of > +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the > +GNU General Public License for more details. > + > +You should have received a copy of the GNU General Public License > +along with GCC; see the file COPYING3. If not see > +<http://www.gnu.org/licenses/>. */ > + > +#include "config.h" > +#include "system.h" > +#include "coretypes.h" > +#include "backend.h" > +#include "tree.h" > +#include "gimple.h" > +#include "tree-pass.h" > +#include "ssa.h" > +#include "fold-const.h" > +#include "gimple-iterator.h" > +#include "gimple-fold.h" > +#include "tree-cfg.h" > +#include "tree-dfa.h" > +#include "tree-into-ssa.h" > +#include "cfghooks.h" > +#include "cfganal.h" > +#include "stringpool.h" > +#include "attribs.h" > +#include "builtins.h" > +#include "gimple-pretty-print.h" > + > +/* This pass recognizes short-circuited equality tests over contiguous > + bytewise-comparable storage and rewrites them into __builtin_memcmp. > + > + (1) A chain of conditional field comparisons feeding a PHI node, as > + produced by C++20 defaulted operator== or by hand-written > + short-circuited && chains. Contiguous fields with the same base are > + folded into one memcmp. > + > + (2) Equality loops over contiguous integer elements. The loop handling > + accepts fixed-trip-count ARRAY_REF loops first, then pointer-walking > + loops whose full byte range is statically provable, and finally the > + std::__equal::equal helper emitted by libstdc++ where the algorithm > + precondition supplies range validity that is not visible in the helper > + body. > + > + All rewrites are conservative: the pass only widens to a memcmp when the > + compared bytes exactly model source equality and the full byte range is > + known safe to read. */ > + > +namespace { > + > +/* Return the EDGE_TRUE_VALUE successor edge in EDGES. */ > + > +static inline edge > +get_true_edge (vec<edge, va_gc> *edges) > +{ > + return EDGE_I (edges, (EDGE_I (edges, 0)->flags & EDGE_TRUE_VALUE) ? 0 : 1); > +} > + > +/* Return the EDGE_FALSE_VALUE successor edge in EDGES. */ > + > +static inline edge > +get_false_edge (vec<edge, va_gc> *edges) > +{ > + return EDGE_I (edges, (EDGE_I (edges, 0)->flags & EDGE_FALSE_VALUE) ? 0 : 1); > +} > + > +/* Description of one loaded value used by a comparison block. > + BASE, OFFSET and SIZE describe the memory location and byte range, > + SSA_VAR_DEF is the statement that computes the value or address, and > + IS_ADDRESS records whether SSA_VAR_DEF already yields an address. */ > + > +struct load_info > +{ > + tree base; > + widest_int offset; > + widest_int size; > + gimple *ssa_var_def; > + bool is_address; > +}; > + > +/* Description of one equality comparison operation. */ > +struct cmp_info > +{ > + load_info lhs; > + load_info rhs; > + /* True when bytewise equality matches source-level equality. */ > + bool can_use_memcmp_p; > + /* The compare condition is normalized; true means lhs == rhs. */ > + /* Value assigned to the result PHI for the condition false edge. */ > + tree phi_false_val; > + /* Value assigned to the result PHI for the condition true edge. */ > + tree phi_true_val; > +}; > + > +struct cmp_chain > +{ > + vec<cmp_info> cmps; > + > + basic_block last_bb; > + /* The list of edges coming into the first block in the chain. */ > + vec<edge> incoming_edges; > +}; > + > +/* Return true if CMP holds a successfully parsed comparison. */ > + > +static inline bool > +cmp_info_is_valid (const cmp_info &cmp) > +{ > + return cmp.lhs.base != NULL; > +} > + > +/* Return true if LOAD holds a successfully parsed load. */ > + > +static inline bool > +load_info_is_valid (const load_info &load) > +{ > + return load.base != NULL; > +} > + > +/* Return a cmp_info that fails cmp_info_is_valid. */ > + > +static inline cmp_info > +invalid_cmp_info () > +{ > + return { > + { NULL, 0, 0, NULL, false }, > + { NULL, 0, 0, NULL, false }, > + false, NULL_TREE, NULL_TREE > + }; > +} > + > +static bool comparison_block_p (basic_block bb, bool allow_phi = false); > +static cmp_info parse_cmp_block (basic_block bb); > +static cmp_info parse_load_cmp_cond (gcond *stmt); > +static cmp_info parse_memcmp_cond (gcond *stmt); > +static load_info load_info_from_ssa (tree ssa); > +static bool ssa_load_can_use_memcmp_p (tree ssa); > +static bool normalize_bb_condition (basic_block bb, > + tree_code true_edge_code = EQ_EXPR); > +static edge find_decision_edge_from_phi_arg (gphi *phi_stmt, size_t arg_i); > +static gphi *find_phi_with_result (basic_block bb, tree result); > +static basic_block find_succ_ignore_empties (basic_block bb); > + > +/* Phase 2 loop parsers/appliers, defined below but used by the shared > + per-mismatch-edge driver. */ > +struct indexed_cmp_loop; > +struct ptr_cmp_loop; > +static bool parse_indexed_cmp_loop (basic_block bb_compare, > + basic_block bb_bound, > + basic_block bb_phi, > + basic_block bb_end, > + indexed_cmp_loop *loop); > +static bool apply_indexed_cmp_loop (indexed_cmp_loop &loop, basic_block bb_phi, > + tree result_phi_name, > + tree false_value, tree true_value); > +static bool parse_ptr_cmp_loop (basic_block bb_compare, > + basic_block bb_bound, > + basic_block bb_phi, > + basic_block bb_end, > + ptr_cmp_loop *loop); > +static bool apply_ptr_cmp_loop (ptr_cmp_loop &loop, basic_block bb_phi, > + tree result_phi_name, > + tree false_value, tree true_value, > + bool require_static_range_p); > +static bool ptr_cmp_loop_static_range_safe_p (const ptr_cmp_loop &loop); > +static bool try_rewrite_cmp_loop_from_mismatch (edge mismatch_e, > + basic_block bb_phi, > + tree result_phi_name, > + tree false_value, tree true_value, > + bool require_static_range_p); > + > +/* Return true for empty forwarders and blocks that contain only prediction > + hints. Early return prediction statements should not hide the comparison > + block that logically feeds a PHI argument. */ > + > +static bool > +empty_or_predict_block_p (basic_block bb) > +{ > + if (empty_block_p (bb)) > + return true; > + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); > + gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (is_gimple_debug (stmt) || gimple_code (stmt) == GIMPLE_PREDICT) > + continue; > + return false; > + } > + return true; > +} > + > +/* If E_CURRENT comes from an empty or prediction-only fallthrough block, > + walk backward through single-predecessor forwarding blocks to the edge from > + the block that made the control-flow decision. */ > + > +static edge > +find_decision_edge_through_forwarders (edge e_current) > +{ > + if (!empty_or_predict_block_p (e_current->src)) > + return e_current; > + if (!(e_current->flags & EDGE_FALLTHRU)) > + return NULL; > + > + /* Prediction-only early-return blocks are transparent for this pattern, > + but only while the predecessor chain is unambiguous. */ > + if (!single_pred_p (e_current->src)) > + return e_current; > + basic_block bb_current = e_current->src; > + while (bb_current != NULL) > + { > + e_current = single_pred_edge (bb_current); > + bb_current = e_current->src; > + if (!empty_or_predict_block_p (bb_current)) > + return e_current; > + if (!single_pred_p (bb_current)) > + return e_current; > + } > + return NULL; > +} > + > +/* Return the decision edge that logically feeds PHI argument ARG_I of > + BB_PHI. > + If the direct PHI predecessor is an empty or prediction-only fallthrough > + block, walk backward through single-predecessor forwarding blocks to the > + branch that selected that PHI value. */ > + > +static edge > +find_decision_edge_from_phi_arg (gphi *phi_stmt, size_t arg_i) > +{ > + return find_decision_edge_through_forwarders > + (gimple_phi_arg_edge (phi_stmt, arg_i)); > +} > + > +/* Return the current PHI in BB whose result is RESULT. > + > + Creating edges into a PHI block can reallocate PHI nodes. Callers that > + select a PHI before CFG mutation should keep the result SSA_NAME and use > + this helper before touching the PHI again. */ > + > +static gphi * > +find_phi_with_result (basic_block bb, tree result) > +{ > + for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); > + gsi_next (&gpi)) > + { > + gphi *phi = *gpi; > + if (gimple_phi_result (phi) == result) > + return phi; > + } > + return NULL; > +} > + > +/* Follow single-successor empty blocks until a non-empty block is reached. > + Return NULL if an empty block with more than one successor is hit. */ > + > +static basic_block > +find_succ_ignore_empties (basic_block bb) > +{ > + basic_block bb_current = bb; > + while (true) > + { > + if (!empty_or_predict_block_p (bb_current)) > + return bb_current; > + if (!single_succ_p (bb_current)) > + return NULL; > + bb_current = single_succ (bb_current); > + } > +} > + > +/* Starting from E, follow single-successor empty or prediction-only blocks > + until DEST is reached. Return the edge entering DEST, or NULL if the path > + is not an unambiguous forwarder chain to DEST. */ > + > +static edge > +find_edge_to_dest_through_forwarders (edge e, basic_block dest) > +{ > + if (e->dest == dest) > + return e; > + > + basic_block bb_current = e->dest; > + while (empty_or_predict_block_p (bb_current)) > + { > + if (!single_succ_p (bb_current)) > + return NULL; > + e = single_succ_edge (bb_current); > + if (e->dest == dest) > + return e; > + bb_current = e->dest; > + } > + return NULL; > +} > + > +/* Save every PHI argument from OLD_EDGE so it can later be attached to a new > + edge reaching the same successor. > + > + Non-terminal loop rewrites bypass the original all-equal exit edge but > + continue to the same successor. The new edge must therefore carry the same > + PHI values. This is semantically required for real PHIs; copying virtual > + PHIs too keeps PHI arity consistent until TODO_update_ssa refreshes virtual > + operands. */ > + > +static void > +save_phi_args_from_edge (edge old_edge, > + auto_vec<tree> &args, > + auto_vec<location_t> &locations) > +{ > + for (gphi_iterator gpi = gsi_start_phis (old_edge->dest); > + !gsi_end_p (gpi); gsi_next (&gpi)) > + { > + gphi *phi = *gpi; > + args.safe_push (gimple_phi_arg_def_from_edge (phi, old_edge)); > + locations.safe_push (gimple_phi_arg_location_from_edge (phi, old_edge)); > + } > +} > + > +/* Add saved PHI ARGS and LOCATIONS to NEW_EDGE. DEST is the successor block > + whose PHI list was used by save_phi_args_from_edge. */ > + > +static void > +add_saved_phi_args_to_new_edge (basic_block dest, edge new_edge, > + auto_vec<tree> &args, > + auto_vec<location_t> &locations) > +{ > + gcc_checking_assert (dest == new_edge->dest); > + gcc_checking_assert (args.length () == locations.length ()); > + > + unsigned i = 0; > + for (gphi_iterator gpi = gsi_start_phis (dest); > + !gsi_end_p (gpi); gsi_next (&gpi), ++i) > + { > + gcc_checking_assert (i < args.length ()); > + add_phi_arg (*gpi, args[i], new_edge, locations[i]); > + } > + gcc_checking_assert (i == args.length ()); > +} > + > +static void > +copy_phi_args_to_new_edge (edge old_edge, edge new_edge) > +{ > + auto_vec<tree> args; > + auto_vec<location_t> locations; > + save_phi_args_from_edge (old_edge, args, locations); > + add_saved_phi_args_to_new_edge (old_edge->dest, new_edge, args, locations); > +} > + > +/* An equality loop feeding a result PHI is self-described by its mismatch edge: > + MISMATCH_E is the branch out of the compare block BB_COMPARE that goes to the > + PHI when an element differs. Recover the loop's bound-test block into > + *BB_BOUND and the block its all-equal exit reaches into *BB_END. */ > + > +static bool > +loop_seed_from_compare (basic_block bb_compare, edge mismatch_e, > + basic_block *bb_bound, basic_block *bb_end) > +{ > + if (EDGE_COUNT (bb_compare->succs) != 2) > + return false; > + > + edge eq_e = EDGE_SUCC (bb_compare, 0) == mismatch_e > + ? EDGE_SUCC (bb_compare, 1) : EDGE_SUCC (bb_compare, 0); > + > + basic_block equal_dest = find_succ_ignore_empties (eq_e->dest); > + if (equal_dest == NULL) > + return false; > + > + basic_block bound; > + if (EDGE_COUNT (equal_dest->succs) == 2) > + /* Latch form: the equality edge lands on the fused bound-test block. */ > + bound = equal_dest; > + else if (single_succ_p (equal_dest)) > + /* Header form: the equality edge lands on the advance block; the bound > + test is its successor. */ > + bound = find_succ_ignore_empties (single_succ (equal_dest)); > + else > + return false; > + if (bound == NULL || EDGE_COUNT (bound->succs) != 2) > + return false; > + > + /* Classify the bound-test block's edges: one continues to BB_COMPARE, the > + other exits the loop. */ > + edge exit_e = NULL, continue_e = NULL; > + edge e; > + edge_iterator ei; > + FOR_EACH_EDGE (e, ei, bound->succs) > + { > + if (find_succ_ignore_empties (e->dest) == bb_compare) > + { > + if (continue_e != NULL) > + return false; > + continue_e = e; > + } > + else > + { > + if (exit_e != NULL) > + return false; > + exit_e = e; > + } > + } > + if (exit_e == NULL || continue_e == NULL) > + return false; > + > + *bb_bound = bound; > + *bb_end = find_succ_ignore_empties (exit_e->dest); > + return *bb_end != NULL; > +} > + > +/* Normalize an EQ/NE condition and its outgoing edge labels so the > + EDGE_TRUE_VALUE successor is taken when the condition evaluates > + TRUE_EDGE_CODE. > + > + TRUE_EDGE_CODE must be EQ_EXPR or NE_EXPR. If the condition currently > + uses the opposite code, swap TRUE/FALSE edge labels and update the > + condition code to preserve semantics. Return false for conditions > + using neither EQ nor NE. Blocks with no condition are left > + unchanged and accepted. */ > + > +static bool > +normalize_bb_condition (basic_block bb, tree_code true_edge_code) > +{ > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gcond *cond = safe_dyn_cast <gcond *> (gsi_stmt (gsi)); > + if (!cond) > + continue; > + gcc_checking_assert (true_edge_code == EQ_EXPR > + || true_edge_code == NE_EXPR); > + tree_code cond_op = gimple_cond_code (cond); > + if (cond_op != EQ_EXPR && cond_op != NE_EXPR) > + return false; > + if (cond_op == true_edge_code) > + continue; > + > + edge e; > + edge_iterator it; > + FOR_EACH_EDGE (e, it, bb->succs) > + { > + if (e->flags & EDGE_TRUE_VALUE) > + { > + e->flags ^= EDGE_TRUE_VALUE; > + e->flags |= EDGE_FALSE_VALUE; > + } > + else if (e->flags & EDGE_FALSE_VALUE) > + { > + e->flags ^= EDGE_FALSE_VALUE; > + e->flags |= EDGE_TRUE_VALUE; > + } > + } > + gimple_cond_set_code (cond, true_edge_code); > + return true; > + } > + return true; > +} > + > +/* Return true if BB is a comparison block accepted by this pass. > + The accepted shape is either two COMPONENT_REF, ARRAY_REF, or permitted > + MEM_REF loads (or their address-taken form) with one use each followed by > + an EQ/NE branch, or the equivalent memcmp-based block produced by an > + earlier run of this pass. */ > + > +static bool > +comparison_block_p (basic_block bb, bool allow_phi) > +{ > + if (!allow_phi && phi_nodes (bb) != NULL) > + return false; > + auto_vec<tree, 4> cmp_ssas; > + gcall *memcmp_call_stmt = NULL; > + > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple *g = gsi_stmt (gsi); > + if (is_gimple_debug (g)) > + continue; > + if (gimple_has_volatile_ops (g)) > + return false; > + if (gassign *assign_stmt = safe_dyn_cast <gassign *> (g)) > + { > + if (cmp_ssas.length () == 2) > + return false; > + if (gimple_assign_rhs2 (assign_stmt) != NULL_TREE) > + return false; > + > + tree assign_val = gimple_assign_rhs1 (assign_stmt); > + if (TREE_CODE (assign_val) == ADDR_EXPR) > + assign_val = TREE_OPERAND (assign_val, 0); > + if (TREE_CODE (assign_val) != COMPONENT_REF > + && TREE_CODE (assign_val) != ARRAY_REF > + && TREE_CODE (assign_val) != MEM_REF) > + return false; > + > + tree cmp_ssa = gimple_assign_lhs (assign_stmt); > + if (TREE_CODE (cmp_ssa) != SSA_NAME) > + return false; > + if (num_imm_uses (cmp_ssa) != 1) > + return false; > + > + cmp_ssas.safe_push (cmp_ssa); > + } > + else if (gcall *memcmp_stmt = safe_dyn_cast <gcall *> (g)) > + { > + if (memcmp_call_stmt != NULL) > + return false; > + tree fndecl = gimple_call_fndecl (memcmp_stmt); > + if (!fndecl > + || !fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)) > + return false; > + if (gimple_call_num_args (memcmp_stmt) != 3 > + || (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_MEMCMP > + && DECL_FUNCTION_CODE (fndecl) != BUILT_IN_MEMCMP_EQ)) > + return false; > + tree lhs = gimple_call_lhs (memcmp_stmt); > + if (!lhs || num_imm_uses (lhs) != 1) > + return false; > + > + memcmp_call_stmt = memcmp_stmt; > + } > + else if (gcond *cmp_cond = safe_dyn_cast <gcond *> (g)) > + { > + tree_code code = gimple_cond_code (cmp_cond); > + if (code != EQ_EXPR && code != NE_EXPR) > + return false; > + > + if (cmp_ssas.length () == 2 && memcmp_call_stmt == NULL) > + { > + /* Plain load compare: > + _1 = a->x; _2 = b->x; if (_1 != _2) */ > + if (gimple_cond_rhs (cmp_cond) == gimple_cond_lhs (cmp_cond)) > + return false; > + if (gimple_cond_lhs (cmp_cond) != cmp_ssas[0] > + && gimple_cond_lhs (cmp_cond) != cmp_ssas[1]) > + return false; > + if (gimple_cond_rhs (cmp_cond) != cmp_ssas[0] > + && gimple_cond_rhs (cmp_cond) != cmp_ssas[1]) > + return false; > + return true; > + } > + else if (cmp_ssas.length () == 2 && memcmp_call_stmt != NULL) > + { > + /* Memcmp-based block from an earlier pass run. */ > + tree memcmp_res_ssa = gimple_call_lhs (memcmp_call_stmt); > + if (((gimple_cond_lhs (cmp_cond) == memcmp_res_ssa) > + ^ (gimple_cond_rhs (cmp_cond) == memcmp_res_ssa)) == 0) > + return false; > + > + tree cond_lhs = gimple_cond_lhs (cmp_cond); > + tree cond_rhs = gimple_cond_rhs (cmp_cond); > + tree cond_constval > + = memcmp_res_ssa == cond_lhs ? cond_rhs : cond_lhs; > + > + if (TREE_CODE_CLASS (TREE_CODE (cond_constval)) != tcc_constant) > + return false; > + if (!integer_zerop (cond_constval)) > + return false; > + > + tree memcmp_a0 = gimple_call_arg (memcmp_call_stmt, 0); > + tree memcmp_a1 = gimple_call_arg (memcmp_call_stmt, 1); > + if (memcmp_a0 == memcmp_a1) > + return false; > + if (memcmp_a0 != cmp_ssas[0] && memcmp_a1 != cmp_ssas[0]) > + return false; > + if (memcmp_a0 != cmp_ssas[1] && memcmp_a1 != cmp_ssas[1]) > + return false; > + tree memcmp_size = gimple_call_arg (memcmp_call_stmt, 2); > + if (TREE_CODE_CLASS (TREE_CODE (memcmp_size)) != tcc_constant) > + return false; > + return true; > + } > + return false; > + } > + else > + return false; > + } > + return false; > +} > + > +/* Parse the condition in BB into a cmp_info. > + Handles direct COMPONENT_REF or ARRAY_REF comparisons and memcmp result > + comparisons produced when this pass runs again after inlining. */ > + > +static cmp_info > +parse_cmp_block (basic_block bb) > +{ > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + if (gcond *stmt = safe_dyn_cast <gcond *> (gsi_stmt (gsi))) > + { > + tree cond_lhs = gimple_cond_lhs (stmt); > + tree cond_rhs = gimple_cond_rhs (stmt); > + if (TREE_CODE_CLASS (TREE_CODE (cond_lhs)) == tcc_constant > + || TREE_CODE_CLASS (TREE_CODE (cond_rhs)) == tcc_constant) > + return parse_memcmp_cond (stmt); > + return parse_load_cmp_cond (stmt); > + } > + } > + return invalid_cmp_info (); > +} > + > +/* Parse component or array reference comparison conditions. */ > + > +static cmp_info > +parse_load_cmp_cond (gcond *stmt) > +{ > + tree cond_lhs = gimple_cond_lhs (stmt); > + tree cond_rhs = gimple_cond_rhs (stmt); > + load_info cond_lhs_load = load_info_from_ssa (cond_lhs); > + load_info cond_rhs_load = load_info_from_ssa (cond_rhs); > + if (!load_info_is_valid (cond_lhs_load) > + || !load_info_is_valid (cond_rhs_load) > + || cond_lhs_load.size != cond_rhs_load.size) > + return invalid_cmp_info (); > + > + /* Avoid memcmp for loads from by-value parameters. The rewrite would take > + their address, and after inlining that can leave aggregate temporaries that > + eSRA cannot remove. */ > + > + bool can_use_memcmp_p > + = (ssa_load_can_use_memcmp_p (cond_lhs) > + && ssa_load_can_use_memcmp_p (cond_rhs) > + && TREE_CODE (cond_lhs_load.base) != PARM_DECL > + && TREE_CODE (cond_rhs_load.base) != PARM_DECL); > + return { cond_lhs_load, cond_rhs_load, can_use_memcmp_p, > + NULL_TREE, NULL_TREE }; > +} > + > +/* Parse a __builtin_memcmp result comparison. */ > + > +static cmp_info > +parse_memcmp_cond (gcond *stmt) > +{ > + tree cond_lhs = gimple_cond_lhs (stmt); > + tree cond_rhs = gimple_cond_rhs (stmt); > + > + tree memcmp_res_ssa > + = TREE_CODE_CLASS (TREE_CODE (cond_lhs)) == tcc_constant > + ? cond_rhs : cond_lhs; > + gimple *memcmp_def = SSA_NAME_DEF_STMT (memcmp_res_ssa); > + > + tree lhs_base_ssa = gimple_call_arg (memcmp_def, 0); > + tree rhs_base_ssa = gimple_call_arg (memcmp_def, 1); > + tree load_size = gimple_call_arg (memcmp_def, 2); > + if (TREE_CODE (load_size) != INTEGER_CST) > + return invalid_cmp_info (); > + widest_int load_bytes = wi::to_widest (load_size); > + > + load_info lhs_load = load_info_from_ssa (lhs_base_ssa); > + load_info rhs_load = load_info_from_ssa (rhs_base_ssa); > + if (!load_info_is_valid (lhs_load) || !load_info_is_valid (rhs_load)) > + return invalid_cmp_info (); > + lhs_load.size = load_bytes; > + rhs_load.size = load_bytes; > + return { lhs_load, rhs_load, true, NULL_TREE, NULL_TREE }; > +} > + > +/* Return true if TYPE is an integer type whose object representation has no > + padding bits that value equality would ignore. Boolean and bit-precise > + integer types are kept as scalar comparisons because equal values need not > + have identical object representations. */ > + > +static bool > +type_can_use_memcmp_p (tree type) > +{ > + if (!INTEGRAL_TYPE_P (type) > + || TREE_CODE (type) == BOOLEAN_TYPE > + || BITINT_TYPE_P (type) > + || !SCALAR_INT_MODE_P (TYPE_MODE (type))) > + return false; > + > + machine_mode mode = TYPE_MODE (type); > + return (type_has_mode_precision_p (type) > + && known_eq (GET_MODE_PRECISION (mode), GET_MODE_BITSIZE (mode))); > +} > + > +/* Return true if SSA is defined by a load whose equality is bytewise. */ > + > +static bool > +ssa_load_can_use_memcmp_p (tree ssa) > +{ > + if (TREE_CODE (ssa) != SSA_NAME) > + return false; > + gimple *ssa_def = SSA_NAME_DEF_STMT (ssa); > + if (!ssa_def || !is_a <gassign *> (ssa_def)) > + return false; > + tree ssa_type = TREE_TYPE (gimple_assign_rhs1 (ssa_def)); > + return type_can_use_memcmp_p (ssa_type); > +} > + > +/* Find the SSA definition and parse it into load_info. > + Use load_info_is_valid to check result validity. */ > + > +static load_info > +load_info_from_ssa (tree ssa) > +{ > + load_info invalid = { NULL, 0, 0, NULL, false }; > + if (TREE_CODE (ssa) != SSA_NAME) > + return invalid; > + gimple *ssa_def = SSA_NAME_DEF_STMT (ssa); > + if (!ssa_def || !is_a <gassign *> (ssa_def)) > + return invalid; > + > + tree ssa_rhs = gimple_assign_rhs1 (ssa_def); > + bool rhs_is_address = false; > + if (TREE_CODE (ssa_rhs) == ADDR_EXPR) > + { > + ssa_rhs = TREE_OPERAND (ssa_rhs, 0); > + rhs_is_address = true; > + } > + > + tree ssa_base; > + widest_int ssa_offset; > + /* COMPONENT_REF and ARRAY_REF are both handled by > + get_addr_base_and_unit_offset, which walks the access chain to > + find the underlying object plus a constant byte offset. > + > + A plain pointer dereference, such as "_1 = *p_2", reaches us as a > + MEM_REF. For a dereference with an embedded byte offset, such as > + "_1 = MEM[(int *)p_2 + 4B]", the MEM_REF itself is the base here; the > + offset is folded into ssa_offset below. */ > + if (TREE_CODE (ssa_rhs) == COMPONENT_REF > + || TREE_CODE (ssa_rhs) == ARRAY_REF) > + { > + poly_int64 ssa_poffset; > + HOST_WIDE_INT ssa_offseti; > + ssa_base = get_addr_base_and_unit_offset (ssa_rhs, &ssa_poffset); > + if (ssa_base == NULL_TREE || !ssa_poffset.is_constant (&ssa_offseti)) > + return invalid; > + ssa_offset = ssa_offseti; > + } > + else if (TREE_CODE (ssa_rhs) == MEM_REF) > + { > + ssa_base = ssa_rhs; > + ssa_offset = 0; > + } > + else > + return invalid; > + > + /* Roll the MEM_REF's byte offset into our local offset and clone the > + MEM_REF with that operand zeroed. Crucially DO NOT mutate the > + original MEM_REF tree in place: GIMPLE shares tree nodes, so the same > + MEM_REF may be referenced by other statements we are not transforming. */ > + if (TREE_CODE (ssa_base) == MEM_REF) > + { > + tree base_tree_offset = TREE_OPERAND (ssa_base, 1); > + if (base_tree_offset != NULL_TREE && !integer_zerop (base_tree_offset)) > + { > + if (TREE_CODE (base_tree_offset) != INTEGER_CST > + || !tree_fits_shwi_p (base_tree_offset)) > + return invalid; > + ssa_offset = wi::add (ssa_offset, tree_to_shwi (base_tree_offset)); > + ssa_base = build2 (MEM_REF, TREE_TYPE (ssa_base), > + TREE_OPERAND (ssa_base, 0), > + build_zero_cst (TREE_TYPE (base_tree_offset))); > + } > + } > + > + tree ssa_type = TREE_TYPE (ssa_rhs); > + tree ssa_size = TYPE_SIZE_UNIT (ssa_type); > + if (ssa_size == NULL_TREE || TREE_CODE (ssa_size) != INTEGER_CST) > + return invalid; > + > + return { ssa_base, ssa_offset, wi::to_widest (ssa_size), > + ssa_def, rhs_is_address }; > +} > + > +/* Phase 1: struct field compare merging. */ > + > +/* Rewrite the load described by *LOAD so SSA_VAR_DEF computes an address. > + For a value load such as "_1 = this->a", build "_24 = &this->a". If > + the original statement already computed an address, still clone it with a > + fresh SSA name because the caller inserts the new statement into another > + block and the old SSA name must keep a single definition. */ > + > +static void > +make_address_load_rhs (load_info *load) > +{ > + /* Even if the load is already an address, use a fresh SSA name so the > + cloned statement can be inserted into a different block. */ > + if (load->is_address) > + { > + tree load_rhs = gimple_assign_rhs1 (load->ssa_var_def); > + tree load_new_ssa = make_ssa_name (TREE_TYPE (load_rhs), NULL); > + gimple *new_stmt = gimple_build_assign (load_new_ssa, load_rhs); > + load->ssa_var_def = new_stmt; > + return; > + } > + tree load_rhs = gimple_assign_rhs1 (load->ssa_var_def); > + tree load_rhs_type = build_pointer_type (TREE_TYPE (load_rhs)); > + > + tree load_new_ssa = make_ssa_name (load_rhs_type, NULL); > + tree load_addr_rhs = build1 (ADDR_EXPR, load_rhs_type, load_rhs); > + gimple *new_stmt = gimple_build_assign (load_new_ssa, load_addr_rhs); > + > + load->ssa_var_def = new_stmt; > + load->is_address = true; > +} > + > +/* Return true if A sorts before B by left-hand-side byte offset. > + Clustering by base object happens before this sort. */ > + > +static bool > +cmp_offset_less_p (const cmp_info &a, const cmp_info &b) > +{ > + return wi::lts_p (a.lhs.offset, b.lhs.offset); > +} > + > +/* Sort comparison descriptors by their left-hand-side byte offset. */ > + > +static void > +sort_cmps_by_offset (vec<cmp_info> &cmps) > +{ > + for (size_t i = 1; i < cmps.length (); ++i) > + { > + cmp_info current = cmps[i]; > + size_t j = i; > + while (j > 0 && cmp_offset_less_p (current, cmps[j - 1])) > + { > + cmps[j] = cmps[j - 1]; > + --j; > + } > + cmps[j] = current; > + } > +} > + > +/* Return true if reading SIZE bytes at byte OFFSET from BASE stays within > + the complete type of BASE. > + Phase 1 widens several scalar field loads into one memcmp. That is > + only valid when the widened read cannot pass the object boundary. > + BASE is either a MEM_REF rooted at a pointer, or a DECL for a > + directly addressed object. Unknown or variable-sized object types > + are rejected. */ > + > +static bool > +merged_access_within_type_p (tree base, const widest_int &offset, > + const widest_int &size) > +{ > + tree pointee_type = NULL_TREE; > + if (TREE_CODE (base) == MEM_REF) > + { > + tree ptr = TREE_OPERAND (base, 0); > + if (POINTER_TYPE_P (TREE_TYPE (ptr))) > + pointee_type = TREE_TYPE (TREE_TYPE (ptr)); > + } > + else if (DECL_P (base)) > + pointee_type = TREE_TYPE (base); > + > + if (!pointee_type || !COMPLETE_TYPE_P (pointee_type)) > + return false; > + > + tree size_tree = TYPE_SIZE_UNIT (pointee_type); > + if (!size_tree || TREE_CODE (size_tree) != INTEGER_CST) > + return false; > + > + if (wi::lts_p (offset, 0) || wi::lts_p (size, 0)) > + return false; > + > + widest_int type_size = wi::to_widest (size_tree); > + return wi::les_p (offset + size, type_size); > +} > + > +/* Cluster comparisons by base object and bytewise-comparability, then > + merge contiguous byte ranges within each cluster. */ > + > +static vec<cmp_info> > +simplify_cmps (vec<cmp_info> &cmps) > +{ > + /* The last cmp's phi_true_val is first propagated to every cmp, > + and a freshly allocated vec is returned. */ > + if (cmps.last ().phi_true_val != NULL_TREE) > + for (size_t i = 0; i < cmps.length () - 1; ++i) > + { > + gcc_assert (cmps[i].phi_true_val == NULL_TREE); > + cmps[i].phi_true_val = cmps.last ().phi_true_val; > + } > + > + vec<vec<cmp_info> > clusters = vNULL; > + clusters.reserve (cmps.length ()); > + > + for (size_t i = 0; i < cmps.length (); ++i) > + { > + bool added_to_cluster = false; > + if (clusters.length () > 0 && cmps[i].can_use_memcmp_p > + && (i == 0 || cmps[i - 1].can_use_memcmp_p)) > + { > + for (unsigned j = clusters.length (); j-- > 0; ) > + { > + vec<cmp_info> *cluster = &clusters[j]; > + if (cluster->is_empty ()) > + break; > + bool same_order > + = (operand_equal_p ((*cluster)[0].lhs.base, cmps[i].lhs.base, > + OEP_ADDRESS_OF) > + && operand_equal_p ((*cluster)[0].rhs.base, cmps[i].rhs.base, > + OEP_ADDRESS_OF)); > + bool swapped_order > + = (operand_equal_p ((*cluster)[0].lhs.base, cmps[i].rhs.base, > + OEP_ADDRESS_OF) > + && operand_equal_p ((*cluster)[0].rhs.base, cmps[i].lhs.base, > + OEP_ADDRESS_OF)); > + if (same_order || swapped_order) > + { > + /* Normalize the cmp to the cluster head's lhs/rhs > + orientation before pushing. */ > + cmp_info entry = cmps[i]; > + if (swapped_order && !same_order) > + std::swap (entry.lhs, entry.rhs); > + cluster->safe_push (entry); > + added_to_cluster = true; > + break; > + } > + } > + } > + if (!added_to_cluster) > + { > + vec<cmp_info> empty = vNULL; > + clusters.quick_push (empty); > + clusters.last ().safe_push (cmps[i]); > + } > + } > + > + vec<cmp_info> result = vNULL; > + result.reserve (cmps.length ()); > + for (size_t j = 0; j < clusters.length (); ++j) > + { > + vec<cmp_info> *cluster = &clusters[j]; > + sort_cmps_by_offset (*cluster); > + > + cmp_info *current = &(*cluster)[0]; > + for (size_t i = 1; i < cluster->length (); ++i) > + { > + cmp_info *next = &(*cluster)[i]; > + bool contig_lhs > + = (current->lhs.offset > + + current->lhs.size > + == next->lhs.offset); > + bool contig_rhs > + = (current->rhs.offset > + + current->rhs.size > + == next->rhs.offset); > + > + /* Even when contiguous, reject the merge if widening the load > + would extend past the dereferenceable bounds of either side's > + underlying object. See merged_access_within_type_p above for > + the rationale. */ > + widest_int new_lhs_size = current->lhs.size > + + next->lhs.size; > + widest_int new_rhs_size = current->rhs.size > + + next->rhs.size; > + bool within_bounds > + = (merged_access_within_type_p > + (current->lhs.base, > + current->lhs.offset, new_lhs_size) > + && merged_access_within_type_p > + (current->rhs.base, > + current->rhs.offset, new_rhs_size)); > + > + if (contig_lhs && contig_rhs && within_bounds) > + { > + current->lhs.size = new_lhs_size; > + current->rhs.size = new_rhs_size; > + } > + else > + { > + if (dump_file && contig_lhs && contig_rhs && !within_bounds) > + fprintf (dump_file, "eqmerge: refusing widening\n"); > + result.safe_push (*current); > + current = next; > + } > + } > + result.quick_push (*current); > + } > + for (size_t j = 0; j < clusters.length (); ++j) > + clusters[j].release (); > + clusters.release (); > + return result; > +} > + > +/* Emit the GIMPLE for a single comparison CMP at the end of BB_CURRENT and > + return its closing GIMPLE_COND. > + > + Two forms are produced depending on whether the operands can be compared > + bytewise (CMP->can_use_memcmp_p). When bytewise comparison is not valid, > + the original value loads are re-emitted under fresh SSA names, so that the > + cloned definitions satisfy the SSA single-definition rule in this block, > + and a direct "lhs == rhs" condition is rebuilt. Otherwise the loads are > + rewritten into address computations by make_address_load_rhs and a memcmp > + over CMP->lhs.size bytes is emitted, with the condition testing > + "memcmp (...) == 0". */ > + > +static gimple * > +apply_cmp_to_bb (basic_block bb_current, cmp_info *cmp) > +{ > + gimple_seq seq = NULL; > + gimple *cond_stmt; > + if (!cmp->can_use_memcmp_p) > + { > + tree lhs_rhs = gimple_assign_rhs1 (cmp->lhs.ssa_var_def); > + tree rhs_rhs = gimple_assign_rhs1 (cmp->rhs.ssa_var_def); > + tree new_lhs_ssa = make_ssa_name (TREE_TYPE (lhs_rhs), NULL); > + tree new_rhs_ssa = make_ssa_name (TREE_TYPE (rhs_rhs), NULL); > + > + cmp->lhs.ssa_var_def = gimple_build_assign (new_lhs_ssa, lhs_rhs); > + cmp->rhs.ssa_var_def = gimple_build_assign (new_rhs_ssa, rhs_rhs); > + > + tree rebuilt = build2 (EQ_EXPR, boolean_type_node, > + new_lhs_ssa, new_rhs_ssa); > + cond_stmt = gimple_build_cond_from_tree (rebuilt, NULL_TREE, NULL_TREE); > + > + gimple_seq_add_stmt (&seq, cmp->lhs.ssa_var_def); > + gimple_seq_add_stmt (&seq, cmp->rhs.ssa_var_def); > + gimple_seq_add_stmt (&seq, cond_stmt); > + } > + else > + { > + make_address_load_rhs (&cmp->lhs); > + make_address_load_rhs (&cmp->rhs); > + gimple *lhs_def = cmp->lhs.ssa_var_def; > + gimple *rhs_def = cmp->rhs.ssa_var_def; > + > + tree memcmp_res = make_ssa_name (integer_type_node, NULL); > + tree memcmp_len = wide_int_to_tree (size_type_node, > + cmp->lhs.size); > + tree memcmp_lhs = gimple_assign_lhs (lhs_def); > + tree memcmp_rhs = gimple_assign_lhs (rhs_def); > + gcall *memcmp_call > + = gimple_build_call (builtin_decl_implicit (BUILT_IN_MEMCMP), 3, > + memcmp_lhs, memcmp_rhs, memcmp_len); > + gimple_call_set_lhs (memcmp_call, memcmp_res); > + > + tree zero = build_int_cst (integer_type_node, 0); > + tree memcmp_cond = build2 (EQ_EXPR, boolean_type_node, memcmp_res, zero); > + cond_stmt = gimple_build_cond_from_tree (memcmp_cond, > + NULL_TREE, NULL_TREE); > + > + gimple_seq_add_stmt (&seq, lhs_def); > + gimple_seq_add_stmt (&seq, rhs_def); > + gimple_seq_add_stmt (&seq, memcmp_call); > + gimple_seq_add_stmt (&seq, cond_stmt); > + } > + > + gimple_stmt_iterator gsi_current = gsi_last_bb (bb_current); > + gsi_insert_seq_before (&gsi_current, seq, GSI_CONTINUE_LINKING); > + return cond_stmt; > +} > + > +/* Append CMP to BB_CURRENT, split the block after the new condition, > + and wire the two outgoing edges for the rebuilt comparison chain. > + > + For intermediate comparisons, equality continues to the split successor > + and inequality goes to BB_PHI. For the final comparison, equality goes > + to BB_PHI and inequality falls through to the split successor; > + apply_cmp_chain later connects the final equality edge to the original > + success destination. */ > + > +static basic_block > +apply_cmp_and_split (basic_block bb_phi, basic_block bb_current, > + cmp_info *cmp, bool final_cmp_p) > +{ > + /* Add address loads, the comparison operation, and condition to > + BB_CURRENT. */ > + gimple *cond_stmt = apply_cmp_to_bb (bb_current, cmp); > + edge e_split = split_block (bb_current, cond_stmt); > + e_split->flags &= ~EDGE_FALLTHRU; > + > + /* For intermediate comparisons, the split successor is the next > + comparison block. For the final comparison, it is the empty block > + reached by the false edge. */ > + e_split->flags |= final_cmp_p ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE; > + > + /* Add flow into the PHI block. */ > + edge e_end = find_edge (bb_current, bb_phi); > + if (e_end != NULL) > + remove_edge (e_end); > + e_end = make_edge (bb_current, bb_phi, > + final_cmp_p ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE); > + > + e_end->probability = profile_probability::even (); > + e_split->probability = e_end->probability.invert (); > + > + return e_split->dest; > +} > + > +/* Starting from DISCOVER_BB, return the normalized comparison blocks in > + the same short-circuit equality chain. > + Blocks are removed from CANDIDATE_CHAIN_BLOCKS as they are consumed. */ > + > +static vec<basic_block> > +discover_cmp_chain_bbs (basic_block discover_bb, > + hash_set<basic_block> &candidate_chain_blocks, > + basic_block bb_phi) > +{ > + if (!comparison_block_p (discover_bb)) > + { > + candidate_chain_blocks.remove (discover_bb); > + return vNULL; > + } > + /* The pred/succ walkers normalize each newly discovered block, but > + discover_bb itself is the entry point and never goes through them. > + Without this, get_cmp_chains_for_phi reads its TRUE/FALSE edges in the > + un-normalized (possibly NE) orientation, which inverts phi_true_val > + and phi_false_val for "if (a != b) return false;" chains. */ > + normalize_bb_condition (discover_bb); > + > + auto get_pred_chain_bb = [&bb_phi, &candidate_chain_blocks] > + (basic_block bb_current) > + { > + candidate_chain_blocks.remove (bb_current); > + /* Only the first element in a comparison chain may contain multiple > + predecessors, so a multi-pred block marks the start of the chain. */ > + if (!single_pred_p (bb_current)) > + return (basic_block) NULL; > + basic_block bb_pred = single_pred (bb_current); > + if (!candidate_chain_blocks.contains (bb_pred)) > + return (basic_block) NULL; > + if (!comparison_block_p (bb_pred)) > + return (basic_block) NULL; > + normalize_bb_condition (bb_pred); > + /* After condition normalization, TRUE continues to BB_CURRENT and > + FALSE reaches BB_PHI. */ > + edge e; > + edge_iterator it; > + FOR_EACH_EDGE (e, it, bb_pred->succs) > + { > + if (e->flags & EDGE_TRUE_VALUE) > + { > + /* There are normally no empty blocks inside a comparison chain, but > + handle them here for robustness. */ > + if (find_succ_ignore_empties (e->dest) != bb_current) > + return (basic_block) NULL; > + } > + else if (e->flags & EDGE_FALSE_VALUE) > + { > + /* The failure edge of each predecessor must reach BB_PHI. */ > + if (find_succ_ignore_empties (e->dest) != bb_phi) > + return (basic_block) NULL; > + } > + else > + return (basic_block) NULL; > + } > + return bb_pred; > + }; > + > + auto get_succ_chain_bb = [&bb_phi, &candidate_chain_blocks] > + (basic_block bb_current) > + { > + candidate_chain_blocks.remove (bb_current); > + basic_block bb_succ = get_true_edge (bb_current->succs)->dest; > + if (!single_pred_p (bb_succ)) > + return (basic_block) NULL; > + if (!candidate_chain_blocks.contains (bb_succ)) > + return (basic_block) NULL; > + if (!comparison_block_p (bb_succ)) > + return (basic_block) NULL; > + normalize_bb_condition (bb_succ); > + > + /* The successor must only have TRUE/FALSE edges, with FALSE reaching > + BB_PHI. */ > + edge e; > + edge_iterator it; > + FOR_EACH_EDGE (e, it, bb_succ->succs) > + { > + if (e->flags & EDGE_FALSE_VALUE) > + { > + if (find_succ_ignore_empties (e->dest) != bb_phi) > + return (basic_block) NULL; > + } > + else if (!(e->flags & EDGE_TRUE_VALUE)) > + return (basic_block) NULL; > + } > + return bb_succ; > + }; > + > + vec<basic_block> chain_bbs = vNULL; > + chain_bbs.reserve (candidate_chain_blocks.elements ()); > + chain_bbs.quick_push (discover_bb); > + /* Discover the chain blocks by following the predecessor edges. */ > + basic_block bb_current = discover_bb; > + while (true) > + { > + bb_current = get_pred_chain_bb (bb_current); > + if (bb_current == NULL) > + break; > + chain_bbs.quick_insert (0, bb_current); > + } > + /* Discover the chain blocks by following the successor edges. */ > + bb_current = discover_bb; > + while (true) > + { > + bb_current = get_succ_chain_bb (bb_current); > + if (bb_current == NULL) > + break; > + chain_bbs.quick_push (bb_current); > + } > + return chain_bbs; > +} > + > +/* Discover comparison chains that feed the result PHI in BB_PHI. */ > + > +static vec<cmp_chain> > +get_cmp_chains_for_phi (basic_block bb_phi, gphi *phi_stmt) > +{ > + unsigned phi_arg_n = gimple_phi_num_args (phi_stmt); > + > + /* The rebuilt comparison chain has boolean success and failure paths. > + Reject the whole PHI when any incoming value is not the integer constant > + zero or one; otherwise merging comparisons could collapse distinct > + results such as mismatch codes into a single value. */ > + for (unsigned i = 0; i < phi_arg_n; ++i) > + { > + tree incoming = gimple_phi_arg_def (phi_stmt, i); > + if (incoming == NULL_TREE > + || TREE_CODE (incoming) != INTEGER_CST > + || (!integer_zerop (incoming) && !integer_onep (incoming))) > + { > + if (dump_file) > + fprintf (dump_file, "eqmerge: skipping non-boolean PHI\n"); > + return vNULL; > + } > + } > + > + /* Candidate blocks that may belong to chains feeding BB_PHI. */ > + hash_set<basic_block> candidate_chain_blocks; > + /* Map each logical incoming edge to the PHI value it contributes. */ > + hash_map<edge, tree> phi_args_map; > + > + for (size_t i = 0; i < phi_arg_n; i++) > + { > + /* Find the basic block this PHI argument logically comes from. */ > + edge bb_incoming_e = find_decision_edge_from_phi_arg (phi_stmt, i); > + if (bb_incoming_e == NULL) > + continue; > + tree incoming = gimple_phi_arg_def (phi_stmt, i); > + phi_args_map.put (bb_incoming_e, incoming); > + candidate_chain_blocks.add (bb_incoming_e->src); > + } > + if (candidate_chain_blocks.is_empty ()) > + return vNULL; > + > + /* Early CFG cleanup tends to merge all the FALSE-edge tails of a > + comparison chain into one shared empty block before the PHI. Expand > + the candidate block set transitively through any empty block we land on, > + so the chain comparison blocks themselves become discoverable. */ > + { > + auto_vec<basic_block> worklist; > + for (auto it = candidate_chain_blocks.begin (); > + it != candidate_chain_blocks.end (); ++it) > + worklist.safe_push (*it); > + while (!worklist.is_empty ()) > + { > + basic_block bb = worklist.pop (); > + if (!empty_block_p (bb)) > + continue; > + edge e; > + edge_iterator ei; > + FOR_EACH_EDGE (e, ei, bb->preds) > + { > + /* hash_set::add returns true if the element was already present. */ > + if (candidate_chain_blocks.add (e->src)) > + continue; > + worklist.safe_push (e->src); > + } > + } > + } > + > + vec<cmp_chain> chains = vNULL; > + chains.reserve (candidate_chain_blocks.elements ()); > + while (!candidate_chain_blocks.is_empty ()) > + { > + /* Start from the lowest-index remaining block for deterministic dumps. > + discover_cmp_chain_bbs removes consumed blocks from > + candidate_chain_blocks. */ > + basic_block discover_bb = NULL; > + for (auto it = candidate_chain_blocks.begin (); > + it != candidate_chain_blocks.end (); ++it) > + if (discover_bb == NULL || (*it)->index < discover_bb->index) > + discover_bb = *it; > + > + vec<basic_block> chain_bbs > + = discover_cmp_chain_bbs (discover_bb, candidate_chain_blocks, bb_phi); > + if (chain_bbs.is_empty ()) > + continue; > + vec<cmp_info> chain_cmps = vNULL; > + chain_cmps.reserve (chain_bbs.length ()); > + bool parse_failed = false; > + for (size_t i = 0; i < chain_bbs.length (); i++) > + { > + cmp_info cmp = parse_cmp_block (chain_bbs[i]); > + if (!cmp_info_is_valid (cmp)) > + { > + parse_failed = true; > + break; > + } > + tree *ptv = phi_args_map.get (get_true_edge (chain_bbs[i]->succs)); > + tree *pfv = phi_args_map.get (get_false_edge (chain_bbs[i]->succs)); > + if (ptv != NULL) > + cmp.phi_true_val = *ptv; > + if (pfv != NULL) > + cmp.phi_false_val = *pfv; > + chain_cmps.quick_push (cmp); > + } > + if (parse_failed) > + { > + chain_cmps.release (); > + chain_bbs.release (); > + continue; > + } > + if (chain_cmps.length () <= 1) > + { > + chain_cmps.release (); > + chain_bbs.release (); > + continue; > + } > + > + /* Refuse to rewrite chains that mix bytewise-comparable fields with > + non-bytewise fields (booleans, pointers, etc.). Such a chain has a > + short-circuit && over a mix of plain field equality and conditional > + sub-expressions like "(!flag || known_eq (a, b))". Even when each > + lowered cmp still matches comparison_block_p, the surrounding CFG > + carries short-circuit branches that the linear rebuild in > + apply_cmp_chain cannot reproduce, so we conservatively bail. */ > + bool all_cmps_can_use_memcmp_p = true; > + for (size_t k = 0; k < chain_cmps.length (); k++) > + if (!chain_cmps[k].can_use_memcmp_p) > + { > + all_cmps_can_use_memcmp_p = false; > + break; > + } > + if (!all_cmps_can_use_memcmp_p) > + { > + if (dump_file) > + fprintf (dump_file, "eqmerge: skipping non-bytewise chain\n"); > + chain_cmps.release (); > + chain_bbs.release (); > + continue; > + } > + > + /* In the usual case, each mismatch edge reaches the PHI directly, so > + the per-comparison lookup above records phi_false_val from the > + comparison false edge. It can also reach the PHI through a > + forwarding block: > + > + cmp0 false --\ > + cmp1 false ----> shared_empty -> bb_phi > + cmp2 false --/ > + > + In that case the PHI argument is keyed by shared_empty->bb_phi, not > + by any comparison block. Follow each comparison false edge to the > + PHI and read the PHI arg from that exact edge; do not use an > + arbitrary edge outside CHAIN_BBS, since another chain may feed the > + same PHI. */ > + for (size_t k = 0; k < chain_cmps.length (); k++) > + if (chain_cmps[k].phi_false_val == NULL_TREE) > + { > + edge false_edge = get_false_edge (chain_bbs[k]->succs); > + edge phi_edge > + = find_edge_to_dest_through_forwarders (false_edge, bb_phi); > + if (phi_edge == NULL) > + { > + parse_failed = true; > + break; > + } > + chain_cmps[k].phi_false_val > + = gimple_phi_arg_def_from_edge (phi_stmt, phi_edge); > + } > + if (parse_failed) > + { > + chain_cmps.release (); > + chain_bbs.release (); > + continue; > + } > + > + cmp_chain chain = { chain_cmps, chain_bbs.last (), vNULL }; > + chain.incoming_edges.reserve (EDGE_COUNT (chain_bbs[0]->preds)); > + edge e; > + edge_iterator it; > + FOR_EACH_EDGE (e, it, chain_bbs[0]->preds) > + chain.incoming_edges.quick_push (e); > + chains.quick_push (chain); > + chain_bbs.release (); > + } > + if (chains.is_empty ()) > + { > + chains.release (); > + return vNULL; > + } > + return chains; > +} > + > +/* Detach the original comparison-chain CFG that feeds BB_PHI and rebuild > + it from CHAIN's (already simplified) cmps. > + > + Before -- one cmp per BB, FALSE edges drain through one shared empty > + tail; for a 4-field defaulted operator== this is N == 4: > + > + +------+ eq +------+ eq +------+ > + preds --->| cmp0 |---->| cmp1 |---->...-->| cmpN |---> success... > + +------+ +------+ +------+ > + | neq | neq | neq > + V V V > + +----------------------------------+ > + | shared empty tail | > + +----------------------------------+ > + | > + V > + bb_phi > + > + After. The N input cmps collapse into K <= N rebuilt comparison blocks, > + with one mcmp per merged cluster. Each block is created empty only as a > + clean CFG splice point; apply_cmp_and_split then inserts the memcmp and > + condition into it: > + > + +-------+ eq +-------+ eq +-------+ > + preds --->| mcmp0 |---->| mcmp1 |---->...-->| mcmpK |---> success... > + +-------+ +-------+ +-------+ > + | neq | neq | neq > + V V V > + +----------------------------------+ > + | empty fallthrough tail |---> bb_phi > + +----------------------------------+ > + > + BB_PHI's PHI args are repointed: the > + success edge gets the chain's phi_true_val, the empty-fallthrough edge > + gets phi_false_val. The original chain blocks become unreachable > + and are reaped by TODO_cleanup_cfg. */ > + > +static void > +apply_cmp_chain (cmp_chain &chain, basic_block bb_phi, tree result_phi_name) > +{ > + basic_block bb_last = chain.last_bb; > + edge old_success_edge = get_true_edge (bb_last->succs); > + basic_block old_success_dest = old_success_edge->dest; > + auto_vec<tree> success_phi_args; > + auto_vec<location_t> success_phi_locations; > + save_phi_args_from_edge (old_success_edge, > + success_phi_args, > + success_phi_locations); > + edge e_to_empty = split_block (bb_last, > + gsi_stmt (gsi_last_bb (bb_last))); > + basic_block bb_empty = e_to_empty->dest; > + remove_edge (e_to_empty); > + > + for (size_t i = 0; i < chain.incoming_edges.length (); ++i) > + redirect_edge_succ (chain.incoming_edges[i], bb_empty); > + > + while (EDGE_COUNT (bb_empty->succs) > 0) > + remove_edge (EDGE_SUCC (bb_empty, 0)); > + > + basic_block bb_last_head = bb_empty, bb_current_head = bb_empty; > + vec<basic_block> new_bbs = vNULL; > + new_bbs.reserve (chain.cmps.length () + 1); > + new_bbs.quick_push (bb_empty); > + for (size_t i = 0; i < chain.cmps.length (); i++) > + { > + bb_last_head = bb_current_head; > + bb_current_head = apply_cmp_and_split > + (bb_phi, bb_current_head, &chain.cmps[i], > + i == chain.cmps.length () - 1); > + new_bbs.quick_push (bb_current_head); > + } > + > + /* Make the last comparison flow into an empty block on inequality, > + which then falls through to BB_PHI. This is not strictly required, > + but preserves the shape of operator== comparison chains for later > + optimization passes. */ > + edge e_rem = find_edge (bb_current_head, bb_phi); > + if (e_rem != NULL) > + remove_edge (e_rem); > + e_rem = find_edge (bb_last_head, bb_phi); > + if (e_rem != NULL) > + remove_edge (e_rem); > + edge e_reattach > + = make_edge (bb_last_head, old_success_dest, EDGE_TRUE_VALUE); > + edge e_fallthru_phi > + = make_edge (bb_current_head, bb_phi, EDGE_FALLTHRU); > + add_saved_phi_args_to_new_edge (old_success_dest, e_reattach, > + success_phi_args, success_phi_locations); > + e_reattach->probability = profile_probability::even (); > + e_fallthru_phi->probability = profile_probability::always (); > + > + /* Adjust PHI node arguments to reflect the new structure. */ > + gphi *phi = find_phi_with_result (bb_phi, result_phi_name); > + gcc_assert (phi != NULL); > + for (size_t i = 0; i < EDGE_COUNT (bb_phi->preds); ++i) > + { > + edge decision_e = find_decision_edge_from_phi_arg (phi, i); > + if (decision_e == NULL) > + continue; > + > + bool from_rebuilt_chain = false; > + for (basic_block bb : new_bbs) > + if (bb == decision_e->src) > + { > + from_rebuilt_chain = true; > + break; > + } > + > + if (decision_e->src == bb_last_head > + && (decision_e->flags & EDGE_TRUE_VALUE)) > + SET_PHI_ARG_DEF (phi, i, chain.cmps.last ().phi_true_val); > + else if (from_rebuilt_chain > + && (decision_e->flags & EDGE_FALSE_VALUE)) > + SET_PHI_ARG_DEF (phi, i, chain.cmps.last ().phi_false_val); > + } > + new_bbs.release (); > +} > + > +/* Phase 1 entry per PHI block. Recognizes short-circuit comparison > + chains whose inequality edges drain to BB_PHI through direct or empty > + forwarding blocks, then runs simplify_cmps to merge contiguous > + bytewise-comparable compares > + sharing a base, and rewrites the CFG via apply_cmp_chain. > + Returns true if any chain was actually shrunk and the IR changed. */ > + > +static bool > +merge_cmp_chains_for_phi (basic_block bb_phi) > +{ > + /* The rewrite updates the comparison result PHI only. Ignore virtual PHIs > + here, but reject blocks with multiple real PHIs because redirecting their > + incoming edges would leave their arguments inconsistent with the rewritten > + control flow. */ > + gphi *phi_stmt = NULL; > + for (gphi_iterator phi_i = gsi_start_phis (bb_phi); !gsi_end_p (phi_i); > + gsi_next (&phi_i)) > + { > + gphi *candidate = *phi_i; > + if (virtual_operand_p (gimple_phi_result (candidate))) > + continue; > + if (phi_stmt != NULL) > + return false; > + phi_stmt = candidate; > + } > + if (phi_stmt == NULL) > + return false; > + > + tree result_phi_name = gimple_phi_result (phi_stmt); > + vec<cmp_chain> chains = get_cmp_chains_for_phi (bb_phi, phi_stmt); > + if (chains.is_empty ()) > + return false; > + > + if (dump_file) > + fprintf (dump_file, "eqmerge: discovered %d chain(s)\n", chains.length ()); > + > + bool changed = false; > + for (size_t i = 0; i < chains.length (); i++) > + { > + size_t orig_ncomparisons = chains[i].cmps.length (); > + vec<cmp_info> orig_cmps = chains[i].cmps; > + chains[i].cmps = simplify_cmps (orig_cmps); > + orig_cmps.release (); > + if (chains[i].cmps.length () >= orig_ncomparisons) > + continue; > + if (dump_file) > + fprintf (dump_file, > + "eqmerge: merged struct comparisons %zu -> %u\n", > + orig_ncomparisons, chains[i].cmps.length ()); > + apply_cmp_chain (chains[i], bb_phi, result_phi_name); > + changed = true; > + } > + for (size_t i = 0; i < chains.length (); i++) > + { > + chains[i].cmps.release (); > + chains[i].incoming_edges.release (); > + } > + chains.release (); > + return changed; > +} > + > +/* Phase 2: equality loop collapsing. */ > + > +/* Parsed pieces of the pointer-walking loop form. The three block > + records name the SSA values that must line up across compare, advance, > + and bound-check blocks before the loop can be replaced by one memcmp. */ > +struct ptr_bound_check > +{ > + basic_block bb; > + tree end_base_ssa; > + tree initial_base_ssa1; > + tree initial_base_ssa2; > + tree next_base_ssa1; > + tree next_base_ssa2; > + tree current_base_ssa1; > + tree current_base_ssa2; > + edge initial_edge; > + edge exit_edge; > + edge continue_edge; > + bool bound_on_second_p; > +}; > + > +struct ptr_compare > +{ > + basic_block bb; > + tree current_base_ssa1; > + tree current_base_ssa2; > + cmp_info cmp; > + edge eq_edge; > + edge neq_edge; > +}; > + > +struct ptr_advance > +{ > + basic_block bb; > + tree current_base_ssa1; > + tree current_base_ssa2; > + tree next_base_ssa1; > + tree next_base_ssa2; > + widest_int advance_bytes; > +}; > + > +struct ptr_cmp_loop > +{ > + ptr_compare bb_compare; > + ptr_advance bb_advance; > + ptr_bound_check bb_bounds; > + basic_block bb_phi; > +}; > + > +/* Make the loop operand that is checked against the end pointer operand #1. > + This lets the rest of the pointer-loop rewrite continue to compute the > + memcmp length as end_base_ssa - initial_base_ssa1. */ > + > +static void > +canonicalize_ptr_cmp_loop_bound (ptr_cmp_loop *loop) > +{ > + if (!loop->bb_bounds.bound_on_second_p) > + return; > + > + load_info load_tmp = loop->bb_compare.cmp.lhs; > + loop->bb_compare.cmp.lhs = loop->bb_compare.cmp.rhs; > + loop->bb_compare.cmp.rhs = load_tmp; > + > + tree tree_tmp = loop->bb_compare.current_base_ssa1; > + loop->bb_compare.current_base_ssa1 = loop->bb_compare.current_base_ssa2; > + loop->bb_compare.current_base_ssa2 = tree_tmp; > + > + tree_tmp = loop->bb_advance.current_base_ssa1; > + loop->bb_advance.current_base_ssa1 = loop->bb_advance.current_base_ssa2; > + loop->bb_advance.current_base_ssa2 = tree_tmp; > + tree_tmp = loop->bb_advance.next_base_ssa1; > + loop->bb_advance.next_base_ssa1 = loop->bb_advance.next_base_ssa2; > + loop->bb_advance.next_base_ssa2 = tree_tmp; > + > + tree_tmp = loop->bb_bounds.initial_base_ssa1; > + loop->bb_bounds.initial_base_ssa1 = loop->bb_bounds.initial_base_ssa2; > + loop->bb_bounds.initial_base_ssa2 = tree_tmp; > + tree_tmp = loop->bb_bounds.next_base_ssa1; > + loop->bb_bounds.next_base_ssa1 = loop->bb_bounds.next_base_ssa2; > + loop->bb_bounds.next_base_ssa2 = tree_tmp; > + tree_tmp = loop->bb_bounds.current_base_ssa1; > + loop->bb_bounds.current_base_ssa1 = loop->bb_bounds.current_base_ssa2; > + loop->bb_bounds.current_base_ssa2 = tree_tmp; > + > + loop->bb_bounds.bound_on_second_p = false; > +} > + > +/* Parsed pieces of a counted ARRAY_REF equality loop. */ > +struct indexed_compare_info > +{ > + basic_block bb; > + tree index; > + tree lhs_ref; > + tree lhs_start_addr; > + tree rhs_ref; > + tree rhs_start_addr; > + tree elem_size; > + tree lhs_base; > + tree rhs_base; > + widest_int lhs_offset; > + widest_int rhs_offset; > + edge eq_edge; > + edge neq_edge; > +}; > + > +struct indexed_bound_info > +{ > + basic_block bb; > + edge entry_edge; > + tree initial_index; > + tree next_index; > + HOST_WIDE_INT bound; > + HOST_WIDE_INT step; > + edge continue_edge; > + edge exit_edge; > +}; > + > +struct indexed_cmp_loop > +{ > + indexed_compare_info compare; > + indexed_bound_info bounds; > + HOST_WIDE_INT first_index; > + HOST_WIDE_INT last_index; > + widest_int length; > +}; > + > +/* Return true if every immediate use of NAME is in one of the three > + recognized loop blocks. */ > + > +static bool > +name_uses_within_blocks_p (tree name, basic_block bb1, basic_block bb2, > + basic_block bb3) > +{ > + imm_use_iterator use_iter; > + gimple *use_stmt; > + FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name) > + { > + if (is_gimple_debug (use_stmt)) > + continue; > + basic_block use_bb = gimple_bb (use_stmt); > + if (use_bb != bb1 && use_bb != bb2 && use_bb != bb3) > + return false; > + } > + return true; > +} > + > +/* Strip a short chain of SSA conversions around an array index. */ > + > +static tree > +strip_index_conversion (tree index) > +{ > + while (TREE_CODE (index) == SSA_NAME) > + { > + gimple *def = SSA_NAME_DEF_STMT (index); > + if (!def || !is_a <gassign *> (def)) > + break; > + gassign *assign = as_a <gassign *> (def); > + if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (assign))) > + break; > + tree rhs = gimple_assign_rhs1 (assign); > + if (TREE_CODE (rhs) != SSA_NAME) > + break; > + index = rhs; > + } > + return index; > +} > + > +/* Parse SSA as an integer ARRAY_REF load indexed by INDEX. Return the > + address of the low-bound element and the object information needed for > + bounds checking. */ > + > +static bool > +parse_indexed_array_load (tree ssa, tree index, tree *start_addr, > + tree *elem_size, tree *base_out, > + widest_int *offset_out) > +{ > + if (TREE_CODE (ssa) != SSA_NAME) > + return false; > + gimple *def = SSA_NAME_DEF_STMT (ssa); > + if (!def || !is_a <gassign *> (def)) > + return false; > + > + tree ref = gimple_assign_rhs1 (def); > + if (TREE_CODE (ref) != ARRAY_REF > + || strip_index_conversion (TREE_OPERAND (ref, 1)) != index) > + return false; > + > + tree element_type = TREE_TYPE (ref); > + if (!type_can_use_memcmp_p (element_type)) > + return false; > + tree size = TYPE_SIZE_UNIT (element_type); > + if (!size || TREE_CODE (size) != INTEGER_CST) > + return false; > + > + tree start_ref = copy_node (ref); > + TREE_OPERAND (start_ref, 1) = array_ref_low_bound (ref); > + poly_int64 poly_offset; > + HOST_WIDE_INT offset; > + tree base = get_addr_base_and_unit_offset (start_ref, &poly_offset); > + if (base == NULL_TREE || !poly_offset.is_constant (&offset)) > + return false; > + > + *start_addr = build_fold_addr_expr (start_ref); > + *elem_size = size; > + *base_out = base; > + *offset_out = offset; > + return true; > +} > + > +/* Return true if REF contains exactly one ARRAY_REF and record it. */ > + > +static bool > +find_indexed_array_ref (tree ref, tree *array_ref_out) > +{ > + *array_ref_out = NULL_TREE; > + while (true) > + { > + if (TREE_CODE (ref) == ARRAY_REF) > + { > + if (*array_ref_out != NULL_TREE) > + return false; > + *array_ref_out = ref; > + } > + > + switch (TREE_CODE (ref)) > + { > + case ARRAY_REF: > + case COMPONENT_REF: > + case MEM_REF: > + ref = TREE_OPERAND (ref, 0); > + break; > + default: > + return *array_ref_out != NULL_TREE; > + } > + } > +} > + > +/* Return true if ADDR_REF starts at the same byte as ARRAY_REF. The indexed > + loop rewrite compares a range beginning at ARRAY_REF; accepting &x[i].a is > + only valid when .a is a zero-offset subobject. */ > + > +static bool > +indexed_array_addr_starts_at_ref_p (tree addr_ref, tree array_ref) > +{ > + while (addr_ref != array_ref) > + { > + switch (TREE_CODE (addr_ref)) > + { > + case COMPONENT_REF: > + { > + tree field = TREE_OPERAND (addr_ref, 1); > + tree byte_offset = component_ref_field_offset (addr_ref); > + if (byte_offset == NULL_TREE > + || !integer_zerop (byte_offset) > + || !integer_zerop (DECL_FIELD_BIT_OFFSET (field))) > + return false; > + addr_ref = TREE_OPERAND (addr_ref, 0); > + break; > + } > + > + default: > + return false; > + } > + } > + > + return true; > +} > + > +/* Parse SSA as the address of an indexed array element or a zero-offset > + subobject of it. Return the element ARRAY_REF and its constant element size. > + The memcmp size check decides whether the compared range covers the full > + element. */ > + > +static bool > +parse_indexed_array_addr (tree ssa, tree *index_out, tree *ref_out, > + tree *elem_size_out) > +{ > + if (TREE_CODE (ssa) != SSA_NAME) > + return false; > + gimple *def = SSA_NAME_DEF_STMT (ssa); > + if (!def || !is_a <gassign *> (def)) > + return false; > + > + /* For example, RHS = &x[i_3].a. */ > + tree rhs = gimple_assign_rhs1 (def); > + if (TREE_CODE (rhs) != ADDR_EXPR) > + return false; > + tree addr_ref = TREE_OPERAND (rhs, 0); > + > + /* REF = x[i_3]. */ > + tree ref; > + if (!find_indexed_array_ref (addr_ref, &ref) > + || !indexed_array_addr_starts_at_ref_p (addr_ref, ref)) > + return false; > + > + /* INDEX = i_3. */ > + tree index = strip_index_conversion (TREE_OPERAND (ref, 1)); > + if (TREE_CODE (index) != SSA_NAME) > + return false; > + > + tree elem_size = TYPE_SIZE_UNIT (TREE_TYPE (ref)); > + if (!elem_size || TREE_CODE (elem_size) != INTEGER_CST) > + return false; > + > + *index_out = index; > + *ref_out = ref; > + *elem_size_out = elem_size; > + return true; > +} > + > +/* Parse the indexed loop comparison block. > + > + The scalar-load form is: > + > + _1 = x[_3]; > + _2 = y[_3]; > + if (_1 == _2) > + goto <bb x>; > + else > + goto <bb y>; > + > + The per-element memcmp form is produced after a full-element struct > + comparison has already been lowered to memcmp: > + > + _1 = &x[_3].a; > + _2 = &y[_3].a; > + _4 = __builtin_memcmp (_1, _2, sizeof (T)); > + if (_4 == 0) > + goto <bb x>; > + else > + goto <bb y>; > + > + Both forms must use the same SSA index on both sides. The true edge is > + the equality edge and the false edge is the inequality edge after the > + condition is normalized. */ > + > +static indexed_compare_info > +parse_indexed_compare (basic_block bb) > +{ > + indexed_compare_info invalid > + = { NULL, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, > + NULL_TREE, NULL_TREE, NULL_TREE, 0, 0, NULL, NULL }; > + indexed_compare_info result = invalid; > + if (EDGE_COUNT (bb->succs) != 2 || !normalize_bb_condition (bb)) > + return invalid; > + > + auto_vec<tree, 2> loads; > + auto_vec<tree, 2> addr_ssas; > + gcall *memcmp_stmt = NULL; > + gcond *cond = NULL; > + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); > + gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (is_gimple_debug (stmt)) > + continue; > + if (gimple_has_volatile_ops (stmt)) > + return invalid; > + if (gassign *assign = safe_dyn_cast <gassign *> (stmt)) > + { > + if (gimple_assign_rhs2 (assign) != NULL_TREE) > + return invalid; > + tree lhs = gimple_assign_lhs (assign); > + tree rhs = gimple_assign_rhs1 (assign); > + if (TREE_CODE (lhs) != SSA_NAME || num_imm_uses (lhs) != 1) > + return invalid; > + if (TREE_CODE (rhs) == ARRAY_REF) > + { > + if (loads.length () == 2) > + return invalid; > + loads.safe_push (lhs); > + } > + else if (TREE_CODE (rhs) == ADDR_EXPR > + && handled_component_p (TREE_OPERAND (rhs, 0))) > + { > + if (addr_ssas.length () == 2) > + return invalid; > + addr_ssas.safe_push (lhs); > + } > + else > + return invalid; > + } > + else if (gcall *call = safe_dyn_cast <gcall *> (stmt)) > + { > + if (memcmp_stmt != NULL > + || (!gimple_call_builtin_p (call, BUILT_IN_MEMCMP) > + && !gimple_call_builtin_p (call, BUILT_IN_MEMCMP_EQ)) > + || gimple_call_num_args (call) != 3 > + || gimple_call_lhs (call) == NULL_TREE > + || num_imm_uses (gimple_call_lhs (call)) != 1) > + return invalid; > + memcmp_stmt = call; > + } > + else if (gcond *candidate = safe_dyn_cast <gcond *> (stmt)) > + { > + if (cond != NULL) > + return invalid; > + cond = candidate; > + } > + else > + return invalid; > + } > + > + if (cond == NULL) > + return invalid; > + > + if (memcmp_stmt != NULL) > + { > + if (!loads.is_empty () || addr_ssas.length () != 2) > + return invalid; > + tree memcmp_arg0 = gimple_call_arg (memcmp_stmt, 0); > + tree memcmp_arg1 = gimple_call_arg (memcmp_stmt, 1); > + if (!((memcmp_arg0 == addr_ssas[0] && memcmp_arg1 == addr_ssas[1]) > + || (memcmp_arg0 == addr_ssas[1] && memcmp_arg1 == addr_ssas[0]))) > + return invalid; > + > + tree memcmp_result = gimple_call_lhs (memcmp_stmt); > + if (((gimple_cond_lhs (cond) == memcmp_result) > + ^ (gimple_cond_rhs (cond) == memcmp_result)) == 0) > + return invalid; > + tree zero = gimple_cond_lhs (cond) == memcmp_result > + ? gimple_cond_rhs (cond) : gimple_cond_lhs (cond); > + if (!integer_zerop (zero)) > + return invalid; > + > + tree lhs_index, rhs_index, lhs_ref, rhs_ref, lhs_size, rhs_size; > + if (!parse_indexed_array_addr (memcmp_arg0, > + &lhs_index, &lhs_ref, &lhs_size) > + || !parse_indexed_array_addr (memcmp_arg1, > + &rhs_index, &rhs_ref, &rhs_size) > + || lhs_index != rhs_index > + || wi::to_widest (lhs_size) != wi::to_widest (rhs_size)) > + return invalid; > + > + tree memcmp_size = gimple_call_arg (memcmp_stmt, 2); > + if (TREE_CODE (memcmp_size) != INTEGER_CST > + || wi::to_widest (memcmp_size) != wi::to_widest (lhs_size)) > + return invalid; > + > + result.bb = bb; > + result.lhs_ref = lhs_ref; > + result.rhs_ref = rhs_ref; > + result.index = lhs_index; > + result.elem_size = lhs_size; > + result.eq_edge = get_true_edge (bb->succs); > + result.neq_edge = get_false_edge (bb->succs); > + return result; > + } > + > + if (!addr_ssas.is_empty () || loads.length () != 2 > + || gimple_cond_lhs (cond) == gimple_cond_rhs (cond) > + || ((gimple_cond_lhs (cond) != loads[0] > + && gimple_cond_lhs (cond) != loads[1]) > + || (gimple_cond_rhs (cond) != loads[0] > + && gimple_cond_rhs (cond) != loads[1]))) > + return invalid; > + > + tree lhs_ref > + = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (loads[0])); > + tree rhs_ref > + = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (loads[1])); > + tree index = strip_index_conversion (TREE_OPERAND (lhs_ref, 1)); > + if (TREE_CODE (index) != SSA_NAME > + || index != strip_index_conversion (TREE_OPERAND (rhs_ref, 1))) > + return invalid; > + > + tree lhs_size, rhs_size; > + if (!parse_indexed_array_load (loads[0], index, &result.lhs_start_addr, > + &lhs_size, &result.lhs_base, > + &result.lhs_offset) > + || !parse_indexed_array_load (loads[1], index, &result.rhs_start_addr, > + &rhs_size, &result.rhs_base, > + &result.rhs_offset) > + || wi::to_widest (lhs_size) != wi::to_widest (rhs_size)) > + return invalid; > + > + result.bb = bb; > + result.lhs_ref = lhs_ref; > + result.rhs_ref = rhs_ref; > + result.index = index; > + result.elem_size = lhs_size; > + result.eq_edge = get_true_edge (bb->succs); > + result.neq_edge = get_false_edge (bb->succs); > + return result; > +} > + > +/* Parse a loop condition comparing INDEX with a constant and normalize its > + bound to the exclusive stop value. */ > + > +static bool > +parse_index_bound (gcond *cond, tree index, HOST_WIDE_INT *bound_out, > + edge *continue_edge, edge *exit_edge) > +{ > + tree lhs = strip_index_conversion (gimple_cond_lhs (cond)); > + tree rhs = strip_index_conversion (gimple_cond_rhs (cond)); > + bool lhs_is_index = lhs == index; > + bool rhs_is_index = rhs == index; > + tree bound; > + if (lhs_is_index && TREE_CODE (rhs) == INTEGER_CST) > + bound = rhs; > + else if (rhs_is_index && TREE_CODE (lhs) == INTEGER_CST) > + bound = lhs; > + else > + return false; > + > + if (!tree_fits_shwi_p (bound)) > + return false; > + > + HOST_WIDE_INT value = tree_to_shwi (bound); > + tree_code code = gimple_cond_code (cond); > + bool continue_on_true; > + if (code == NE_EXPR || code == LT_EXPR || code == GT_EXPR) > + continue_on_true = true; > + else if (code == EQ_EXPR) > + continue_on_true = false; > + else if ((code == LE_EXPR && lhs_is_index) > + || (code == GE_EXPR && rhs_is_index)) > + { > + if (value == HOST_WIDE_INT_MAX) > + return false; > + ++value; > + continue_on_true = true; > + } > + else if ((code == GE_EXPR && lhs_is_index) > + || (code == LE_EXPR && rhs_is_index)) > + { > + if (value == HOST_WIDE_INT_MIN) > + return false; > + --value; > + continue_on_true = true; > + } > + else > + return false; > + > + *bound_out = value; > + *continue_edge = continue_on_true > + ? get_true_edge (gimple_bb (cond)->succs) > + : get_false_edge (gimple_bb (cond)->succs); > + *exit_edge = continue_on_true > + ? get_false_edge (gimple_bb (cond)->succs) > + : get_true_edge (gimple_bb (cond)->succs); > + return true; > +} > + > +/* Parse indexed equality loop bounds for either accepted layout. > + > + Header-tested loops return from BB_COMPARE through BB_ADVANCE before > + testing the bound again: > + > + bb_bound: > + # _1 = PHI <init(entry), _2(bb_advance)> > + if (_1 cmp bound) > + goto bb_compare; > + else > + goto bb_end; > + > + bb_compare: > + if (x[_1] == y[_1]) > + goto bb_advance; > + else > + goto bb_phi; > + > + bb_advance: > + _2 = _1 + step; > + goto bb_bound; > + > + Latch-tested loops compare first and test the advanced index in BB_BOUND: > + > + bb_compare: > + # _1 = PHI <init(entry), _2(bb_bound)> > + if (x[_1] == y[_1]) > + goto bb_bound; > + else > + goto bb_phi; > + > + bb_bound: > + _2 = _1 + step; > + if (_2 cmp bound) > + goto bb_compare; > + else > + goto bb_end; > + > + In the header-tested form BB_BOUND owns the index PHI and bound condition, > + while EQUAL_DEST is the separate advance block reached from BB_COMPARE on > + equality. > + > + In the latch-tested form EQUAL_DEST == BB_BOUND. BB_COMPARE owns the index > + PHI, and BB_BOUND both produces NEXT_INDEX and tests the bound before > + looping back to BB_COMPARE or exiting to BB_END. */ > + > +static indexed_bound_info > +parse_indexed_bounds (basic_block bb_bound, > + const indexed_compare_info &compare, > + basic_block bb_end, basic_block equal_dest) > +{ > + indexed_bound_info invalid > + = { NULL, NULL, NULL_TREE, NULL_TREE, 0, 0, NULL, NULL }; > + indexed_bound_info result = invalid; > + bool latch_form = equal_dest == bb_bound; > + basic_block index_bb = latch_form ? compare.bb : bb_bound; > + basic_block advance_bb = latch_form ? bb_bound : equal_dest; > + > + gcond *cond = NULL; > + gassign *step_stmt = NULL; > + for (gimple_stmt_iterator gsi = gsi_start_bb (bb_bound); !gsi_end_p (gsi); > + gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (is_gimple_debug (stmt)) > + continue; > + if (gassign *assign = safe_dyn_cast <gassign *> (stmt)) > + { > + if (!latch_form || step_stmt != NULL) > + return invalid; > + step_stmt = assign; > + } > + else if (gcond *candidate = safe_dyn_cast <gcond *> (stmt)) > + { > + if (cond != NULL) > + return invalid; > + cond = candidate; > + } > + else > + return invalid; > + } > + > + gphi *index_phi = NULL; > + for (gphi_iterator gpi = gsi_start_phis (index_bb); !gsi_end_p (gpi); > + gsi_next (&gpi)) > + { > + if (gimple_phi_result (*gpi) != compare.index || index_phi != NULL) > + return invalid; > + index_phi = *gpi; > + } > + if (index_phi == NULL || gimple_phi_num_args (index_phi) != 2) > + return invalid; > + > + for (unsigned i = 0; i < 2; ++i) > + { > + edge direct_edge = gimple_phi_arg_edge (index_phi, i); > + edge incoming_edge = find_decision_edge_from_phi_arg (index_phi, i); > + if (incoming_edge != NULL && incoming_edge->src == advance_bb) > + { > + if (result.next_index != NULL_TREE) > + return invalid; > + result.next_index = gimple_phi_arg_def (index_phi, i); > + } > + else > + { > + if (result.initial_index != NULL_TREE) > + return invalid; > + result.initial_index = gimple_phi_arg_def (index_phi, i); > + result.entry_edge = direct_edge; > + } > + } > + if (result.initial_index == NULL_TREE || result.next_index == NULL_TREE > + || result.entry_edge == NULL) > + return invalid; > + > + /* Get the step statement from ADVANCE_BB: > + _2 = _1 + step; or > + _2 = step + _1. */ > + if (!latch_form) > + { > + if (!single_succ_p (advance_bb) > + || find_succ_ignore_empties (single_succ (advance_bb)) != bb_bound) > + return invalid; > + > + for (gimple_stmt_iterator gsi = gsi_start_bb (advance_bb); > + !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (is_gimple_debug (stmt)) > + continue; > + if (step_stmt != NULL) > + return invalid; > + step_stmt = safe_dyn_cast <gassign *> (stmt); > + } > + } > + > + if (!step_stmt || gimple_assign_lhs (step_stmt) != result.next_index > + || gimple_assign_rhs_code (step_stmt) != PLUS_EXPR) > + return invalid; > + > + tree rhs1 = gimple_assign_rhs1 (step_stmt); > + tree rhs2 = gimple_assign_rhs2 (step_stmt); > + if (rhs2 == compare.index && TREE_CODE (rhs1) == INTEGER_CST) > + std::swap (rhs1, rhs2); > + if (rhs1 != compare.index || TREE_CODE (rhs2) != INTEGER_CST > + || !tree_fits_shwi_p (rhs2)) > + return invalid; > + result.step = tree_to_shwi (rhs2); > + > + tree bound_index = latch_form ? result.next_index : compare.index; > + if (cond == NULL > + || !parse_index_bound (cond, bound_index, &result.bound, > + &result.continue_edge, &result.exit_edge) > + || find_succ_ignore_empties (result.continue_edge->dest) != compare.bb > + || find_succ_ignore_empties (result.exit_edge->dest) != bb_end) > + return invalid; > + > + /* Ensure the index variable is only used for this loop. */ > + basic_block extra_block = latch_form ? NULL : advance_bb; > + if (!name_uses_within_blocks_p (compare.index, compare.bb, bb_bound, > + extra_block) > + || !name_uses_within_blocks_p (result.next_index, compare.bb, > + bb_bound, extra_block)) > + return invalid; > + > + result.bb = bb_bound; > + return result; > +} > + > +/* Compute the address of REF[START_INDEX] and its complete-object byte > + offset. Return true if the offset is constant. */ > + > +static bool > +compute_indexed_start_addr_and_offset (tree ref, HOST_WIDE_INT start_index, > + tree *start_addr, tree *base_out, > + widest_int *offset_out) > +{ > + tree start_ref = copy_node (ref); > + tree ref_index = TREE_OPERAND (ref, 1); > + TREE_OPERAND (start_ref, 1) > + = wide_int_to_tree (TREE_TYPE (ref_index), start_index); > + > + poly_int64 poly_offset; > + HOST_WIDE_INT offset; > + tree base = get_addr_base_and_unit_offset (start_ref, &poly_offset); > + if (base == NULL_TREE || !poly_offset.is_constant (&offset)) > + return false; > + > + *start_addr = build_fold_addr_expr (start_ref); > + *base_out = base; > + *offset_out = offset; > + return true; > +} > + > +/* Compute the inclusive memory range and byte length for LOOP. > + > + Return true if the counted loop has a supported unit stride and finite positive length. */ > + > +static bool > +compute_indexed_cmp_loop_range (indexed_cmp_loop *loop) > +{ > + if (TREE_CODE (loop->bounds.initial_index) != INTEGER_CST > + || !tree_fits_shwi_p (loop->bounds.initial_index) > + || !tree_fits_shwi_p (loop->compare.elem_size)) > + return false; > + > + HOST_WIDE_INT initial = tree_to_shwi (loop->bounds.initial_index); > + HOST_WIDE_INT trip_count; > + if (loop->bounds.step == 1) > + { > + if (loop->bounds.bound <= initial) > + return false; > + > + if (initial < 0 && loop->bounds.bound > HOST_WIDE_INT_MAX + initial) > + return false; > + trip_count = loop->bounds.bound - initial; > + loop->first_index = initial; > + loop->last_index = loop->bounds.bound - 1; > + } > + else if (loop->bounds.step == -1) > + { > + if (loop->bounds.bound >= initial) > + return false; > + > + if (loop->bounds.bound < 0 > + && initial > HOST_WIDE_INT_MAX + loop->bounds.bound) > + return false; > + trip_count = initial - loop->bounds.bound; > + loop->first_index = loop->bounds.bound + 1; > + loop->last_index = initial; > + } > + else > + return false; > + > + HOST_WIDE_INT element_size = tree_to_shwi (loop->compare.elem_size); > + if (element_size <= 0 > + || trip_count > HOST_WIDE_INT_MAX / element_size) > + return false; > + loop->length = trip_count * element_size; > + return true; > +} > + > +/* Compute the replacement start addresses and object offsets for LOOP. > + Return true if both sides resolve to constant offsets in complete objects. */ > + > +static bool > +compute_indexed_cmp_loop_start_addresses (indexed_cmp_loop *loop) > +{ > + return (compute_indexed_start_addr_and_offset (loop->compare.lhs_ref, > + loop->first_index, > + &loop->compare.lhs_start_addr, > + &loop->compare.lhs_base, > + &loop->compare.lhs_offset) > + && compute_indexed_start_addr_and_offset (loop->compare.rhs_ref, > + loop->first_index, > + &loop->compare.rhs_start_addr, > + &loop->compare.rhs_base, > + &loop->compare.rhs_offset)); > +} > + > +/* Return false if either replacement start address depends on a pointer > + defined in the loop's entry block. Moving the replacement to that block's > + incoming edge would place the use before its definition. */ > + > +static bool > +indexed_cmp_loop_start_defs_available_p (const indexed_cmp_loop &loop) > +{ > + tree bases[2] = { loop.compare.lhs_base, loop.compare.rhs_base }; > + basic_block entry_bb = loop.bounds.entry_edge->src; > + > + for (tree base : bases) > + { > + if (TREE_CODE (base) != MEM_REF) > + continue; > + tree ptr = TREE_OPERAND (base, 0); > + if (TREE_CODE (ptr) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (ptr)) > + continue; > + gimple *def = SSA_NAME_DEF_STMT (ptr); > + if (def && gimple_bb (def) == entry_bb) > + return false; > + } > + return true; > +} > + > +/* Return true if both complete objects contain the indexed range. */ > + > +static bool > +indexed_cmp_loop_range_safe_p (const indexed_cmp_loop &loop) > +{ > + if (wi::lt_p (loop.compare.lhs_offset, 0, SIGNED) > + || wi::lt_p (loop.compare.rhs_offset, 0, SIGNED)) > + return false; > + return (merged_access_within_type_p (loop.compare.lhs_base, > + loop.compare.lhs_offset, loop.length) > + && merged_access_within_type_p (loop.compare.rhs_base, > + loop.compare.rhs_offset, loop.length)); > +} > + > +/* Return true if DECL is in top-level namespace std, ignoring C++ inline > + namespace wrappers such as libstdc++ version namespace. Do not accept > + arbitrary nested implementation namespaces below std. */ > + > +static bool > +decl_in_std_namespace_p (tree decl) > +{ > + tree context = DECL_CONTEXT (decl); > + while (context != NULL_TREE) > + { > + if (TREE_CODE (context) == TRANSLATION_UNIT_DECL) > + return false; > + if (TREE_CODE (context) != NAMESPACE_DECL) > + return false; > + > + tree name = DECL_NAME (context); > + if (name && strcmp (IDENTIFIER_POINTER (name), "std") == 0) > + { > + /* The class must be a direct member of namespace std, modulo inline > + namespaces. For NAMESPACE_DECL, TREE_LANG_FLAG_0 is the C++ front > + end's DECL_NAMESPACE_INLINE_P. */ > + tree immediate_context = DECL_CONTEXT (decl); > + if (immediate_context != context > + && (TREE_CODE (immediate_context) != NAMESPACE_DECL > + || !TREE_LANG_FLAG_0 (immediate_context))) > + return false; > + > + tree parent = DECL_CONTEXT (context); > + if (parent == NULL_TREE || TREE_CODE (parent) == TRANSLATION_UNIT_DECL) > + return true; > + /* The C++ front end may represent the global namespace as an unnamed > + NAMESPACE_DECL instead of a TRANSLATION_UNIT_DECL. */ > + return (TREE_CODE (parent) == NAMESPACE_DECL > + && DECL_NAME (parent) == NULL_TREE); > + } > + > + /* In C++, TREE_LANG_FLAG_0 on NAMESPACE_DECL is DECL_NAMESPACE_INLINE_P. > + Other nested namespaces are not part of the libstdc++ std::__equal > + name. */ > + if (!TREE_LANG_FLAG_0 (context)) > + return false; > + context = DECL_CONTEXT (context); > + } > + > + return false; > +} > + > +/* Return true if FUNDECL is the libstdc++ std::__equal<>::equal helper used by > + std::equal. The match requires a static member function named "equal" in a > + class named "__equal" directly in namespace std, modulo inline namespaces. */ > + > +static bool > +is_libstdcpp_equal_helper (tree fundecl) > +{ > + if (TREE_CODE (fundecl) != FUNCTION_DECL) > + return false; > + tree fn_name = DECL_NAME (fundecl); > + if (!fn_name || strcmp (IDENTIFIER_POINTER (fn_name), "equal") != 0) > + return false; > + > + /* Static member function: context is the class RECORD_TYPE. */ > + tree ctxt = DECL_CONTEXT (fundecl); > + if (!ctxt || !TYPE_P (ctxt)) > + return false; > + tree ctxt_type_decl = TYPE_NAME (ctxt); > + if (!ctxt_type_decl) > + return false; > + tree ctxt_name = DECL_NAME (ctxt_type_decl); > + if (!ctxt_name > + || strcmp (IDENTIFIER_POINTER (ctxt_name), "__equal") != 0) > + return false; > + if (!decl_in_std_namespace_p (ctxt_type_decl)) > + return false; > + return true; > +} > + > +/* Cross-check that the per-block parsing results stored in LOOP are > + self-consistent and form the expected std::__equal::equal cycle: > + > + +-------------- continue --------------+ > + | | > + V | > + +-------------+ eq +-------------+ ft | > + | bb_compare |------>| bb_advance |-------->+ > + +-------------+ +-------------+ | > + | +------------+ > + | neq | bb_bounds | > + | +------------+ > + V | > + bb_phi <----------- exit ----------------+ > + > + In particular it checks that the SSA pointers used by the comparison, > + advanced by the advance block, and PHI'd in the bounds block are the > + same triplet, that the failure path from compare drains to bb_phi, > + and that the bounds-block continue edge feeds back to compare (with > + any number of empty fallthrough blocks in between). Returns false if > + the structure does not match. */ > + > +static bool > +valid_ptr_cmp_loop_p (const ptr_cmp_loop &loop, basic_block bb_end) > +{ > + if (find_succ_ignore_empties (loop.bb_compare.eq_edge->dest) > + != loop.bb_advance.bb) > + return false; > + if (find_succ_ignore_empties (loop.bb_compare.neq_edge->dest) > + != loop.bb_phi) > + return false; > + if (loop.bb_compare.current_base_ssa1 != loop.bb_advance.current_base_ssa1) > + return false; > + if (loop.bb_compare.current_base_ssa2 != loop.bb_advance.current_base_ssa2) > + return false; > + if (loop.bb_advance.next_base_ssa1 != loop.bb_bounds.next_base_ssa1) > + return false; > + if (loop.bb_advance.next_base_ssa2 != loop.bb_bounds.next_base_ssa2) > + return false; > + if (loop.bb_advance.current_base_ssa1 != loop.bb_bounds.current_base_ssa1) > + return false; > + if (loop.bb_advance.current_base_ssa2 != loop.bb_bounds.current_base_ssa2) > + return false; > + if (find_succ_ignore_empties (loop.bb_bounds.exit_edge->dest) != bb_end) > + return false; > + if (find_succ_ignore_empties (loop.bb_bounds.continue_edge->dest) > + != loop.bb_compare.bb) > + return false; > + if (TREE_CODE (loop.bb_bounds.initial_base_ssa1) != SSA_NAME) > + return false; > + if (TREE_CODE (loop.bb_bounds.initial_base_ssa2) != SSA_NAME) > + return false; > + > + /* The current and advanced iterator names are defined inside the loop and > + become unreachable after replacement. Reject the loop if any such name > + is also used outside. */ > + if (!name_uses_within_blocks_p (loop.bb_bounds.current_base_ssa1, > + loop.bb_compare.bb, > + loop.bb_advance.bb, loop.bb_bounds.bb) > + || !name_uses_within_blocks_p (loop.bb_bounds.current_base_ssa2, > + loop.bb_compare.bb, > + loop.bb_advance.bb, loop.bb_bounds.bb) > + || !name_uses_within_blocks_p (loop.bb_bounds.next_base_ssa1, > + loop.bb_compare.bb, > + loop.bb_advance.bb, loop.bb_bounds.bb) > + || !name_uses_within_blocks_p (loop.bb_bounds.next_base_ssa2, > + loop.bb_compare.bb, > + loop.bb_advance.bb, loop.bb_bounds.bb)) > + return false; > + return true; > +} > + > +/* Return true if LOOP's per-iteration comparison is equivalent to comparing > + the whole element advanced by the iterator step. Phase 2 replaces the > + entire loop with one memcmp from the initial iterator to the end iterator, > + so a comparison of only a subobject (for example T::operator== comparing > + just T::id) is not enough: the range memcmp would also observe members and > + padding that source equality deliberately ignores. */ > + > +static bool > +ptr_cmp_loop_covers_full_step_p (const ptr_cmp_loop &loop) > +{ > + if (!loop.bb_compare.cmp.can_use_memcmp_p) > + return false; > + > + if (wi::ne_p (loop.bb_compare.cmp.lhs.offset, 0) > + || wi::ne_p (loop.bb_compare.cmp.rhs.offset, 0)) > + return false; > + > + widest_int lhs_size = loop.bb_compare.cmp.lhs.size; > + widest_int rhs_size = loop.bb_compare.cmp.rhs.size; > + if (lhs_size != loop.bb_advance.advance_bytes > + || rhs_size != loop.bb_advance.advance_bytes) > + return false; > + > + return true; > +} > + > +/* If TYPE describes a pointer or reference to a complete fixed-size array, > + return the array type. Return NULL_TREE otherwise. */ > + > +static tree > +array_type_from_pointer_or_reference_type (tree type) > +{ > + if (!type) > + return NULL_TREE; > + > + if (TREE_CODE (type) == REFERENCE_TYPE) > + type = TREE_TYPE (type); > + if (POINTER_TYPE_P (type)) > + type = TREE_TYPE (type); > + > + if (TREE_CODE (type) != ARRAY_TYPE || !COMPLETE_TYPE_P (type)) > + return NULL_TREE; > + > + tree size = TYPE_SIZE_UNIT (type); > + if (!size || TREE_CODE (size) != INTEGER_CST) > + return NULL_TREE; > + > + return type; > +} > + > +/* Reduce PTR to an SSA origin plus a constant nonnegative byte offset. > + Given: > + ptr_2 = base_1(D) + 20; > + PTR == ptr_2 produces base_1(D) in *ORIGIN and 20 in *BYTE_OFFSET. > + Return false when it cannot reduce the pointer. */ > + > +static bool > +pointer_origin_and_offset (tree ptr, tree *origin, widest_int *byte_offset) > +{ > + *byte_offset = 0; > + > + while (TREE_CODE (ptr) == SSA_NAME) > + { > + if (SSA_NAME_IS_DEFAULT_DEF (ptr)) > + { > + *origin = ptr; > + return true; > + } > + > + gimple *def = SSA_NAME_DEF_STMT (ptr); > + if (!def || !is_a <gassign *> (def)) > + return false; > + > + gassign *assign = as_a <gassign *> (def); > + if (gimple_assign_rhs_code (assign) != POINTER_PLUS_EXPR) > + return false; > + > + tree step = gimple_assign_rhs2 (assign); > + if (TREE_CODE (step) != INTEGER_CST) > + return false; > + > + widest_int step_bytes = wi::to_widest (step); > + if (wi::lt_p (step_bytes, 0, SIGNED)) > + return false; > + > + *byte_offset = *byte_offset + step_bytes; > + ptr = gimple_assign_rhs1 (assign); > + } > + > + return false; > +} > + > +/* Try to prove that PTR points into a fixed-size array object. Return the > + array type and set *BYTE_OFFSET to PTR byte offset from the start of the > + array. */ > + > +static tree > +array_type_from_pointer_origin (tree ptr, widest_int *byte_offset) > +{ > + tree origin; > + if (!pointer_origin_and_offset (ptr, &origin, byte_offset)) > + return NULL_TREE; > + > + tree var = SSA_NAME_VAR (origin); > + if (var == NULL_TREE) > + return NULL_TREE; > + return array_type_from_pointer_or_reference_type (TREE_TYPE (var)); > +} > + > +/* Return true if a LEN-byte range starting at PTR is contained in the > + complete pointed-to type or in a fixed-size array object that PTR is > + derived from. This is the pointer-loop analogue of > + merged_access_within_type_p: raw pointer parameters do not by themselves > + prove that arbitrary bytes after PTR are dereferenceable, so unknown > + pointee sizes are rejected. */ > + > +static bool > +pointer_within_pointee_type_p (tree ptr, const widest_int &len) > +{ > + if (TREE_CODE (ptr) != SSA_NAME || !POINTER_TYPE_P (TREE_TYPE (ptr))) > + return false; > + > + widest_int byte_offset; > + tree array_type = array_type_from_pointer_origin (ptr, &byte_offset); > + if (array_type != NULL_TREE) > + { > + tree size = TYPE_SIZE_UNIT (array_type); > + return wi::les_p (byte_offset + len, wi::to_widest (size)); > + } > + > + tree pointee_type = TREE_TYPE (TREE_TYPE (ptr)); > + if (!pointee_type || !COMPLETE_TYPE_P (pointee_type)) > + return false; > + > + tree size = TYPE_SIZE_UNIT (pointee_type); > + if (!size || TREE_CODE (size) != INTEGER_CST) > + return false; > + > + return wi::les_p (len, wi::to_widest (size)); > +} > + > +/* Return true if LOOP has a statically provable full pointer range. */ > + > +static bool > +ptr_cmp_loop_static_range_safe_p (const ptr_cmp_loop &loop) > +{ > + tree start_origin, end_origin; > + widest_int start_offset, end_offset; > + if (!pointer_origin_and_offset (loop.bb_bounds.initial_base_ssa1, > + &start_origin, &start_offset) > + || !pointer_origin_and_offset (loop.bb_bounds.end_base_ssa, > + &end_origin, &end_offset) > + || start_origin != end_origin) > + return false; > + > + widest_int len = end_offset - start_offset; > + if (wi::le_p (len, 0, SIGNED)) > + return false; > + > + return (pointer_within_pointee_type_p (loop.bb_bounds.initial_base_ssa1, len) > + && pointer_within_pointee_type_p > + (loop.bb_bounds.initial_base_ssa2, len)); > +} > + > +/* Restructure libstdc++ std::__equal<>::equal after the pointer-loop memcmp > + rewrite so it matches the branch shape used for merged field comparisons: > + > + <bb 2> > + _1 = __last1_6(D) - __first1_7(D); > + if (_1 != 0) > + goto <bb 3>; > + else > + goto <bb 4>; > + > + <bb 3> > + _12 = (long unsigned int) _1; > + _14 = __builtin_memcmp (__first1_7(D), __first2_11(D), _12); > + _13 = _14 == 0; > + > + <bb 4> > + # _4 = PHI <_13(3), 1(2)> > + > + to: > + > + <bb 2> > + _1 = __last1_6(D) - __first1_7(D); > + _12 = (long unsigned int) _1; > + _14 = __builtin_memcmp (__first1_7(D), __first2_11(D), _12); > + if (_14 == 0) > + goto <bb 4>; > + else > + goto <bb 3>; > + > + <bb 3> > + > + <bb 4> > + # _4 = PHI <0(3), 1(2)> > +*/ > + > +static bool > +restructure_memcmp_equal_helper (basic_block bb_phi, gphi *result_phi) > +{ > + tree result_phi_name = gimple_phi_result (result_phi); > + if (gimple_phi_num_args (result_phi) != 2) > + return false; > + basic_block bb_len_test = NULL, bb_compare = NULL; > + tree compare_result = NULL_TREE; > + for (size_t i = 0; i < 2; ++i) > + { > + edge bb_incoming_e = find_decision_edge_from_phi_arg (result_phi, i); > + if (bb_incoming_e == NULL) > + return false; > + tree incoming = gimple_phi_arg_def (result_phi, i); > + if (CONSTANT_CLASS_P (incoming)) > + { > + if (!integer_onep (incoming) || bb_len_test != NULL) > + return false; > + bb_len_test = bb_incoming_e->src; > + } > + else > + { > + if (TREE_CODE (incoming) != SSA_NAME || bb_compare != NULL) > + return false; > + bb_compare = bb_incoming_e->src; > + compare_result = incoming; > + } > + } > + if (bb_len_test == NULL || bb_compare == NULL) > + return false; > + if (!single_pred_p (bb_len_test)) > + return false; > + > + gassign *len_def_stmt = NULL; > + gimple_stmt_iterator gsi = gsi_start_bb (bb_len_test); > + if ((len_def_stmt = safe_dyn_cast <gassign *> (gsi_stmt (gsi)))) > + { > + if (gimple_assign_rhs_code (len_def_stmt) != POINTER_DIFF_EXPR) > + return false; > + if (TREE_CODE (gimple_assign_rhs1 (len_def_stmt)) != SSA_NAME) > + return false; > + if (TREE_CODE (gimple_assign_rhs2 (len_def_stmt)) != SSA_NAME) > + return false; > + if (!SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs1 (len_def_stmt))) > + return false; > + if (!SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs2 (len_def_stmt))) > + return false; > + } > + else > + return false; > + > + gassign *compare_def > + = safe_dyn_cast <gassign *> (SSA_NAME_DEF_STMT (compare_result)); > + if (compare_def == NULL > + || gimple_bb (compare_def) != bb_compare > + || gimple_assign_rhs_code (compare_def) != EQ_EXPR) > + return false; > + > + tree compare_lhs = gimple_assign_rhs1 (compare_def); > + tree compare_rhs = gimple_assign_rhs2 (compare_def); > + tree memcmp_result = NULL_TREE; > + if (TREE_CODE (compare_lhs) == SSA_NAME && integer_zerop (compare_rhs)) > + memcmp_result = compare_lhs; > + else if (TREE_CODE (compare_rhs) == SSA_NAME > + && integer_zerop (compare_lhs)) > + memcmp_result = compare_rhs; > + else > + return false; > + > + gcall *memcmp_stmt > + = safe_dyn_cast <gcall *> (SSA_NAME_DEF_STMT (memcmp_result)); > + if (memcmp_stmt == NULL > + || gimple_bb (memcmp_stmt) != bb_compare > + || (!gimple_call_builtin_p (memcmp_stmt, BUILT_IN_MEMCMP) > + && !gimple_call_builtin_p (memcmp_stmt, BUILT_IN_MEMCMP_EQ))) > + return false; > + > + for (gsi = gsi_start_bb (bb_compare); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (is_gimple_debug (stmt) || gimple_code (stmt) == GIMPLE_PREDICT) > + continue; > + if (stmt == memcmp_stmt || stmt == compare_def) > + continue; > + if (gassign *assign = safe_dyn_cast <gassign *> (stmt)) > + { > + if (gimple_has_side_effects (assign) > + || gimple_could_trap_p (assign) > + || gimple_vdef (assign)) > + return false; > + continue; > + } > + return false; > + } > + > + edge cmp_to_newcmp > + = split_block (bb_compare, gsi_stmt (gsi_last_bb (bb_compare))); > + basic_block bb_new_compare = cmp_to_newcmp->dest; > + > + tree len_def_end = gimple_assign_rhs1 (len_def_stmt); > + tree len_def_start = gimple_assign_rhs2 (len_def_stmt); > + tree new_len_ssa = make_ssa_name (ptrdiff_type_node, NULL); > + tree new_len_cast_ssa = make_ssa_name (size_type_node, NULL); > + > + tree memcmp_arg0 = gimple_call_arg (memcmp_stmt, 0); > + tree memcmp_arg1 = gimple_call_arg (memcmp_stmt, 1); > + tree new_memcmp_ssa = make_ssa_name (integer_type_node, NULL); > + > + gimple *new_len_def > + = gimple_build_assign (new_len_ssa, POINTER_DIFF_EXPR, > + len_def_end, len_def_start); > + gimple *new_len_cast > + = gimple_build_assign (new_len_cast_ssa, > + fold_convert (size_type_node, new_len_ssa)); > + gcall *new_memcmp > + = gimple_build_call (builtin_decl_implicit (BUILT_IN_MEMCMP), 3, > + memcmp_arg0, memcmp_arg1, new_len_cast_ssa); > + gimple_call_set_lhs (new_memcmp, new_memcmp_ssa); > + tree new_cond_tree = build2 (EQ_EXPR, boolean_type_node, > + new_memcmp_ssa, > + build_zero_cst (integer_type_node)); > + gimple *new_cond = gimple_build_cond_from_tree (new_cond_tree, > + NULL_TREE, NULL_TREE); > + > + gsi = gsi_last_bb (bb_new_compare); > + gsi_insert_after (&gsi, new_len_def, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, new_len_cast, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, new_memcmp, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, new_cond, GSI_CONTINUE_LINKING); > + > + redirect_edge_succ (find_edge (single_pred (bb_len_test), bb_len_test), > + bb_new_compare); > + if (find_edge (bb_new_compare, bb_phi)) > + remove_edge (find_edge (bb_new_compare, bb_phi)); > + > + edge new_cmp_to_empty = split_block (bb_new_compare, > + gsi_stmt > + (gsi_last_bb (bb_new_compare))); > + new_cmp_to_empty->flags &= ~EDGE_FALLTHRU; > + new_cmp_to_empty->flags |= EDGE_FALSE_VALUE; > + new_cmp_to_empty->probability = profile_probability::even (); > + > + basic_block bb_new_empty = new_cmp_to_empty->dest; > + make_edge (bb_new_compare, bb_phi, EDGE_TRUE_VALUE)->probability > + = profile_probability::even (); > + make_edge (bb_new_empty, bb_phi, EDGE_FALLTHRU)->probability > + = profile_probability::always (); > + > + gphi *phi = find_phi_with_result (bb_phi, result_phi_name); > + gcc_assert (phi != NULL); > + tree phi_arg_type = TREE_TYPE (gimple_phi_result (phi)); > + for (size_t i = 0; i < EDGE_COUNT (bb_phi->preds); ++i) > + { > + edge e_bb = gimple_phi_arg_edge (phi, i); > + if (e_bb->src == bb_new_compare) > + SET_PHI_ARG_DEF (phi, i, build_int_cst (phi_arg_type, 1)); > + else if (e_bb->src == bb_new_empty) > + SET_PHI_ARG_DEF (phi, i, build_int_cst (phi_arg_type, 0)); > + } > + if (dump_file) > + fprintf (dump_file, "eqmerge: restructured equality helper\n"); > + return true; > +} > + > +/* Parse the pointer equality loop bound-check block: > + > + bb_bound: > + # p_2 = PHI <x_7(D)(entry), p_14(bb_advance)> > + # q_3 = PHI <y_8(D)(entry), q_15(bb_advance)> > + if (p_2 != end_10(D)) > + goto bb_compare; > + else > + goto bb_phi; > + > + bb_advance: > + p_14 = p_2 + 4; > + q_15 = q_3 + 4; > + goto bb_bound; > + > + ADVANCE identifies the PHI latch values. The other PHI argument is the > + initial pointer, and its common incoming edge is recorded as the point at > + which to insert the loop replacement. */ > + > +static ptr_bound_check > +parse_ptr_bound_check (basic_block bb, const ptr_advance &advance) > +{ > + ptr_bound_check invalid > + = { NULL, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, > + NULL_TREE, NULL_TREE, NULL, NULL, NULL, false }; > + ptr_bound_check bb_bounds = invalid; > + bb_bounds.bb = bb; > + > + for (gphi_iterator phi_i = gsi_start_phis (bb); !gsi_end_p (phi_i); gsi_next (&phi_i)) > + { > + gphi *phi_stmt = *phi_i; > + if (gimple_phi_num_args (phi_stmt) != 2) > + return invalid; > + tree current_base = gimple_phi_result (phi_stmt); > + tree expected_next; > + unsigned pointer_i; > + if (current_base == advance.current_base_ssa1) > + { > + expected_next = advance.next_base_ssa1; > + pointer_i = 0; > + } > + else if (current_base == advance.current_base_ssa2) > + { > + expected_next = advance.next_base_ssa2; > + pointer_i = 1; > + } > + else > + return invalid; > + > + size_t latch_idx > + = gimple_phi_arg_def (phi_stmt, 0) == expected_next ? 0 : 1; > + if (gimple_phi_arg_def (phi_stmt, latch_idx) != expected_next) > + return invalid; > + size_t initial_idx = 1 - latch_idx; > + edge latch_edge = find_decision_edge_from_phi_arg (phi_stmt, latch_idx); > + if (!latch_edge || latch_edge->src != advance.bb) > + return invalid; > + > + edge initial_edge = gimple_phi_arg_edge (phi_stmt, initial_idx); > + if (bb_bounds.initial_edge == NULL) > + bb_bounds.initial_edge = initial_edge; > + else if (bb_bounds.initial_edge != initial_edge) > + return invalid; > + > + tree initial_base = gimple_phi_arg_def (phi_stmt, initial_idx); > + tree next_base = gimple_phi_arg_def (phi_stmt, latch_idx); > + > + if (pointer_i == 0 && bb_bounds.current_base_ssa1 == NULL_TREE) > + { > + bb_bounds.current_base_ssa1 = current_base; > + bb_bounds.next_base_ssa1 = next_base; > + bb_bounds.initial_base_ssa1 = initial_base; > + } > + else if (pointer_i == 1 && bb_bounds.current_base_ssa2 == NULL_TREE) > + { > + bb_bounds.current_base_ssa2 = current_base; > + bb_bounds.next_base_ssa2 = next_base; > + bb_bounds.initial_base_ssa2 = initial_base; > + } > + else > + return invalid; > + } > + > + if (bb_bounds.current_base_ssa1 == NULL_TREE > + || bb_bounds.current_base_ssa2 == NULL_TREE) > + return invalid; > + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); > + gsi_next (&gsi)) > + { > + gimple *g = gsi_stmt (gsi); > + if (is_gimple_debug (g)) > + continue; > + gcond *cond = safe_dyn_cast <gcond *> (g); > + if (!cond) > + return invalid; > + if (!normalize_bb_condition (bb_bounds.bb, NE_EXPR)) > + return invalid; > + tree cond_lhs = gimple_cond_lhs (cond); > + tree cond_rhs = gimple_cond_rhs (cond); > + bool uses_first = (cond_lhs == bb_bounds.current_base_ssa1 > + || cond_rhs == bb_bounds.current_base_ssa1); > + bool uses_second = (cond_lhs == bb_bounds.current_base_ssa2 > + || cond_rhs == bb_bounds.current_base_ssa2); > + if (uses_first == uses_second) > + return invalid; > + > + /* The bound may be checked against either walked pointer. Record the > + orientation here and canonicalize the bounded iterator to slot 1 after > + the full loop has been parsed. */ > + tree bounded_base = uses_first ? bb_bounds.current_base_ssa1 > + : bb_bounds.current_base_ssa2; > + bb_bounds.end_base_ssa > + = (cond_lhs != bounded_base) ? cond_lhs : cond_rhs; > + bb_bounds.bound_on_second_p = uses_second; > + bb_bounds.continue_edge = get_true_edge (bb_bounds.bb->succs); > + bb_bounds.exit_edge = get_false_edge (bb_bounds.bb->succs); > + } > + return bb_bounds; > +} > + > +/* Parse the pointer equality loop comparison block: > + > + _12 = __first1_2->a; > + _17 = __first2_3->a; > + if (_12 == _17) > + goto <bb x>; > + else > + goto <bb y>; */ > + > +static ptr_compare > +parse_ptr_compare (basic_block bb, bool allow_phi = false) > +{ > + ptr_compare invalid > + = { NULL, NULL_TREE, NULL_TREE, > + { { NULL, 0, 0, NULL, false }, > + { NULL, 0, 0, NULL, false }, > + false, NULL_TREE, NULL_TREE }, > + NULL, NULL }; > + ptr_compare bb_compare = invalid; > + bb_compare.bb = bb; > + if (!comparison_block_p (bb, allow_phi)) > + return invalid; > + > + bb_compare.cmp = parse_cmp_block (bb); > + if (!load_info_is_valid (bb_compare.cmp.lhs) > + || !load_info_is_valid (bb_compare.cmp.rhs)) > + return invalid; > + > + bb_compare.current_base_ssa1 = bb_compare.cmp.lhs.base; > + bb_compare.current_base_ssa2 = bb_compare.cmp.rhs.base; > + if (TREE_CODE (bb_compare.current_base_ssa1) != MEM_REF > + || TREE_CODE (bb_compare.current_base_ssa2) != MEM_REF) > + return invalid; > + > + if (!normalize_bb_condition (bb)) > + return invalid; > + bb_compare.eq_edge = get_true_edge (bb_compare.bb->succs); > + bb_compare.neq_edge = get_false_edge (bb_compare.bb->succs); > + bb_compare.current_base_ssa1 = TREE_OPERAND (bb_compare.current_base_ssa1, 0); > + bb_compare.current_base_ssa2 = TREE_OPERAND (bb_compare.current_base_ssa2, 0); > + return bb_compare; > +} > + > +/* Parse the pointer equality loop pointer-advance block: > + > + __first1_14 = __first1_2 + 4; > + __first2_15 = __first2_3 + 4; > + goto <bb x>; */ > + > +static ptr_advance > +parse_ptr_advance (basic_block bb, bool allow_cond = false) > +{ > + ptr_advance invalid > + = { NULL, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, 0 }; > + ptr_advance bb_advance = invalid; > + bb_advance.bb = bb; > + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); > + gsi_next (&gsi)) > + { > + gimple *g = gsi_stmt (gsi); > + if (is_gimple_debug (g)) > + continue; > + /* In the latch (do-while) form the advance shares its block with the > + loop-bound test, so tolerate a single trailing condition. */ > + if (allow_cond && safe_dyn_cast <gcond *> (g)) > + continue; > + gassign *stmt = safe_dyn_cast <gassign *> (g); > + if (!stmt) > + return invalid; > + > + /* A range memcmp needs a fixed byte stride. Check the statement shape > + before converting the step to widest_int, since a POINTER_PLUS_EXPR may > + use an SSA name for a runtime stride. */ > + if (gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR > + || gimple_assign_rhs3 (stmt) != NULL_TREE) > + return invalid; > + > + tree next_base = gimple_assign_lhs (stmt); > + tree current_base = gimple_assign_rhs1 (stmt); > + tree advance_bytes_cst = gimple_assign_rhs2 (stmt); > + if (current_base == NULL_TREE > + || TREE_CODE (advance_bytes_cst) != INTEGER_CST) > + return invalid; > + widest_int advance_bytes = wi::to_widest (advance_bytes_cst); > + if (bb_advance.current_base_ssa1 == NULL_TREE) > + { > + bb_advance.current_base_ssa1 = current_base; > + bb_advance.next_base_ssa1 = next_base; > + bb_advance.advance_bytes = advance_bytes; > + } > + else if (bb_advance.current_base_ssa2 == NULL_TREE) > + { > + if (bb_advance.advance_bytes != advance_bytes) > + return invalid; > + bb_advance.current_base_ssa2 = current_base; > + bb_advance.next_base_ssa2 = next_base; > + } > + else > + return invalid; > + } > + if (bb_advance.current_base_ssa1 == NULL_TREE > + || bb_advance.current_base_ssa2 == NULL_TREE) > + return invalid; > + return bb_advance; > +} > + > +/* Parse the increment-and-test latch form of a pointer equality loop: > + > + bb_compare: > + # __first1_2 = PHI <__first1_7 (D) (entry), __first1_14 (bb_latch)> > + # __first2_3 = PHI <__first2_8 (D) (entry), __first2_15 (bb_latch)> > + _12 = __first1_2->a; > + _17 = __first2_3->a; > + if (_12 == _17) > + goto bb_latch; > + else > + goto bb_phi; > + > + bb_latch: > + __first1_14 = __first1_2 + 4; > + __first2_15 = __first2_3 + 4; > + if (__first1_14 != __last1_10 (D)) > + goto bb_compare; > + else > + goto bb_end; > + > + Here the iterator PHIs live in BB_COMPARE and the advance is fused with the > + bound test in BB_LATCH, so the loop bound compares the advanced pointer. > + ADVANCE names the fused POINTER_PLUS results. This is the pointer analogue > + of the indexed latch form. */ > + > +static ptr_bound_check > +parse_ptr_latch (basic_block bb_latch, const ptr_advance &advance, > + basic_block bb_compare) > +{ > + ptr_bound_check invalid > + = { NULL, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE, > + NULL_TREE, NULL_TREE, NULL, NULL, NULL, false }; > + ptr_bound_check bb_bounds = invalid; > + bb_bounds.bb = bb_latch; > + > + /* The iterator PHIs are in the comparison block for this form. */ > + for (gphi_iterator phi_i = gsi_start_phis (bb_compare); !gsi_end_p (phi_i); > + gsi_next (&phi_i)) > + { > + gphi *phi_stmt = *phi_i; > + if (gimple_phi_num_args (phi_stmt) != 2) > + return invalid; > + tree current_base = gimple_phi_result (phi_stmt); > + tree expected_next; > + unsigned pointer_i; > + if (current_base == advance.current_base_ssa1) > + { > + expected_next = advance.next_base_ssa1; > + pointer_i = 0; > + } > + else if (current_base == advance.current_base_ssa2) > + { > + expected_next = advance.next_base_ssa2; > + pointer_i = 1; > + } > + else > + return invalid; > + > + size_t latch_idx > + = gimple_phi_arg_def (phi_stmt, 0) == expected_next ? 0 : 1; > + if (gimple_phi_arg_def (phi_stmt, latch_idx) != expected_next) > + return invalid; > + size_t initial_idx = 1 - latch_idx; > + edge latch_edge = find_decision_edge_from_phi_arg (phi_stmt, latch_idx); > + if (!latch_edge || latch_edge->src != bb_latch) > + return invalid; > + > + edge initial_edge = gimple_phi_arg_edge (phi_stmt, initial_idx); > + if (bb_bounds.initial_edge == NULL) > + bb_bounds.initial_edge = initial_edge; > + else if (bb_bounds.initial_edge != initial_edge) > + return invalid; > + > + tree initial_base = gimple_phi_arg_def (phi_stmt, initial_idx); > + tree next_base = gimple_phi_arg_def (phi_stmt, latch_idx); > + > + if (pointer_i == 0 && bb_bounds.current_base_ssa1 == NULL_TREE) > + { > + bb_bounds.current_base_ssa1 = current_base; > + bb_bounds.next_base_ssa1 = next_base; > + bb_bounds.initial_base_ssa1 = initial_base; > + } > + else if (pointer_i == 1 && bb_bounds.current_base_ssa2 == NULL_TREE) > + { > + bb_bounds.current_base_ssa2 = current_base; > + bb_bounds.next_base_ssa2 = next_base; > + bb_bounds.initial_base_ssa2 = initial_base; > + } > + else > + return invalid; > + } > + > + if (bb_bounds.current_base_ssa1 == NULL_TREE > + || bb_bounds.current_base_ssa2 == NULL_TREE) > + return invalid; > + > + /* The bound test in BB_LATCH compares the advanced pointer against the end > + pointer. */ > + if (!normalize_bb_condition (bb_latch, NE_EXPR)) > + return invalid; > + gcond *cond = safe_dyn_cast <gcond *> (gsi_stmt (gsi_last_bb (bb_latch))); > + if (!cond) > + return invalid; > + tree cond_lhs = gimple_cond_lhs (cond); > + tree cond_rhs = gimple_cond_rhs (cond); > + bool uses_first = (cond_lhs == bb_bounds.next_base_ssa1 > + || cond_rhs == bb_bounds.next_base_ssa1); > + bool uses_second = (cond_lhs == bb_bounds.next_base_ssa2 > + || cond_rhs == bb_bounds.next_base_ssa2); > + if (uses_first == uses_second) > + return invalid; > + > + /* The bound may be checked against either walked pointer. Record the > + orientation here and canonicalize the bounded iterator to slot 1 after > + the full loop has been parsed. */ > + tree bounded_base = uses_first ? bb_bounds.next_base_ssa1 > + : bb_bounds.next_base_ssa2; > + bb_bounds.end_base_ssa > + = (cond_lhs != bounded_base) ? cond_lhs : cond_rhs; > + bb_bounds.bound_on_second_p = uses_second; > + bb_bounds.continue_edge = get_true_edge (bb_latch->succs); > + bb_bounds.exit_edge = get_false_edge (bb_latch->succs); > + return bb_bounds; > +} > + > +/* Try to collapse a pointer-walking equality loop feeding BB_PHI. > + > + The accepted loop has one comparison block, BB_COMPARE, one pointer-advance > + block, BB_ADVANCE, and one bounds block, BB_BOUND_CHECK. The comparison > + must cover exactly the iterator step, starting at offset zero, so replacing > + all iterations with one memcmp observes only the bytes source equality > + already observes. > + > + Two loop layouts are accepted, mirroring the indexed-loop parser. In the > + header-tested form BB_BOUND owns the iterator PHIs and the bound test, > + with a separate advance block on the equality path. In the latch-tested > + (do-while) form the iterator PHIs live in BB_COMPARE and the advance is > + fused with the bound test in BB_BOUND. BB_END is the block the loop's > + all-equal exit reaches. > + > + Return true if the loop parses into *LOOP. The caller applies the > + static-range safety proof separately. */ > + > +static bool > +parse_ptr_cmp_loop (basic_block bb_compare, basic_block bb_bound, > + basic_block bb_phi, basic_block bb_end, ptr_cmp_loop *loop) > +{ > + if (bb_bound == NULL || EDGE_COUNT (bb_bound->succs) != 2 > + || !normalize_bb_condition (bb_bound, NE_EXPR)) > + return false; > + > + if (find_succ_ignore_empties (get_false_edge (bb_bound->succs)->dest) > + != bb_end) > + return false; > + > + /* parse_ptr_compare validates the comparison block (allowing PHIs, since in > + the latch form the block owns the iterator PHIs). */ > + loop->bb_phi = bb_phi; > + loop->bb_compare = parse_ptr_compare (bb_compare, true); > + if (loop->bb_compare.bb == NULL) > + return false; > + > + basic_block equal_dest > + = find_succ_ignore_empties (loop->bb_compare.eq_edge->dest); > + if (equal_dest == bb_bound) > + { > + /* Latch-tested (do-while) form: advance and bound test are fused in > + BB_BOUND and the iterator PHIs are in BB_COMPARE. */ > + loop->bb_advance = parse_ptr_advance (bb_bound, true); > + if (loop->bb_advance.bb == NULL) > + return false; > + loop->bb_bounds > + = parse_ptr_latch (bb_bound, loop->bb_advance, bb_compare); > + if (loop->bb_bounds.bb == NULL) > + return false; > + } > + else > + { > + /* Header-tested form: BB_BOUND owns the PHIs and the bound test, with > + a separate advance block on the equality path. */ > + loop->bb_advance = parse_ptr_advance (equal_dest); > + if (loop->bb_advance.bb == NULL) > + return false; > + loop->bb_bounds > + = parse_ptr_bound_check (bb_bound, loop->bb_advance); > + if (loop->bb_bounds.bb == NULL) > + return false; > + } > + > + canonicalize_ptr_cmp_loop_bound (loop); > + > + return (valid_ptr_cmp_loop_p (*loop, bb_end) > + && ptr_cmp_loop_covers_full_step_p (*loop)); > +} > + > + > +/* Return true if LOOP's replacement byte length is statically known. */ > + > +static bool > +ptr_cmp_loop_static_length_p (const ptr_cmp_loop &loop, widest_int *length) > +{ > + tree start_origin, end_origin; > + widest_int start_offset, end_offset; > + if (!pointer_origin_and_offset (loop.bb_bounds.initial_base_ssa1, > + &start_origin, &start_offset) > + || !pointer_origin_and_offset (loop.bb_bounds.end_base_ssa, > + &end_origin, &end_offset) > + || start_origin != end_origin) > + return false; > + > + *length = end_offset - start_offset; > + return wi::gt_p (*length, 0, SIGNED); > +} > + > +/* Emit one memcmp block per pointer loop in source order. > + > + Each loop is rewritten in place at its OWN entry edge > + (LOOP.bb_bounds.initial_edge), so a loop's initial iterator SSA, which may be > + defined in a block between loops, is always available at the insertion point. > + For a non-final loop the "all equal" edge continues to that loop's original > + success destination, which flows into the next loop; the final loop's "all > + equal" edge feeds BB_PHI with TRUE_VALUE. Every mismatch edge feeds BB_PHI > + with FALSE_VALUE. */ > + > +static bool > +apply_ptr_cmp_loop (ptr_cmp_loop &loop, basic_block bb_phi, tree result_phi_name, > + tree false_value, tree true_value, bool require_static_range_p) > +{ > + if (require_static_range_p && !ptr_cmp_loop_static_range_safe_p (loop)) > + return false; > + > + /* The block reached when this loop finds every element equal. For a > + non-terminal loop this leads into the next loop's entry region; a terminal > + loop's all-equal exit reaches BB_PHI directly. Capture it before mutating > + the CFG. */ > + basic_block equal_dest = loop.bb_bounds.exit_edge->dest; > + bool terminal = (find_succ_ignore_empties (equal_dest) == bb_phi); > + > + /* Rewrite at this loop's own entry edge so its start pointers are in > + scope. */ > + basic_block rewrite_bb = split_edge (loop.bb_bounds.initial_edge); > + while (EDGE_COUNT (rewrite_bb->succs) > 0) > + remove_edge (EDGE_SUCC (rewrite_bb, 0)); > + > + gimple_stmt_iterator gsi = gsi_last_bb (rewrite_bb); > + widest_int static_length; > + tree memcmp_length; > + if (ptr_cmp_loop_static_length_p (loop, &static_length)) > + memcmp_length = wide_int_to_tree (size_type_node, static_length); > + else > + { > + tree length = make_ssa_name (ptrdiff_type_node, NULL); > + gimple *length_stmt > + = gimple_build_assign (length, POINTER_DIFF_EXPR, > + loop.bb_bounds.end_base_ssa, > + loop.bb_bounds.initial_base_ssa1); > + gsi_insert_after (&gsi, length_stmt, GSI_CONTINUE_LINKING); > + > + memcmp_length = make_ssa_name (size_type_node, NULL); > + gimple *length_cast > + = gimple_build_assign (memcmp_length, > + fold_convert (size_type_node, length)); > + gsi_insert_after (&gsi, length_cast, GSI_CONTINUE_LINKING); > + } > + > + tree memcmp_result = make_ssa_name (integer_type_node, NULL); > + gcall *memcmp_call > + = gimple_build_call (builtin_decl_implicit (BUILT_IN_MEMCMP), 3, > + loop.bb_bounds.initial_base_ssa1, > + loop.bb_bounds.initial_base_ssa2, > + memcmp_length); > + gimple_call_set_lhs (memcmp_call, memcmp_result); > + gimple *memcmp_cond > + = gimple_build_cond_from_tree > + (build2 (EQ_EXPR, boolean_type_node, memcmp_result, > + build_zero_cst (integer_type_node)), > + NULL_TREE, NULL_TREE); > + gsi_insert_after (&gsi, memcmp_call, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, memcmp_cond, GSI_CONTINUE_LINKING); > + > + if (terminal) > + { > + /* Preserve the operator== shape: mismatch drains through an empty > + block that falls through to BB_PHI. */ > + edge split = split_block (rewrite_bb, memcmp_cond); > + basic_block next_bb = split->dest; > + remove_edge (split); > + > + edge true_edge = make_edge (rewrite_bb, bb_phi, EDGE_TRUE_VALUE); > + true_edge->probability = profile_probability::even (); > + make_edge (rewrite_bb, next_bb, EDGE_FALSE_VALUE)->probability > + = profile_probability::even (); > + edge false_edge = make_edge (next_bb, bb_phi, EDGE_FALLTHRU); > + false_edge->probability = profile_probability::always (); > + gphi *phi = find_phi_with_result (bb_phi, result_phi_name); > + gcc_assert (phi != NULL); > + add_phi_arg (phi, true_value, true_edge, UNKNOWN_LOCATION); > + add_phi_arg (phi, false_value, false_edge, UNKNOWN_LOCATION); > + } > + else > + { > + /* All equal: continue to this loop's original success destination, > + which enters the next loop. Mismatch: go to BB_PHI. */ > + edge true_edge = make_edge (rewrite_bb, equal_dest, EDGE_TRUE_VALUE); > + true_edge->probability = profile_probability::even (); > + copy_phi_args_to_new_edge (loop.bb_bounds.exit_edge, true_edge); > + edge false_edge = make_edge (rewrite_bb, bb_phi, EDGE_FALSE_VALUE); > + false_edge->probability = profile_probability::even (); > + gphi *phi = find_phi_with_result (bb_phi, result_phi_name); > + gcc_assert (phi != NULL); > + add_phi_arg (phi, false_value, false_edge, UNKNOWN_LOCATION); > + } > + > + if (dump_file) > + fprintf (dump_file, "eqmerge: unrolled pointer loop\n"); > + return true; > +} > + > + > +/* Collapse equality loops feeding the result PHI in BB_PHI into memcmp calls. > + > + The result PHI has one success argument (integer 1) and one or more failure > + arguments (integer 0). Each failure argument's decision edge is the mismatch > + edge of one equality loop; because that edge fully identifies the loop, every > + loop feeding BB_PHI is discovered and rewritten independently -- indexed and > + pointer loops may be freely mixed, and arbitrary code may sit between loops. > + > + IS_LIBSTDCPP_EQUAL_FUNC enables the libstdc++ std::__equal::equal helper > + reshape, which applies when the PHI has no clean boolean success/failure > + shape. Return true if any loop was rewritten. */ > + > +static bool > +analyze_cmp_loops (basic_block bb_phi, bool is_libstdcpp_equal_func) > +{ > + if (!single_succ_p (bb_phi)) > + return false; > + > + /* Find the single non-virtual result PHI. Virtual-operand PHIs (.MEM) may > + coexist and are ignored. */ > + gphi *phi_stmt = NULL; > + for (gphi_iterator gpi = gsi_start_phis (bb_phi); !gsi_end_p (gpi); > + gsi_next (&gpi)) > + { > + gphi *p = *gpi; > + if (virtual_operand_p (gimple_phi_result (p))) > + continue; > + if (phi_stmt != NULL) > + return false; > + phi_stmt = p; > + } > + if (phi_stmt == NULL) > + return false; > + > + tree false_value = NULL_TREE; > + tree true_value = NULL_TREE; > + bool has_unclassified_arg = false; > + auto_vec<edge> mismatch_edges; > + for (unsigned i = 0; i < gimple_phi_num_args (phi_stmt); ++i) > + { > + edge incoming_edge = find_decision_edge_from_phi_arg (phi_stmt, i); > + if (incoming_edge == NULL) > + { > + has_unclassified_arg = true; > + continue; > + } > + tree incoming = gimple_phi_arg_def (phi_stmt, i); > + if (incoming == NULL_TREE || !CONSTANT_CLASS_P (incoming)) > + { > + has_unclassified_arg = true; > + continue; > + } > + > + if (integer_zerop (incoming)) > + { > + false_value = incoming; > + mismatch_edges.safe_push (incoming_edge); > + } > + else if (integer_onep (incoming)) > + true_value = incoming; > + else > + return false; > + } > + > + if (true_value == NULL_TREE || false_value == NULL_TREE || has_unclassified_arg) > + { > + if (is_libstdcpp_equal_func) > + return restructure_memcmp_equal_helper (bb_phi, phi_stmt); > + return false; > + } > + > + tree result_phi_name = gimple_phi_result (phi_stmt); > + > + /* Rewrite each loop identified by a mismatch edge. Distinct loops > + have distinct compare blocks; skip duplicates in case several failure edges > + drain through a shared tail back to the same compare block. */ > + bool changed = false; > + auto_vec<basic_block> seen_compares; > + for (edge mismatch_e : mismatch_edges) > + { > + basic_block bb_compare = mismatch_e->src; > + if (seen_compares.contains (bb_compare)) > + continue; > + seen_compares.safe_push (bb_compare); > + > + if (try_rewrite_cmp_loop_from_mismatch (mismatch_e, bb_phi, result_phi_name, > + false_value, > + true_value, > + !is_libstdcpp_equal_func)) > + changed = true; > + } > + return changed; > +} > + > +/* Parse one fixed-size indexed equality loop whose all-equal exit reaches > + BB_END. > + > + BB_BOUND is the block that proves the loop has not reached its bound. > + One successor exits to BB_END, which is either BB_PHI for the final loop or > + the entry point of the next loop in a short-circuit chain. The other > + successor reaches BB_COMPARE, whose inequality edge must feed BB_PHI with > + FALSE_VALUE. > + > + Return true if the loop shape, range and object-size checks all succeed. */ > + > +static bool > +parse_indexed_cmp_loop (basic_block bb_compare, basic_block bb_bound, > + basic_block bb_phi, basic_block bb_end, > + indexed_cmp_loop *loop) > +{ > + if (bb_bound == NULL || EDGE_COUNT (bb_bound->succs) != 2) > + return false; > + > + if (find_succ_ignore_empties (get_false_edge (bb_bound->succs)->dest) > + != bb_end) > + return false; > + > + indexed_compare_info compare = parse_indexed_compare (bb_compare); > + if (compare.bb == NULL > + || find_succ_ignore_empties (compare.neq_edge->dest) != bb_phi) > + return false; > + > + basic_block equal_dest = find_succ_ignore_empties (compare.eq_edge->dest); > + if (equal_dest == NULL) > + return false; > + > + indexed_bound_info bounds > + = parse_indexed_bounds (bb_bound, compare, bb_end, equal_dest); > + if (bounds.bb == NULL) > + return false; > + > + loop->compare = compare; > + loop->bounds = bounds; > + loop->first_index = 0; > + loop->last_index = 0; > + loop->length = 0; > + return (compute_indexed_cmp_loop_range (loop) > + && compute_indexed_cmp_loop_start_addresses (loop) > + && indexed_cmp_loop_start_defs_available_p (*loop) > + && indexed_cmp_loop_range_safe_p (*loop)); > +} > + > +/* Rewrite one indexed LOOP in place at its own entry edge into a memcmp > + feeding BB_PHI. A terminal loop (all-equal exit reaches BB_PHI) yields > + TRUE_VALUE on equal and FALSE_VALUE on mismatch; a non-terminal loop > + continues to its original success destination on equal and feeds FALSE_VALUE > + on mismatch. */ > + > +static bool > +apply_indexed_cmp_loop (indexed_cmp_loop &loop, basic_block bb_phi, > + tree result_phi_name, tree false_value, tree true_value) > +{ > + /* The block reached when this loop finds every element equal; capture it > + before mutating the CFG. */ > + basic_block equal_dest = loop.bounds.exit_edge->dest; > + bool terminal = (find_succ_ignore_empties (equal_dest) == bb_phi); > + > + basic_block rewrite_bb = split_edge (loop.bounds.entry_edge); > + while (EDGE_COUNT (rewrite_bb->succs) > 0) > + remove_edge (EDGE_SUCC (rewrite_bb, 0)); > + > + tree lhs_ptr = make_ssa_name (TREE_TYPE (loop.compare.lhs_start_addr), NULL); > + tree rhs_ptr = make_ssa_name (TREE_TYPE (loop.compare.rhs_start_addr), NULL); > + gimple *lhs_stmt = gimple_build_assign (lhs_ptr, loop.compare.lhs_start_addr); > + gimple *rhs_stmt = gimple_build_assign (rhs_ptr, loop.compare.rhs_start_addr); > + tree length = wide_int_to_tree (size_type_node, loop.length); > + tree memcmp_result = make_ssa_name (integer_type_node, NULL); > + gcall *memcmp_call > + = gimple_build_call (builtin_decl_implicit (BUILT_IN_MEMCMP), 3, > + lhs_ptr, rhs_ptr, length); > + gimple_call_set_lhs (memcmp_call, memcmp_result); > + gimple *memcmp_cond > + = gimple_build_cond_from_tree > + (build2 (EQ_EXPR, boolean_type_node, memcmp_result, > + build_zero_cst (integer_type_node)), > + NULL_TREE, NULL_TREE); > + > + gimple_stmt_iterator gsi = gsi_last_bb (rewrite_bb); > + gsi_insert_after (&gsi, lhs_stmt, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, rhs_stmt, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, memcmp_call, GSI_CONTINUE_LINKING); > + gsi_insert_after (&gsi, memcmp_cond, GSI_CONTINUE_LINKING); > + > + if (terminal) > + { > + edge split = split_block (rewrite_bb, memcmp_cond); > + basic_block next_bb = split->dest; > + remove_edge (split); > + edge true_edge = make_edge (rewrite_bb, bb_phi, EDGE_TRUE_VALUE); > + true_edge->probability = profile_probability::even (); > + make_edge (rewrite_bb, next_bb, EDGE_FALSE_VALUE)->probability > + = profile_probability::even (); > + edge false_edge = make_edge (next_bb, bb_phi, EDGE_FALLTHRU); > + false_edge->probability = profile_probability::always (); > + gphi *phi = find_phi_with_result (bb_phi, result_phi_name); > + gcc_assert (phi != NULL); > + add_phi_arg (phi, true_value, true_edge, UNKNOWN_LOCATION); > + add_phi_arg (phi, false_value, false_edge, UNKNOWN_LOCATION); > + } > + else > + { > + edge true_edge = make_edge (rewrite_bb, equal_dest, EDGE_TRUE_VALUE); > + true_edge->probability = profile_probability::even (); > + copy_phi_args_to_new_edge (loop.bounds.exit_edge, true_edge); > + edge false_edge = make_edge (rewrite_bb, bb_phi, EDGE_FALSE_VALUE); > + false_edge->probability = profile_probability::even (); > + gphi *phi = find_phi_with_result (bb_phi, result_phi_name); > + gcc_assert (phi != NULL); > + add_phi_arg (phi, false_value, false_edge, UNKNOWN_LOCATION); > + } > + > + if (dump_file) > + fprintf (dump_file, "eqmerge: unrolled indexed loop\n"); > + return true; > +} > + > +/* Try to rewrite the equality loop whose mismatch (false) edge is MISMATCH_E > + feeding BB_PHI, where MISMATCH_E->src is the loop's compare block. Attempt > + both loop kinds -- indexed ARRAY_REF loops and pointer-walking loops -- each > + of which internally handles the header and latch layouts. The loop is > + self-described by its mismatch edge, so it is parsed and rewritten > + independently of any other loop feeding the same PHI. REQUIRE_STATIC_RANGE_P > + selects the pointer-loop safety proof. Return true if one kind matched and > + was rewritten. */ > + > +static bool > +try_rewrite_cmp_loop_from_mismatch (edge mismatch_e, basic_block bb_phi, > + tree result_phi_name, > + tree false_value, tree true_value, > + bool require_static_range_p) > +{ > + basic_block bb_compare = mismatch_e->src; > + basic_block bb_bound, bb_end; > + if (!loop_seed_from_compare (bb_compare, mismatch_e, &bb_bound, &bb_end)) > + return false; > + > + indexed_cmp_loop iloop; > + if (parse_indexed_cmp_loop (bb_compare, bb_bound, bb_phi, bb_end, &iloop)) > + return apply_indexed_cmp_loop (iloop, bb_phi, result_phi_name, false_value, > + true_value); > + > + ptr_cmp_loop ploop; > + if (parse_ptr_cmp_loop (bb_compare, bb_bound, bb_phi, bb_end, &ploop)) > + { > + if (require_static_range_p && !ptr_cmp_loop_static_range_safe_p (ploop)) > + return false; > + return apply_ptr_cmp_loop (ploop, bb_phi, result_phi_name, false_value, > + true_value, require_static_range_p); > + } > + > + return false; > +} > + > +const pass_data pass_data_eq_merge = > +{ > + GIMPLE_PASS, /* type */ > + "eqmerge", /* name */ > + OPTGROUP_NONE, /* optinfo_flags */ > + TV_TREE_EQMERGE, /* tv_id */ > + PROP_cfg | PROP_ssa, /* properties_required */ > + 0, /* properties_provided */ > + 0, /* properties_destroyed */ > + 0, /* todo_flags_start */ > + 0 /* todo_flags_finish */ > +}; > + > +class pass_eq_merge : public gimple_opt_pass > +{ > +public: > + pass_eq_merge (gcc::context *ctxt) > + : gimple_opt_pass (pass_data_eq_merge, ctxt) > + {} > + opt_pass *clone () final override { return new pass_eq_merge (m_ctxt); } > + /* Run at -O2 and above. */ > + bool gate (function *) final override { return optimize >= 2; } > + unsigned int execute (function *) final override; > +}; > + > +/* Execute the eqmerge pass for FUN. > + > + Phase 1 runs over all result PHI blocks and merges short-circuited > + equality chains. Phase 2 then collapses indexed array and pointer-walking > + equality loops into memcmp: each loop feeding a result PHI is discovered > + independently from its mismatch edge, so mixed loop kinds and code between > + loops are handled uniformly, subject to a visible static range or the known > + libstdc++ equality-helper precondition. The pass requests CFG cleanup and > + SSA update only when a rewrite happened. */ > + > +unsigned int > +pass_eq_merge::execute (function *fun) > +{ > + if (!builtin_decl_implicit (BUILT_IN_MEMCMP)) > + return 0; > + > + bool changed = false; > + > + /* Phase 1: merge field-compare chains feeding any PHI in this function. > + The structural pattern match in comparison_block_p is selective enough > + to leave non-chain functions untouched. */ > + basic_block bb; > + FOR_EACH_BB_REVERSE_FN (bb, fun) > + { > + if (phi_nodes (bb) == NULL) > + continue; > + if (merge_cmp_chains_for_phi (bb)) > + changed = true; > + } > + > + /* Phase 2: collapse indexed array and pointer-walking equality loops into > + memcmp. Each loop feeding a result PHI is discovered independently from > + its mismatch edge, so mixed indexed/pointer loops are handled uniformly. > + Ranges are proven inside the pointed-to objects, except for the libstdc++ > + equality helper whose range precondition is not visible from the raw > + pointer parameters inside the helper body. */ > + bool is_libstdcpp_equal_func = is_libstdcpp_equal_helper (fun->decl); > + > + FOR_EACH_BB_REVERSE_FN (bb, fun) > + { > + if (phi_nodes (bb) == NULL) > + continue; > + if (analyze_cmp_loops (bb, is_libstdcpp_equal_func)) > + changed = true; > + } > + > + return changed ? (TODO_cleanup_cfg | TODO_update_ssa) : 0; > +} > + > +} // anon namespace > + > +gimple_opt_pass * > +make_pass_eq_merge (gcc::context *ctxt) > +{ > + return new pass_eq_merge (ctxt); > +} > -- > 2.43.0 >