Fix PR34916, 35519 Combine (Dataflow merge regression.)

Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Andy H]

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

This patch fixes combine bugs. Now cleaned up with Change log entry.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34916
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519

which appeared after dataflow merge (rev 125624).

Could this be committed please? I have tested with cygwin/AVR port and 
there were no regressions.
I cannot test on other targets due to speed of Dejagnu under cygwin.

PS I have assignment paperwork on file with FSF.


2008-03-16 Andy Hutchinson <hutchinsonandy@aim.com>

        PR rtl-optimization/34916
        PR middle-end/35519
         * combine.c (create_log_links): Do not create duplicate LOG_LINKS
         between instruction pairs.


[-- Attachment #2: combine.diff --]
[-- Type: text/plain, Size: 1078 bytes --]

Index: combine.c
===================================================================
--- combine.c   (revision 133282)
+++ combine.c   (working copy)
@@ -976,8 +976,17 @@
                      assignments later.  */
                   if (regno >= FIRST_PSEUDO_REGISTER
                       || asm_noperands (PATTERN (use_insn)) < 0)
-                    LOG_LINKS (use_insn) =
-                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+                    {
+                        /* Don't add duplicates links between instructions. */
+                        rtx links;
+                        for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))
+                            if (insn == XEXP (links, 0))
+                                break;
+                                
+                        if (!links)
+                            LOG_LINKS (use_insn) =
+                              alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+                    }
                 }
               next_use[regno] = NULL_RTX;
             }

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Richard Guenther]

On Tue, Mar 18, 2008 at 10:35 PM, Andy H <hutchinsonandy@aim.com> wrote:
> This patch fixes combine bugs. Now cleaned up with Change log entry.
>
>  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34916
>  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519
>
>  which appeared after dataflow merge (rev 125624).
>
>  Could this be committed please? I have tested with cygwin/AVR port and
>  there were no regressions.
>  I cannot test on other targets due to speed of Dejagnu under cygwin.

That doesn't look cheap.  Also you don't explain how this happens in the
first place.

Richard.

>  PS I have assignment paperwork on file with FSF.
>
>
>  2008-03-16 Andy Hutchinson <hutchinsonandy@aim.com>
>
>         PR rtl-optimization/34916
>         PR middle-end/35519
>          * combine.c (create_log_links): Do not create duplicate LOG_LINKS
>          between instruction pairs.
>
>
> Index: combine.c
>  ===================================================================
>  --- combine.c   (revision 133282)
>  +++ combine.c   (working copy)
>  @@ -976,8 +976,17 @@
>                       assignments later.  */
>                    if (regno >= FIRST_PSEUDO_REGISTER
>                        || asm_noperands (PATTERN (use_insn)) < 0)
>  -                    LOG_LINKS (use_insn) =
>  -                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
>  +                    {
>  +                        /* Don't add duplicates links between instructions. */
>  +                        rtx links;
>  +                        for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))
>  +                            if (insn == XEXP (links, 0))
>  +                                break;
>  +
>  +                        if (!links)
>  +                            LOG_LINKS (use_insn) =
>  +                              alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
>  +                    }
>                  }
>                next_use[regno] = NULL_RTX;
>              }
>
>

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Andy H]

Please refer to PR35519 which contains a detailed explanation.

*http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519*

If necessary, I can provide further clarification.

Anything is cheaper than the current bug but  I could not figure out a 
cheaper way to solve issue.

best regards


