[PATCH 0/5] Tweak IRA handling of tying and earlyclobbers

[PATCH 0/5] Tweak IRA handling of tying and earlyclobbers

[Richard Sandiford]

This series of patches tweaks the IRA handling of matched constraints
and earlyclobbers.  The main explanations are in the individual patches.

Tested on aarch64-linux-gnu (with and without SVE) and x86_64-linux-gnu.

I also tried building at least one target per CPU directory and
comparing the effect of the patches on the assembly output for
gcc.c-torture, gcc.dg and g++.dg using -O2 -ftree-vectorize.  The table
below summarises the effect on the number of lines of assembly, ignoring
tests for which the number of lines was the same:

Target                 Tests  Delta   Best  Worst Median
======                 =====  =====   ====  ===== ======
alpha-linux-gnu           87   -126    -96    138     -1
arm-linux-gnueabi         38    -37    -10      4     -1
arm-linux-gnueabihf       38    -37    -10      4     -1
avr-elf                   19    -64    -60     14     -1
bfin-elf                 143    -55    -21     21     -1
c6x-elf                   38    -32     -9     16     -1
cris-elf                 253  -1456   -192     24     -1
csky-elf                 101   -221    -36     26     -1
frv-linux-gnu             11    -23     -8     -1     -1
ft32-elf                   1     -2     -2     -2     -2
hppa64-hp-hpux11.23       66    -24    -12     12     -1
i686-apple-darwin         22    -45    -24     11     -1
i686-pc-linux-gnu         18    -65    -96     40     -1
ia64-linux-gnu             1     -4     -4     -4     -4
m68k-linux-gnu            83     31    -70     18      1
mcore-elf                 26   -122    -38     11     -2
mmix                      29   -110    -25      3     -1
mn10300-elf              399    258    -70     70      1
msp430-elf               120   1363    -13    833      2
pdp11                     37    -90    -92     25     -1
powerpc-ibm-aix7.0        31    -25     -4      3     -1
powerpc64-linux-gnu       31    -26     -2      2     -1
powerpc64le-linux-gnu     31    -26     -2      2     -1
pru-elf                    2      8      1      7      1
riscv32-elf                1     -2     -2     -2     -2
riscv64-elf                1     -2     -2     -2     -2
rl78-elf                   6    -20    -18      9     -3
rx-elf                   123     32    -58     30     -1
s390-linux-gnu             7     16     -6      9      1
s390x-linux-gnu            1     -3     -3     -3     -3
sh-linux-gnu             475  -4696   -843     42     -1
spu-elf                  168   -296   -114     25     -2
visium-elf               214   -936   -183     22     -1
x86_64-darwin             30    -25     -4      2     -1
x86_64-linux-gnu          28    -29     -4      1     -1

Of course, the number of lines is only a very rough guide to code size
and code size is only a very rough guide to performance.  It's just
a way of getting a feel for how invasive the change is in pracitce.

As often with this kind of comparison, quite a few changes in either
direction come from things that the RA doesn't consider, such as the
ability to merge code after RA.

The msp430-elf results are especially misleading.  The port has patterns
like:

;; Alternatives 2 and 3 are to handle cases generated by reload.
(define_insn "subqi3"
  [(set (match_operand:QI           0 "nonimmediate_operand" "=rYs,  rm,  &?r, ?&r")
	(minus:QI (match_operand:QI 1 "general_operand"       "0,    0,    !r,  !i")
		  (match_operand:QI 2 "general_operand"      " riYs, rmi, rmi,   r")))]
  ""
  "@
  SUB.B\t%2, %0
  SUB%X0.B\t%2, %0
  MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0
  MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0"
)

The patches make more use of the first two (cheap) alternatives
in preference to the third, but sometimes at the cost of introducing
moves elsewhere.  Each alternative counts one line in this test,
but the third alternative is really two instructions.

(If the port does actually want us to prefer the third alternative
over introducing moves, then I think the constraints need to be
changed.  Using "!" heavily disparages the alternative and so
it's reasonable for the optimisers to try hard to avoid it.
If the alternative is actually the preferred way of handling
untied operands then the "?" on operand 0 should be enough.)

The arm-* improvements come from patterns like:

(define_insn_and_split "*negdi2_insn"
  [(set (match_operand:DI         0 "s_register_operand" "=r,&r")
	(neg:DI (match_operand:DI 1 "s_register_operand"  "0,r")))
   (clobber (reg:CC CC_REGNUM))]
  "TARGET_32BIT"

The patches make IRA assign a saving of one full move to ties between
operands 0 and 1, whereas previously it would only assign a saving
of an eigth of a move.

The other big winners (e.g. cris-*, sh-* and visium-*) have similar cases.

I'll post the SVE patches that rely on and test for this later.

Thanks,
Richard

[PATCH 1/5] Use alternative_mask for add_insn_allocno_copies

[Richard Sandiford]

add_insn_allocno_copies and its subroutines used HARD_REG_SET to
represent a bitmask of alternatives.  There's not really any connection
between the number of registers and the maximum number of alternatives,
so this patch uses alternative_mask instead (which wasn't around when
this code was added).

This is just a minor clean-up making way for later patches.


2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* ira-int.h (ira_setup_alts, ira_get_dup_out_num): Use
	alternative_mask instead of HARD_REG_SET to represent a
	bitmask of alternatives.
	* ira.c (ira_setup_alts, ira_get_dup_out_num): Likewise.
	* ira-conflicts.c (add_insn_allocno_copies): Likewise.

Index: gcc/ira-int.h
===================================================================
--- gcc/ira-int.h	2019-06-21 14:34:05.000000000 +0100
+++ gcc/ira-int.h	2019-06-21 14:34:05.883715050 +0100
@@ -963,8 +963,8 @@ extern void ira_print_disposition (FILE
 extern void ira_debug_disposition (void);
 extern void ira_debug_allocno_classes (void);
 extern void ira_init_register_move_cost (machine_mode);
-extern void ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts);
-extern int ira_get_dup_out_num (int op_num, HARD_REG_SET &alts);
+extern alternative_mask ira_setup_alts (rtx_insn *);
+extern int ira_get_dup_out_num (int, alternative_mask);
 
 /* ira-build.c */
 
Index: gcc/ira.c
===================================================================
--- gcc/ira.c	2019-06-21 14:34:05.000000000 +0100
+++ gcc/ira.c	2019-06-21 14:34:05.887715020 +0100
@@ -1784,9 +1784,12 @@ setup_prohibited_mode_move_regs (void)
 
 \f
 
-/* Setup possible alternatives in ALTS for INSN.  */
-void
-ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
+/* Extract INSN and return the set of alternatives that we should consider.
+   This excludes any alternatives whose constraints are obviously impossible
+   to meet (e.g. because the constraint requires a constant and the operand
+   is nonconstant).  */
+alternative_mask
+ira_setup_alts (rtx_insn *insn)
 {
   /* MAP nalt * nop -> start of constraints for given operand and
      alternative.  */
@@ -1798,7 +1801,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
 
   extract_insn (insn);
   alternative_mask preferred = get_preferred_alternatives (insn);
-  CLEAR_HARD_REG_SET (alts);
+  alternative_mask alts = 0;
   insn_constraints.release ();
   insn_constraints.safe_grow_cleared (recog_data.n_operands
 				      * recog_data.n_alternatives + 1);
@@ -1833,8 +1836,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
 	}
       for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
 	{
-	  if (!TEST_BIT (preferred, nalt)
-	      || TEST_HARD_REG_BIT (alts, nalt))
+	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (alts, nalt))
 	    continue;
 
 	  for (nop = 0; nop < recog_data.n_operands; nop++)
@@ -1906,7 +1908,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
 	      ;
 	    }
 	  if (nop >= recog_data.n_operands)
