Combiner fix for PR79910

Combiner fix for PR79910

[Bernd Schmidt]

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

In this PR, we have a few insns involved in two instruction combinations:

insn 16: set r100
insn 27: some calculation
insn 28: some calculation
insn 32: using r100
insn 33: using r100
insn 35: some calculation

Then we combine insns 27, 28 and 33, producing two output insns, As a 
result, insn 28 (i2) now obtains a use of r100. But insn 32, which is 
not involved in this combination, has the LOG_LINKS entry for that 
register, and we don't know that we need to update it. As a result, the 
second combination, involving regs 16, 32 and 35 (based on the remaining 
LOG_LINK for r100), produces incorrect code, as we don't realize there's 
a use of r100 before insn 32.

The following fixes it. Bootstrapped and tested on x86_64-linux, ok (on 
all branches)?


Bernd


[-- Attachment #2: 79910.diff --]
[-- Type: text/x-patch, Size: 6022 bytes --]

	PR rtl-optimization/79910
	* combine.c (record_used_regs): New static function.
	(try_combine): Handle situations where there is an additional
	instruction between I2 and I3 which needs to have a LOG_LINK
	updated.

	PR rtl-optimization/79910
	* gcc.dg/torture/pr79910.c: New test.

Index: gcc/combine.c
===================================================================
--- gcc/combine.c	(revision 245685)
+++ gcc/combine.c	(working copy)
@@ -2559,6 +2560,57 @@ can_split_parallel_of_n_reg_sets (rtx_in
   return true;
 }
 
+/* Set up a set of registers used in an insn.  Called through note_uses,
+   arguments as described for that function.  */
+
+static void
+record_used_regs (rtx *xptr, void *data)
+{
+  bitmap set = (bitmap)data;
+  int i, j;
+  enum rtx_code code;
+  const char *fmt;
+  rtx x = *xptr;
+
+  /* repeat is used to turn tail-recursion into iteration since GCC
+     can't do it when there's no return value.  */
+ repeat:
+  if (x == 0)
+    return;
+
+  code = GET_CODE (x);
+  if (REG_P (x))
+    {
+      unsigned regno = REGNO (x);
+      unsigned end_regno = END_REGNO (x);
+      while (regno < end_regno)
+	bitmap_set_bit (set, regno++);
+      return;
+    }
+
+  /* Recursively scan the operands of this expression.  */
+
+  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  /* If we are about to do the last recursive call
+	     needed at this level, change it into iteration.
+	     This function is called enough to be worth it.  */
+	  if (i == 0)
+	    {
+	      x = XEXP (x, 0);
+	      goto repeat;
+	    }
+
+	  record_used_regs (&XEXP (x, i), data);
+	}
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  record_used_regs (&XVECEXP (x, i, j), data);
+    }
+}
+
 /* Try to combine the insns I0, I1 and I2 into I3.
    Here I0, I1 and I2 appear earlier than I3.
    I0 and I1 can be zero; then we combine just I2 into I3, or I1 and I2 into
@@ -2742,6 +2794,21 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
 
   added_links_insn = 0;
 
+  auto_bitmap i2_regset, i3_regset, links_regset;
+  note_uses (&PATTERN (i2), record_used_regs, (bitmap)i2_regset);
+  note_uses (&PATTERN (i3), record_used_regs, (bitmap)i3_regset);
+  insn_link *ll;
+  FOR_EACH_LOG_LINK (ll, i3)
+    bitmap_set_bit (links_regset, ll->regno);
+  FOR_EACH_LOG_LINK (ll, i2)
+    bitmap_set_bit (links_regset, ll->regno);
+  if (i1)
+   FOR_EACH_LOG_LINK (ll, i1)
+      bitmap_set_bit (links_regset, ll->regno);
+  if (i0)
+    FOR_EACH_LOG_LINK (ll, i0)
+      bitmap_set_bit (links_regset, ll->regno);
+
   /* First check for one important special case that the code below will
      not handle.  Namely, the case where I1 is zero, I2 is a PARALLEL
      and I3 is a SET whose SET_SRC is a SET_DEST in I2.  In that case,
@@ -4051,6 +4124,33 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
       return 0;
     }
 
+  auto_bitmap new_regs_in_i2;
+  if (newi2pat)
+    {
+      /* We need to discover situations where we introduce a use of a
+	 register into I2, where none of the existing LOG_LINKS contain
+	 a reference to it.  This can happen if previously I3 referenced
+	 the reg, and there is an additional use between I2 and I3.  We
+	 must remove the LOG_LINKS entry from that additional use and
+	 distribute it along with our own ones.  */
+	note_uses (&newi2pat, record_used_regs, (bitmap)new_regs_in_i2);
+	bitmap_and_compl_into (new_regs_in_i2, i2_regset);
+	bitmap_and_compl_into (new_regs_in_i2, links_regset);
+
+	/* Here, we first look for situations where a hard register use
+	   moved, and just give up.  This should happen approximately
+	   never, and it's not worth it to deal with possibilities like
+	   multi-word registers.  Later, when fixing up LOG_LINKS, we
+	   deal with the case where a pseudo use moved.  */
+	if (prev_nonnote_insn (i3) != i2)
+	  for (unsigned r = 0; r < FIRST_PSEUDO_REGISTER; r++)
+	    if (bitmap_bit_p (new_regs_in_i2, r))
+	      {
+		undo_all ();
+		return 0;
+	    }
+    }
+
   if (MAY_HAVE_DEBUG_INSNS)
     {
       struct undo *undo;
@@ -4494,6 +4594,45 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
 			    NULL_RTX, NULL_RTX, NULL_RTX);
       }
 
