aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gcc/ChangeLog10
-rw-r--r--gcc/passes.c1
-rw-r--r--gcc/testsuite/ChangeLog4
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/loop-10.c32
-rw-r--r--gcc/tree-flow.h2
-rw-r--r--gcc/tree-pass.h1
-rw-r--r--gcc/tree-ssa-loop-ivcanon.c152
-rw-r--r--gcc/tree-ssa-loop-ivopts.c2
-rw-r--r--gcc/tree-ssa-loop.c28
9 files changed, 231 insertions, 1 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index afe196e..cc62635 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2005-07-12 Zdenek Dvorak <dvorakz@suse.cz>
+
+ * 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 <peter@the-baradas.com>
PR middle-end/16719
diff --git a/gcc/passes.c b/gcc/passes.c
index 04c60a5..1356dc1 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 174c679..2a0a5f8 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2005-07-12 Zdenek Dvorak <dvorakz@suse.cz>
+
+ * gcc.dg/tree-ssa/loop-10.c: New test.
+
2005-07-11 Kazu Hirata <kazu@codesourcery.com>
* 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 0000000..6a0f94d
--- /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 c28de1c8..e457930 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 d420b1b..92d52bd 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 f4f4475..4d02baa 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 8e6b8c1..84c68ab 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 aa99920..1e7d73b 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
generated by cgit v1.1 at 2024-10-07 11:19:59 +0000