PR tree-optimization/42906

	* tree-ssa-dce.c (mark_control_dependent_edges_necessary): Add IGNORE_SELF
	argument; set visited_control_parents for fully processed BBs.
	(find_obviously_necessary_stmts): Update call of
	mark_control_dependent_edges_necessary.
	(propagate_necessity): Likewise; handle PHI edges more curefully.

	* gcc.dg/tree-ssa/dce-1.c: New testcase.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@158004 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 77af22c..a05b595 100644 (file)
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2010-04-06  Jan Hubicka  <jh@suse.czpli
+
+       PR tree-optimization/42906
+
+       * tree-ssa-dce.c (mark_control_dependent_edges_necessary): Add IGNORE_SELF
+       argument; set visited_control_parents for fully processed BBs.
+       (find_obviously_necessary_stmts): Update call of
+       mark_control_dependent_edges_necessary.
+       (propagate_necessity): Likewise; handle PHI edges more curefully.
+

 2010-04-06  Uros Bizjak  <ubizjak@gmail.com>
 
        * config/i386/i386.md: Remove comment about 'e' and 'E'
 2010-04-06  Uros Bizjak  <ubizjak@gmail.com>
 
        * config/i386/i386.md: Remove comment about 'e' and 'E'

diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index e6fc3c0..22f8934 100644 (file)
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2010-04-06  Jan Hubicka  <jh@suse.czpli
+
+       PR tree-optimization/42906
+       * gcc.dg/tree-ssa/dce-1.c: New testcase.
+

 2010-04-06  Tobias Burnus  <burnus@net-b.de>
 
        PR fortran/43178
 2010-04-06  Tobias Burnus  <burnus@net-b.de>
 
        PR fortran/43178

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c b/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c
new file mode 100644 (file)
index 0000000..12612e5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cddce1" } */
+int foo (int b, int j)
+{
+  if (b)
+    {
+      int i;
+      for (i = 0; i<1000; ++i)
+        ;
+      j = 0;
+    }
+  return j;
+}
+/* Check that empty loop is eliminated in this case.  We should no longer have
+   the exit condition after the loop.  */
+/* { dg-final { scan-tree-dump-not "999" "cddce1"} } */
+/* { dg-final { scan-tree-dump-not "1000" "cddce1"} } */
+/* { dg-final { cleanup-tree-dump "cddce1" } } */
+

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index f54511c..a1f1c71 100644 (file)
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -373,12 +373,15 @@ mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
 
 /* Make corresponding control dependent edges necessary.  We only
    have to do this once for each basic block, so we clear the bitmap
 
 /* Make corresponding control dependent edges necessary.  We only
    have to do this once for each basic block, so we clear the bitmap

-   after we're done.  */
+   after we're done.
+
+   When IGNORE_SELF it true, ignore BB from the list of control dependences.  */

 static void
 static void

-mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
+mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, bool ignore_self)

 {
   bitmap_iterator bi;
   unsigned edge_number;
 {
   bitmap_iterator bi;
   unsigned edge_number;

+  bool skipped = false;

 
   gcc_assert (bb != EXIT_BLOCK_PTR);
 
 
   gcc_assert (bb != EXIT_BLOCK_PTR);
 


@@ -390,6 +393,12 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
       gimple stmt;
       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 
       gimple stmt;
       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 

+      if (ignore_self && cd_bb == bb)
+       {
+         skipped = true;
+         continue;
+       }
+

       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
        continue;
       SET_BIT (last_stmt_necessary, cd_bb->index);
       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
        continue;
       SET_BIT (last_stmt_necessary, cd_bb->index);


@@ -399,6 +408,8 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
       if (stmt && is_ctrl_stmt (stmt))
        mark_stmt_necessary (stmt, true);
     }
       if (stmt && is_ctrl_stmt (stmt))
        mark_stmt_necessary (stmt, true);
     }

+  if (!skipped)
+    SET_BIT (visited_control_parents, bb->index);

 }
 
 
 }
 
 


@@ -459,7 +470,7 @@ find_obviously_necessary_stmts (struct edge_list *el)
                  if (dump_file)
                    fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
                             e->src->index, e->dest->index);
                  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);
+                 mark_control_dependent_edges_necessary (e->dest, el, false);

                }
          }
 
                }
          }
 


@@ -468,7 +479,7 @@ find_obviously_necessary_stmts (struct edge_list *el)
          {
            if (dump_file)
              fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
          {
            if (dump_file)
              fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);

-           mark_control_dependent_edges_necessary (loop->latch, el);
+           mark_control_dependent_edges_necessary (loop->latch, el, false);

          }
       scev_finalize ();
     }
          }
       scev_finalize ();
     }


