OSDN Git Service

* tree-flow.h (remove_empty_loops, single_dom_exit): Declare.
authorrakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 11 Jul 2005 23:59:17 +0000 (23:59 +0000)
committerrakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 11 Jul 2005 23:59:17 +0000 (23:59 +0000)
* 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
gcc/passes.c
gcc/testsuite/ChangeLog
gcc/testsuite/gcc.dg/tree-ssa/loop-10.c [new file with mode: 0644]
gcc/tree-flow.h
gcc/tree-pass.h
gcc/tree-ssa-loop-ivcanon.c
gcc/tree-ssa-loop-ivopts.c
gcc/tree-ssa-loop.c

index afe196e..cc62635 100644 (file)
@@ -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
index 04c60a5..1356dc1 100644 (file)
@@ -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);
index 174c679..2a0a5f8 100644 (file)
@@ -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 (file)
index 0000000..6a0f94d
--- /dev/null
@@ -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" } } */
index c28de1c..e457930 100644 (file)
@@ -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.  */
index d420b1b..92d52bd 100644 (file)
@@ -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;
index f4f4475..4d02baa 100644 (file)
@@ -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 ();
+    }
+}
index 8e6b8c1..84c68ab 100644 (file)
@@ -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;
index aa99920..1e7d73b 100644 (file)
@@ -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