+    if (newi2pat)
+      {
+	bitmap_iterator iter;
+	unsigned int i;
+
+	/* See comments above where we calculate the bitmap.  */
+	EXECUTE_IF_SET_IN_BITMAP ((bitmap)new_regs_in_i2,
+				  LAST_VIRTUAL_REGISTER, i, iter)
+	  {
+	    rtx reg = regno_reg_rtx[i];
+	    rtx_insn *other;
+	    for (other = NEXT_INSN (i2); other != i3; other = NEXT_INSN (other))
+	      if (NONDEBUG_INSN_P (other)
+		  && (reg_overlap_mentioned_p (reg, PATTERN (other))
+		      || (CALL_P (other) && find_reg_fusage (other, USE, reg))))
+		{
+		  if (dump_file)
+		    fprintf (dump_file,
+			     "found extra use of reg %d at insn %d\n", i,
+			     INSN_UID (other));
+		  insn_link **plink;
+		  for (plink = &LOG_LINKS (other);
+		       *plink;
+		       plink = &(*plink)->next)
+		    {
+		      insn_link *link = *plink;
+		      if (link->regno == i)
+			{
+			  *plink = link->next;
+			  link->next = i3links;
+			  i3links = link;
+			  break;
+			}
+		    }
+		  break;
+		}
+	  }
+      }
+
     distribute_links (i3links);
     distribute_links (i2links);
     distribute_links (i1links);
Index: gcc/testsuite/gcc.dg/torture/pr79910.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr79910.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr79910.c	(working copy)
@@ -0,0 +1,29 @@
+/* { dg-do run } */
+/* { dg-additional-options "-fweb" } */
+
+typedef unsigned char u8;
+typedef unsigned int u32;
+typedef unsigned long long u64;
+int a;
+
+static __attribute__ ((noinline, noclone)) u64
+foo (u8 p1, u32 p2)
+{
+  u64 b = a <= 0;
+  p2 = 4;
+  b >>= a == 0;
+  p1 %= 0xfffffffff;
+  p2 >>= b & 31;
+  p1 += b;
+  p2 <<= 31;
+  return p1 + p2 + b;
+}
+
+int
+main (void)
+{
+  u64 x = foo (0, 1);
+  if (x != 0)
+    __builtin_abort ();
+  return 0;
+}

Re: Combiner fix for PR79910

[Jeff Law]

On 03/10/2017 04:24 PM, Bernd Schmidt wrote:
> In this PR, we have a few insns involved in two instruction combinations:
>
> insn 16: set r100
> insn 27: some calculation
> insn 28: some calculation
> insn 32: using r100
> insn 33: using r100
> insn 35: some calculation
>
> Then we combine insns 27, 28 and 33, producing two output insns, As a
> result, insn 28 (i2) now obtains a use of r100. But insn 32, which is
> not involved in this combination, has the LOG_LINKS entry for that
> register, and we don't know that we need to update it. As a result, the
> second combination, involving regs 16, 32 and 35 (based on the remaining
> LOG_LINK for r100), produces incorrect code, as we don't realize there's
> a use of r100 before insn 32.
>
> The following fixes it. Bootstrapped and tested on x86_64-linux, ok (on
> all branches)?
>
>
> Bernd
>
>
> 79910.diff
>
>
> 	PR rtl-optimization/79910
> 	* combine.c (record_used_regs): New static function.
> 	(try_combine): Handle situations where there is an additional
> 	instruction between I2 and I3 which needs to have a LOG_LINK
> 	updated.
>
> 	PR rtl-optimization/79910
> 	* gcc.dg/torture/pr79910.c: New test.
What a nasty little problem.

