This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Speed up for_each_rtx


I found out that the cause of the speed up in my patch is not the elimination of the indirect call, but the elimination of useless recursive calls for leaves. Indeed this much simpler patch (and suitable for stage3) that I attach still achieves a good speedup:

              FOR_EACH_RTX  this patch
combine.i       0m18.010s    0m17.710s (-1.67%)
fold-const.i    0m38.460s    0m37.880s (-1.51%)
insn-attrtab.i  0m31.320s    0m30.870s (-1.44%)
insn-recog.i    0m49.890s    0m49.520s (-0.75%)
reload.i        0m14.180s    0m13.750s (-3.04%)
reload1.i       0m13.540s    0m12.790s (-5.54%)

bootstrap 123m13.560s 121m31.390s (-1.39%)

(I'll point out once more that a long time in bootstrap is spent in ld -- about 8 minutes).

This is also much safer at this stage. Bootstrapped/regtested powerpc-darwin, ok for mainline?

Paolo
2005-01-20  Paolo Bonzini  <bonzini@gnu.org>

	* rtlanal.c (non_rtx_starting_operands, for_each_rtx_1,
	init_rtlanal): New.
	(for_each_rtx): Call for_each_rtx_1.
	* rtl.h (init_rtlanal): Declare.
	* toplev.c (backend_init): Call init_rtlanal.

Index: rtlanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtlanal.c,v
retrieving revision 1.210
diff -u -r1.210 rtlanal.c
--- rtlanal.c	18 Jan 2005 11:36:19 -0000	1.210
+++ rtlanal.c	20 Jan 2005 12:53:30 -0000
@@ -58,6 +58,10 @@
 static unsigned int num_sign_bit_copies1 (rtx, enum machine_mode, rtx,
                                           enum machine_mode, unsigned int);
 
+/* Offset of the first 'e', 'E' or 'V' operand for each rtx code, or
+   -1 if a code has no such operand.  */
+static int non_rtx_starting_operands[NUM_RTX_CODE];
+
 /* Bit flags that specify the machine subtype we are compiling for.
    Bits are tested using macros TARGET_... defined in the tm.h file
    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
@@ -2624,6 +2628,82 @@
   return 0;
 }
 
+/* Optimized loop of for_each_rtx, which tries to avoid useless recursive
+   calls.  Processes the subexpressions of EXP and passes them to F*/
+static int
+for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
+{
+  int result, i, j;
+  const char *format = GET_RTX_FORMAT (GET_CODE (exp));
+  rtx *x;
+
+  for (; format[n] != '\0'; n++)
+    {
+      switch (format[n])
+	{
+	case 'e':
+	  /* Call F on X.  */
+	  x = &XEXP (exp, n);
+	  result = (*f) (x, data);
+	  if (result == -1)
+	    /* Do not traverse sub-expressions.  */
+	    continue;
+	  else if (result != 0)
+	    /* Stop the traversal.  */
+	    return result;
+	
+	  if (*x == NULL_RTX)
+	    /* There are no sub-expressions.  */
+	    continue;
+	
+	  i = non_rtx_starting_operands[GET_CODE (*x)];
+	  if (i >= 0)
+	    {
+	      result = for_each_rtx_1 (*x, i, f, data);
+	      if (result != 0)
+		return result;
+	    }
+	  break;
+
+	case 'V':
+	case 'E':
+	  if (XVEC (exp, n) == 0)
+	    continue;
+	  for (j = 0; j < XVECLEN (exp, n); ++j)
+	    {
+	      /* Call F on X.  */
+	      x = &XVECEXP (exp, n, j);
+	      result = (*f) (x, data);
+	      if (result == -1)
+		/* Do not traverse sub-expressions.  */
+		continue;
+	      else if (result != 0)
+		/* Stop the traversal.  */
+		return result;
+	
+	      if (*x == NULL_RTX)
+		/* There are no sub-expressions.  */
+		continue;
+	
+	      i = non_rtx_starting_operands[GET_CODE (*x)];
+	      if (i >= 0)
+		{
+		  result = for_each_rtx_1 (*x, i, f, data);
+		  if (result != 0)
+		    return result;
+	        }
+	    }
+	  break;
+
+	default:
+	  /* Nothing to do.  */
+	  break;
+	}
+    }
+
+  return 0;
+}
+
 /* Traverse X via depth-first search, calling F for each
    sub-expression (including X itself).  F is also passed the DATA.
    If F returns -1, do not traverse sub-expressions, but continue
@@ -2641,8 +2721,6 @@
 for_each_rtx (rtx *x, rtx_function f, void *data)
 {
   int result;
-  int length;
-  const char *format;
   int i;
 
   /* Call F on X.  */
@@ -2658,43 +2736,14 @@
     /* There are no sub-expressions.  */
     return 0;
 
-  length = GET_RTX_LENGTH (GET_CODE (*x));
-  format = GET_RTX_FORMAT (GET_CODE (*x));
-
-  for (i = 0; i < length; ++i)
-    {
-      switch (format[i])
-	{
-	case 'e':
-	  result = for_each_rtx (&XEXP (*x, i), f, data);
-	  if (result != 0)
-	    return result;
-	  break;
-
-	case 'V':
-	case 'E':
-	  if (XVEC (*x, i) != 0)
-	    {
-	      int j;
-	      for (j = 0; j < XVECLEN (*x, i); ++j)
-		{
-		  result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
-		  if (result != 0)
-		    return result;
-		}
-	    }
-	  break;
-
-	default:
-	  /* Nothing to do.  */
-	  break;
-	}
-
-    }
+  i = non_rtx_starting_operands[GET_CODE (*x)];
+  if (i < 0)
+    return 0;
 
-  return 0;
+  return for_each_rtx_1 (*x, i, f, data);
 }
 
+
 /* Searches X for any reference to REGNO, returning the rtx of the
    reference found if any.  Otherwise, returns NULL_RTX.  */
 
@@ -4612,3 +4661,15 @@
 				 allow_cc_mode, valid_at_insn_p);
 }
 
+
+void
+init_rtlanal (void)
+{
+  int i;
+  for (i = 0; i < NUM_RTX_CODE; i++)
+    {
+      const char *format = GET_RTX_FORMAT (i);
+      const char *first = strpbrk (format, "eEV");
+      non_rtx_starting_operands[i] = first ? first - format : -1;
+    }
+}
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.939
diff -u -r1.939 toplev.c
--- toplev.c	18 Jan 2005 23:54:43 -0000	1.939
+++ toplev.c	20 Jan 2005 12:53:30 -0000
@@ -1951,6 +1951,7 @@
 #endif
 		    || flag_test_coverage);
 
+  init_rtlanal ();
   init_regs ();
   init_fake_stack_mems ();
   init_alias_once ();
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.532
diff -u -r1.532 rtl.h
--- rtl.h	17 Jan 2005 08:46:15 -0000	1.532
+++ rtl.h	20 Jan 2005 12:53:30 -0000
@@ -967,6 +967,7 @@
    not to use an rtx with this cost under any circumstances.  */
 #define MAX_COST INT_MAX
 
+extern void init_rtlanal (void);
 extern int rtx_cost (rtx, enum rtx_code);
 extern int address_cost (rtx, enum machine_mode);
 extern unsigned int subreg_lsb (rtx);

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]