Patchwork Detect loops in find_comparison_args

login
register
mail settings
Submitter Sandra Loosemore
Date July 26, 2012, 2:25 a.m.
Message ID <5010AA7E.7000608@codesourcery.com>
Download mbox | patch
Permalink /patch/173317/
State New
Headers show

Comments

Sandra Loosemore - July 26, 2012, 2:25 a.m.
On 07/25/2012 01:27 AM, Paolo Bonzini wrote:
> 
> What I'm worried about is the extra cost of malloc-ing and free-ing the
> pointer set.  Perhaps you can skip the pointer set creation in the common
> case where find_comparison_args does not iterate?  Something like this:
> 
> [snip]

I think this version is a little neater; it just defers initialization of the pointer set to the end of the loop.  I checked the test case on the two targets where we've previously observed failures (the original one on MIPS and the current one on PowerPC), as well as doing a full bootstrap and regression-test on x86_64.  OK to check in?

-Sandra


2012-07-25  Andrew Jenner  <andrew@codesourcery.com>
	    Sandra Loosemore  <sandra@codesourcery.com>

	gcc/
	* cse.c (find_comparison_args): Check for cycles of any length.

	gcc/testsuite/
	* gcc.c-torture/compile/pr50380.c: Add code to cause cycle of length 2.
Paolo Bonzini - July 26, 2012, 7:28 a.m.
Il 26/07/2012 04:25, Sandra Loosemore ha scritto:
> On 07/25/2012 01:27 AM, Paolo Bonzini wrote:
>> 
>> What I'm worried about is the extra cost of malloc-ing and free-ing
>> the pointer set.  Perhaps you can skip the pointer set creation in
>> the common case where find_comparison_args does not iterate?
>> Something like this:
>> 
>> [snip]
> 
> I think this version is a little neater; it just defers
> initialization of the pointer set to the end of the loop.

But the while condition could still fail right after you create the set,
and I would expect that to be the common case.

Paolo

> I checked
> the test case on the two targets where we've previously observed
> failures (the original one on MIPS and the current one on PowerPC),
> as well as doing a full bootstrap and regression-test on x86_64.  OK
> to check in?
> 
> -Sandra
> 
> 
> 2012-07-25  Andrew Jenner  <andrew@codesourcery.com> Sandra Loosemore
> <sandra@codesourcery.com>
> 
> gcc/ * cse.c (find_comparison_args): Check for cycles of any length.
> 
> gcc/testsuite/ * gcc.c-torture/compile/pr50380.c: Add code to cause
> cycle of length 2.
>

Patch

Index: gcc/cse.c
===================================================================
--- gcc/cse.c	(revision 189859)
+++ gcc/cse.c	(working copy)
@@ -43,6 +43,7 @@  along with GCC; see the file COPYING3.  
 #include "tree-pass.h"
 #include "df.h"
 #include "dbgcnt.h"
+#include "pointer-set.h"
 
 /* The basic idea of common subexpression elimination is to go
    through the code, keeping a record of expressions that would
@@ -2897,6 +2898,7 @@  find_comparison_args (enum rtx_code code
 		      enum machine_mode *pmode1, enum machine_mode *pmode2)
 {
   rtx arg1, arg2;
+  struct pointer_set_t *visited = NULL;
 
   arg1 = *parg1, arg2 = *parg2;
 
@@ -2985,10 +2987,8 @@  find_comparison_args (enum rtx_code code
 	  if (! exp_equiv_p (p->exp, p->exp, 1, false))
 	    continue;
 
-	  /* If it's the same comparison we're already looking at, skip it.  */
-	  if (COMPARISON_P (p->exp)
-	      && XEXP (p->exp, 0) == arg1
-	      && XEXP (p->exp, 1) == arg2)
+	  /* If it's a comparison we've used before, skip it.  */
+	  if (visited && pointer_set_contains (visited, p->exp))
 	    continue;
 
 	  if (GET_CODE (p->exp) == COMPARE
@@ -3062,6 +3062,10 @@  find_comparison_args (enum rtx_code code
       else if (COMPARISON_P (x))
 	code = GET_CODE (x);
       arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
+
+      if (!visited)
+	visited = pointer_set_create ();
+      pointer_set_insert (visited, x);
     }
 
   /* Return our results.  Return the modes from before fold_rtx
@@ -3069,6 +3073,8 @@  find_comparison_args (enum rtx_code code
   *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
   *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
 
+  if (visited)
+    pointer_set_destroy (visited);
   return code;
 }
 
Index: gcc/testsuite/gcc.c-torture/compile/pr50380.c
===================================================================
--- gcc/testsuite/gcc.c-torture/compile/pr50380.c	(revision 189859)
+++ gcc/testsuite/gcc.c-torture/compile/pr50380.c	(working copy)
@@ -1,12 +1,22 @@ 
-/* This test used to get stuck in an infinite loop in find_comparison_args
-   when compiling for MIPS at -O2.  */
-
 __attribute__ ((__noreturn__)) extern void fail (void);
 
 char x;
 
+/* This used to get stuck in an infinite loop in find_comparison_args
+   when compiling this function for MIPS at -O2.  */
+
 void foo (const unsigned char y)
 {
    ((void) (__builtin_expect((!! y == y), 1) ? 0 : (fail (), 0)));
    x = ! y;
 }
+
+/* This used to similarly get stuck when compiling for PowerPC at -O2.  */
+
+int foo2 (int arg)
+{
+  if (arg != !arg)
+    fail ();
+  if (arg)
+    fail ();
+}