This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Don't bypass blocks with multiple latch edges (PR middle-end/54838)


In this PR, for the C testcase, in .cse1 we have:

            ENTRY    
             |   
             |   
             2   
             |   
             |   
   +-------- 4 ----------+
   |        / \          |   
   |       /   \         |   
   |      6     5        |   
   |     /\     |\       |   
   |    /  \    | \      |   
   |   7    3   |  8     |   
   |   |    |   |  /\    /   
   +---|----|   | /  \  /
       |      --10    9/  
       |    -/  
      EXIT-/

(3->4 and 9->4 are back edges).  Now, in bypass_block, when we're
trying to bypass BB 4, we iterate over BB 4's incoming edges,
then we're iterating over reg_use_table (registers used in
insn).  Here we call
set = find_bypass_set (regno, e->src->index);
but since it returns non-NULL value, redirect_edge_and_branch_force 
later redirects edges and BB 4 is gone.
We then end up with
Redirecting fallthru edge 3->4 to 6
JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 1 [0x1])
Bypass edge from 3->4 to 6
Redirecting fallthru edge 9->4 to 5
JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
Bypass edge from 9->4 to 5
i.e., it is assumed that in one reg there "are" two constants, that can't
be right, right?!  I've tried to fix this by not redirecting edges (thus
bypassing block) if BB has more
incoming latch edges and the hash table has more different SRC rtxs with
the same hash value.
FWIW, the table looks like the below:
SET hash table (11 buckets, 3 entries)
Index 0 (hash value 4)
  (reg:SI 59 [ D.1735 ]) := (const_int 1 [0x1])
Index 1 (hash value 5)
  (reg/v/f:DI 60 [ b ]) := (const_int 0 [0])
Index 2 (hash value 4)
  (reg:SI 59 [ D.1735 ]) := (const_int 3 [0x3])

(Only not bypassing BB when it has more latch edges would work too,
but I'm afraid it could pessimize stuff somewhere else.)
I've also changed some zeros into NULLs for pointers.
Also, as folowup, we could get rid of may_be_loop_header variable 
completely, at one place where it is used we can use just 'n_latches > 0'.
And add the C++ TC as well.
Regtested/bootstrapped on x86_64-linux, ok for trunk?

2012-11-26  Marek Polacek  <polacek@redhat.com>

	PR middle-end/54838
	* cprop.c (only_one_const_p): New function.
	(find_bypass_set): New parameter.  Conditionally call
	only_one_const_p.  Use NULL instead of 0.
	(bypass_block): Adjust caller.  Determine number of latch edges.
	(n_latches): New variable.

	* gcc.dg/pr54838.c: New test.

--- gcc/cprop.c.mp	2012-11-26 12:13:08.631193625 +0100
+++ gcc/cprop.c	2012-11-26 14:41:32.864034283 +0100
@@ -1429,14 +1429,26 @@ find_implicit_sets (void)
 
 static int bypass_last_basic_block;
 
+/* Determine whether there is only one constant SRC rtx in the hash table
+   for REGNO.  Here we assume that for the same hash value there won't be
+   more entries with the same SRC rtx.  Return true if there is only one
+   constant, false otherwise.  */
+
+static bool
+only_one_const_p (int regno)
+{
+  struct expr *set = lookup_set (regno, &set_hash_table);
+  return next_set (regno, set) == NULL;
+}
+
 /* Find a set of REGNO to a constant that is available at the end of basic
    block BB.  Return NULL if no such set is found.  Based heavily upon
    find_avail_set.  */
 
 static struct expr *
-find_bypass_set (int regno, int bb)
+find_bypass_set (int regno, int bb, bool multiple_latches)
 {
-  struct expr *result = 0;
+  struct expr *result = NULL;
 
   for (;;)
     {
@@ -1450,9 +1462,15 @@ find_bypass_set (int regno, int bb)
 	  set = next_set (regno, set);
 	}
 
-      if (set == 0)
+      if (set == NULL)
 	break;
 
+      /* If there are more latch edges coming to the BB, we need to
+	 make sure that for the same hash value there aren't
+	 more constants.  */
+      if (multiple_latches && !only_one_const_p (regno))
+	return NULL;
+
       src = set->src;
       if (cprop_constant_p (src))
 	result = set;
@@ -1502,6 +1520,7 @@ bypass_block (basic_block bb, rtx setcc,
   int may_be_loop_header;
   unsigned removed_p;
   unsigned i;
+  unsigned n_latches;
   edge_iterator ei;
 
   insn = (setcc != NULL) ? setcc : jump;
@@ -1514,12 +1533,12 @@ bypass_block (basic_block bb, rtx setcc,
     find_used_regs (&XEXP (note, 0), NULL);
 
   may_be_loop_header = false;
+  n_latches = 0;
   FOR_EACH_EDGE (e, ei, bb->preds)
     if (e->flags & EDGE_DFS_BACK)
-      {
-	may_be_loop_header = true;
-	break;
-      }
+      n_latches++;
+
+  may_be_loop_header = n_latches > 0;
 
   change = 0;
   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
@@ -1557,7 +1576,7 @@ bypass_block (basic_block bb, rtx setcc,
 	  struct expr *set;
 	  rtx src, new_rtx;
 
-	  set = find_bypass_set (regno, e->src->index);
+	  set = find_bypass_set (regno, e->src->index, n_latches > 1);
 
 	  if (! set)
 	    continue;
--- gcc/testsuite/gcc.dg/pr54838.c.mp	2012-11-26 14:48:43.783980854 +0100
+++ gcc/testsuite/gcc.dg/pr54838.c	2012-11-26 14:49:51.051158719 +0100
@@ -0,0 +1,24 @@
+/* PR middle-end/54838 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-forward-propagate -ftracer" } */
+
+void bar (void);
+
+void
+foo (void *b, int *c)
+{
+again:
+  switch (*c)
+    {
+    case 1:
+      if (!b)
+	{
+	  bar ();
+	  return;
+	}
+      goto again;
+    case 3:
+      if (!b)
+	goto again;
+    }
+}

	Marek


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]