-	    SET_HARD_REG_BIT (alts, nalt);
+	    alts |= ALTERNATIVE_BIT (nalt);
 	}
       if (commutative < 0)
 	break;
@@ -1916,6 +1918,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
       if (curr_swapped)
 	break;
     }
+  return alts;
 }
 
 /* Return the number of the output non-early clobber operand which
@@ -1923,7 +1926,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
    negative value if there is no such operand).  The function takes
    only really possible alternatives into consideration.  */
 int
-ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
+ira_get_dup_out_num (int op_num, alternative_mask alts)
 {
   int curr_alt, c, original, dup;
   bool ignore_p, use_commut_op_p;
@@ -1940,7 +1943,7 @@ ira_get_dup_out_num (int op_num, HARD_RE
     {
       rtx op = recog_data.operand[op_num];
       
-      for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
+      for (curr_alt = 0, ignore_p = !TEST_BIT (alts, curr_alt),
 	   original = -1;;)
 	{
 	  c = *str;
@@ -1951,7 +1954,7 @@ ira_get_dup_out_num (int op_num, HARD_RE
 	  else if (c == ',')
 	    {
 	      curr_alt++;
-	      ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
+	      ignore_p = !TEST_BIT (alts, curr_alt);
 	    }
 	  else if (! ignore_p)
 	    switch (c)
Index: gcc/ira-conflicts.c
===================================================================
--- gcc/ira-conflicts.c	2019-06-21 14:34:05.000000000 +0100
+++ gcc/ira-conflicts.c	2019-06-21 14:34:05.883715050 +0100
@@ -358,7 +358,7 @@ add_insn_allocno_copies (rtx_insn *insn)
   rtx set, operand, dup;
   bool bound_p[MAX_RECOG_OPERANDS];
   int i, n, freq;
-  HARD_REG_SET alts;
+  alternative_mask alts;
 
   freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
   if (freq == 0)
@@ -379,7 +379,7 @@ add_insn_allocno_copies (rtx_insn *insn)
      there are no dead registers, there will be no such copies.  */
   if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
     return;
-  ira_setup_alts (insn, alts);
+  alts = ira_setup_alts (insn);
   for (i = 0; i < recog_data.n_operands; i++)
     bound_p[i] = false;
   for (i = 0; i < recog_data.n_operands; i++)

[PATCH 2/5] Simplify ira_setup_alts

[Richard Sandiford]

ira_setup_alts has its own code to calculate the start of the
constraint string for each operand/alternative combination,
but preprocess_constraints now provides that information in (almost)
constant time for non-asm instructions.  Using it here should speed
up the common case at the cost of potentially slowing down the handling
of asm statements.

The real reason for doing this is that a later patch wants to use
more of the operand_alternative information.


2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* ira.c (ira_setup_alts): Use preprocess_constraints to get the
	constraint string for each operand/alternative combo.  Only handle
	'%' at the start of constraint strings, and look for it outside
	the main loop.

Index: gcc/ira.c
===================================================================
--- gcc/ira.c	2019-06-21 14:34:05.887715020 +0100
+++ gcc/ira.c	2019-06-21 14:34:09.455685354 +0100
@@ -1791,60 +1791,42 @@ setup_prohibited_mode_move_regs (void)
 alternative_mask
 ira_setup_alts (rtx_insn *insn)
 {
-  /* MAP nalt * nop -> start of constraints for given operand and
-     alternative.  */
-  static vec<const char *> insn_constraints;
   int nop, nalt;
   bool curr_swapped;
   const char *p;
   int commutative = -1;
 
   extract_insn (insn);
+  preprocess_constraints (insn);
   alternative_mask preferred = get_preferred_alternatives (insn);
   alternative_mask alts = 0;
-  insn_constraints.release ();
-  insn_constraints.safe_grow_cleared (recog_data.n_operands
-				      * recog_data.n_alternatives + 1);
   /* Check that the hard reg set is enough for holding all
      alternatives.  It is hard to imagine the situation when the
      assertion is wrong.  */
   ira_assert (recog_data.n_alternatives
 	      <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
 			    FIRST_PSEUDO_REGISTER));
+  for (nop = 0; nop < recog_data.n_operands; nop++)
+    if (recog_data.constraints[nop][0] == '%')
+      {
+	commutative = nop;
+	break;
+      }
   for (curr_swapped = false;; curr_swapped = true)
     {
-      /* Calculate some data common for all alternatives to speed up the
-	 function.  */
-      for (nop = 0; nop < recog_data.n_operands; nop++)
-	{
-	  for (nalt = 0, p = recog_data.constraints[nop];
-	       nalt < recog_data.n_alternatives;
-	       nalt++)
-	    {
-	      insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
-	      while (*p && *p != ',')
-		{
-		  /* We only support one commutative marker, the first
-		     one.  We already set commutative above.  */
-		  if (*p == '%' && commutative < 0)
-		    commutative = nop;
-		  p++;
-		}
-	      if (*p)
-		p++;
-	    }
-	}
       for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
 	{
 	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (alts, nalt))
 	    continue;
 
+	  const operand_alternative *op_alt
+	    = &recog_op_alt[nalt * recog_data.n_operands];
 	  for (nop = 0; nop < recog_data.n_operands; nop++)
 	    {
 	      int c, len;
 
 	      rtx op = recog_data.operand[nop];
-	      p = insn_constraints[nop * recog_data.n_alternatives + nalt];
+	      p = op_alt[nop].constraint;
 	      if (*p == 0 || *p == ',')
 		continue;
 	      

[PATCH 3/5] Make ira_get_dup_out_num handle more cases

[Richard Sandiford]

SVE has a prefix instruction (MOVPRFX) that acts as a move but is
designed to be easily fusible with the following instruction.  The SVE
port therefore has lots of patterns with constraints of the form:

  A: operand 0: =w,?w
     ...
     operand n:  0, w

where the first alternative is a single instruction and the second
alternative uses MOVPRFX.

Ideally we want operand n to be allocated to the same register as
operand 0 in this case.

add_insn_allocno_copies is the main IRA routine that deals with tied
operands.  It is (rightly) very conservative, and only handles cases in
which we're confident about saving a full move.  So for a pattern like:

  B: operand 0: =w,w
     ...
     operand n:  0,w

we don't (and shouldn't) assume that tying operands 0 and n would
save the cost of a move.

But in A, the second alternative has a ? marker, which makes it more
expensive than the first alternative by a full reload.  So I think for
copy elision we should ignore the untied operand n in the second
alternative of A.

One approach would be to add '*' markers to each pattern and make
ira_get_dup_out_num honour them.  But I think the rule applies on
first principles, so marking with '*' shouldn't be necessary.

This patch instead makes ira_get_dup_out_num ignore expensive
alternatives if there are other alternatives that match exactly.
The cheapest way of doing that seemed to be to take expensive
alternatives out of consideration in ira_setup_alts, which provides
a bitmask of alternatives and has all the information available.
add_insn_allocno_copies is the only current user of ira_setup_alts,
so no other code should be affected.

If all available alternatives are disparaged or need a reload,
there's not much we can do to cut them down at this stage,
since it's hard to predict which operands will be reloaded and
which registers will need to be spilled.

An interesting case is patterns like this msp430 one:

;; Alternatives 2 and 3 are to handle cases generated by reload.
(define_insn "subqi3"
  [(set (match_operand:QI           0 "nonimmediate_operand" "=rYs,  rm,  &?r, ?&r")
	(minus:QI (match_operand:QI 1 "general_operand"       "0,    0,    !r,  !i")
		  (match_operand:QI 2 "general_operand"      " riYs, rmi, rmi,   r")))]
  ""
  "@
  SUB.B\t%2, %0
  SUB%X0.B\t%2, %0
  MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0
  MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0"
)

Here alternative 3 is significantly more expensive then alternative 0
(reject costs 0 and 606 respectively).  But if operand 1 is an integer
constant, we'll still use alternative 3 if operand 2 is an allocated
register.  On the other hand, if operand 1 is an integer constant but
operand 2 is spilled to memory, we'll move the constant into a register
and use the first alternative.

So in this case, if operand 1 is a register, we should consider
only the first two alternatives and thus try to tie operand 1
to operand 0 (which we didn't do previously).  If operand 1 is a
constant integer, we should consider at least alternatives 0, 1 and 3.
We could exclude alternative 2, but I don't have any evidence that
that's useful.


2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* ira.c (ira_setup_alts): If any valid alternatives have zero cost,
	exclude any others that are disparaged or that are bound to need
	a reload or spill.
	(ira_get_dup_out_num): Expand comment.

Index: gcc/ira.c
===================================================================
--- gcc/ira.c	2019-06-21 14:34:09.455685354 +0100
+++ gcc/ira.c	2019-06-21 14:34:13.239653892 +0100
@@ -1787,7 +1787,9 @@ setup_prohibited_mode_move_regs (void)
 /* Extract INSN and return the set of alternatives that we should consider.
    This excludes any alternatives whose constraints are obviously impossible
    to meet (e.g. because the constraint requires a constant and the operand
-   is nonconstant).  */
+   is nonconstant).  It also excludes alternatives that are bound to need
+   a spill or reload, as long as we have other alternatives that match
+   exactly.  */
 alternative_mask
 ira_setup_alts (rtx_insn *insn)
 {
@@ -1800,6 +1802,7 @@ ira_setup_alts (rtx_insn *insn)
   preprocess_constraints (insn);
   alternative_mask preferred = get_preferred_alternatives (insn);
   alternative_mask alts = 0;
+  alternative_mask exact_alts = 0;
   /* Check that the hard reg set is enough for holding all
      alternatives.  It is hard to imagine the situation when the
      assertion is wrong.  */
@@ -1816,20 +1819,24 @@ ira_setup_alts (rtx_insn *insn)
     {
       for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
 	{
-	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (alts, nalt))
+	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (exact_alts, nalt))
 	    continue;
 
 	  const operand_alternative *op_alt
 	    = &recog_op_alt[nalt * recog_data.n_operands];
+	  int this_reject = 0;
 	  for (nop = 0; nop < recog_data.n_operands; nop++)
 	    {
 	      int c, len;
 
+	      this_reject += op_alt[nop].reject;
+
 	      rtx op = recog_data.operand[nop];
 	      p = op_alt[nop].constraint;
 	      if (*p == 0 || *p == ',')
 		continue;
-	      
+
+	      bool win_p = false;
 	      do
 		switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
 		  {
@@ -1847,7 +1854,14 @@ ira_setup_alts (rtx_insn *insn)
 
 		  case '0':  case '1':  case '2':  case '3':  case '4':
 		  case '5':  case '6':  case '7':  case '8':  case '9':
-		    goto op_success;
+		    {
+		      rtx other = recog_data.operand[c - '0'];
+		      if (MEM_P (other)
+			  ? rtx_equal_p (other, op)
+			  : REG_P (op) || SUBREG_P (op))
+			goto op_success;
+		      win_p = true;
+		    }
 		    break;
 		    
 		  case 'g':
@@ -1861,7 +1875,11 @@ ira_setup_alts (rtx_insn *insn)
 			{
 			case CT_REGISTER:
 			  if (reg_class_for_constraint (cn) != NO_REGS)
-			    goto op_success;
+			    {
+			      if (REG_P (op) || SUBREG_P (op))
+				goto op_success;
+			      win_p = true;
+			    }
 			  break;
 
 			case CT_CONST_INT:
@@ -1872,9 +1890,14 @@ ira_setup_alts (rtx_insn *insn)
 			  break;
 
 			case CT_ADDRESS:
+			  goto op_success;
+
 			case CT_MEMORY:
 			case CT_SPECIAL_MEMORY:
-			  goto op_success;
+			  if (MEM_P (op))
+			    goto op_success;
+			  win_p = true;
+			  break;
 
 			case CT_FIXED_FORM:
 			  if (constraint_satisfied_p (op, cn))
@@ -1885,12 +1908,22 @@ ira_setup_alts (rtx_insn *insn)
 		    }
 		  }
 	      while (p += len, c);
-	      break;
+	      if (!win_p)
+		break;
+	      /* We can make the alternative match by spilling a register
+		 to memory or loading something into a register.  Count a
+		 cost of one reload (the equivalent of the '?' constraint).  */
+	      this_reject += 6;
 	    op_success:
 	      ;
 	    }
+
 	  if (nop >= recog_data.n_operands)
-	    alts |= ALTERNATIVE_BIT (nalt);
+	    {
+	      alts |= ALTERNATIVE_BIT (nalt);
+	      if (this_reject == 0)
+		exact_alts |= ALTERNATIVE_BIT (nalt);
+	    }
 	}
       if (commutative < 0)
 	break;
@@ -1900,13 +1933,13 @@ ira_setup_alts (rtx_insn *insn)
       if (curr_swapped)
 	break;
     }
-  return alts;
+  return exact_alts ? exact_alts : alts;
 }
 
 /* Return the number of the output non-early clobber operand which
    should be the same in any case as operand with number OP_NUM (or
-   negative value if there is no such operand).  The function takes
-   only really possible alternatives into consideration.  */
+   negative value if there is no such operand).  ALTS is the mask
+   of alternatives that we should consider.  */
 int
 ira_get_dup_out_num (int op_num, alternative_mask alts)
 {

[PATCH 4/5] Allow earlyclobbers in ira_get_dup_out_num

[Richard Sandiford]

ira_get_dup_out_num punted on operands that are matched to
earlyclobber outputs:

	    /* It is better ignore an alternative with early clobber.  */
	    else if (*str == '&')
	      goto fail;

But I'm not sure why this is the right thing to do.  At this stage
we've established that *all* alternatives of interest require the
input to match the output, so

(a) the earlyclobber can only affect other operands and
(b) not tying the registers is bound to introduce a move

The code was part of the initial commit and so isn't obviously
related to a specific testcase.  Also, I can imagine LRA makes
a much better job of this situation than reload did.  (Certainly
SVE uses matched earlyclobbers extensively and I haven't seen any
problems.)

In case this turns out to regress something important: the main
case that matters for SVE is the one in which all alternatives
are earlyclobber.


2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* ira.c (ira_get_dup_out_num): Don't punt for earlyclobbers.
	Use recog_data to test for an output operand.

Index: gcc/ira.c
===================================================================
--- gcc/ira.c	2019-06-21 14:34:13.239653892 +0100
+++ gcc/ira.c	2019-06-21 14:34:15.947631377 +0100
@@ -1999,26 +1999,8 @@ ira_get_dup_out_num (int op_num, alterna
 	}
       if (original == -1)
 	goto fail;
-      dup = -1;
-      for (ignore_p = false, str = recog_data.constraints[original - '0'];
-	   *str != 0;
-	   str++)
-	if (ignore_p)
-	  {
-	    if (*str == ',')
-	      ignore_p = false;
-	  }
-	else if (*str == '#')
-	  ignore_p = true;
-	else if (! ignore_p)
-	  {
-	    if (*str == '=')
-	      dup = original - '0';
-	    /* It is better ignore an alternative with early clobber.  */
-	    else if (*str == '&')
-	      goto fail;
-	  }
-      if (dup >= 0)
+      dup = original - '0';
+      if (recog_data.operand_type[dup] == OP_OUT)
 	return dup;
     fail:
       if (use_commut_op_p)

[PATCH 5/5] Use ira_setup_alts for conflict detection

[Richard Sandiford]

make_early_clobber_and_input_conflicts records allocno conflicts
between inputs and earlyclobber outputs.  It (rightly) avoids
doing this for inputs that are explicitly allowed to match the
output due to matching constraints.

The problem is that whether this matching is allowed varies
between alternatives.  At the moment the code avoids adding
a clobber if *any* enabled alternative allows the match,
even if some other operand makes that alternative impossible.

The specific instance of this for SVE is that some alternatives
allow matched earlyclobbers when a third operand X is constant zero.
We should avoid adding conflicts when X really is constant zero,
but should ignore the match if X is nonzero or nonconstant.

ira_setup_alts can already filter these alternatives out for us,
so all we need to do is use it in process_bb_node_lives.  The
preferred_alternatives variable is only used for this earlyclobber
detection, so no other check should be affected.

With the previous patch to check the reject weight in ira_setup_alts,
this has the effect of ignoring expensive alternatives if we have
other valid alternatives with zero cost.  It seems reasonable to base
the heuristic on only the alternatives that we'd actually like to use,
but if this ends up being too aggressive, we could instead make the new
reject behaviour conditional and only use it for add_insn_allocno_copies.


2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* ira-lives.c (process_bb_node_lives): Use ira_setup_alts.

Index: gcc/ira-lives.c
===================================================================
--- gcc/ira-lives.c	2019-05-29 10:49:39.512701998 +0100
+++ gcc/ira-lives.c	2019-06-21 14:34:19.071605402 +0100
@@ -1236,9 +1236,7 @@ process_bb_node_lives (ira_loop_tree_nod
 		  }
 	      }
 
-	  extract_insn (insn);
-	  preferred_alternatives = get_preferred_alternatives (insn);
-	  preprocess_constraints (insn);
+	  preferred_alternatives = ira_setup_alts (insn);
 	  process_single_reg_class_operands (false, freq);
 
 	  if (call_p)

Re: [PATCH 0/5] Tweak IRA handling of tying and earlyclobbers

[Richard Sandiford]

Richard Sandiford <richard.sandiford@arm.com> writes:
> This series of patches tweaks the IRA handling of matched constraints
> and earlyclobbers.  The main explanations are in the individual patches.
>
> Tested on aarch64-linux-gnu (with and without SVE) and x86_64-linux-gnu.
>
> I also tried building at least one target per CPU directory and
> comparing the effect of the patches on the assembly output for
> gcc.c-torture, gcc.dg and g++.dg using -O2 -ftree-vectorize.  The table
> below summarises the effect on the number of lines of assembly, ignoring
> tests for which the number of lines was the same:

Forgot to say that this list excludes targets for which there were
no changes in assembly length.  (Thought I'd better say that since
the list clearly doesn't have one entry per CPU directory.)

FWIW the full list was:

    aarch64-linux-gnu aarch64_be-linux-gnu alpha-linux-gnu amdgcn-amdhsa
    arc-elf arm-linux-gnueabi arm-linux-gnueabihf avr-elf bfin-elf
    c6x-elf cr16-elf cris-elf csky-elf epiphany-elf fr30-elf
    frv-linux-gnu ft32-elf h8300-elf hppa64-hp-hpux11.23 ia64-linux-gnu
    i686-pc-linux-gnu i686-apple-darwin iq2000-elf lm32-elf m32c-elf
    m32r-elf m68k-linux-gnu mcore-elf microblaze-elf mipsel-linux-gnu
    mipsisa64-linux-gnu mmix mn10300-elf moxie-rtems msp430-elf
    nds32le-elf nios2-linux-gnu nvptx-none or1k-elf pdp11
    powerpc64-linux-gnu powerpc64le-linux-gnu powerpc-ibm-aix7.0 pru-elf
    riscv32-elf riscv64-elf rl78-elf rx-elf s390-linux-gnu
    s390x-linux-gnu sh-linux-gnu sparc-linux-gnu sparc64-linux-gnu
    sparc-wrs-vxworks spu-elf tilegx-elf tilepro-elf xstormy16-elf
    v850-elf vax-netbsdelf visium-elf x86_64-darwin x86_64-linux-gnu
    xtensa-elf

> Target                 Tests  Delta   Best  Worst Median
> ======                 =====  =====   ====  ===== ======
> alpha-linux-gnu           87   -126    -96    138     -1
> arm-linux-gnueabi         38    -37    -10      4     -1
> arm-linux-gnueabihf       38    -37    -10      4     -1
> avr-elf                   19    -64    -60     14     -1
> bfin-elf                 143    -55    -21     21     -1
> c6x-elf                   38    -32     -9     16     -1
> cris-elf                 253  -1456   -192     24     -1
> csky-elf                 101   -221    -36     26     -1
> frv-linux-gnu             11    -23     -8     -1     -1
> ft32-elf                   1     -2     -2     -2     -2
> hppa64-hp-hpux11.23       66    -24    -12     12     -1
> i686-apple-darwin         22    -45    -24     11     -1
> i686-pc-linux-gnu         18    -65    -96     40     -1
> ia64-linux-gnu             1     -4     -4     -4     -4
> m68k-linux-gnu            83     31    -70     18      1
> mcore-elf                 26   -122    -38     11     -2
> mmix                      29   -110    -25      3     -1
> mn10300-elf              399    258    -70     70      1
> msp430-elf               120   1363    -13    833      2
> pdp11                     37    -90    -92     25     -1
> powerpc-ibm-aix7.0        31    -25     -4      3     -1
> powerpc64-linux-gnu       31    -26     -2      2     -1
> powerpc64le-linux-gnu     31    -26     -2      2     -1
> pru-elf                    2      8      1      7      1
> riscv32-elf                1     -2     -2     -2     -2
> riscv64-elf                1     -2     -2     -2     -2
> rl78-elf                   6    -20    -18      9     -3
> rx-elf                   123     32    -58     30     -1
> s390-linux-gnu             7     16     -6      9      1
> s390x-linux-gnu            1     -3     -3     -3     -3
> sh-linux-gnu             475  -4696   -843     42     -1
> spu-elf                  168   -296   -114     25     -2
> visium-elf               214   -936   -183     22     -1
> x86_64-darwin             30    -25     -4      2     -1
> x86_64-linux-gnu          28    -29     -4      1     -1
>
> Of course, the number of lines is only a very rough guide to code size
> and code size is only a very rough guide to performance.  It's just
> a way of getting a feel for how invasive the change is in pracitce.
>
> As often with this kind of comparison, quite a few changes in either
> direction come from things that the RA doesn't consider, such as the
> ability to merge code after RA.
>
> The msp430-elf results are especially misleading.  The port has patterns
> like:
>
> ;; Alternatives 2 and 3 are to handle cases generated by reload.
> (define_insn "subqi3"
>   [(set (match_operand:QI           0 "nonimmediate_operand" "=rYs,  rm,  &?r, ?&r")
> 	(minus:QI (match_operand:QI 1 "general_operand"       "0,    0,    !r,  !i")
> 		  (match_operand:QI 2 "general_operand"      " riYs, rmi, rmi,   r")))]
>   ""
>   "@
>   SUB.B\t%2, %0
>   SUB%X0.B\t%2, %0
>   MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0
>   MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0"
> )
>
> The patches make more use of the first two (cheap) alternatives
> in preference to the third, but sometimes at the cost of introducing
> moves elsewhere.  Each alternative counts one line in this test,
> but the third alternative is really two instructions.
>
> (If the port does actually want us to prefer the third alternative
> over introducing moves, then I think the constraints need to be
> changed.  Using "!" heavily disparages the alternative and so
> it's reasonable for the optimisers to try hard to avoid it.
> If the alternative is actually the preferred way of handling
> untied operands then the "?" on operand 0 should be enough.)
>
> The arm-* improvements come from patterns like:
>
> (define_insn_and_split "*negdi2_insn"
>   [(set (match_operand:DI         0 "s_register_operand" "=r,&r")
> 	(neg:DI (match_operand:DI 1 "s_register_operand"  "0,r")))
>    (clobber (reg:CC CC_REGNUM))]
>   "TARGET_32BIT"
>
> The patches make IRA assign a saving of one full move to ties between
> operands 0 and 1, whereas previously it would only assign a saving
> of an eigth of a move.
>
> The other big winners (e.g. cris-*, sh-* and visium-*) have similar cases.
>
> I'll post the SVE patches that rely on and test for this later.
>
> Thanks,
> Richard

Re: [PATCH 0/5] Tweak IRA handling of tying and earlyclobbers

[Eric Botcazou]

> Forgot to say that this list excludes targets for which there were
> no changes in assembly length.  (Thought I'd better say that since
> the list clearly doesn't have one entry per CPU directory.)
> 
> FWIW the full list was:
> 
>     aarch64-linux-gnu aarch64_be-linux-gnu alpha-linux-gnu amdgcn-amdhsa
>     arc-elf arm-linux-gnueabi arm-linux-gnueabihf avr-elf bfin-elf
>     c6x-elf cr16-elf cris-elf csky-elf epiphany-elf fr30-elf
>     frv-linux-gnu ft32-elf h8300-elf hppa64-hp-hpux11.23 ia64-linux-gnu
>     i686-pc-linux-gnu i686-apple-darwin iq2000-elf lm32-elf m32c-elf
>     m32r-elf m68k-linux-gnu mcore-elf microblaze-elf mipsel-linux-gnu
>     mipsisa64-linux-gnu mmix mn10300-elf moxie-rtems msp430-elf
>     nds32le-elf nios2-linux-gnu nvptx-none or1k-elf pdp11
>     powerpc64-linux-gnu powerpc64le-linux-gnu powerpc-ibm-aix7.0 pru-elf
>     riscv32-elf riscv64-elf rl78-elf rx-elf s390-linux-gnu
>     s390x-linux-gnu sh-linux-gnu sparc-linux-gnu sparc64-linux-gnu
>     sparc-wrs-vxworks spu-elf tilegx-elf tilepro-elf xstormy16-elf
>     v850-elf vax-netbsdelf visium-elf x86_64-darwin x86_64-linux-gnu
>     xtensa-elf

Thanks for the note, I was about to ask what happened for SPARC. :-)

Btw, where does this sparc-wrs-vxworks target come from?  It's quite obsolete 
so should be replaced with sparc-elf at this point.

-- 
Eric Botcazou

Re: [PATCH 0/5] Tweak IRA handling of tying and earlyclobbers

[Richard Sandiford]

Eric Botcazou <ebotcazou@adacore.com> writes:
>> Forgot to say that this list excludes targets for which there were
>> no changes in assembly length.  (Thought I'd better say that since
>> the list clearly doesn't have one entry per CPU directory.)
>> 
>> FWIW the full list was:
>> 
>>     aarch64-linux-gnu aarch64_be-linux-gnu alpha-linux-gnu amdgcn-amdhsa
>>     arc-elf arm-linux-gnueabi arm-linux-gnueabihf avr-elf bfin-elf
>>     c6x-elf cr16-elf cris-elf csky-elf epiphany-elf fr30-elf
>>     frv-linux-gnu ft32-elf h8300-elf hppa64-hp-hpux11.23 ia64-linux-gnu
>>     i686-pc-linux-gnu i686-apple-darwin iq2000-elf lm32-elf m32c-elf
>>     m32r-elf m68k-linux-gnu mcore-elf microblaze-elf mipsel-linux-gnu
>>     mipsisa64-linux-gnu mmix mn10300-elf moxie-rtems msp430-elf
>>     nds32le-elf nios2-linux-gnu nvptx-none or1k-elf pdp11
>>     powerpc64-linux-gnu powerpc64le-linux-gnu powerpc-ibm-aix7.0 pru-elf
>>     riscv32-elf riscv64-elf rl78-elf rx-elf s390-linux-gnu
>>     s390x-linux-gnu sh-linux-gnu sparc-linux-gnu sparc64-linux-gnu
>>     sparc-wrs-vxworks spu-elf tilegx-elf tilepro-elf xstormy16-elf
>>     v850-elf vax-netbsdelf visium-elf x86_64-darwin x86_64-linux-gnu
>>     xtensa-elf
>
> Thanks for the note, I was about to ask what happened for SPARC. :-)

:-)

> Btw, where does this sparc-wrs-vxworks target come from?  It's quite
> obsolete so should be replaced with sparc-elf at this point.

It's based on an old list that also tried to include at least one
target for each supported OS (although it looks like there's no
longer a -vms target, hmm).  I think at the time I was making target
hook changes for which the OS made a difference.

Richard

Re: [PATCH 2/5] Simplify ira_setup_alts

[Vladimir Makarov]

On 2019-06-21 9:40 a.m., Richard Sandiford wrote:
> ira_setup_alts has its own code to calculate the start of the
> constraint string for each operand/alternative combination,
> but preprocess_constraints now provides that information in (almost)
> constant time for non-asm instructions.  Using it here should speed
> up the common case at the cost of potentially slowing down the handling
> of asm statements.

The documentation says that '%' should be the very first constraint 
character.  But I think there is a possibility that somebody can forget 
this and put a blank before '%' and effect of this would be very hard to 
find as still the correct code would be generated although the code 
might be slower.  That was my thoughts why I processed all constraint 
string.

It is hard to for me to say what the probability of this can be. I guess 
it is tiny.  So the patch is ok for me.

> The real reason for doing this is that a later patch wants to use
> more of the operand_alternative information.
>
> 2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
> 	* ira.c (ira_setup_alts): Use preprocess_constraints to get the
> 	constraint string for each operand/alternative combo.  Only handle
> 	'%' at the start of constraint strings, and look for it outside
> 	the main loop.
>
> Index: gcc/ira.c
> ===================================================================
> --- gcc/ira.c	2019-06-21 14:34:05.887715020 +0100
> +++ gcc/ira.c	2019-06-21 14:34:09.455685354 +0100
> @@ -1791,60 +1791,42 @@ setup_prohibited_mode_move_regs (void)
>   alternative_mask
>   ira_setup_alts (rtx_insn *insn)
>   {
> -  /* MAP nalt * nop -> start of constraints for given operand and
> -     alternative.  */
> -  static vec<const char *> insn_constraints;
>     int nop, nalt;
>     bool curr_swapped;
>     const char *p;
>     int commutative = -1;
>   
>     extract_insn (insn);
> +  preprocess_constraints (insn);
>     alternative_mask preferred = get_preferred_alternatives (insn);
>     alternative_mask alts = 0;
> -  insn_constraints.release ();
> -  insn_constraints.safe_grow_cleared (recog_data.n_operands
> -				      * recog_data.n_alternatives + 1);
>     /* Check that the hard reg set is enough for holding all
>        alternatives.  It is hard to imagine the situation when the
>        assertion is wrong.  */
>     ira_assert (recog_data.n_alternatives
>   	      <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
>   			    FIRST_PSEUDO_REGISTER));
> +  for (nop = 0; nop < recog_data.n_operands; nop++)
> +    if (recog_data.constraints[nop][0] == '%')
> +      {
> +	commutative = nop;
> +	break;
> +      }
>     for (curr_swapped = false;; curr_swapped = true)
>       {
> -      /* Calculate some data common for all alternatives to speed up the
> -	 function.  */
> -      for (nop = 0; nop < recog_data.n_operands; nop++)
> -	{
> -	  for (nalt = 0, p = recog_data.constraints[nop];
> -	       nalt < recog_data.n_alternatives;
> -	       nalt++)
> -	    {
> -	      insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
> -	      while (*p && *p != ',')
> -		{
> -		  /* We only support one commutative marker, the first
> -		     one.  We already set commutative above.  */
> -		  if (*p == '%' && commutative < 0)
> -		    commutative = nop;
> -		  p++;
> -		}
> -	      if (*p)
> -		p++;
> -	    }
> -	}
>         for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
>   	{
>   	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (alts, nalt))
>   	    continue;
>   
> +	  const operand_alternative *op_alt
> +	    = &recog_op_alt[nalt * recog_data.n_operands];
>   	  for (nop = 0; nop < recog_data.n_operands; nop++)
>   	    {
>   	      int c, len;
>   
>   	      rtx op = recog_data.operand[nop];
> -	      p = insn_constraints[nop * recog_data.n_alternatives + nalt];
> +	      p = op_alt[nop].constraint;
>   	      if (*p == 0 || *p == ',')
>   		continue;
>   	

Re: [PATCH 3/5] Make ira_get_dup_out_num handle more cases

[Vladimir Makarov]

On 2019-06-21 9:42 a.m., Richard Sandiford wrote:
> SVE has a prefix instruction (MOVPRFX) that acts as a move but is
> designed to be easily fusible with the following instruction.  The SVE
> port therefore has lots of patterns with constraints of the form:
>
>    A: operand 0: =w,?w
>       ...
>       operand n:  0, w
>
> where the first alternative is a single instruction and the second
> alternative uses MOVPRFX.
>
> Ideally we want operand n to be allocated to the same register as
> operand 0 in this case.
>
> add_insn_allocno_copies is the main IRA routine that deals with tied
> operands.  It is (rightly) very conservative, and only handles cases in
> which we're confident about saving a full move.  So for a pattern like:
>
>    B: operand 0: =w,w
>       ...
>       operand n:  0,w
>
> we don't (and shouldn't) assume that tying operands 0 and n would
> save the cost of a move.
>
> But in A, the second alternative has a ? marker, which makes it more
> expensive than the first alternative by a full reload.  So I think for
> copy elision we should ignore the untied operand n in the second
> alternative of A.
>
> One approach would be to add '*' markers to each pattern and make
> ira_get_dup_out_num honour them.  But I think the rule applies on
> first principles, so marking with '*' shouldn't be necessary.
I think direct approach is better.  The modifiers were designed for the 
old algorithms.  Now I think their treatment prevent and will prevent 
significant RA algorithm modifications.  I found that when tried to 
significantly change algorithm for calculation of register class costs 
and register class preferences.
> This patch instead makes ira_get_dup_out_num ignore expensive
> alternatives if there are other alternatives that match exactly.
> The cheapest way of doing that seemed to be to take expensive
> alternatives out of consideration in ira_setup_alts, which provides
> a bitmask of alternatives and has all the information available.
> add_insn_allocno_copies is the only current user of ira_setup_alts,
> so no other code should be affected.
>
>
> 2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
> 	* ira.c (ira_setup_alts): If any valid alternatives have zero cost,
> 	exclude any others that are disparaged or that are bound to need
> 	a reload or spill.
> 	(ira_get_dup_out_num): Expand comment.
The patch is ok for me.
> Index: gcc/ira.c
> ===================================================================
> --- gcc/ira.c	2019-06-21 14:34:09.455685354 +0100
> +++ gcc/ira.c	2019-06-21 14:34:13.239653892 +0100
> @@ -1787,7 +1787,9 @@ setup_prohibited_mode_move_regs (void)
>   /* Extract INSN and return the set of alternatives that we should consider.
>      This excludes any alternatives whose constraints are obviously impossible
>      to meet (e.g. because the constraint requires a constant and the operand
> -   is nonconstant).  */
> +   is nonconstant).  It also excludes alternatives that are bound to need
> +   a spill or reload, as long as we have other alternatives that match
> +   exactly.  */
>   alternative_mask
>   ira_setup_alts (rtx_insn *insn)
>   {
> @@ -1800,6 +1802,7 @@ ira_setup_alts (rtx_insn *insn)
>     preprocess_constraints (insn);
>     alternative_mask preferred = get_preferred_alternatives (insn);
>     alternative_mask alts = 0;
> +  alternative_mask exact_alts = 0;
>     /* Check that the hard reg set is enough for holding all
>        alternatives.  It is hard to imagine the situation when the
>        assertion is wrong.  */
> @@ -1816,20 +1819,24 @@ ira_setup_alts (rtx_insn *insn)
>       {
>         for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
>   	{
> -	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (alts, nalt))
> +	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (exact_alts, nalt))
>   	    continue;
>   
>   	  const operand_alternative *op_alt
>   	    = &recog_op_alt[nalt * recog_data.n_operands];
> +	  int this_reject = 0;
>   	  for (nop = 0; nop < recog_data.n_operands; nop++)
>   	    {
>   	      int c, len;
>   
> +	      this_reject += op_alt[nop].reject;
> +
>   	      rtx op = recog_data.operand[nop];
>   	      p = op_alt[nop].constraint;
>   	      if (*p == 0 || *p == ',')
>   		continue;
> -	
> +
> +	      bool win_p = false;
>   	      do
>   		switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
>   		  {
> @@ -1847,7 +1854,14 @@ ira_setup_alts (rtx_insn *insn)
>   
>   		  case '0':  case '1':  case '2':  case '3':  case '4':
>   		  case '5':  case '6':  case '7':  case '8':  case '9':
> -		    goto op_success;
> +		    {
> +		      rtx other = recog_data.operand[c - '0'];
> +		      if (MEM_P (other)
> +			  ? rtx_equal_p (other, op)
> +			  : REG_P (op) || SUBREG_P (op))
> +			goto op_success;
> +		      win_p = true;
> +		    }
>   		    break;
>   		
>   		  case 'g':
> @@ -1861,7 +1875,11 @@ ira_setup_alts (rtx_insn *insn)
>   			{
>   			case CT_REGISTER:
>   			  if (reg_class_for_constraint (cn) != NO_REGS)
> -			    goto op_success;
> +			    {
> +			      if (REG_P (op) || SUBREG_P (op))
> +				goto op_success;
> +			      win_p = true;
> +			    }
>   			  break;
>   
>   			case CT_CONST_INT:
> @@ -1872,9 +1890,14 @@ ira_setup_alts (rtx_insn *insn)
>   			  break;
>   
>   			case CT_ADDRESS:
> +			  goto op_success;
> +
>   			case CT_MEMORY:
>   			case CT_SPECIAL_MEMORY:
> -			  goto op_success;
> +			  if (MEM_P (op))
> +			    goto op_success;
> +			  win_p = true;
> +			  break;
>   
>   			case CT_FIXED_FORM:
>   			  if (constraint_satisfied_p (op, cn))
> @@ -1885,12 +1908,22 @@ ira_setup_alts (rtx_insn *insn)
>   		    }
>   		  }
>   	      while (p += len, c);
> -	      break;
> +	      if (!win_p)
> +		break;
> +	      /* We can make the alternative match by spilling a register
> +		 to memory or loading something into a register.  Count a
> +		 cost of one reload (the equivalent of the '?' constraint).  */
> +	      this_reject += 6;
>   	    op_success:
>   	      ;
>   	    }
> +
>   	  if (nop >= recog_data.n_operands)
> -	    alts |= ALTERNATIVE_BIT (nalt);
> +	    {
> +	      alts |= ALTERNATIVE_BIT (nalt);
> +	      if (this_reject == 0)
> +		exact_alts |= ALTERNATIVE_BIT (nalt);
> +	    }
>   	}
>         if (commutative < 0)
>   	break;
> @@ -1900,13 +1933,13 @@ ira_setup_alts (rtx_insn *insn)
>         if (curr_swapped)
>   	break;
>       }
> -  return alts;
> +  return exact_alts ? exact_alts : alts;
>   }
>   
>   /* Return the number of the output non-early clobber operand which
>      should be the same in any case as operand with number OP_NUM (or
> -   negative value if there is no such operand).  The function takes
> -   only really possible alternatives into consideration.  */
> +   negative value if there is no such operand).  ALTS is the mask
> +   of alternatives that we should consider.  */
>   int
>   ira_get_dup_out_num (int op_num, alternative_mask alts)
>   {

Re: [PATCH 4/5] Allow earlyclobbers in ira_get_dup_out_num

[Vladimir Makarov]

On 2019-06-21 9:42 a.m., Richard Sandiford wrote:
> ira_get_dup_out_num punted on operands that are matched to
> earlyclobber outputs:
>
> 	    /* It is better ignore an alternative with early clobber.  */
> 	    else if (*str == '&')
> 	      goto fail;
>
> But I'm not sure why this is the right thing to do.  At this stage
> we've established that *all* alternatives of interest require the
> input to match the output, so
>
> (a) the earlyclobber can only affect other operands and
> (b) not tying the registers is bound to introduce a move
>
> The code was part of the initial commit and so isn't obviously
> related to a specific testcase.  Also, I can imagine LRA makes
> a much better job of this situation than reload did.  (Certainly
> SVE uses matched earlyclobbers extensively and I haven't seen any
> problems.)
I don't remember the reason for this either as the code is more 10 years 
old.  I can only speculate that this approach was influenced by the old 
RA (global.c).  I remember that it processed earlyclobber registers too 
but may be in a different way.
> In case this turns out to regress something important: the main
> case that matters for SVE is the one in which all alternatives
> are earlyclobber.
>
OK to commit.
> 2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
> 	* ira.c (ira_get_dup_out_num): Don't punt for earlyclobbers.
> 	Use recog_data to test for an output operand.
>
> Index: gcc/ira.c
> ===================================================================
> --- gcc/ira.c	2019-06-21 14:34:13.239653892 +0100
> +++ gcc/ira.c	2019-06-21 14:34:15.947631377 +0100
> @@ -1999,26 +1999,8 @@ ira_get_dup_out_num (int op_num, alterna
>   	}
>         if (original == -1)
>   	goto fail;
> -      dup = -1;
> -      for (ignore_p = false, str = recog_data.constraints[original - '0'];
> -	   *str != 0;
> -	   str++)
> -	if (ignore_p)
> -	  {
> -	    if (*str == ',')
> -	      ignore_p = false;
> -	  }
> -	else if (*str == '#')
> -	  ignore_p = true;
> -	else if (! ignore_p)
> -	  {
> -	    if (*str == '=')
> -	      dup = original - '0';
> -	    /* It is better ignore an alternative with early clobber.  */
> -	    else if (*str == '&')
> -	      goto fail;
> -	  }
> -      if (dup >= 0)
> +      dup = original - '0';
> +      if (recog_data.operand_type[dup] == OP_OUT)
>   	return dup;
>       fail:
>         if (use_commut_op_p)

Re: [PATCH 5/5] Use ira_setup_alts for conflict detection

[Vladimir Makarov]

On 2019-06-21 9:43 a.m., Richard Sandiford wrote:
> make_early_clobber_and_input_conflicts records allocno conflicts
> between inputs and earlyclobber outputs.  It (rightly) avoids
> doing this for inputs that are explicitly allowed to match the
> output due to matching constraints.
>
> The problem is that whether this matching is allowed varies
> between alternatives.  At the moment the code avoids adding
> a clobber if *any* enabled alternative allows the match,
> even if some other operand makes that alternative impossible.
>
> The specific instance of this for SVE is that some alternatives
> allow matched earlyclobbers when a third operand X is constant zero.
> We should avoid adding conflicts when X really is constant zero,
> but should ignore the match if X is nonzero or nonconstant.
>
> ira_setup_alts can already filter these alternatives out for us,
> so all we need to do is use it in process_bb_node_lives.  The
> preferred_alternatives variable is only used for this earlyclobber
> detection, so no other check should be affected.
>
> With the previous patch to check the reject weight in ira_setup_alts,
> this has the effect of ignoring expensive alternatives if we have
> other valid alternatives with zero cost.  It seems reasonable to base
> the heuristic on only the alternatives that we'd actually like to use,
> but if this ends up being too aggressive, we could instead make the new
> reject behaviour conditional and only use it for add_insn_allocno_copies.
>
This patch definitely improves the heuristics.

The only missed part is a comment for preferred_alternatives

/* The value of get_preferred_alternatives for the current instruction,
    supplemental to recog_data.  */
static alternative_mask preferred_alternatives;

The comment becomes misleading after the patch.

With changing the comment, the patch is ok for me.

Richard, thank you for the patches improving the RA.

> 2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
> 	* ira-lives.c (process_bb_node_lives): Use ira_setup_alts.
>
> Index: gcc/ira-lives.c
> ===================================================================
> --- gcc/ira-lives.c	2019-05-29 10:49:39.512701998 +0100
> +++ gcc/ira-lives.c	2019-06-21 14:34:19.071605402 +0100
> @@ -1236,9 +1236,7 @@ process_bb_node_lives (ira_loop_tree_nod
>   		  }
>   	      }
>   
> -	  extract_insn (insn);
> -	  preferred_alternatives = get_preferred_alternatives (insn);
> -	  preprocess_constraints (insn);
> +	  preferred_alternatives = ira_setup_alts (insn);
>   	  process_single_reg_class_operands (false, freq);
>   
>   	  if (call_p)

Re: [PATCH 1/5] Use alternative_mask for add_insn_allocno_copies

[Richard Sandiford]

Ping.  (And thanks for the reviews of the other patches in the series.)

Richard Sandiford <richard.sandiford@arm.com> writes:
> add_insn_allocno_copies and its subroutines used HARD_REG_SET to
> represent a bitmask of alternatives.  There's not really any connection
> between the number of registers and the maximum number of alternatives,
> so this patch uses alternative_mask instead (which wasn't around when
> this code was added).
>
> This is just a minor clean-up making way for later patches.
>
>
> 2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
> 	* ira-int.h (ira_setup_alts, ira_get_dup_out_num): Use
> 	alternative_mask instead of HARD_REG_SET to represent a
> 	bitmask of alternatives.
> 	* ira.c (ira_setup_alts, ira_get_dup_out_num): Likewise.
> 	* ira-conflicts.c (add_insn_allocno_copies): Likewise.
>
> Index: gcc/ira-int.h
> ===================================================================
> --- gcc/ira-int.h	2019-06-21 14:34:05.000000000 +0100
> +++ gcc/ira-int.h	2019-06-21 14:34:05.883715050 +0100
> @@ -963,8 +963,8 @@ extern void ira_print_disposition (FILE
>  extern void ira_debug_disposition (void);
>  extern void ira_debug_allocno_classes (void);
>  extern void ira_init_register_move_cost (machine_mode);
> -extern void ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts);
> -extern int ira_get_dup_out_num (int op_num, HARD_REG_SET &alts);
> +extern alternative_mask ira_setup_alts (rtx_insn *);
> +extern int ira_get_dup_out_num (int, alternative_mask);
>  
>  /* ira-build.c */
>  
> Index: gcc/ira.c
> ===================================================================
> --- gcc/ira.c	2019-06-21 14:34:05.000000000 +0100
> +++ gcc/ira.c	2019-06-21 14:34:05.887715020 +0100
> @@ -1784,9 +1784,12 @@ setup_prohibited_mode_move_regs (void)
>  
>  \f
>  
> -/* Setup possible alternatives in ALTS for INSN.  */
> -void
> -ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
> +/* Extract INSN and return the set of alternatives that we should consider.
> +   This excludes any alternatives whose constraints are obviously impossible
> +   to meet (e.g. because the constraint requires a constant and the operand
> +   is nonconstant).  */
> +alternative_mask
> +ira_setup_alts (rtx_insn *insn)
>  {
>    /* MAP nalt * nop -> start of constraints for given operand and
>       alternative.  */
> @@ -1798,7 +1801,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
>  
>    extract_insn (insn);
>    alternative_mask preferred = get_preferred_alternatives (insn);
> -  CLEAR_HARD_REG_SET (alts);
> +  alternative_mask alts = 0;
>    insn_constraints.release ();
>    insn_constraints.safe_grow_cleared (recog_data.n_operands
>  				      * recog_data.n_alternatives + 1);
> @@ -1833,8 +1836,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
>  	}
>        for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
>  	{
> -	  if (!TEST_BIT (preferred, nalt)
> -	      || TEST_HARD_REG_BIT (alts, nalt))
> +	  if (!TEST_BIT (preferred, nalt) || TEST_BIT (alts, nalt))
>  	    continue;
>  
>  	  for (nop = 0; nop < recog_data.n_operands; nop++)
> @@ -1906,7 +1908,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
>  	      ;
>  	    }
>  	  if (nop >= recog_data.n_operands)
> -	    SET_HARD_REG_BIT (alts, nalt);
> +	    alts |= ALTERNATIVE_BIT (nalt);
>  	}
>        if (commutative < 0)
>  	break;
> @@ -1916,6 +1918,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
>        if (curr_swapped)
>  	break;
>      }
> +  return alts;
>  }
>  
>  /* Return the number of the output non-early clobber operand which
> @@ -1923,7 +1926,7 @@ ira_setup_alts (rtx_insn *insn, HARD_REG
>     negative value if there is no such operand).  The function takes
>     only really possible alternatives into consideration.  */
>  int
> -ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
> +ira_get_dup_out_num (int op_num, alternative_mask alts)
>  {
>    int curr_alt, c, original, dup;
>    bool ignore_p, use_commut_op_p;
> @@ -1940,7 +1943,7 @@ ira_get_dup_out_num (int op_num, HARD_RE
>      {
>        rtx op = recog_data.operand[op_num];
>        
> -      for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
> +      for (curr_alt = 0, ignore_p = !TEST_BIT (alts, curr_alt),
>  	   original = -1;;)
>  	{
>  	  c = *str;
> @@ -1951,7 +1954,7 @@ ira_get_dup_out_num (int op_num, HARD_RE
>  	  else if (c == ',')
>  	    {
>  	      curr_alt++;
> -	      ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
> +	      ignore_p = !TEST_BIT (alts, curr_alt);
>  	    }
>  	  else if (! ignore_p)
>  	    switch (c)
> Index: gcc/ira-conflicts.c
> ===================================================================
> --- gcc/ira-conflicts.c	2019-06-21 14:34:05.000000000 +0100
> +++ gcc/ira-conflicts.c	2019-06-21 14:34:05.883715050 +0100
> @@ -358,7 +358,7 @@ add_insn_allocno_copies (rtx_insn *insn)
>    rtx set, operand, dup;
>    bool bound_p[MAX_RECOG_OPERANDS];
>    int i, n, freq;
> -  HARD_REG_SET alts;
> +  alternative_mask alts;
>  
>    freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
>    if (freq == 0)
> @@ -379,7 +379,7 @@ add_insn_allocno_copies (rtx_insn *insn)
>       there are no dead registers, there will be no such copies.  */
>    if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
>      return;
> -  ira_setup_alts (insn, alts);
> +  alts = ira_setup_alts (insn);
>    for (i = 0; i < recog_data.n_operands; i++)
>      bound_p[i] = false;
>    for (i = 0; i < recog_data.n_operands; i++)

Re: [PATCH 1/5] Use alternative_mask for add_insn_allocno_copies

[Vladimir Makarov]

On 2019-06-28 7:46 a.m., Richard Sandiford wrote:
> Ping.  (And thanks for the reviews of the other patches in the series.)
Sorry, I missed this patch.  Yes, the patch is OK, Richard.
> Richard Sandiford <richard.sandiford@arm.com> writes:
>> add_insn_allocno_copies and its subroutines used HARD_REG_SET to
>> represent a bitmask of alternatives.  There's not really any connection
>> between the number of registers and the maximum number of alternatives,
>> so this patch uses alternative_mask instead (which wasn't around when
>> this code was added).
>>
>> This is just a minor clean-up making way for later patches.
>>
>>
>> 2019-06-21  Richard Sandiford  <richard.sandiford@arm.com>
>>
>> gcc/
>> 	* ira-int.h (ira_setup_alts, ira_get_dup_out_num): Use
>> 	alternative_mask instead of HARD_REG_SET to represent a
>> 	bitmask of alternatives.
>> 	* ira.c (ira_setup_alts, ira_get_dup_out_num): Likewise.
>> 	* ira-conflicts.c (add_insn_allocno_copies): Likewise.
>>

Re: [PATCH 5/5] Use ira_setup_alts for conflict detection

[Richard Sandiford]

Vladimir Makarov <vmakarov@redhat.com> writes:
> On 2019-06-21 9:43 a.m., Richard Sandiford wrote:
>> make_early_clobber_and_input_conflicts records allocno conflicts
>> between inputs and earlyclobber outputs.  It (rightly) avoids
>> doing this for inputs that are explicitly allowed to match the
>> output due to matching constraints.
>>
>> The problem is that whether this matching is allowed varies
>> between alternatives.  At the moment the code avoids adding
>> a clobber if *any* enabled alternative allows the match,
>> even if some other operand makes that alternative impossible.
>>
>> The specific instance of this for SVE is that some alternatives
>> allow matched earlyclobbers when a third operand X is constant zero.
>> We should avoid adding conflicts when X really is constant zero,
>> but should ignore the match if X is nonzero or nonconstant.
>>
>> ira_setup_alts can already filter these alternatives out for us,
>> so all we need to do is use it in process_bb_node_lives.  The
>> preferred_alternatives variable is only used for this earlyclobber
>> detection, so no other check should be affected.
>>
>> With the previous patch to check the reject weight in ira_setup_alts,
>> this has the effect of ignoring expensive alternatives if we have
>> other valid alternatives with zero cost.  It seems reasonable to base
>> the heuristic on only the alternatives that we'd actually like to use,
>> but if this ends up being too aggressive, we could instead make the new
>> reject behaviour conditional and only use it for add_insn_allocno_copies.
>>
> This patch definitely improves the heuristics.
>
> The only missed part is a comment for preferred_alternatives
>
> /* The value of get_preferred_alternatives for the current instruction,
>     supplemental to recog_data.  */
> static alternative_mask preferred_alternatives;
>
> The comment becomes misleading after the patch.

Oops, thanks for noticing that.

> With changing the comment, the patch is ok for me.

Thanks, here's what I installed after testing on aarch64-linux-gnu
and x86_64-linux-gnu.

Richard


2019-07-01  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* ira-lives.c (process_bb_node_lives): Use ira_setup_alts.

Index: gcc/ira-lives.c
===================================================================
--- gcc/ira-lives.c	2019-06-29 17:20:49.000000000 +0100
+++ gcc/ira-lives.c	2019-07-01 09:33:14.026477923 +0100
@@ -80,8 +80,9 @@ Software Foundation; either version 3, o
 /* The number of last call at which given allocno was saved.  */
 static int *allocno_saved_at_call;
 
-/* The value of get_preferred_alternatives for the current instruction,
-   supplemental to recog_data.  */
+/* The value returned by ira_setup_alts for the current instruction;
+   i.e. the set of alternatives that we should consider to be likely
+   candidates during reloading.  */
 static alternative_mask preferred_alternatives;
 
 /* If non-NULL, the source operand of a register to register copy for which
@@ -1236,9 +1237,7 @@ process_bb_node_lives (ira_loop_tree_nod
 		  }
 	      }
 
-	  extract_insn (insn);
-	  preferred_alternatives = get_preferred_alternatives (insn);
-	  preprocess_constraints (insn);
+	  preferred_alternatives = ira_setup_alts (insn);
 	  process_single_reg_class_operands (false, freq);
 
 	  if (call_p)