+ case NEGATE_EXPR:
+ tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
+ aff_combination_scale (comb, -1);
+ return;
+
+ case ADDR_EXPR:
+ core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
+ &toffset, &mode, &unsignedp, &volatilep,
+ false);
+ if (bitpos % BITS_PER_UNIT != 0)
+ break;
+ aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
+ core = build_fold_addr_expr (core);
+ if (TREE_CODE (core) == ADDR_EXPR)
+ aff_combination_add_elt (comb, core, 1);
+ else
+ {
+ tree_to_aff_combination (core, type, &tmp);
+ aff_combination_add (comb, &tmp);
+ }
+ if (toffset)
+ {
+ tree_to_aff_combination (toffset, type, &tmp);
+ aff_combination_add (comb, &tmp);
+ }
+ return;
+
+ default:
+ break;
+ }
+
+ aff_combination_elt (comb, type, expr);
+}
+
+/* Creates EXPR + ELT * SCALE in TYPE. MASK is the mask for width of TYPE. */
+
+static tree
+add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
+ unsigned HOST_WIDE_INT mask)
+{
+ enum tree_code code;
+
+ scale &= mask;
+ elt = fold_convert (type, elt);
+
+ if (scale == 1)
+ {
+ if (!expr)
+ return elt;
+
+ return fold_build2 (PLUS_EXPR, type, expr, elt);
+ }
+
+ if (scale == mask)
+ {
+ if (!expr)
+ return fold_build1 (NEGATE_EXPR, type, elt);
+
+ return fold_build2 (MINUS_EXPR, type, expr, elt);
+ }
+
+ if (!expr)
+ return fold_build2 (MULT_EXPR, type, elt,
+ build_int_cst_type (type, scale));
+
+ if ((scale | (mask >> 1)) == mask)
+ {
+ /* Scale is negative. */
+ code = MINUS_EXPR;
+ scale = (-scale) & mask;
+ }
+ else
+ code = PLUS_EXPR;
+
+ elt = fold_build2 (MULT_EXPR, type, elt,
+ build_int_cst_type (type, scale));
+ return fold_build2 (code, type, expr, elt);
+}
+
+/* Copies the tree elements of COMB to ensure that they are not shared. */
+
+static void
+unshare_aff_combination (struct affine_tree_combination *comb)
+{
+ unsigned i;
+
+ for (i = 0; i < comb->n; i++)
+ comb->elts[i] = unshare_expr (comb->elts[i]);
+ if (comb->rest)
+ comb->rest = unshare_expr (comb->rest);
+}
+
+/* Makes tree from the affine combination COMB. */
+
+static tree
+aff_combination_to_tree (struct affine_tree_combination *comb)
+{
+ tree type = comb->type;
+ tree expr = comb->rest;
+ unsigned i;
+ unsigned HOST_WIDE_INT off, sgn;
+
+ if (comb->n == 0 && comb->offset == 0)
+ {
+ if (expr)
+ {
+ /* Handle the special case produced by get_computation_aff when
+ the type does not fit in HOST_WIDE_INT. */
+ return fold_convert (type, expr);
+ }
+ else
+ return build_int_cst (type, 0);
+ }
+
+ gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
+
+ for (i = 0; i < comb->n; i++)
+ expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
+ comb->mask);
+
+ if ((comb->offset | (comb->mask >> 1)) == comb->mask)
+ {
+ /* Offset is negative. */
+ off = (-comb->offset) & comb->mask;
+ sgn = comb->mask;
+ }
+ else
+ {
+ off = comb->offset;
+ sgn = 1;
+ }
+ return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
+ comb->mask);
+}
+
+/* Folds EXPR using the affine expressions framework. */
+
+static tree
+fold_affine_expr (tree expr)
+{
+ tree type = TREE_TYPE (expr);
+ struct affine_tree_combination comb;
+
+ if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT)
+ return expr;
+
+ tree_to_aff_combination (expr, type, &comb);
+ return aff_combination_to_tree (&comb);
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+ CAND at statement AT in LOOP. The expression is stored in a decomposed
+ form into AFF. Returns false if USE cannot be expressed using CAND. */
+
+static bool
+get_computation_aff (struct loop *loop,
+ struct iv_use *use, struct iv_cand *cand, tree at,
+ struct affine_tree_combination *aff)
+{
+ tree ubase = use->iv->base;
+ tree ustep = use->iv->step;
+ tree cbase = cand->iv->base;
+ tree cstep = cand->iv->step;
+ tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+ tree uutype;
+ tree expr, delta;
+ tree ratio;
+ unsigned HOST_WIDE_INT ustepi, cstepi;
+ HOST_WIDE_INT ratioi;
+ struct affine_tree_combination cbase_aff, expr_aff;
+ tree cstep_orig = cstep, ustep_orig = ustep;
+ double_int rat;
+
+ if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
+ {
+ /* We do not have a precision to express the values of use. */
+ return false;
+ }
+
+ expr = var_at_stmt (loop, cand, at);
+
+ if (TREE_TYPE (expr) != ctype)
+ {
+ /* This may happen with the original ivs. */
+ expr = fold_convert (ctype, expr);
+ }
+
+ if (TYPE_UNSIGNED (utype))
+ uutype = utype;
+ else
+ {
+ uutype = unsigned_type_for (utype);
+ ubase = fold_convert (uutype, ubase);
+ ustep = fold_convert (uutype, ustep);
+ }
+
+ if (uutype != ctype)
+ {
+ expr = fold_convert (uutype, expr);
+ cbase = fold_convert (uutype, cbase);
+ cstep = fold_convert (uutype, cstep);
+
+ /* If the conversion is not noop, we must take it into account when
+ considering the value of the step. */
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
+ cstep_orig = cstep;
+ }
+
+ if (cst_and_fits_in_hwi (cstep_orig)
+ && cst_and_fits_in_hwi (ustep_orig))
+ {
+ ustepi = int_cst_value (ustep_orig);
+ cstepi = int_cst_value (cstep_orig);
+
+ if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
+ {
+ /* TODO maybe consider case when ustep divides cstep and the ratio is
+ a power of 2 (so that the division is fast to execute)? We would
+ need to be much more careful with overflows etc. then. */
+ return false;
+ }
+
+ ratio = build_int_cst_type (uutype, ratioi);
+ }
+ else
+ {
+ if (!constant_multiple_of (ustep_orig, cstep_orig, &rat))
+ return false;
+ ratio = double_int_to_tree (uutype, rat);
+
+ /* Ratioi is only used to detect special cases when the multiplicative
+ factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may
+ set it to 0. */
+ if (double_int_fits_in_shwi_p (rat))
+ ratioi = double_int_to_shwi (rat);
+ else
+ ratioi = 0;
+ }
+
+ /* We may need to shift the value if we are after the increment. */
+ if (stmt_after_increment (loop, cand, at))
+ cbase = fold_build2 (PLUS_EXPR, uutype, cbase, cstep);
+
+ /* use = ubase - ratio * cbase + ratio * var.
+
+ In general case ubase + ratio * (var - cbase) could be better (one less
+ multiplication), but often it is possible to eliminate redundant parts
+ of computations from (ubase - ratio * cbase) term, and if it does not
+ happen, fold is able to apply the distributive law to obtain this form
+ anyway. */
+
+ if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
+ {
+ /* Let's compute in trees and just return the result in AFF. This case
+ should not be very common, and fold itself is not that bad either,
+ so making the aff. functions more complicated to handle this case
+ is not that urgent. */
+ if (ratioi == 1)
+ {
+ delta = fold_build2 (MINUS_EXPR, uutype, ubase, cbase);
+ expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
+ }
+ else if (ratioi == -1)
+ {
+ delta = fold_build2 (PLUS_EXPR, uutype, ubase, cbase);
+ expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
+ }
+ else
+ {
+ delta = fold_build2 (MULT_EXPR, uutype, cbase, ratio);
+ delta = fold_build2 (MINUS_EXPR, uutype, ubase, delta);
+ expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
+ expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
+ }
+
+ aff->type = uutype;
+ aff->n = 0;
+ aff->offset = 0;
+ aff->mask = 0;
+ aff->rest = expr;
+ return true;
+ }
+
+ /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
+ possible to compute ratioi. */
+ gcc_assert (ratioi);
+
+ tree_to_aff_combination (ubase, uutype, aff);
+ tree_to_aff_combination (cbase, uutype, &cbase_aff);
+ tree_to_aff_combination (expr, uutype, &expr_aff);
+ aff_combination_scale (&cbase_aff, -ratioi);
+ aff_combination_scale (&expr_aff, ratioi);
+ aff_combination_add (aff, &cbase_aff);
+ aff_combination_add (aff, &expr_aff);
+
+ return true;
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+ CAND at statement AT in LOOP. The computation is unshared. */
+
+static tree
+get_computation_at (struct loop *loop,
+ struct iv_use *use, struct iv_cand *cand, tree at)
+{
+ struct affine_tree_combination aff;
+ tree type = TREE_TYPE (use->iv->base);
+
+ if (!get_computation_aff (loop, use, cand, at, &aff))
+ return NULL_TREE;
+ unshare_aff_combination (&aff);
+ return fold_convert (type, aff_combination_to_tree (&aff));
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+ CAND in LOOP. The computation is unshared. */
+
+static tree
+get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
+{
+ return get_computation_at (loop, use, cand, use->stmt);
+}
+
+/* Returns cost of addition in MODE. */
+
+static unsigned
+add_cost (enum machine_mode mode)
+{
+ static unsigned costs[NUM_MACHINE_MODES];
+ rtx seq;
+ unsigned cost;
+
+ if (costs[mode])
+ return costs[mode];
+
+ start_sequence ();
+ force_operand (gen_rtx_fmt_ee (PLUS, mode,
+ gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+ gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
+ NULL_RTX);
+ seq = get_insns ();
+ end_sequence ();
+
+ cost = seq_cost (seq);
+ if (!cost)
+ cost = 1;
+
+ costs[mode] = cost;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Addition in %s costs %d\n",
+ GET_MODE_NAME (mode), cost);
+ return cost;
+}
+
+/* Entry in a hashtable of already known costs for multiplication. */
+struct mbc_entry
+{
+ HOST_WIDE_INT cst; /* The constant to multiply by. */
+ enum machine_mode mode; /* In mode. */
+ unsigned cost; /* The cost. */
+};
+
+/* Counts hash value for the ENTRY. */
+
+static hashval_t
+mbc_entry_hash (const void *entry)
+{
+ const struct mbc_entry *e = entry;
+
+ return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
+}
+
+/* Compares the hash table entries ENTRY1 and ENTRY2. */
+
+static int
+mbc_entry_eq (const void *entry1, const void *entry2)
+{
+ const struct mbc_entry *e1 = entry1;
+ const struct mbc_entry *e2 = entry2;
+
+ return (e1->mode == e2->mode
+ && e1->cst == e2->cst);
+}
+
+/* Returns cost of multiplication by constant CST in MODE. */
+
+unsigned
+multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
+{
+ static htab_t costs;
+ struct mbc_entry **cached, act;
+ rtx seq;
+ unsigned cost;
+
+ if (!costs)
+ costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
+
+ act.mode = mode;