diff mbox

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

Message ID 20150318223541.GA17168@f1.c.bardezibar.internal
State New
Headers show

Commit Message

Sebastian Pop March 18, 2015, 10:35 p.m. UTC 
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

Comments

Richard Biener March 19, 2015, 9:16 a.m. UTC | #1 
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
Jeff Law March 23, 2015, 5:37 a.m. UTC | #2 
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
diff mbox

Patch

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