[PATCH] Fix PR71366

[Richard Biener <rguenther at suse dot de>]

The following fixes PR71366, a latent issue in unrolling where removing
found-to-be always not executed edges may cause the parent loop to vanish.
That's something we try to avoid by killing off loops late thus we have
to move removing those edges late as well.  Furthermore this breaks
the way we track outer loops we want to apply constant propagation to
thus this patch re-writes it to track BBs of said outer loops we can
re-discover (to its original parent) after such outer loop vanished.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

The issue looks latent to me but is more easily triggered with the
latest peeling patches.

Richard.

2016-06-01  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/71366
	* tree-ssa-loop-ivopts.c (edges_to_remove): New global.
	(unloop_loops): Move removing edges here ...
	(try_unroll_loop_completely): ... from here.
	(try_peel_loop): ... and here.
	(tree_unroll_loops_completely_1): Track parent loops via
	bitmap of header BBs.
	(tree_unroll_loops_completely): Adjust for that.

	* gcc.dg/torture/pr71366-1.c: New testcase.
	* gcc.dg/torture/pr71366-2.c: Likewise.

Index: gcc/tree-ssa-loop-ivcanon.c
===================================================================
*** gcc/tree-ssa-loop-ivcanon.c	(revision 236977)
--- gcc/tree-ssa-loop-ivcanon.c	(working copy)
*************** remove_redundant_iv_tests (struct loop *
*** 591,599 ****
    return changed;
  }
  
! /* Stores loops that will be unlooped after we process whole loop tree. */
  static vec<loop_p> loops_to_unloop;
  static vec<int> loops_to_unloop_nunroll;
  /* Stores loops that has been peeled.  */
  static bitmap peeled_loops;
  
--- 613,623 ----
    return changed;
  }
  
! /* Stores loops that will be unlooped and edges that will be removed
!    after we process whole loop tree. */
  static vec<loop_p> loops_to_unloop;
  static vec<int> loops_to_unloop_nunroll;
+ static vec<edge> edges_to_remove;
  /* Stores loops that has been peeled.  */
  static bitmap peeled_loops;
  
*************** static void
*** 613,618 ****
--- 637,652 ----
  unloop_loops (bitmap loop_closed_ssa_invalidated,
  	      bool *irred_invalidated)
  {
+   /* First remove edges in peeled copies.  */
+   unsigned i;
+   edge e;
+   FOR_EACH_VEC_ELT (edges_to_remove, i, e)
+     {
+       bool ok = remove_path (e);
+       gcc_assert (ok);
+     }
+   edges_to_remove.release ();
+ 
    while (loops_to_unloop.length ())
      {
        struct loop *loop = loops_to_unloop.pop ();
*************** try_unroll_loop_completely (struct loop
*** 725,734 ****
    if (n_unroll)
      {
        sbitmap wont_exit;
-       edge e;
-       unsigned i;
        bool large;
-       vec<edge> to_remove = vNULL;
        if (ul == UL_SINGLE_ITER)
  	return false;
  
--- 759,765 ----
*************** try_unroll_loop_completely (struct loop
*** 862,868 ****
  
        if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
  						 n_unroll, wont_exit,
! 						 exit, &to_remove,
  						 DLTHE_FLAG_UPDATE_FREQ
  						 | DLTHE_FLAG_COMPLETTE_PEEL))
  	{
--- 893,899 ----
  
        if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
  						 n_unroll, wont_exit,
! 						 exit, &edges_to_remove,
  						 DLTHE_FLAG_UPDATE_FREQ
  						 | DLTHE_FLAG_COMPLETTE_PEEL))
  	{
*************** try_unroll_loop_completely (struct loop
*** 873,890 ****
  	  return false;
  	}
  
-       FOR_EACH_VEC_ELT (to_remove, i, e)
- 	{
- 	  bool ok = remove_path (e);
- 	  gcc_assert (ok);
- 	}
- 
-       to_remove.release ();
        free (wont_exit);
        free_original_copy_tables ();
      }
  
- 
    /* Remove the conditional from the last copy of the loop.  */
    if (edge_to_cancel)
      {
--- 904,913 ----
*************** try_peel_loop (struct loop *loop,
*** 960,968 ****
    struct loop_size size;
    int peeled_size;
    sbitmap wont_exit;
-   unsigned i;
-   vec<edge> to_remove = vNULL;
-   edge e;
  
    if (!flag_peel_loops || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0
        || !peeled_loops)
--- 983,988 ----
*************** try_peel_loop (struct loop *loop,
*** 1052,1069 ****
      }
    if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
  					     npeel, wont_exit,
! 					     exit, &to_remove,
  					     DLTHE_FLAG_UPDATE_FREQ))
      {
        free_original_copy_tables ();
        free (wont_exit);
        return false;
      }
-   FOR_EACH_VEC_ELT (to_remove, i, e)
-     {
-       bool ok = remove_path (e);
-       gcc_assert (ok);
-     }
    free (wont_exit);
    free_original_copy_tables ();
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 1072,1084 ----
      }
    if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
  					     npeel, wont_exit,
! 					     exit, &edges_to_remove,
  					     DLTHE_FLAG_UPDATE_FREQ))
      {
        free_original_copy_tables ();
        free (wont_exit);
        return false;
      }
    free (wont_exit);
    free_original_copy_tables ();
    if (dump_file && (dump_flags & TDF_DETAILS))
