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

login
register
mail settings
Submitter Marek Polacek
Date Nov. 26, 2012, 2:28 p.m.
Message ID <20121126142843.GH17362@redhat.com>
Download mbox | patch
Permalink /patch/201704/
State New
Headers show

Comments

Marek Polacek - Nov. 26, 2012, 2:28 p.m.
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.


	Marek
Eric Botcazou - Nov. 28, 2012, 9:52 a.m.
> 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?!

No, I don't think that's the problem.  The above messages are admittedly a bit 
terse, they should say:

JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
             when BB 4 is entered from BB 9.  Redirect edge 9->4 to 5.

so you can have different constants for BB 3 and BB 9.  The patch to tweak the 
dump messages along these lines is pre-approved.

The ICE in merge_latch_edges means that the loop structure and the CFG aren't 
in sync anymore.  Does the cprop pass modify the former without declaring it?

Patch

--- 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;
+    }
+}