[PATCH] Speedup CONSTRAINT_LEN

[PATCH] Speedup CONSTRAINT_LEN

[Richard Guenther]

This speeds up CONSTRAINT_LEN which is on top of the profiles of a
-O0 tramp3d compile by recognizing that at the moment we do two function
calls just to figure out that if the first constraint letter is 'Y' the
length is two and else one (for i686).  So instead of

#define CONSTRAINT_LEN(c_,s_) insn_constraint_len (lookup_constraint (s_))

we now emit an inline

static inline size_t
insn_constraint_len_s (char fc, const char *str ATTRIBUTE_UNUSED)
{
  switch (fc)
    {
    case 'Y':
        return 2;
      break;
    default: break;
    }
  return 1;
}

#define CONSTRAINT_LEN(c_,s_) insn_constraint_len_s (c_,s_)

into tm-preds.h.  With this patch genpreds.c recognizes same-length
subcodes (we only have such at the moment, only s390 has two of them).

This results in 2.5% to 3.5% speedup for a -O0 tramp3d compile.

Bootstrap and regtest in progress, I plan to commit this tomorrow if
that succeeded and there are no objections.

Thanks,
Richard.

2007-04-01  Richard Guenther  <rguenther@suse.de>

	PR target/31420
	* genpreds.c (write_insn_constraint_len_s): New function to
	optimize CONSTRAINT_LEN.
	(write_tm_preds_h): Use it.
	(write_insn_preds_c): Call it.

Index: genpreds.c
===================================================================
*** genpreds.c	(revision 123399)
--- genpreds.c	(working copy)
*************** write_lookup_constraint (void)
*** 1001,1006 ****
--- 1001,1059 ----
  	"}\n");
  }
  
+ /* Write out a function which looks at a string and determines what
+    the constraint name length is.  */
+ static void
+ write_insn_constraint_len_s (void)
+ {
+   unsigned int i;
+   puts ("static inline size_t\n"
+ 	"insn_constraint_len_s (char fc, const char *str ATTRIBUTE_UNUSED)\n"
+ 	"{\n"
+ 	"  switch (fc)\n"
+ 	"    {");
+ 
+   for (i = 0; i < ARRAY_SIZE(constraints_by_letter_table); i++)
+     {
+       struct constraint_data *c = constraints_by_letter_table[i], *c2;
+       int len;
+ 
+       if (!c
+       	  || c->namelen == 1)
+ 	continue;
+ 
+       printf ("    case '%c':\n", i);
+ 
+       /* Special case same-length subcodes.  */
+       len = c->namelen;
+       c2 = c->next_this_letter;
+       while (c2)
+ 	{
+ 	  if (c2->namelen != (unsigned)len)
+ 	    len = -1;
+ 	  c2 = c2->next_this_letter;
+ 	}
+       if (len != -1)
+         printf ("        return %lu;\n", (unsigned long int) len);
+       else
+ 	do
+ 	  {
+ 	    printf ("      if (!strncmp (str, \"%s\", %lu))\n"
+ 		    "        return %lu;\n",
+ 		    c->name, (unsigned long int) c->namelen,
+ 		    (unsigned long int) c->namelen);
+ 	    c = c->next_this_letter;
+ 	  }
+ 	while (c);
+       puts ("      break;");
+     }
+ 
+   puts ("    default: break;\n"
+ 	"    }\n"
+ 	"  return 1;\n"
+ 	"}\n");
+ }
+ 
  /* Write out the function which computes constraint name lengths from
     their enumerators. */
  static void
*************** write_tm_preds_h (void)
*** 1248,1256 ****
  	    "extern bool constraint_satisfied_p (rtx, enum constraint_num);\n");
  
        if (constraint_max_namelen > 1)
! 	puts ("extern size_t insn_constraint_len (enum constraint_num);\n"
! 	      "#define CONSTRAINT_LEN(c_,s_) "
! 	      "insn_constraint_len (lookup_constraint (s_))\n");
        else
  	puts ("#define CONSTRAINT_LEN(c_,s_) 1\n");
        if (have_register_constraints)
--- 1301,1312 ----
  	    "extern bool constraint_satisfied_p (rtx, enum constraint_num);\n");
  
        if (constraint_max_namelen > 1)
!         {
! 	  puts ("extern size_t insn_constraint_len (enum constraint_num);\n");
! 	  write_insn_constraint_len_s ();
! 	  puts ("#define CONSTRAINT_LEN(c_,s_) "
! 		"insn_constraint_len_s (c_,s_)\n");
! 	}
        else
  	puts ("#define CONSTRAINT_LEN(c_,s_) 1\n");
        if (have_register_constraints)

