This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for PR22325
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 15 Jul 2005 14:11:22 +0200
- Subject: [patch] for PR22325
Hello,
this patch implements replacement of final value of iv in cases when the
final value is not a constant. E.g.
for (i = 0; i < 100; i++)
a+=3;
is replaced by
for (i = 0; i < 100; i++)
;
a+=300;
Bootstrapped & regtested on i686.
Zdenek
PR tree-optimization/22325
* tree-flow.h (compute_phi_arg_on_exit, force_expr_to_var_cost):
Declare.
* tree-scalar-evolution.c (scev_const_prop): Add generic final
value replacement.
* tree-ssa-loop-ivopts.c (force_expr_to_var_cost): Split from ...
(force_var_cost): ... this function.
(compute_phi_arg_on_exit): Export.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.125
diff -c -3 -p -r2.125 tree-flow.h
*** tree-flow.h 11 Jul 2005 23:59:09 -0000 2.125
--- tree-flow.h 15 Jul 2005 12:05:25 -0000
*************** bool for_each_index (tree *, bool (*) (t
*** 707,712 ****
--- 707,714 ----
void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
tree *, tree *);
void split_loop_exit_edge (edge);
+ void compute_phi_arg_on_exit (edge, tree, tree);
+ unsigned force_expr_to_var_cost (tree);
basic_block bsi_insert_on_edge_immediate_loop (edge, tree);
void standard_iv_increment_position (struct loop *, block_stmt_iterator *,
bool *);
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.30
diff -c -3 -p -r2.30 tree-scalar-evolution.c
*** tree-scalar-evolution.c 26 Jun 2005 21:21:31 -0000 2.30
--- tree-scalar-evolution.c 15 Jul 2005 12:05:27 -0000
*************** scev_finalize (void)
*** 2608,2615 ****
}
/* Replace ssa names for that scev can prove they are constant by the
! appropriate constants. Most importantly, this takes care of final
! value replacement.
We only consider SSA names defined by phi nodes; rest is left to the
ordinary constant propagation pass. */
--- 2608,2615 ----
}
/* Replace ssa names for that scev can prove they are constant by the
! appropriate constants. Also perform final value replacement in loops,
! in case the replacement expressions are cheap.
We only consider SSA names defined by phi nodes; rest is left to the
ordinary constant propagation pass. */
*************** void
*** 2618,2626 ****
scev_const_prop (void)
{
basic_block bb;
! tree name, phi, type, ev;
! struct loop *loop;
bitmap ssa_names_to_remove = NULL;
if (!current_loops)
return;
--- 2618,2627 ----
scev_const_prop (void)
{
basic_block bb;
! tree name, phi, next_phi, type, ev;
! struct loop *loop, *ex_loop;
bitmap ssa_names_to_remove = NULL;
+ unsigned i;
if (!current_loops)
return;
*************** scev_const_prop (void)
*** 2675,2678 ****
--- 2676,2731 ----
BITMAP_FREE (ssa_names_to_remove);
scev_reset ();
}
+
+ /* Now the regular final value replacement. */
+ for (i = current_loops->num - 1; i > 0; i--)
+ {
+ edge exit;
+ tree def, stmts;
+
+ loop = current_loops->parray[i];
+ if (!loop)
+ continue;
+
+ /* If we do not know exact number of iterations of the loop, we cannot
+ replace the final value. */
+ exit = loop->single_exit;
+ if (!exit
+ || number_of_iterations_in_loop (loop) == chrec_dont_know)
+ continue;
+ ex_loop = exit->dest->loop_father;
+
+ for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
+ {
+ next_phi = PHI_CHAIN (phi);
+ def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ if (!is_gimple_reg (def)
+ || expr_invariant_in_loop_p (loop, def))
+ continue;
+
+ if (!POINTER_TYPE_P (TREE_TYPE (def))
+ && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
+ continue;
+
+ def = analyze_scalar_evolution_in_loop (ex_loop, ex_loop, def);
+ if (!tree_does_not_contain_chrecs (def)
+ || chrec_contains_symbols_defined_in_loop (def, loop->num))
+ continue;
+
+ /* If computing the expression is expensive, let it remain in
+ loop. TODO -- we should take the cost of computing the expression
+ in loop into account. */
+ if (force_expr_to_var_cost (def) >= target_spill_cost)
+ continue;
+
+ if (is_gimple_val (def))
+ stmts = NULL_TREE;
+ else
+ def = force_gimple_operand (def, &stmts, true,
+ SSA_NAME_VAR (PHI_RESULT (phi)));
+ SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit), def);
+ if (stmts)
+ compute_phi_arg_on_exit (exit, stmts, def);
+ }
+ }
}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.84
diff -c -3 -p -r2.84 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 11 Jul 2005 23:59:11 -0000 2.84
--- tree-ssa-loop-ivopts.c 15 Jul 2005 12:05:34 -0000
*************** get_address_cost (bool symbol_present, b
*** 3414,3425 ****
return cost + acost;
}
- /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
- invariants the computation depends on. */
! static unsigned
! force_var_cost (struct ivopts_data *data,
! tree expr, bitmap *depends_on)
{
static bool costs_initialized = false;
static unsigned integer_cost;
--- 3414,3424 ----
return cost + acost;
}
! /* Estimates cost of forcing expression EXPR into a variable. */
!
! unsigned
! force_expr_to_var_cost (tree expr)
{
static bool costs_initialized = false;
static unsigned integer_cost;
*************** force_var_cost (struct ivopts_data *data
*** 3451,3457 ****
build_int_cst_type (type, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "force_var_cost:\n");
fprintf (dump_file, " integer %d\n", (int) integer_cost);
fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
fprintf (dump_file, " address %d\n", (int) address_cost);
--- 3450,3456 ----
build_int_cst_type (type, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "force_expr_to_var_cost:\n");
fprintf (dump_file, " integer %d\n", (int) integer_cost);
fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
fprintf (dump_file, " address %d\n", (int) address_cost);
*************** force_var_cost (struct ivopts_data *data
*** 3464,3475 ****
STRIP_NOPS (expr);
- if (depends_on)
- {
- fd_ivopts_data = data;
- walk_tree (&expr, find_depends, depends_on, NULL);
- }
-
if (SSA_VAR_P (expr))
return 0;
--- 3463,3468 ----
*************** force_var_cost (struct ivopts_data *data
*** 3504,3515 ****
if (is_gimple_val (op0))
cost0 = 0;
else
! cost0 = force_var_cost (data, op0, NULL);
if (is_gimple_val (op1))
cost1 = 0;
else
! cost1 = force_var_cost (data, op1, NULL);
break;
--- 3497,3508 ----
if (is_gimple_val (op0))
cost0 = 0;
else
! cost0 = force_expr_to_var_cost (op0);
if (is_gimple_val (op1))
cost1 = 0;
else
! cost1 = force_expr_to_var_cost (op1);
break;
*************** force_var_cost (struct ivopts_data *data
*** 3549,3554 ****
--- 3542,3563 ----
return cost < target_spill_cost ? cost : target_spill_cost;
}
+ /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
+ invariants the computation depends on. */
+
+ static unsigned
+ force_var_cost (struct ivopts_data *data,
+ tree expr, bitmap *depends_on)
+ {
+ if (depends_on)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&expr, find_depends, depends_on, NULL);
+ }
+
+ return force_expr_to_var_cost (expr);
+ }
+
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
to false if the corresponding part is missing. DEPENDS_ON is a set of the
*************** protect_loop_closed_ssa_form (edge exit,
*** 5599,5605 ****
so that they are emitted on the correct place, and so that the loop closed
ssa form is preserved. */
! static void
compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
{
tree_stmt_iterator tsi;
--- 5608,5614 ----
so that they are emitted on the correct place, and so that the loop closed
ssa form is preserved. */
! void
compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
{
tree_stmt_iterator tsi;