[patch] PR 32283

[Zdenek Dvorak <rakdver at kam dot mff dot cuni dot cz>]

Hi,

the patch below makes us use bdnz for the testcase from comment 20,
again.  While this most likely does not solve the PR in general,
the patch contains fixes for two rather serious-looking missed
optimization issues:

1) scev_probably_wraps_p uses the type of the step of the induction
   variable to decide whether the iv can wrap.  For pointer ivs, this
   is wrong, as the type of the step is sizetype, and we are led to
   believe that the iv might wrap.
2) simplify-rtx.c:simplify_plus_minus may fail before it actually tries
   to simplify the expression, so it may e.g. leave (x+y)-y
   unsimplified.

Other changes in the patch include:

-- a change of the placement of the statements that initialize the new
   bound with that the control variable of the loop is compared.  The
   statements are emitted outside of the loop, which leads to
   a bit less confusing code for the rtl optimizers to consider (and
   also reduces the work done by rtl level invariant motion).
-- changes to loop-iv.c and simplify-rtx.c to enable us to determine
   that ((x << 2) - 4) & 3 == 0.

Bootstrapped & regtested on i686.  I need an approval for the changes
outside of the loop optimizer, i.e., the simplify-rtx.c changes.

Zdenek

	PR rtl-optimization/32283
	* tree-ssa-loop-niter.c (scev_probably_wraps_p): Use type of the base
	of the induction variable to decide whether it may wrap.
	* tree-ssa-loop-ivopts.c (rewrite_use_compare): Emit the initialization
	of the bound before the loop.
	* simplify-rtx.c (simplify_binary_operation_1): Add two simplifications
	regarding AND.
	(simplify_plus_minus): Only fail if no simplification is possible.
	* loop-iv.c (simple_rhs_p): Consider reg + reg and reg << cst simple.

Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 141912)
--- tree-ssa-loop-niter.c	(working copy)
*************** scev_probably_wraps_p (tree base, tree s
*** 3053,3059 ****
  
    /* If we can use the fact that signed and pointer arithmetics does not
       wrap, we are done.  */
!   if (use_overflow_semantics && nowrap_type_p (type))
      return false;
  
    /* To be able to use estimates on number of iterations of the loop,
--- 3053,3059 ----
  
    /* If we can use the fact that signed and pointer arithmetics does not
       wrap, we are done.  */
!   if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
      return false;
  
    /* To be able to use estimates on number of iterations of the loop,
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c	(revision 141912)
--- tree-ssa-loop-ivopts.c	(working copy)
*************** rewrite_use_compare (struct ivopts_data
*** 5323,5333 ****
      {
        tree var = var_at_stmt (data->current_loop, cand, use->stmt);
        tree var_type = TREE_TYPE (var);
  
        compare = iv_elimination_compare (data, use);
        bound = unshare_expr (fold_convert (var_type, bound));
!       op = force_gimple_operand_gsi (&bsi, bound, true, NULL_TREE,
! 				     true, GSI_SAME_STMT);
  
        gimple_cond_set_lhs (use->stmt, var);
        gimple_cond_set_code (use->stmt, compare);
--- 5323,5337 ----
      {
        tree var = var_at_stmt (data->current_loop, cand, use->stmt);
        tree var_type = TREE_TYPE (var);
+       gimple_seq stmts;
  
        compare = iv_elimination_compare (data, use);
        bound = unshare_expr (fold_convert (var_type, bound));
!       op = force_gimple_operand (bound, &stmts, true, NULL_TREE);
!       if (stmts)
! 	gsi_insert_seq_on_edge_immediate (
! 		loop_preheader_edge (data->current_loop),
! 		stmts);
  
        gimple_cond_set_lhs (use->stmt, var);
        gimple_cond_set_code (use->stmt, compare);
Index: simplify-rtx.c
===================================================================
*** simplify-rtx.c	(revision 141912)
--- simplify-rtx.c	(working copy)
*************** simplify_binary_operation_1 (enum rtx_co
*** 2391,2397 ****
  	 ((A & N) + B) & M -> (A + B) & M
  	 Similarly if (N & M) == 0,
  	 ((A | N) + B) & M -> (A + B) & M
! 	 and for - instead of + and/or ^ instead of |.  */
        if (GET_CODE (trueop1) == CONST_INT
  	  && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
  	  && ~INTVAL (trueop1)
--- 2391,2399 ----
  	 ((A & N) + B) & M -> (A + B) & M
  	 Similarly if (N & M) == 0,
  	 ((A | N) + B) & M -> (A + B) & M
! 	 and for - instead of + and/or ^ instead of |.
!          Also, if (N & M) == 0, then
! 	 (A +- N) & M -> A & M.  */
        if (GET_CODE (trueop1) == CONST_INT
  	  && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
  	  && ~INTVAL (trueop1)
*************** simplify_binary_operation_1 (enum rtx_co
*** 2404,2409 ****
--- 2406,2415 ----
  	  pmop[0] = XEXP (op0, 0);
  	  pmop[1] = XEXP (op0, 1);
  
+ 	  if (GET_CODE (pmop[1]) == CONST_INT
+ 	      && (INTVAL (pmop[1]) & INTVAL (trueop1)) == 0)
+ 	    return simplify_gen_binary (AND, mode, pmop[0], op1);
+ 
  	  for (which = 0; which < 2; which++)
  	    {
  	      tem = pmop[which];
*************** simplify_binary_operation_1 (enum rtx_co
*** 2434,2439 ****
--- 2440,2459 ----
  	    }
  	}
  
+       /* If N and M are constants, transform
+ 	 (X << N) & M -> (X << N) & ((M >> N) << N).  */
+       if (GET_CODE (op1) == CONST_INT
+ 	  && GET_CODE (op0) == ASHIFT
+ 	  && GET_CODE (XEXP (op0, 1)) == CONST_INT)
+ 	{
+ 	  HOST_WIDE_INT n = INTVAL (XEXP (op0, 1));
+ 	  HOST_WIDE_INT m = INTVAL (op1), new_m = (m >> n) << n;
+ 
+ 	  if (m != new_m)
+ 	    return simplify_gen_binary (AND, mode, op0,
+ 					gen_int_mode (new_m, mode));
+ 	}
+ 
        /* (and X (ior (not X) Y) -> (and X Y) */
        if (GET_CODE (op1) == IOR
  	  && GET_CODE (XEXP (op1, 0)) == NOT
*************** simplify_plus_minus (enum rtx_code code,
*** 3591,3600 ****
            ops[j + 1] = save;
          }
  
-       /* This is only useful the first time through.  */
-       if (!canonicalized)
-         return NULL_RTX;
- 
        changed = 0;
        for (i = n_ops - 1; i > 0; i--)
  	for (j = i - 1; j >= 0; j--)
--- 3611,3616 ----
*************** simplify_plus_minus (enum rtx_code code,
*** 3650,3659 ****
--- 3666,3680 ----
  		    ops[i].neg = lneg;
  		    ops[j].op = NULL_RTX;
  		    changed = 1;
+ 		    canonicalized = 1;
  		  }
  	      }
  	  }
  
+       /* If nothing changed, fail.  */
+       if (!canonicalized)
+         return NULL_RTX;
+ 
        /* Pack all the operands to the lower-numbered entries.  */
        for (i = 0, j = 0; j < n_ops; j++)
          if (ops[j].op)
Index: loop-iv.c
===================================================================
*** loop-iv.c	(revision 141912)
--- loop-iv.c	(working copy)
*************** simple_rhs_p (rtx rhs)
*** 1337,1349 ****
      case MINUS:
        op0 = XEXP (rhs, 0);
        op1 = XEXP (rhs, 1);
!       /* Allow reg + const sets only.  */
!       if (REG_P (op0) && !HARD_REGISTER_P (op0) && CONSTANT_P (op1))
! 	return true;
!       if (REG_P (op1) && !HARD_REGISTER_P (op1) && CONSTANT_P (op0))
! 	return true;
  
!       return false;
  
      default:
        return false;
--- 1337,1362 ----
      case MINUS:
        op0 = XEXP (rhs, 0);
        op1 = XEXP (rhs, 1);
!       /* Allow reg + const and reg + reg.  */
!       if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
! 	  && !CONSTANT_P (op0))
! 	return false;
!       if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
! 	  && !CONSTANT_P (op1))
! 	return false;
  
!       return true;
! 
!     case ASHIFT:
!       op0 = XEXP (rhs, 0);
!       op1 = XEXP (rhs, 1);
!       /* Allow reg << const.  */
!       if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
! 	return false;
!       if (!CONSTANT_P (op1))
! 	return false;
! 
!       return true;
  
      default:
        return false;