Re: [PATCH] Speedup CONSTRAINT_LEN

[Richard Guenther]

On Sun, 1 Apr 2007, Richard Guenther wrote:

> into tm-preds.h.  With this patch genpreds.c recognizes same-length
> subcodes (we only have such at the moment, only s390 has two of them).

Actually s390 is worse, we generate

static inline size_t
insn_constraint_len_s (char fc, const char *str ATTRIBUTE_UNUSED)
{
  switch (fc)
    {
    case 'A':
        return 2;
      break;
    case 'B':
        return 2;
      break;
    case 'N':
        return 5;
      break;
    case 'O':
        return 2;
      break;
    default: break;
    }
  return 1;
}

I guess exchanging 'O' and 'C' names and 'N' and 'D' would generate 
somewhat better code.  Or even merging 'A', 'B' and 'O'.  Still the
above should be not too bad.

Richard.

[PATCH] Speedup CONSTRAINT_LEN (updated), constrain allowed constraints

[Richard Guenther]

On Sun, 1 Apr 2007, Richard Guenther wrote:

> into tm-preds.h.  With this patch genpreds.c recognizes same-length
> subcodes (we only have such at the moment, only s390 has two of them).

We can actually do better, by forcing this as a rule.  Also this was
the only use of insn_constraint_len, so I just changed its prototype.

That's no longer non-algorithmic, so, ok for mainline?

Thanks,
Richard.

2007-04-01  Richard Guenther  <rguenther@suse.de>

	* genpreds.c (write_insn_constraint_len): Write function
	optimized for CONSTRAINT_LEN implementation.
	(write_tm_preds_h): Output insn_constraint_len inline and
	use it for CONSTRAINT_LEN.
	(write_insn_preds_c): Don't output insn_constraint_len.
	* doc/md.texi (define_register_constraint): Document multi-letter
	constraints shall have the same length if they start with the same
	letter.

Index: doc/md.texi
===================================================================
*** doc/md.texi	(revision 123399)
--- doc/md.texi	(working copy)
*************** definitions.
*** 3063,3069 ****
  @deffn {MD Expression} define_register_constraint name regclass docstring
  All three arguments are string constants.
  @var{name} is the name of the constraint, as it will appear in
! @code{match_operand} expressions.  @var{regclass} can be either the
  name of the corresponding register class (@pxref{Register Classes}),
  or a C expression which evaluates to the appropriate register class.
  If it is an expression, it must have no side effects, and it cannot
--- 3063,3071 ----
  @deffn {MD Expression} define_register_constraint name regclass docstring
  All three arguments are string constants.
  @var{name} is the name of the constraint, as it will appear in
! @code{match_operand} expressions.  If @var{name} is a multi-letter
! constraint its length shall be the same for all constraints starting
! with the same letter.  @var{regclass} can be either the
  name of the corresponding register class (@pxref{Register Classes}),
  or a C expression which evaluates to the appropriate register class.
  If it is an expression, it must have no side effects, and it cannot
Index: genpreds.c
===================================================================
*** genpreds.c	(revision 123399)
--- genpreds.c	(working copy)
*************** write_lookup_constraint (void)
*** 1001,1026 ****
  	"}\n");
  }
  
! /* Write out the function which computes constraint name lengths from
!    their enumerators. */
  static void
  write_insn_constraint_len (void)
  {
!   struct constraint_data *c;
! 
!   if (constraint_max_namelen == 1)
!     return;
  
!   puts ("size_t\n"
! 	"insn_constraint_len (enum constraint_num c)\n"
  	"{\n"
! 	"  switch (c)\n"
  	"    {");
  
!   FOR_ALL_CONSTRAINTS (c)
!     if (c->namelen > 1)
!       printf ("    case CONSTRAINT_%s: return %lu;\n", c->c_name,
! 	      (unsigned long int) c->namelen);
  
    puts ("    default: break;\n"
  	"    }\n"
--- 1001,1044 ----
  	"}\n");
  }
  