*************** propagate_constants_for_unrolling (basic
*** 1299,1306 ****
  
  static bool
  tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
! 				vec<loop_p, va_heap>& father_stack,
! 				struct loop *loop)
  {
    struct loop *loop_father;
    bool changed = false;
--- 1314,1320 ----
  
  static bool
  tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
! 				bitmap father_bbs, struct loop *loop)
  {
    struct loop *loop_father;
    bool changed = false;
*************** tree_unroll_loops_completely_1 (bool may
*** 1310,1316 ****
    /* Process inner loops first.  */
    for (inner = loop->inner; inner != NULL; inner = inner->next)
      changed |= tree_unroll_loops_completely_1 (may_increase_size,
! 					       unroll_outer, father_stack,
  					       inner);
   
    /* If we changed an inner loop we cannot process outer loops in this
--- 1324,1330 ----
    /* Process inner loops first.  */
    for (inner = loop->inner; inner != NULL; inner = inner->next)
      changed |= tree_unroll_loops_completely_1 (may_increase_size,
! 					       unroll_outer, father_bbs,
  					       inner);
   
    /* If we changed an inner loop we cannot process outer loops in this
*************** tree_unroll_loops_completely_1 (bool may
*** 1344,1354 ****
  	 within the new basic blocks to fold away induction variable
  	 computations; otherwise, the size might blow up before the
  	 iteration is complete and the IR eventually cleaned up.  */
!       if (loop_outer (loop_father) && !loop_father->aux)
! 	{
! 	  father_stack.safe_push (loop_father);
! 	  loop_father->aux = loop_father;
! 	}
  
        return true;
      }
--- 1358,1365 ----
  	 within the new basic blocks to fold away induction variable
  	 computations; otherwise, the size might blow up before the
  	 iteration is complete and the IR eventually cleaned up.  */
!       if (loop_outer (loop_father))
! 	bitmap_set_bit (father_bbs, loop_father->header->index);
  
        return true;
      }
