Unswitching fixes (PR middle-end/43866)

Hi!

This patch fixes a couple of problems in tree-ssa-loop-unswitch.c.

The first problem is in tree_may_unswitch_on - a tuplification error.
Result of build2 (cond_code, ...) is never integer_zerop nor
integer_nonzerop.  While we could fold, we can just test for the canonical
true/false conditions using gimple_cond* predicates.

Another problem is that when hitting --param max-unswitch-level nesting
level we wouldn't adjust the conditions.  Some further pass probably would
do so, but when we already have the code to handle it, it is IMHO better to
do it right away.  When hitting the max level we just won't consider any new
conditions for unswitching.

The last issue is that there is no cfg cleanup in between the unswitching
levels, which means we often choose conditions that are never tested
in any reachable bb in the loop.  Instead of doing cfg cleanup and updating
everything, this patch just does a quick discovery of reachable bbs in the
loop (which takes into account the modified conditions) and doesn't consider
conditions that aren't reachable.

Bootstrapped/regtested on x86_64-linux and i686-linux.  Ok for trunk?

2010-06-25  Jakub Jelinek  <jakub@redhat.com>

	PR middle-end/43866
	* tree-ssa-loop-unswitch.c (tree_may_unswitch_on): If stmt is always
	true or always false, return NULL_TREE.
	(tree_unswitch_single_loop): Optimize conditions even when reaching
	max-unswitch-level parameter.  If num > 0, optimize first all conditions
	using entry checks, then do still reachable block discovery and consider
	only conditions in still reachable basic blocks in the loop.

	* gfortran.dg/pr43866.f90: New test.


	Jakub

On Fri, 25 Jun 2010, Jakub Jelinek wrote:

> Hi!
> 
> This patch fixes a couple of problems in tree-ssa-loop-unswitch.c.
> 
> The first problem is in tree_may_unswitch_on - a tuplification error.
> Result of build2 (cond_code, ...) is never integer_zerop nor
> integer_nonzerop.  While we could fold, we can just test for the canonical
> true/false conditions using gimple_cond* predicates.
> 
> Another problem is that when hitting --param max-unswitch-level nesting
> level we wouldn't adjust the conditions.  Some further pass probably would
> do so, but when we already have the code to handle it, it is IMHO better to
> do it right away.  When hitting the max level we just won't consider any new
> conditions for unswitching.
> 
> The last issue is that there is no cfg cleanup in between the unswitching
> levels, which means we often choose conditions that are never tested
> in any reachable bb in the loop.  Instead of doing cfg cleanup and updating
> everything, this patch just does a quick discovery of reachable bbs in the
> loop (which takes into account the modified conditions) and doesn't consider
> conditions that aren't reachable.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux.  Ok for trunk?

Ok.

Thanks,
Richard.

