From 8feba6612e24a14434021be5f4982506b7d7d250 Mon Sep 17 00:00:00 2001 From: rakdver Date: Mon, 11 Jul 2005 23:59:17 +0000 Subject: [PATCH] * tree-flow.h (remove_empty_loops, single_dom_exit): Declare. * passes.c (init_optimization_passes): Add pass_empty_loop. * tree-pass.h (pass_empty_loop): Declare. * tree-ssa-loop-ivcanon.c (empty_loop_p, remove_empty_loop, try_remove_empty_loop, remove_empty_loops): New functions. * tree-ssa-loop-ivopts.c (single_dom_exit): Export. * tree-ssa-loop.c (tree_ssa_empty_loop, pass_empty_loop): New. * gcc.dg/tree-ssa/loop-10.c: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@101901 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 10 +++ gcc/passes.c | 1 + gcc/testsuite/ChangeLog | 4 + gcc/testsuite/gcc.dg/tree-ssa/loop-10.c | 32 +++++++ gcc/tree-flow.h | 2 + gcc/tree-pass.h | 1 + gcc/tree-ssa-loop-ivcanon.c | 152 ++++++++++++++++++++++++++++++++ gcc/tree-ssa-loop-ivopts.c | 2 +- gcc/tree-ssa-loop.c | 28 ++++++ 9 files changed, 231 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-10.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index afe196e6202..cc62635be33 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2005-07-12 Zdenek Dvorak + + * tree-flow.h (remove_empty_loops, single_dom_exit): Declare. + * passes.c (init_optimization_passes): Add pass_empty_loop. + * tree-pass.h (pass_empty_loop): Declare. + * tree-ssa-loop-ivcanon.c (empty_loop_p, remove_empty_loop, + try_remove_empty_loop, remove_empty_loops): New functions. + * tree-ssa-loop-ivopts.c (single_dom_exit): Export. + * tree-ssa-loop.c (tree_ssa_empty_loop, pass_empty_loop): New. + 2005-07-12 Peter Barada PR middle-end/16719 diff --git a/gcc/passes.c b/gcc/passes.c index 04c60a5b006..1356dc171a8 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -554,6 +554,7 @@ init_optimization_passes (void) NEXT_PASS (pass_lim); NEXT_PASS (pass_unswitch); NEXT_PASS (pass_scev_cprop); + NEXT_PASS (pass_empty_loop); NEXT_PASS (pass_record_bounds); NEXT_PASS (pass_linear_transform); NEXT_PASS (pass_iv_canon); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 174c6793b13..2a0a5f8eb00 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2005-07-12 Zdenek Dvorak + + * gcc.dg/tree-ssa/loop-10.c: New test. + 2005-07-11 Kazu Hirata * gcc.c-torture/execute/20020720-1.x: Remove. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-10.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-10.c new file mode 100644 index 00000000000..6a0f94d880f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-10.c @@ -0,0 +1,32 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-vars" } */ + +int bar (void); + +void foo (void) +{ + unsigned i, j, n; + + for (i = 0; i < 100000; i++) + ; + + n = bar (); + for (i = 0; i < n; i++) + ; + + for (i = 0; i < n; i++) + for (j = 0; j < n; j++) + ; + + /* These should not be removed. */ + for (i = 0; i < 10000; i++) + bar (); + + for (i = 0; i != n; i += 2) + ; +} + +/* { dg-final { scan-tree-dump-times "if " 3 "vars" } } */ +/* { dg-final { scan-tree-dump-times "bar " 2 "vars" } } */ + +/* { dg-final { cleanup-tree-dump "vars" } } */ diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index c28de1c8ab5..e45793033f8 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -688,6 +688,7 @@ void tree_ssa_lim (struct loops *); void tree_ssa_unswitch_loops (struct loops *); void canonicalize_induction_variables (struct loops *); void tree_unroll_loops_completely (struct loops *, bool); +void remove_empty_loops (struct loops *); void tree_ssa_iv_optimize (struct loops *); bool number_of_iterations_exit (struct loop *, edge, @@ -719,6 +720,7 @@ struct loop *tree_ssa_loop_version (struct loops *, struct loop *, tree, basic_block *); tree expand_simple_operations (tree); void substitute_in_loop_info (struct loop *, tree, tree); +edge single_dom_exit (struct loop *); /* In tree-ssa-loop-im.c */ /* The possibilities of statement movement. */ diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index d420b1b1714..92d52bda0b3 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -228,6 +228,7 @@ extern struct tree_opt_pass pass_lim; extern struct tree_opt_pass pass_unswitch; extern struct tree_opt_pass pass_iv_canon; extern struct tree_opt_pass pass_scev_cprop; +extern struct tree_opt_pass pass_empty_loop; extern struct tree_opt_pass pass_record_bounds; extern struct tree_opt_pass pass_if_conversion; extern struct tree_opt_pass pass_vectorize; diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index f4f44759f9b..4d02baabd2d 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -371,3 +371,155 @@ tree_unroll_loops_completely (struct loops *loops, bool may_increase_size) if (changed) cleanup_tree_cfg_loop (); } + +/* Checks whether LOOP is empty. */ + +static bool +empty_loop_p (struct loop *loop) +{ + edge exit; + struct tree_niter_desc niter; + tree phi, def; + basic_block *body; + block_stmt_iterator bsi; + unsigned i; + tree stmt; + + /* 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 (!number_of_iterations_exit (loop, exit, &niter)) + return false; + + /* Values of all loop exit phi nodes must be invariants. */ + for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) + { + 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 (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) + || stmt_ann (stmt)->has_volatile_ops) + { + 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 (TREE_CODE (stmt)) + { + case RETURN_EXPR: + case MODIFY_EXPR: + stmt = get_call_expr_in (stmt); + if (!stmt) + break; + + case CALL_EXPR: + if (TREE_SIDE_EFFECTS (stmt)) + { + free (body); + return false; + } + break; + + case ASM_EXPR: + /* We cannot remove volatile assembler. */ + if (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); + tree cond_stmt = last_stmt (exit->src); + tree do_exit; + + if (exit->flags & EDGE_TRUE_VALUE) + do_exit = boolean_true_node; + else + do_exit = boolean_false_node; + + COND_EXPR_COND (cond_stmt) = do_exit; + update_stmt (cond_stmt); +} + +/* 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. */ + +void +remove_empty_loops (struct loops *loops) +{ + bool changed = false; + struct loop *loop; + + for (loop = loops->tree_root->inner; loop; loop = loop->next) + try_remove_empty_loop (loop, &changed); + + if (changed) + { + scev_reset (); + cleanup_tree_cfg_loop (); + } +} diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 8e6b8c168d4..84c68abad9c 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -358,7 +358,7 @@ loop_data (struct loop *loop) /* The single loop exit if it dominates the latch, NULL otherwise. */ -static edge +edge single_dom_exit (struct loop *loop) { edge exit = loop->single_exit; diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index aa99920f88b..1e7d73b8885 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -311,6 +311,34 @@ struct tree_opt_pass pass_scev_cprop = 0 /* letter */ }; +/* Remove empty loops. */ + +static void +tree_ssa_empty_loop (void) +{ + if (!current_loops) + return; + + remove_empty_loops (current_loops); +} + +struct tree_opt_pass pass_empty_loop = +{ + "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_flags_finish */ + 0 /* letter */ +}; + /* Record bounds on numbers of iterations of loops. */ static void -- 2.11.4.GIT