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] Improve condition elimination in simple loop analysis


Hello,

as noted by Pat Haugen, some conditions that could be eliminated in the
simple loop recognition are not.  This patch fixes it by

1) Handling A < B implies A + 1 <= B in implies_p.
2) Handling comparisons with mode bounds in
   simplify_const_relational_operation.

Bootstrapped & regtested on ppc.

Zdenek

(the patch includes the previous patch
http://gcc.gnu.org/ml/gcc-patches/2004-05/msg00497.html, only the new
parts are mentioned in the changelog).

	* loop-iv.c (implies_p): Handle A < B ==> A + 1 <= B.
	* simplify-rtx.c (simplify_const_relational_operation): Optimize
	comparisons with mode bounds.

Index: loop-iv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-iv.c,v
retrieving revision 2.7
diff -c -3 -p -r2.7 loop-iv.c
*** loop-iv.c	18 Mar 2004 16:42:31 -0000	2.7
--- loop-iv.c	11 May 2004 22:29:02 -0000
*************** determine_max_iter (struct niter_desc *d
*** 1203,1209 ****
  	}
      }
  
!   get_mode_bounds (desc->mode, desc->signed_p, &mmin, &mmax);
    nmax = INTVAL (mmax) - INTVAL (mmin);
  
    if (GET_CODE (niter) == UDIV)
--- 1203,1209 ----
  	}
      }
  
!   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
    nmax = INTVAL (mmax) - INTVAL (mmin);
  
    if (GET_CODE (niter) == UDIV)
