[PATCH] Speed up gcse.c / improve PR15855 some more
Richard Guenther
rguenther@suse.de
Fri Sep 16 14:05:00 GMT 2005
This removes one quadratic-ness in gcse load/store-motion, namely
traversing a list for searching entries in the load/store table (sigh!).
We happen to have a hashvalue computed for speeding up the compare
while walking the list, so the easy way to fix it is to throw some
memory at it by means of a hashtable.
Pays off with a 10% reduction in compile-time for PR15855 and ldst_entry
now completely off the profile. Compile-time changes for cc1-files
is in the noise, usually I would expect a minor slowdown - but it is
not measurable.
I might further experiment with ditching the linked list completely
and walking the hashtable where necessary, but this may not pay off
as we also remove entries from the list, so the hashtable may be
sparsely populated at walk time. For another time to investigate.
Bootstrapped and regtested on x86_64-unknown-linux for all languages
except ada and treelang.
Ok for mainline?
Thanks,
Richard.
:ADDPATCH rtl:
2005-09-16 Richard Guenther <rguenther@suse.de>
PR middle-end/15855
* gcse.c: Include hashtab.h, define ldst entry hashtable.
(pre_ldst_expr_hash, pre_ldst_expr_eq): New functions.
(ldst_entry): Use the hashtable instead of list-walking.
(find_rtx_in_ldst): Likewise.
(free_ldst_entry): Free the hashtable.
(compute_ld_motion_mems): Create the hashtable.
(trim_ld_motion_mems): Remove entry from hashtable if
removing it from list.
(compute_store_table): Likewise^2.
(store_motion): Free hashtable in case we did not see
any stores.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.348
diff -c -3 -p -r1.348 gcse.c
*** gcse.c 6 Sep 2005 08:15:35 -0000 1.348
--- gcse.c 16 Sep 2005 12:31:30 -0000
*************** Software Foundation, 51 Franklin Street,
*** 170,175 ****
--- 170,176 ----
#include "obstack.h"
#include "timevar.h"
#include "tree-pass.h"
+ #include "hashtab.h"
/* Propagate flow information through back edges and thus enable PRE's
moving loop invariant calculations out of loops.
*************** static rtx *implicit_sets;
*** 471,476 ****
--- 472,480 ----
/* Head of the list of load/store memory refs. */
static struct ls_expr * pre_ldst_mems = NULL;
+ /* Hashtable for the load/store memory refs. */
+ static htab_t pre_ldst_table = NULL;
+
/* Bitmap containing one bit for each register in the program.
Used when performing GCSE to track which registers have been set since
the start of the basic block. */
*************** one_code_hoisting_pass (void)
*** 5015,5020 ****
--- 5019,5039 ----
load towards the exit, and we end up with no loads or stores of 'i'
in the loop. */
+ static hashval_t
+ pre_ldst_expr_hash (const void *p)
+ {
+ int do_not_record_p = 0;
+ const struct ls_expr *x = p;
+ return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
+ }
+
+ static int
+ pre_ldst_expr_eq (const void *p1, const void *p2)
+ {
+ const struct ls_expr *ptr1 = p1, *ptr2 = p2;
+ return expr_equiv_p (ptr1->pattern, ptr2->pattern);
+ }
+
/* This will search the ldst list for a matching expression. If it
doesn't find one, we create one and initialize it. */
*************** ldst_entry (rtx x)
*** 5024,5036 ****
int do_not_record_p = 0;
struct ls_expr * ptr;
unsigned int hash;
hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
NULL, /*have_reg_qty=*/false);
! for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
! if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x))
! return ptr;
ptr = xmalloc (sizeof (struct ls_expr));
--- 5043,5058 ----
int do_not_record_p = 0;
struct ls_expr * ptr;
unsigned int hash;
+ void **slot;
+ struct ls_expr e;
hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
NULL, /*have_reg_qty=*/false);
! e.pattern = x;
! slot = htab_find_slot_with_hash (pre_ldst_table, &e, hash, INSERT);
! if (*slot)
! return (struct ls_expr *)*slot;
ptr = xmalloc (sizeof (struct ls_expr));
*************** ldst_entry (rtx x)
*** 5045,5050 ****
--- 5067,5073 ----
ptr->index = 0;
ptr->hash_index = hash;
pre_ldst_mems = ptr;
+ *slot = ptr;
return ptr;
}
*************** free_ldst_entry (struct ls_expr * ptr)
*** 5065,5070 ****
--- 5088,5096 ----
static void
free_ldst_mems (void)
{
+ htab_delete (pre_ldst_table);
+ pre_ldst_table = NULL;
+
while (pre_ldst_mems)
{
struct ls_expr * tmp = pre_ldst_mems;
*************** print_ldst_list (FILE * file)
*** 5117,5129 ****
static struct ls_expr *
find_rtx_in_ldst (rtx x)
{
! struct ls_expr * ptr;
!
! for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
! if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid)
! return ptr;
!
! return NULL;
}
/* Assign each element of the list of mems a monotonically increasing value. */
--- 5143,5155 ----
static struct ls_expr *
find_rtx_in_ldst (rtx x)
{
! struct ls_expr e;
! void **slot;
! e.pattern = x;
! slot = htab_find_slot (pre_ldst_table, &e, NO_INSERT);
! if (!slot || ((struct ls_expr *)*slot)->invalid)
! return NULL;
! return *slot;
}
/* Assign each element of the list of mems a monotonically increasing value. */
*************** compute_ld_motion_mems (void)
*** 5244,5249 ****
--- 5270,5277 ----
rtx insn;
pre_ldst_mems = NULL;
+ pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
+ pre_ldst_expr_eq, NULL);
FOR_EACH_BB (bb)
{
*************** trim_ld_motion_mems (void)
*** 5334,5339 ****
--- 5362,5368 ----
else
{
*last = ptr->next;
+ htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
free_ldst_entry (ptr);
ptr = * last;
}
*************** compute_store_table (void)
*** 5693,5698 ****
--- 5722,5729 ----
max_gcse_regno);
sbitmap_vector_zero (reg_set_in_block, last_basic_block);
pre_ldst_mems = 0;
+ pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
+ pre_ldst_expr_eq, NULL);
last_set_in = xcalloc (max_gcse_regno, sizeof (int));
already_set = xmalloc (sizeof (int) * max_gcse_regno);
*************** compute_store_table (void)
*** 5780,5785 ****
--- 5811,5817 ----
if (!AVAIL_STORE_LIST (ptr))
{
*prev_next_ptr_ptr = ptr->next;
+ htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
free_ldst_entry (ptr);
}
else
*************** store_motion (void)
*** 6399,6404 ****
--- 6431,6438 ----
num_stores = compute_store_table ();
if (num_stores == 0)
{
+ htab_delete (pre_ldst_table);
+ pre_ldst_table = NULL;
sbitmap_vector_free (reg_set_in_block);
end_alias_analysis ();
return;
More information about the Gcc-patches
mailing list