[15/25] Don't double-count early-clobber matches.

Message ID 99dbde9ad7afdc6199cfc2f024d8a039028fc208.1536144068.git.ams@codesourcery.com
State New
Headers show
Series
  • AMD GCN Port
Related show

Commit Message

Andrew Stubbs Sept. 5, 2018, 11:51 a.m.
Given a pattern with a number of operands:

(match_operand 0 "" "=&v")
(match_operand 1 "" " v0")
(match_operand 2 "" " v0")
(match_operand 3 "" " v0")

GCC will currently increment "reject" once, for operand 0, and then decrement
it once for each of the other operands, ending with reject == -2 and an
assertion failure.  If there's a conflict then it might try to decrement reject
yet again.

Incidentally, what these patterns are trying to achieve is an allocation in
which operand 0 may match one of the other operands, but may not partially
overlap any of them.  Ideally there'd be a better way to do this.

In any case, it will affect any pattern in which multiple operands may (or
must) match an early-clobber operand.

The patch only allows a reject-- when one has not already occurred, for that
operand.

2018-09-05  Andrew Stubbs  <ams@codesourcery.com>

	gcc/
	* lra-constraints.c (process_alt_operands): Check
	matching_early_clobber before decrementing reject, and set
	matching_early_clobber after.
	* lra-int.h (struct lra_operand_data): Add matching_early_clobber.
	* lra.c (setup_operand_alternative): Initialize matching_early_clobber.
---
 gcc/lra-constraints.c | 22 ++++++++++++++--------
 gcc/lra-int.h         |  3 +++
 gcc/lra.c             |  1 +
 3 files changed, 18 insertions(+), 8 deletions(-)

Comments

Richard Sandiford Sept. 17, 2018, 9:18 a.m. | #1
<ams@codesourcery.com> writes:
> Given a pattern with a number of operands:

>

> (match_operand 0 "" "=&v")

> (match_operand 1 "" " v0")

> (match_operand 2 "" " v0")

> (match_operand 3 "" " v0")

>

> GCC will currently increment "reject" once, for operand 0, and then decrement

> it once for each of the other operands, ending with reject == -2 and an

> assertion failure.  If there's a conflict then it might try to decrement reject

> yet again.

>

> Incidentally, what these patterns are trying to achieve is an allocation in

> which operand 0 may match one of the other operands, but may not partially

> overlap any of them.  Ideally there'd be a better way to do this.

>

> In any case, it will affect any pattern in which multiple operands may (or

> must) match an early-clobber operand.

>

> The patch only allows a reject-- when one has not already occurred, for that

> operand.

>

> 2018-09-05  Andrew Stubbs  <ams@codesourcery.com>

>

> 	gcc/

> 	* lra-constraints.c (process_alt_operands): Check

> 	matching_early_clobber before decrementing reject, and set

> 	matching_early_clobber after.

> 	* lra-int.h (struct lra_operand_data): Add matching_early_clobber.

> 	* lra.c (setup_operand_alternative): Initialize matching_early_clobber.

> ---

>  gcc/lra-constraints.c | 22 ++++++++++++++--------

>  gcc/lra-int.h         |  3 +++

>  gcc/lra.c             |  1 +

>  3 files changed, 18 insertions(+), 8 deletions(-)

>

> diff --git a/gcc/lra-constraints.c b/gcc/lra-constraints.c

> index 8be4d46..55163f1 100644

> --- a/gcc/lra-constraints.c

> +++ b/gcc/lra-constraints.c

> @@ -2202,7 +2202,13 @@ process_alt_operands (int only_alternative)

>  				 "            %d Matching earlyclobber alt:"

>  				 " reject--\n",

>  				 nop);

> -			    reject--;

> +			    if (!curr_static_id->operand[m]

> +						 .matching_early_clobber)

> +			      {

> +				reject--;

> +				curr_static_id->operand[m]

> +						.matching_early_clobber = 1;

> +			      }

>  			  }

>  			/* Otherwise we prefer no matching

>  			   alternatives because it gives more freedom

> @@ -2948,15 +2954,11 @@ process_alt_operands (int only_alternative)

>  	      curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++]

>  		= last_conflict_j;

>  	      losers++;

> -	      /* Early clobber was already reflected in REJECT. */