> 2010-06-25  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR middle-end/43866
> 	* tree-ssa-loop-unswitch.c (tree_may_unswitch_on): If stmt is always
> 	true or always false, return NULL_TREE.
> 	(tree_unswitch_single_loop): Optimize conditions even when reaching
> 	max-unswitch-level parameter.  If num > 0, optimize first all conditions
> 	using entry checks, then do still reachable block discovery and consider
> 	only conditions in still reachable basic blocks in the loop.
> 
> 	* gfortran.dg/pr43866.f90: New test.
> 
> --- gcc/tree-ssa-loop-unswitch.c.jj	2010-06-07 11:25:05.000000000 +0200
> +++ gcc/tree-ssa-loop-unswitch.c	2010-06-24 17:25:09.000000000 +0200
> @@ -129,6 +129,12 @@ tree_may_unswitch_on (basic_block bb, st
>    if (!stmt || gimple_code (stmt) != GIMPLE_COND)
>      return NULL_TREE;
>  
> +  /* To keep the things simple, we do not directly remove the conditions,
> +     but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
> +     loop where we would unswitch again on such a condition.  */
> +  if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
> +    return NULL_TREE;
> +
>    /* Condition must be invariant.  */
>    FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
>      {
> @@ -142,12 +148,6 @@ tree_may_unswitch_on (basic_block bb, st
>    cond = build2 (gimple_cond_code (stmt), boolean_type_node,
>  		 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
>  
> -  /* To keep the things simple, we do not directly remove the conditions,
> -     but just replace tests with 0/1.  Prevent the infinite loop where we
> -     would unswitch again on such a condition.  */
> -  if (integer_zerop (cond) || integer_nonzerop (cond))
> -    return NULL_TREE;
> -
>    return cond;
>  }
>  
> @@ -193,21 +193,14 @@ tree_unswitch_single_loop (struct loop *
>  {
>    basic_block *bbs;
>    struct loop *nloop;
> -  unsigned i;
> +  unsigned i, found;
>    tree cond = NULL_TREE;
>    gimple stmt;
>    bool changed = false;
>  
> -  /* Do not unswitch too much.  */
> -  if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
> -    {
> -      if (dump_file && (dump_flags & TDF_DETAILS))
> -	fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
> -      return false;
> -    }
> -
>    i = 0;
>    bbs = get_loop_body (loop);
> +  found = loop->num_nodes;
>  
>    while (1)
>      {
> @@ -218,8 +211,17 @@ tree_unswitch_single_loop (struct loop *
>  
>        if (i == loop->num_nodes)
>  	{
> -	  free (bbs);
> -	  return changed;
> +	  if (dump_file
> +	      && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
> +	      && (dump_flags & TDF_DETAILS))
> +	    fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
> +
> +	  if (found == loop->num_nodes)
> +	    {
> +	      free (bbs);
> +	      return changed;
> +	    }
> +	  break;
>  	}
>  
>        cond = simplify_using_entry_checks (loop, cond);
> @@ -236,19 +238,107 @@ tree_unswitch_single_loop (struct loop *
>  	  gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
>  	  changed = true;
>  	}
> +      /* Do not unswitch too much.  */
> +      else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
> +	{
> +	  i++;
> +	  continue;
> +	}
> +      /* In nested tree_unswitch_single_loop first optimize all conditions
> +	 using entry checks, then discover still reachable blocks in the
> +	 loop and find the condition only among those still reachable bbs.  */
> +      else if (num != 0)
> +	{
> +	  if (found == loop->num_nodes)
> +	    found = i;
> +	  i++;
> +	  continue;
> +	}
>        else
> -	break;
> +	{
> +	  found = i;
> +	  break;
> +	}
>  
>        update_stmt (stmt);
>        i++;
>      }
>  
> +  if (num != 0)
> +    {
> +      basic_block *tos, *worklist;
> +
> +      /* When called recursively, first do a quick discovery
> +	 of reachable bbs after the above changes and only
> +	 consider conditions in still reachable bbs.  */
> +      tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
> +
> +      for (i = 0; i < loop->num_nodes; i++)
> +	bbs[i]->flags &= ~BB_REACHABLE;
> +
> +      /* Start with marking header.  */
> +      *tos++ = bbs[0];
> +      bbs[0]->flags |= BB_REACHABLE;
> +
> +      /* Iterate: find everything reachable from what we've already seen
> +	 within the same innermost loop.  Don't look through false edges
> +	 if condition is always true or true edges if condition is
> +	 always false.  */
> +      while (tos != worklist)
> +	{
> +	  basic_block b = *--tos;
> +	  edge e;
> +	  edge_iterator ei;
> +	  int flags = 0;
> +
> +	  if (EDGE_COUNT (b->succs) == 2)
> +	    {
> +	      gimple stmt = last_stmt (b);
> +	      if (stmt
> +		  && gimple_code (stmt) == GIMPLE_COND)
> +		{
> +		  if (gimple_cond_true_p (stmt))
> +		    flags = EDGE_FALSE_VALUE;
> +		  else if (gimple_cond_false_p (stmt))
> +		    flags = EDGE_TRUE_VALUE;
> +		}
> +	    }
> +
> +	  FOR_EACH_EDGE (e, ei, b->succs)
> +	    {
> +	      basic_block dest = e->dest;
> +
> +	      if (dest->loop_father == loop
> +		  && !(dest->flags & BB_REACHABLE)
> +		  && !(e->flags & flags))
> +		{
> +		  *tos++ = dest;
> +		  dest->flags |= BB_REACHABLE;
> +		}
> +	    }
> +	}
> +
> +      free (worklist);
> +
> +      /* Find a bb to unswitch on.  */
> +      for (; found < loop->num_nodes; found++)
> +	if ((bbs[found]->flags & BB_REACHABLE)
> +	    && (cond = tree_may_unswitch_on (bbs[found], loop)))
> +	  break;
> +
> +      if (found == loop->num_nodes)
> +	{
> +	  free (bbs);
> +	  return changed;
> +	}
> +    }
> +
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      fprintf (dump_file, ";; Unswitching loop\n");
>  
>    initialize_original_copy_tables ();
>    /* Unswitch the loop on this condition.  */
> -  nloop = tree_unswitch_loop (loop, bbs[i], cond);
> +  nloop = tree_unswitch_loop (loop, bbs[found], cond);
>    if (!nloop)
>      {
>        free_original_copy_tables ();
> --- gcc/testsuite/gfortran.dg/pr43866.f90.jj	2010-06-25 09:51:40.000000000 +0200
> +++ gcc/testsuite/gfortran.dg/pr43866.f90	2010-06-25 09:53:29.000000000 +0200
> @@ -0,0 +1,43 @@
> +! PR middle-end/43866
> +! { dg-do run }
> +! { dg-options "-funswitch-loops -fbounds-check" }
> +
> +MODULE PR43866
> +  IMPLICIT NONE
> +  TYPE TT
> +    REAL(KIND=4), DIMENSION(:,:), POINTER :: A
> +    REAL(KIND=8), DIMENSION(:,:), POINTER :: B
> +  END TYPE
> +CONTAINS
> +  SUBROUTINE FOO(M,X,Y,T)
> +    TYPE(TT), POINTER :: M
> +    INTEGER, INTENT(IN) :: Y, X
> +    INTEGER :: C, D
> +    LOGICAL :: T
> +    REAL(KIND = 4), DIMENSION(:,:), POINTER :: P
> +    REAL(KIND = 8), DIMENSION(:,:), POINTER :: Q
> +
> +    Q => M%B
> +    P => M%A
> +    DO C=1,X
> +      DO D=C+1,Y
> +        IF (T) THEN
> +          P(D,C)=P(C,D)
> +        ELSE
> +          Q(D,C)=Q(C,D)
> +        ENDIF
> +      ENDDO
> +    ENDDO
> +  END SUBROUTINE FOO
> +END MODULE PR43866
> +
> +  USE PR43866
> +  TYPE(TT), POINTER :: Q
> +  INTEGER, PARAMETER :: N=17
> +  ALLOCATE (Q)
> +  ALLOCATE (Q%B(N,N))
> +  Q%B=0
> +  CALL FOO (Q,N,N,.FALSE.)
> +END
> +
> +! { dg-final { cleanup-modules "pr43866" } }
> 
> 	Jakub
> 
>