Patchwork PATCH: fix infinite loop in CSE

login
register
mail settings
Submitter Sandra Loosemore
Date Dec. 13, 2011, 2:53 a.m.
Message ID <4EE6BE29.9020005@codesourcery.com>
Download mbox | patch
Permalink /patch/130973/
State New
Headers show

Comments

Sandra Loosemore - Dec. 13, 2011, 2:53 a.m.
The test case in the attached patch gets stuck in an infinite loop in 
find_comparison_args in CSE when compiled for MIPS at -O2.  This bug has 
been present at least as far back as GCC 4.5 and probably much earlier 
than that.

The problem is that the inner loop over equivalences in the hash table 
is finding something that rewrites to exactly the same expression that 
we've already got in the outer loop, and there is no test for circular 
rewrites.

This patch fixes the specific problem in the test case by skipping over 
equivalences that would rewrite to exactly the same expression as on the 
current iteration.  But, it's not clear that there can't also be cycles 
of length > 1.  I don't see much point in getting fancy here (I assume 
that if this were a common problem it would have been reported and fixed 
long before now) so I just added a simple limit on the number of 
iterations to be sure the outer loop always terminates.

I regression-tested this in a GCC 4.5-based build for mips-linux-gnu and 
also did a full bootstrap and regression test for i686-pc-linux-gnu on 
mainline head.  OK to check in on mainline?

-Sandra


2011-12-12  Sandra Loosemore  <sandra@codesourcery.com>
	    Tom de Vries <tom@codesourcery.com>

	gcc/
	* cse.c (find_comparison_args): Add cap on number of iterations
	to avoid infinite loop in case of cycles.  Avoid obvious case
	that would result in a circular rewrite.

	gcc/testsuite/
	* gcc.dg/cse-bug.c: New testcase.
Andrew Pinski - Dec. 13, 2011, 3 a.m.
On Mon, Dec 12, 2011 at 6:53 PM, Sandra Loosemore
<sandra@codesourcery.com> wrote:
> The test case in the attached patch gets stuck in an infinite loop in
> find_comparison_args in CSE when compiled for MIPS at -O2.  This bug has
> been present at least as far back as GCC 4.5 and probably much earlier than
> that.
>
> The problem is that the inner loop over equivalences in the hash table is
> finding something that rewrites to exactly the same expression that we've
> already got in the outer loop, and there is no test for circular rewrites.
>
> This patch fixes the specific problem in the test case by skipping over
> equivalences that would rewrite to exactly the same expression as on the
> current iteration.  But, it's not clear that there can't also be cycles of
> length > 1.  I don't see much point in getting fancy here (I assume that if
> this were a common problem it would have been reported and fixed long before
> now) so I just added a simple limit on the number of iterations to be sure
> the outer loop always terminates.
>
> I regression-tested this in a GCC 4.5-based build for mips-linux-gnu and
> also did a full bootstrap and regression test for i686-pc-linux-gnu on
> mainline head.  OK to check in on mainline?

This is http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50380 .

Thanks,
Andrew Pinski
Sandra Loosemore - Dec. 13, 2011, 3:33 a.m.
On 12/12/2011 08:00 PM, Andrew Pinski wrote:
> On Mon, Dec 12, 2011 at 6:53 PM, Sandra Loosemore
> <sandra@codesourcery.com>  wrote:
>> The test case in the attached patch gets stuck in an infinite loop in
>> find_comparison_args in CSE when compiled for MIPS at -O2.  This bug has
>> been present at least as far back as GCC 4.5 and probably much earlier than
>> that.
>>
>> The problem is that the inner loop over equivalences in the hash table is
>> finding something that rewrites to exactly the same expression that we've
>> already got in the outer loop, and there is no test for circular rewrites.
>>
>> This patch fixes the specific problem in the test case by skipping over
>> equivalences that would rewrite to exactly the same expression as on the
>> current iteration.  But, it's not clear that there can't also be cycles of
>> length>  1.  I don't see much point in getting fancy here (I assume that if
>> this were a common problem it would have been reported and fixed long before
>> now) so I just added a simple limit on the number of iterations to be sure
>> the outer loop always terminates.
>>
>> I regression-tested this in a GCC 4.5-based build for mips-linux-gnu and
>> also did a full bootstrap and regression test for i686-pc-linux-gnu on
>> mainline head.  OK to check in on mainline?
>
> This is http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50380 .

Hmmmm.  It looks to me like the patch that allegedly fixes the problem 
on mainline may do so by coincidence.  At least, it's not obvious to me 
that it does something to ensure that the loop in find_comparison_args 
always terminates.....

-Sandra
Eric Botcazou - Dec. 18, 2011, 12:21 p.m.
> This patch fixes the specific problem in the test case by skipping over
> equivalences that would rewrite to exactly the same expression as on the
> current iteration.  But, it's not clear that there can't also be cycles
> of length > 1.  I don't see much point in getting fancy here (I assume
> that if this were a common problem it would have been reported and fixed
> long before now) so I just added a simple limit on the number of
> iterations to be sure the outer loop always terminates.

Sure, but we don't like arbitrary numbers in the compiler like

+  int maxiter = 16;

and adding a --param for it would be overkill, so let's drop the cap.

> 2011-12-12  Sandra Loosemore  <sandra@codesourcery.com>
> 	    Tom de Vries <tom@codesourcery.com>
>
> 	gcc/
> 	* cse.c (find_comparison_args): Add cap on number of iterations
> 	to avoid infinite loop in case of cycles.  Avoid obvious case
> 	that would result in a circular rewrite.

OK everywhere without the cap and with the same test on ARG2:

	  /* 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)
	    continue;

One could imagine a zero being loaded in a register and ARG1 compared with the 
register earlier.

> 	gcc/testsuite/
> 	* gcc.dg/cse-bug.c: New testcase.

If a testcase doesn't need fancy options, it must go in gcc.c-torture/compile.

Patch

Index: gcc/cse.c
===================================================================
--- gcc/cse.c	(revision 181994)
+++ gcc/cse.c	(working copy)
@@ -2967,12 +2967,14 @@  find_comparison_args (enum rtx_code code
 		      enum machine_mode *pmode1, enum machine_mode *pmode2)
 {
   rtx arg1, arg2;
+  int iter = 0;
+  int maxiter = 16;
 
   arg1 = *parg1, arg2 = *parg2;
 
   /* If ARG2 is const0_rtx, see what ARG1 is equivalent to.  */
 
-  while (arg2 == CONST0_RTX (GET_MODE (arg1)))
+  while (arg2 == CONST0_RTX (GET_MODE (arg1)) && iter++ < maxiter)
     {
       /* Set nonzero when we find something of interest.  */
       rtx x = 0;
@@ -3055,6 +3057,10 @@  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)
+	    continue;
+
 	  if (GET_CODE (p->exp) == COMPARE
 	      /* Another possibility is that this machine has a compare insn
 		 that includes the comparison code.  In that case, ARG1 would
Index: gcc/testsuite/gcc.dg/cse-bug.c
===================================================================
--- gcc/testsuite/gcc.dg/cse-bug.c	(revision 0)
+++ gcc/testsuite/gcc.dg/cse-bug.c	(revision 0)
@@ -0,0 +1,16 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-timeout 10 } */
+
+/* This test used to get stuck in an infinite loop in find_comparison_args
+   when compiling for MIPS.  */
+
+__attribute__ ((__noreturn__)) extern void fail (void);
+
+char x;
+
+void foo (const unsigned char y)
+{
+   ((void) (__builtin_expect((!! y == y), 1) ? 0 : (fail (), 0)));
+   x = ! y;
+}