> -	      lra_assert (reject > 0);

>  	      if (lra_dump_file != NULL)

>  		fprintf

>  		  (lra_dump_file,

>  		   "            %d Conflict early clobber reload: reject--\n",

>  		   i);

> -	      reject--;

> -	      overall += LRA_LOSER_COST_FACTOR - 1;

>  	    }

>  	  else

>  	    {

> @@ -2980,17 +2982,21 @@ process_alt_operands (int only_alternative)

>  		}

>  	      curr_alt_win[i] = curr_alt_match_win[i] = false;

>  	      losers++;

> -	      /* Early clobber was already reflected in REJECT. */

> -	      lra_assert (reject > 0);

>  	      if (lra_dump_file != NULL)

>  		fprintf

>  		  (lra_dump_file,

>  		   "            %d Matched conflict early clobber reloads: "

>  		   "reject--\n",

>  		   i);

> +	    }

> +	  /* Early clobber was already reflected in REJECT. */

> +	  if (!curr_static_id->operand[i].matching_early_clobber)

> +	    {

> +	      lra_assert (reject > 0);

>  	      reject--;

> -	      overall += LRA_LOSER_COST_FACTOR - 1;

> +	      curr_static_id->operand[i].matching_early_clobber = 1;

>  	    }

> +	  overall += LRA_LOSER_COST_FACTOR - 1;

>  	}

>        if (lra_dump_file != NULL)

>  	fprintf (lra_dump_file, "          alt=%d,overall=%d,losers=%d,rld_nregs=%d\n",


The idea looks good to me FWIW, but you can't use curr_static_id for
the state, since that's a static description of the .md pattern rather
than data about this particular instance.

Thanks,
Richard
Andrew Stubbs Sept. 27, 2018, 9:14 p.m. | #2
On 17/09/18 10:18, Richard Sandiford wrote:
> The idea looks good to me FWIW, but you can't use curr_static_id for

> the state, since that's a static description of the .md pattern rather

> than data about this particular instance.


I clearly misunderstood what that was for.

This patch does the same thing, but uses a local variable to store the 
state. That probably means it does it more correctly, too.

OK?

Andrew
Don't double-count early-clobber matches.

Given a pattern with a number of operands:

(match_operand 0 "" "=&v")
(match_operand 1 "" " v0")
(match_operand 2 "" " v0")
(match_operand 3 "" " v0")

GCC will currently increment "reject" once, for operand 0, and then decrement
it once for each of the other operands, ending with reject == -2 and an
assertion failure.  If there's a conflict then it might try to decrement reject
yet again.

Incidentally, what these patterns are trying to achieve is an allocation in
which operand 0 may match one of the other operands, but may not partially
overlap any of them.  Ideally there'd be a better way to do this.

In any case, it will affect any pattern in which multiple operands may (or
must) match an early-clobber operand.

The patch only allows a reject-- when one has not already occurred, for that
operand.

2018-09-27  Andrew Stubbs  <ams@codesourcery.com>

	gcc/
	* lra-constraints.c (process_alt_operands): Check
	matching_early_clobber before decrementing reject, and set
	matching_early_clobber after.
	* lra-int.h (struct lra_operand_data): Add matching_early_clobber.
	* lra.c (setup_operand_alternative): Initialize matching_early_clobber.

diff --git a/gcc/lra-constraints.c b/gcc/lra-constraints.c
index 774d1ff..e1d1688 100644
--- a/gcc/lra-constraints.c
+++ b/gcc/lra-constraints.c
@@ -1969,6 +1969,7 @@ process_alt_operands (int only_alternative)
       if (!TEST_BIT (preferred, nalt))
 	continue;
 
+      bool matching_early_clobber[MAX_RECOG_OPERANDS] = {};
       curr_small_class_check++;
       overall = losers = addr_losers = 0;
       static_reject = reject = reload_nregs = reload_sum = 0;
@@ -2175,7 +2176,11 @@ process_alt_operands (int only_alternative)
 				 "            %d Matching earlyclobber alt:"
 				 " reject--\n",
 				 nop);
