Multiple fixes: PRs 14692, 15274 and 15463

	PR c++/15463
	* loop-iv.c (iv_number_of_iterations):  Use trunc_int_for_mode on
	result of inverse.

	PR rtl-optimization/15274
	* loop-iv.c (determine_max_iter, shorten_into_mode,
	iv_number_of_iterations): Handle constants correctly.
	* rtl.h (get_mode_bounds): Declaration changed.
	* stor-layout.c (get_mode_bounds): Return a constant suitable for
	the target mode.

	PR rtl-optimization/14692
	* loop-unswitch.c (may_unswitch_on): Try folding the result.
	(unswitch_single_loop): Work correctly when may_unswitch_on
	returns a folded constant.

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

	* function.c (struct temp_slot): Add new field prev.
	(free_after_compilation, init_temp_slots): Free new fields.
	(cut_slot_from_list, insert_slot_to_list,
	temp_slots_at_level, max_slot_level, move_slot_to_level,
	make_slot_available): New functions.
	(assign_stack_temp_for_type, combine_temp_slots,
	find_temp_slot_from_address, preserve_temp_slots,
	preserve_rtl_expr_result, free_temp_slots,
	free_temps_for_rtl_expr, pop_temp_slots): Work with
	the new structure of lists.
	(mark_all_temps_used): Removed.
	* function.h (struct function): Field x_temp_slots
	replaced by x_used_temp_slots and x_avail_temp_slots.
	(temp_slots): Replaced by ...
	(used_temp_slots, avail_temp_slots): New.
	* tree.h (mark_all_temps_used): Declaration removed.

	* loop-iv.c (mark_single_set, get_biv_step_1, iv_analyze,
	simplify_using_assignment): Take the expression out of
	the expr_list wrapper.

	* loop-iv.c (iv_number_of_iterations): Improve clasification of
	infinite loops.

From-SVN: r82028

1 files changed, 97 insertions, 23 deletions

diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index face41d..0e416c4 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -254,7 +254,9 @@ mark_single_set (rtx insn, rtx set)
   unsigned regno, uid;
 
   src = find_reg_equal_equiv_note (insn);
-  if (!src)
+  if (src)
+    src = XEXP (src, 0);
+  else
     src = SET_SRC (set);
 
   if (!simple_set_p (SET_DEST (set), src))
@@ -603,7 +605,9 @@ get_biv_step_1 (rtx insn, rtx reg,
 
   set = single_set (insn);
   rhs = find_reg_equal_equiv_note (insn);
-  if (!rhs)
+  if (rhs)
+    rhs = XEXP (rhs, 0);
+  else
     rhs = SET_SRC (set);
   lhs = SET_DEST (set);
 
@@ -979,7 +983,9 @@ iv_analyze (rtx insn, rtx def, struct rtx_iv *iv)
 
   set = single_set (insn);
   rhs = find_reg_equal_equiv_note (insn);
-  if (!rhs)
+  if (rhs)
+    rhs = XEXP (rhs, 0);
+  else
     rhs = SET_SRC (set);
   code = GET_CODE (rhs);
 
@@ -1203,7 +1209,7 @@ determine_max_iter (struct niter_desc *desc)
 	}
     }
 
-  get_mode_bounds (desc->mode, desc->signed_p, &mmin, &mmax);
+  get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
   nmax = INTVAL (mmax) - INTVAL (mmin);
 
   if (GET_CODE (niter) == UDIV)
@@ -1337,7 +1343,9 @@ simplify_using_assignment (rtx insn, rtx *expr, regset altered)
     return;
 
   rhs = find_reg_equal_equiv_note (insn);
-  if (!rhs)
+  if (rhs)
+    rhs = XEXP (rhs, 0);
+  else
     rhs = SET_SRC (set);
 
   if (!simple_rhs_p (rhs))
@@ -1354,7 +1362,8 @@ simplify_using_assignment (rtx insn, rtx *expr, regset altered)
 static bool
 implies_p (rtx a, rtx b)
 {
-  rtx op0, op1, r;
+  rtx op0, op1, opb0, opb1, r;
+  enum machine_mode mode;
 
   if (GET_CODE (a) == EQ)
     {
@@ -1376,6 +1385,45 @@ implies_p (rtx a, rtx b)
 	}
     }
 
