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: Cselib speedup


> Hi,
> this patch cuts insn-recog.c -O3 compilation time from 98 seconds to 72.  We
> spend huge amount of time in htab_traverse called via cselib_invalidate_mem.
> This patch implements special purpose list for maintaining the values
> that may be stored in the memory references and thus has to be checked.
> 
> Now reload_cse regs takes about the same time as CSE2, so something is still
> wrong here, not quite sure what.
> For insn-recog next showstopper is GCSE.
> 
> Bootstrapped/regtested i386.  OK for mainline/3.3 branch?
> Honza
> 
> Tue Mar 11 19:51:12 CET 2003  Jan Hubicka  <jh at suse dot cz>
> 	* cselib.c (cselib_invalidate_mem_1): Move too ...
> 	(cselib_invalidate_mem): ... here; use new list
> 	(dummy_val, first_containing_mem): New static variables.
> 	(clear_table): Initialize first_containing_mem.
> 	(discard_useless_values):  Compact the containing_mem list.
> 	(add_mem_for_addr): Add to the list.
> 	* cselib.h (cselib_val): Add next_containing_mem.
Hmm, while looking at the code, I forget to clear the next_containig_mem
that may cause cselib to miss some of them.  I am testing updated patch.
Still has same performance effect.

OK assuming it passes?

Index: cselib.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cselib.c,v
retrieving revision 1.24
diff -c -3 -p -r1.24 cselib.c
*** cselib.c	7 Jan 2003 22:14:42 -0000	1.24
--- cselib.c	11 Mar 2003 19:08:28 -0000
*************** static cselib_val *cselib_lookup_mem	PAR
*** 63,69 ****
  static void cselib_invalidate_regno	PARAMS ((unsigned int,
  						 enum machine_mode));
  static int cselib_mem_conflict_p	PARAMS ((rtx, rtx));
- static int cselib_invalidate_mem_1	PARAMS ((void **, void *));
  static void cselib_invalidate_mem	PARAMS ((rtx));
  static void cselib_invalidate_rtx	PARAMS ((rtx, rtx, void *));
  static void cselib_record_set		PARAMS ((rtx, cselib_val *,
--- 63,68 ----
*************** static GTY((deletable (""))) struct elt_
*** 128,133 ****
--- 127,141 ----
  /* Set by discard_useless_locs if it deleted the last location of any
     value.  */
  static int values_became_useless;
+ 
+ /* Used as stop element of the containing_mem list so we can check
+    presence in the list by checking the next pointer.  */
+ static cselib_val dummy_val;
+ 
+ /* Used to list all values that contain memory reference. 
+    May or may not contain the useless values - the list is compacted
+    each time memory is invalidated.  */
+ static cselib_val *first_containing_mem = &dummy_val;
  
  
  /* Allocate a struct elt_list and fill in its two elements with the
*************** clear_table (clear_all)
*** 237,242 ****
--- 245,252 ----
    n_useless_values = 0;
  
    next_unknown_value = 0;
+ 
+   first_containing_mem = &dummy_val;
  }
  
  /* The equality test for our hash table.  The first argument ENTRY is a table
*************** discard_useless_values (x, info)
*** 371,376 ****
--- 381,387 ----
  static void
  remove_useless_values ()
  {
+   cselib_val **p, *v;
    /* First pass: eliminate locations that reference the value.  That in
       turn can make more values useless.  */
    do
*************** remove_useless_values ()
*** 383,388 ****
--- 394,408 ----
    /* Second pass: actually remove the values.  */
    htab_traverse (hash_table, discard_useless_values, 0);
  
+   p = &first_containing_mem;
+   for (v = *p; v != &dummy_val; v = v->next_containing_mem)
+     if (v->locs)
+       {
+ 	*p = v;
+ 	p = &(*p)->next_containing_mem;
+       }
+   *p = &dummy_val;
+ 
    if (n_useless_values != 0)
      abort ();
  }
*************** new_cselib_val (value, mode)
*** 706,711 ****
--- 726,732 ----
    CSELIB_VAL_PTR (e->u.val_rtx) = e;
    e->addr_list = 0;
    e->locs = 0;
+   e->next_containing_mem = 0;
    return e;
  }
  
*************** add_mem_for_addr (addr_elt, mem_elt, x)
*** 730,735 ****
--- 751,761 ----
    mem_elt->locs
      = new_elt_loc_list (mem_elt->locs,
  			replace_equiv_address_nv (x, addr_elt->u.val_rtx));
+   if (mem_elt->next_containing_mem == NULL)
+     {
+       mem_elt->next_containing_mem = first_containing_mem;
+       first_containing_mem = mem_elt;
+     }
  }
  
  /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
*************** cselib_mem_conflict_p (mem_base, val)
*** 1078,1145 ****
    return 0;
  }
  