I don't like that we have to build these bitmaps due to the compile-time 
cost.  Would it make sense to only build them when i0/i1 exist?

We don't do 4->3 combinations, just 4->2 and 3->2, so it's only the 
i2pattern where we might need to conjure up a LOG_LINK, right?


We don't do 4->3 combinations, right?  So we only have to care about 
when there's going to be an newi2pat, right (3->2 or 4->2).
We don't ever create a newi1pat (for a 4->3 combination), right?  So we 
only have to worry about testing when there's a newi2pat, right?


Do you need to handle 4->3, in which case the new bits could be on newi1pat?
>
> Index: gcc/combine.c
> ===================================================================
> --- gcc/combine.c	(revision 245685)
> +++ gcc/combine.c	(working copy)
> @@ -2559,6 +2560,57 @@ can_split_parallel_of_n_reg_sets (rtx_in
>    return true;
>  }
>

> @@ -4051,6 +4124,33 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
>        return 0;
>      }
>
> +  auto_bitmap new_regs_in_i2;
> +  if (newi2pat)
> +    {
> +      /* We need to discover situations where we introduce a use of a
> +	 register into I2, where none of the existing LOG_LINKS contain
> +	 a reference to it.  This can happen if previously I3 referenced
> +	 the reg, and there is an additional use between I2 and I3.  We
> +	 must remove the LOG_LINKS entry from that additional use and
> +	 distribute it along with our own ones.  */
> +	note_uses (&newi2pat, record_used_regs, (bitmap)new_regs_in_i2);
> +	bitmap_and_compl_into (new_regs_in_i2, i2_regset);
> +	bitmap_and_compl_into (new_regs_in_i2, links_regset);
> +
> +	/* Here, we first look for situations where a hard register use
> +	   moved, and just give up.  This should happen approximately
> +	   never, and it's not worth it to deal with possibilities like
> +	   multi-word registers.  Later, when fixing up LOG_LINKS, we
> +	   deal with the case where a pseudo use moved.  */
> +	if (prev_nonnote_insn (i3) != i2)
> +	  for (unsigned r = 0; r < FIRST_PSEUDO_REGISTER; r++)
> +	    if (bitmap_bit_p (new_regs_in_i2, r))
if (prev_nonnote_insn (i3) != i2
     && bitmap_first_set_bit (new_regs_in_i2) < FIRST_PSEUDO_REGISTER)

?



Overall it seems reasonable.  If possible, let's avoid the calls to 
create the bitmaps in case where we know we'll never be creating a new 
use in i2.

I'm not wed to using bitmap_first_set_bit.  It's clearer and may be 
faster since you're not doing a ton of calls into bitmap_bit_p.  The 
bitmap_first_set_bit implementation under the hood finds the word within 
the first bitmap element that is nonzero, then uses ctzl on that to get 
its bit.

Jeff

Re: Combiner fix for PR79910

[Bernd Schmidt]

On 03/15/2017 12:03 AM, Jeff Law wrote:
> On 03/10/2017 04:24 PM, Bernd Schmidt wrote:
>>
>>     PR rtl-optimization/79910
>>     * combine.c (record_used_regs): New static function.
>>     (try_combine): Handle situations where there is an additional
>>     instruction between I2 and I3 which needs to have a LOG_LINK
>>     updated.
>>
>>     PR rtl-optimization/79910
>>     * gcc.dg/torture/pr79910.c: New test.
> What a nasty little problem.
>
> I don't like that we have to build these bitmaps due to the compile-time
> cost.  Would it make sense to only build them when i0/i1 exist?

I suppose at the moment we don't do 2->2 combinations, so we could 
conditionalize this on having an i1.

> We don't do 4->3 combinations, just 4->2 and 3->2, so it's only the
> i2pattern where we might need to conjure up a LOG_LINK, right?
>
>
> We don't do 4->3 combinations, right?  So we only have to care about
> when there's going to be an newi2pat, right (3->2 or 4->2).

> We don't ever create a newi1pat (for a 4->3 combination), right?  So we
> only have to worry about testing when there's a newi2pat, right?

Yes to all, there isn't a newi1pat, only 4->2 and 3->2 can be an issue.

>> +    if (prev_nonnote_insn (i3) != i2)
>> +      for (unsigned r = 0; r < FIRST_PSEUDO_REGISTER; r++)
>> +        if (bitmap_bit_p (new_regs_in_i2, r))
> if (prev_nonnote_insn (i3) != i2
>     && bitmap_first_set_bit (new_regs_in_i2) < FIRST_PSEUDO_REGISTER)

Ah. I had wondered about the loop but only thought in the direction of 
intersecting this bitmap with one of all hard regs (and I think there 
isn't such a bitmap, so I kept the loop). I'll retest with your 
suggestion and with the bitmap creation conditional on i1 being nonnull.


Bernd

Re: Combiner fix for PR79910

[Bernd Schmidt]

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

On 03/15/2017 12:09 AM, Bernd Schmidt wrote:
>  I'll retest with your
> suggestion and with the bitmap creation conditional on i1 being nonnull.

Like this (also had to throw in a bitmap_empty_p). Retested as before. Ok?


Bernd


[-- Attachment #2: combine-v3.diff --]
[-- Type: text/x-patch, Size: 5752 bytes --]

Index: gcc/combine.c
===================================================================
--- gcc/combine.c	(revision 245685)
+++ gcc/combine.c	(working copy)
@@ -104,6 +104,7 @@ along with GCC; see the file COPYING3.
 #include "valtrack.h"
 #include "rtl-iter.h"
 #include "print-rtl.h"
+#include "dbgcnt.h"
 
 /* Number of attempts to combine instructions in this function.  */
 
@@ -2559,6 +2560,57 @@ can_split_parallel_of_n_reg_sets (rtx_in
   return true;
 }
 
+/* Set up a set of registers used in an insn.  Called through note_uses,
+   arguments as described for that function.  */
+
+static void
+record_used_regs (rtx *xptr, void *data)
+{
+  bitmap set = (bitmap)data;
+  int i, j;
+  enum rtx_code code;
+  const char *fmt;
+  rtx x = *xptr;
+
+  /* repeat is used to turn tail-recursion into iteration since GCC
+     can't do it when there's no return value.  */
+ repeat:
+  if (x == 0)
+    return;
+
+  code = GET_CODE (x);
+  if (REG_P (x))
+    {
+      unsigned regno = REGNO (x);
+      unsigned end_regno = END_REGNO (x);
+      while (regno < end_regno)
+	bitmap_set_bit (set, regno++);
+      return;
+    }
+
+  /* Recursively scan the operands of this expression.  */
+
+  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  /* If we are about to do the last recursive call
+	     needed at this level, change it into iteration.
+	     This function is called enough to be worth it.  */
+	  if (i == 0)
+	    {
+	      x = XEXP (x, 0);
+	      goto repeat;
+	    }
+
+	  record_used_regs (&XEXP (x, i), data);
+	}
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  record_used_regs (&XVECEXP (x, i, j), data);
+    }
+}
+
 /* Try to combine the insns I0, I1 and I2 into I3.
    Here I0, I1 and I2 appear earlier than I3.
    I0 and I1 can be zero; then we combine just I2 into I3, or I1 and I2 into
@@ -2742,6 +2794,27 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
 
   added_links_insn = 0;
 
+  /* For combinations that may result in two insns, we have to gather
+     some extra information about registers used, so that we can
+     update all relevant LOG_LINKS later.  */
+  auto_bitmap i2_regset, i3_regset, links_regset;
+  if (i1)
+    {
+      note_uses (&PATTERN (i2), record_used_regs, (bitmap)i2_regset);
+      note_uses (&PATTERN (i3), record_used_regs, (bitmap)i3_regset);
+      insn_link *ll;
+      FOR_EACH_LOG_LINK (ll, i3)
+	bitmap_set_bit (links_regset, ll->regno);
+      FOR_EACH_LOG_LINK (ll, i2)
+	bitmap_set_bit (links_regset, ll->regno);
+      if (i1)
+	FOR_EACH_LOG_LINK (ll, i1)
+	  bitmap_set_bit (links_regset, ll->regno);
+      if (i0)
+	FOR_EACH_LOG_LINK (ll, i0)
+	  bitmap_set_bit (links_regset, ll->regno);
+    }
+
   /* First check for one important special case that the code below will
      not handle.  Namely, the case where I1 is zero, I2 is a PARALLEL
      and I3 is a SET whose SET_SRC is a SET_DEST in I2.  In that case,
@@ -4004,6 +4077,12 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
 	}
     }
 
+  if (!dbg_cnt (combine))
+    {
+      undo_all ();
+      return 0;
+    }
+
   /* If it still isn't recognized, fail and change things back the way they
      were.  */
   if ((insn_code_number < 0
@@ -4051,6 +4130,33 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
       return 0;
     }
 
+  auto_bitmap new_regs_in_i2;
+  if (newi2pat)
+    {
+      /* We need to discover situations where we introduce a use of a
+	 register into I2, where none of the existing LOG_LINKS contain
+	 a reference to it.  This can happen if previously I3 referenced
+	 the reg, and there is an additional use between I2 and I3.  We
+	 must remove the LOG_LINKS entry from that additional use and
+	 distribute it along with our own ones.  */
+	note_uses (&newi2pat, record_used_regs, (bitmap)new_regs_in_i2);
+	bitmap_and_compl_into (new_regs_in_i2, i2_regset);
+	bitmap_and_compl_into (new_regs_in_i2, links_regset);
+
+	/* Here, we first look for situations where a hard register use
+	   moved, and just give up.  This should happen approximately
+	   never, and it's not worth it to deal with possibilities like
+	   multi-word registers.  Later, when fixing up LOG_LINKS, we
+	   deal with the case where a pseudo use moved.  */
+	if (!bitmap_empty_p (new_regs_in_i2)
+	    && prev_nonnote_insn (i3) != i2
+	    && bitmap_first_set_bit (new_regs_in_i2) < FIRST_PSEUDO_REGISTER)
+	  {
+	    undo_all ();
+	    return 0;
+	  }
+    }
+
   if (MAY_HAVE_DEBUG_INSNS)
     {
       struct undo *undo;
@@ -4494,6 +4600,45 @@ try_combine (rtx_insn *i3, rtx_insn *i2,
 			    NULL_RTX, NULL_RTX, NULL_RTX);
       }
 
+    if (newi2pat)
+      {
+	bitmap_iterator iter;
+	unsigned int i;
+
+	/* See comments above where we calculate the bitmap.  */
+	EXECUTE_IF_SET_IN_BITMAP ((bitmap)new_regs_in_i2,
+				  LAST_VIRTUAL_REGISTER, i, iter)
+	  {
+	    rtx reg = regno_reg_rtx[i];
+	    rtx_insn *other;
+	    for (other = NEXT_INSN (i2); other != i3; other = NEXT_INSN (other))
+	      if (NONDEBUG_INSN_P (other)
+		  && (reg_overlap_mentioned_p (reg, PATTERN (other))
+		      || (CALL_P (other) && find_reg_fusage (other, USE, reg))))
+		{
+		  if (dump_file)
+		    fprintf (dump_file,
+			     "found extra use of reg %d at insn %d\n", i,
+			     INSN_UID (other));
+		  insn_link **plink;
+		  for (plink = &LOG_LINKS (other);
+		       *plink;
+		       plink = &(*plink)->next)
+		    {
+		      insn_link *link = *plink;
+		      if (link->regno == i)
+			{
+			  *plink = link->next;
+			  link->next = i3links;
+			  i3links = link;
+			  break;
+			}
+		    }
+		  break;
+		}
+	  }
+      }
+
     distribute_links (i3links);
     distribute_links (i2links);
     distribute_links (i1links);

Re: Combiner fix for PR79910

[Bernd Schmidt]

On 03/15/2017 04:00 PM, Bernd Schmidt wrote:
> On 03/15/2017 12:09 AM, Bernd Schmidt wrote:
>>  I'll retest with your
>> suggestion and with the bitmap creation conditional on i1 being nonnull.
>
> Like this (also had to throw in a bitmap_empty_p). Retested as before. Ok?

Oops, that one also has dbg_cnt stuff in it which I was going to remove. 
If you want to approve that along with the rest, the following bit is 
also needed:

Index: gcc/dbgcnt.def
===================================================================
--- gcc/dbgcnt.def	(revision 245685)
+++ gcc/dbgcnt.def	(working copy)
@@ -145,6 +145,7 @@ DEBUG_COUNTER (asan_use_after_scope)
  DEBUG_COUNTER (auto_inc_dec)
  DEBUG_COUNTER (ccp)
  DEBUG_COUNTER (cfg_cleanup)
+DEBUG_COUNTER (combine)
  DEBUG_COUNTER (cprop)
  DEBUG_COUNTER (cse2_move2add)
  DEBUG_COUNTER (dce)


Bernd

Re: Combiner fix for PR79910

[Jeff Law]

On 03/15/2017 09:00 AM, Bernd Schmidt wrote:
> On 03/15/2017 12:09 AM, Bernd Schmidt wrote:
>>  I'll retest with your
>> suggestion and with the bitmap creation conditional on i1 being nonnull.
>
> Like this (also had to throw in a bitmap_empty_p). Retested as before. Ok?
Yea, not surprised you needed the bitmap_empty_p.

OK with or without the debug counter -- your decide on whether or not to 
include it.

jeff

Re: Combiner fix for PR79910

[Jeff Law]

On 03/15/2017 11:07 AM, Jeff Law wrote:
> On 03/15/2017 09:00 AM, Bernd Schmidt wrote:
>> On 03/15/2017 12:09 AM, Bernd Schmidt wrote:
>>>  I'll retest with your
>>> suggestion and with the bitmap creation conditional on i1 being nonnull.
>>
>> Like this (also had to throw in a bitmap_empty_p). Retested as before.
>> Ok?
> Yea, not surprised you needed the bitmap_empty_p.
>
> OK with or without the debug counter -- your decide on whether or not to
> include it.
Given your note that you had planned to remove the dbg_cnt stuff, I went 
ahead and remove the dbg_cnt stuff, and installed the patch (and testcase).

Jeff

Re: Combiner fix for PR79910

[Segher Boessenkool]

Thanks for not cc:ing me on any of this.

On Wed, Mar 15, 2017 at 04:00:21PM +0100, Bernd Schmidt wrote:
> +/* Set up a set of registers used in an insn.  Called through note_uses,
> +   arguments as described for that function.  */
> +
> +static void
> +record_used_regs (rtx *xptr, void *data)
> +{
> +  bitmap set = (bitmap)data;

Space after cast, throughout.

> +  int i, j;
> +  enum rtx_code code;
> +  const char *fmt;
> +  rtx x = *xptr;
> +
> +  /* repeat is used to turn tail-recursion into iteration since GCC
> +     can't do it when there's no return value.  */
> + repeat:

This comment is incorrect.

> +	  /* If we are about to do the last recursive call
> +	     needed at this level, change it into iteration.
> +	     This function is called enough to be worth it.  */

This function is called enough that it should not be called at all.

> +  /* For combinations that may result in two insns, we have to gather
> +     some extra information about registers used, so that we can
> +     update all relevant LOG_LINKS later.  */

Please just refuse to do the combination in such cases instead.

> +	/* See comments above where we calculate the bitmap.  */
> +	EXECUTE_IF_SET_IN_BITMAP ((bitmap)new_regs_in_i2,
> +				  LAST_VIRTUAL_REGISTER, i, iter)

Why do you need a cast here at all?

> +	  {
> +	    rtx reg = regno_reg_rtx[i];
> +	    rtx_insn *other;
> +	    for (other = NEXT_INSN (i2); other != i3; other = NEXT_INSN (other))
> +	      if (NONDEBUG_INSN_P (other)
> +		  && (reg_overlap_mentioned_p (reg, PATTERN (other))
> +		      || (CALL_P (other) && find_reg_fusage (other, USE, reg))))
> +		{
> +		  if (dump_file)
> +		    fprintf (dump_file,
> +			     "found extra use of reg %d at insn %d\n", i,
> +			     INSN_UID (other));
> +		  insn_link **plink;
> +		  for (plink = &LOG_LINKS (other);
> +		       *plink;
> +		       plink = &(*plink)->next)
> +		    {
> +		      insn_link *link = *plink;
> +		      if (link->regno == i)
> +			{
> +			  *plink = link->next;
> +			  link->next = i3links;
> +			  i3links = link;
> +			  break;
> +			}
> +		    }
> +		  break;
> +		}
> +	  }

This should be a separate function.

So, no, I'm not okay with this.  It is very expensive, it is doing open
heart surgery on combine's internal structures (in a way that may or may
not work), and all that to combine some insns in a case that should not
exist anyway.


Segher

Re: Combiner fix for PR79910

[Segher Boessenkool]

On Wed, Mar 15, 2017 at 12:09:18AM +0100, Bernd Schmidt wrote:
> I suppose at the moment we don't do 2->2 combinations, so we could 
> conditionalize this on having an i1.

You suppose wrong.  If one of the resulting insns is set_noop_p then
2->2 is allowed, for example.  Also in the hopefully not so far future
we will allow 2->2 in general.


Segher

Re: Combiner fix for PR79910

[Jeff Law]

On 03/17/2017 04:16 PM, Segher Boessenkool wrote:
> On Wed, Mar 15, 2017 at 12:09:18AM +0100, Bernd Schmidt wrote:
>> I suppose at the moment we don't do 2->2 combinations, so we could
>> conditionalize this on having an i1.
>
> You suppose wrong.  If one of the resulting insns is set_noop_p then
> 2->2 is allowed, for example.  Also in the hopefully not so far future
> we will allow 2->2 in general.
But in a 2->2 where one is a nop we're not going to run into problems.

jeff

Re: Combiner fix for PR79910

[Jeff Law]

On 03/17/2017 04:14 PM, Segher Boessenkool wrote:
> Thanks for not cc:ing me on any of this.
There's really no need for getting upset.  Bernd posted the message to 
the patches list.  That's sufficient.

>
> On Wed, Mar 15, 2017 at 04:00:21PM +0100, Bernd Schmidt wrote:
>> +/* Set up a set of registers used in an insn.  Called through note_uses,
>> +   arguments as described for that function.  */
>> +
>> +static void
>> +record_used_regs (rtx *xptr, void *data)
>> +{
>> +  bitmap set = (bitmap)data;
>
> Space after cast, throughout.
A nit.  Bernd, can you please fix this.

>
>> +  int i, j;
>> +  enum rtx_code code;
>> +  const char *fmt;
>> +  rtx x = *xptr;
>> +
>> +  /* repeat is used to turn tail-recursion into iteration since GCC
>> +     can't do it when there's no return value.  */
>> + repeat:
>
> This comment is incorrect.
Depends on the situation.  GCC's ability to turn tail recursion into 
iteration is not good.

>
>> +	  /* If we are about to do the last recursive call
>> +	     needed at this level, change it into iteration.
>> +	     This function is called enough to be worth it.  */
>
> This function is called enough that it should not be called at all.
I disagree.  We have a code gen bug. We need a solution.  Feel free to 
come up with something better.

>
>> +  /* For combinations that may result in two insns, we have to gather
>> +     some extra information about registers used, so that we can
>> +     update all relevant LOG_LINKS later.  */
>
> Please just refuse to do the combination in such cases instead.
?!? That would essentially mean we can't do 3->2 combinations.

>
>> +	/* See comments above where we calculate the bitmap.  */
>> +	EXECUTE_IF_SET_IN_BITMAP ((bitmap)new_regs_in_i2,
>> +				  LAST_VIRTUAL_REGISTER, i, iter)
>
> Why do you need a cast here at all?
>
>> +	  {
>> +	    rtx reg = regno_reg_rtx[i];
>> +	    rtx_insn *other;
>> +	    for (other = NEXT_INSN (i2); other != i3; other = NEXT_INSN (other))
>> +	      if (NONDEBUG_INSN_P (other)
>> +		  && (reg_overlap_mentioned_p (reg, PATTERN (other))
>> +		      || (CALL_P (other) && find_reg_fusage (other, USE, reg))))
>> +		{
>> +		  if (dump_file)
>> +		    fprintf (dump_file,
>> +			     "found extra use of reg %d at insn %d\n", i,
>> +			     INSN_UID (other));
>> +		  insn_link **plink;
>> +		  for (plink = &LOG_LINKS (other);
>> +		       *plink;
>> +		       plink = &(*plink)->next)
>> +		    {
>> +		      insn_link *link = *plink;
>> +		      if (link->regno == i)
>> +			{
>> +			  *plink = link->next;
>> +			  link->next = i3links;
>> +			  i3links = link;
>> +			  break;
>> +			}
>> +		    }
>> +		  break;
>> +		}
>> +	  }
>
> This should be a separate function.
Bernd, can you pull this out into its own function.

>
> So, no, I'm not okay with this.  It is very expensive, it is doing open
> heart surgery on combine's internal structures (in a way that may or may
> not work), and all that to combine some insns in a case that should not
> exist anyway.
Please don't be dramatic.  If you've got a better suggestion for how to 
fix this, be my guest.  I don't like the compile-time cost either, but I 
don't see a better solution.

Jeff

Re: Combiner fix for PR79910

[Segher Boessenkool]

On Fri, Mar 17, 2017 at 04:23:57PM -0600, Jeff Law wrote:
> >>+  /* For combinations that may result in two insns, we have to gather
> >>+     some extra information about registers used, so that we can
> >>+     update all relevant LOG_LINKS later.  */
> >
> >Please just refuse to do the combination in such cases instead.
> ?!? That would essentially mean we can't do 3->2 combinations.

No, only those that would lead to trouble.

> >So, no, I'm not okay with this.  It is very expensive, it is doing open
> >heart surgery on combine's internal structures (in a way that may or may
> >not work), and all that to combine some insns in a case that should not
> >exist anyway.
> Please don't be dramatic.  If you've got a better suggestion for how to 
> fix this, be my guest.  I don't like the compile-time cost either, but I 
> don't see a better solution.

I'll commit the following monday or so:


Subject: [PATCH] combine: Fix 79910

If the dest of an I0 or I1 is used in an insn before I2, as can happen
in various uncommon cases, and we manage to do the combination, the set
is moved to I2, which is wrong.  Don't allow combining the insns in this
case.

This fixes the PR79910 testcase.  I also tested building Linux kernels
for all supported architectures: this fixes a bug for blackfin and
makes no changes on other architectures.

Bootstrapped and regression checked on x86_64-linux and powerpc64-linux
{-m32,-m64}.


Segher


2017-03-18  Segher Boessenkool  <segher@kernel.crashing.org>

	PR rtl-optimization/79910
	* combine.c (can_combine_p): Do not allow combining an I0 or I1
	if its dest is used by an insn before I2 (other than the combined
	insns themselves, which are properly handled already).

---
 gcc/combine.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/gcc/combine.c b/gcc/combine.c
index 3e5c439..24ecedf 100644
--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -1953,6 +1953,10 @@ can_combine_p (rtx_insn *insn, rtx_insn *i3, rtx_insn *pred ATTRIBUTE_UNUSED,
       || (succ2 && FIND_REG_INC_NOTE (succ2, dest))
       /* Don't substitute into a non-local goto, this confuses CFG.  */
       || (JUMP_P (i3) && find_reg_note (i3, REG_NON_LOCAL_GOTO, NULL_RTX))
+      /* Make sure that DEST is not used after INSN but before SUCC, or
+	 between SUCC and SUCC2.  */
+      || (succ && reg_used_between_p (dest, insn, succ))
+      || (succ2 && reg_used_between_p (dest, succ, succ2))
       /* Make sure that DEST is not used after SUCC but before I3.  */
       || (!all_adjacent
 	  && ((succ2
-- 
1.9.3

Re: Combiner fix for PR79910

[Segher Boessenkool]

On Sat, Mar 18, 2017 at 11:23:56AM -0500, Segher Boessenkool wrote:
> Bootstrapped and regression checked on x86_64-linux and powerpc64-linux
> {-m32,-m64}.

Now also tested on aarch64-linux; no new failures.

Segher


> 2017-03-18  Segher Boessenkool  <segher@kernel.crashing.org>
> 
> 	PR rtl-optimization/79910
> 	* combine.c (can_combine_p): Do not allow combining an I0 or I1
> 	if its dest is used by an insn before I2 (other than the combined
> 	insns themselves, which are properly handled already).

Re: Combiner fix for PR79910

[Segher Boessenkool]

On Sat, Mar 18, 2017 at 11:23:56AM -0500, Segher Boessenkool wrote:
> > >So, no, I'm not okay with this.  It is very expensive, it is doing open
> > >heart surgery on combine's internal structures (in a way that may or may
> > >not work), and all that to combine some insns in a case that should not
> > >exist anyway.
> > Please don't be dramatic.  If you've got a better suggestion for how to 
> > fix this, be my guest.  I don't like the compile-time cost either, but I 
> > don't see a better solution.
> 
> I'll commit the following monday or so:

Done now, with the previous patches to combine.c reverted.


Segher