Richard Guenther wrote:
> On Tue, Mar 18, 2008 at 10:35 PM, Andy H <hutchinsonandy@aim.com> wrote:
>   
>> This patch fixes combine bugs. Now cleaned up with Change log entry.
>>
>>  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34916
>>  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519
>>
>>  which appeared after dataflow merge (rev 125624).
>>
>>  Could this be committed please? I have tested with cygwin/AVR port and
>>  there were no regressions.
>>  I cannot test on other targets due to speed of Dejagnu under cygwin.
>>     
>
> That doesn't look cheap.  Also you don't explain how this happens in the
> first place.
>
> Richard.
>
>   
>>  PS I have assignment paperwork on file with FSF.
>>
>>
>>  2008-03-16 Andy Hutchinson <hutchinsonandy@aim.com>
>>
>>         PR rtl-optimization/34916
>>         PR middle-end/35519
>>          * combine.c (create_log_links): Do not create duplicate LOG_LINKS
>>          between instruction pairs.
>>
>>
>> Index: combine.c
>>  ===================================================================
>>  --- combine.c   (revision 133282)
>>  +++ combine.c   (working copy)
>>  @@ -976,8 +976,17 @@
>>                       assignments later.  */
>>                    if (regno >= FIRST_PSEUDO_REGISTER
>>                        || asm_noperands (PATTERN (use_insn)) < 0)
>>  -                    LOG_LINKS (use_insn) =
>>  -                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
>>  +                    {
>>  +                        /* Don't add duplicates links between instructions. */
>>  +                        rtx links;
>>  +                        for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))
>>  +                            if (insn == XEXP (links, 0))
>>  +                                break;
>>  +
>>  +                        if (!links)
>>  +                            LOG_LINKS (use_insn) =
>>  +                              alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
>>  +                    }
>>                  }
>>                next_use[regno] = NULL_RTX;
>>              }
>>
>>
>>     

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Richard Guenther]

On Tue, Mar 18, 2008 at 11:27 PM, Andy H <hutchinsonandy@aim.com> wrote:
> Please refer to PR35519 which contains a detailed explanation.
>
>  *http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519*
>
>  If necessary, I can provide further clarification.
>
>  Anything is cheaper than the current bug but  I could not figure out a
>  cheaper way to solve issue.

From the comment it seems you could get away just checking the first element
for the duplicate and not bother to continue walking if that didn't match.

You can add a ENABLE_CHECKING path that verifies this assumption.

Otherwise I think the log-links are a poor data structure ;)

Richard.

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Andy H]

Log_links are  awkward - I can easily agree - I did not create them.

But short of a major change to  combine, there is no simple solution.

I looked at just using  DF information - but DF only gives all DEFs - 
not just adjacent DEFs,  so you have to walk instructions to reject 
those with intervening USEs.

I was tempted to leave in duplicates and look for match pairs/triples 
during instruction combine attempts - it looks cheap but of course is 
very expensive!

Check first element might work. The registers are grouped because they 
happen to have been put in DF lists at same time. But there is no 
written constraint that says DF could not re-order the registers in its 
chains - or that the DF chains  have any order. So I did not want to 
propose patch that would break so easily.

The log_links list  being walked is very short - only one element per 
immediately linked instruction. So typical length is perhaps 2 (without 
duplicates). The largest would be for an instruction which has many 
input operands where each is the output of an instructions in same 
block, with no intervening usage.   Maybe a libcall call of some type.  
But still short list!

The bug is problematic as you will have noted from 
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34916 so excuse my 
persistence. :-P

Andy





Richard Guenther wrote:
> On Tue, Mar 18, 2008 at 11:27 PM, Andy H <hutchinsonandy@aim.com> wrote:
>   
>> Please refer to PR35519 which contains a detailed explanation.
>>
>>  *http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519*
>>
>>  If necessary, I can provide further clarification.
>>
>>  Anything is cheaper than the current bug but  I could not figure out a
>>  cheaper way to solve issue.
>>     
>
> From the comment it seems you could get away just checking the first element
> for the duplicate and not bother to continue walking if that didn't match.
>
> You can add a ENABLE_CHECKING path that verifies this assumption.
>
> Otherwise I think the log-links are a poor data structure ;)
>
> Richard.
>   

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Paolo Bonzini]

> The log_links list  being walked is very short - only one element per 
> immediately linked instruction. So typical length is perhaps 2 (without 
> duplicates). The largest would be for an instruction which has many 
> input operands where each is the output of an instructions in same 
> block, with no intervening usage.   Maybe a libcall call of some type.  
> But still short list!