*************** simplify_using_assignment (rtx insn, rtx
*** 1354,1360 ****
  static bool
  implies_p (rtx a, rtx b)
  {
!   rtx op0, op1, r;
  
    if (GET_CODE (a) == EQ)
      {
--- 1354,1361 ----
  static bool
  implies_p (rtx a, rtx b)
  {
!   rtx op0, op1, opb0, opb1, r;
!   enum machine_mode mode;
  
    if (GET_CODE (a) == EQ)
      {
*************** implies_p (rtx a, rtx b)
*** 1376,1381 ****
--- 1377,1423 ----
  	}
      }
  
+   /* A < B implies A + 1 <= B.  */
+   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
+       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
+     {
+       op0 = XEXP (a, 0);
+       op1 = XEXP (a, 1);
+       opb0 = XEXP (b, 0);
+       opb1 = XEXP (b, 1);
+ 
+       if (GET_CODE (a) == GT)
+ 	{
+ 	  r = op0;
+ 	  op0 = op1;
+ 	  op1 = r;
+ 	}
+ 
+       if (GET_CODE (b) == GE)
+ 	{
+ 	  r = opb0;
+ 	  opb0 = opb1;
+ 	  opb1 = r;
+ 	}
+ 
+       mode = GET_MODE (op0);
+       if (mode != GET_MODE (opb0))
+ 	mode = VOIDmode;
+       else if (mode != VOIDmode)
+ 	;
+       else
+ 	{
+ 	  mode = GET_MODE (op1);
+ 	  if (mode != GET_MODE (opb1))
+ 	    mode = VOIDmode;
+ 	}
+ 
+       if (mode != VOIDmode
+ 	  && rtx_equal_p (op1, opb1)
+ 	  && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
+ 	return true;
+     }
+ 
    return false;
  }
  
*************** shorten_into_mode (struct rtx_iv *iv, en
*** 1696,1702 ****
  {
    rtx mmin, mmax, cond_over, cond_under;
  
!   get_mode_bounds (mode, signed_p, &mmin, &mmax);
    cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
  					iv->base, mmin);
    cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
--- 1738,1744 ----
  {
    rtx mmin, mmax, cond_over, cond_under;
  
!   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
    cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
  					iv->base, mmin);
    cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
*************** iv_number_of_iterations (struct loop *lo
*** 1873,1879 ****
    rtx assumption;
    enum rtx_code cond;
    enum machine_mode mode, comp_mode;
!   rtx mmin, mmax;
    unsigned HOST_WIDEST_INT s, size, d;
    HOST_WIDEST_INT up, down, inc;
    int was_sharp = false;
--- 1915,1921 ----
    rtx assumption;
    enum rtx_code cond;
    enum machine_mode mode, comp_mode;
!   rtx mmin, mmax, mode_mmin, mode_mmax;
    unsigned HOST_WIDEST_INT s, size, d;
    HOST_WIDEST_INT up, down, inc;
    int was_sharp = false;
*************** iv_number_of_iterations (struct loop *lo
*** 1959,1965 ****
    comp_mode = iv0.extend_mode;
    mode = iv0.mode;
    size = GET_MODE_BITSIZE (mode);
!   get_mode_bounds (mode, (cond == LE || cond == LT), &mmin, &mmax);
  
    if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
      goto fail;
--- 2001,2009 ----
    comp_mode = iv0.extend_mode;
    mode = iv0.mode;
    size = GET_MODE_BITSIZE (mode);
!   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
!   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
!   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
  
    if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
      goto fail;
*************** iv_number_of_iterations (struct loop *lo
*** 2001,2007 ****
  	if (iv0.step == const0_rtx)
  	  {
  	    tmp = lowpart_subreg (mode, iv0.base, comp_mode);
! 	    assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mmax);
  	    if (assumption == const_true_rtx)
  	      goto zero_iter;
  	    iv0.base = simplify_gen_binary (PLUS, comp_mode,
--- 2045,2052 ----
  	if (iv0.step == const0_rtx)
  	  {
  	    tmp = lowpart_subreg (mode, iv0.base, comp_mode);
! 	    assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
! 						  mode_mmax);
  	    if (assumption == const_true_rtx)
  	      goto zero_iter;
  	    iv0.base = simplify_gen_binary (PLUS, comp_mode,
*************** iv_number_of_iterations (struct loop *lo
*** 2010,2016 ****
  	else
  	  {
  	    tmp = lowpart_subreg (mode, iv1.base, comp_mode);
! 	    assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mmin);
  	    if (assumption == const_true_rtx)
  	      goto zero_iter;
  	    iv1.base = simplify_gen_binary (PLUS, comp_mode,
--- 2055,2062 ----
  	else
  	  {
  	    tmp = lowpart_subreg (mode, iv1.base, comp_mode);
! 	    assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
! 						  mode_mmin);
  	    if (assumption == const_true_rtx)
  	      goto zero_iter;
  	    iv1.base = simplify_gen_binary (PLUS, comp_mode,
*************** iv_number_of_iterations (struct loop *lo
*** 2035,2041 ****
        if (iv0.step == const0_rtx)
  	{
  	  tmp = lowpart_subreg (mode, iv0.base, comp_mode);
! 	  if (rtx_equal_p (tmp, mmin))
  	    {
  	      desc->infinite =
  		      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
--- 2081,2087 ----
        if (iv0.step == const0_rtx)
  	{
  	  tmp = lowpart_subreg (mode, iv0.base, comp_mode);
! 	  if (rtx_equal_p (tmp, mode_mmin))
  	    {
  	      desc->infinite =
  		      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
*************** iv_number_of_iterations (struct loop *lo
*** 2045,2051 ****
        else
  	{
  	  tmp = lowpart_subreg (mode, iv1.base, comp_mode);
! 	  if (rtx_equal_p (tmp, mmax))
  	    {
  	      desc->infinite =
  		      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
--- 2091,2097 ----
        else
  	{
  	  tmp = lowpart_subreg (mode, iv1.base, comp_mode);
! 	  if (rtx_equal_p (tmp, mode_mmax))
  	    {
  	      desc->infinite =
  		      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
*************** iv_number_of_iterations (struct loop *lo
*** 2122,2129 ****
  	  if (GET_CODE (iv1.base) == CONST_INT)
  	    up = INTVAL (iv1.base);
  	  else
! 	    up = INTVAL (mmax) - inc;
! 	  down = INTVAL (GET_CODE (iv0.base) == CONST_INT ? iv0.base : mmin);
  	  desc->niter_max = (up - down) / inc + 1;
  
  	  if (iv0.step == const0_rtx)
--- 2168,2177 ----
  	  if (GET_CODE (iv1.base) == CONST_INT)
  	    up = INTVAL (iv1.base);
  	  else
! 	    up = INTVAL (mode_mmax) - inc;
! 	  down = INTVAL (GET_CODE (iv0.base) == CONST_INT
! 			 ? iv0.base
! 			 : mode_mmin);
  	  desc->niter_max = (up - down) / inc + 1;
  
  	  if (iv0.step == const0_rtx)
*************** iv_number_of_iterations (struct loop *lo
*** 2204,2210 ****
  	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
  	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
  
! 	  bound = simplify_gen_binary (MINUS, mode, mmax, step);
  	  assumption = simplify_gen_relational (cond, SImode, mode,
  						tmp1, bound);
  	  desc->assumptions =
--- 2252,2259 ----
  	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
  	  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 =
*************** iv_number_of_iterations (struct loop *lo
*** 2227,2233 ****
  	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
  	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
  
! 	  bound = simplify_gen_binary (MINUS, mode, mmin, step);
  	  assumption = simplify_gen_relational (cond, SImode, mode,
  						bound, tmp0);
  	  desc->assumptions =
--- 2276,2283 ----
  	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
  	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
  
! 	  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 =
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.470
diff -c -3 -p -r1.470 rtl.h
*** rtl.h	3 May 2004 01:27:55 -0000	1.470
--- rtl.h	11 May 2004 22:29:02 -0000
*************** extern void tracer (void);
*** 2462,2468 ****
  extern void variable_tracking_main (void);
  
  /* In stor-layout.c.  */
! extern void get_mode_bounds (enum machine_mode, int, rtx *, rtx *);
  
  /* In loop-unswitch.c  */
  extern rtx reversed_condition (rtx);
--- 2462,2469 ----
  extern void variable_tracking_main (void);
  
  /* In stor-layout.c.  */
! extern void get_mode_bounds (enum machine_mode, int, enum machine_mode,
! 			     rtx *, rtx *);
  
  /* In loop-unswitch.c  */
  extern rtx reversed_condition (rtx);
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.189
diff -c -3 -p -r1.189 simplify-rtx.c
*** simplify-rtx.c	1 May 2004 09:36:55 -0000	1.189
--- simplify-rtx.c	11 May 2004 22:29:02 -0000
*************** simplify_const_relational_operation (enu
*** 2892,2897 ****
--- 2892,2954 ----
    /* Otherwise, there are some code-specific tests we can make.  */
    else
      {
+       /* Optimize comparisons with upper and lower bounds.  */
+       if (INTEGRAL_MODE_P (mode)
+ 	  && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
+ 	{
+ 	  rtx mmin, mmax;
+ 	  int sign;
+ 
+ 	  if (code == GEU
+ 	      || code == LEU
+ 	      || code == GTU
+ 	      || code == LTU)
+ 	    sign = 0;
+ 	  else
+ 	    sign = 1;
+ 
+ 	  get_mode_bounds (mode, sign, mode, &mmin, &mmax);
+ 
+ 	  tem = NULL_RTX;
+ 	  switch (code)
+ 	    {
+ 	    case GEU:
+ 	    case GE:
+ 	      /* x >= min is always true.  */
+ 	      if (rtx_equal_p (trueop1, mmin))
+ 		tem = const_true_rtx;
+ 	      else 
+ 	      break;
+ 
+ 	    case LEU:
+ 	    case LE:
+ 	      /* x <= max is always true.  */
+ 	      if (rtx_equal_p (trueop1, mmax))
+ 		tem = const_true_rtx;
+ 	      break;
+ 
+ 	    case GTU:
+ 	    case GT:
+ 	      /* x > max is always false.  */
+ 	      if (rtx_equal_p (trueop1, mmax))
+ 		tem = const0_rtx;
+ 	      break;
+ 
+ 	    case LTU:
+ 	    case LT:
+ 	      /* x < min is always false.  */
+ 	      if (rtx_equal_p (trueop1, mmin))
+ 		tem = const0_rtx;
+ 	      break;
+ 
+ 	    default:
+ 	      break;
+ 	    }
+ 	  if (tem == const0_rtx
+ 	      || tem == const_true_rtx)
+ 	    return tem;
+ 	}
+ 
        switch (code)
  	{
  	case EQ:
*************** simplify_const_relational_operation (enu
*** 2902,2934 ****
  	case NE:
  	  if (trueop1 == const0_rtx && nonzero_address_p (op0))
  	    return const_true_rtx;
- 	  break;
- 
- 	case GEU:
- 	  /* Unsigned values are never negative.  */
- 	  if (trueop1 == const0_rtx)
- 	    return const_true_rtx;
- 	  break;
- 
- 	case LTU:
- 	  if (trueop1 == const0_rtx)
- 	    return const0_rtx;
- 	  break;
- 
- 	case LEU:
- 	  /* Unsigned values are never greater than the largest
- 	     unsigned value.  */
- 	  if (GET_CODE (trueop1) == CONST_INT
- 	      && (unsigned HOST_WIDE_INT) INTVAL (trueop1) == GET_MODE_MASK (mode)
- 	    && INTEGRAL_MODE_P (mode))
- 	  return const_true_rtx;
- 	  break;
- 
- 	case GTU:
- 	  if (GET_CODE (trueop1) == CONST_INT
- 	      && (unsigned HOST_WIDE_INT) INTVAL (trueop1) == GET_MODE_MASK (mode)
- 	      && INTEGRAL_MODE_P (mode))
- 	    return const0_rtx;
  	  break;
  
  	case LT:
--- 2959,2964 ----
Index: stor-layout.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stor-layout.c,v
retrieving revision 1.187
diff -c -3 -p -r1.187 stor-layout.c
*** stor-layout.c	19 Apr 2004 18:02:40 -0000	1.187
--- stor-layout.c	11 May 2004 22:29:02 -0000
*************** get_best_mode (int bitsize, int bitpos, 
*** 2156,2181 ****
  }
  
  /* Gets minimal and maximal values for MODE (signed or unsigned depending on
!    SIGN).  */
  
  void
! get_mode_bounds (enum machine_mode mode, int sign, rtx *mmin, rtx *mmax)
  {
!   int size = GET_MODE_BITSIZE (mode);
  
    if (size > HOST_BITS_PER_WIDE_INT)
      abort ();
  
    if (sign)
      {
!       *mmin = GEN_INT (-((unsigned HOST_WIDE_INT) 1 << (size - 1)));
!       *mmax = GEN_INT (((unsigned HOST_WIDE_INT) 1 << (size - 1)) - 1);
      }
    else
      {
!       *mmin = const0_rtx;
!       *mmax = GEN_INT (((unsigned HOST_WIDE_INT) 1 << (size - 1) << 1) - 1);
      }
  }
  
  #include "gt-stor-layout.h"
--- 2156,2187 ----
  }
  
  /* Gets minimal and maximal values for MODE (signed or unsigned depending on
!    SIGN).  The returned constants are made to be usable in TARGET_MODE.  */
  
  void
! get_mode_bounds (enum machine_mode mode, int sign,
! 		 enum machine_mode target_mode,
! 		 rtx *mmin, rtx *mmax)
  {
!   unsigned size = GET_MODE_BITSIZE (mode);
!   unsigned HOST_WIDE_INT min_val, max_val;
  
    if (size > HOST_BITS_PER_WIDE_INT)
      abort ();
  
    if (sign)
      {
!       min_val = -((unsigned HOST_WIDE_INT) 1 << (size - 1));
!       max_val = ((unsigned HOST_WIDE_INT) 1 << (size - 1)) - 1;
      }
    else
      {
!       min_val = 0;
!       max_val = ((unsigned HOST_WIDE_INT) 1 << (size - 1) << 1) - 1;
      }
+ 
+   *mmin = GEN_INT (trunc_int_for_mode (min_val, target_mode));
+   *mmax = GEN_INT (trunc_int_for_mode (max_val, target_mode));
  }
  
  #include "gt-stor-layout.h"


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