This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] Do not remove (potentially) infinite loops


Hello,

as discussed in the mailing list, dce should not remove inifinite loops.
This patch prevents it. It actually prevents removing of empty loops at
all since the means to recognize the finite ones are not available in
the branch; I will prepare something slightly more clever for lno
branch.

It also fixes bogus testcase gcc.dg/tree-ssa/20040211-1.c where we were
actually verifying that we behave incorrectly.

Bootstrapped & regtested on i686.

Zdenek

	* tree-ssa-dce.c (find_obviously_necessary_stmts,
	perform_tree_ssa_dce): Do not remove loops.

	* gcc.dg/tree-ssa/20040211-1.c: Update outcome.
	* gcc.dg/tree-ssa/ssa-dce-3.c: New test.

Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.83
diff -c -3 -p -r1.1.2.83 tree-ssa-dce.c
*** tree-ssa-dce.c	11 Mar 2004 05:07:18 -0000	1.1.2.83
--- tree-ssa-dce.c	20 Mar 2004 09:45:25 -0000
*************** static inline void mark_operand_necessar
*** 109,115 ****
  
  static bool need_to_preserve_store (tree);
  static void mark_stmt_if_obviously_necessary (tree, bool);
! static void find_obviously_necessary_stmts (bool);
  
  static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
  static void propagate_necessity (struct edge_list *);
--- 109,115 ----
  
  static bool need_to_preserve_store (tree);
  static void mark_stmt_if_obviously_necessary (tree, bool);
! static void find_obviously_necessary_stmts (struct edge_list *);
  
  static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
  static void propagate_necessity (struct edge_list *);
*************** mark_stmt_if_obviously_necessary (tree s
*** 404,417 ****
  /* Find obviously necessary statements.  These are things like most function
     calls, and stores to file level variables.
  
!    If AGGRESSIVE is false, control statements are conservatively marked as
!    necessary.  */
  
  static void
! find_obviously_necessary_stmts (bool aggressive)
  {
    basic_block bb;
    block_stmt_iterator i;
  
    FOR_EACH_BB (bb)
      {
--- 404,419 ----
  /* Find obviously necessary statements.  These are things like most function
     calls, and stores to file level variables.
  
!    If EL is NULL, control statements are conservatively marked as
!    necessary.  Otherwise it contains the list of edges used by control
!    dependence analysis.  */
  
  static void
! find_obviously_necessary_stmts (struct edge_list *el)
  {
    basic_block bb;
    block_stmt_iterator i;
+   edge e;
  
    FOR_EACH_BB (bb)
      {
*************** find_obviously_necessary_stmts (bool agg
*** 438,444 ****
  	{
  	  tree stmt = bsi_stmt (i);
  	  NECESSARY (stmt) = 0;
! 	  mark_stmt_if_obviously_necessary (stmt, aggressive);
  	}
  
        /* Mark this basic block as `not visited'.  A block will be marked
--- 440,446 ----
  	{
  	  tree stmt = bsi_stmt (i);
  	  NECESSARY (stmt) = 0;
! 	  mark_stmt_if_obviously_necessary (stmt, el != NULL);
  	}
  
        /* Mark this basic block as `not visited'.  A block will be marked
*************** find_obviously_necessary_stmts (bool agg
*** 446,451 ****
--- 448,468 ----
  	 marked.  */
        bb->flags &= ~BB_VISITED;
      }
+ 
+   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)
+ 	{
+ 	  for (e = bb->succ; e; e = e->succ_next)
+ 	    if (e->flags & EDGE_DFS_BACK)
+ 	      break;
+ 
+ 	  if (e)
+ 	    mark_control_dependent_edges_necessary (bb, el);
+ 	}
+     }
  }
  
  /* Make corresponding control dependent edges necessary.  We only
*************** perform_tree_ssa_dce (bool aggressive)
*** 818,826 ****
        el = create_edge_list ();
        find_all_control_dependences (el);
        timevar_pop (TV_CONTROL_DEPENDENCES);
      }
  
!   find_obviously_necessary_stmts (aggressive);
  
    propagate_necessity (el);
  
--- 835,845 ----
        el = create_edge_list ();
        find_all_control_dependences (el);
        timevar_pop (TV_CONTROL_DEPENDENCES);
+ 
+       mark_dfs_back_edges ();
      }
  
!   find_obviously_necessary_stmts (el);
  
    propagate_necessity (el);
  
Index: testsuite/gcc.dg/tree-ssa/20040211-1.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/20040211-1.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 20040211-1.c
*** testsuite/gcc.dg/tree-ssa/20040211-1.c	1 Mar 2004 14:41:04 -0000	1.1.2.2
--- testsuite/gcc.dg/tree-ssa/20040211-1.c	20 Mar 2004 09:45:26 -0000
*************** com (rtx insn, int blah)
*** 35,40 ****
      foo ();
  }
  
! /* After cddce we should have no IF statements remaining since this
!    whole function collapses down to a simple return.  */
! /* { dg-final { scan-tree-dump-times "if " 0 "cddce"} } */
--- 35,40 ----
      foo ();
  }
  
! /* Cddce cannot remove possibly infinite loops and there is no way how to
!    determine whether the loop in can_move_up ends.  */
! /* { dg-final { scan-tree-dump "if " "cddce"} } */
Index: testsuite/gcc.dg/tree-ssa/ssa-dce-3.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/ssa-dce-3.c
diff -N testsuite/gcc.dg/tree-ssa/ssa-dce-3.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/ssa-dce-3.c	20 Mar 2004 09:45:26 -0000
***************
*** 0 ****
--- 1,29 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-cddce" } */
+ 
+ int main(void)
+ {
+   unsigned i, j;
+ 
+   for (i = 1, j = 0; i != 0; i+=2)
+     {
+       j += 500;
+       if (j % 7)
+ 	{
+ 	  j++;
+ 	}
+       else
+ 	{
+ 	  j--;
+ 	}
+     }
+ 
+   return 0;
+ }
+ 
+ /* We should eliminate the inner condition, but the loop must be preserved
+    as it is infinite.  Therefore there should be just one phi node (for i):  */
+ /* { dg-final { scan-tree-dump-times "PHI " 1 "cddce"} } */
+ 
+ /* And one if (for the exit condition of the loop):  */
+ /* { dg-final { scan-tree-dump-times "if " 1 "cddce"} } */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]