*************** tree_unroll_loops_completely_1 (bool may
*** 1363,1369 ****
  unsigned int
  tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
  {
!   auto_vec<loop_p, 16> father_stack;
    bool changed;
    int iteration = 0;
    bool irred_invalidated = false;
--- 1374,1380 ----
  unsigned int
  tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
  {
!   bitmap father_bbs = BITMAP_ALLOC (NULL);
    bool changed;
    int iteration = 0;
    bool irred_invalidated = false;
*************** tree_unroll_loops_completely (bool may_i
*** 1380,1399 ****
        estimate_numbers_of_iterations ();
  
        changed = tree_unroll_loops_completely_1 (may_increase_size,
! 						unroll_outer, father_stack,
  						current_loops->tree_root);
        if (changed)
  	{
- 	  struct loop **iter;
  	  unsigned i;
  
- 	  /* Be sure to skip unlooped loops while procesing father_stack
- 	     array.  */
- 	  FOR_EACH_VEC_ELT (loops_to_unloop, i, iter)
- 	    (*iter)->aux = NULL;
- 	  FOR_EACH_VEC_ELT (father_stack, i, iter)
- 	    if (!(*iter)->aux)
- 	      *iter = NULL;
            unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
  
  	  /* We can not use TODO_update_ssa_no_phi because VOPS gets confused.  */
--- 1391,1402 ----
        estimate_numbers_of_iterations ();
  
        changed = tree_unroll_loops_completely_1 (may_increase_size,
! 						unroll_outer, father_bbs,
  						current_loops->tree_root);
        if (changed)
  	{
  	  unsigned i;
  
            unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
  
  	  /* We can not use TODO_update_ssa_no_phi because VOPS gets confused.  */
*************** tree_unroll_loops_completely (bool may_i
*** 1404,1421 ****
  	  else
  	    update_ssa (TODO_update_ssa);
  
  	  /* Propagate the constants within the new basic blocks.  */
! 	  FOR_EACH_VEC_ELT (father_stack, i, iter)
! 	    if (*iter)
! 	      {
! 		unsigned j;
! 		basic_block *body = get_loop_body_in_dom_order (*iter);
! 		for (j = 0; j < (*iter)->num_nodes; j++)
! 		  propagate_constants_for_unrolling (body[j]);
! 		free (body);
! 		(*iter)->aux = NULL;
! 	      }
! 	  father_stack.truncate (0);
  
  	  /* This will take care of removing completely unrolled loops
  	     from the loop structures so we can continue unrolling now
--- 1407,1436 ----
  	  else
  	    update_ssa (TODO_update_ssa);
  
+ 	  /* father_bbs is a bitmap of loop father header BB indices.
+ 	     Translate that to what non-root loops these BBs belong to now.  */
+ 	  bitmap_iterator bi;
+ 	  bitmap fathers = BITMAP_ALLOC (NULL);
+ 	  EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
+ 	    {
+ 	      basic_block unrolled_loop_bb = BASIC_BLOCK_FOR_FN (cfun, i);
+ 	      if (! unrolled_loop_bb)
+ 		continue;
+ 	      if (loop_outer (unrolled_loop_bb->loop_father))
+ 		bitmap_set_bit (fathers,
+ 				unrolled_loop_bb->loop_father->num);
+ 	    }
+ 	  bitmap_clear (father_bbs);
  	  /* Propagate the constants within the new basic blocks.  */
! 	  EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
! 	    {
! 	      loop_p father = get_loop (cfun, i);
! 	      basic_block *body = get_loop_body_in_dom_order (father);
! 	      for (unsigned j = 0; j < father->num_nodes; j++)
! 		propagate_constants_for_unrolling (body[j]);
! 	      free (body);
! 	    }
! 	  BITMAP_FREE (fathers);
  
  	  /* This will take care of removing completely unrolled loops
  	     from the loop structures so we can continue unrolling now
*************** tree_unroll_loops_completely (bool may_i
*** 1435,1441 ****
    while (changed
  	 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
  
!   father_stack.release ();
  
    if (irred_invalidated
        && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
--- 1450,1456 ----
    while (changed
  	 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
  
!   BITMAP_FREE (father_bbs);
  
    if (irred_invalidated
        && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
Index: gcc/testsuite/gcc.dg/torture/pr71366-1.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr71366-1.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr71366-1.c	(working copy)
***************
*** 0 ****
--- 1,23 ----
+ /* { dg-do compile } */
+ 
+ int a[1][2], b, c;
+ 
+ int
+ fn1 ()
+ { 
+   int d;
+   for (; c;)
+     for (d = 2; d >= 0;)
+       { 
+ 	int e[4], f = e[3];
+ 	if (f)
+ 	  return b;
+ 	d--;
+ 	for (;;)
+ 	  { 
+ 	    c = a[0][d];
+ 	    break;
+ 	  }
+       }
+   return 0;
+ }
Index: gcc/testsuite/gcc.dg/torture/pr71366-2.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr71366-2.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr71366-2.c	(working copy)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ 
+ char a[1];
+ int b;
+ void fn1()
+ {
+   int i;
+   for (;;)
+     {
+       i = 0;
+       for (; i < 6; i++)
+ 	{
+ 	  if (b)
+ 	    for (;;)
+ 	      ;
+ 	  int c = a[i];
+ 	  __builtin_printf("", i);
+ 	}
+     }
+ }