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

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

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 673 bytes --]

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

[-- Attachment #2: 0001-fix-65177.patch --]
[-- Type: text/x-diff, Size: 8052 bytes --]

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

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

[Richard Biener]

On Wed, Mar 18, 2015 at 11:35 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> 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?

I don't like the special-casing in copy_bbs (with bb_in_bbs doing a
linear walk anyway...).
Is the first test

+             /* When creating a jump-thread, we only redirect edges to
+                consecutive basic blocks.  */
+             if (i + 1 < n)
+               {
+                 if (e->dest != bbs[i + 1])
+                   continue;

not really always the case for jump threads?  copy_bbs doesn't impose
any restriction
on ordering on bbs[], so it seems to be a speciality of the caller.

+               {
+                 /* Do not jump back into the jump-thread path from the last
+                    BB.  */
+                 if (bb_in_bbs (e->dest, bbs, n - 1))
+                   continue;

this one sounds easier to ensure in the caller as well - just remove the extra
unwanted edge.

That said - please instead fixup after copy_bbs in duplicate_seme_region.

Richard.

> Thanks,
> Sebastian

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

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 298 bytes --]

Richard Biener wrote:
> please instead fixup after copy_bbs in duplicate_seme_region.
> 

Thanks for the review.
Attached patch that does not modify copy_bbs.
Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp

Full bootstrap and regtest in progress on x86_64-linux.  Ok for trunk?

[-- Attachment #2: 0001-diamonds-are-not-valid-execution-threads-for-jump-th.patch --]
[-- Type: text/x-diff, Size: 5690 bytes --]

From 8f1516235bce3e1c4f359149dcc546d813ed7817 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 17 Mar 2015 20:28:19 +0100
Subject: [PATCH] diamonds are not valid execution threads for jump threading

	PR tree-optimization/65177
	* tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.
	(bb_in_bbs): New.
	(duplicate_seme_region): Renamed duplicate_thread_path.  Redirect all
	edges not adjacent on the path to the original code.
---
 gcc/tree-ssa-threadupdate.c |   93 +++++++++++++++++++++++++++++++------------
 1 files changed, 67 insertions(+), 26 deletions(-)

diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 7a159bb..610e807 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2328,36 +2328,32 @@ 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);
+    gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
+}
 