I agree, create_log_links doesn't even add LOG_LINKS to asms, which 
potentially have a lot of uses.  I think this is entirely comparable to 
using insertion sort because you know the size of the array is small.

I cannot approve this though (and would not like to override Richi anyway).

Paolo

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Paolo Bonzini]

> The log_links list  being walked is very short - only one element per 
> immediately linked instruction. So typical length is perhaps 2 (without 
> duplicates). The largest would be for an instruction which has many 
> input operands where each is the output of an instructions in same 
> block, with no intervening usage.   Maybe a libcall call of some type.  
> But still short list!

I agree, create_log_links doesn't even add LOG_LINKS to asms, which 
potentially have a lot of uses.  I think this is entirely comparable to 
using insertion sort because you know the size of the array is small.

I cannot approve this though (and would not like to override Richi anyway).

Paolo

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Richard Guenther]

On Wed, Mar 19, 2008 at 8:30 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>
>  > The log_links list  being walked is very short - only one element per
>  > immediately linked instruction. So typical length is perhaps 2 (without
>  > duplicates). The largest would be for an instruction which has many
>  > input operands where each is the output of an instructions in same
>  > block, with no intervening usage.   Maybe a libcall call of some type.
>  > But still short list!
>
>  I agree, create_log_links doesn't even add LOG_LINKS to asms, which
>  potentially have a lot of uses.  I think this is entirely comparable to
>  using insertion sort because you know the size of the array is small.
>
>  I cannot approve this though (and would not like to override Richi anyway).

So I'll take your word for it and approve the patch for trunk.  If there are
no problems within a few days it is also ok for the 4.3 branch as this is
obviously a regression, right?

Thanks,
Richard.

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Paolo Bonzini]

> So I'll take your word for it and approve the patch for trunk.

Thanks!

> If there are
> no problems within a few days it is also ok for the 4.3 branch as this is
> obviously a regression, right?

Yes.

Paolo

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Paolo Bonzini]

> So I'll take your word for it and approve the patch for trunk.

Thanks!

> If there are
> no problems within a few days it is also ok for the 4.3 branch as this is
> obviously a regression, right?

Yes.

Paolo

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Jakub Jelinek]

On Tue, Mar 18, 2008 at 05:35:39PM -0400, Andy H wrote:
> 2008-03-16 Andy Hutchinson <hutchinsonandy@aim.com>
> 
>        PR rtl-optimization/34916
>        PR middle-end/35519
>         * combine.c (create_log_links): Do not create duplicate LOG_LINKS
>         between instruction pairs.
> 

> Index: combine.c
> ===================================================================
> --- combine.c   (revision 133282)
> +++ combine.c   (working copy)
> @@ -976,8 +976,17 @@
>                       assignments later.  */
>                    if (regno >= FIRST_PSEUDO_REGISTER
>                        || asm_noperands (PATTERN (use_insn)) < 0)
> -                    LOG_LINKS (use_insn) =
> -                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
> +                    {
> +                        /* Don't add duplicates links between instructions. */
> +                        rtx links;
> +                        for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))
> +                            if (insn == XEXP (links, 0))
> +                                break;
> +                                
> +                        if (!links)
> +                            LOG_LINKS (use_insn) =
> +                              alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
> +                    }

Please fix formatting, the indentation is supposed to be only 2 spaces rather
than 4 as you've done, also a tab should be used instead of each 8 spaces.

	Jakub

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[hutchinsonandy]

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


Reformatted identation and corrected spelling mistake. I used all 
spaces - as most of combine.c does the same.

2008-03-19 Andy Hutchinson <hutchinsonandy@aim.com>

  PR rtl-optimization/34916
  PR middle-end/35519
  * combine.c (create_log_links): Do not create duplicate LOG_LINKS
  between instruction pairs.




