[PATCH] Fix PR23855

[PATCH] Fix PR23855

[Richard Biener]

For GCC 6 unswitching gained the ability to hoist loop guard checks.
The following extends this to make sure we can hoist multiple guards
(including those that were hoisted from inner loops) - this allows
us to hoist all guards in a three-loop nest completely out of the
nest (the gcc.dg/loop-unswitch-2.c covers this case but had only
two expected hoists).

In the process of this I've removed the virtual SSA rewrite we were
doing per guard hoisting.

Bootstrap and regtest running on x86_64-unknown-linux-gnu (including
the virtual SSA form verifier patch).

I already built SPEC 2k6 for this patch (but w/o the verifier) without
issues, all test runs pass (with -Ofast -march=native on Skylake).

Richard.

2016-08-15  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/23855
	* tree-ssa-loop-unswitch.c: Include tree-ssa-loop-manip.h.
	(tree_unswitch_outer_loop): Iterate find_loop_guard as long as we
	find guards to hoist.  Do not update SSA form but rewrite virtuals
	into loop closed SSA.
	(find_loop_guard): Adjust to skip already hoisted guards.  Do
	not mark virtuals for renaming or update SSA form.

	* gcc.dg/loop-unswitch-2.c: Adjust.

Index: gcc/testsuite/gcc.dg/loop-unswitch-2.c
===================================================================
*** gcc/testsuite/gcc.dg/loop-unswitch-2.c	(revision 239473)
--- gcc/testsuite/gcc.dg/loop-unswitch-2.c	(working copy)
*************** void foo (float **a, float **b, float *c
*** 11,15 ****
  	c[i] += a[i][k] * b[k][j];
  }
  
! /* { dg-final { scan-tree-dump-times "guard hoisted" 2 "unswitch" } } */
  
--- 11,15 ----
  	c[i] += a[i][k] * b[k][j];
  }
  
! /* { dg-final { scan-tree-dump-times "guard hoisted" 3 "unswitch" } } */
  
Index: gcc/tree-ssa-loop-unswitch.c
===================================================================
*** gcc/tree-ssa-loop-unswitch.c	(revision 239478)
--- gcc/tree-ssa-loop-unswitch.c	(working copy)
*************** along with GCC; see the file COPYING3.
*** 37,42 ****
--- 37,43 ----
  #include "tree-inline.h"
  #include "gimple-iterator.h"
  #include "cfghooks.h"
+ #include "tree-ssa-loop-manip.h"
  
  /* This file implements the loop unswitching, i.e. transformation of loops like
  
*************** tree_unswitch_outer_loop (struct loop *l
*** 451,464 ****
        return false;
      }
  
!   guard = find_loop_guard (loop);
!   if (guard)
      {
        hoist_guard (loop, guard);
!       update_ssa (TODO_update_ssa);
!       return true;
      }
!   return false;
  }
  
  /* Checks if the body of the LOOP is within an invariant guard.  If this
--- 452,466 ----
        return false;
      }
  
!   bool changed = false;
!   while ((guard = find_loop_guard (loop)))
      {
+       if (! changed)
+ 	rewrite_virtuals_into_loop_closed_ssa (loop);
        hoist_guard (loop, guard);
!       changed = true;
      }
!   return changed;
  }
  
  /* Checks if the body of the LOOP is within an invariant guard.  If this
*************** find_loop_guard (struct loop *loop)
*** 501,513 ****
  	b) anything defined in something1, something2 and something3
  	   is not used outside of the loop.  */
  
!   while (single_succ_p (header))
!     header = single_succ (header);
!   if (!last_stmt (header)
!       || gimple_code (last_stmt (header)) != GIMPLE_COND)
!     return NULL;
! 
!   extract_true_false_edges_from_block (header, &te, &fe);
    if (!flow_bb_inside_loop_p (loop, te->dest)
        || !flow_bb_inside_loop_p (loop, fe->dest))
      return NULL;
--- 503,530 ----
  	b) anything defined in something1, something2 and something3
  	   is not used outside of the loop.  */
  
!   gcond *cond;
!   do
!     {
!       if (single_succ_p (header))
! 	header = single_succ (header);
!       else
! 	{
! 	  cond = dyn_cast <gcond *> (last_stmt (header));
! 	  if (! cond)
! 	    return NULL;
! 	  extract_true_false_edges_from_block (header, &te, &fe);
! 	  /* Make sure to skip earlier hoisted guards that are left
! 	     in place as if (true).  */
! 	  if (gimple_cond_true_p (cond))
! 	    header = te->dest;
! 	  else if (gimple_cond_false_p (cond))
! 	    header = fe->dest;
! 	  else
! 	    break;
! 	}
!     }
!   while (1);
    if (!flow_bb_inside_loop_p (loop, te->dest)
        || !flow_bb_inside_loop_p (loop, fe->dest))
      return NULL;
*************** find_loop_guard (struct loop *loop)
*** 549,555 ****
  	     guard_edge->src->index, guard_edge->dest->index, loop->num);
    /* Check if condition operands do not have definitions inside loop since
       any bb copying is not performed.  */
!   FOR_EACH_SSA_TREE_OPERAND (use, last_stmt (header), iter, SSA_OP_USE)
      {
        gimple *def = SSA_NAME_DEF_STMT (use);
        basic_block def_bb = gimple_bb (def);
--- 566,572 ----
  	     guard_edge->src->index, guard_edge->dest->index, loop->num);
    /* Check if condition operands do not have definitions inside loop since
       any bb copying is not performed.  */
!   FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
      {
        gimple *def = SSA_NAME_DEF_STMT (use);
        basic_block def_bb = gimple_bb (def);
*************** hoist_guard (struct loop *loop, edge gua
*** 762,769 ****
  	}
      }
  
-   mark_virtual_operands_for_renaming (cfun);
-   update_ssa (TODO_update_ssa);
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "  guard hoisted.\n");
  }
--- 779,784 ----