You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* This pass tries to find the optimal set of induction variables for the loop.
It optimizes just the basic linear induction variables (although adding
bool preserve_biv; /* For the original biv, whether to preserve it. */
};
-/* Information attached to loop. */
-struct loop_data
-{
- unsigned regs_used; /* Number of registers used. */
-};
-
/* Types of uses. */
enum use_type
{
USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
- USE_OUTER, /* The induction variable is used outside the loop. */
USE_ADDRESS, /* Use in an address. */
USE_COMPARE /* Use is a compare. */
};
/* The currently optimized loop. */
struct loop *current_loop;
+ /* Number of registers used in it. */
+ unsigned regs_used;
+
/* Numbers of iterations for all exits of the current loop. */
htab_t niters;
return VEC_index (iv_cand_p, data->iv_candidates, i);
}
-/* The data for LOOP. */
-
-static inline struct loop_data *
-loop_data (struct loop *loop)
-{
- return loop->aux;
-}
-
/* The single loop exit if it dominates the latch, NULL otherwise. */
-static edge
+edge
single_dom_exit (struct loop *loop)
{
edge exit = loop->single_exit;
fprintf (file, " generic\n");
break;
- case USE_OUTER:
- fprintf (file, " outside\n");
- break;
-
case USE_ADDRESS:
fprintf (file, " address\n");
break;
nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
nfe_desc->exit = exit;
nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
- exit, &nfe_desc->niter);
+ exit, &nfe_desc->niter,
+ true);
*slot = nfe_desc;
}
else
}
/* Initializes data structures used by the iv optimization pass, stored
- in DATA. LOOPS is the loop tree. */
+ in DATA. */
static void
-tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
+tree_ssa_iv_optimize_init (struct ivopts_data *data)
{
- unsigned i;
-
data->version_info_size = 2 * num_ssa_names;
- data->version_info = xcalloc (data->version_info_size,
- sizeof (struct version_info));
+ data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
data->relevant = BITMAP_ALLOC (NULL);
data->important_candidates = BITMAP_ALLOC (NULL);
data->max_inv_id = 0;
data->niters = htab_create (10, nfe_hash, nfe_eq, free);
-
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
-
data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
static struct iv *
alloc_iv (tree base, tree step)
{
- struct iv *iv = xcalloc (1, sizeof (struct iv));
+ struct iv *iv = XCNEW (struct iv);
if (step && integer_zerop (step))
step = NULL_TREE;
determine_biv_step (tree phi)
{
struct loop *loop = bb_for_stmt (phi)->loop_father;
- tree name = PHI_RESULT (phi), base, step;
+ tree name = PHI_RESULT (phi);
+ affine_iv iv;
if (!is_gimple_reg (name))
return NULL_TREE;
- if (!simple_iv (loop, phi, name, &base, &step, true))
+ if (!simple_iv (loop, phi, name, &iv, true))
return NULL_TREE;
- if (zero_p (step))
- return NULL_TREE;
-
- return step;
+ return (zero_p (iv.step) ? NULL_TREE : iv.step);
}
/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
}
/* Checks whether STMT defines a linear induction variable and stores its
- parameters to BASE and STEP. */
+ parameters to IV. */
static bool
-find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt,
- tree *base, tree *step)
+find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
{
tree lhs;
struct loop *loop = data->current_loop;
- *base = NULL_TREE;
- *step = NULL_TREE;
+ iv->base = NULL_TREE;
+ iv->step = NULL_TREE;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step, true))
+ if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true))
return false;
- *base = expand_simple_operations (*base);
+ iv->base = expand_simple_operations (iv->base);
- if (contains_abnormal_ssa_name_p (*base)
- || contains_abnormal_ssa_name_p (*step))
+ if (contains_abnormal_ssa_name_p (iv->base)
+ || contains_abnormal_ssa_name_p (iv->step))
return false;
return true;
static void
find_givs_in_stmt (struct ivopts_data *data, tree stmt)
{
- tree base, step;
+ affine_iv iv;
- if (!find_givs_in_stmt_scev (data, stmt, &base, &step))
+ if (!find_givs_in_stmt_scev (data, stmt, &iv))
return;
- set_iv (data, TREE_OPERAND (stmt, 0), base, step);
+ set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
tree stmt, enum use_type use_type)
{
- struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
+ struct iv_use *use = XCNEW (struct iv_use);
use->id = n_iv_uses (data);
use->type = use_type;
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
}
-/* Checks whether the use OP is interesting and if so, records it
- as TYPE. */
+/* Checks whether the use OP is interesting and if so, records it. */
static struct iv_use *
-find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
- enum use_type type)
+find_interesting_uses_op (struct ivopts_data *data, tree op)
{
struct iv *iv;
struct iv *civ;
{
use = iv_use (data, iv->use_id);
- gcc_assert (use->type == USE_NONLINEAR_EXPR
- || use->type == USE_OUTER);
-
- if (type == USE_NONLINEAR_EXPR)
- use->type = USE_NONLINEAR_EXPR;
+ gcc_assert (use->type == USE_NONLINEAR_EXPR);
return use;
}
}
iv->have_use_for = true;
- civ = xmalloc (sizeof (struct iv));
+ civ = XNEW (struct iv);
*civ = *iv;
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (TREE_CODE (stmt) == PHI_NODE
|| TREE_CODE (stmt) == MODIFY_EXPR);
- use = record_use (data, NULL, civ, stmt, type);
+ use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
iv->use_id = use->id;
return use;
}
-/* Checks whether the use OP is interesting and if so, records it. */
-
-static struct iv_use *
-find_interesting_uses_op (struct ivopts_data *data, tree op)
-{
- return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
-}
-
-/* Records a definition of induction variable OP that is used outside of the
- loop. */
-
-static struct iv_use *
-find_interesting_uses_outer (struct ivopts_data *data, tree op)
-{
- return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
-}
-
/* Checks whether the condition *COND_P in STMT is interesting
and if so, records it. */
return;
}
- civ = xmalloc (sizeof (struct iv));
+ civ = XNEW (struct iv);
*civ = zero_p (iv0->step) ? *iv1: *iv0;
record_use (data, cond_p, civ, stmt, USE_COMPARE);
}
/* The step for pointer arithmetics already is 1 byte. */
step = build_int_cst (sizetype, 1);
+ /* FIXME: convert_step should not be used outside chrec_convert: fix
+ this by calling chrec_convert. */
iv_step = convert_step (dta->ivopts_data->current_loop,
sizetype, iv->base, iv->step, dta->stmt);
unsigned base_align;
/* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
- thus they are not missaligned. */
+ thus they are not misaligned. */
if (TREE_CODE (ref) == TARGET_MEM_REF)
return false;
/* Ignore bitfields for now. Not really something terribly complicated
to handle. TODO. */
- if (TREE_CODE (base) == COMPONENT_REF
- && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
+ if (TREE_CODE (base) == BIT_FIELD_REF
+ || (TREE_CODE (base) == COMPONENT_REF
+ && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1))))
goto fail;
if (STRICT_ALIGNMENT
for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
{
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
- find_interesting_uses_outer (data, def);
+ find_interesting_uses_op (data, def);
}
}
return orig_expr;
*offset = int_cst_value (expr);
- return build_int_cst_type (orig_type, 0);
+ return build_int_cst (orig_type, 0);
case PLUS_EXPR:
case MINUS_EXPR:
if (i == n_iv_cands (data))
{
- cand = xcalloc (1, sizeof (struct iv_cand));
+ cand = XCNEW (struct iv_cand);
cand->id = i;
if (!base && !step)
add_candidate (data, base, iv->step, false, use);
}
-/* Possibly adds pseudocandidate for replacing the final value of USE by
- a direct computation. */
-
-static void
-add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
-{
- struct tree_niter_desc *niter;
-
- /* We must know where we exit the loop and how many times does it roll. */
- niter = niter_for_single_dom_exit (data);
- if (!niter
- || !zero_p (niter->may_be_zero))
- return;
-
- add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
-}
-
/* Adds candidates based on the uses. */
static void
add_iv_value_candidates (data, use->iv, use);
break;
- case USE_OUTER:
- add_iv_value_candidates (data, use->iv, use);
-
- /* Additionally, add the pseudocandidate for the possibility to
- replace the final value by a direct computation. */
- add_iv_outer_candidates (data, use);
- break;
-
default:
gcc_unreachable ();
}
}
use->n_map_members = size;
- use->cost_map = xcalloc (size, sizeof (struct cost_pair));
+ use->cost_map = XCNEWVEC (struct cost_pair, size);
}
}
expr_p = &TREE_OPERAND (*expr_p, 0))
continue;
obj = *expr_p;
- if (DECL_P (obj))
+ if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
x = produce_memory_decl_rtl (obj, regno);
break;
comb->n--;
comb->coefs[i] = comb->coefs[comb->n];
comb->elts[i] = comb->elts[comb->n];
+
+ if (comb->rest)
+ {
+ gcc_assert (comb->n == MAX_AFF_ELTS - 1);
+ comb->coefs[comb->n] = 1;
+ comb->elts[comb->n] = comb->rest;
+ comb->rest = NULL_TREE;
+ comb->n++;
+ }
return;
}
if (comb->n < MAX_AFF_ELTS)
unsigned i;
comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
- for (i = 0; i < comb2-> n; i++)
+ for (i = 0; i < comb2->n; i++)
aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
if (comb2->rest)
aff_combination_add_elt (comb1, comb2->rest, 1);
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;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (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)
- && cst_and_fits_in_hwi (ustep))
+ if (cst_and_fits_in_hwi (cstep_orig)
+ && cst_and_fits_in_hwi (ustep_orig))
{
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
+ ustepi = int_cst_value (ustep_orig);
+ cstepi = int_cst_value (cstep_orig);
if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
{
}
else
{
- ratio = constant_multiple_of (uutype, ustep, cstep);
+ ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
if (!ratio)
return false;
/* 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));
+ cbase = fold_build2 (PLUS_EXPR, uutype, cbase, cstep);
/* use = ubase - ratio * cbase + ratio * var.
start_sequence ();
force_operand (gen_rtx_fmt_ee (PLUS, mode,
- gen_raw_REG (mode, FIRST_PSEUDO_REGISTER),
- gen_raw_REG (mode, FIRST_PSEUDO_REGISTER + 1)),
+ gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+ gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
NULL_RTX);
seq = get_insns ();
end_sequence ();
if (*cached)
return (*cached)->cost;
- *cached = xmalloc (sizeof (struct mbc_entry));
+ *cached = XNEW (struct mbc_entry);
(*cached)->mode = mode;
(*cached)->cst = cst;
start_sequence ();
- expand_mult (mode, gen_raw_REG (mode, FIRST_PSEUDO_REGISTER), GEN_INT (cst),
- NULL_RTX, 0);
+ expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+ gen_int_mode (cst, mode), NULL_RTX, 0);
seq = get_insns ();
end_sequence ();
if (!valid_mult)
{
- rtx reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
+ rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
rtx addr;
HOST_WIDE_INT i;
HOST_WIDE_INT i;
initialized = true;
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
+ reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
for (i = 1; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = GEN_INT (i);
+ XEXP (addr, 1) = gen_int_mode (i, Pmode);
if (!memory_address_p (Pmode, addr))
break;
}
for (i = 1; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = GEN_INT (-i);
+ XEXP (addr, 1) = gen_int_mode (-i, Pmode);
if (!memory_address_p (Pmode, addr))
break;
}
acost = costs[symbol_present][var_present][offset_p][ratio_p];
if (!acost)
{
+ int old_cse_not_expected;
acost = 0;
- addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 1);
+ addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+ reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
if (ratio_p)
- addr = gen_rtx_fmt_ee (MULT, Pmode, addr, GEN_INT (rat));
+ addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));
if (var_present)
addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
base = gen_rtx_fmt_e (CONST, Pmode,
gen_rtx_fmt_ee (PLUS, Pmode,
base,
- GEN_INT (off)));
+ gen_int_mode (off, Pmode)));
}
else if (offset_p)
- base = GEN_INT (off);
+ base = gen_int_mode (off, Pmode);
else
base = NULL_RTX;
addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
start_sequence ();
+ /* To avoid splitting addressing modes, pretend that no cse will
+ follow. */
+ old_cse_not_expected = cse_not_expected;
+ cse_not_expected = true;
addr = memory_address (Pmode, addr);
+ cse_not_expected = old_cse_not_expected;
seq = get_insns ();
end_sequence ();
return cost + acost;
}
-/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
- invariants the computation depends on. */
-static unsigned
-force_var_cost (struct ivopts_data *data,
- tree expr, bitmap *depends_on)
+/* Estimates cost of forcing expression EXPR into a variable. */
+
+unsigned
+force_expr_to_var_cost (tree expr)
{
static bool costs_initialized = false;
static unsigned integer_cost;
tree addr;
tree type = build_pointer_type (integer_type_node);
- integer_cost = computation_cost (build_int_cst_type (integer_type_node,
- 2000));
+ integer_cost = computation_cost (build_int_cst (integer_type_node,
+ 2000));
SET_DECL_RTL (var, x);
TREE_STATIC (var) = 1;
address_cost
= computation_cost (build2 (PLUS_EXPR, type,
addr,
- build_int_cst_type (type, 2000))) + 1;
+ build_int_cst (type, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "force_var_cost:\n");
+ fprintf (dump_file, "force_expr_to_var_cost:\n");
fprintf (dump_file, " integer %d\n", (int) integer_cost);
fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
fprintf (dump_file, " address %d\n", (int) address_cost);
STRIP_NOPS (expr);
- if (depends_on)
- {
- fd_ivopts_data = data;
- walk_tree (&expr, find_depends, depends_on, NULL);
- }
-
if (SSA_VAR_P (expr))
return 0;
if (is_gimple_val (op0))
cost0 = 0;
else
- cost0 = force_var_cost (data, op0, NULL);
+ cost0 = force_expr_to_var_cost (op0);
if (is_gimple_val (op1))
cost1 = 0;
else
- cost1 = force_var_cost (data, op1, NULL);
+ cost1 = force_expr_to_var_cost (op1);
break;
return cost < target_spill_cost ? cost : target_spill_cost;
}
+/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
+ invariants the computation depends on. */
+
+static unsigned
+force_var_cost (struct ivopts_data *data,
+ tree expr, bitmap *depends_on)
+{
+ if (depends_on)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&expr, find_depends, depends_on, NULL);
+ }
+
+ return force_expr_to_var_cost (expr);
+}
+
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
to false if the corresponding part is missing. DEPENDS_ON is a set of the
tree type = TREE_TYPE (iv->base);
niter = fold_convert (type, niter);
- val = fold (build2 (MULT_EXPR, type, iv->step, niter));
+ val = fold_build2 (MULT_EXPR, type, iv->step, niter);
- return fold (build2 (PLUS_EXPR, type, iv->base, val));
+ return fold_build2 (PLUS_EXPR, type, iv->base, val);
}
/* Computes value of candidate CAND at position AT in iteration NITER. */
tree type = TREE_TYPE (cand->iv->base);
if (stmt_after_increment (loop, cand, at))
- val = fold (build2 (PLUS_EXPR, type, val, cand->iv->step));
+ val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
return val;
}
else
wider_type = nit_type;
- if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
- fold_convert (wider_type, period),
- fold_convert (wider_type, nit)))))
+ if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
+ fold_convert (wider_type, period),
+ fold_convert (wider_type, nit))))
return false;
*bound = cand_value_at (loop, cand, use->stmt, nit);
return cost != INFTY;
}
-/* Checks whether it is possible to replace the final value of USE by
- a direct computation. If so, the formula is stored to *VALUE. */
-
-static bool
-may_replace_final_value (struct ivopts_data *data, struct iv_use *use,
- tree *value)
-{
- struct loop *loop = data->current_loop;
- edge exit;
- struct tree_niter_desc *niter;
-
- exit = single_dom_exit (loop);
- if (!exit)
- return false;
-
- gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
- bb_for_stmt (use->stmt)));
-
- niter = niter_for_single_dom_exit (data);
- if (!niter
- || !zero_p (niter->may_be_zero))
- return false;
-
- *value = iv_value (use->iv, niter->niter);
-
- return true;
-}
-
-/* Determines cost of replacing final value of USE using CAND. */
-
-static bool
-determine_use_iv_cost_outer (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
-{
- bitmap depends_on;
- unsigned cost;
- edge exit;
- tree value = NULL_TREE;
- struct loop *loop = data->current_loop;
-
- /* The simple case first -- if we need to express value of the preserved
- original biv, the cost is 0. This also prevents us from counting the
- cost of increment twice -- once at this use and once in the cost of
- the candidate. */
- if (cand->pos == IP_ORIGINAL
- && cand->incremented_at == use->stmt)
- {
- set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
- return true;
- }
-
- if (!cand->iv)
- {
- if (!may_replace_final_value (data, use, &value))
- {
- set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
- return false;
- }
-
- depends_on = NULL;
- cost = force_var_cost (data, value, &depends_on);
-
- cost /= AVG_LOOP_NITER (loop);
-
- set_use_iv_cost (data, use, cand, cost, depends_on, value);
- return cost != INFTY;
- }
-
- exit = single_dom_exit (loop);
- if (exit)
- {
- /* If there is just a single exit, we may use value of the candidate
- after we take it to determine the value of use. */
- cost = get_computation_cost_at (data, use, cand, false, &depends_on,
- last_stmt (exit->src));
- if (cost != INFTY)
- cost /= AVG_LOOP_NITER (loop);
- }
- else
- {
- /* Otherwise we just need to compute the iv. */
- cost = get_computation_cost (data, use, cand, false, &depends_on);
- }
-
- set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
-
- return cost != INFTY;
-}
-
/* Determines cost of basing replacement of USE on CAND. Returns false
if USE cannot be based on CAND. */
case USE_NONLINEAR_EXPR:
return determine_use_iv_cost_generic (data, use, cand);
- case USE_OUTER:
- return determine_use_iv_cost_outer (data, use, cand);
-
case USE_ADDRESS:
return determine_use_iv_cost_address (data, use, cand);
static unsigned
ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
{
- return global_cost_for_size (size,
- loop_data (data->current_loop)->regs_used,
- n_iv_uses (data));
+ return global_cost_for_size (size, data->regs_used, n_iv_uses (data));
}
/* For each size of the induction variable set determine the penalty. */
n++;
}
- loop_data (loop)->regs_used = n;
+ data->regs_used = n;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " regs_used %d\n", n);
iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
struct cost_pair *new_cp, struct iv_ca_delta *next_change)
{
- struct iv_ca_delta *change = xmalloc (sizeof (struct iv_ca_delta));
+ struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
change->use = use;
change->old_cp = old_cp;
static struct iv_ca *
iv_ca_new (struct ivopts_data *data)
{
- struct iv_ca *nw = xmalloc (sizeof (struct iv_ca));
+ struct iv_ca *nw = XNEW (struct iv_ca);
nw->upto = 0;
nw->bad_uses = 0;
- nw->cand_for_use = xcalloc (n_iv_uses (data), sizeof (struct cost_pair *));
- nw->n_cand_uses = xcalloc (n_iv_cands (data), sizeof (unsigned));
+ nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
+ nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
nw->cands = BITMAP_ALLOC (NULL);
nw->n_cands = 0;
nw->n_regs = 0;
nw->cand_use_cost = 0;
nw->cand_cost = 0;
- nw->n_invariant_uses = xcalloc (data->max_inv_id + 1, sizeof (unsigned));
+ nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
nw->cost = 0;
return nw;
{
block_stmt_iterator bsi = bsi_for_stmt (stmt);
- bsi_remove (&bsi);
+ bsi_remove (&bsi, true);
}
}
introduce a new computation (that might also need casting the
variable to unsigned and back). */
if (cand->pos == IP_ORIGINAL
- && TREE_CODE (use->stmt) == MODIFY_EXPR
- && TREE_OPERAND (use->stmt, 0) == cand->var_after)
+ && cand->incremented_at == use->stmt)
{
+ tree step, ctype, utype;
+ enum tree_code incr_code = PLUS_EXPR;
+
+ gcc_assert (TREE_CODE (use->stmt) == MODIFY_EXPR);
+ gcc_assert (TREE_OPERAND (use->stmt, 0) == cand->var_after);
+
+ step = cand->iv->step;
+ ctype = TREE_TYPE (step);
+ utype = TREE_TYPE (cand->var_after);
+ if (TREE_CODE (step) == NEGATE_EXPR)
+ {
+ incr_code = MINUS_EXPR;
+ step = TREE_OPERAND (step, 0);
+ }
+
+ /* Check whether we may leave the computation unchanged.
+ This is the case only if it does not rely on other
+ computations in the loop -- otherwise, the computation
+ we rely upon may be removed in remove_unused_ivs,
+ thus leading to ICE. */
op = TREE_OPERAND (use->stmt, 1);
+ if (TREE_CODE (op) == PLUS_EXPR
+ || TREE_CODE (op) == MINUS_EXPR)
+ {
+ if (TREE_OPERAND (op, 0) == cand->var_before)
+ op = TREE_OPERAND (op, 1);
+ else if (TREE_CODE (op) == PLUS_EXPR
+ && TREE_OPERAND (op, 1) == cand->var_before)
+ op = TREE_OPERAND (op, 0);
+ else
+ op = NULL_TREE;
+ }
+ else
+ op = NULL_TREE;
- /* Be a bit careful. In case variable is expressed in some
- complicated way, rewrite it so that we may get rid of this
- complicated expression. */
- if ((TREE_CODE (op) == PLUS_EXPR
- || TREE_CODE (op) == MINUS_EXPR)
- && TREE_OPERAND (op, 0) == cand->var_before
- && TREE_CODE (TREE_OPERAND (op, 1)) == INTEGER_CST)
+ if (op
+ && (TREE_CODE (op) == INTEGER_CST
+ || operand_equal_p (op, step, 0)))
return;
+
+ /* Otherwise, add the necessary computations to express
+ the iv. */
+ op = fold_convert (ctype, cand->var_before);
+ comp = fold_convert (utype,
+ build2 (incr_code, ctype, op,
+ unshare_expr (step)));
}
+ else
+ comp = get_computation (data->current_loop, use, cand);
- comp = get_computation (data->current_loop, use, cand);
switch (TREE_CODE (use->stmt))
{
case PHI_NODE:
and extracts this single useful piece of information. */
static tree
-get_ref_tag (tree ref)
+get_ref_tag (tree ref, tree orig)
{
tree var = get_base_address (ref);
- tree tag;
+ tree aref = NULL_TREE, tag, sv;
+ HOST_WIDE_INT offset, size, maxsize;
+
+ for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
+ {
+ aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
+ if (ref)
+ break;
+ }
+
+ if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
+ return unshare_expr (sv);
if (!var)
return NULL_TREE;
if (TREE_CODE (var) == INDIRECT_REF)
- var = TREE_OPERAND (var, 0);
- if (TREE_CODE (var) == SSA_NAME)
{
+ /* If the base is a dereference of a pointer, first check its name memory
+ tag. If it does not have one, use its symbol memory tag. */
+ var = TREE_OPERAND (var, 0);
+ if (TREE_CODE (var) != SSA_NAME)
+ return NULL_TREE;
+
if (SSA_NAME_PTR_INFO (var))
{
tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
}
var = SSA_NAME_VAR (var);
+ tag = var_ann (var)->symbol_mem_tag;
+ gcc_assert (tag != NULL_TREE);
+ return tag;
}
-
- if (DECL_P (var))
- {
- tag = var_ann (var)->type_mem_tag;
+ else
+ {
+ if (!DECL_P (var))
+ return NULL_TREE;
+
+ tag = var_ann (var)->symbol_mem_tag;
if (tag)
return tag;
return var;
}
-
- return NULL_TREE;
}
/* Copies the reference information from OLD_REF to NEW_REF. */
copy_mem_ref_info (new_ref, old_ref);
else
{
- TMR_TAG (new_ref) = get_ref_tag (old_ref);
TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
+ TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
}
}
so that they are emitted on the correct place, and so that the loop closed
ssa form is preserved. */
-static void
+void
compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
{
tree_stmt_iterator tsi;
{
for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
{
- bsi_insert_after (&bsi, tsi_stmt (tsi), BSI_NEW_STMT);
- protect_loop_closed_ssa_form (exit, bsi_stmt (bsi));
+ tree stmt = tsi_stmt (tsi);
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
+ protect_loop_closed_ssa_form (exit, stmt);
}
}
else
{
- bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
- protect_loop_closed_ssa_form (exit, bsi_stmt (bsi));
+ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ protect_loop_closed_ssa_form (exit, stmts);
}
if (!op)
stmt = build2 (MODIFY_EXPR, TREE_TYPE (op),
def, op);
SSA_NAME_DEF_STMT (def) = stmt;
- bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
- }
- }
-}
-
-/* Rewrites the final value of USE (that is only needed outside of the loop)
- using candidate CAND. */
-
-static void
-rewrite_use_outer (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
-{
- edge exit;
- tree value, op, stmts, tgt;
- tree phi;
-
- switch (TREE_CODE (use->stmt))
- {
- case PHI_NODE:
- tgt = PHI_RESULT (use->stmt);
- break;
- case MODIFY_EXPR:
- tgt = TREE_OPERAND (use->stmt, 0);
- break;
- default:
- gcc_unreachable ();
- }
-
- exit = single_dom_exit (data->current_loop);
-
- if (exit)
- {
- if (!cand->iv)
- {
- struct cost_pair *cp = get_use_iv_cost (data, use, cand);
- value = unshare_expr (cp->value);
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
}
- else
- value = get_computation_at (data->current_loop,
- use, cand, last_stmt (exit->src));
-
- op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
-
- /* If we will preserve the iv anyway and we would need to perform
- some computation to replace the final value, do nothing. */
- if (stmts && name_info (data, tgt)->preserve_biv)
- return;
-
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
- {
- use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
-
- if (USE_FROM_PTR (use_p) == tgt)
- SET_USE (use_p, op);
- }
-
- if (stmts)
- compute_phi_arg_on_exit (exit, stmts, op);
-
- /* Enable removal of the statement. We cannot remove it directly,
- since we may still need the aliasing information attached to the
- ssa name defined by it. */
- name_info (data, tgt)->iv->have_use_for = false;
- return;
}
-
- /* If the variable is going to be preserved anyway, there is nothing to
- do. */
- if (name_info (data, tgt)->preserve_biv)
- return;
-
- /* Otherwise we just need to compute the iv. */
- rewrite_use_nonlinear_expr (data, use, cand);
}
/* Rewrites USE using candidate CAND. */
rewrite_use_nonlinear_expr (data, use, cand);
break;
- case USE_OUTER:
- rewrite_use_outer (data, use, cand);
- break;
-
case USE_ADDRESS:
rewrite_use_address (data, use, cand);
break;
default:
gcc_unreachable ();
}
- update_stmt (use->stmt);
+ mark_new_vars_to_rename (use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
{
data->version_info_size = 2 * num_ssa_names;
free (data->version_info);
- data->version_info = xcalloc (data->version_info_size,
- sizeof (struct version_info));
+ data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
}
data->max_inv_id = 0;
loop tree. */
static void
-tree_ssa_iv_optimize_finalize (struct loops *loops, struct ivopts_data *data)
+tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
{
- unsigned i;
-
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- {
- free (loops->parray[i]->aux);
- loops->parray[i]->aux = NULL;
- }
-
free_loop_data (data);
free (data->version_info);
BITMAP_FREE (data->relevant);
struct loop *loop;
struct ivopts_data data;
- tree_ssa_iv_optimize_init (loops, &data);
+ tree_ssa_iv_optimize_init (&data);
/* Optimize the loops starting with the innermost ones. */
loop = loops->tree_root;
loop = loop->outer;
}
- tree_ssa_iv_optimize_finalize (loops, &data);
+ tree_ssa_iv_optimize_finalize (&data);
}