[PATCH] Fix CSE bogus RTL creation

[PATCH] Fix CSE bogus RTL creation

[Paul Brook]

The patch below fixes a bug observed on an ARM target. The problematic code 
starts with (mem (plus (reg) (reg))). CSE then replaces the first REG by a 
CONST_INT. This results in invalid rtl: (plus (const_int) (reg)) - it is 
expected that the CONST_INT be the second argument of the PLUS. This works its 
way through the compiler and ends up confusing the assembly output patterns.

The patch below fixes this by calling simplify_rtx if any substitutions are 
done. This should ensure that the result if canonical RTL.

My original fix tested specifically for my example above. However it was 
suggested that I should use simplify_rtx instead, to catch similar latent 
bugs.

Unfortunately the original testcase if very large and fragile. I am unable to 
construct a testcase to reproduce this reliably.

Tested on arm-none-eabi and x86_64-linux.
Ok?

Paul

2010-06-14  Paul Brook  <paul@codesourcery.com>
 
	gcc/
	* cse.c (cse_process_notes_1): Call simplify_rtx is a substitution
	was made.

Index: gcc/cse.c
===================================================================
--- gcc/cse.c	(revision 160724)
+++ gcc/cse.c	(working copy)
@@ -5989,6 +5989,7 @@ cse_process_notes_1 (rtx x, rtx object,
   enum rtx_code code = GET_CODE (x);
   const char *fmt = GET_RTX_FORMAT (code);
   int i;
+  bool did_change = false;
 
   switch (code)
     {
@@ -6057,7 +6058,18 @@ cse_process_notes_1 (rtx x, rtx object,
   for (i = 0; i < GET_RTX_LENGTH (code); i++)
     if (fmt[i] == 'e')
       validate_change (object, &XEXP (x, i),
-		       cse_process_notes (XEXP (x, i), object, changed), 0);
+		       cse_process_notes (XEXP (x, i), object, &did_change), 0);
+
+  /* We may need to rebuild the expression after substitution.
+     e.g. if the first operand of a PLUS is replaced by a constant.  */
+  if (did_change)
+    {
+      rtx simplified;
+      *changed = true;
+      simplified = simplify_rtx(x);
+      if (simplified)
+	x = simplified;
+    }
 
   return x;
 }

Re: [PATCH] Fix CSE bogus RTL creation

[Mark Mitchell]

Paul Brook wrote:

> 2010-06-14  Paul Brook  <paul@codesourcery.com>
>  
> 	gcc/
> 	* cse.c (cse_process_notes_1): Call simplify_rtx is a substitution
> 	was made.

I think this qualifies as near-obvious.  OK.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix CSE bogus RTL creation

[Steven Bosscher]

On Tue, Jun 15, 2010 at 1:41 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> Paul Brook wrote:
>
>> 2010-06-14  Paul Brook  <paul@codesourcery.com>
>>
>>       gcc/
>>       * cse.c (cse_process_notes_1): Call simplify_rtx is a substitution
>>       was made.
>
> I think this qualifies as near-obvious.  OK.

How is this obvious?

1. It means validate_change validates something that is not canonical RTL.

2. You are canonicalizing something that is in a REG-note. How does
this non-canonical note content escape from the note into an INSN? Is
that not the point where this bug should be fixed?

It makes me suspect that this change only papers over a bug elsewhere,
where a note replacement in an insn is not validated properly.

Ciao!
Steven

Re: [PATCH] Fix CSE bogus RTL creation

[Paolo Bonzini]

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

On 06/15/2010 07:16 AM, Steven Bosscher wrote:
> On Tue, Jun 15, 2010 at 1:41 AM, Mark Mitchell<mark@codesourcery.com>  wrote:
>> Paul Brook wrote:
>>
>>> 2010-06-14  Paul Brook<paul@codesourcery.com>
>>>
>>>        gcc/
>>>        * cse.c (cse_process_notes_1): Call simplify_rtx is a substitution
>>>        was made.
>>
>> I think this qualifies as near-obvious.  OK.
>
> How is this obvious?
>
> 1. It means validate_change validates something that is not canonical RTL.

But that is not the task of validate_change.  It would be done with a 
patch like the attached (which is not meant to be applied right away, 
but would do the same as Paul's in a better way).

> 2. You are canonicalizing something that is in a REG-note. How does
> this non-canonical note content escape from the note into an INSN? Is
> that not the point where this bug should be fixed?
>
> It makes me suspect that this change only papers over a bug elsewhere,
> where a note replacement in an insn is not validated properly.

It may still cause a missed optimization, so it's sensible to apply my 
patch or something like that after investigating (2).  But I also would 
like to understand where is the note used in an insn, and why recog 
isn't trapping it there.

Paolo

[-- Attachment #2: paolo.patch --]
[-- Type: text/plain, Size: 1535 bytes --]

Index: cse.c
===================================================================
--- cse.c	(revision 160609)
+++ cse.c	(working copy)
@@ -6005,9 +6005,19 @@ cse_process_notes_1 (rtx x, rtx object, 
       return x;
 
     case MEM:
-      validate_change (x, &XEXP (x, 0),
-		       cse_process_notes (XEXP (x, 0), x, changed), 0);
-      return x;
+      {
+        int n = num_validated_changes ();
+        rtx new = cse_process_notes (XEXP (x, 0), x, changed);
+        validate_change (x, &XEXP (x, 0), new, 1);
+        if (verify_changes (n))
+          {
+            if (!n)
+              confirm_change_group ();
+          }
+        else
+          cancel_changes (n);
+        return x;
+      }
 
     case EXPR_LIST:
     case INSN_LIST:
@@ -6025,7 +6035,7 @@ cse_process_notes_1 (rtx x, rtx object, 
 	/* We don't substitute VOIDmode constants into these rtx,
 	   since they would impede folding.  */
 	if (GET_MODE (new_rtx) != VOIDmode)
-	  validate_change (object, &XEXP (x, 0), new_rtx, 0);
+	  validate_change (object, &XEXP (x, 0), new_rtx, object != NULL_RTX);
 	return x;
       }
 
@@ -6057,8 +6067,11 @@ cse_process_notes_1 (rtx x, rtx object, 
   for (i = 0; i < GET_RTX_LENGTH (code); i++)
     if (fmt[i] == 'e')
       validate_change (object, &XEXP (x, i),
-		       cse_process_notes (XEXP (x, i), object, changed), 0);
+		       cse_process_notes (XEXP (x, i), object, changed), 1);
 
+  canonicalize_change_group (object, x);
+  if (object == NULL_RTX)
+    apply_change_group ();
   return x;
 }
 

Re: [PATCH] Fix CSE bogus RTL creation

[Paolo Bonzini]

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

On 06/15/2010 07:16 AM, Steven Bosscher wrote:
> On Tue, Jun 15, 2010 at 1:41 AM, Mark Mitchell<mark@codesourcery.com>  wrote:
>> Paul Brook wrote:
>>
>>> 2010-06-14  Paul Brook<paul@codesourcery.com>
>>>
>>>        gcc/
>>>        * cse.c (cse_process_notes_1): Call simplify_rtx is a substitution
>>>        was made.
>>
>> I think this qualifies as near-obvious.  OK.
>
> How is this obvious?
>
> 1. It means validate_change validates something that is not canonical RTL.

But that is not the task of validate_change.  It would be done with a 
patch like the attached (which is not meant to be applied right away, 
but would do the same as Paul's in a better way).

> 2. You are canonicalizing something that is in a REG-note. How does
> this non-canonical note content escape from the note into an INSN? Is
> that not the point where this bug should be fixed?
>
> It makes me suspect that this change only papers over a bug elsewhere,
> where a note replacement in an insn is not validated properly.

It may still cause a missed optimization, so it's sensible to apply my 
patch or something like that after investigating (2).  But I also would 
like to understand where is the note used in an insn, and why recog 
isn't trapping it there.

Paolo

[-- Attachment #2: paolo.patch --]
[-- Type: text/plain, Size: 1535 bytes --]

Index: cse.c
===================================================================
--- cse.c	(revision 160609)
+++ cse.c	(working copy)
@@ -6005,9 +6005,19 @@ cse_process_notes_1 (rtx x, rtx object, 
       return x;
 
     case MEM:
-      validate_change (x, &XEXP (x, 0),
-		       cse_process_notes (XEXP (x, 0), x, changed), 0);
-      return x;
+      {
+        int n = num_validated_changes ();
+        rtx new = cse_process_notes (XEXP (x, 0), x, changed);
+        validate_change (x, &XEXP (x, 0), new, 1);
+        if (verify_changes (n))
+          {
+            if (!n)
+              confirm_change_group ();
+          }
+        else
+          cancel_changes (n);
+        return x;
+      }
 
     case EXPR_LIST:
     case INSN_LIST:
@@ -6025,7 +6035,7 @@ cse_process_notes_1 (rtx x, rtx object, 
 	/* We don't substitute VOIDmode constants into these rtx,
 	   since they would impede folding.  */
 	if (GET_MODE (new_rtx) != VOIDmode)
-	  validate_change (object, &XEXP (x, 0), new_rtx, 0);
+	  validate_change (object, &XEXP (x, 0), new_rtx, object != NULL_RTX);
 	return x;
       }
 
@@ -6057,8 +6067,11 @@ cse_process_notes_1 (rtx x, rtx object, 
   for (i = 0; i < GET_RTX_LENGTH (code); i++)
     if (fmt[i] == 'e')
       validate_change (object, &XEXP (x, i),
-		       cse_process_notes (XEXP (x, i), object, changed), 0);
+		       cse_process_notes (XEXP (x, i), object, changed), 1);
 
+  canonicalize_change_group (object, x);
+  if (object == NULL_RTX)
+    apply_change_group ();
   return x;
 }
 

Re: [PATCH] Fix CSE bogus RTL creation

[Steven Bosscher]

On Tue, Jun 15, 2010 at 11:35 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> 1. It means validate_change validates something that is not canonical RTL.
>
> But that is not the task of validate_change.  It would be done with a patch
> like the attached (which is not meant to be applied right away, but would do
> the same as Paul's in a better way).

That's one possibility. I was thinking, since it's only in a REG_NOTE,
a change doesn't even have to be validated at all (AFAIU, anything
goes in a note), so instead of validate_change the replacement should
perhaps be done with simplify_replace_rtx...?

Ciao!
Steven

Re: [PATCH] Fix CSE bogus RTL creation

[Paolo Bonzini]

On 06/15/2010 12:07 PM, Steven Bosscher wrote:
> On Tue, Jun 15, 2010 at 11:35 AM, Paolo Bonzini<bonzini@gnu.org>  wrote:
>>> 1. It means validate_change validates something that is not canonical RTL.
>>
>> But that is not the task of validate_change.  It would be done with a patch
>> like the attached (which is not meant to be applied right away, but would do
>> the same as Paul's in a better way).
>
> That's one possibility. I was thinking, since it's only in a REG_NOTE,
> a change doesn't even have to be validated at all (AFAIU, anything
> goes in a note)

Even invalid addresses? (Genuine question; those are definitely ruled 
out by validate_change, and that part dates back to the initial import 
of GCC sources).

> , so instead of validate_change the replacement should
> perhaps be done with simplify_replace_rtx...?

Yes, the whole cse_process_notes function can become a single call to 
simplify_replace_fn_rtx (the replacement function being basically the 
REG case of cse_process_notes_1).  Even better, simplify_replace_fn_rtx 
knows how to deal with SUBREGs, so this case would go away:

         /* We don't substitute VOIDmode constants into these rtx,
            since they would impede folding.  */
         if (GET_MODE (new_rtx) != VOIDmode)
           validate_change (object, &XEXP (x, 0), new_rtx, 0);

Besides possible problems due to invalid addresses (because 
simplify_replace_rtx uses replace_equiv_address_nv) I like this.

Paolo

Re: [PATCH] Fix CSE bogus RTL creation

[Mark Mitchell]

Steven Bosscher wrote:

>>> 2010-06-14  Paul Brook  <paul@codesourcery.com>
>>>
>>>       gcc/
>>>       * cse.c (cse_process_notes_1): Call simplify_rtx is a substitution
>>>       was made.

> How is this obvious?

> It makes me suspect that this change only papers over a bug elsewhere,
> where a note replacement in an insn is not validated properly.

I think we worry too much about that.  Or, rather, we confuse
*suboptimal* patches with *wrong* patches.

A wrong patch is one that will make the compiler generate wrong code, or
slow code, or cause an ICE, or do some other user-observable bad thing.
 A suboptimal patch is one for which there exists a superior
implementation technique, possibly involving some much larger reworking
of the sourcebase, that would produce a solution to more problems, a
more elegant solution to the same problem, or in some other way be superior.

Of course, I am all for superior patches, good infrastructure,
clean-ups, and so forth.  But, it seemed clear to me that (a)
validate_change wasn't in the business of making canonical RTL, and (b)
simplify_rtx was, and (c) this patch made the compiler better from a
user-observable point of view, in that it eliminated crashes, and (d)
there had been some previous discussion suggesting this approach, and
(e) I couldn't see any user-observable harm it would do, and (f) it was
a small local change.

I think that should be good enough.  Now, of course, if you have an idea
about how to do it better, I think that's great!  A more general, more
elegant solution would be terrific.  But, I don't want perfect to be the
enemy of good.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix CSE bogus RTL creation

[Paolo Bonzini]

On 06/15/2010 04:08 PM, Mark Mitchell wrote:
> Of course, I am all for superior patches, good infrastructure,
> clean-ups, and so forth.  But, it seemed clear to me that (a)
> validate_change wasn't in the business of making canonical RTL, and
> (b) simplify_rtx was

For that matter, canonicalize_change_group also is, and is more directly
related to validate_change.

> and (c) this patch made the compiler better from a user-observable
> point of view, in that it eliminated crashes,

Without knowing the real bug, you cannot know if there are other
identical crashes waiting to bite you.

> and (d) there had been some previous discussion suggesting this
> approach

Where?

> I think that should be good enough.  Now, of course, if you have an
> idea about how to do it better, I think that's great!  A more
> general, more elegant solution would be terrific.

I gave a patch and Steven outlined another idea that might be even
better.  Again, I cannot say if Steven's idea would work without knowing
what the real bug is.

> But, I don't want perfect to be the enemy of good.

But "papering over the real bug" _is_ the enemy of "good".  That is
something clearly undesirable, not just suboptimal, especially at the
beginning of stage1.

I'm not opposing the patch at all costs, but definitely the bug hasn't
been analyzed thoroughly enough.

Paolo

Re: [PATCH] Fix CSE bogus RTL creation

[Steven Bosscher]

On Tue, Jun 15, 2010 at 5:32 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 06/15/2010 04:08 PM, Mark Mitchell wrote:
>>
>> Of course, I am all for superior patches, good infrastructure,
>> clean-ups, and so forth.  But, it seemed clear to me that (a)
>> validate_change wasn't in the business of making canonical RTL, and
>> (b) simplify_rtx was
>
> For that matter, canonicalize_change_group also is, and is more directly
> related to validate_change.
>
>> and (c) this patch made the compiler better from a user-observable
>> point of view, in that it eliminated crashes,
>
> Without knowing the real bug, you cannot know if there are other
> identical crashes waiting to bite you.
>
>> and (d) there had been some previous discussion suggesting this
>> approach
>
> Where?
>
>> I think that should be good enough.  Now, of course, if you have an
>> idea about how to do it better, I think that's great!  A more
>> general, more elegant solution would be terrific.
>
> I gave a patch and Steven outlined another idea that might be even
> better.  Again, I cannot say if Steven's idea would work without knowing
> what the real bug is.
>
>> But, I don't want perfect to be the enemy of good.
>
> But "papering over the real bug" _is_ the enemy of "good".  That is
> something clearly undesirable, not just suboptimal, especially at the
> beginning of stage1.
>
> I'm not opposing the patch at all costs, but definitely the bug hasn't
> been analyzed thoroughly enough.

And apparently we're now completely stalled. Paul, are you still
working on this? Is there anything you can file in bugzilla, at least,
so this discussion will not get lost?

Ciao!
Steven

Re: [PATCH] Fix CSE bogus RTL creation

[Mark Mitchell]

Steven Bosscher wrote:

>> I'm not opposing the patch at all costs, but definitely the bug hasn't
>> been analyzed thoroughly enough.
> 
> And apparently we're now completely stalled. Paul, are you still
> working on this? Is there anything you can file in bugzilla, at least,
> so this discussion will not get lost?

We do seem badly stuck.

But, I don't understand, at this point, what we can do to get unstuck.
I've just reread the thread and I don't see a clear direction about what
form of patch would be acceptable here.  Or, if we don't understand that
yet, what information we need next.

Paolo, Steven, would you please comment?

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix CSE bogus RTL creation

[Paolo Bonzini]

On 08/05/2010 12:27 AM, Mark Mitchell wrote:
> Steven Bosscher wrote:
>
>>> I'm not opposing the patch at all costs, but definitely the bug hasn't
>>> been analyzed thoroughly enough.
>>
>> And apparently we're now completely stalled. Paul, are you still
>> working on this? Is there anything you can file in bugzilla, at least,
>> so this discussion will not get lost?
>
> We do seem badly stuck.
>
> But, I don't understand, at this point, what we can do to get unstuck.
> I've just reread the thread and I don't see a clear direction about what
> form of patch would be acceptable here.  Or, if we don't understand that
> yet, what information we need next.

We need to know why the non-canonical note gets into an insn.  This is a 
much more serious bug than a non-canonical note.

After that, or if that fails, I posted another patch in the thread and I 
would like to understand if this patch also fixes the bug.

Paolo

Re: [PATCH] Fix CSE bogus RTL creation

[Mark Mitchell]

Paolo Bonzini wrote:

> We need to know why the non-canonical note gets into an insn.  This is a
> much more serious bug than a non-canonical note.

Paul, can you debug the compiler to figure out that question?

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix CSE bogus RTL creation

[Steven Bosscher]

On Thu, Aug 5, 2010 at 2:16 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> Paolo Bonzini wrote:
>
>> We need to know why the non-canonical note gets into an insn.  This is a
>> much more serious bug than a non-canonical note.
>
> Paul, can you debug the compiler to figure out that question?

This issue has gotten stuck again. Ping?

Ciao!
Steven