-			    reject--;
+			    if (!matching_early_clobber[m])
+			      {
+				reject--;
+				matching_early_clobber[m] = 1;
+			      }
 			  }
 			/* Otherwise we prefer no matching
 			   alternatives because it gives more freedom
@@ -2921,15 +2926,11 @@ process_alt_operands (int only_alternative)
 	      curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++]
 		= last_conflict_j;
 	      losers++;
-	      /* Early clobber was already reflected in REJECT. */
-	      lra_assert (reject > 0);
 	      if (lra_dump_file != NULL)
 		fprintf
 		  (lra_dump_file,
 		   "            %d Conflict early clobber reload: reject--\n",
 		   i);
-	      reject--;
-	      overall += LRA_LOSER_COST_FACTOR - 1;
 	    }
 	  else
 	    {
@@ -2953,17 +2954,21 @@ process_alt_operands (int only_alternative)
 		}
 	      curr_alt_win[i] = curr_alt_match_win[i] = false;
 	      losers++;
-	      /* Early clobber was already reflected in REJECT. */
-	      lra_assert (reject > 0);
 	      if (lra_dump_file != NULL)
 		fprintf
 		  (lra_dump_file,
 		   "            %d Matched conflict early clobber reloads: "
 		   "reject--\n",
 		   i);
+	    }
+	  /* Early clobber was already reflected in REJECT. */
+	  if (!matching_early_clobber[i])
+	    {
+	      lra_assert (reject > 0);
 	      reject--;
-	      overall += LRA_LOSER_COST_FACTOR - 1;
+	      matching_early_clobber[i] = 1;
 	    }
