Fix PR 65177: diamonds are not valid execution threads for jump threading

[Sebastian Pop <sebpop at gmail dot com>]

Hi,

the attached patch fixes PR 65177 in which the code generator of FSM jump thread
would create a diamond on the copied path: see https://gcc.gnu.org/PR65177#c18
for a detailed description.

The patch is renaming SEME into jump_thread as the notion of SEME is more
general than the special case that we are interested in, in the case of
jump-threading: an execution thread to be jump-threaded has the property that
each node on the path has exactly one predecessor, disallowing any other
control flow like diamonds or back-edge loops within the SEME region.

The patch passes regstrap on x86-64-linux, and fixes the make check of hmmer.
Ok to commit?

Thanks,
Sebastian

>From 8c82e8b8c7d864c009bb7a116faf4acf64954704 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 17 Mar 2015 20:28:19 +0100
Subject: [PATCH] fix 65177

	PR tree-optimization/65177
	* cfghooks.c (bb_in_bbs): New.
	(copy_bbs): Add parameter make_jump_thread.
	* cfghooks.h (copy_bbs): Update definition.
	* cfgloopmanip.c (duplicate_loop_to_header_edge): Update use of
	copy_bbs.
	* trans-mem.c (ipa_uninstrument_transaction): Same.
	* tree-cfg.c (gimple_duplicate_sese_region): Same.
	(gimple_duplicate_sese_tail): Same.
	* tree-vect-loop-manip.c (slpeel_tree_duplicate_loop_to_edge_cfg): Same.
	* tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.

---
 gcc/cfghooks.c              |   39 +++++++++++++++++++++++++++++++++++++--
 gcc/cfghooks.h              |    2 +-
 gcc/cfgloopmanip.c          |    2 +-
 gcc/trans-mem.c             |    2 +-
 gcc/tree-cfg.c              |    4 ++--
 gcc/tree-ssa-threadupdate.c |   31 ++++++++-----------------------
 gcc/tree-vect-loop-manip.c  |    2 +-
 7 files changed, 51 insertions(+), 31 deletions(-)

diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
index abeab8c..1a9e2f9 100644
--- a/gcc/cfghooks.c
+++ b/gcc/cfghooks.c
@@ -1300,6 +1300,18 @@ end:
   return ret;
 }
 
+/* Return true when BB is one of the first N items in BBS.  */
+
+static inline bool
+bb_in_bbs (basic_block bb, basic_block *bbs, int n)
+{
+  for (int i = 0; i < n; i++)
+    if (bb == bbs[i])
+      return true;
+
+  return false;
+}
+
 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
    are placed into array NEW_BBS in the same order.  Edges from basic blocks
    in BBS are also duplicated and copies of those that lead into BBS are
@@ -1321,12 +1333,16 @@ end:
    also in the same order.
 
    Newly created basic blocks are put after the basic block AFTER in the
-   instruction stream, and the order of the blocks in BBS array is preserved.  */
+   instruction stream, and the order of the blocks in BBS array is preserved.
+
+   When MAKE_JUMP_THREAD is true, only redirect edges to consecutive elements of
+   BBS.  */
 
 void
 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
 	  edge *edges, unsigned num_edges, edge *new_edges,
-	  struct loop *base, basic_block after, bool update_dominance)
+	  struct loop *base, basic_block after, bool update_dominance,
+	  bool make_jump_thread)
 {
   unsigned i, j;
   basic_block bb, new_bb, dom_bb;
@@ -1385,6 +1401,25 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
 
 	  if (!(e->dest->flags & BB_DUPLICATED))
 	    continue;
+
+	  if (make_jump_thread)
+	    {
+	      /* When creating a jump-thread, we only redirect edges to
+		 consecutive basic blocks.  */
+	      if (i + 1 < n)
+		{
+		  if (e->dest != bbs[i + 1])
+		    continue;
+		}
+	      else
+		{
+		  /* Do not jump back into the jump-thread path from the last
+		     BB.  */
+		  if (bb_in_bbs (e->dest, bbs, n - 1))
+		    continue;
+		}
+	    }
+
 	  redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
 	}
     }
diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h
index 4a1340e..9a17180 100644
--- a/gcc/cfghooks.h
+++ b/gcc/cfghooks.h
@@ -238,7 +238,7 @@ extern void lv_add_condition_to_bb (basic_block, basic_block, basic_block,
 extern bool can_copy_bbs_p (basic_block *, unsigned);
 extern void copy_bbs (basic_block *, unsigned, basic_block *,
 		      edge *, unsigned, edge *, struct loop *,
-		      basic_block, bool);
+		      basic_block, bool, bool);
 
 void account_profile_record (struct profile_record *, int);
 
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 45cc85d..e987b6b 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -1337,7 +1337,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e,
 
       /* Copy bbs.  */
       copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
-		place_after, true);
+		place_after, true, false);
       place_after = new_spec_edges[SE_LATCH]->src;
 
       if (flags & DLTHE_RECORD_COPY_NUMBER)
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index 078c2da..eb88735 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -4162,7 +4162,7 @@ ipa_uninstrument_transaction (struct tm_region *region,
   basic_block *new_bbs = XNEWVEC (basic_block, n);
 
   copy_bbs (queue.address (), n, new_bbs, NULL, 0, NULL, NULL, transaction_bb,
-	    true);
+	    true, false);
   edge e = make_edge (transaction_bb, new_bbs[0], EDGE_TM_UNINSTRUMENTED);
   add_phi_args_after_copy (new_bbs, n, e);
 
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 006bc08..e769fb7 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -6071,7 +6071,7 @@ gimple_duplicate_sese_region (edge entry, edge exit,
     }
 
   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
-	    split_edge_bb_loc (entry), update_dominance);
+	    split_edge_bb_loc (entry), update_dominance, false);
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
@@ -6240,7 +6240,7 @@ gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNU
     }
 
   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
-	    split_edge_bb_loc (exit), true);
+	    split_edge_bb_loc (exit), true, false);
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 7a159bb..96a83fa 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2328,30 +2328,16 @@ bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED)
   return false;
 }
 
-/* Verify that the REGION is a Single Entry Multiple Exits region: make sure no
-   edge other than ENTRY is entering the REGION.  */
+/* Verify that the REGION is a valid jump thread.  A jump thread is a special
+   case of SEME Single Entry Multiple Exits region in which all nodes in the
+   REGION have exactly one incoming edge.  The only exception is the first block
+   that may not have been connected to the rest of the cfg yet.  */
 
 DEBUG_FUNCTION void
-verify_seme (edge entry, basic_block *region, unsigned n_region)
+verify_jump_thread (basic_block *region, unsigned n_region)
 {
-  bitmap bbs = BITMAP_ALLOC (NULL);
-
-  for (unsigned i = 0; i < n_region; i++)
-    bitmap_set_bit (bbs, region[i]->index);
-
   for (unsigned i = 0; i < n_region; i++)
-    {
-      edge e;
-      edge_iterator ei;
-      basic_block bb = region[i];
-
-      /* All predecessors other than ENTRY->src should be in the region.  */
-      for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ei_next (&ei))
-	if (e != entry)
-	  gcc_assert (bitmap_bit_p (bbs, e->src->index));
-    }
-
-  BITMAP_FREE (bbs);
+    gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
 }
 
 /* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic
@@ -2428,7 +2414,7 @@ duplicate_seme_region (edge entry, edge exit,
     }
 
   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
-	    split_edge_bb_loc (entry), 0);
+	    split_edge_bb_loc (entry), false, true);
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
@@ -2445,8 +2431,7 @@ duplicate_seme_region (edge entry, edge exit,
     }
 
 #ifdef ENABLE_CHECKING
-  /* Make sure no edge other than ENTRY is entering the copied region.  */
-  verify_seme (entry, region_copy, n_region);
+  verify_jump_thread (region_copy, n_region);
 #endif
 
   /* Remove the last branch in the jump thread path.  */
diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
index a344a49..c561f46 100644
--- a/gcc/tree-vect-loop-manip.c
+++ b/gcc/tree-vect-loop-manip.c
@@ -814,7 +814,7 @@ slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop,
   exit = single_exit (scalar_loop);
   copy_bbs (bbs, scalar_loop->num_nodes + 1, new_bbs,
 	    &exit, 1, &new_exit, NULL,
-	    e->src, true);
+	    e->src, true, false);
   exit = single_exit (loop);
   basic_block new_preheader = new_bbs[scalar_loop->num_nodes];
 
-- 
1.7.2.5