Allow CD-DCE to remove (finite) empty loops
Jan Hubicka
hubicka@ucw.cz
Fri Jul 3 00:05:00 GMT 2009
Hi
this patch removes empty loop removal pass and adds corresponding logic to
cd-dce. The motivation is that cd-dce is less restricted that empty loop
removal (i.e. it can handle empty loops with multiple exits, nested empty loops
or loops only controlling number of iterations of other empty loop) and that we
can do this during early optimizations avoiding some confussion of inliner
metrics on code using pooma. (yes, tramo3d ;)
I looked for cases where empty loop removal pass still matches, there are 3 in bootstrap,
all of them because of loop that has __builtin_expect in exit conditoin. Before inlining
we don't estimate number of iterations since we scalar evolution code does not see through
__builtin_expect, while after inlining we remove the hint and get count right.
The loops are removed by later cddce pass, so code quality is same.
While patch removes a pass, it is not compile time improvement per se, since
initialization/deinitialization of SCEV is more expnesive that trivial pass
through already initialized datastructures. However I tried to benchmark it on
tramp3d and on GCC modules and didn't measured any off-noise difference.
The patch also adds hunk removing phi nodes Richard requested to be removed from
previous patch. Now the following testcase ICE without testsuite/gcc.c-torture/compile/921011-2.c:
extern int foobar1 ();
typedef struct
{
unsigned long colormap;
unsigned long red_max;
unsigned long red_mult;
unsigned long green_max;
unsigned long green_mult;
unsigned long blue_max;
unsigned long blue_mult;
unsigned long base_pixel;
unsigned long visualid;
unsigned long killid;
}
frotz;
int
foobar (stdcmap, count)
frotz **stdcmap;
int *count;
{
register int i;
frotz *data = ((void *) 0);
unsigned long nitems;
int ncmaps;
int old_style = 0;
unsigned long def_visual = 0L;
frotz *cmaps;
if ( foobar1 (&data) != 0)
return 0;
if (nitems < 10)
{
ncmaps = 1;
if (nitems < 9)
{
}
}
else
ncmaps = (nitems / 10);
{
register frotz *map;
register frotz *prop;
for (i = ncmaps, map = cmaps, prop = data; i > 0; i--, map++, prop++)
{
map->colormap = prop->colormap;
map->red_max = prop->red_max;
map->red_mult = prop->red_mult;
map->green_max = prop->green_max;
map->green_mult = prop->green_mult;
map->blue_max = prop->blue_max;
map->blue_mult = prop->blue_mult;
map->base_pixel = prop->base_pixel;
map->visualid = (def_visual ? def_visual : prop->visualid);
map->killid = (old_style ? 0L : prop->killid);
}
}
*stdcmap = cmaps;
*count = ncmaps;
}
Bootstrapped/regtested x86_64-linux, OK?
2009-07-03 Jan Hubicka <jh@suse.cz>
* tree-ssa-loop-iv-canon.c (empty_loop_p, remove_empty_loop,
try_remove_empty_loop, remove_empty_loops): Remove.
* tree-ssa-loop.c (tree_ssa_empty_loop, pass_empty_loop): Remove.
* tree-ssa-dce.c (find_obviously_necessary_stmts): Use finiteness info
to mark regular loops as neccesary.
(eliminate_unnecessary_stmts): Take care to remove uses of results of
virtual PHI nodes that became unreachable.
(perform_tree_ssa_dce): Initialize/deinitialize loop optimizer.
* tree-flow.h (remove_empty_loops): Remove.
* passes.c (init_optimization_passes): Remove.
Index: tree-ssa-loop-ivcanon.c
===================================================================
*** tree-ssa-loop-ivcanon.c (revision 149199)
--- tree-ssa-loop-ivcanon.c (working copy)
*************** tree_unroll_loops_completely (bool may_i
*** 558,744 ****
return 0;
}
-
- /* Checks whether LOOP is empty. */
-
- static bool
- empty_loop_p (struct loop *loop)
- {
- edge exit;
- basic_block *body;
- gimple_stmt_iterator gsi;
- unsigned i;
-
- /* If the loop has multiple exits, it is too hard for us to handle.
- Similarly, if the exit is not dominating, we cannot determine
- whether the loop is not infinite. */
- exit = single_dom_exit (loop);
- if (!exit)
- return false;
-
- /* The loop must be finite. */
- if (!finite_loop_p (loop))
- return false;
-
- /* Values of all loop exit phi nodes must be invariants. */
- for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple phi = gsi_stmt (gsi);
- tree def;
-
- if (!is_gimple_reg (PHI_RESULT (phi)))
- continue;
-
- def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
-
- if (!expr_invariant_in_loop_p (loop, def))
- return false;
- }
-
- /* And there should be no memory modifying or from other reasons
- unremovable statements. */
- body = get_loop_body (loop);
- for (i = 0; i < loop->num_nodes; i++)
- {
- /* Irreducible region might be infinite. */
- if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
- {
- free (body);
- return false;
- }
-
- for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
-
- if (gimple_vdef (stmt)
- || gimple_has_volatile_ops (stmt))
- {
- free (body);
- return false;
- }
-
- /* Also, asm statements and calls may have side effects and we
- cannot change the number of times they are executed. */
- switch (gimple_code (stmt))
- {
- case GIMPLE_CALL:
- if (gimple_has_side_effects (stmt))
- {
- free (body);
- return false;
- }
- break;
-
- case GIMPLE_ASM:
- /* We cannot remove volatile assembler. */
- if (gimple_asm_volatile_p (stmt))
- {
- free (body);
- return false;
- }
- break;
-
- default:
- break;
- }
- }
- }
- free (body);
-
- return true;
- }
-
- /* Remove LOOP by making it exit in the first iteration. */
-
- static void
- remove_empty_loop (struct loop *loop)
- {
- edge exit = single_dom_exit (loop), non_exit;
- gimple cond_stmt = last_stmt (exit->src);
- basic_block *body;
- unsigned n_before, freq_in, freq_h;
- gcov_type exit_count = exit->count;
-
- if (dump_file)
- fprintf (dump_file, "Removing empty loop %d\n", loop->num);
-
- non_exit = EDGE_SUCC (exit->src, 0);
- if (non_exit == exit)
- non_exit = EDGE_SUCC (exit->src, 1);
-
- if (exit->flags & EDGE_TRUE_VALUE)
- gimple_cond_make_true (cond_stmt);
- else
- gimple_cond_make_false (cond_stmt);
- update_stmt (cond_stmt);
-
- /* Let us set the probabilities of the edges coming from the exit block. */
- exit->probability = REG_BR_PROB_BASE;
- non_exit->probability = 0;
- non_exit->count = 0;
-
- /* Update frequencies and counts. Everything before
- the exit needs to be scaled FREQ_IN/FREQ_H times,
- where FREQ_IN is the frequency of the entry edge
- and FREQ_H is the frequency of the loop header.
- Everything after the exit has zero frequency. */
- freq_h = loop->header->frequency;
- freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
- if (freq_h != 0)
- {
- body = get_loop_body_in_dom_order (loop);
- for (n_before = 1; n_before <= loop->num_nodes; n_before++)
- if (body[n_before - 1] == exit->src)
- break;
- scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
- scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
- 0, 1);
- free (body);
- }
-
- /* Number of executions of exit is not changed, thus we need to restore
- the original value. */
- exit->count = exit_count;
- }
-
- /* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED
- is set to true if LOOP or any of its subloops is removed. */
-
- static bool
- try_remove_empty_loop (struct loop *loop, bool *changed)
- {
- bool nonempty_subloop = false;
- struct loop *sub;
-
- /* First, all subloops must be removed. */
- for (sub = loop->inner; sub; sub = sub->next)
- nonempty_subloop |= !try_remove_empty_loop (sub, changed);
-
- if (nonempty_subloop || !empty_loop_p (loop))
- return false;
-
- remove_empty_loop (loop);
- *changed = true;
- return true;
- }
-
- /* Remove the empty loops. */
-
- unsigned int
- remove_empty_loops (void)
- {
- bool changed = false;
- struct loop *loop;
-
- for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
- try_remove_empty_loop (loop, &changed);
-
- if (changed)
- {
- scev_reset ();
- return TODO_cleanup_cfg;
- }
- return 0;
- }
-
--- 558,560 ----
Index: tree-ssa-loop.c
===================================================================
*** tree-ssa-loop.c (revision 149199)
--- tree-ssa-loop.c (working copy)
*************** struct gimple_opt_pass pass_scev_cprop =
*** 433,469 ****
}
};
- /* Remove empty loops. */
-
- static unsigned int
- tree_ssa_empty_loop (void)
- {
- if (number_of_loops () <= 1)
- return 0;
-
- return remove_empty_loops ();
- }
-
- struct gimple_opt_pass pass_empty_loop =
- {
- {
- GIMPLE_PASS,
- "empty", /* name */
- NULL, /* gate */
- tree_ssa_empty_loop, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_COMPLETE_UNROLL, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_loops
- | TODO_ggc_collect /* todo_flags_finish */
- }
- };
-
/* Record bounds on numbers of iterations of loops. */
static unsigned int
--- 433,438 ----
Index: tree-ssa-dce.c
===================================================================
*** tree-ssa-dce.c (revision 149199)
--- tree-ssa-dce.c (working copy)
*************** find_obviously_necessary_stmts (struct e
*** 434,450 ****
}
}
if (el)
{
! /* Prevent the loops from being removed. We must keep the infinite loops,
! and we currently do not have a means to recognize the finite ones. */
! FOR_EACH_BB (bb)
! {
! edge_iterator ei;
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->flags & EDGE_DFS_BACK)
! mark_control_dependent_edges_necessary (e->dest, el);
! }
}
}
--- 434,475 ----
}
}
+ /* Pure and const functions are finite and thus have no infinite loops in
+ them. */
+ if ((TREE_READONLY (current_function_decl)
+ || DECL_PURE_P (current_function_decl))
+ && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
+ return;
+
+ /* Prevent the empty possibly infinite loops from being removed. */
if (el)
{
! loop_iterator li;
! struct loop *loop;
! scev_initialize ();
! if (mark_irreducible_loops ())
! FOR_EACH_BB (bb)
! {
! edge_iterator ei;
! FOR_EACH_EDGE (e, ei, bb->succs)
! if ((e->flags & EDGE_DFS_BACK)
! && (e->flags & EDGE_IRREDUCIBLE_LOOP))
! {
! if (dump_file)
! fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
! e->src->index, e->dest->index);
! mark_control_dependent_edges_necessary (e->dest, el);
! }
! }
!
! FOR_EACH_LOOP (li, loop, 0)
! if (!finite_loop_p (loop))
! {
! if (dump_file)
! fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
! mark_control_dependent_edges_necessary (loop->latch, el);
! }
! scev_finalize ();
}
}
*************** eliminate_unnecessary_stmts (void)
*** 1094,1100 ****
}
}
}
!
FOR_EACH_BB (bb)
{
/* Remove dead PHI nodes. */
--- 1119,1160 ----
}
}
}
! /* Since we don't track liveness of virtual PHI nodes, it is possible that we
! rendered some PHI nodes unreachable while they are still in use.
! Mark them for renaming. */
! if (cfg_altered)
! {
! basic_block next_bb;
! find_unreachable_blocks ();
! for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
! {
! next_bb = bb->next_bb;
! if (!(bb->flags & BB_REACHABLE))
! {
! for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
! if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
! {
! bool found = false;
! imm_use_iterator iter;
!
! FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
! {
! if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
! continue;
! if (gimple_code (stmt) == GIMPLE_PHI
! || gimple_plf (stmt, STMT_NECESSARY))
! {
! found = true;
! BREAK_FROM_IMM_USE_STMT (iter);
! }
! }
! if (found)
! mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
! }
! delete_basic_block (bb);
! }
! }
! }
FOR_EACH_BB (bb)
{
/* Remove dead PHI nodes. */
*************** perform_tree_ssa_dce (bool aggressive)
*** 1197,1202 ****
--- 1257,1265 ----
struct edge_list *el = NULL;
bool something_changed = 0;
+ if (aggressive)
+ loop_optimizer_init (LOOPS_HAVE_PREHEADERS);
+
tree_dce_init (aggressive);
if (aggressive)
*************** perform_tree_ssa_dce (bool aggressive)
*** 1216,1221 ****
--- 1279,1287 ----
find_obviously_necessary_stmts (el);
+ if (aggressive)
+ loop_optimizer_finalize ();
+
longest_chain = 0;
total_chain = 0;
chain_ovfl = false;
Index: tree-flow.h
===================================================================
*** tree-flow.h (revision 149199)
--- tree-flow.h (working copy)
*************** unsigned int tree_ssa_unswitch_loops (vo
*** 745,751 ****
unsigned int canonicalize_induction_variables (void);
unsigned int tree_unroll_loops_completely (bool, bool);
unsigned int tree_ssa_prefetch_arrays (void);
- unsigned int remove_empty_loops (void);
void tree_ssa_iv_optimize (void);
unsigned tree_predictive_commoning (void);
tree canonicalize_loop_ivs (struct loop *, htab_t, tree *);
--- 745,750 ----
Index: passes.c
===================================================================
*** passes.c (revision 149199)
--- passes.c (working copy)
*************** init_optimization_passes (void)
*** 651,657 ****
NEXT_PASS (pass_lim);
NEXT_PASS (pass_tree_unswitch);
NEXT_PASS (pass_scev_cprop);
- NEXT_PASS (pass_empty_loop);
NEXT_PASS (pass_record_bounds);
NEXT_PASS (pass_check_data_deps);
NEXT_PASS (pass_loop_distribution);
--- 651,656 ----
More information about the Gcc-patches
mailing list