------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-27 15:00 -------
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> ------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
> 2005-01-27 13:18 -------
> Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
>
> With the following patch I got some speedup for depth 100.
>
> from:
> tree iv optimization : 2.62 (62%) usr 0.27 (82%) sys 2.92 (62%) wall
> tree iv optimization : 2.33 (59%) usr 0.25 (83%) sys 2.63 (54%) wall
>
> to:
> tree iv optimization : 1.19 (46%) usr 0.04 (40%) sys 1.26 (45%) wall
> tree iv optimization : 1.21 (47%) usr 0.05 (45%) sys 1.30 (46%) wall
>
> Basically we're reseting too much information each time scev_reset is
> called. It would even be possible to reset only the part of the scev
> database that contains symbols instead of erasing everything.
>
> Do somebody know how to iterate over all the elements of the hash
> setting to NULL_TREE the elements that answer true to
> chrec_contains_symbols?
the patch is below (in stronger form -- only removing entries that
contain invalidated symbols), and indeed helps with this testcase.
It however causes measurable slow down on normal code (see analysis
in one of the previous mails).
Note that your patch is not entirely correct -- in case loop is
unrolled, its number of iterations is changed, so in this case
scev_reset should clear its number of iterations unconditionally
(I think something similar occurs with vectorizer, so we need to
be a bit careful).
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-loop-linear.c,v
retrieving revision 2.6
diff -c -3 -p -r2.6 tree-loop-linear.c
*** tree-loop-linear.c 18 Jan 2005 11:36:24 -0000 2.6
--- tree-loop-linear.c 24 Jan 2005 01:34:04 -0000
*************** linear_transform_loops (struct loops *lo
*** 373,379 ****
free_data_refs (datarefs);
}
free_df ();
! scev_reset ();
rewrite_into_loop_closed_ssa ();
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
--- 373,379 ----
free_data_refs (datarefs);
}
free_df ();
! scev_reset (NULL);
rewrite_into_loop_closed_ssa ();
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.16
diff -c -3 -p -r2.16 tree-scalar-evolution.c
*** tree-scalar-evolution.c 18 Jan 2005 11:36:26 -0000 2.16
--- tree-scalar-evolution.c 24 Jan 2005 01:34:05 -0000
*************** scev_initialize (struct loops *loops)
*** 2475,2484 ****
loops->parray[i]->nb_iterations = NULL_TREE;
}
! /* Cleans up the information cached by the scalar evolutions analysis. */
void
! scev_reset (void)
{
unsigned i;
struct loop *loop;
--- 2475,2539 ----
loops->parray[i]->nb_iterations = NULL_TREE;
}
! /* Returns true if EXPR references one of the ssa names in set
! INVALIDATED_NAMES. */
!
! static bool
! tree_references_names (tree expr, bitmap invalidated_names)
! {
! if (!expr)
! return false;
!
! if (TREE_CODE (expr) == SSA_NAME)
! return bitmap_bit_p (invalidated_names, SSA_NAME_VERSION (expr));
!
! switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
! {
! case 4:
! if (tree_references_names (TREE_OPERAND (expr, 3), invalidated_names))
! return true;
! case 3:
! if (tree_references_names (TREE_OPERAND (expr, 2), invalidated_names))
! return true;
! case 2:
! if (tree_references_names (TREE_OPERAND (expr, 1), invalidated_names))
! return true;
! case 1:
! if (tree_references_names (TREE_OPERAND (expr, 0), invalidated_names))
! return true;
! case 0:
! return false;
!
! default:
! /* Don't worry about handling strange cases. This function is only used
! in a way in that it does not matter if we return true here. */
! return true;
! }
! }
!
! /* If the SLOT in the scev cache contains ssa name belonging to the set
! passed in DATA, the function removes it from the cache. Callback
! for htab_traverse. */
!
! static int
! invalidate_names_reference (void **slot, void *data)
! {
! bitmap invalidated_names = data;
! struct scev_info_str *elt = *slot;
!
! if (tree_references_names (elt->var, invalidated_names)
! || tree_references_names (elt->chrec, invalidated_names))
! htab_clear_slot (scalar_evolution_info, slot);
!
! return 1;
! }
!
! /* Cleans up the information cached by the scalar evolutions analysis.
! If INVALIDATED_NAMES is provided, only the references to invalidated
! ssa names are removed. */
void
! scev_reset (bitmap invalidated_names)
{
unsigned i;
struct loop *loop;
*************** scev_reset (void)
*** 2486,2497 ****
if (!scalar_evolution_info || !current_loops)
return;
! htab_empty (scalar_evolution_info);
for (i = 1; i < current_loops->num; i++)
{
loop = current_loops->parray[i];
! if (loop)
! loop->nb_iterations = NULL_TREE;
}
}
--- 2541,2564 ----
if (!scalar_evolution_info || !current_loops)
return;
! if (invalidated_names)
! htab_traverse (scalar_evolution_info, invalidate_names_reference,
! invalidated_names);
! else
! htab_empty (scalar_evolution_info);
!
for (i = 1; i < current_loops->num; i++)
{
loop = current_loops->parray[i];
! if (!loop
! || !loop->nb_iterations)
! continue;
!
! if (invalidated_names
! && !tree_references_names (loop->nb_iterations, invalidated_names))
! continue;
!
! loop->nb_iterations = NULL_TREE;
}
}
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.h,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-scalar-evolution.h
*** tree-scalar-evolution.h 17 Nov 2004 22:06:00 -0000 2.3
--- tree-scalar-evolution.h 24 Jan 2005 01:34:05 -0000
*************** extern tree number_of_iterations_in_loop
*** 26,32 ****
extern tree get_loop_exit_condition (struct loop *);
extern void scev_initialize (struct loops *loops);
! extern void scev_reset (void);
extern void scev_finalize (void);
extern tree analyze_scalar_evolution (struct loop *, tree);
extern tree instantiate_parameters (struct loop *, tree);
--- 26,32 ----
extern tree get_loop_exit_condition (struct loop *);
extern void scev_initialize (struct loops *loops);
! extern void scev_reset (bitmap);
extern void scev_finalize (void);
extern tree analyze_scalar_evolution (struct loop *, tree);
extern tree instantiate_parameters (struct loop *, tree);
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c 1 Oct 2004 18:26:31 -0000 2.5
--- tree-ssa-loop-ivcanon.c 24 Jan 2005 01:34:05 -0000
*************** canonicalize_induction_variables (struct
*** 262,268 ****
/* Clean up the information about numbers of iterations, since brute force
evaluation could reveal new information. */
! scev_reset ();
#if 0
/* The necessary infrastructure is not in yet. */
--- 262,268 ----
/* Clean up the information about numbers of iterations, since brute force
evaluation could reveal new information. */
! scev_reset (NULL);
#if 0
/* The necessary infrastructure is not in yet. */
*************** tree_unroll_loops_completely (struct loo
*** 294,300 ****
/* Clean up the information about numbers of iterations, since complete
unrolling might have invalidated it. */
! scev_reset ();
#if 0
/* The necessary infrastructure is not in yet. */
--- 294,300 ----
/* Clean up the information about numbers of iterations, since complete
unrolling might have invalidated it. */
! scev_reset (NULL);
#if 0
/* The necessary infrastructure is not in yet. */
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.42
diff -c -3 -p -r2.42 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 19 Jan 2005 22:50:04 -0000 2.42
--- tree-ssa-loop-ivopts.c 24 Jan 2005 01:34:05 -0000
*************** struct ivopts_data
*** 208,213 ****
--- 208,216 ----
/* The bitmap of indices in version_info whose value was changed. */
bitmap relevant;
+ /* The set of ssa names whose scev info might get invalidated. */
+ bitmap invalidated_names;
+
/* The maximum invariant id. */
unsigned max_inv_id;
*************** tree_ssa_iv_optimize_init (struct loops
*** 651,656 ****
--- 654,660 ----
data->version_info = xcalloc (data->version_info_size,
sizeof (struct version_info));
data->relevant = BITMAP_XMALLOC ();
+ data->invalidated_names = BITMAP_XMALLOC ();
data->important_candidates = BITMAP_XMALLOC ();
data->max_inv_id = 0;
*************** remove_unused_ivs (struct ivopts_data *d
*** 5016,5022 ****
&& !info->inv_id
&& !info->iv->have_use_for
&& !info->preserve_biv)
! remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
}
}
--- 5020,5029 ----
&& !info->inv_id
&& !info->iv->have_use_for
&& !info->preserve_biv)
! {
! bitmap_set_bit (data->invalidated_names, j);
! remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
! }
}
}
*************** free_loop_data (struct ivopts_data *data
*** 5041,5046 ****
--- 5048,5054 ----
info->inv_id = 0;
}
bitmap_clear (data->relevant);
+ bitmap_clear (data->invalidated_names);
bitmap_clear (data->important_candidates);
for (i = 0; i < n_iv_uses (data); i++)
*************** tree_ssa_iv_optimize_finalize (struct lo
*** 5104,5109 ****
--- 5112,5118 ----
free_loop_data (data);
free (data->version_info);
BITMAP_XFREE (data->relevant);
+ BITMAP_XFREE (data->invalidated_names);
BITMAP_XFREE (data->important_candidates);
VARRAY_FREE (decl_rtl_to_reset);
*************** tree_ssa_iv_optimize_loop (struct ivopts
*** 5177,5183 ****
/* We have changed the structure of induction variables; it might happen
that definitions in the scev database refer to some of them that were
eliminated. */
! scev_reset ();
finish:
free_loop_data (data);
--- 5186,5192 ----
/* We have changed the structure of induction variables; it might happen
that definitions in the scev database refer to some of them that were
eliminated. */
! scev_reset (data->invalidated_names);
finish:
free_loop_data (data);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-manip.c,v
retrieving revision 2.21
diff -c -3 -p -r2.21 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c 29 Nov 2004 17:53:47 -0000 2.21
--- tree-ssa-loop-manip.c 24 Jan 2005 01:34:05 -0000
*************** tree_duplicate_loop_to_header_edge (stru
*** 633,639 ****
set_phi_def_stmts (bb->rbi->original);
}
! scev_reset ();
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
#endif
--- 633,639 ----
set_phi_def_stmts (bb->rbi->original);
}
! scev_reset (NULL);
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
#endif
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.23
diff -c -3 -p -r2.23 tree-ssa-loop.c
*** tree-ssa-loop.c 26 Nov 2004 06:42:25 -0000 2.23
--- tree-ssa-loop.c 24 Jan 2005 01:34:05 -0000
*************** tree_ssa_loop_bounds (void)
*** 306,312 ****
return;
estimate_numbers_of_iterations (current_loops);
! scev_reset ();
}
struct tree_opt_pass pass_record_bounds =
--- 306,312 ----
return;
estimate_numbers_of_iterations (current_loops);
! scev_reset (NULL);
}
struct tree_opt_pass pass_record_bounds =
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.c,v
retrieving revision 2.62
diff -c -3 -p -r2.62 tree-vectorizer.c
*** tree-vectorizer.c 18 Jan 2005 11:36:29 -0000 2.62
--- tree-vectorizer.c 24 Jan 2005 01:34:05 -0000
*************** vect_do_peeling_for_loop_bound (loop_vec
*** 3258,3264 ****
vect_update_ivs_after_vectorizer (loop, ratio_mult_vf_name, update_e);
/* After peeling we have to reset scalar evolution analyzer. */
! scev_reset ();
return;
}
--- 3258,3264 ----
vect_update_ivs_after_vectorizer (loop, ratio_mult_vf_name, update_e);
/* After peeling we have to reset scalar evolution analyzer. */
! scev_reset (NULL);
return;
}
*************** vect_do_peeling_for_alignment (loop_vec_
*** 3442,3448 ****
vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
/* After peeling we have to reset scalar evolution analyzer. */
! scev_reset ();
return;
}
--- 3442,3448 ----
vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
/* After peeling we have to reset scalar evolution analyzer. */
! scev_reset (NULL);
return;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
