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]

Re: [PATCH] Unswitching fixes (PR middle-end/43866)


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
> 
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex


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