+	  overall += LRA_LOSER_COST_FACTOR - 1;
 	}
       if (lra_dump_file != NULL)
 	fprintf (lra_dump_file, "          alt=%d,overall=%d,losers=%d,rld_nregs=%d\n",
Richard Sandiford Oct. 4, 2018, 8:39 p.m. | #3
Andrew Stubbs <ams@codesourcery.com> writes:
> On 17/09/18 10:18, Richard Sandiford wrote:

>> The idea looks good to me FWIW, but you can't use curr_static_id for

>> the state, since that's a static description of the .md pattern rather

>> than data about this particular instance.

>

> I clearly misunderstood what that was for.

>

> This patch does the same thing, but uses a local variable to store the 

> state. That probably means it does it more correctly, too.

>

> OK?

>

> Andrew

>

> Don't double-count early-clobber matches.

>

> Given a pattern with a number of operands:

>

> (match_operand 0 "" "=&v")

> (match_operand 1 "" " v0")

> (match_operand 2 "" " v0")

> (match_operand 3 "" " v0")

>

> GCC will currently increment "reject" once, for operand 0, and then decrement

> it once for each of the other operands, ending with reject == -2 and an

> assertion failure.  If there's a conflict then it might try to decrement reject

> yet again.

>

> Incidentally, what these patterns are trying to achieve is an allocation in

> which operand 0 may match one of the other operands, but may not partially

> overlap any of them.  Ideally there'd be a better way to do this.

>

> In any case, it will affect any pattern in which multiple operands may (or

> must) match an early-clobber operand.

>

> The patch only allows a reject-- when one has not already occurred, for that

> operand.

>

> 2018-09-27  Andrew Stubbs  <ams@codesourcery.com>

>

> 	gcc/

> 	* lra-constraints.c (process_alt_operands): Check

> 	matching_early_clobber before decrementing reject, and set

> 	matching_early_clobber after.

> 	* lra-int.h (struct lra_operand_data): Add matching_early_clobber.

> 	* lra.c (setup_operand_alternative): Initialize matching_early_clobber.

>

> diff --git a/gcc/lra-constraints.c b/gcc/lra-constraints.c

> index 774d1ff..e1d1688 100644

> --- a/gcc/lra-constraints.c

> +++ b/gcc/lra-constraints.c

> @@ -1969,6 +1969,7 @@ process_alt_operands (int only_alternative)

>        if (!TEST_BIT (preferred, nalt))

>  	continue;

>  

> +      bool matching_early_clobber[MAX_RECOG_OPERANDS] = {};


This is potentially expensive, since MAX_RECOG_OPERANDS >= 30 and
most instructions have operand counts in the low single digits.
(And this is a very compile-time sensitive function -- it often
shows up at the top or near the top of a "cc1 -O0" profile.)

How about clearing it in this loop:

      curr_small_class_check++;
      overall = losers = addr_losers = 0;
      static_reject = reject = reload_nregs = reload_sum = 0;
      for (nop = 0; nop < n_operands; nop++)
	{
	  ...
	}

OK with that change if it works, thanks.

Sorry for the slow reply...

Richard
Andrew Stubbs Oct. 22, 2018, 2:26 p.m. | #4
On 04/10/2018 21:39, Richard Sandiford wrote:
> OK with that change if it works, thanks.


Thanks, here's what I've committed.

Andrew
Don't double-count early-clobber matches.

Given a pattern with a number of operands:

(match_operand 0 "" "=&v")
(match_operand 1 "" " v0")
(match_operand 2 "" " v0")
(match_operand 3 "" " v0")

GCC will currently increment "reject" once, for operand 0, and then decrement
it once for each of the other operands, ending with reject == -2 and an
assertion failure.  If there's a conflict then it might try to decrement reject
yet again.

Incidentally, what these patterns are trying to achieve is an allocation in
which operand 0 may match one of the other operands, but may not partially
overlap any of them.  Ideally there'd be a better way to do this.

In any case, it will affect any pattern in which multiple operands may (or
must) match an early-clobber operand.

The patch only allows a reject-- when one has not already occurred, for that
operand.

2018-10-22  Andrew Stubbs  <ams@codesourcery.com>

	gcc/
	* lra-constraints.c (process_alt_operands): New local array,
	matching_early_clobber.  Check matching_early_clobber before
	decrementing reject, and set matching_early_clobber after.

diff --git a/gcc/lra-constraints.c b/gcc/lra-constraints.c
index 774d1ff..3b355a8 100644
--- a/gcc/lra-constraints.c
+++ b/gcc/lra-constraints.c
@@ -1969,6 +1969,7 @@ process_alt_operands (int only_alternative)
       if (!TEST_BIT (preferred, nalt))
 	continue;
 
+      bool matching_early_clobber[MAX_RECOG_OPERANDS];
       curr_small_class_check++;
       overall = losers = addr_losers = 0;
       static_reject = reject = reload_nregs = reload_sum = 0;
@@ -1980,6 +1981,7 @@ process_alt_operands (int only_alternative)
 	    fprintf (lra_dump_file,
 		     "            Staticly defined alt reject+=%d\n", inc);
 	  static_reject += inc;
+	  matching_early_clobber[nop] = 0;
 	}
       reject += static_reject;
       early_clobbered_regs_num = 0;
@@ -2175,7 +2177,11 @@ process_alt_operands (int only_alternative)
 				 "            %d Matching earlyclobber alt:"
 				 " reject--\n",
 				 nop);
-			    reject--;
+			    if (!matching_early_clobber[m])
+			      {
+				reject--;
+				matching_early_clobber[m] = 1;
+			      }
 			  }
 			/* Otherwise we prefer no matching
 			   alternatives because it gives more freedom
@@ -2921,15 +2927,11 @@ process_alt_operands (int only_alternative)
 	      curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++]
 		= last_conflict_j;
 	      losers++;
-	      /* Early clobber was already reflected in REJECT. */
-	      lra_assert (reject > 0);
 	      if (lra_dump_file != NULL)
 		fprintf
 		  (lra_dump_file,
 		   "            %d Conflict early clobber reload: reject--\n",
 		   i);
-	      reject--;
-	      overall += LRA_LOSER_COST_FACTOR - 1;
 	    }
 	  else
 	    {
@@ -2953,17 +2955,21 @@ process_alt_operands (int only_alternative)
 		}
 	      curr_alt_win[i] = curr_alt_match_win[i] = false;
 	      losers++;
-	      /* Early clobber was already reflected in REJECT. */
-	      lra_assert (reject > 0);
 	      if (lra_dump_file != NULL)
 		fprintf
 		  (lra_dump_file,
 		   "            %d Matched conflict early clobber reloads: "
 		   "reject--\n",
 		   i);