! /* For the value found in SLOT, walk its locations to determine if any overlap
!    INFO (which is a MEM rtx).  */
  
! static int
! cselib_invalidate_mem_1 (slot, info)
!      void **slot;
!      void *info;
  {
!   cselib_val *v = (cselib_val *) *slot;
!   rtx mem_rtx = (rtx) info;
!   struct elt_loc_list **p = &v->locs;
!   int had_locs = v->locs != 0;
  
!   while (*p)
      {
!       rtx x = (*p)->loc;
!       cselib_val *addr;
!       struct elt_list **mem_chain;
! 
!       /* MEMs may occur in locations only at the top level; below
! 	 that every MEM or REG is substituted by its VALUE.  */
!       if (GET_CODE (x) != MEM
! 	  || ! cselib_mem_conflict_p (mem_rtx, x))
! 	{
! 	  p = &(*p)->next;
! 	  continue;
! 	}
  
!       /* This one overlaps.  */
!       /* We must have a mapping from this MEM's address to the
! 	 value (E).  Remove that, too.  */
!       addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
!       mem_chain = &addr->addr_list;
!       for (;;)
  	{
! 	  if ((*mem_chain)->elt == v)
  	    {
! 	      unchain_one_elt_list (mem_chain);
! 	      break;
  	    }
  
! 	  mem_chain = &(*mem_chain)->next;
! 	}
! 
!       unchain_one_elt_loc_list (p);
!     }
  
!   if (had_locs && v->locs == 0)
!     n_useless_values++;
  
!   return 1;
! }
  
! /* Invalidate any locations in the table which are changed because of a
!    store to MEM_RTX.  If this is called because of a non-const call
!    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
  
! static void
! cselib_invalidate_mem (mem_rtx)
!      rtx mem_rtx;
! {
!   htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
  }
  
  /* Invalidate DEST, which is being assigned to or clobbered.  The second and
--- 1104,1178 ----
    return 0;
  }
  
! /* Invalidate any locations in the table which are changed because of a
!    store to MEM_RTX.  If this is called because of a non-const call
!    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
  
! static void
! cselib_invalidate_mem (mem_rtx)
!      rtx mem_rtx;
  {
!   cselib_val **vp, *v, *next;
  
!   vp = &first_containing_mem;
!   for (v = *vp; v != &dummy_val; v = next)
      {
!       bool has_mem = false;
!       struct elt_loc_list **p = &v->locs;
!       int had_locs = v->locs != 0;
  
!       while (*p)
  	{
! 	  rtx x = (*p)->loc;
! 	  cselib_val *addr;
! 	  struct elt_list **mem_chain;
! 
! 	  /* MEMs may occur in locations only at the top level; below
! 	     that every MEM or REG is substituted by its VALUE.  */
! 	  if (GET_CODE (x) != MEM)
  	    {
! 	      p = &(*p)->next;
! 	      continue;
! 	    }
! 	  if (! cselib_mem_conflict_p (mem_rtx, x))
! 	    {
! 	      has_mem = true;
! 	      p = &(*p)->next;
! 	      continue;
  	    }
  
! 	  /* This one overlaps.  */
! 	  /* We must have a mapping from this MEM's address to the
! 	     value (E).  Remove that, too.  */
! 	  addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
! 	  mem_chain = &addr->addr_list;
! 	  for (;;)
! 	    {
! 	      if ((*mem_chain)->elt == v)
! 		{
! 		  unchain_one_elt_list (mem_chain);
! 		  break;
! 		}
  
! 	      mem_chain = &(*mem_chain)->next;
! 	    }
  
! 	  unchain_one_elt_loc_list (p);
! 	}
  
!       if (had_locs && v->locs == 0)
! 	n_useless_values++;
  
!       next = v->next_containing_mem;
!       if (has_mem)
! 	{
! 	  *vp = v;
! 	  vp = &(*vp)->next_containing_mem;
! 	}
!       else
! 	v->next_containing_mem = NULL;
!     }
!   *vp = &dummy_val;
  }
  
  /* Invalidate DEST, which is being assigned to or clobbered.  The second and
Index: cselib.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cselib.h,v
retrieving revision 1.6
diff -c -3 -p -r1.6 cselib.h
*** cselib.h	7 Jan 2003 22:14:42 -0000	1.6
--- cselib.h	11 Mar 2003 19:08:28 -0000
*************** typedef struct cselib_val_struct GTY(())
*** 38,43 ****
--- 38,45 ----
    /* If this value is used as an address, points to a list of values that
       use it as an address in a MEM.  */
    struct elt_list *addr_list;
+ 
+   struct cselib_val_struct *next_containing_mem;
  } cselib_val;
  
  /* A list of rtl expressions that hold the same value.  */


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