@@ -653,10 +664,7 @@ propagate_necessity (struct edge_list *el)
          basic_block bb = gimple_bb (stmt);
          if (bb != ENTRY_BLOCK_PTR
              && ! TEST_BIT (visited_control_parents, bb->index))
          basic_block bb = gimple_bb (stmt);
          if (bb != ENTRY_BLOCK_PTR
              && ! TEST_BIT (visited_control_parents, bb->index))

-           {
-             SET_BIT (visited_control_parents, bb->index);
-             mark_control_dependent_edges_necessary (bb, el);
-           }
+           mark_control_dependent_edges_necessary (bb, el, false);

        }
 
       if (gimple_code (stmt) == GIMPLE_PHI
        }
 
       if (gimple_code (stmt) == GIMPLE_PHI


@@ -679,17 +687,98 @@ propagate_necessity (struct edge_list *el)
                mark_operand_necessary (arg);
            }
 
                mark_operand_necessary (arg);
            }
 

+         /* For PHI operands it matters from where the control flow arrives
+            to the BB.  Consider the following example:
+
+            a=exp1;
+            b=exp2;
+            if (test)
+               ;
+            else
+               ;
+            c=PHI(a,b)
+
+            We need to mark control dependence of the empty basic blocks, since they
+            contains computation of PHI operands.
+
+            Doing so is too restrictive in the case the predecestor block is in
+            the loop. Consider:
+
+             if (b)
+               {
+                 int i;
+                 for (i = 0; i<1000; ++i)
+                   ;
+                 j = 0;
+               }
+             return j;
+
+            There is PHI for J in the BB containing return statement.
+            In this case the control dependence of predecestor block (that is
+            within the empty loop) also contains the block determining number
+            of iterations of the block that would prevent removing of empty
+            loop in this case.
+
+            This scenario can be avoided by splitting critical edges.
+            To save the critical edge splitting pass we identify how the control
+            dependence would look like if the edge was split.
+
+            Consider the modified CFG created from current CFG by splitting
+            edge B->C.  In the postdominance tree of modified CFG, C' is
+            always child of C.  There are two cases how chlids of C' can look
+            like:
+
+               1) C' is leaf
+
+                  In this case the only basic block C' is control dependent on is B.
+
+               2) C' has single child that is B
+
+                  In this case control dependence of C' is same as control
+                  dependence of B in original CFG except for block B itself.
+                  (since C' postdominate B in modified CFG)
+
+            Now how to decide what case happens?  There are two basic options:
+
+               a) C postdominate B.  Then C immediately postdominate B and
+                  case 2 happens iff there is no other way from B to C except
+                  the edge B->C.
+
+                  There is other way from B to C iff there is succesor of B that
+                  is not postdominated by B.  Testing this condition is somewhat
+                  expensive, because we need to iterate all succesors of B.
+                  We are safe to assume that this does not happen: we will mark B
+                  as needed when processing the other path from B to C that is
+                  conrol dependent on B and marking control dependencies of B
+                  itself is harmless because they will be processed anyway after
+                  processing control statement in B.
+
+               b) C does not postdominate B.  Always case 1 happens since there is
+                  path from C to exit that does not go through B and thus also C'.  */
+

          if (aggressive && !degenerate_phi_p (stmt))
            {
              for (k = 0; k < gimple_phi_num_args (stmt); k++)
                {
                  basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
          if (aggressive && !degenerate_phi_p (stmt))
            {
              for (k = 0; k < gimple_phi_num_args (stmt); k++)
                {
                  basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;

-                 if (arg_bb != ENTRY_BLOCK_PTR
-                     && ! TEST_BIT (visited_control_parents, arg_bb->index))
+
+                 if (gimple_bb (stmt)
+                     != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))

                    {
                    {

-                     SET_BIT (visited_control_parents, arg_bb->index);
-                     mark_control_dependent_edges_necessary (arg_bb, el);
+                     if (!TEST_BIT (last_stmt_necessary, arg_bb->index))
+                       {
+                         gimple stmt2;
+                         SET_BIT (last_stmt_necessary, arg_bb->index);
+                         SET_BIT (bb_contains_live_stmts, arg_bb->index);
+
+                         stmt2 = last_stmt (arg_bb);
+                         if (stmt2 && is_ctrl_stmt (stmt2))
+                           mark_stmt_necessary (stmt2, true);
+                       }

                    }
                    }

+                 else if (arg_bb != ENTRY_BLOCK_PTR
+                          && ! TEST_BIT (visited_control_parents, arg_bb->index))
+                   mark_control_dependent_edges_necessary (arg_bb, el, true);

                }
            }
        }
                }
            }
        }