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]

[patch] for PR19001


Hello,

we fail to unroll loops of type

for (i = a; i < b; i += const)
  ...

The reason is that the # of iterations analysis needs to assume that
b <= max - const + 1, so that it can claim that the number of iterations is
(b - a + const - 1) / const.  This assumption usually cannot be proved using the
information contained in the program, so unrolling cannot occur.

However in the special case that const is a power of two if the overflow occurs,
the loop must be infinite, and therefore unrolling is safe.

This patch makes # of iterations handle this case and record the
appropriate assumptions for infiniteness of the loop instead.

Bootstrapped (with -funroll-loops) & regtested on x86_64 and ppc.

Zdenek

	PR rtl-optimization/19001
	* loop-iv.c (iv_number_of_iterations): Record assumptions for loops
	with power of two step to 'infinite' field.

Index: loop-iv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-iv.c,v
retrieving revision 2.24
diff -c -3 -p -r2.24 loop-iv.c
*** loop-iv.c	25 Nov 2004 09:30:03 -0000	2.24
--- loop-iv.c	15 Dec 2004 00:33:11 -0000
*************** iv_number_of_iterations (struct loop *lo
*** 2017,2025 ****
    enum machine_mode mode, comp_mode;
    rtx mmin, mmax, mode_mmin, mode_mmax;
    unsigned HOST_WIDEST_INT s, size, d, inv;
!   HOST_WIDEST_INT up, down, inc;
    int was_sharp = false;
    rtx old_niter;
  
    /* The meaning of these assumptions is this:
       if !assumptions
--- 2017,2026 ----
    enum machine_mode mode, comp_mode;
    rtx mmin, mmax, mode_mmin, mode_mmax;
    unsigned HOST_WIDEST_INT s, size, d, inv;
!   HOST_WIDEST_INT up, down, inc, step_val;
    int was_sharp = false;
    rtx old_niter;
+   bool step_is_pow2;
  
    /* The meaning of these assumptions is this:
       if !assumptions
*************** iv_number_of_iterations (struct loop *lo
*** 2126,2135 ****
    if (iv0.step == const0_rtx && iv1.step == const0_rtx)
      goto fail;
  
!   /* Ignore loops of while (i-- < 10) type.  */
!   if (cond != NE
!       && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
!     goto fail;
  
    /* Some more condition normalization.  We must record some assumptions
       due to overflows.  */
--- 2127,2152 ----
    if (iv0.step == const0_rtx && iv1.step == const0_rtx)
      goto fail;
  
!   if (cond != NE)
!     {
!       if (iv0.step == const0_rtx)
! 	step_val = -INTVAL (iv1.step);
!       else
! 	step_val = INTVAL (iv1.step);
! 
!       /* Ignore loops of while (i-- < 10) type.  */
!       if (step_val < 0)
! 	goto fail;
! 
!       step_is_pow2 = !(step_val & (step_val - 1));
!     }
!   else
!     {
!       /* We do not care about whether the step is power of two in this
! 	 case.  */
!       step_is_pow2 = false;
!       step_val = 0;
!     }
  
    /* Some more condition normalization.  We must record some assumptions
       due to overflows.  */
*************** iv_number_of_iterations (struct loop *lo
*** 2270,2277 ****
  	      /* If the step is a power of two and the final value we have
  		 computed overflows, the cycle is infinite.  Otherwise it
  		 is nontrivial to compute the number of iterations.  */
! 	      s = INTVAL (step);
! 	      if ((s & (s - 1)) == 0)
  		desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
  						  desc->infinite);
  	      else
--- 2287,2293 ----
  	      /* If the step is a power of two and the final value we have
  		 computed overflows, the cycle is infinite.  Otherwise it
  		 is nontrivial to compute the number of iterations.  */
! 	      if (step_is_pow2)
  		desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
  						  desc->infinite);
  	      else
*************** iv_number_of_iterations (struct loop *lo
*** 2372,2382 ****
  	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
  
  	  bound = simplify_gen_binary (MINUS, mode, mode_mmax,
! 				       lowpart_subreg (mode, step, comp_mode));
! 	  assumption = simplify_gen_relational (cond, SImode, mode,
! 						tmp1, bound);
! 	  desc->assumptions =
! 		  alloc_EXPR_LIST (0, assumption, desc->assumptions);
  
  	  tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
  	  tmp = lowpart_subreg (mode, tmp, comp_mode);
--- 2388,2419 ----
  	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
  
  	  bound = simplify_gen_binary (MINUS, mode, mode_mmax,
! 				       lowpart_subreg (mode, step,
! 						       comp_mode));
! 	  if (step_is_pow2)
! 	    {
! 	      rtx t0, t1;
! 
! 	      /* If s is power of 2, we know that the loop is infinite if
! 		 a % s <= b % s and b + s overflows.  */
! 	      assumption = simplify_gen_relational (reverse_condition (cond),
! 						    SImode, mode,
! 						    tmp1, bound);
! 
! 	      t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
! 	      t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
! 	      tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
! 	      assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
! 	      desc->infinite =
! 		      alloc_EXPR_LIST (0, assumption, desc->infinite);
! 	    }
! 	  else
! 	    {
! 	      assumption = simplify_gen_relational (cond, SImode, mode,
! 						    tmp1, bound);
! 	      desc->assumptions =
! 		      alloc_EXPR_LIST (0, assumption, desc->assumptions);
! 	    }
  
  	  tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
  	  tmp = lowpart_subreg (mode, tmp, comp_mode);
*************** iv_number_of_iterations (struct loop *lo
*** 2397,2406 ****
  
  	  bound = simplify_gen_binary (MINUS, mode, mode_mmin,
  				       lowpart_subreg (mode, step, comp_mode));
! 	  assumption = simplify_gen_relational (cond, SImode, mode,
! 						bound, tmp0);
! 	  desc->assumptions =
! 		  alloc_EXPR_LIST (0, assumption, desc->assumptions);
  
  	  tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
  	  tmp = lowpart_subreg (mode, tmp, comp_mode);
--- 2434,2463 ----
  
  	  bound = simplify_gen_binary (MINUS, mode, mode_mmin,
  				       lowpart_subreg (mode, step, comp_mode));
! 	  if (step_is_pow2)
! 	    {
! 	      rtx t0, t1;
! 
! 	      /* If s is power of 2, we know that the loop is infinite if
! 		 a % s <= b % s and a - s overflows.  */
! 	      assumption = simplify_gen_relational (reverse_condition (cond),
! 						    SImode, mode,
! 						    bound, tmp0);
! 
! 	      t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
! 	      t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
! 	      tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
! 	      assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
! 	      desc->infinite =
! 		      alloc_EXPR_LIST (0, assumption, desc->infinite);
! 	    }
! 	  else
! 	    {
! 	      assumption = simplify_gen_relational (cond, SImode, mode,
! 						    bound, tmp0);
! 	      desc->assumptions =
! 		      alloc_EXPR_LIST (0, assumption, desc->assumptions);
! 	    }
  
  	  tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
  	  tmp = lowpart_subreg (mode, tmp, comp_mode);


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