This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Serious performance regression -- some tree optimizer questions
Hello,
> >They should obviously be performed before ivopts, so there is no
> >interference (ivopts may be easily used for the "single canonical iv"
> >creation,
> >if needed).
>
> Without it doing strength reduction (which i don't want to happen till
> later, since it removes array references and whatnot)?
here is the patch (not tested except for looking on dump for
one testcase and letting it compile first few files of bootstrap,
so I hope nothing should be fundamentally broken, but there may be some
problems).
Zdenek
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.75
diff -c -3 -p -r2.75 tree-flow.h
*** tree-flow.h 10 Dec 2004 21:54:41 -0000 2.75
--- tree-flow.h 12 Jan 2005 20:39:17 -0000
*************** void tree_ssa_unswitch_loops (struct loo
*** 657,662 ****
--- 657,663 ----
void canonicalize_induction_variables (struct loops *);
void tree_unroll_loops_completely (struct loops *);
void tree_ssa_iv_optimize (struct loops *);
+ void force_single_biv (struct loops *);
void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
struct tree_niter_desc *);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.67
diff -c -3 -p -r2.67 tree-optimize.c
*** tree-optimize.c 4 Jan 2005 01:54:26 -0000 2.67
--- tree-optimize.c 12 Jan 2005 20:39:17 -0000
*************** init_tree_optimization_passes (void)
*** 408,413 ****
--- 408,414 ----
NEXT_PASS (pass_lim);
NEXT_PASS (pass_unswitch);
NEXT_PASS (pass_record_bounds);
+ NEXT_PASS (pass_force_single_biv);
NEXT_PASS (pass_linear_transform);
NEXT_PASS (pass_iv_canon);
NEXT_PASS (pass_if_conversion);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.23
diff -c -3 -p -r2.23 tree-pass.h
*** tree-pass.h 4 Jan 2005 01:54:26 -0000 2.23
--- tree-pass.h 12 Jan 2005 20:39:17 -0000
*************** extern struct tree_opt_pass pass_expand;
*** 164,169 ****
--- 164,170 ----
extern struct tree_opt_pass pass_rest_of_compilation;
extern struct tree_opt_pass pass_fre;
extern struct tree_opt_pass pass_linear_transform;
+ extern struct tree_opt_pass pass_force_single_biv;
extern struct tree_opt_pass pass_maybe_create_global_var;
#endif /* GCC_TREE_PASS_H */
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.40
diff -c -3 -p -r2.40 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 12 Jan 2005 00:05:55 -0000 2.40
--- tree-ssa-loop-ivopts.c 12 Jan 2005 20:39:17 -0000
*************** find_invariants_stmt (struct ivopts_data
*** 1502,1511 ****
}
}
! /* Finds interesting uses of induction variables in the statement STMT. */
static void
! find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
{
struct iv *iv;
tree op, lhs, rhs;
--- 1502,1514 ----
}
}
! /* Finds interesting uses of induction variables in the statement STMT.
! If ONLY_IV_DEFS is true, only find definitions of induction variables,
! otherwise consider addresses of memory references as well. */
static void
! find_interesting_uses_stmt (struct ivopts_data *data, tree stmt,
! bool only_iv_defs)
{
struct iv *iv;
tree op, lhs, rhs;
*************** find_interesting_uses_stmt (struct ivopt
*** 1543,1548 ****
--- 1546,1554 ----
return;
case tcc_reference:
+ if (only_iv_defs)
+ break;
+
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
if (REFERENCE_CLASS_P (lhs))
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
*************** find_interesting_uses_stmt (struct ivopt
*** 1552,1558 ****
}
if (REFERENCE_CLASS_P (lhs)
! && is_gimple_val (rhs))
{
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
find_interesting_uses_op (data, rhs);
--- 1558,1565 ----
}
if (REFERENCE_CLASS_P (lhs)
! && is_gimple_val (rhs)
! && !only_iv_defs)
{
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
find_interesting_uses_op (data, rhs);
*************** find_interesting_uses_outside (struct iv
*** 1619,1628 ****
}
}
! /* Finds uses of the induction variables that are interesting. */
static void
! find_interesting_uses (struct ivopts_data *data)
{
basic_block bb;
block_stmt_iterator bsi;
--- 1626,1638 ----
}
}
! /* Finds uses of the induction variables that are interesting.
! If ONLY_IV_DEFS is true, we find only the definitions of
! induction variables. Otherwise we also try to find other
! uses (addresses of memory references). */
static void
! find_interesting_uses (struct ivopts_data *data, bool only_iv_defs)
{
basic_block bb;
block_stmt_iterator bsi;
*************** find_interesting_uses (struct ivopts_dat
*** 1646,1654 ****
find_interesting_uses_outside (data, e);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
! find_interesting_uses_stmt (data, phi);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! find_interesting_uses_stmt (data, bsi_stmt (bsi));
}
if (dump_file && (dump_flags & TDF_DETAILS))
--- 1656,1664 ----
find_interesting_uses_outside (data, e);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
! find_interesting_uses_stmt (data, phi, only_iv_defs);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! find_interesting_uses_stmt (data, bsi_stmt (bsi), only_iv_defs);
}
if (dump_file && (dump_flags & TDF_DETAILS))
*************** tree_ssa_iv_optimize_loop (struct ivopts
*** 5129,5135 ****
goto finish;
/* Finds interesting uses (item 1). */
! find_interesting_uses (data);
if (n_iv_uses (data) > MAX_CONSIDERED_USES)
goto finish;
--- 5139,5145 ----
goto finish;
/* Finds interesting uses (item 1). */
! find_interesting_uses (data, false);
if (n_iv_uses (data) > MAX_CONSIDERED_USES)
goto finish;
*************** tree_ssa_iv_optimize (struct loops *loop
*** 5215,5217 ****
--- 5225,5392 ----
tree_ssa_iv_optimize_finalize (loops, &data);
}
+
+ /* Selects a canonical iv with base 0 and step 1. */
+
+ static void
+ select_single_canonical_iv (struct ivopts_data *data)
+ {
+ tree widest_type = NULL, type;
+ unsigned i;
+ struct iv_use *use;
+ enum iv_position pos;
+
+ /* We might be more clever here and check whether one of the original
+ ivs is not usable. Not done for simplicity. */
+
+ /* Check the uses and find the one whose type is the widest. */
+
+ for (i = 0; i < n_iv_uses (data); i++)
+ {
+ use = iv_use (data, i);
+ type = TREE_TYPE (use->iv->base);
+
+ if (!widest_type
+ || TYPE_PRECISION (type) > TYPE_PRECISION (widest_type))
+ widest_type = type;
+ }
+
+ type = unsigned_type_for (widest_type);
+
+ /* Add the iv. */
+ pos = ip_normal_pos (data->current_loop) ? IP_NORMAL : IP_END;
+ add_candidate_1 (data,
+ build_int_cst_type (type, 0),
+ build_int_cst_type (type, 1),
+ true, pos, NULL, NULL_TREE);
+
+ record_important_candidates (data);
+ }
+
+ /* Forces just a a single canonical biv with base 0 and step 1 to be used
+ in the LOOP. Returns true if successful. */
+
+ static bool
+ force_single_biv_loop (struct ivopts_data *data, struct loop *loop)
+ {
+ bool changed = false;
+ struct iv_ca *iv_ca;
+ edge exit;
+
+ data->current_loop = loop;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Processing loop %d\n", loop->num);
+
+ exit = single_dom_exit (loop);
+ if (exit)
+ {
+ fprintf (dump_file, " single exit %d -> %d, exit condition ",
+ exit->src->index, exit->dest->index);
+ print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ fprintf (dump_file, "\n");
+ }
+
+ /* For each ssa name determines whether it behaves as an induction variable
+ in some loop. */
+ if (!find_induction_variables (data))
+ goto finish;
+
+ /* Finds interesting uses. Only definitions of induction variables are taken
+ into account, so that we do not rewrite memory references. */
+ find_interesting_uses (data, true);
+ if (n_iv_uses (data) > MAX_CONSIDERED_USES
+ || n_iv_uses (data) == 0)
+ goto finish;
+
+ /* Create the candidate for the canonical iv. */
+ select_single_canonical_iv (data);
+
+ /* This as well as find_optimal_iv_set is a waste of time here, since
+ it is clear what must be selected. Kept here just to make things
+ simpler. */
+
+ /* Calculates the costs. */
+ determine_use_iv_costs (data);
+ determine_iv_costs (data);
+ determine_set_costs (data);
+
+ /* Find the optimal set of induction variables. */
+ iv_ca = find_optimal_iv_set (data);
+ if (!iv_ca)
+ goto finish;
+ changed = true;
+
+ /* Create the new induction variables (item 4, part 1). */
+ create_new_ivs (data, iv_ca);
+ iv_ca_free (&iv_ca);
+
+ /* Rewrite the uses (item 4, part 2). */
+ rewrite_uses (data);
+
+ /* Remove the ivs that are unused after rewriting. */
+ remove_unused_ivs (data);
+
+ loop_commit_inserts ();
+
+ /* 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);
+
+ return changed;
+ }
+
+ /* Alternative entry to the pass. Forces all LOOPs to have just one biv
+ with base 0 and step 1. */
+
+ void
+ force_single_biv (struct loops *loops)
+ {
+ struct loop *loop;
+ struct ivopts_data data;
+
+ tree_ssa_iv_optimize_init (loops, &data);
+
+ /* Optimize the loops starting with the innermost ones. */
+ loop = loops->tree_root;
+ while (loop->inner)
+ loop = loop->inner;
+
+ #ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ verify_stmts ();
+ #endif
+
+ /* Scan the loops, inner ones first. */
+ while (loop != loops->tree_root)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ flow_loop_dump (loop, dump_file, NULL, 1);
+
+ force_single_biv_loop (&data, loop);
+
+ if (loop->next)
+ {
+ loop = loop->next;
+ while (loop->inner)
+ loop = loop->inner;
+ }
+ else
+ loop = loop->outer;
+ }
+
+ #ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ verify_stmts ();
+ #endif
+
+ tree_ssa_iv_optimize_finalize (loops, &data);
+ }
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 12 Jan 2005 20:39:17 -0000
*************** struct tree_opt_pass pass_vectorize =
*** 228,233 ****
--- 228,267 ----
0 /* letter */
};
+ /* Single canonical iv creation. */
+
+ static void
+ tree_force_single_biv (void)
+ {
+ if (!current_loops)
+ return;
+
+ force_single_biv (current_loops);
+ }
+
+ static bool
+ gate_force_single_biv (void)
+ {
+ /* For testing purposes only. */
+ return true;
+ }
+
+ struct tree_opt_pass pass_force_single_biv =
+ {
+ "fsbiv", /* name */
+ gate_force_single_biv, /* gate */
+ tree_force_single_biv, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+ };
/* Loop nest optimizations. */