! /* Write out a function which looks at a string and determines what
!    the constraint name length is.  */
  static void
  write_insn_constraint_len (void)
  {
!   unsigned int i;
  
!   puts ("static inline size_t\n"
! 	"insn_constraint_len (char fc, const char *str ATTRIBUTE_UNUSED)\n"
  	"{\n"
! 	"  switch (fc)\n"
  	"    {");
  
!   for (i = 0; i < ARRAY_SIZE(constraints_by_letter_table); i++)
!     {
!       struct constraint_data *c = constraints_by_letter_table[i];
! 
!       if (!c
!       	  || c->namelen == 1)
! 	continue;
! 
!       /* Constraints with multiple characters should have the same
! 	 length.  */
!       {
! 	struct constraint_data *c2 = c->next_this_letter;
! 	size_t len = c->namelen;
! 	while (c2)
! 	  {
! 	    if (c2->namelen != len)
! 	      error ("Multi-letter constraints with first letter '%c' "
! 		     "should have same length", i);
! 	    c2 = c2->next_this_letter;
! 	  }
!       }
! 
!       printf ("    case '%c': return %lu;\n",
! 	      i, (unsigned long int) c->namelen);
!     }
  
    puts ("    default: break;\n"
  	"    }\n"
*************** write_tm_preds_h (void)
*** 1248,1256 ****
  	    "extern bool constraint_satisfied_p (rtx, enum constraint_num);\n");
  
        if (constraint_max_namelen > 1)
! 	puts ("extern size_t insn_constraint_len (enum constraint_num);\n"
! 	      "#define CONSTRAINT_LEN(c_,s_) "
! 	      "insn_constraint_len (lookup_constraint (s_))\n");
        else
  	puts ("#define CONSTRAINT_LEN(c_,s_) 1\n");
        if (have_register_constraints)
--- 1266,1276 ----
  	    "extern bool constraint_satisfied_p (rtx, enum constraint_num);\n");
  
        if (constraint_max_namelen > 1)
!         {
! 	  write_insn_constraint_len ();
! 	  puts ("#define CONSTRAINT_LEN(c_,s_) "
! 		"insn_constraint_len (c_,s_)\n");
! 	}
        else
  	puts ("#define CONSTRAINT_LEN(c_,s_) 1\n");
        if (have_register_constraints)
*************** write_insn_preds_c (void)
*** 1341,1349 ****
  	write_regclass_for_constraint ();
        write_constraint_satisfied_p ();
        
-       if (constraint_max_namelen > 1)
- 	write_insn_constraint_len ();
- 
        if (have_const_int_constraints)
  	write_insn_const_int_ok_for_constraint ();
  
--- 1361,1366 ----

Re: [PATCH] Speedup CONSTRAINT_LEN

[Andrew Pinski]

On 4/1/07, Richard Guenther <rguenther@suse.de> wrote:
> On Sun, 1 Apr 2007, Richard Guenther wrote:
>
> > into tm-preds.h.  With this patch genpreds.c recognizes same-length
> > subcodes (we only have such at the moment, only s390 has two of them).
>
> Actually s390 is worse, we generate
> I guess exchanging 'O' and 'C' names and 'N' and 'D' would generate
> somewhat better code.  Or even merging 'A', 'B' and 'O'.  Still the
> above should be not too bad.

The tree optimizers should be able to combine those parts of the
switch statement.

-- Pinski

Re: [PATCH] Speedup CONSTRAINT_LEN (updated), constrain allowed constraints

[Richard Henderson]

On Sun, Apr 01, 2007 at 08:37:00PM +0200, Richard Guenther wrote:
> 	* genpreds.c (write_insn_constraint_len): Write function
> 	optimized for CONSTRAINT_LEN implementation.
> 	(write_tm_preds_h): Output insn_constraint_len inline and
> 	use it for CONSTRAINT_LEN.
> 	(write_insn_preds_c): Don't output insn_constraint_len.
> 	* doc/md.texi (define_register_constraint): Document multi-letter
> 	constraints shall have the same length if they start with the same
> 	letter.

Ok.


r~

Re: [PATCH] Speedup CONSTRAINT_LEN (updated), constrain allowed constraints

[Richard Guenther]

On Mon, 2 Apr 2007, Richard Henderson wrote:

> On Sun, Apr 01, 2007 at 08:37:00PM +0200, Richard Guenther wrote:
> > 	* genpreds.c (write_insn_constraint_len): Write function
> > 	optimized for CONSTRAINT_LEN implementation.
> > 	(write_tm_preds_h): Output insn_constraint_len inline and
> > 	use it for CONSTRAINT_LEN.
> > 	(write_insn_preds_c): Don't output insn_constraint_len.
> > 	* doc/md.texi (define_register_constraint): Document multi-letter
> > 	constraints shall have the same length if they start with the same
> > 	letter.
> 
> Ok.

Looks like it made a noticable difference for optimized compile as well ;)

Sadly, no more low-hanging fruit for tramp3d left :(
Still, r123451, r123381, r123329, r123303 and r123259 account for 20% 
compile-time for a -O2 -funroll-loops -ffast-math compile of tramp3d.

Richard.