[-- Attachment #2: combine.diff --]
[-- Type: text/plain, Size: 1058 bytes --]

Index: combine.c
===================================================================
--- combine.c	(revision 133342)
+++ combine.c	(working copy)
@@ -976,8 +976,17 @@
                      assignments later.  */
                   if (regno >= FIRST_PSEUDO_REGISTER
                       || asm_noperands (PATTERN (use_insn)) < 0)
-                    LOG_LINKS (use_insn) =
-                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+                    {
+                      /* Don't add duplicate links between instructions.  */
+                      rtx links;
+                      for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))
+                        if (insn == XEXP (links, 0))
+                          break;
+
+                      if (!links)
+                        LOG_LINKS (use_insn) =
+                          alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+                    }
                 }
               next_use[regno] = NULL_RTX;
             }
@@ -13056,3 +13065,4 @@
  }
 };
 
+

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[hutchinsonandy]

Can this now be committed?

Andy


-----Original Message-----
From: hutchinsonandy@aim.com
To: jakub@redhat.com
Cc: gcc-patches@gcc.gnu.org; steven@gcc.gnu.org
Sent: Wed, 19 Mar 2008 8:49 am
Subject: Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)


Reformatted identation and corrected spelling mistake. I used all 
spaces - as most of combine.c does the same. 
 
2008-03-19 Andy Hutchinson <hutchinsonandy@aim.com> 
 
 PR rtl-optimization/34916 
 PR middle-end/35519 
 * combine.c (create_log_links): Do not create duplicate LOG_LINKS 
 between instruction pairs. 
 
 

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Eric Botcazou]

> Can this now be committed?

No, please use TABS as instructed by Jakub.  If you don't see any of them in 
combine.c, then you most likely have a problem with your editor.

-- 
Eric Botcazou

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[hutchinsonandy]

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

I apologise for mistake.

I was trying to  match existing combine.c  which does not always use 
tabs to replace 8 spaces, as you can see from diff.

 here  is same patch with TABS replacing 8 leading spaces.


Andy

2008-03-25 Andy Hutchinson <hutchinsonandy@aim.com>

 PR rtl-optimization/34916
 PR middle-end/35519
 * combine.c (create_log_links): Do not create duplicate LOG_LINKS
 between instruction pairs.




-----Original Message-----
From: Eric Botcazou <ebotcazou@adacore.com>
To: hutchinsonandy@aim.com
Cc: gcc-patches@gcc.gnu.org; jakub@redhat.com; steven@gcc.gnu.org
Sent: Tue, 25 Mar 2008 6:24 am
Subject: Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)



> Can this now be committed?

No, please use TABS as instructed by Jakub.  If you don't see any of 
them in
combine.c, then you most likely have a problem with your editor.

--
Eric Botcazou


[-- Attachment #2: combine.diff --]
[-- Type: text/plain, Size: 899 bytes --]

Index: combine.c
===================================================================
--- combine.c	(revision 133510)
+++ combine.c	(working copy)
@@ -976,8 +976,17 @@
                      assignments later.  */
                   if (regno >= FIRST_PSEUDO_REGISTER
                       || asm_noperands (PATTERN (use_insn)) < 0)
-                    LOG_LINKS (use_insn) =
-                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+		    {
+		      /* Don't add duplicate links between instructions.  */
+		      rtx links;
+		      for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))
+		        if (insn == XEXP (links, 0))
+			  break;
+
+		      if (!links)
+			LOG_LINKS (use_insn) =
+			  alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+		    }
                 }
               next_use[regno] = NULL_RTX;
             }
@@ -13056,3 +13065,5 @@
  }
 };
 
+
+

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Jakub Jelinek]

On Tue, Mar 25, 2008 at 08:30:32AM -0400, hutchinsonandy@aim.com wrote:
> --- combine.c	(revision 133510)
> +++ combine.c	(working copy)
> @@ -976,8 +976,17 @@
>                       assignments later.  */
>                    if (regno >= FIRST_PSEUDO_REGISTER
>                        || asm_noperands (PATTERN (use_insn)) < 0)
> -                    LOG_LINKS (use_insn) =
> -                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
> +		    {
> +		      /* Don't add duplicate links between instructions.  */
> +		      rtx links;
> +		      for (links = LOG_LINKS (use_insn); links; links = XEXP (links, 1))

This line is too long (89 chars), put links = XEXP (links, 1)) on a separate line.

