/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
-
+
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
4) The trees are transformed to use the new variables, the dead code is
removed.
-
+
All of this is done loop by loop. Doing it globally is theoretically
possible, it might give a better performance and it might enable us
to decide costs more precisely, but getting all the interactions right
print_generic_expr (dump_file, niter, TDF_SLIM);
fprintf (dump_file, "\n\n");
};
-
+
fprintf (dump_file, "Induction variables:\n\n");
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
iv = get_iv (data, op);
if (!iv)
return NULL;
-
+
if (iv->have_use_for)
{
use = iv_use (data, iv->use_id);
|| bitpos % GET_MODE_ALIGNMENT (mode) != 0
|| bitpos % BITS_PER_UNIT != 0)
return true;
-
+
if (!constant_multiple_of (step, al, &mul))
return true;
}
while (handled_component_p (*ref))
ref = &TREE_OPERAND (*ref, 0);
if (TREE_CODE (*ref) == INDIRECT_REF)
- *ref = fold_indirect_ref (*ref);
+ {
+ tree tem = gimple_fold_indirect_ref (TREE_OPERAND (*ref, 0));
+ if (tem)
+ *ref = tem;
+ }
}
}
unsigned i;
struct iv_cand *cand = NULL;
tree type, orig_type;
-
+
if (base)
{
orig_type = TREE_TYPE (base);
it. The candidate computation is scheduled on all available positions. */
static void
-add_candidate (struct ivopts_data *data,
+add_candidate (struct ivopts_data *data,
tree base, tree step, bool important, struct iv_use *use)
{
if (ip_normal_pos (data->current_loop))
return ret;
}
-
+
/* n_map_members is a power of two, so this computes modulo. */
s = cand->id & (use->n_map_members - 1);
for (i = s; i < use->n_map_members; i++)
addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj));
enum machine_mode address_mode = targetm.addr_space.address_mode (as);
rtx x;
-
+
gcc_assert (obj);
if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
{
if (stmt_after_increment (loop, cand, at))
{
aff_tree cstep_aff;
-
+
if (common_type != uutype)
cstep_common = fold_convert (common_type, cstep);
else
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);
gen_int_mode (cst, mode), NULL_RTX, 0);
seq = get_insns ();
end_sequence ();
-
+
cost = seq_cost (seq, speed);
if (dump_file && (dump_flags & TDF_DETAILS))
base = gen_int_mode (off, address_mode);
else
base = NULL_RTX;
-
+
if (base)
addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, base);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Address costs:\n");
-
+
for (i = 0; i < 16; i++)
{
sym_p = i & 1;
case MULT_EXPR:
if (cst_and_fits_in_hwi (op0))
cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
- else if (cst_and_fits_in_hwi (op1))
+ else if (cst_and_fits_in_hwi (op1))
cost = new_cost (multiply_by_cost (int_cst_value (op1), mode, speed), 0);
else
return new_cost (target_spill_cost [speed], 0);
tree toffset;
enum machine_mode mode;
int unsignedp, volatilep;
-
+
core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
&unsignedp, &volatilep, false);
*var_present = false;
return zero_cost;
}
-
+
*symbol_present = false;
*var_present = true;
return zero_cost;
if (!constant_multiple_of (ustep, cstep, &rat))
return infinite_cost;
-
+
if (double_int_fits_in_shwi_p (rat))
ratio = double_int_to_shwi (rat);
else
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
-
+
ubase - ratio * cbase + ratio * var
-
+
(also holds in the case ratio == -1, TODO. */
if (cst_and_fits_in_hwi (cbase))
{
- offset = - ratio * int_cst_value (cbase);
+ offset = - ratio * int_cst_value (cbase);
cost = difference_cost (data,
ubase, build_int_cst (utype, 0),
&symbol_present, &var_present, &offset,
bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
comp_cost elim_cost, express_cost, cost;
bool ok;
+ tree *control_var, *bound_cst;
/* Only consider real candidates. */
if (!cand->iv)
/* Try expressing the original giv. If it is compared with an invariant,
note that we cannot get rid of it. */
- ok = extract_cond_operands (data, use->stmt, NULL, NULL, NULL, &cmp_iv);
+ ok = extract_cond_operands (data, use->stmt, &control_var, &bound_cst,
+ NULL, &cmp_iv);
gcc_assert (ok);
+ /* When the condition is a comparison of the candidate IV against
+ zero, prefer this IV.
+
+ TODO: The constant that we're substracting from the cost should
+ be target-dependent. This information should be added to the
+ target costs for each backend. */
+ if (!infinite_cost_p (elim_cost) /* Do not try to decrease infinite! */
+ && integer_zerop (*bound_cst)
+ && (operand_equal_p (*control_var, cand->var_after, 0)
+ || operand_equal_p (*control_var, cand->var_before, 0)))
+ elim_cost.cost -= 1;
+
express_cost = get_computation_cost (data, use, cand, false,
&depends_on_express, NULL);
fd_ivopts_data = data;
if (cand->pos != IP_ORIGINAL
|| DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
cost++;
-
+
/* Prefer not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
if (cand->pos == IP_END
etc.). For now the reserve is a constant 3.
Let I be the number of induction variables.
-
+
-- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
make a lot of ivs without a reason).
-- if A - R < U + I <= A, the cost is I * PRES_COST
if (!iv_ca_has_deps (ivs, new_cp))
continue;
-
+
if (!cheaper_cost_pair (new_cp, old_cp))
continue;
continue;
if (!iv_ca_has_deps (ivs, cp))
continue;
-
+
if (!cheaper_cost_pair (cp, new_cp))
continue;
continue;
if (!iv_ca_has_deps (ivs, cp))
continue;
-
+
if (!cheaper_cost_pair (cp, new_cp))
continue;
/* Already tried this. */
if (cand->important && cand->iv->base_object == NULL_TREE)
continue;
-
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
for (i = 0; i < n_iv_cands (data); i++)
{
cand = iv_cand (data, i);
-
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
/* Rewrite the increment so that it uses var_before directly. */
find_interesting_uses_op (data, cand->var_after)->selected = cand;
-
+
return;
}
-
+
gimple_add_tmp_var (cand->var_before);
add_referenced_var (cand->var_before);
{
aff_tree aff;
gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+ tree base_hint = NULL_TREE;
tree ref;
bool ok;
gcc_assert (ok);
unshare_aff_combination (&aff);
- ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, data->speed);
+ /* To avoid undefined overflow problems, all IV candidates use unsigned
+ integer types. The drawback is that this makes it impossible for
+ create_mem_ref to distinguish an IV that is based on a memory object
+ from one that represents simply an offset.
+
+ To work around this problem, we pass a hint to create_mem_ref that
+ indicates which variable (if any) in aff is an IV based on a memory
+ object. Note that we only consider the candidate. If this is not
+ based on an object, the base of the reference is in some subexpression
+ of the use -- but these will use pointer types, so they are recognized
+ by the create_mem_ref heuristics anyway. */
+ if (cand->iv->base_object)
+ base_hint = var_at_stmt (data->current_loop, cand, use->stmt);
+
+ ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, base_hint,
+ data->speed);
copy_ref_info (ref, *use->op_p);
*use->op_p = ref;
}
default:
gcc_unreachable ();
}
-
+
update_stmt (use->stmt);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Processing loop %d\n", loop->num);
-
+
exit = single_dom_exit (loop);
if (exit)
{
/* Create the new induction variables (item 4, part 1). */
create_new_ivs (data, iv_ca);
iv_ca_free (&iv_ca);
-
+
/* Rewrite the uses (item 4, part 2). */
rewrite_uses (data);
OSDN Git Service
