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]

Re: Speedup CSE by 5%


The part that I feel less confortable with is allocating the stack with alloca, but overall it is nice. I attach the patch for cse.c as a proof of concept.

Paolo

Yuck, no patch here!


Paolo
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	18 Jan 2005 10:35:00 -0000
@@ -2181,6 +2173,145 @@
 /* In modulo-sched.c.  */
 extern void sms_schedule (FILE *);
 
+/* 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
+   traversing the rest of the tree.  Upon an iteration, SUB_RTX points
+   to an rtx in the tree; rtx_iter_skip can be called to avoid visiting
+   the subexpressions of SUB_RTX.  */
+
+/* Always ensure two free items in the list, which are needed for rtvecs.  */
+#define FOR_EACH_RTX(X, SUB_RTX, ITER) \
+  for ((SUB_RTX) = rtx_iter_init (&(ITER), (X)); \
+       (SUB_RTX); \
+       ((ITER).free == NULL \
+	? (void) ((ITER).free = alloca (sizeof (rtx_stack_entry)), \
+	    (ITER).free->next = NULL) : (void) 0), \
+       ((ITER).free->next == NULL \
+	? (void) ((ITER).free->next = alloca (sizeof (rtx_stack_entry)), \
+	    (ITER).free->next->next = NULL) : (void) 0), \
+        (SUB_RTX) = rtx_iter_next (&(ITER)))
+
+union rtx_stack_item {
+  rtx   *x;
+  rtvec  vec;
+};
+
+typedef struct rtx_stack_entry {
+  struct rtx_stack_entry *next;
+  union rtx_stack_item    fld;
+  int			  n;
+  const char		 *format;
+} rtx_stack_entry;
+
+typedef struct {
+  rtx_stack_entry	 *stack, *free;
+  rtx             *next;
+} rtx_iter;
+
+static inline rtx *
+rtx_iter_init (rtx_iter *iter, rtx *x)
+{
+  iter->stack = NULL;
+  iter->free = NULL;
+  iter->next = x;
+  return x;
+}
+
+static void
+rtx_iter_push_vec (rtx_iter *iter, rtvec vec)
+{
+  struct rtx_stack_entry *cur;
+  iter->next = &RTVEC_ELT (vec, 0);
+
+  cur = iter->free;
+  iter->free = cur->next;
+
+  cur->n = 1;
+  cur->fld.vec = vec;
+  cur->format = NULL;
+  cur->next = iter->stack;
+  iter->stack = cur;
+}
+
+static inline rtx *
+rtx_iter_next (rtx_iter *iter)
+{
+  struct rtx_stack_entry *cur;
+  const char *format, *recursion_point;
+
+  if (iter->next && *iter->next)
+    {
+      format = GET_RTX_FORMAT (GET_CODE (*iter->next));
+      recursion_point = strpbrk (format, "eEV");
+
+      /* Optimize leaves (like PC, or REGs).  */
+      if (recursion_point != NULL)
+        {
+	  /* We have to push an entry on the stack.  */
+	  cur = iter->free;
+	  cur->n = recursion_point - format;
+	  cur->fld.x = iter->next;
+	  cur->format = format;
+
+	  iter->free = cur->next;
+	  cur->next = iter->stack;
+	  iter->stack = cur;
+	}
+    }
+
+  /* rtx_iter_skip may cause the entry condition to be false!  */
+  while ((cur = iter->stack) != NULL)
+    {
+      const char *format = cur->format;
+      if (format)
+        {
+	  /* Looking in an rtx */
+	  char c;
+	  rtx x = *cur->fld.x;
+          for (; (c = format[cur->n]) != '\0'; cur->n++)
+            if (c == 'e')
+	      {
+	        iter->next = &XEXP (x, cur->n);
+		cur->n++;
+	        return iter->next;
+	      }
+	    else if ((c == 'E' || c == 'V') && XVECLEN (x, cur->n) > 0)
+	      {
+		rtx_iter_push_vec (iter, XVEC (x, cur->n));
+		cur->n++;
+	        return iter->next;
+	      }
+	}
+      else
+        {
+	  /* Looking in an rtvec */
+	  rtvec vec = cur->fld.vec;
+          if (cur->n < GET_NUM_ELEM (vec))
+	    {
+	      iter->next = &RTVEC_ELT (vec, cur->n);
+	      cur->n++;
+	      return iter->next;
+	    }
+	}
+
+      /* Pop an entry off the stack */
+      iter->stack = cur->next;
+      cur->next = iter->free;
+      iter->free = cur;
+    }
+
+  return NULL;
+}
+
+/* Avoid that *X's subexpressions are visited.  There is no way to stop
+   visiting the elements of a vector.  */
+static inline void
+rtx_iter_skip (rtx_iter *iter)
+{
+  iter->next = NULL;
+}
+
 struct rtl_hooks
 {
   rtx (*gen_lowpart) (enum machine_mode, rtx);
Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.329
diff -u -r1.329 cse.c
--- cse.c	5 Jan 2005 23:19:17 -0000	1.329
+++ cse.c	18 Jan 2005 10:35:02 -0000
@@ -262,14 +262,6 @@
 /* The table of all qtys, indexed by qty number.  */
 static struct qty_table_elem *qty_table;
 
-/* Structure used to pass arguments via for_each_rtx to function
-   cse_change_cc_mode.  */
-struct change_cc_mode_args
-{
-  rtx insn;
-  rtx newreg;
-};
-
 #ifdef HAVE_cc0
 /* For machines that have a CC0, we do not record its value in the hash
    table since its use is guaranteed to be the insn immediately following
@@ -600,7 +592,6 @@
 
 static bool fixed_base_plus_p (rtx x);
 static int notreg_cost (rtx, enum rtx_code);
-static int approx_reg_cost_1 (rtx *, void *);
 static int approx_reg_cost (rtx);
 static int preferable (int, int, int, int);
 static void new_basic_block (void);
@@ -650,16 +641,16 @@
 static void invalidate_skipped_block (rtx);
 static rtx cse_basic_block (rtx, rtx, struct branch_path *);
 static void count_reg_usage (rtx, int *, int);
-static int check_for_label_ref (rtx *, void *);
+static bool check_for_label_ref (rtx);
 extern void dump_class (struct table_elt*);
 static struct cse_reg_info * get_cse_reg_info (unsigned int);
-static int check_dependence (rtx *, void *);
+static bool check_dependence (rtx, rtx, enum machine_mode, rtx);
 
 static void flush_hash_table (void);
 static bool insn_live_p (rtx, int *);
 static bool set_live_p (rtx, rtx, int *);
 static bool dead_libcall_p (rtx, int *);
-static int cse_change_cc_mode (rtx *, void *);
+static void cse_change_cc_mode (rtx *, rtx, rtx);
 static void cse_change_cc_mode_insn (rtx, rtx);
 static void cse_change_cc_mode_insns (rtx, rtx, rtx);
 static enum machine_mode cse_cc_succs (basic_block, rtx, rtx, bool);
@@ -717,34 +708,6 @@
     }
 }
 
-/* Subroutine of approx_reg_cost; called through for_each_rtx.  */
-
-static int
-approx_reg_cost_1 (rtx *xp, void *data)
-{
-  rtx x = *xp;
-  int *cost_p = data;
-
-  if (x && REG_P (x))
-    {
-      unsigned int regno = REGNO (x);
-
-      if (! CHEAP_REGNO (regno))
-	{
-	  if (regno < FIRST_PSEUDO_REGISTER)
-	    {
-	      if (SMALL_REGISTER_CLASSES)
-		return 1;
-	      *cost_p += 2;
-	    }
-	  else
-	    *cost_p += 1;
-	}
-    }
-
-  return 0;
-}
-
 /* Return an estimate of the cost of the registers used in an rtx.
    This is mostly the number of different REG expressions in the rtx;
    however for some exceptions like fixed registers we use a cost of
@@ -754,9 +717,26 @@
 approx_reg_cost (rtx x)
 {
   int cost = 0;
+  rtx_iter iter;
+  rtx *loc;
 
-  if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))
-    return MAX_COST;
+  FOR_EACH_RTX (&x, loc, iter)
+    if (*loc && REG_P (*loc))
+      {
+        unsigned int regno = REGNO (*loc);
+
+        if (! CHEAP_REGNO (regno))
+	  {
+	    if (regno < FIRST_PSEUDO_REGISTER)
+	      {
+	        if (SMALL_REGISTER_CLASSES)
+		  return MAX_COST;
+	        cost += 2;
+	      }
+	    else
+	      cost += 1;
+	  }
+      }
 
   return cost;
 }
@@ -1715,24 +1695,19 @@
 	  remove_from_table (p, i);
       }
 }
-
 /* Function called for each rtx to check whether true dependence exist.  */
-struct check_dependence_data
-{
-  enum machine_mode mode;
-  rtx exp;
-  rtx addr;
-};
 
-static int
-check_dependence (rtx *x, void *data)
+static bool
+check_dependence (rtx x, rtx exp, enum machine_mode mode, rtx addr)
 {
-  struct check_dependence_data *d = (struct check_dependence_data *) data;
-  if (*x && MEM_P (*x))
-    return canon_true_dependence (d->exp, d->mode, d->addr, *x,
-		    		  cse_rtx_varies_p);
-  else
-    return 0;
+  rtx_iter iter;
+  rtx *loc;
+  FOR_EACH_RTX (&x, loc, iter)
+    if (*loc && MEM_P (*loc)
+        && canon_true_dependence (exp, mode, addr, *loc, cse_rtx_varies_p))
+      return true;
+
+  return false;
 }
 
 /* Remove from the hash table, or mark as invalid, all expressions whose
@@ -1862,18 +1837,13 @@
 	      next = p->next_same_hash;
 	      if (p->in_memory)
 		{
-		  struct check_dependence_data d;
-
 		  /* Just canonicalize the expression once;
 		     otherwise each time we call invalidate
 		     true_dependence will canonicalize the
 		     expression again.  */
 		  if (!p->canon_exp)
 		    p->canon_exp = canon_rtx (p->exp);
-		  d.exp = x;
-		  d.addr = addr;
-		  d.mode = full_mode;
-		  if (for_each_rtx (&p->canon_exp, check_dependence, &d))
+		  if (check_dependence (p->canon_exp, x, full_mode, addr))
 		    remove_from_table (p, i);
 		}
 	    }
