A new copy propagation and PHI elimination pass

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>

5 files changed, 762 insertions, 0 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f284c13..754eceb 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 0000000..ac5ec32
--- /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 d3fccdf..43b416f 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -101,6 +101,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);
@@ -370,6 +371,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 0000000..1e61a6b
--- /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 de2820b..52fd57f 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);