This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Cselib speedup
- From: Jan Hubicka <jh at suse dot cz>
- To: Jan Hubicka <jh at suse dot cz>
- Cc: gcc-patches at gcc dot gnu dot org, rth at redhat dot com
- Date: Tue, 11 Mar 2003 20:11:24 +0100
- Subject: Re: Cselib speedup
- References: <20030311185617.GH29606@kam.mff.cuni.cz>
> 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. */