This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Use htabs for the scev database
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org, sebastian dot pop at cri dot ensmp dot fr
- Date: Wed, 21 Apr 2004 15:48:46 +0200
- Subject: [lno] Use htabs for the scev database
Hello,
this patch makes a hashtable to be used for scev database (since the
list stored there may get really long and slow to traverse).
Zdenek
* tree-flow.h (linear_transform_loops): Prototype changed.
* tree-vectorizer.h (vectorize_loops): Ditto.
* tree-loop-linear.c (linear_transform_loops): Remove unused
argument.
* tree-vectorizer.c (vectorize_loops): Ditto.
* tree-scalar-evolution.c (scalar_evolution_info): Type changed
to hash table.
(new_scev_info_str): Use xmalloc instead of ggc_alloc.
(hash_scev_info, eq_scev_info, del_scev_info,
gather_stats_on_scev_database_1): New functions.
(find_var_scev_info, dump_chrecs_stats, gather_stats_on_scev_database,
scev_initialize, scev_finalize): Work with hash table instead of a
list.
(scev_elim_checks, scev_vectorize): Do not pass unused arguments to
functions.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.23
diff -c -3 -p -r1.1.4.177.2.23 tree-flow.h
*** tree-flow.h 15 Apr 2004 01:09:48 -0000 1.1.4.177.2.23
--- tree-flow.h 21 Apr 2004 13:15:40 -0000
*************** struct loop *tree_ssa_loop_version (stru
*** 621,627 ****
basic_block *);
void update_lv_condition (basic_block *, tree);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
! void linear_transform_loops (struct loops *, varray_type);
void loop_commit_inserts (void);
void tree_ssa_unswitch_loops (struct loops *loops);
unsigned estimate_loop_size (struct loop *loop);
--- 621,627 ----
basic_block *);
void update_lv_condition (basic_block *, tree);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
! void linear_transform_loops (struct loops *);
void loop_commit_inserts (void);
void tree_ssa_unswitch_loops (struct loops *loops);
unsigned estimate_loop_size (struct loop *loop);
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 tree-loop-linear.c
*** tree-loop-linear.c 21 Mar 2004 03:20:20 -0000 1.1.2.2
--- tree-loop-linear.c 21 Apr 2004 13:15:40 -0000
*************** Software Foundation, 59 Temple Place - S
*** 63,70 ****
/* Perform a set of linear transforms on LOOPS. */
void
! linear_transform_loops (struct loops *loops,
! varray_type ev_info ATTRIBUTE_UNUSED)
{
unsigned int i;
for (i = 1; i < loops->num; i++)
--- 63,69 ----
/* Perform a set of linear transforms on LOOPS. */
void
! linear_transform_loops (struct loops *loops)
{
unsigned int i;
for (i = 1; i < loops->num; i++)
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.37
diff -c -3 -p -r1.1.2.37 tree-scalar-evolution.c
*** tree-scalar-evolution.c 21 Apr 2004 11:59:12 -0000 1.1.2.37
--- tree-scalar-evolution.c 21 Apr 2004 13:15:40 -0000
*************** tree chrec_top;
*** 289,297 ****
tree chrec_bot;
static struct loops *current_loops;
- static varray_type scalar_evolution_info;
static varray_type already_instantiated;
/* Flag to indicate availability of dependency info. */
static bool dd_info_available;
--- 289,298 ----
tree chrec_bot;
static struct loops *current_loops;
static varray_type already_instantiated;
+ static htab_t scalar_evolution_info;
+
/* Flag to indicate availability of dependency info. */
static bool dd_info_available;
*************** new_scev_info_str (tree var)
*** 303,315 ****
{
struct scev_info_str *res;
! res = ggc_alloc (sizeof (struct scev_info_str));
res->var = var;
res->chrec = chrec_not_analyzed_yet;
return res;
}
/* Get the index corresponding to VAR in the current LOOP. If
it's the first time we ask for this VAR, then we return
chrec_not_analysed_yet for this VAR and return its index. */
--- 304,343 ----
{
struct scev_info_str *res;
! res = xmalloc (sizeof (struct scev_info_str));
res->var = var;
res->chrec = chrec_not_analyzed_yet;
return res;
}
+ /* Computes a hash function for database element ELT. */
+
+ static hashval_t
+ hash_scev_info (const void *elt)
+ {
+ return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
+ }
+
+ /* Compares database elements E1 and E2. */
+
+ static int
+ eq_scev_info (const void *e1, const void *e2)
+ {
+ const struct scev_info_str *elt1 = e1;
+ const struct scev_info_str *elt2 = e2;
+
+ return elt1->var == elt2->var;
+ }
+
+ /* Deletes database element E. */
+
+ static void
+ del_scev_info (void *e)
+ {
+ free (e);
+ }
+
/* Get the index corresponding to VAR in the current LOOP. If
it's the first time we ask for this VAR, then we return
chrec_not_analysed_yet for this VAR and return its index. */
*************** new_scev_info_str (tree var)
*** 317,336 ****
static tree *
find_var_scev_info (tree var)
{
- unsigned int i;
struct scev_info_str *res;
!
! for (i = 0; i < VARRAY_ACTIVE_SIZE (scalar_evolution_info); i++)
! {
! res = VARRAY_GENERIC_PTR (scalar_evolution_info, i);
! if (res->var == var)
! return &res->chrec;
! }
!
! /* The variable is not in the table, create a new entry for it. */
! res = new_scev_info_str (var);
! VARRAY_PUSH_GENERIC_PTR (scalar_evolution_info, res);
!
return &res->chrec;
}
--- 345,361 ----
static tree *
find_var_scev_info (tree var)
{
struct scev_info_str *res;
! struct scev_info_str tmp;
! PTR *slot;
!
! tmp.var = var;
! slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
!
! if (!*slot)
! *slot = new_scev_info_str (var);
! res = *slot;
!
return &res->chrec;
}
*************** dump_chrecs_stats (FILE *file, struct ch
*** 3135,3141 ****
stats->nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
! (int) VARRAY_ACTIVE_SIZE (scalar_evolution_info));
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
--- 3160,3166 ----
stats->nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
! (int) htab_elements (scalar_evolution_info));
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
*************** analyze_scalar_evolution_for_all_loop_ph
*** 3269,3294 ****
dump_chrecs_stats (dump_file, &stats);
}
/* Classify the chrecs of the whole database. */
void
gather_stats_on_scev_database (void)
{
- unsigned i;
struct chrec_stats stats;
if (!dump_file)
return;
reset_chrecs_counters (&stats);
!
! for (i = 0; i < VARRAY_ACTIVE_SIZE (scalar_evolution_info); i++)
! {
! struct scev_info_str *elt =
! VARRAY_GENERIC_PTR (scalar_evolution_info, i);
! gather_chrec_stats (elt->chrec, &stats);
! }
!
dump_chrecs_stats (dump_file, &stats);
}
--- 3294,3327 ----
dump_chrecs_stats (dump_file, &stats);
}
+ /* Callback for htab_traverse, gathers information on chrecs in the
+ hashtable. */
+
+ static int
+ gather_stats_on_scev_database_1 (void **slot, void *stats)
+ {
+ struct scev_info_str *entry = *slot;
+
+ gather_chrec_stats (entry->chrec, stats);
+
+ return 1;
+ }
+
/* Classify the chrecs of the whole database. */
void
gather_stats_on_scev_database (void)
{
struct chrec_stats stats;
if (!dump_file)
return;
reset_chrecs_counters (&stats);
!
! htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
! &stats);
!
dump_chrecs_stats (dump_file, &stats);
}
*************** scev_initialize (struct loops *loops)
*** 3329,3336 ****
unsigned i;
current_loops = loops;
! VARRAY_GENERIC_PTR_INIT (scalar_evolution_info, 100,
! "scalar_evolution_info");
VARRAY_TREE_INIT (already_instantiated, 3,
"already_instantiated");
--- 3362,3369 ----
unsigned i;
current_loops = loops;
! scalar_evolution_info = htab_create (100, hash_scev_info,
! eq_scev_info, del_scev_info);
VARRAY_TREE_INIT (already_instantiated, 3,
"already_instantiated");
*************** scev_elim_checks (void)
*** 3394,3400 ****
static void
scev_linear_transform (void)
{
! linear_transform_loops (current_loops, scalar_evolution_info);
}
/* Runs the canonical iv creation pass. */
--- 3427,3433 ----
static void
scev_linear_transform (void)
{
! linear_transform_loops (current_loops);
}
/* Runs the canonical iv creation pass. */
*************** scev_vectorize (void)
*** 3412,3418 ****
{
bitmap_clear (vars_to_rename);
! vectorize_loops (current_loops, scalar_evolution_info);
}
/* Finalize the scalar evolution analysis. */
--- 3445,3451 ----
{
bitmap_clear (vars_to_rename);
! vectorize_loops (current_loops);
}
/* Finalize the scalar evolution analysis. */
*************** scev_vectorize (void)
*** 3420,3426 ****
void
scev_finalize (void)
{
! scalar_evolution_info = NULL;
already_instantiated = NULL;
current_loops = NULL;
}
--- 3453,3459 ----
void
scev_finalize (void)
{
! htab_delete (scalar_evolution_info);
already_instantiated = NULL;
current_loops = NULL;
}
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.c,v
retrieving revision 1.1.2.28
diff -c -3 -p -r1.1.2.28 tree-vectorizer.c
*** tree-vectorizer.c 20 Apr 2004 17:23:25 -0000 1.1.2.28
--- tree-vectorizer.c 21 Apr 2004 13:15:40 -0000
*************** need_imm_uses_for (tree var)
*** 3334,3341 ****
Entry Point to loop vectorization phase. */
void
! vectorize_loops (struct loops *loops,
! varray_type ev_info ATTRIBUTE_UNUSED)
{
unsigned int i;
unsigned int num_vectorized_loops = 0;
--- 3334,3340 ----
Entry Point to loop vectorization phase. */
void
! vectorize_loops (struct loops *loops)
{
unsigned int i;
unsigned int num_vectorized_loops = 0;
Index: tree-vectorizer.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.h,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-vectorizer.h
*** tree-vectorizer.h 15 Apr 2004 15:21:37 -0000 1.1.2.10
--- tree-vectorizer.h 21 Apr 2004 13:15:40 -0000
*************** typedef struct _loop_vec_info {
*** 164,170 ****
/*-----------------------------------------------------------------*/
/* Main driver. */
! extern void vectorize_loops (struct loops *, varray_type);
/* creation and deletion of loop and stmt info structs. */
extern loop_vec_info new_loop_vec_info (struct loop *loop);
--- 164,170 ----
/*-----------------------------------------------------------------*/
/* Main driver. */
! extern void vectorize_loops (struct loops *);
/* creation and deletion of loop and stmt info structs. */
extern loop_vec_info new_loop_vec_info (struct loop *loop);