[v4] A new copy propagation and PHI elimination pass

  > > > Hi,
> > > 
> > > this is a patch that I submitted two months ago as an RFC. I added some polish
> > > since.
> > > 
> > > It is a new lightweight pass that removes redundant PHI functions and as a
> > > bonus does basic copy propagation. With Jan Hubi?ka we measured that it is able
> > > to remove usually more than 5% of all PHI functions when run among early passes
> > > (sometimes even 13% or more). Those are mostly PHI functions that would be
> > > later optimized away but with this pass it is possible to remove them early
> > > enough so that they don't get streamed when runing LTO (and also potentially
> > > inlined at multiple places). It is also able to remove some redundant PHIs
> > > that otherwise would still be present during RTL expansion.
> > > 
> > > Jakub Jel?nek was concerned about debug info coverage so I compiled cc1plus
> > > with and without this patch. These are the sizes of .debug_info and
> > > .debug_loclists
> > > 
> > > .debug_info without patch 181694311
> > > .debug_info    with patch 181692320
> > > +0.0011% change
> > > 
> > > .debug_loclists without patch 47934753
> > > .debug_loclists    with patch 47934966
> > > -0.0004% change
> > > 
> > > I wanted to use dwlocstat to compare debug coverages but didn't manage to get
> > > the program working on my machine sadly. Hope this suffices. Seems to me that
> > > my patch doesn't have a significant impact on debug info.
> > > 
> > > Bootstraped and tested* on x86_64-pc-linux-gnu.
> > > 
> > > * One testcase (pr79691.c) did regress. However that is because the test is
> > > dependent on a certain variable not being copy propagated. I will go into more
> > > detail about this in a reply to this mail.
> > > 
> > > Ok to commit?
> > 
> > This is a second version of the patch.  In this version, I modified the
> > pr79691.c testcase so that it works as intended with other changes from the
> > patch.
> > 
> > The pr79691.c testcase checks that we get constants from snprintf calls and
> > that they simplify into a single constant.  The testcase doesn't account for
> > the fact that this constant may be further copy propagated which is exactly
> > what happens with this patch applied.
> > 
> > Bootstrapped and tested on x86_64-pc-linux-gnu.
> > 
> > Ok to commit?
> 
> This is the third version of the patch. In this version, I adressed most of
> Richards remarks about the second version. Here is a summary of changes I made:
> 
> - Rename the pass from tree-ssa-sccopy.cc to gimple-ssa-sccopy.cc
> - Use simple_dce_from_worklist to remove propagated statements
> - Use existing replace_uses API instead of reinventing it
>   - This allowed me to get rid of some now redundant cleanup code
> - Encapsulate the SCC finding into a class
> - Rework stmt_may_generate_copy to get rid of redundant checks
> - Add check that PHI doesn't contain two non-SSA-name values to
>   stmt_may_generate_copy
> - Regarding alignment and value ranges in stmt_may_generate_copy: For now use
>   the conservative check that Richard suggested
> - Index array of vertices that SCC discovery uses by SSA name version numbers
>   instead of numbering statements myself.
> 
> 
> I didn't make any changes based on these remarks:
> 
> 1 It might be nice to optimize SCCs of size 1 somehow, not sure how
>   many times these appear - possibly prevent them from even entering
>   the SCC discovery?
> 
> It would be nice. But the only way to do this that I see right now is to first
> propagate SCCs of size 1 and then the rest. This would mean adding a new copy
> propagation procedure. It wouldn't be a trivial procedure. Efficiency of the
> pass relies on having SCCs topogically sorted so this procedure would have to
> implement some topological sort algorithm.
> 
> This could be done. It could save allocating some vec<>s (right now, SCCs of
> size 1 are represented by a vec<> with a single element). But is it worth it to
> optimize the pass this way right now? If possible, I'd like to see that the
> pass works and sort out any problems people encounter with it before I start
> optimizing it.
> 
> 2 Instead of collecting all stmts that may generate a copy at the beginning of
>   the pass into a vec<>, let the SCC discovery check that statements may
>   generate a copy on the fly.
> 
> This would be a big change to the pass, it would require a lot of reworking.
> I'm also not sure if this would help reduce the number of allocated vec<>s that
> much because I'll still want to represent SCCs by vec<>s.
> 
> Again - its possible I'll want to rework the pass in this way in the future but
> I'd like to leave it as it is for now.
> 
> 3 Add a comment saying that the pass is doing optimistic copy propagation
> 
> I don't think the pass works in an optimistic way. It doesn't assume that all
> variables are copies of each other at any point. It instead identifies copy
> statements (or PHI SCCs that act as copy statements) and then for each of these
> it propagates: By that I mean if a copy statement says that _3 is a copy of _2,
> then it replaces all uses of _3 by _2.
> 
> But its possible that I still misinterpret what 'optimistic' means. If
> mentioning that it works in an optimistic way would help readability of the
> pass, I'm happy to add that comment.
>
> Richard, is the patch ok as it is now? Or do you think that making changes 1, 2
> or 3 is necessary? Or are there any other issues which should be adressed?
>
> Filip

This is the fourth version of this patch. Changes in this version:
- Disabled the pass for -Og
  - This meant that I could revert my changes to gcc.dg/tree-ssa/pr79691.c
- Fixed formatting of the patch (like braces around a single-statment if body)
- compute_sccs (auto_vec<>...) -> compute_sccs (vec<> ...)
- auto_vec<gimple *> worklist; worklist = ...; ->
  auto_vec<gimple *> worklist = ...;

I've also checked that there are no memory leak issues. Valgrind doesn't detect
any aditional leaks when running with sccopy vs running without sccopy:

[fkastl@scala playground]$ valgrind $HOME/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2
==27363== Memcheck, a memory error detector
==27363== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==27363== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==27363== Command: /home/fkastl/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2
==27363== 
==27363== 
==27363== HEAP SUMMARY:
==27363==     in use at exit: 174,234 bytes in 92 blocks
==27363==   total heap usage: 408 allocs, 316 frees, 228,050 bytes allocated
==27363== 
==27363== LEAK SUMMARY:
==27363==    definitely lost: 5,935 bytes in 23 blocks
==27363==    indirectly lost: 82 bytes in 5 blocks
==27363==      possibly lost: 0 bytes in 0 blocks
==27363==    still reachable: 168,217 bytes in 64 blocks
==27363==                       of which reachable via heuristic:
==27363==                         newarray           : 1,544 bytes in 1 blocks
==27363==         suppressed: 0 bytes in 0 blocks
==27363== Rerun with --leak-check=full to see details of leaked memory
==27363== 
==27363== For lists of detected and suppressed errors, rerun with: -s
==27363== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

[fkastl@scala playground]$ valgrind $HOME/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2 -fdisable-tree-sccopy1 -fdisable-tree-sccopy2
==27372== Memcheck, a memory error detector
==27372== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==27372== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==27372== Command: /home/fkastl/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2 -fdisable-tree-sccopy1 -fdisable-tree-sccopy2
==27372== 
cc1: note: disable pass tree-sccopy1 for functions in the range of [0, 4294967295]
cc1: note: disable pass tree-sccopy2 for functions in the range of [0, 4294967295]
==27372== 
==27372== HEAP SUMMARY:
==27372==     in use at exit: 174,282 bytes in 92 blocks
==27372==   total heap usage: 408 allocs, 316 frees, 228,674 bytes allocated
==27372== 
==27372== LEAK SUMMARY:
==27372==    definitely lost: 5,935 bytes in 23 blocks
==27372==    indirectly lost: 82 bytes in 5 blocks
==27372==      possibly lost: 0 bytes in 0 blocks
==27372==    still reachable: 168,265 bytes in 64 blocks
==27372==                       of which reachable via heuristic:
==27372==                         newarray           : 1,544 bytes in 1 blocks
==27372==         suppressed: 0 bytes in 0 blocks
==27372== Rerun with --leak-check=full to see details of leaked memory
==27372== 
==27372== For lists of detected and suppressed errors, rerun with: -s
==27372== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Richard, I wrote down the bitmap vs hash_set optimizations you suggested so
that I can work on the pass more later and optimize it.

I didn't yet bootstrap this version. I just regtested it. Will bootstrap and
regtest on the most current commit. Once that is successfully done, is the pass
OK to be pushed to main?

Filip

-- >8 --

This patch adds the strongly-connected copy propagation (SCCOPY) pass.
It is a lightweight GIMPLE copy propagation pass that also removes some
redundant PHI statements. It handles degenerate PHIs, e.g.:

_5 = PHI <_1>;
_6 = PHI <_6, _6, _1, _1>;
_7 = PHI <16, _7>;
// Replaces occurences of _5 and _6 by _1 and _7 by 16

It also handles more complicated situations, e.g.:

_8 = PHI <_9, _10>;
_9 = PHI <_8, _10>;
_10 = PHI <_8, _9, _1>;
// Replaces occurences of _8, _9 and _10 by _1

gcc/ChangeLog:

	* Makefile.in: Added sccopy pass.
	* passes.def: Added sccopy pass before LTO streaming and before
	  RTL expansion.
	* tree-pass.h (make_pass_sccopy): Added sccopy pass.
	* gimple-ssa-sccopy.cc: New file.

gcc/testsuite/ChangeLog:

	* gcc.dg/sccopy-1.c: New test.

Signed-off-by: Filip Kastl <fkastl@suse.cz>
---
 gcc/Makefile.in                 |   1 +
 gcc/gimple-ssa-sccopy.cc        | 680 ++++++++++++++++++++++++++++++++
 gcc/passes.def                  |   2 +
 gcc/testsuite/gcc.dg/sccopy-1.c |  78 ++++
 gcc/tree-pass.h                 |   1 +
 5 files changed, 762 insertions(+)
 create mode 100644 gcc/gimple-ssa-sccopy.cc
 create mode 100644 gcc/testsuite/gcc.dg/sccopy-1.c
  