@@ -6944,8 +6914,7 @@
 	  /* If we haven't already found an insn where we added a LABEL_REF,
 	     check this one.  */
 	  if (NONJUMP_INSN_P (insn) && ! recorded_label_ref
-	      && for_each_rtx (&PATTERN (insn), check_for_label_ref,
-			       (void *) insn))
+	      && check_for_label_ref (insn))
 	    recorded_label_ref = 1;
 	}
 
@@ -7042,23 +7011,28 @@
   return to ? NEXT_INSN (to) : 0;
 }
 
-/* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
-   there isn't a REG_LABEL note.  Return one if so.  DATA is the insn.  */
+/* Called to see if INSN is using a LABEL_REF for which there isn't a REG_LABEL
+   note.  Return true if so.  */
 
-static int
-check_for_label_ref (rtx *rtl, void *data)
+static bool
+check_for_label_ref (rtx insn)
 {
-  rtx insn = (rtx) data;
+  rtx_iter iter;
+  rtx *rtl;
 
   /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
      we must rerun jump since it needs to place the note.  If this is a
      LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
      since no REG_LABEL will be added.  */
-  return (GET_CODE (*rtl) == LABEL_REF
-	  && ! LABEL_REF_NONLOCAL_P (*rtl)
-	  && LABEL_P (XEXP (*rtl, 0))
-	  && INSN_UID (XEXP (*rtl, 0)) != 0
-	  && ! find_reg_note (insn, REG_LABEL, XEXP (*rtl, 0)));
+  FOR_EACH_RTX (&PATTERN (insn), rtl, iter)
+    if (GET_CODE (*rtl) == LABEL_REF
+	&& ! LABEL_REF_NONLOCAL_P (*rtl)
+	&& LABEL_P (XEXP (*rtl, 0))
+	&& INSN_UID (XEXP (*rtl, 0)) != 0
+	&& ! find_reg_note (insn, REG_LABEL, XEXP (*rtl, 0)))
+      return true;
+
+  return false;
 }
 
 /* Count the number of times registers are used (not set) in X.
@@ -7367,26 +7341,24 @@
   return ndead;
 }
 
-/* This function is called via for_each_rtx.  The argument, NEWREG, is
-   a condition code register with the desired mode.  If we are looking
-   at the same register in a different mode, replace it with
-   NEWREG.  */
+/* The argument, NEWREG, is a condition code register with the desired mode.
+   Wherever INSN refers to the same register in a different mode, replace it
+   with NEWREG.  */
 