> @@ -13056,3 +13065,5 @@
>   }
>  };
>  
> +
> +

And this is completely unnecessary and unrelated change.

	Jakub

Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[hutchinsonandy]

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

Corrections applied

Third time lucky?




-----Original Message-----
From: Jakub Jelinek <jakub@redhat.com>
To: hutchinsonandy@aim.com
Cc: ebotcazou@adacore.com; gcc-patches@gcc.gnu.org; steven@gcc.gnu.org
Sent: Tue, 25 Mar 2008 7:45 am
Subject: Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)



On Tue, Mar 25, 2008 at 08:30:32AM -0400, hutchinsonandy@aim.com wrote:
> --- combine.c (revision 133510)
> +++ combine.c (working copy)
> @@ -976,8 +976,17 @@
>                       assignments later.  */
>                    if (regno >= FIRST_PSEUDO_REGISTER
>                        || asm_noperands (PATTERN (use_insn)) < 0)
> -                    LOG_LINKS (use_insn) =
> -                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
> +         {
> +           /* Don't add duplicate links between instructions.  */
> +           rtx links;
> +           for (links = LOG_LINKS (use_insn); links; links = XEXP 
(links, 1))

This line is too long (89 chars), put links = XEXP (links, 1)) on a 
separate
line.

> @@ -13056,3 +13065,5 @@
>   }
>  };
>
> +
> +

And this is completely unnecessary and unrelated change.

    Jakub


[-- Attachment #2: combine.diff --]
[-- Type: text/plain, Size: 867 bytes --]

Index: combine.c
===================================================================
--- combine.c	(revision 133510)
+++ combine.c	(working copy)
@@ -976,8 +976,18 @@
                      assignments later.  */
                   if (regno >= FIRST_PSEUDO_REGISTER
                       || asm_noperands (PATTERN (use_insn)) < 0)
-                    LOG_LINKS (use_insn) =
-                      alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+		    {
+		      /* Don't add duplicate links between instructions.  */
+		      rtx links;
+		      for (links = LOG_LINKS (use_insn); links;
+			   links = XEXP (links, 1))
+		        if (insn == XEXP (links, 0))
+			  break;
+
+		      if (!links)
+			LOG_LINKS (use_insn) =
+			  alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+		    }
                 }
               next_use[regno] = NULL_RTX;
             }

[PING] Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Andy H]

Is this patch ok now for approval and comit mainline?

http://gcc.gnu.org/ml/gcc-patches/2008-03/msg01475.html

Andy

Re: [PING] Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Richard Guenther]

On Thu, Apr 3, 2008 at 2:20 AM, Andy H <hutchinsonandy@aim.com> wrote:
> Is this patch ok now for approval and comit mainline?
>
>  http://gcc.gnu.org/ml/gcc-patches/2008-03/msg01475.html

Yes.

I see you don't have SVN write access - please apply for it on
http://sourceware.org/cgi-bin/pdw/ps_form.cgi, you can use me as
a sponsor.  (I suppose your paperwork is on file)

Thanks,
Richard.

Re: [PING] Re: Fix PR34916, 35519 Combine (Dataflow merge regression.)

[Gerald Pfeifer]

On Thu, 3 Apr 2008, Richard Guenther wrote:
> I see you don't have SVN write access - please apply for it on
> http://sourceware.org/cgi-bin/pdw/ps_form.cgi, you can use me as
> a sponsor.  (I suppose your paperwork is on file)

Confirmed -- paperwork is on file.

As a general note, please don't hand out SVN write access without 
confirming this a priori.  I am happy to help with that, and I know that 
David Edelsohn also has access to the fsf.org cluster, for example.

Gerald