> Am 13.12.2023 um 17:12 schrieb Filip Kastl <fkastl@suse.cz>:
> 
> 
>> 
>>>> Hi,
>>>> 
>>>> this is a patch that I submitted two months ago as an RFC. I added some polish
>>>> since.
>>>> 
>>>> It is a new lightweight pass that removes redundant PHI functions and as a
>>>> bonus does basic copy propagation. With Jan Hubi?ka we measured that it is able
>>>> to remove usually more than 5% of all PHI functions when run among early passes
>>>> (sometimes even 13% or more). Those are mostly PHI functions that would be
>>>> later optimized away but with this pass it is possible to remove them early
>>>> enough so that they don't get streamed when runing LTO (and also potentially
>>>> inlined at multiple places). It is also able to remove some redundant PHIs
>>>> that otherwise would still be present during RTL expansion.
>>>> 
>>>> Jakub Jel?nek was concerned about debug info coverage so I compiled cc1plus
>>>> with and without this patch. These are the sizes of .debug_info and
>>>> .debug_loclists
>>>> 
>>>> .debug_info without patch 181694311
>>>> .debug_info    with patch 181692320
>>>> +0.0011% change
>>>> 
>>>> .debug_loclists without patch 47934753
>>>> .debug_loclists    with patch 47934966
>>>> -0.0004% change
>>>> 
>>>> I wanted to use dwlocstat to compare debug coverages but didn't manage to get
>>>> the program working on my machine sadly. Hope this suffices. Seems to me that
>>>> my patch doesn't have a significant impact on debug info.
>>>> 
>>>> Bootstraped and tested* on x86_64-pc-linux-gnu.
>>>> 
>>>> * One testcase (pr79691.c) did regress. However that is because the test is
>>>> dependent on a certain variable not being copy propagated. I will go into more
>>>> detail about this in a reply to this mail.
>>>> 
>>>> Ok to commit?
>>> 
>>> This is a second version of the patch.  In this version, I modified the
>>> pr79691.c testcase so that it works as intended with other changes from the
>>> patch.
>>> 
>>> The pr79691.c testcase checks that we get constants from snprintf calls and
>>> that they simplify into a single constant.  The testcase doesn't account for
>>> the fact that this constant may be further copy propagated which is exactly
>>> what happens with this patch applied.
>>> 
>>> Bootstrapped and tested on x86_64-pc-linux-gnu.
>>> 
>>> Ok to commit?
>> 
>> This is the third version of the patch. In this version, I adressed most of
>> Richards remarks about the second version. Here is a summary of changes I made:
>> 
>> - Rename the pass from tree-ssa-sccopy.cc to gimple-ssa-sccopy.cc
>> - Use simple_dce_from_worklist to remove propagated statements
>> - Use existing replace_uses API instead of reinventing it
>>  - This allowed me to get rid of some now redundant cleanup code
>> - Encapsulate the SCC finding into a class
>> - Rework stmt_may_generate_copy to get rid of redundant checks
>> - Add check that PHI doesn't contain two non-SSA-name values to
>>  stmt_may_generate_copy
>> - Regarding alignment and value ranges in stmt_may_generate_copy: For now use
>>  the conservative check that Richard suggested
>> - Index array of vertices that SCC discovery uses by SSA name version numbers
>>  instead of numbering statements myself.
>> 
>> 
>> I didn't make any changes based on these remarks:
>> 
>> 1 It might be nice to optimize SCCs of size 1 somehow, not sure how
>>  many times these appear - possibly prevent them from even entering
>>  the SCC discovery?
>> 
>> It would be nice. But the only way to do this that I see right now is to first
>> propagate SCCs of size 1 and then the rest. This would mean adding a new copy
>> propagation procedure. It wouldn't be a trivial procedure. Efficiency of the
>> pass relies on having SCCs topogically sorted so this procedure would have to
>> implement some topological sort algorithm.
>> 
>> This could be done. It could save allocating some vec<>s (right now, SCCs of
>> size 1 are represented by a vec<> with a single element). But is it worth it to
>> optimize the pass this way right now? If possible, I'd like to see that the
>> pass works and sort out any problems people encounter with it before I start
>> optimizing it.
>> 
>> 2 Instead of collecting all stmts that may generate a copy at the beginning of
>>  the pass into a vec<>, let the SCC discovery check that statements may
>>  generate a copy on the fly.
>> 
>> This would be a big change to the pass, it would require a lot of reworking.
>> I'm also not sure if this would help reduce the number of allocated vec<>s that
>> much because I'll still want to represent SCCs by vec<>s.
>> 
>> Again - its possible I'll want to rework the pass in this way in the future but
>> I'd like to leave it as it is for now.
>> 
>> 3 Add a comment saying that the pass is doing optimistic copy propagation
>> 
>> I don't think the pass works in an optimistic way. It doesn't assume that all
>> variables are copies of each other at any point. It instead identifies copy
>> statements (or PHI SCCs that act as copy statements) and then for each of these
>> it propagates: By that I mean if a copy statement says that _3 is a copy of _2,
>> then it replaces all uses of _3 by _2.
>> 
>> But its possible that I still misinterpret what 'optimistic' means. If
>> mentioning that it works in an optimistic way would help readability of the
>> pass, I'm happy to add that comment.
>> 
>> Richard, is the patch ok as it is now? Or do you think that making changes 1, 2
>> or 3 is necessary? Or are there any other issues which should be adressed?
>> 
>> Filip
> 
> This is the fourth version of this patch. Changes in this version:
> - Disabled the pass for -Og
>  - This meant that I could revert my changes to gcc.dg/tree-ssa/pr79691.c
> - Fixed formatting of the patch (like braces around a single-statment if body)
> - compute_sccs (auto_vec<>...) -> compute_sccs (vec<> ...)
> - auto_vec<gimple *> worklist; worklist = ...; ->
>  auto_vec<gimple *> worklist = ...;
> 
> I've also checked that there are no memory leak issues. Valgrind doesn't detect
> any aditional leaks when running with sccopy vs running without sccopy:
> 
> [fkastl@scala playground]$ valgrind $HOME/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2
> ==27363== Memcheck, a memory error detector
> ==27363== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
> ==27363== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
> ==27363== Command: /home/fkastl/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2
> ==27363== 
> ==27363== 
> ==27363== HEAP SUMMARY:
> ==27363==     in use at exit: 174,234 bytes in 92 blocks
> ==27363==   total heap usage: 408 allocs, 316 frees, 228,050 bytes allocated
> ==27363== 
> ==27363== LEAK SUMMARY:
> ==27363==    definitely lost: 5,935 bytes in 23 blocks
> ==27363==    indirectly lost: 82 bytes in 5 blocks
> ==27363==      possibly lost: 0 bytes in 0 blocks
> ==27363==    still reachable: 168,217 bytes in 64 blocks
> ==27363==                       of which reachable via heuristic:
> ==27363==                         newarray           : 1,544 bytes in 1 blocks
> ==27363==         suppressed: 0 bytes in 0 blocks
> ==27363== Rerun with --leak-check=full to see details of leaked memory
> ==27363== 
> ==27363== For lists of detected and suppressed errors, rerun with: -s
> ==27363== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
> 
> [fkastl@scala playground]$ valgrind $HOME/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2 -fdisable-tree-sccopy1 -fdisable-tree-sccopy2
> ==27372== Memcheck, a memory error detector
> ==27372== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
> ==27372== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
> ==27372== Command: /home/fkastl/gcc/inst/bin/gcc /home/fkastl/gcc/src/gcc/testsuite/gcc.dg/sccopy-1.c -fgimple -O2 -fdisable-tree-sccopy1 -fdisable-tree-sccopy2
> ==27372== 
> cc1: note: disable pass tree-sccopy1 for functions in the range of [0, 4294967295]
> cc1: note: disable pass tree-sccopy2 for functions in the range of [0, 4294967295]
> ==27372== 
> ==27372== HEAP SUMMARY:
> ==27372==     in use at exit: 174,282 bytes in 92 blocks
> ==27372==   total heap usage: 408 allocs, 316 frees, 228,674 bytes allocated
> ==27372== 
> ==27372== LEAK SUMMARY:
> ==27372==    definitely lost: 5,935 bytes in 23 blocks
> ==27372==    indirectly lost: 82 bytes in 5 blocks
> ==27372==      possibly lost: 0 bytes in 0 blocks
> ==27372==    still reachable: 168,265 bytes in 64 blocks
> ==27372==                       of which reachable via heuristic:
> ==27372==                         newarray           : 1,544 bytes in 1 blocks
> ==27372==         suppressed: 0 bytes in 0 blocks
> ==27372== Rerun with --leak-check=full to see details of leaked memory
> ==27372== 
> ==27372== For lists of detected and suppressed errors, rerun with: -s
> ==27372== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
> 
> Richard, I wrote down the bitmap vs hash_set optimizations you suggested so
> that I can work on the pass more later and optimize it.
> 
> I didn't yet bootstrap this version. I just regtested it. Will bootstrap and
> regtest on the most current commit. Once that is successfully done, is the pass
> OK to be pushed to main?

