Fix/work around PR57676, LRA terminates prematurely

Fix/work around PR57676, LRA terminates prematurely

[Bernd Schmidt]

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

The testcase in this PR causes gcc to abort with

internal compiler error: Maximum number of LRA constraint passes is 
achieved (30)

[in theory - I've not managed to reproduce this on my system with any 
compiler]

The abort is premature, allowing LRA to continue would allow the 
testcase to compile. Vlad would like to leave the check in, however, as 
it is a good way to catch problems with machine descriptions as they are 
converted to use LRA.

The following is a compromise I came up with after some internal 
discussion. The idea is to leave the assert in under -fchecking, so that 
release compilers do not prematurely abort for valid testcases, while 
development builds get an additional sanity check.

Bootstrapped and tested on x86_64-linux. Ok?


Bernd

	PR rtl-optimization/57676
	* lra-assigns.c (lra_assign): Guard test for maximum iterations
	with flag_checking.

	PR rtl-optimization/57676
	* gcc.dg/torture/pr57676.c: New test.


[-- Attachment #2: assigns-max.diff --]
[-- Type: text/x-patch, Size: 1609 bytes --]

Index: gcc/lra-assigns.c
===================================================================
--- gcc/lra-assigns.c	(revision 233451)
+++ gcc/lra-assigns.c	(working copy)
@@ -1620,7 +1620,12 @@ lra_assign (void)
   timevar_pop (TV_LRA_ASSIGN);
   if (former_reload_pseudo_spill_p)
     lra_assignment_iter_after_spill++;
-  if (lra_assignment_iter_after_spill > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER)
+  /* This is conditional on flag_checking because valid code can take
+     more than this maximum number of iteration, but at the same time
+     the test can uncover errors in machine descriptions.  */
+  if (flag_checking
+      && (lra_assignment_iter_after_spill
+	  > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
     internal_error
       ("Maximum number of LRA assignment passes is achieved (%d)\n",
        LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
Index: gcc/testsuite/gcc.dg/torture/pr57676.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr57676.c	(revision 0)
+++ gcc/testsuite/gcc.dg/torture/pr57676.c	(working copy)
@@ -0,0 +1,28 @@
+/* Verify that LRA does not abort prematurely in a release build of the
+   compiler.  */
+/* { dg-do compile } */
+/* { dg-options "-fno-checking -w -funroll-loops" } */
+
+int a, b, c;
+
+void f(p1)
+{
+    for(;;)
+    {
+        if(p1 ? : (c /= 0))
+        {
+            int d;
+
+            for(; d; d++)
+            {
+                for(b = 0; b < 4; b++)
+                    p1 /= p1;
+lbl:
+                while(a);
+            }
+        }
+
+        if((c &= 1))
+            goto lbl;
+    }
+}

Re: Fix/work around PR57676, LRA terminates prematurely

[Jeff Law]

On 02/19/2016 02:32 PM, Bernd Schmidt wrote:
> The testcase in this PR causes gcc to abort with
>
> internal compiler error: Maximum number of LRA constraint passes is
> achieved (30)
>
> [in theory - I've not managed to reproduce this on my system with any
> compiler]
>
> The abort is premature, allowing LRA to continue would allow the
> testcase to compile. Vlad would like to leave the check in, however, as
> it is a good way to catch problems with machine descriptions as they are
> converted to use LRA.
>
> The following is a compromise I came up with after some internal
> discussion. The idea is to leave the assert in under -fchecking, so that
> release compilers do not prematurely abort for valid testcases, while
> development builds get an additional sanity check.
>
> Bootstrapped and tested on x86_64-linux. Ok?
>
>
> Bernd
>
>      PR rtl-optimization/57676
>      * lra-assigns.c (lra_assign): Guard test for maximum iterations
>      with flag_checking.
>
>      PR rtl-optimization/57676
>      * gcc.dg/torture/pr57676.c: New test.
OK.  Your call on backporting the release branches.

jeff

Re: Fix/work around PR57676, LRA terminates prematurely

[Richard Biener]

On Fri, Feb 19, 2016 at 10:34 PM, Jeff Law <law@redhat.com> wrote:
> On 02/19/2016 02:32 PM, Bernd Schmidt wrote:
>>
>> The testcase in this PR causes gcc to abort with
>>
>> internal compiler error: Maximum number of LRA constraint passes is
>> achieved (30)
>>
>> [in theory - I've not managed to reproduce this on my system with any
>> compiler]
>>
>> The abort is premature, allowing LRA to continue would allow the
>> testcase to compile. Vlad would like to leave the check in, however, as
>> it is a good way to catch problems with machine descriptions as they are
>> converted to use LRA.
>>
>> The following is a compromise I came up with after some internal
>> discussion. The idea is to leave the assert in under -fchecking, so that
>> release compilers do not prematurely abort for valid testcases, while
>> development builds get an additional sanity check.
>>
>> Bootstrapped and tested on x86_64-linux. Ok?
>>
>>
>> Bernd
>>
>>      PR rtl-optimization/57676
>>      * lra-assigns.c (lra_assign): Guard test for maximum iterations
>>      with flag_checking.
>>
>>      PR rtl-optimization/57676
>>      * gcc.dg/torture/pr57676.c: New test.
>
> OK.  Your call on backporting the release branches.

Hum, but then you get to "inifinite" compiles again when LRA is buggy
or the user presents it with an impossible to handle asm.

I don't think that's a good idea - maybe bumping the limit is the way to
go instead?

30 constraint passes sounds excessive and a sign of a bug to me anyway.

Richard.

> jeff

Re: Fix/work around PR57676, LRA terminates prematurely

[Jeff Law]

On 02/22/2016 07:34 AM, Richard Biener wrote:

> Hum, but then you get to "inifinite" compiles again when LRA is buggy
> or the user presents it with an impossible to handle asm.
Neither should be happening in practice, even an impossible asm should 
cause LRA to halt in some way or another.

In practice looping has occurred due to bugs in machine descriptions are 
are typically seen during development/porting.  Hence the desire to put 
it under -fchecking for gcc-6 and possibly implement something smarter 
for gcc-7 (where we'd track more precisely whether or not we're making 
forward progress).

>
> I don't think that's a good idea - maybe bumping the limit is the way to
> go instead?
No, because one just needs to build a longer chain of insns needing 
reloading.

>
> 30 constraint passes sounds excessive and a sign of a bug to me anyway.
Not really.  If you look at the testcase and the chain of reloads, it's 
legitimate.  Essentially each pass exposes a case where spill a register 
in an insn that previously had a register allocated.

Jeff

Re: Fix/work around PR57676, LRA terminates prematurely

[Richard Biener]

On Mon, Feb 22, 2016 at 4:34 PM, Jeff Law <law@redhat.com> wrote:
> On 02/22/2016 07:34 AM, Richard Biener wrote:
>
>> Hum, but then you get to "inifinite" compiles again when LRA is buggy
>> or the user presents it with an impossible to handle asm.
>
> Neither should be happening in practice, even an impossible asm should cause
> LRA to halt in some way or another.
>
> In practice looping has occurred due to bugs in machine descriptions are are
> typically seen during development/porting.  Hence the desire to put it under
> -fchecking for gcc-6 and possibly implement something smarter for gcc-7
> (where we'd track more precisely whether or not we're making forward
> progress).
>
>>
>> I don't think that's a good idea - maybe bumping the limit is the way to
>> go instead?
>
> No, because one just needs to build a longer chain of insns needing
> reloading.
>
>>
>> 30 constraint passes sounds excessive and a sign of a bug to me anyway.
>
> Not really.  If you look at the testcase and the chain of reloads, it's
> legitimate.  Essentially each pass exposes a case where spill a register in
> an insn that previously had a register allocated.

But requiring another full reload pass to handle such chains is pointing at
a wrong algorithm IMHO.  Isn't this also quadratic in the length of the chain?

Richard.

> Jeff

Re: Fix/work around PR57676, LRA terminates prematurely

[Vladimir Makarov]

On 02/23/2016 06:56 AM, Richard Biener wrote:
> On Mon, Feb 22, 2016 at 4:34 PM, Jeff Law <law@redhat.com> wrote:
>> On 02/22/2016 07:34 AM, Richard Biener wrote:
>>
>>> Hum, but then you get to "inifinite" compiles again when LRA is buggy
>>> or the user presents it with an impossible to handle asm.
>> Neither should be happening in practice, even an impossible asm should cause
>> LRA to halt in some way or another.
>>
>> In practice looping has occurred due to bugs in machine descriptions are are
>> typically seen during development/porting.  Hence the desire to put it under
>> -fchecking for gcc-6 and possibly implement something smarter for gcc-7
>> (where we'd track more precisely whether or not we're making forward
>> progress).
>>
>>> I don't think that's a good idea - maybe bumping the limit is the way to
>>> go instead?
>> No, because one just needs to build a longer chain of insns needing
>> reloading.
>>
>>> 30 constraint passes sounds excessive and a sign of a bug to me anyway.
>> Not really.  If you look at the testcase and the chain of reloads, it's
>> legitimate.  Essentially each pass exposes a case where spill a register in
>> an insn that previously had a register allocated.
> But requiring another full reload pass to handle such chains is pointing at
> a wrong algorithm IMHO.  Isn't this also quadratic in the length of the chain?
>
This is a pathological case.  It is not quadratic although we have 
quadratic algorithms already in GCC.  IRA building conflict graphs (as 
the old global.c)  can be quadratic for some pathological cases.  
Actually reload + IRA can be slow as LRA for this case too if we takes 
into account that reload is asking IRA to reallocate a spilled pseudo 
each time.

But you are right for this case we can speed up LRA for such cases 
considering rebuilding live info only for places where there are 
changes.  Probably it will speed up most other cases too.

Re: Fix/work around PR57676, LRA terminates prematurely

[Jeff Law]

On 02/23/2016 04:56 AM, Richard Biener wrote:
> On Mon, Feb 22, 2016 at 4:34 PM, Jeff Law <law@redhat.com> wrote:
>> On 02/22/2016 07:34 AM, Richard Biener wrote:
>>
>>> Hum, but then you get to "inifinite" compiles again when LRA is buggy
>>> or the user presents it with an impossible to handle asm.
>>
>> Neither should be happening in practice, even an impossible asm should cause
>> LRA to halt in some way or another.
>>
>> In practice looping has occurred due to bugs in machine descriptions are are
>> typically seen during development/porting.  Hence the desire to put it under
>> -fchecking for gcc-6 and possibly implement something smarter for gcc-7
>> (where we'd track more precisely whether or not we're making forward
>> progress).
>>
>>>
>>> I don't think that's a good idea - maybe bumping the limit is the way to
>>> go instead?
>>
>> No, because one just needs to build a longer chain of insns needing
>> reloading.
>>
>>>
>>> 30 constraint passes sounds excessive and a sign of a bug to me anyway.
>>
>> Not really.  If you look at the testcase and the chain of reloads, it's
>> legitimate.  Essentially each pass exposes a case where spill a register in
>> an insn that previously had a register allocated.
>
> But requiring another full reload pass to handle such chains is pointing at
> a wrong algorithm IMHO.  Isn't this also quadratic in the length of the chain?
Note that reload behaves similarly.  Not for this exact case, but it's 
essentially a "keep iterating until nothing changes" algorithm.  It's 
just so poor in its ability to assign things to registers that these 
deep chains are rare.

As Vlad noted, the test is definitely a pathological case.  I think 
Bernd's patch is a very reasonable approach to address the current 
problem.  Namely that LRA can be making progress on a pathological 
testcase, but it gets terminated by the anti-looping clamp.  The clamp 
itself was put in place to catch bugs in LRA or ports that are in the 
process of converting to LRA.

Jeff

Re: Fix/work around PR57676, LRA terminates prematurely

[Bernd Schmidt]

On 02/24/2016 11:01 PM, Jeff Law wrote:
> As Vlad noted, the test is definitely a pathological case.  I think
> Bernd's patch is a very reasonable approach to address the current
> problem.  Namely that LRA can be making progress on a pathological
> testcase, but it gets terminated by the anti-looping clamp.  The clamp
> itself was put in place to catch bugs in LRA or ports that are in the
> process of converting to LRA.

Richard, are you upholding your objection?


Bernd

Re: Fix/work around PR57676, LRA terminates prematurely

[Richard Biener]

On Wed, Mar 2, 2016 at 7:39 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> On 02/24/2016 11:01 PM, Jeff Law wrote:
>>
>> As Vlad noted, the test is definitely a pathological case.  I think
>> Bernd's patch is a very reasonable approach to address the current
>> problem.  Namely that LRA can be making progress on a pathological
>> testcase, but it gets terminated by the anti-looping clamp.  The clamp
>> itself was put in place to catch bugs in LRA or ports that are in the
>> process of converting to LRA.
>
>
> Richard, are you upholding your objection?

No.

Richard.

>
> Bernd
>