+ return benefit;
+}
+
+
+/* Free IV structures for LOOP. */
+
+static void
+loop_ivs_free (struct loop *loop)
+{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
+ struct iv_class *iv = ivs->list;
+
+ free (ivs->regs);
+
+ while (iv)
+ {
+ struct iv_class *next = iv->next;
+ struct induction *induction;
+ struct induction *next_induction;
+
+ for (induction = iv->biv; induction; induction = next_induction)
+ {
+ next_induction = induction->next_iv;
+ free (induction);
+ }
+ for (induction = iv->giv; induction; induction = next_induction)
+ {
+ next_induction = induction->next_iv;
+ free (induction);
+ }
+
+ free (iv);
+ iv = next;
+ }
+}
+
+/* Look back before LOOP->START for the insn that sets REG and return
+ the equivalent constant if there is a REG_EQUAL note otherwise just
+ the SET_SRC of REG. */
+
+static rtx
+loop_find_equiv_value (const struct loop *loop, rtx reg)
+{
+ rtx loop_start = loop->start;
+ rtx insn, set;
+ rtx ret;
+
+ ret = reg;
+ for (insn = PREV_INSN (loop_start); insn; insn = PREV_INSN (insn))
+ {
+ if (LABEL_P (insn))
+ break;
+
+ else if (INSN_P (insn) && reg_set_p (reg, insn))
+ {
+ /* We found the last insn before the loop that sets the register.
+ If it sets the entire register, and has a REG_EQUAL note,
+ then use the value of the REG_EQUAL note. */
+ if ((set = single_set (insn))
+ && (SET_DEST (set) == reg))
+ {
+ rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
+
+ /* Only use the REG_EQUAL note if it is a constant.
+ Other things, divide in particular, will cause
+ problems later if we use them. */
+ if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST
+ && CONSTANT_P (XEXP (note, 0)))
+ ret = XEXP (note, 0);
+ else
+ ret = SET_SRC (set);
+
+ /* We cannot do this if it changes between the
+ assignment and loop start though. */
+ if (modified_between_p (ret, insn, loop_start))
+ ret = reg;
+ }
+ break;
+ }
+ }
+ return ret;
+}
+
+/* Find and return register term common to both expressions OP0 and
+ OP1 or NULL_RTX if no such term exists. Each expression must be a
+ REG or a PLUS of a REG. */
+
+static rtx
+find_common_reg_term (rtx op0, rtx op1)
+{
+ if ((REG_P (op0) || GET_CODE (op0) == PLUS)
+ && (REG_P (op1) || GET_CODE (op1) == PLUS))
+ {
+ rtx op00;
+ rtx op01;
+ rtx op10;
+ rtx op11;
+
+ if (GET_CODE (op0) == PLUS)
+ op01 = XEXP (op0, 1), op00 = XEXP (op0, 0);
+ else
+ op01 = const0_rtx, op00 = op0;
+
+ if (GET_CODE (op1) == PLUS)
+ op11 = XEXP (op1, 1), op10 = XEXP (op1, 0);
+ else
+ op11 = const0_rtx, op10 = op1;
+
+ /* Find and return common register term if present. */
+ if (REG_P (op00) && (op00 == op10 || op00 == op11))
+ return op00;
+ else if (REG_P (op01) && (op01 == op10 || op01 == op11))
+ return op01;
+ }
+
+ /* No common register term found. */
+ return NULL_RTX;
+}
+
+/* Determine the loop iterator and calculate the number of loop
+ iterations. Returns the exact number of loop iterations if it can
+ be calculated, otherwise returns zero. */
+
+static unsigned HOST_WIDE_INT
+loop_iterations (struct loop *loop)
+{
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ struct loop_ivs *ivs = LOOP_IVS (loop);
+ rtx comparison, comparison_value;
+ rtx iteration_var, initial_value, increment, final_value;
+ enum rtx_code comparison_code;
+ HOST_WIDE_INT inc;
+ unsigned HOST_WIDE_INT abs_inc;
+ unsigned HOST_WIDE_INT abs_diff;
+ int off_by_one;
+ int increment_dir;
+ int unsigned_p, compare_dir, final_larger;
+ rtx last_loop_insn;
+ struct iv_class *bl;
+
+ loop_info->n_iterations = 0;
+ loop_info->initial_value = 0;
+ loop_info->initial_equiv_value = 0;
+ loop_info->comparison_value = 0;
+ loop_info->final_value = 0;
+ loop_info->final_equiv_value = 0;
+ loop_info->increment = 0;
+ loop_info->iteration_var = 0;
+ loop_info->iv = 0;
+
+ /* We used to use prev_nonnote_insn here, but that fails because it might
+ accidentally get the branch for a contained loop if the branch for this
+ loop was deleted. We can only trust branches immediately before the
+ loop_end. */
+ last_loop_insn = PREV_INSN (loop->end);
+
+ /* ??? We should probably try harder to find the jump insn
+ at the end of the loop. The following code assumes that
+ the last loop insn is a jump to the top of the loop. */
+ if (!JUMP_P (last_loop_insn))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: No final conditional branch found.\n");
+ return 0;
+ }
+
+ /* If there is a more than a single jump to the top of the loop
+ we cannot (easily) determine the iteration count. */
+ if (LABEL_NUSES (JUMP_LABEL (last_loop_insn)) > 1)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Loop has multiple back edges.\n");
+ return 0;
+ }
+
+ /* Find the iteration variable. If the last insn is a conditional
+ branch, and the insn before tests a register value, make that the
+ iteration variable. */
+
+ comparison = get_condition_for_loop (loop, last_loop_insn);
+ if (comparison == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: No final comparison found.\n");
+ return 0;
+ }
+
+ /* ??? Get_condition may switch position of induction variable and
+ invariant register when it canonicalizes the comparison. */
+
+ comparison_code = GET_CODE (comparison);
+ iteration_var = XEXP (comparison, 0);
+ comparison_value = XEXP (comparison, 1);
+
+ if (!REG_P (iteration_var))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Comparison not against register.\n");
+ return 0;
+ }
+
+ /* The only new registers that are created before loop iterations
+ are givs made from biv increments or registers created by
+ load_mems. In the latter case, it is possible that try_copy_prop
+ will propagate a new pseudo into the old iteration register but
+ this will be marked by having the REG_USERVAR_P bit set. */
+
+ gcc_assert ((unsigned) REGNO (iteration_var) < ivs->n_regs
+ || REG_USERVAR_P (iteration_var));
+
+ /* Determine the initial value of the iteration variable, and the amount
+ that it is incremented each loop. Use the tables constructed by
+ the strength reduction pass to calculate these values. */
+
+ /* Clear the result values, in case no answer can be found. */
+ initial_value = 0;
+ increment = 0;
+
+ /* The iteration variable can be either a giv or a biv. Check to see
+ which it is, and compute the variable's initial value, and increment
+ value if possible. */
+
+ /* If this is a new register, can't handle it since we don't have any
+ reg_iv_type entry for it. */
+ if ((unsigned) REGNO (iteration_var) >= ivs->n_regs)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: No reg_iv_type entry for iteration var.\n");
+ return 0;
+ }
+
+ /* Reject iteration variables larger than the host wide int size, since they
+ could result in a number of iterations greater than the range of our
+ `unsigned HOST_WIDE_INT' variable loop_info->n_iterations. */
+ else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
+ > HOST_BITS_PER_WIDE_INT))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Iteration var rejected because mode too large.\n");
+ return 0;
+ }
+ else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Iteration var not an integer.\n");
+ return 0;
+ }
+
+ /* Try swapping the comparison to identify a suitable iv. */
+ if (REG_IV_TYPE (ivs, REGNO (iteration_var)) != BASIC_INDUCT
+ && REG_IV_TYPE (ivs, REGNO (iteration_var)) != GENERAL_INDUCT
+ && REG_P (comparison_value)
+ && REGNO (comparison_value) < ivs->n_regs)
+ {
+ rtx temp = comparison_value;
+ comparison_code = swap_condition (comparison_code);
+ comparison_value = iteration_var;
+ iteration_var = temp;
+ }
+
+ if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
+ {
+ gcc_assert (REGNO (iteration_var) < ivs->n_regs);
+
+ /* Grab initial value, only useful if it is a constant. */
+ bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
+ initial_value = bl->initial_value;
+ if (!bl->biv->always_executed || bl->biv->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Basic induction var not set once in each iteration.\n");
+ return 0;
+ }
+
+ increment = biv_total_increment (bl);
+ }
+ else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
+ {
+ HOST_WIDE_INT offset = 0;
+ struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
+ rtx biv_initial_value;
+
+ gcc_assert (REGNO (v->src_reg) < ivs->n_regs);
+
+ if (!v->always_executed || v->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: General induction var not set once in each iteration.\n");
+ return 0;
+ }
+
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+
+ /* Increment value is mult_val times the increment value of the biv. */
+
+ increment = biv_total_increment (bl);
+ if (increment)
+ {
+ struct induction *biv_inc;
+
+ increment = fold_rtx_mult_add (v->mult_val,
+ extend_value_for_giv (v, increment),
+ const0_rtx, v->mode);
+ /* The caller assumes that one full increment has occurred at the
+ first loop test. But that's not true when the biv is incremented
+ after the giv is set (which is the usual case), e.g.:
+ i = 6; do {;} while (i++ < 9) .
+ Therefore, we bias the initial value by subtracting the amount of
+ the increment that occurs between the giv set and the giv test. */
+ for (biv_inc = bl->biv; biv_inc; biv_inc = biv_inc->next_iv)
+ {
+ if (loop_insn_first_p (v->insn, biv_inc->insn))
+ {
+ if (REG_P (biv_inc->add_val))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Basic induction var add_val is REG %d.\n",
+ REGNO (biv_inc->add_val));
+ return 0;
+ }
+
+ /* If we have already counted it, skip it. */
+ if (biv_inc->same)
+ continue;
+
+ offset -= INTVAL (biv_inc->add_val);
+ }
+ }
+ }
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Giv iterator, initial value bias %ld.\n",
+ (long) offset);
+
+ /* Initial value is mult_val times the biv's initial value plus
+ add_val. Only useful if it is a constant. */
+ biv_initial_value = extend_value_for_giv (v, bl->initial_value);
+ initial_value
+ = fold_rtx_mult_add (v->mult_val,
+ plus_constant (biv_initial_value, offset),
+ v->add_val, v->mode);
+ }
+ else
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Not basic or general induction var.\n");
+ return 0;
+ }
+
+ if (initial_value == 0)
+ return 0;
+
+ unsigned_p = 0;
+ off_by_one = 0;
+ switch (comparison_code)
+ {
+ case LEU:
+ unsigned_p = 1;
+ case LE:
+ compare_dir = 1;
+ off_by_one = 1;
+ break;
+ case GEU:
+ unsigned_p = 1;
+ case GE:
+ compare_dir = -1;
+ off_by_one = -1;
+ break;
+ case EQ:
+ /* Cannot determine loop iterations with this case. */
+ compare_dir = 0;
+ break;
+ case LTU:
+ unsigned_p = 1;
+ case LT:
+ compare_dir = 1;
+ break;
+ case GTU:
+ unsigned_p = 1;
+ case GT:
+ compare_dir = -1;
+ break;
+ case NE:
+ compare_dir = 0;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
+ /* If the comparison value is an invariant register, then try to find
+ its value from the insns before the start of the loop. */
+
+ final_value = comparison_value;
+ if (REG_P (comparison_value)
+ && loop_invariant_p (loop, comparison_value))
+ {
+ final_value = loop_find_equiv_value (loop, comparison_value);
+
+ /* If we don't get an invariant final value, we are better
+ off with the original register. */
+ if (! loop_invariant_p (loop, final_value))
+ final_value = comparison_value;
+ }
+
+ /* Calculate the approximate final value of the induction variable
+ (on the last successful iteration). The exact final value
+ depends on the branch operator, and increment sign. It will be
+ wrong if the iteration variable is not incremented by one each
+ time through the loop and (comparison_value + off_by_one -
+ initial_value) % increment != 0.
+ ??? Note that the final_value may overflow and thus final_larger
+ will be bogus. A potentially infinite loop will be classified
+ as immediate, e.g. for (i = 0x7ffffff0; i <= 0x7fffffff; i++) */
+ if (off_by_one)
+ final_value = plus_constant (final_value, off_by_one);
+
+ /* Save the calculated values describing this loop's bounds, in case
+ precondition_loop_p will need them later. These values can not be
+ recalculated inside precondition_loop_p because strength reduction
+ optimizations may obscure the loop's structure.
+
+ These values are only required by precondition_loop_p and insert_bct
+ whenever the number of iterations cannot be computed at compile time.
+ Only the difference between final_value and initial_value is
+ important. Note that final_value is only approximate. */
+ loop_info->initial_value = initial_value;
+ loop_info->comparison_value = comparison_value;
+ loop_info->final_value = plus_constant (comparison_value, off_by_one);
+ loop_info->increment = increment;
+ loop_info->iteration_var = iteration_var;
+ loop_info->comparison_code = comparison_code;
+ loop_info->iv = bl;
+
+ /* Try to determine the iteration count for loops such
+ as (for i = init; i < init + const; i++). When running the
+ loop optimization twice, the first pass often converts simple
+ loops into this form. */
+
+ if (REG_P (initial_value))
+ {
+ rtx reg1;
+ rtx reg2;
+ rtx const2;
+
+ reg1 = initial_value;
+ if (GET_CODE (final_value) == PLUS)
+ reg2 = XEXP (final_value, 0), const2 = XEXP (final_value, 1);
+ else
+ reg2 = final_value, const2 = const0_rtx;
+
+ /* Check for initial_value = reg1, final_value = reg2 + const2,
+ where reg1 != reg2. */
+ if (REG_P (reg2) && reg2 != reg1)
+ {
+ rtx temp;