Yes.

Thanks,
Richard 


> Filip
> 
> -- >8 --
> 
> This patch adds the strongly-connected copy propagation (SCCOPY) pass.
> It is a lightweight GIMPLE copy propagation pass that also removes some
> redundant PHI statements. It handles degenerate PHIs, e.g.:
> 
> _5 = PHI <_1>;
> _6 = PHI <_6, _6, _1, _1>;
> _7 = PHI <16, _7>;
> // Replaces occurences of _5 and _6 by _1 and _7 by 16
> 
> It also handles more complicated situations, e.g.:
> 
> _8 = PHI <_9, _10>;
> _9 = PHI <_8, _10>;
> _10 = PHI <_8, _9, _1>;
> // Replaces occurences of _8, _9 and _10 by _1
> 
> gcc/ChangeLog:
> 
>    * Makefile.in: Added sccopy pass.
>    * passes.def: Added sccopy pass before LTO streaming and before
>      RTL expansion.
>    * tree-pass.h (make_pass_sccopy): Added sccopy pass.
>    * gimple-ssa-sccopy.cc: New file.
> 
> gcc/testsuite/ChangeLog:
> 
>    * gcc.dg/sccopy-1.c: New test.
> 
> Signed-off-by: Filip Kastl <fkastl@suse.cz>
> ---
> gcc/Makefile.in                 |   1 +
> gcc/gimple-ssa-sccopy.cc        | 680 ++++++++++++++++++++++++++++++++
> gcc/passes.def                  |   2 +
> gcc/testsuite/gcc.dg/sccopy-1.c |  78 ++++
> gcc/tree-pass.h                 |   1 +
> 5 files changed, 762 insertions(+)
> create mode 100644 gcc/gimple-ssa-sccopy.cc
> create mode 100644 gcc/testsuite/gcc.dg/sccopy-1.c
> 
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 753f2f36618..2e6f2fef1ba 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1497,6 +1497,7 @@ OBJS = \
>    gimple-ssa-backprop.o \
>    gimple-ssa-isolate-paths.o \
>    gimple-ssa-nonnull-compare.o \
> +    gimple-ssa-sccopy.o \
>    gimple-ssa-split-paths.o \
>    gimple-ssa-store-merging.o \
>    gimple-ssa-strength-reduction.o \
> diff --git a/gcc/gimple-ssa-sccopy.cc b/gcc/gimple-ssa-sccopy.cc
> new file mode 100644
> index 00000000000..ac5ec32eb32
> --- /dev/null
> +++ b/gcc/gimple-ssa-sccopy.cc
> @@ -0,0 +1,680 @@
> +/* Strongly-connected copy propagation pass for the GNU compiler.
> +   Copyright (C) 2023 Free Software Foundation, Inc.
> +   Contributed by Filip Kastl <fkastl@suse.cz>
> +
> +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 "gimple-iterator.h"
> +#include "vec.h"
> +#include "hash-set.h"
> +#include <algorithm>
> +#include "ssa-iterators.h"
> +#include "gimple-fold.h"
> +#include "gimplify.h"
> +#include "tree-cfg.h"
> +#include "tree-eh.h"
> +#include "builtins.h"
> +#include "tree-ssa-dce.h"
> +#include "fold-const.h"
> +
> +/* Strongly connected copy propagation pass.
> +
> +   This is a lightweight copy propagation pass that is also able to eliminate
> +   redundant PHI statements.  The pass considers the following types of copy
> +   statements:
> +
> +   1 An assignment statement with a single argument.
> +
> +   _3 = _2;
> +   _4 = 5;
> +
> +   2 A degenerate PHI statement.  A degenerate PHI is a PHI that only refers to
> +     itself or one other value.
> +
> +   _5 = PHI <_1>;
> +   _6 = PHI <_6, _6, _1, _1>;
> +   _7 = PHI <16, _7>;
> +
> +   3 A set of PHI statements that only refer to each other or to one other
> +     value.
> +
> +   _8 = PHI <_9, _10>;
> +   _9 = PHI <_8, _10>;
> +   _10 = PHI <_8, _9, _1>;
> +
> +   All of these statements produce copies and can be eliminated from the
> +   program.  For a copy statement we identify the value it creates a copy of
> +   and replace references to the statement with the value -- we propagate the
> +   copy.
> +
> +   _3 = _2; // Replace all occurences of _3 by _2
> +
> +   _8 = PHI <_9, _10>;
> +   _9 = PHI <_8, _10>;
> +   _10 = PHI <_8, _9, _1>; // Replace all occurences of _8, _9 and _10 by _1
> +
> +   To find all three types of copy statements we use an algorithm based on
> +   strongly-connected components (SCCs) in dataflow graph.  The algorithm was
> +   introduced in an article from 2013[1]. We describe the algorithm bellow.
> +
> +   To identify SCCs we implement the Robert Tarjan's SCC algorithm.  For the
> +   SCC computation we wrap potential copy statements in the 'vertex' struct.
> +   To each of these statements we also assign a vertex number ('vxnum'). Since
> +   the main algorithm has to be able to compute SCCs of subgraphs of the whole
> +   dataflow graph we use GIMPLE stmt flags to prevent Tarjan's algorithm from
> +   leaving the subgraph.
> +
> +   References:
> +
> +     [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
> +     Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
> +     Section 3.2.  */
> +
> +/* Bitmap tracking statements which were propagated to be removed at the end of
> +   the pass.  */
> +
> +static bitmap dead_stmts;
> +
> +/* State of vertex during SCC discovery.
> +
> +   unvisited  Vertex hasn't yet been popped from worklist.
> +   vopen      DFS has visited vertex for the first time.  Vertex has been put
> +          on Tarjan stack.
> +   closed     DFS has backtracked through vertex.  At this point, vertex
> +          doesn't have any unvisited neighbors.
> +   in_scc     Vertex has been popped from Tarjan stack.  */
> +
> +enum vstate
> +{
> +  unvisited,
> +  vopen,
> +  closed,
> +  in_scc
> +};
> +
> +/* Information about a vertex.  Used by SCC discovery.  */
> +
> +struct vertex
> +{
> +  bool active; /* scc_discovery::compute_sccs () only considers a subgraph of
> +          the whole dataflow graph.  It uses this flag so that it knows
> +          which vertices are part of this subgraph.  */
> +  vstate state;
> +  unsigned index;
> +  unsigned lowlink;
> +};
> +
> +/* SCC discovery.
> +
> +   Used to find SCCs in a dataflow graph.  Implements Tarjan's SCC
> +   algorithm.  */
> +
> +class scc_discovery
> +{
> +public:
> +  scc_discovery ();
> +  ~scc_discovery ();
> +  auto_vec<vec<gimple *>> compute_sccs (vec<gimple *> &stmts);
> +
> +private:
> +  unsigned curr_generation = 0;
> +  vertex* vertices; /* Indexed by SSA_NAME_VERSION.  */
> +  auto_vec<unsigned> worklist; /* DFS stack.  */
> +  auto_vec<unsigned> stack; /* Tarjan stack.  */
> +
> +  void visit_neighbor (tree neigh_tree, unsigned parent_vxnum);
> +};
> +
> +scc_discovery::scc_discovery ()
> +{
> +  /* Create vertex struct for each SSA name.  */
> +  vertices = XNEWVEC (struct vertex, num_ssa_names);
> +  unsigned i = 0;
> +  for (i = 0; i < num_ssa_names; i++)
> +    vertices[i].active = false;
> +}
> +
> +scc_discovery::~scc_discovery ()
> +{
> +  XDELETEVEC (vertices);
> +}
> +
> +/* Part of 'scc_discovery::compute_sccs ()'.  */
> +
> +void
> +scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version)
> +{
> +  if (TREE_CODE (neigh_tree) != SSA_NAME)
> +    return; /* Skip any neighbor that isn't an SSA name.  */
> +  unsigned neigh_version = SSA_NAME_VERSION (neigh_tree);
> +
> +  /* Skip neighbors outside the subgraph that Tarjan currently works
> +     with.  */
> +  if (!vertices[neigh_version].active)
> +    return;
> +
> +  vstate neigh_state = vertices[neigh_version].state;
> +  vstate parent_state = vertices[parent_version].state;
> +  if (parent_state == vopen) /* We're currently opening parent.  */
> +    {
> +      /* Put unvisited neighbors on worklist.  Update lowlink of parent
> +     vertex according to indices of neighbors present on stack.  */
> +      switch (neigh_state)
> +    {
> +    case unvisited:
> +      worklist.safe_push (neigh_version);
> +      break;
> +    case vopen:
> +    case closed:
> +      vertices[parent_version].lowlink
> +        = std::min (vertices[parent_version].lowlink,
> +            vertices[neigh_version].index);
> +      break;
> +    case in_scc:
> +      /* Ignore these edges.  */
> +      break;
> +    }
> +    }
> +  else if (parent_state == closed) /* We're currently closing parent.  */
> +    {
> +      /* Update lowlink of parent vertex according to lowlinks of
> +     children of parent (in terms of DFS tree).  */
> +      if (neigh_state == closed)
> +    {
> +      vertices[parent_version].lowlink
> +        = std::min (vertices[parent_version].lowlink,
> +            vertices[neigh_version].lowlink);
> +    }
> +    }
> +}
> +
> +/* Compute SCCs in dataflow graph on given statements 'stmts'.  Ignore
> +   statements outside 'stmts'.  Return the SCCs in a reverse topological
> +   order.
> +
> +   stmt_may_generate_copy () must be true for all statements from 'stmts'!  */
> +
> +auto_vec<vec<gimple *>>
> +scc_discovery::compute_sccs (vec<gimple *> &stmts)
> +{
> +  auto_vec<vec<gimple *>> sccs;
> +
> +  for (gimple *stmt : stmts)
> +    {
> +      unsigned i;
> +      switch (gimple_code (stmt))
> +    {
> +      case GIMPLE_ASSIGN:
> +        i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
> +        break;
> +      case GIMPLE_PHI:
> +        i = SSA_NAME_VERSION (gimple_phi_result (stmt));
> +        break;
> +      default:
> +        gcc_unreachable ();
> +    }
> +
> +      vertices[i].index = 0;
> +      vertices[i].lowlink = 0;
> +      vertices[i].state = unvisited;
> +      vertices[i].active = true; /* Mark the subgraph we'll be working on so
> +                    that we don't leave it.  */
> +
> +      worklist.safe_push (i);
> +    }
> +
> +  /* Worklist loop.  */
> +  unsigned curr_index = 0;
> +  while (!worklist.is_empty ())
> +    {
> +      unsigned i = worklist.pop ();
> +      gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i));
> +      vstate state = vertices[i].state;
> +
> +      if (state == unvisited)
> +    {
> +      vertices[i].state = vopen;
> +
> +      /* Assign index to this vertex.  */
> +      vertices[i].index = curr_index;
> +      vertices[i].lowlink = curr_index;
> +      curr_index++;
> +
> +      /* Put vertex on stack and also on worklist to be closed later.  */
> +      stack.safe_push (i);
> +      worklist.safe_push (i);
> +    }
> +      else if (state == vopen)
> +    vertices[i].state = closed;
> +
> +      /* Visit neighbors of this vertex.  */
> +      tree op;
> +      gphi *phi;
> +      switch (gimple_code (stmt))
> +    {
> +      case GIMPLE_PHI:
> +        phi = as_a <gphi *> (stmt);
> +        unsigned j;
> +        for (j = 0; j < gimple_phi_num_args (phi); j++)
> +          {
> +        op = gimple_phi_arg_def (phi, j);
> +        visit_neighbor (op, i);
> +          }
> +        break;
> +      case GIMPLE_ASSIGN:
> +        op = gimple_assign_rhs1 (stmt);
> +        visit_neighbor (op, i);
> +        break;
> +      default:
> +        gcc_unreachable ();
> +    }
> +
> +      /* If we've just closed a root vertex of an scc, pop scc from stack.  */
> +      if (state == vopen && vertices[i].lowlink == vertices[i].index)
> +    {
> +      vec<gimple *> scc = vNULL;
> +
> +      unsigned j;
> +      do
> +        {
> +          j = stack.pop ();
> +          scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j)));
> +          vertices[j].state = in_scc;
> +        }
> +      while (j != i);
> +
> +      sccs.safe_push (scc);
> +    }
> +    }
> +
> +  if (!stack.is_empty ())
> +    gcc_unreachable ();
> +
> +  /* Clear 'active' flags.  */
> +  for (gimple *stmt : stmts)
> +    {
> +      unsigned i;
> +      switch (gimple_code (stmt))
> +    {
> +      case GIMPLE_ASSIGN:
> +        i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
> +        break;
> +      case GIMPLE_PHI:
> +        i = SSA_NAME_VERSION (gimple_phi_result (stmt));
> +        break;
> +      default:
> +        gcc_unreachable ();
> +    }
> +
> +      vertices[i].active = false;
> +    }
> +
> +  return sccs;
> +}
> +
> +/* Could this statement potentially be a copy statement?
> +
> +   This pass only considers statements for which this function returns 'true'.
> +   Those are basically PHI functions and assignment statements similar to
> +
> +   _2 = _1;
> +   or
> +   _2 = 5;  */
> +
> +static bool
> +stmt_may_generate_copy (gimple *stmt)
> +{
> +  /* A PHI may generate a copy.  */
> +  if (gimple_code (stmt) == GIMPLE_PHI)
> +    {
> +      gphi *phi = as_a <gphi *> (stmt);
> +
> +      /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs.  */
> +      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
> +    return false;
> +
> +      unsigned i;
> +      for (i = 0; i < gimple_phi_num_args (phi); i++)
> +    {
> +      tree op = gimple_phi_arg_def (phi, i);
> +      if (TREE_CODE (op) == SSA_NAME
> +          && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
> +        return false;
> +    }
> +
> +      /* If PHI has more than one unique non-SSA arguments, it won't generate a
> +     copy.  */
> +      tree const_op = NULL_TREE;
> +      for (i = 0; i < gimple_phi_num_args (phi); i++)
> +    {
> +      tree op = gimple_phi_arg_def (phi, i);
> +      if (TREE_CODE (op) != SSA_NAME)
> +        {
> +          if (const_op && !operand_equal_p (op, const_op))
> +        return false;
> +          const_op = op;
> +        }
> +    }
> +
> +      return true;
> +    }
> +
> +  /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy.  */
> +
> +  if (!gimple_assign_single_p (stmt))
> +    return false;
> +
> +  tree lhs = gimple_assign_lhs (stmt);
> +  tree rhs = gimple_assign_rhs1 (stmt);
> +
> +  if (TREE_CODE (lhs) != SSA_NAME)
> +    return false;
> +
> +  /* lhs shouldn't flow through any abnormal edges.  */
> +  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
> +    return false;
> +
> +  if (is_gimple_min_invariant (rhs))
> +    return true;  /* A statement of type _2 = 5;.  */
> +
> +  if (TREE_CODE (rhs) != SSA_NAME)
> +    return false;
> +
> +  /* rhs shouldn't flow through any abnormal edges.  */
> +  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
> +    return false;
> +
> +  /* It is possible that lhs has more alignment or value range information.  By
> +     propagating we would lose this information.  So in the case that alignment
> +     or value range information differs, we are conservative and do not
> +     propagate.
> +
> +     FIXME: Propagate alignment and value range info the same way copy-prop
> +     does.  */
> +  if (POINTER_TYPE_P (TREE_TYPE (lhs))
> +      && POINTER_TYPE_P (TREE_TYPE (rhs))
> +      && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs))
> +    return false;
> +  if (!POINTER_TYPE_P (TREE_TYPE (lhs))
> +      && !POINTER_TYPE_P (TREE_TYPE (rhs))
> +      && SSA_NAME_RANGE_INFO (lhs) != SSA_NAME_RANGE_INFO (rhs))
> +    return false;
> +
> +  return true;  /* A statement of type _2 = _1;.  */
> +}
> +
> +/* Return all statements in cfun that could generate copies.  All statements
> +   for which stmt_may_generate_copy returns 'true'.  */
> +
> +static auto_vec<gimple *>
> +get_all_stmt_may_generate_copy (void)
> +{
> +  auto_vec<gimple *> result;
> +
> +  basic_block bb;
> +  FOR_EACH_BB_FN (bb, cfun)
> +    {
> +      gimple_stmt_iterator gsi;
> +      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +    {
> +      gimple *s = gsi_stmt (gsi);
> +      if (stmt_may_generate_copy (s))
> +        result.safe_push (s);
> +    }
> +
> +      gphi_iterator pi;
> +      for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
> +    {
> +      gimple *s = pi.phi ();
> +      if (stmt_may_generate_copy (s))
> +        result.safe_push (s);
> +    }
> +    }
> +
> +  return result;
> +}
> +
> +/* For each statement from given SCC, replace its usages by value
> +   VAL.  */
> +
> +static void
> +replace_scc_by_value (vec<gimple *> scc, tree val)
> +{
> +  for (gimple *stmt : scc)
> +    {
> +      tree name = gimple_get_lhs (stmt);
> +      replace_uses_by (name, val);
> +      bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name));
> +    }
> +
> +  if (dump_file)
> +    fprintf (dump_file, "Replacing SCC of size %d\n", scc.length ());
> +}
> +
> +/* Part of 'sccopy_propagate ()'.  */
> +
> +static void
> +sccopy_visit_op (tree op, hash_set<tree> &outer_ops,
> +         hash_set<gimple *> &scc_set, bool &is_inner,
> +         tree &last_outer_op)
> +{
> +  bool op_in_scc = false;
> +
> +  if (TREE_CODE (op) == SSA_NAME)
> +    {
> +      gimple *op_stmt = SSA_NAME_DEF_STMT (op);
> +      if (scc_set.contains (op_stmt))
> +    op_in_scc = true;
> +    }
> +
> +  if (!op_in_scc)
> +    {
> +      outer_ops.add (op);
> +      last_outer_op = op;
> +      is_inner = false;
> +    }
> +}
> +
> +/* Main function of this pass.  Find and propagate all three types of copy
> +   statements (see pass description above).
> +
> +   This is an implementation of an algorithm from the paper Simple and
> +   Efficient Construction of Static Single Assignmemnt Form[1].  It is based
> +   on strongly-connected components (SCCs) in dataflow graph.  The original
> +   algorithm only considers PHI statements.  We extend it to also consider
> +   assignment statements of type _2 = _1;.
> +
> +   The algorithm is based on this definition of a set of redundant PHIs[1]:
> +
> +     A non-empty set P of PHI functions is redundant iff the PHI functions just
> +     reference each other or one other value
> +
> +   It uses this lemma[1]:
> +
> +     Let P be a redundant set of PHI functions.  Then there is a
> +     strongly-connected component S subset of P that is also redundant.
> +
> +   The algorithm works in this way:
> +
> +     1 Find SCCs
> +     2 For each SCC S in topological order:
> +     3   Construct set 'inner' of statements that only have other statements
> +     from S on their right hand side
> +     4   Construct set 'outer' of values that originate outside S and appear on
> +     right hand side of some statement from S
> +     5   If |outer| = 1, outer only contains a value v.  Statements in S only
> +     refer to each other or to v -- they are redundant.  Propagate v.
> +     Else, recurse on statements in inner.
> +
> +   The implementation is non-recursive.
> +
> +   References:
> +
> +     [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
> +     Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
> +     Section 3.2.  */
> +
> +static void
> +sccopy_propagate ()
> +{
> +  auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy ();
> +  scc_discovery discovery;
> +
> +  auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (useful_stmts);
> +
> +  while (!worklist.is_empty ())
> +    {
> +      vec<gimple *> scc = worklist.pop ();
> +
> +      auto_vec<gimple *> inner;
> +      hash_set<tree> outer_ops;
> +      tree last_outer_op = NULL_TREE;
> +
> +      /* Prepare hash set of PHIs in scc to query later.  */
> +      hash_set<gimple *> scc_set;
> +      for (gimple *stmt : scc)
> +    scc_set.add (stmt);
> +
> +      for (gimple *stmt : scc)
> +    {
> +      bool is_inner = true;
> +
> +      gphi *phi;
> +      tree op;
> +
> +      switch (gimple_code (stmt))
> +        {
> +          case GIMPLE_PHI:
> +        phi = as_a <gphi *> (stmt);
> +        unsigned j;
> +        for (j = 0; j < gimple_phi_num_args (phi); j++)
> +          {
> +            op = gimple_phi_arg_def (phi, j);
> +            sccopy_visit_op (op, outer_ops, scc_set, is_inner,
> +                   last_outer_op);
> +          }
> +        break;
> +          case GIMPLE_ASSIGN:
> +        op = gimple_assign_rhs1 (stmt);
> +        sccopy_visit_op (op, outer_ops, scc_set, is_inner,
> +                   last_outer_op);
> +        break;
> +          default:
> +        gcc_unreachable ();
> +        }
> +
> +      if (is_inner)
> +        inner.safe_push (stmt);
> +    }
> +
> +      if (outer_ops.elements () == 1)
> +    {
> +      /* The only operand in outer_ops.  */
> +      tree outer_op = last_outer_op;
> +      replace_scc_by_value (scc, outer_op);
> +    }
> +      else if (outer_ops.elements () > 1)
> +    {
> +      /* Add inner sccs to worklist.  */
> +      auto_vec<vec<gimple *>> inner_sccs
> +        = discovery.compute_sccs (inner);
> +      for (vec<gimple *> inner_scc : inner_sccs)
> +        worklist.safe_push (inner_scc);
> +    }
> +      else
> +    gcc_unreachable ();
> +
> +      scc.release ();
> +    }
> +}
> +
> +/* Called when pass execution starts.  */
> +
> +static void
> +init_sccopy (void)
> +{
> +  /* For propagated statements.  */
> +  dead_stmts = BITMAP_ALLOC (NULL);
> +}
> +
> +/* Called before pass execution ends.  */
> +
> +static void
> +finalize_sccopy (void)
> +{
> +  /* Remove all propagated statements.  */
> +  simple_dce_from_worklist (dead_stmts);
> +  BITMAP_FREE (dead_stmts);
> +
> +  /* Propagating a constant may create dead eh edges.  */
> +  basic_block bb;
> +  FOR_EACH_BB_FN (bb, cfun)
> +    gimple_purge_dead_eh_edges (bb);
> +}
> +
> +namespace {
> +
> +const pass_data pass_data_sccopy =
> +{
> +  GIMPLE_PASS, /* type */
> +  "sccopy", /* name */
> +  OPTGROUP_NONE, /* optinfo_flags */
> +  TV_NONE, /* tv_id */
> +  ( PROP_cfg | PROP_ssa ), /* properties_required */
> +  0, /* properties_provided */
> +  0, /* properties_destroyed */
> +  0, /* todo_flags_start */
> +  TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
> +};
> +
> +class pass_sccopy : public gimple_opt_pass
> +{
> +public:
> +  pass_sccopy (gcc::context *ctxt)
> +    : gimple_opt_pass (pass_data_sccopy, ctxt)
> +  {}
> +
> +  /* opt_pass methods: */
> +  virtual bool gate (function *) { return true; }
> +  virtual unsigned int execute (function *);
> +  opt_pass * clone () final override { return new pass_sccopy (m_ctxt); }
> +}; // class pass_sccopy
> +
> +unsigned
> +pass_sccopy::execute (function *)
> +{
> +  init_sccopy ();
> +  sccopy_propagate ();
> +  finalize_sccopy ();
> +  return 0;
> +}
> +
> +} // anon namespace
> +
> +gimple_opt_pass *
> +make_pass_sccopy (gcc::context *ctxt)
> +{
> +  return new pass_sccopy (ctxt);
> +}
> diff --git a/gcc/passes.def b/gcc/passes.def
> index 1e1950bdb39..048ad3ee7a5 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -100,6 +100,7 @@ along with GCC; see the file COPYING3.  If not see
>      NEXT_PASS (pass_if_to_switch);
>      NEXT_PASS (pass_convert_switch);
>      NEXT_PASS (pass_cleanup_eh);
> +      NEXT_PASS (pass_sccopy);
>      NEXT_PASS (pass_profile);
>      NEXT_PASS (pass_local_pure_const);
>      NEXT_PASS (pass_modref);
> @@ -368,6 +369,7 @@ along with GCC; see the file COPYING3.  If not see
>     However, this also causes us to misdiagnose cases that should be
>     real warnings (e.g., testsuite/gcc.dg/pr18501.c).  */
>       NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */);
> +      NEXT_PASS (pass_sccopy);
>       NEXT_PASS (pass_tail_calls);
>       /* Split critical edges before late uninit warning to reduce the
>          number of false positives from it.  */
> diff --git a/gcc/testsuite/gcc.dg/sccopy-1.c b/gcc/testsuite/gcc.dg/sccopy-1.c
> new file mode 100644
> index 00000000000..1e61a6b320e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/sccopy-1.c
> @@ -0,0 +1,78 @@
> +/* { dg-do compile } */
> +/* { dg-options "-fgimple -fdump-tree-sccopy -O2" } */
> +/* { dg-final { scan-tree-dump "Replacing SCC of size 2" "sccopy1" } } */
> +
> +int __GIMPLE (ssa, startwith ("sccopy"))
> +main ()
> +{
> +  int a;
> +  int y;
> +  int x;
> +  int _1;
> +  int _2;
> +  int _13;
> +
> +  __BB(2):
> +  if (x_7(D) == 5)
> +    goto __BB3;
> +  else
> +    goto __BB4;
> +
> +  __BB(3):
> +  a_10 = x_7(D);
> +  goto __BB5;
> +
> +  __BB(4):
> +  a_9 = y_8(D);
> +  goto __BB5;
> +
> +  __BB(5):
> +  a_3 = __PHI (__BB3: a_10, __BB4: a_9);
> +  if (x_7(D) == y_8(D))
> +    goto __BB6;
> +  else
> +    goto __BB11;
> +
> +  __BB(6):
> +  a_11 = a_3 + 1;
> +  goto __BB7;
> +
> +  __BB(7):
> +  a_4 = __PHI (__BB6: a_11, __BB11: a_6);
> +label1:
> +  if (x_7(D) != y_8(D))
> +    goto __BB8;
> +  else
> +    goto __BB10;
> +
> +  __BB(8):
> +  goto __BB9;
> +
> +  __BB(9):
> +  a_12 = __PHI (__BB8: a_4, __BB10: a_5);
> +  goto __BB10;
> +
> +  __BB(10,loop_header(1)):
> +  a_5 = __PHI (__BB7: a_4, __BB9: a_12);
> +label2:
> +  _1 = y_8(D) * 2;
> +  if (x_7(D) == _1)
> +    goto __BB9;
> +  else
> +    goto __BB11;
> +
> +  __BB(11):
> +  a_6 = __PHI (__BB5: a_3, __BB10: a_5);
> +  _2 = x_7(D) * 3;
> +  if (y_8(D) == _2)
> +    goto __BB7;
> +  else
> +    goto __BB12;
> +
> +  __BB(12):
> +  _13 = 0;
> +  return _13;
> +
> +}
> +
> +
> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> index 09e6ada5b2f..94a48461590 100644
> --- a/gcc/tree-pass.h
> +++ b/gcc/tree-pass.h
> @@ -399,6 +399,7 @@ extern gimple_opt_pass *make_pass_iv_optimize (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_tree_loop_done (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt);
> +extern gimple_opt_pass *make_pass_sccopy (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt);
> extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt);
> --
> 2.43.0
>
  

Successfully bootstrapped and regtested on x86_64-linux. Will push to master.

Filip