+  /* 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)
+	{
+	  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;
 }
 
@@ -1696,7 +1744,7 @@ shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
 {
   rtx mmin, mmax, cond_over, cond_under;
 
-  get_mode_bounds (mode, signed_p, &mmin, &mmax);
+  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,
@@ -1870,11 +1918,11 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 {
   rtx op0, op1, delta, step, bound, may_xform, def_insn, tmp, tmp0, tmp1;
   struct rtx_iv iv0, iv1, tmp_iv;
-  rtx assumption;
+  rtx assumption, may_not_xform;
   enum rtx_code cond;
   enum machine_mode mode, comp_mode;
-  rtx mmin, mmax;
-  unsigned HOST_WIDEST_INT s, size, d;
+  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;
 
@@ -1959,7 +2007,9 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
   comp_mode = iv0.extend_mode;
   mode = iv0.mode;
   size = GET_MODE_BITSIZE (mode);
-  get_mode_bounds (mode, (cond == LE || cond == LT), &mmin, &mmax);
+  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;
@@ -2001,7 +2051,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	if (iv0.step == const0_rtx)
 	  {
 	    tmp = lowpart_subreg (mode, iv0.base, comp_mode);
-	    assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mmax);
+	    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,
@@ -2010,7 +2061,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	else
 	  {
 	    tmp = lowpart_subreg (mode, iv1.base, comp_mode);
-	    assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mmin);
+	    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,
@@ -2035,7 +2087,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       if (iv0.step == const0_rtx)
 	{
 	  tmp = lowpart_subreg (mode, iv0.base, comp_mode);
-	  if (rtx_equal_p (tmp, mmin))
+	  if (rtx_equal_p (tmp, mode_mmin))
 	    {
 	      desc->infinite =
 		      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
@@ -2045,7 +2097,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       else
 	{
 	  tmp = lowpart_subreg (mode, iv1.base, comp_mode);
-	  if (rtx_equal_p (tmp, mmax))
+	  if (rtx_equal_p (tmp, mode_mmax))
 	    {
 	      desc->infinite =
 		      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
@@ -2070,6 +2122,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       delta = lowpart_subreg (mode, delta, comp_mode);
       delta = simplify_gen_binary (UMOD, mode, delta, step);
       may_xform = const0_rtx;
+      may_not_xform = const_true_rtx;
 
       if (GET_CODE (delta) == CONST_INT)
 	{
@@ -2094,6 +2147,9 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	      tmp = lowpart_subreg (mode, iv0.base, comp_mode);
 	      may_xform = simplify_gen_relational (cond, SImode, mode,
 						   bound, tmp);
+	      may_not_xform = simplify_gen_relational (reverse_condition (cond),
+						       SImode, mode,
+						       bound, tmp);
 	    }
 	  else
 	    {
@@ -2103,6 +2159,9 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	      tmp = lowpart_subreg (mode, iv1.base, comp_mode);
 	      may_xform = simplify_gen_relational (cond, SImode, mode,
 						   tmp, bound);
+	      may_not_xform = simplify_gen_relational (reverse_condition (cond),
+						       SImode, mode,
+						       tmp, bound);
 	    }
 	}
 
@@ -2112,8 +2171,18 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	     completely senseless.  This is OK, as we would need this assumption
 	     to determine the number of iterations anyway.  */
 	  if (may_xform != const_true_rtx)
-	    desc->assumptions = alloc_EXPR_LIST (0, may_xform,
-						 desc->assumptions);
+	    {
+	      /* 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
+		desc->assumptions = alloc_EXPR_LIST (0, may_xform,
+						     desc->assumptions);
+	    }
 
 	  /* We are going to lose some information about upper bound on
 	     number of iterations in this step, so record the information
@@ -2122,8 +2191,10 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	  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);
+	    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)
@@ -2186,8 +2257,9 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
 
       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
-      tmp = simplify_gen_binary (MULT, mode,
-				 tmp, GEN_INT (inverse (s, size)));
+      inv = inverse (s, size);
+      inv = trunc_int_for_mode (inv, mode);
+      tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
     }
   else
@@ -2204,7 +2276,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
 	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
 
-	  bound = simplify_gen_binary (MINUS, mode, mmax, step);
+	  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 =
@@ -2227,7 +2300,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 	  tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
 	  tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
 
-	  bound = simplify_gen_binary (MINUS, mode, mmin, step);
+	  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 =