public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* ifcvt/crossjump patch: Fix PR 42496, 21803
@ 2010-03-31 22:08 Bernd Schmidt
  2010-04-01 18:00 ` Steven Bosscher
  0 siblings, 1 reply; 95+ messages in thread
From: Bernd Schmidt @ 2010-03-31 22:08 UTC (permalink / raw)
  To: GCC Patches

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

The two PRs 42496 and 21803 show a problem with the RTL ifcvt pass:
sometimes, we end up with two identical insns, predicated with opposite
conditions.

As suggested in the PR, I've fixed this by reusing the crossjumping
code, adding a variant that looks for matching sequences at the start of
a block.  If we find matches between the then and else blocks, we delete
the tail sequence from the then block and the head sequence from the
else block, and end up with all instructions in their proper order.

Here's an example of the code finding both a head and a tail match:
        cmp     r3, r2                          cmp     r3, r2
        ldrhi   r3, [r5, #112]    |             ldr     r3, [r5, #112]
        addhi   r3, r3, r3, ls                  addhi   r3, r3, r3, ls
        movhi   r3, r3, asr #1                  movhi   r3, r3, asr #1
        strhi   r3, [r5, #112]    <
        ldrls   r3, [r5, #112]    <
        subls   r3, r3, #1                      subls   r3, r3, #1
        strls   r3, [r5, #112]    |             str     r3, [r5, #112]
        b       .L213                           b       .L213

Note that I've added the various EH sanity checks in the cfgcleanup.c
code after successful testing, just to make sure, and hoping I haven't
missed any other corner cases.

A previous arm-eabi{,mthumb} test run exposed one bug which I've fixed;
new test run now in progress overnight.  Ok for 4.6?


Bernd

[-- Attachment #2: ifcvt-pr42496.diff --]
[-- Type: text/plain, Size: 9702 bytes --]

	PR target/21803
	* ifcvt.c (cond_exec_process_if_block): Look for identical sequences
	at the start and end of the then/else blocks, and omit them from the
	conversion.
	* cfgcleanup.c (flow_find_cross_jump): No longer static.
	(flow_find_head_matching_sequence): New function.
	(old_insns_match_p): Check REG_EH_REGION notes for calls.
	* basic-block.h (flow_find_cross_jump,
	flow_find_head_matching_sequence): Declare functions.

	PR target/21803
	* gcc.target/arm/pr42496.c: New test.

Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 157454)
+++ ifcvt.c	(working copy)
@@ -385,6 +385,10 @@ cond_exec_process_if_block (ce_if_block_
   rtx false_expr;		/* test for then block insns */
   rtx true_prob_val;		/* probability of else block */
   rtx false_prob_val;		/* probability of then block */
+  rtx then_last_head = NULL_RTX;	/* Last match at the head of THEN */
+  rtx else_last_head = NULL_RTX;	/* Last match at the head of ELSE */
+  rtx then_first_tail = NULL_RTX;	/* First match at the tail of THEN */
+  rtx else_first_tail = NULL_RTX;	/* First match at the tail of ELSE */
   int n_insns;
   enum rtx_code false_code;
 
@@ -423,10 +427,71 @@ cond_exec_process_if_block (ce_if_block_
 
   if (else_bb)
     {
+      int n_matching;
+
       max *= 2;
       else_start = first_active_insn (else_bb);
       else_end = last_active_insn (else_bb, TRUE);
       n_insns += ce_info->num_else_insns = count_bb_insns (else_bb);
+
+      /* Look for matching sequences at the head and tail of the two blocks,
+	 and limit the range of insns to be converted if possible.  */
+      n_matching = flow_find_cross_jump (0, then_bb, else_bb,
+					 &then_first_tail, &else_first_tail);
+      if (then_first_tail == BB_HEAD (then_bb))
+	then_start = then_end = NULL_RTX;
+      if (else_first_tail == BB_HEAD (else_bb))
+	else_start = else_end = NULL_RTX;
+
+      if (n_matching > 0)
+	{
+	  if (then_end)
+	    then_end = prev_active_insn (then_first_tail);
+	  if (else_end)
+	    else_end = prev_active_insn (else_first_tail);
+	  n_insns -= 2 * n_matching;
+	}
+
+      if (then_start && else_start)
+	{
+	  n_matching
+	    = flow_find_head_matching_sequence (0, then_bb, else_bb,
+						&then_last_head,
+						&else_last_head);
+
+	  if (then_last_head == then_end)
+	    then_start = then_end = NULL_RTX;
+	  if (else_last_head == else_end)
+	    else_start = else_end = NULL_RTX;
+
+	  if (n_matching > 0)
+	    {
+	      rtx insn;
+
+	      if (then_start)
+		then_start = next_active_insn (then_last_head);
+	      if (else_start)
+		else_start = next_active_insn (else_last_head);
+	      n_insns -= 2 * n_matching;
+
+	      /* We won't pass the insns in the head sequence to
+		 cond_exec_process_insns, so we need to test them here
+		 to make sure that they don't clobber the condition.  */
+	      insn = BB_HEAD (then_bb);
+	      for (;;)
+		{
+		  if (!LABEL_P (insn) && !NOTE_P (insn)
+		      && !DEBUG_INSN_P (insn))
+		    {
+		      if (modified_in_p (test_expr, insn))
+			return FALSE;
+		    }
+		  if (insn == then_last_head)
+		    break;
+		  insn = NEXT_INSN (insn);
+		}
+	    }
+	}
     }
 
   if (n_insns > max)
@@ -570,7 +635,18 @@ cond_exec_process_if_block (ce_if_block_
     fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
 	     n_insns, (n_insns == 1) ? " was" : "s were");
 
-  /* Merge the blocks!  */
+  /* Merge the blocks!  If we had matching sequences, make sure to delete one
+     copy at the appropriate location first.  */
+  if (then_first_tail)
+    {
+      rtx from = then_first_tail;
+      if (!INSN_P (from))
+	from = next_active_insn (from);
+      delete_insn_chain (from, BB_END (then_bb), false);
+    }
+  if (else_last_head)
+    delete_insn_chain (first_active_insn (else_bb), else_last_head, false);
+
   merge_if_block (ce_info);
   cond_exec_changed_p = TRUE;
   return TRUE;
Index: cfgcleanup.c
===================================================================
--- cfgcleanup.c	(revision 157454)
+++ cfgcleanup.c	(working copy)
@@ -68,7 +68,6 @@ static bool crossjumps_occured;
 static bool try_crossjump_to_edge (int, edge, edge);
 static bool try_crossjump_bb (int, basic_block);
 static bool outgoing_edges_match (int, basic_block, basic_block);
-static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
 static bool old_insns_match_p (int, rtx, rtx);
 
 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
@@ -972,13 +971,27 @@ old_insns_match_p (int mode ATTRIBUTE_UN
      be filled that clobbers a parameter expected by the subroutine.
 
      ??? We take the simple route for now and assume that if they're
-     equal, they were constructed identically.  */
+     equal, they were constructed identically.
 
-  if (CALL_P (i1)
-      && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
+     Also check for identical exception regions.  */
+
+  if (CALL_P (i1))
+    {
+      /* Ensure the same EH region.  */
+      rtx n1 = find_reg_note (i1, REG_EH_REGION, 0);
+      rtx n2 = find_reg_note (i2, REG_EH_REGION, 0);
+
+      if (!n1 && n2)
+	return false;
+
+      if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
+	return false;
+
+      if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
 			CALL_INSN_FUNCTION_USAGE (i2))
-	  || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
-    return false;
+	  || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2))
+	return false;
+    }
 
 #ifdef STACK_REGS
   /* If cross_jump_death_matters is not 0, the insn's mode
@@ -1024,7 +1037,7 @@ old_insns_match_p (int mode ATTRIBUTE_UN
    To simplify callers of this function, if the blocks match exactly,
    store the head of the blocks in *F1 and *F2.  */
 
-static int
+int
 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
 		      basic_block bb2, rtx *f1, rtx *f2)
 {
@@ -1130,6 +1143,103 @@ flow_find_cross_jump (int mode ATTRIBUTE
   return ninsns;
 }
 
+/* Like flow_find_cross_jump, except start looking for a matching sequence from
+   the head of the two blocks.  Do not include jumps at the end.  */
+
+int
+flow_find_head_matching_sequence (int mode ATTRIBUTE_UNUSED, basic_block bb1,
+				  basic_block bb2, rtx *f1, rtx *f2)
+{
+  rtx i1, i2, last1, last2, beforelast1, beforelast2;
+  int ninsns = 0;
+  edge e;
+  edge_iterator ei;
+  int nehedges1 = 0, nehedges2 = 0;
+
+  FOR_EACH_EDGE (e, ei, bb1->succs)
+    if (e->flags & EDGE_EH)
+      nehedges1++;
+  FOR_EACH_EDGE (e, ei, bb2->succs)
+    if (e->flags & EDGE_EH)
+      nehedges2++;
+
+  i1 = BB_HEAD (bb1);
+  i2 = BB_HEAD (bb2);
+  last1 = beforelast1 = last2 = beforelast2 = NULL_RTX;
+
+  while (true)
+    {
+
+      /* Ignore notes.  */
+      while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
+	i1 = NEXT_INSN (i1);
+
+      while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
+	i2 = NEXT_INSN (i2);
+
+      if (JUMP_P (i1) || JUMP_P (i2))
+	break;
+
+      if ((i1 == BB_END (bb1) && i2 != BB_END (bb2)
+	   && nehedges1 > 0)
+	  || (i2 == BB_END (bb2) && i1 != BB_END (bb1)
+	      && nehedges2 > 0)
+	  || (i1 == BB_END (bb1) && i2 == BB_END (bb2)
+	      && nehedges1 != nehedges2))
+	break;
+
+      if (!old_insns_match_p (mode, i1, i2))
+	break;
+
+      merge_memattrs (i1, i2);
+
+      /* Don't begin a cross-jump with a NOTE insn.  */
+      if (INSN_P (i1))
+	{
+	  /* If the merged insns have different REG_EQUAL notes, then
+	     remove them.  */
+	  rtx equiv1 = find_reg_equal_equiv_note (i1);
+	  rtx equiv2 = find_reg_equal_equiv_note (i2);
+
+	  if (equiv1 && !equiv2)
+	    remove_note (i1, equiv1);
+	  else if (!equiv1 && equiv2)
+	    remove_note (i2, equiv2);
+	  else if (equiv1 && equiv2
+		   && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
+	    {
+	      remove_note (i1, equiv1);
+	      remove_note (i2, equiv2);
+	    }
+
+	  beforelast1 = last1, beforelast2 = last2;
+	  last1 = i1, last2 = i2;
+	  ninsns++;
+	}
+
+      if (i1 == BB_END (bb1) || i2 == BB_END (bb2))
+	break;
+
+      i1 = NEXT_INSN (i1);
+      i2 = NEXT_INSN (i2);
+    }
+
+#ifdef HAVE_cc0
+  /* Don't allow a compare to be shared by cross-jumping unless the insn
+     after the compare is also shared.  */
+  if (ninsns && reg_mentioned_p (cc0_rtx, last1) && sets_cc0_p (last1))
+    last1 = beforelast1, last2 = beforelast2, ninsns--;
+#endif
+
+  if (ninsns)
+    {
+      *f1 = last1;
+      *f2 = last2;
+    }
+
+  return ninsns;
+}
+
 /* Return true iff outgoing edges of BB1 and BB2 match, together with
    the branch instruction.  This means that if we commonize the control
    flow before end of the basic block, the semantic remains unchanged.
Index: basic-block.h
===================================================================
--- basic-block.h	(revision 157454)
+++ basic-block.h	(working copy)
@@ -894,6 +899,10 @@ extern void rtl_make_eh_edge (sbitmap, b
 
 /* In cfgcleanup.c.  */
 extern bool cleanup_cfg (int);
+extern int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
+extern int flow_find_head_matching_sequence (int, basic_block, basic_block,
+					     rtx *, rtx *);
+
 extern bool delete_unreachable_blocks (void);
 
 extern bool mark_dfs_back_edges (void);
Index: testsuite/gcc.target/arm/pr42496.c
===================================================================
--- testsuite/gcc.target/arm/pr42496.c	(revision 0)
+++ testsuite/gcc.target/arm/pr42496.c	(revision 0)
@@ -0,0 +1,16 @@
+/* { dg-options "-O2" }  */
+
+void foo(int i)
+{
+    extern int j;
+
+    if (i) {
+         j = 10;
+    }
+    else {
+          j = 20;
+    }
+}
+
+/* { dg-final { scan-assembler-not "strne" } } */
+/* { dg-final { scan-assembler-not "streq" } } */

^ permalink raw reply	[flat|nested] 95+ messages in thread

end of thread, other threads:[~2010-10-06  2:46 UTC | newest]

Thread overview: 95+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-03-31 22:08 ifcvt/crossjump patch: Fix PR 42496, 21803 Bernd Schmidt
2010-04-01 18:00 ` Steven Bosscher
2010-04-01 18:01   ` Bernd Schmidt
2010-04-02  9:45   ` Bernd Schmidt
2010-04-06  9:21   ` Bernd Schmidt
2010-04-10 10:37     ` Eric Botcazou
2010-04-12 23:34       ` Bernd Schmidt
2010-04-13 21:14         ` Eric Botcazou
2010-04-13 21:36           ` Bernd Schmidt
2010-04-13 21:51             ` Eric Botcazou
2010-04-14 20:51           ` Bernd Schmidt
2010-04-14 21:09       ` Bernd Schmidt
2010-04-19 22:05         ` Eric Botcazou
2010-04-19 22:14           ` Steven Bosscher
2010-04-19 22:18             ` Steven Bosscher
2010-04-19 22:47               ` Steven Bosscher
2010-04-20 10:34             ` Eric Botcazou
2010-04-20 11:26             ` Bernd Schmidt
2010-04-23  9:25               ` Eric Botcazou
2010-04-23 11:15                 ` Steven Bosscher
2010-05-15 11:24                   ` Steven Bosscher
2010-05-28 10:00                     ` Eric Botcazou
2010-05-28 11:20                       ` Steven Bosscher
2010-04-20 12:30           ` Bernd Schmidt
2010-07-20 20:43           ` Bernd Schmidt
2010-07-22 19:47             ` Eric Botcazou
2010-07-22 21:09               ` Bernd Schmidt
2010-07-23 22:06                 ` Eric Botcazou
2010-07-23 22:13                   ` Bernd Schmidt
2010-07-24 13:07                     ` Eric Botcazou
2010-07-26  9:42                       ` Bernd Schmidt
2010-07-26 13:40                         ` Paolo Bonzini
2010-07-26 13:50                           ` Paolo Bonzini
2010-07-26 13:56                           ` Bernd Schmidt
2010-07-26 14:14                             ` Paolo Bonzini
2010-07-27  8:31                             ` Eric Botcazou
2010-07-27  9:37                               ` Bernd Schmidt
2010-07-27 13:35                                 ` Bernd Schmidt
2010-07-27 22:38                                   ` Eric Botcazou
2010-07-28 16:58                                     ` Jeff Law
2010-07-29  8:25                                       ` Eric Botcazou
2010-07-27 17:39                                 ` Jeff Law
2010-07-27 22:05                                   ` Bernd Schmidt
2010-07-27 22:40                                     ` Eric Botcazou
2010-07-28 17:06                                       ` Jeff Law
2010-07-29 17:28                                     ` Jeff Law
2010-07-29 17:43                                       ` Bernd Schmidt
2010-07-27 22:23                                 ` Eric Botcazou
2010-07-27 23:04                                   ` Bernd Schmidt
2010-07-28  8:40                                     ` Eric Botcazou
2010-07-28 10:13                                       ` Bernd Schmidt
2010-07-28 19:40                                         ` Jeff Law
2010-07-28 20:15                                           ` Bernd Schmidt
2010-07-29 16:00                                             ` Jeff Law
2010-07-29 16:21                                               ` Paolo Bonzini
2010-07-29 17:09                                                 ` Bernd Schmidt
2010-07-29 17:13                                                   ` Paolo Bonzini
2010-07-30  0:55                                                 ` Steven Bosscher
2010-07-28 18:31                                     ` Jeff Law
2010-07-28 18:36                                       ` Paolo Bonzini
2010-07-29  9:07                                       ` Eric Botcazou
2010-07-27 23:08                                   ` Paolo Bonzini
2010-07-28 21:44                           ` Bernd Schmidt
2010-07-29 14:31                             ` Jeff Law
2010-07-27 15:31                   ` Jeff Law
2010-07-27 22:18                     ` Eric Botcazou
2010-07-28 17:07                       ` Jeff Law
2010-07-28 17:38                         ` Bernd Schmidt
2010-08-02 15:57             ` Jeff Law
2010-08-02 15:59               ` Bernd Schmidt
2010-08-02 16:05                 ` Jeff Law
2010-08-02 16:15                   ` Bernd Schmidt
2010-08-03 14:10                     ` Bernd Schmidt
2010-08-03 15:16                       ` Jeff Law
2010-08-03 15:31                         ` Bernd Schmidt
2010-08-03 17:13                           ` Jeff Law
2010-08-04 13:36                             ` Bernd Schmidt
2010-08-30 16:00                               ` Bernd Schmidt
2010-09-20 10:23                                 ` Bernd Schmidt
2010-09-20 16:25                                   ` Jeff Law
2010-09-23 15:53                                     ` Bernd Schmidt
2010-09-23 22:00                                       ` Richard Guenther
2010-09-23 22:03                                         ` Richard Guenther
2010-09-23 22:18                                           ` Bernd Schmidt
2010-09-24 11:29                                             ` Richard Guenther
2010-09-27 15:56                                       ` Fix PR45792, cris-elf build breakage from PR44374-fix "ifcvt/crossjump patch: Fix PR 42496, 21803" Hans-Peter Nilsson
2010-09-27 20:34                                         ` Bernd Schmidt
2010-09-27 23:38                                           ` Hans-Peter Nilsson
2010-09-28  0:07                                             ` Bernd Schmidt
2010-10-02 13:07                               ` ifcvt/crossjump patch: Fix PR 42496, 21803 H.J. Lu
2010-10-03 11:33                                 ` Bernd Schmidt
2010-10-03 11:39                                   ` H.J. Lu
2010-10-06  1:12                                   ` H.J. Lu
2010-10-06  2:46                                     ` H.J. Lu
2010-04-12 20:43     ` Jim Wilson

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).