+	    }
+	  /* Early clobber was already reflected in REJECT. */
+	  if (!matching_early_clobber[i])
+	    {
+	      lra_assert (reject > 0);
 	      reject--;
-	      overall += LRA_LOSER_COST_FACTOR - 1;
+	      matching_early_clobber[i] = 1;
 	    }
+	  overall += LRA_LOSER_COST_FACTOR - 1;
 	}
       if (lra_dump_file != NULL)
 	fprintf (lra_dump_file, "          alt=%d,overall=%d,losers=%d,rld_nregs=%d\n",

Patch

diff --git a/gcc/lra-constraints.c b/gcc/lra-constraints.c
index 8be4d46..55163f1 100644
--- a/gcc/lra-constraints.c
+++ b/gcc/lra-constraints.c
@@ -2202,7 +2202,13 @@  process_alt_operands (int only_alternative)
 				 "            %d Matching earlyclobber alt:"
 				 " reject--\n",
 				 nop);
-			    reject--;
+			    if (!curr_static_id->operand[m]
+						 .matching_early_clobber)
+			      {
+				reject--;
+				curr_static_id->operand[m]
+						.matching_early_clobber = 1;
+			      }
 			  }
 			/* Otherwise we prefer no matching
 			   alternatives because it gives more freedom
@@ -2948,15 +2954,11 @@  process_alt_operands (int only_alternative)
 	      curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++]
 		= last_conflict_j;
 	      losers++;
-	      /* Early clobber was already reflected in REJECT. */
-	      lra_assert (reject > 0);
 	      if (lra_dump_file != NULL)
 		fprintf
 		  (lra_dump_file,
 		   "            %d Conflict early clobber reload: reject--\n",
 		   i);
-	      reject--;
-	      overall += LRA_LOSER_COST_FACTOR - 1;
 	    }
 	  else
 	    {
@@ -2980,17 +2982,21 @@  process_alt_operands (int only_alternative)
 		}
 	      curr_alt_win[i] = curr_alt_match_win[i] = false;
 	      losers++;
-	      /* Early clobber was already reflected in REJECT. */
-	      lra_assert (reject > 0);
 	      if (lra_dump_file != NULL)
 		fprintf
 		  (lra_dump_file,
 		   "            %d Matched conflict early clobber reloads: "
 		   "reject--\n",
 		   i);
+	    }
+	  /* Early clobber was already reflected in REJECT. */
+	  if (!curr_static_id->operand[i].matching_early_clobber)
+	    {
+	      lra_assert (reject > 0);
 	      reject--;
-	      overall += LRA_LOSER_COST_FACTOR - 1;
+	      curr_static_id->operand[i].matching_early_clobber = 1;
 	    }
+	  overall += LRA_LOSER_COST_FACTOR - 1;
 	}
       if (lra_dump_file != NULL)
 	fprintf (lra_dump_file, "          alt=%d,overall=%d,losers=%d,rld_nregs=%d\n",
diff --git a/gcc/lra-int.h b/gcc/lra-int.h
index 5267b53..f193e1f 100644
--- a/gcc/lra-int.h
+++ b/gcc/lra-int.h
@@ -147,6 +147,9 @@  struct lra_operand_data
      This field is set up every time when corresponding
      operand_alternative in lra_static_insn_data is set up.  */
   unsigned int early_clobber : 1;
+  /* True if there is an early clobber that has a matching alternative.
+     This field is used to prevent multiple matches being counted.  */
+  unsigned int matching_early_clobber : 1;
   /* True if the operand is an address.  */
   unsigned int is_address : 1;
 };
diff --git a/gcc/lra.c b/gcc/lra.c
index aa768fb..01dd8b8 100644
--- a/gcc/lra.c
+++ b/gcc/lra.c
@@ -797,6 +797,7 @@  setup_operand_alternative (lra_insn_recog_data_t data,
     {
       static_data->operand[i].early_clobber_alts = 0;
       static_data->operand[i].early_clobber = false;
+      static_data->operand[i].matching_early_clobber = false;
       static_data->operand[i].is_address = false;
       if (static_data->operand[i].constraint[0] == '%')
 	{