-static int
-cse_change_cc_mode (rtx *loc, void *data)
+static void
+cse_change_cc_mode (rtx *x, rtx insn, rtx newreg)
 {
-  struct change_cc_mode_args* args = (struct change_cc_mode_args*)data;
-
-  if (*loc
-      && REG_P (*loc)
-      && REGNO (*loc) == REGNO (args->newreg)
-      && GET_MODE (*loc) != GET_MODE (args->newreg))
-    {
-      validate_change (args->insn, loc, args->newreg, 1);
-      
-      return -1;
-    }
-  return 0;
+  rtx_iter iter;
+  rtx *loc;
+  unsigned regno = REGNO (newreg);
+  enum machine_mode mode = GET_MODE (newreg);
+
+  FOR_EACH_RTX (x, loc, iter)
+    if (*loc
+        && REG_P (*loc)
+        && REGNO (*loc) == regno
+        && GET_MODE (*loc) != mode)
+      validate_change (insn, loc, newreg, 1);
 }
 
 /* Change the mode of any reference to the register REGNO (NEWREG) to
@@ -7395,17 +7367,13 @@
 static void
 cse_change_cc_mode_insn (rtx insn, rtx newreg)
 {
-  struct change_cc_mode_args args;
   int success;
 
   if (!INSN_P (insn))
     return;
 
-  args.insn = insn;
-  args.newreg = newreg;
-  
-  for_each_rtx (&PATTERN (insn), cse_change_cc_mode, &args);
-  for_each_rtx (&REG_NOTES (insn), cse_change_cc_mode, &args);
+  cse_change_cc_mode (&PATTERN (insn), insn, newreg);
+  cse_change_cc_mode (&REG_NOTES (insn), insn, newreg);
   
   /* If the following assertion was triggered, there is most probably
      something wrong with the cc_modes_compatible back end function.

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