-  for (unsigned i = 0; i < n_region; i++)
-    {
-      edge e;
-      edge_iterator ei;
-      basic_block bb = region[i];
+/* Return true when BB is one of the first N items in BBS.  */
 
-      /* 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));
-    }
+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;
 
-  BITMAP_FREE (bbs);
+  return false;
 }
 
-/* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic
-   blocks).  The ENTRY edge is redirected to the duplicate of the region.  If
-   REGION is not a Single Entry region, ignore any incoming edges other than
-   ENTRY: this makes the copied region a Single Entry region.
+/* Duplicates a jump-thread path of N_REGION basic blocks.
+   The ENTRY edge is redirected to the duplicate of the region.
 
    Remove the last conditional statement in the last basic block in the REGION,
    and create a single fallthru edge pointing to the same destination as the
@@ -2369,7 +2365,7 @@ verify_seme (edge entry, basic_block *region, unsigned n_region)
    Returns false if it is unable to copy the region, true otherwise.  */
 
 static bool
-duplicate_seme_region (edge entry, edge exit,
+duplicate_thread_path (edge entry, edge exit,
 		       basic_block *region, unsigned n_region,
 		       basic_block *region_copy)
 {
@@ -2428,7 +2424,53 @@ 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);
+
+  /* Fix up: copy_bbs redirects all edges pointing to copied blocks.  The
+     following code ensures that all the edges exiting the jump-thread path are
+     redirected back to the original code: these edges are exceptions
+     invalidating the property that is propagated by executing all the blocks of
+     the jump-thread path in order.  */
+
+  for (i = 0; i < n_region; i++)
+    {
+      edge e;
+      edge_iterator ei;
+      basic_block bb = region_copy[i];
+
+      if (single_succ_p (bb))
+	{
+	  /* Make sure the successor is the next node in the path.  */
+	  gcc_assert (i + 1 == n_region
+		      || region_copy[i + 1] == single_succ_edge (bb)->dest);
+	  continue;
+	}
+
+      /* Special case the last block on the path: make sure that it does not
+	 jump back on the copied path.  */
+      if (i + 1 == n_region)
+	{
+	  FOR_EACH_EDGE (e, ei, bb->succs)
+	    if (bb_in_bbs (e->dest, region_copy, n_region - 1))
+	      {
+		basic_block orig = get_bb_original (e->dest);
+		if (orig)
+		  redirect_edge_and_branch_force (e, orig);
+	      }
+	  continue;
+	}
+
+      /* Redirect all other edges jumping to non-adjacent blocks back to the
+	 original code.  */
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (region_copy[i + 1] != e->dest)
+	  {
+	    basic_block orig = get_bb_original (e->dest);
+	    if (orig)
+	      redirect_edge_and_branch_force (e, orig);
+	  }
+    }
+
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
@@ -2445,8 +2487,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.  */
@@ -2550,7 +2591,7 @@ thread_through_all_blocks (bool may_peel_loop_headers)
       for (unsigned int j = 0; j < len - 1; j++)
 	region[j] = (*path)[j]->e->dest;
 
-      if (duplicate_seme_region (entry, exit, region, len - 1, NULL))
+      if (duplicate_thread_path (entry, exit, region, len - 1, NULL))
 	{
 	  /* We do not update dominance info.  */
 	  free_dominance_info (CDI_DOMINATORS);
-- 
1.7.2.5

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

[Richard Biener]

On Thu, Mar 19, 2015 at 8:54 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> Richard Biener wrote:
>> please instead fixup after copy_bbs in duplicate_seme_region.
>>
>
> Thanks for the review.
> Attached patch that does not modify copy_bbs.
> Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp
>
> Full bootstrap and regtest in progress on x86_64-linux.  Ok for trunk?

Looks good to me.  Please also add a testcase.

Thanks,
Richard.

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

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 561 bytes --]

Richard Biener wrote:
> On Thu, Mar 19, 2015 at 8:54 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> > Richard Biener wrote:
> >> please instead fixup after copy_bbs in duplicate_seme_region.
> >>
> >
> > Thanks for the review.
> > Attached patch that does not modify copy_bbs.
> > Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp
> >
> > Full bootstrap and regtest in progress on x86_64-linux.  Ok for trunk?
> 
> Looks good to me.  Please also add a testcase.

Attached.  I will wait to commit until I have a green light from Jeff.

Sebastian

[-- Attachment #2: 0001-diamonds-are-not-valid-execution-threads-for-jump-th.patch --]
[-- Type: text/x-diff, Size: 6933 bytes --]

From f57f9a44717406cd148b3f432565654c36b33f2f Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Fri, 20 Mar 2015 18:12:47 +0100
Subject: [PATCH] diamonds are not valid execution threads for jump threading

	PR tree-optimization/65177
	* tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.
	(bb_in_bbs): New.
	(duplicate_seme_region): Renamed duplicate_thread_path.  Redirect all
	edges not adjacent on the path to the original code.

	* gcc.dg/tree-ssa/ssa-dom-thread-10.c: New.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c |   24 ++++++
 gcc/tree-ssa-threadupdate.c                       |   93 +++++++++++++++------
 2 files changed, 91 insertions(+), 26 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c
new file mode 100644
index 0000000..4acf580
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c
@@ -0,0 +1,24 @@
+/* PR 65177 */
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+typedef struct p7_profile_s {} P7_PROFILE;
+enum p7t_statetype_e {
+  p7T_S = 4,   p7T_N = 5,   p7T_E = 7,   p7T_C = 8,   p7T_J = 10, };
+typedef struct p7_trace_s {} P7_TRACE;
+typedef struct p7_gmx_s {
+  int L;
+} P7_GMX;
+static inline int select_c(const P7_PROFILE *gm, const P7_GMX *pp, const P7_GMX *gx, int i) {
+  float path[2];
+  return ((path[0] > path[1]) ? p7T_C : p7T_E);
+}
+void p7_GOATrace(const P7_PROFILE *gm, const P7_GMX *pp, const P7_GMX *gx, P7_TRACE *tr) {
+  int i = gx->L;
+  int sprv, scur;
+  while (sprv != p7T_S)     {
+    switch (sprv) {       case p7T_C: scur = select_c(gm, pp, gx, i); break;       }
+    if ( (scur == p7T_N || scur == p7T_J || scur == p7T_C) && scur == sprv) i--;
+    sprv = scur;
+  }
+}
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 7a159bb..610e807 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2328,36 +2328,32 @@ 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);
+    gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
+}
 
-  for (unsigned i = 0; i < n_region; i++)
-    {
-      edge e;
-      edge_iterator ei;
-      basic_block bb = region[i];
+/* Return true when BB is one of the first N items in BBS.  */
 
-      /* 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));
-    }
+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;
 
-  BITMAP_FREE (bbs);
+  return false;
 }
 
-/* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic
-   blocks).  The ENTRY edge is redirected to the duplicate of the region.  If
-   REGION is not a Single Entry region, ignore any incoming edges other than
-   ENTRY: this makes the copied region a Single Entry region.
+/* Duplicates a jump-thread path of N_REGION basic blocks.
+   The ENTRY edge is redirected to the duplicate of the region.
 
    Remove the last conditional statement in the last basic block in the REGION,
    and create a single fallthru edge pointing to the same destination as the
@@ -2369,7 +2365,7 @@ verify_seme (edge entry, basic_block *region, unsigned n_region)
    Returns false if it is unable to copy the region, true otherwise.  */
 
 static bool
-duplicate_seme_region (edge entry, edge exit,
+duplicate_thread_path (edge entry, edge exit,
 		       basic_block *region, unsigned n_region,
 		       basic_block *region_copy)
 {
@@ -2428,7 +2424,53 @@ 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);
+
+  /* Fix up: copy_bbs redirects all edges pointing to copied blocks.  The
+     following code ensures that all the edges exiting the jump-thread path are
+     redirected back to the original code: these edges are exceptions
+     invalidating the property that is propagated by executing all the blocks of
+     the jump-thread path in order.  */
+
+  for (i = 0; i < n_region; i++)
+    {
+      edge e;
+      edge_iterator ei;
+      basic_block bb = region_copy[i];
+
+      if (single_succ_p (bb))
+	{
+	  /* Make sure the successor is the next node in the path.  */
+	  gcc_assert (i + 1 == n_region
+		      || region_copy[i + 1] == single_succ_edge (bb)->dest);
+	  continue;
+	}
+
+      /* Special case the last block on the path: make sure that it does not
+	 jump back on the copied path.  */
+      if (i + 1 == n_region)
+	{
+	  FOR_EACH_EDGE (e, ei, bb->succs)
+	    if (bb_in_bbs (e->dest, region_copy, n_region - 1))
+	      {
+		basic_block orig = get_bb_original (e->dest);
+		if (orig)
+		  redirect_edge_and_branch_force (e, orig);
+	      }
+	  continue;
+	}
+
+      /* Redirect all other edges jumping to non-adjacent blocks back to the
+	 original code.  */
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (region_copy[i + 1] != e->dest)
+	  {
+	    basic_block orig = get_bb_original (e->dest);
+	    if (orig)
+	      redirect_edge_and_branch_force (e, orig);
+	  }
+    }
+
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
@@ -2445,8 +2487,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.  */
@@ -2550,7 +2591,7 @@ thread_through_all_blocks (bool may_peel_loop_headers)
       for (unsigned int j = 0; j < len - 1; j++)
 	region[j] = (*path)[j]->e->dest;
 
-      if (duplicate_seme_region (entry, exit, region, len - 1, NULL))
+      if (duplicate_thread_path (entry, exit, region, len - 1, NULL))
 	{
 	  /* We do not update dominance info.  */
 	  free_dominance_info (CDI_DOMINATORS);
-- 
1.7.2.5

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

[Jeff Law]

On 03/20/2015 12:17 PM, Sebastian Pop wrote:
> Richard Biener wrote:
>> On Thu, Mar 19, 2015 at 8:54 PM, Sebastian Pop <sebpop@gmail.com> wrote:
>>> Richard Biener wrote:
>>>> please instead fixup after copy_bbs in duplicate_seme_region.
>>>>
>>>
>>> Thanks for the review.
>>> Attached patch that does not modify copy_bbs.
>>> Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp
>>>
>>> Full bootstrap and regtest in progress on x86_64-linux.  Ok for trunk?
>>
>> Looks good to me.  Please also add a testcase.
>
> Attached.  I will wait to commit until I have a green light from Jeff.
Sorry, dealing with some non-technical stuff right now.  I should have 
time to look at this over the weekend.

jeff

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

[Jeff Law]

On 03/19/2015 03:16 AM, Richard Biener wrote:
> On Wed, Mar 18, 2015 at 11:35 PM, Sebastian Pop <sebpop@gmail.com> wrote:
>> 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?
>
> I don't like the special-casing in copy_bbs (with bb_in_bbs doing a
> linear walk anyway...).
> Is the first test
>
> +             /* When creating a jump-thread, we only redirect edges to
> +                consecutive basic blocks.  */
> +             if (i + 1 < n)
> +               {
> +                 if (e->dest != bbs[i + 1])
> +                   continue;
>
> not really always the case for jump threads?  copy_bbs doesn't impose
> any restriction
> on ordering on bbs[], so it seems to be a speciality of the caller.
Right.  The assumption of orderings was the initial thing that jumped 
out at me.  While it may be the case that in practice we're going to be 
presented with blocks in that kind of order, depending on it seems unwise.

Jeff

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

[Jeff Law]

On 03/19/2015 01:54 PM, Sebastian Pop wrote:
> Richard Biener wrote:
>> please instead fixup after copy_bbs in duplicate_seme_region.
>>
>
> Thanks for the review.
> Attached patch that does not modify copy_bbs.
> Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp
>
> Full bootstrap and regtest in progress on x86_64-linux.  Ok for trunk?
I'm going to have to find time tomorrow to wrap this up.  I've got a 
morning full of meetings, then I on a plane for the east coast for the 
rest of the day.  I'm in an exit row seat for the 2nd leg, so there 
ought to be enough room to open my laptop and poke at this.

jeff

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

[Jeff Law]

On 03/19/15 13:54, Sebastian Pop wrote:
> Richard Biener wrote:
>> >please instead fixup after copy_bbs in duplicate_seme_region.
>> >
> Thanks for the review.
> Attached patch that does not modify copy_bbs.
> Fixes make check in hmmer and make check RUNTESTFLAGS=tree-ssa.exp
>
> Full bootstrap and regtest in progress on x86_64-linux.  Ok for trunk?
>
>
> 0001-diamonds-are-not-valid-execution-threads-for-jump-th.patch
>
>
>  From 8f1516235bce3e1c4f359149dcc546d813ed7817 Mon Sep 17 00:00:00 2001
> From: Sebastian Pop<sebpop@gmail.com>
> Date: Tue, 17 Mar 2015 20:28:19 +0100
> Subject: [PATCH] diamonds are not valid execution threads for jump threading
>
> 	PR tree-optimization/65177
> 	* tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.
> 	(bb_in_bbs): New.
> 	(duplicate_seme_region): Renamed duplicate_thread_path.  Redirect all
> 	edges not adjacent on the path to the original code.
OK for the trunk.  Though I think there's some stage1 refactoring that 
we're going to want to do.

Specifically, it seems to me that copy_bbs should be refactored into 
copy_bbs and copy_bbs_for_threading or somesuch.  Where those routines 
call into refactored common subroutines, but obviously handle wiring up 
the outgoing edges from the copied blocks differently.

The goal would be to eliminate the overly complex block copy/CFG update 
scheme in tree-ssa-threadupdate.c as part of a larger project to convert 
to a backward threader that can run independently of DOM.

Jeff

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

[Sebastian Pop]

Jeff Law wrote:
> >	PR tree-optimization/65177
> >	* tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.
> >	(bb_in_bbs): New.
> >	(duplicate_seme_region): Renamed duplicate_thread_path.  Redirect all
> >	edges not adjacent on the path to the original code.
> OK for the trunk.  

Committed r221675.

> Though I think there's some stage1 refactoring that we're going to want to do.

Agreed.

> Specifically, it seems to me that copy_bbs should be refactored into
> copy_bbs and copy_bbs_for_threading or somesuch.  Where those
> routines call into refactored common subroutines, but obviously
> handle wiring up the outgoing edges from the copied blocks
> differently.
> 

That would be a good cleanup: I don't like to arbitrarily redirect edges in
copy_bbs just to redirect them back to their initial place in the caller.

> The goal would be to eliminate the overly complex block copy/CFG
> update scheme in tree-ssa-threadupdate.c as part of a larger project
> to convert to a backward threader that can run independently of DOM.

I have a start of a patch for that cleanup, it currently runs wild as it would
replace the existing threadupdate code generator with a call to the new
duplicate_thread_path.  I think we should take smaller more manageable steps to
ease the review and to not destabilize the jump-threader.  In particular I think
we should have both code generators for a while and turn one on/off with an option.

Sebastian

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

[Jeff Law]

On 03/25/2015 05:09 PM, Sebastian Pop wrote:
>> Specifically, it seems to me that copy_bbs should be refactored into
>> copy_bbs and copy_bbs_for_threading or somesuch.  Where those
>> routines call into refactored common subroutines, but obviously
>> handle wiring up the outgoing edges from the copied blocks
>> differently.
>>
>
> That would be a good cleanup: I don't like to arbitrarily redirect edges in
> copy_bbs just to redirect them back to their initial place in the caller.
Exactly.

>
>> The goal would be to eliminate the overly complex block copy/CFG
>> update scheme in tree-ssa-threadupdate.c as part of a larger project
>> to convert to a backward threader that can run independently of DOM.
>
> I have a start of a patch for that cleanup, it currently runs wild as it would
> replace the existing threadupdate code generator with a call to the new
> duplicate_thread_path.  I think we should take smaller more manageable steps to
> ease the review and to not destabilize the jump-threader.  In particular I think
> we should have both code generators for a while and turn one on/off with an option.
I hadn't planned on supporting both with an option, I'd rather make the 
switch and not look back :-)   An option just adds maintenance burdens 
(supporting both approaches) and doesn't actually help the end users 
(though it would help us as developers).

Regardless, probably the first step is a common API for the two path 
duplication approaches.

Jeff

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

[Richard Biener]

On Thu, Mar 26, 2015 at 4:50 PM, Jeff Law <law@redhat.com> wrote:
> On 03/25/2015 05:09 PM, Sebastian Pop wrote:
>>>
>>> Specifically, it seems to me that copy_bbs should be refactored into
>>> copy_bbs and copy_bbs_for_threading or somesuch.  Where those
>>> routines call into refactored common subroutines, but obviously
>>> handle wiring up the outgoing edges from the copied blocks
>>> differently.
>>>
>>
>> That would be a good cleanup: I don't like to arbitrarily redirect edges
>> in
>> copy_bbs just to redirect them back to their initial place in the caller.
>
> Exactly.
>
>>
>>> The goal would be to eliminate the overly complex block copy/CFG
>>> update scheme in tree-ssa-threadupdate.c as part of a larger project
>>> to convert to a backward threader that can run independently of DOM.
>>
>>
>> I have a start of a patch for that cleanup, it currently runs wild as it
>> would
>> replace the existing threadupdate code generator with a call to the new
>> duplicate_thread_path.  I think we should take smaller more manageable
>> steps to
>> ease the review and to not destabilize the jump-threader.  In particular I
>> think
>> we should have both code generators for a while and turn one on/off with
>> an option.
>
> I hadn't planned on supporting both with an option, I'd rather make the
> switch and not look back :-)   An option just adds maintenance burdens
> (supporting both approaches) and doesn't actually help the end users (though
> it would help us as developers).
>
> Regardless, probably the first step is a common API for the two path
> duplication approaches.

Yeah, and refactoring copy_bbs so that the actual edge duplication happens
in another function (thus we can have two of them).

Note we have way too many copy-XYZ APIs/workers on GIMPLE already.

I was also playing with the idea to support value-numbering the stmts
on-the-fly as we copy them and use this for cost estimation of copies
(ok, well - basically do the copy and then either throw it away again
or accept it).
I thought about applying this to loop unrolling, but obviously this also applies
to any block duplication we do during jump threading.

Richard.

> Jeff

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

[Jeff Law]

On 03/27/2015 02:53 AM, Richard Biener wrote:
>
> Yeah, and refactoring copy_bbs so that the actual edge duplication happens
> in another function (thus we can have two of them).
Exactly.


>
> I was also playing with the idea to support value-numbering the stmts
> on-the-fly as we copy them and use this for cost estimation of copies
> (ok, well - basically do the copy and then either throw it away again
> or accept it).
> I thought about applying this to loop unrolling, but obviously this also applies
> to any block duplication we do during jump threading.
It'd definitely be useful in threading.  It's often the case that PHIs 
in the duplicates are degenerates and we can/should cprop them away and 
perform resultant simplifications that propagation enables.

If we could do that integrated with the actual duplication, then we'd be 
able to drop the phi-only cprop pass which exists solely to clean up 
that stuff.

jeff