/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
This file is part of GCC.
unsigned id; /* The id of the use. */
enum use_type type; /* Type of the use. */
struct iv *iv; /* The induction variable it is based on. */
- tree stmt; /* Statement in that it occurs. */
+ gimple stmt; /* Statement in that it occurs. */
tree *op_p; /* The place where it occurs. */
bitmap related_cands; /* The set of "related" iv candidates, plus the common
important ones. */
bool important; /* Whether this is an "important" candidate, i.e. such
that it should be considered by all uses. */
enum iv_position pos; /* Where it is computed. */
- tree incremented_at; /* For original biv, the statement where it is
+ gimple incremented_at;/* For original biv, the statement where it is
incremented. */
tree var_before; /* The variable used for it before increment. */
tree var_after; /* The variable used for it after increment. */
/* 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. */
struct pointer_map_t *niters;
+ /* Number of registers used in it. */
+ unsigned regs_used;
+
/* The size of version_info array allocated. */
unsigned version_info_size;
/* The bitmap of indices in version_info whose value was changed. */
bitmap relevant;
- /* The maximum invariant id. */
- unsigned max_inv_id;
-
/* The uses of induction variables. */
VEC(iv_use_p,heap) *iv_uses;
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* The maximum invariant id. */
+ unsigned max_inv_id;
+
/* Whether to consider just related and important candidates when replacing a
use. */
bool consider_all_candidates;
+
+ /* Are we optimizing for speed? */
+ bool speed;
};
/* An assignment of iv candidates to uses. */
}
fprintf (file, " in statement ");
- print_generic_expr (file, use->stmt, TDF_SLIM);
+ print_gimple_stmt (file, use->stmt, 0, 0);
fprintf (file, "\n");
fprintf (file, " at position ");
emitted in LOOP. */
static bool
-stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
+stmt_after_ip_normal_pos (struct loop *loop, gimple stmt)
{
- basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
+ basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);
gcc_assert (bb);
variable CAND is incremented. */
static bool
-stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
+stmt_after_ip_original_pos (struct iv_cand *cand, gimple stmt)
{
- basic_block cand_bb = bb_for_stmt (cand->incremented_at);
- basic_block stmt_bb = bb_for_stmt (stmt);
- block_stmt_iterator bsi;
+ basic_block cand_bb = gimple_bb (cand->incremented_at);
+ basic_block stmt_bb = gimple_bb (stmt);
+ gimple_stmt_iterator bsi;
if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
return false;
/* Scan the block from the end, since the original ivs are usually
incremented at the end of the loop body. */
- for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
+ for (bsi = gsi_last_bb (stmt_bb); ; gsi_prev (&bsi))
{
- if (bsi_stmt (bsi) == cand->incremented_at)
+ if (gsi_stmt (bsi) == cand->incremented_at)
return false;
- if (bsi_stmt (bsi) == stmt)
+ if (gsi_stmt (bsi) == stmt)
return true;
}
}
CAND is incremented in LOOP. */
static bool
-stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
+stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple stmt)
{
switch (cand->pos)
{
idx_contains_abnormal_ssa_name_p (tree base, tree *index,
void *data ATTRIBUTE_UNUSED)
{
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
return false;
/* If this is a pointer casted to any type, we need to determine
the base object for the pointer; so handle conversions before
throwing away non-pointer expressions. */
- if (TREE_CODE (expr) == NOP_EXPR
- || TREE_CODE (expr) == CONVERT_EXPR)
+ if (CONVERT_EXPR_P (expr))
return determine_base_object (TREE_OPERAND (expr, 0));
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
if (!name_info (data, var)->iv)
{
- bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ bb = gimple_bb (SSA_NAME_DEF_STMT (var));
if (!bb
|| !flow_bb_inside_loop_p (data->current_loop, bb))
not define a simple affine biv with nonzero step. */
static tree
-determine_biv_step (tree phi)
+determine_biv_step (gimple phi)
{
- struct loop *loop = bb_for_stmt (phi)->loop_father;
+ struct loop *loop = gimple_bb (phi)->loop_father;
tree name = PHI_RESULT (phi);
affine_iv iv;
if (!is_gimple_reg (name))
return NULL_TREE;
- if (!simple_iv (loop, phi, name, &iv, true))
+ if (!simple_iv (loop, loop, name, &iv, true))
return NULL_TREE;
return integer_zerop (iv.step) ? NULL_TREE : iv.step;
static bool
find_bivs (struct ivopts_data *data)
{
- tree phi, step, type, base;
+ gimple phi;
+ tree step, type, base;
bool found = false;
struct loop *loop = data->current_loop;
+ gimple_stmt_iterator psi;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
+
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
continue;
static void
mark_bivs (struct ivopts_data *data)
{
- tree phi, var;
+ gimple phi;
+ tree var;
struct iv *iv, *incr_iv;
struct loop *loop = data->current_loop;
basic_block incr_bb;
+ gimple_stmt_iterator psi;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
+
iv = get_iv (data, PHI_RESULT (phi));
if (!iv)
continue;
continue;
/* If the increment is in the subloop, ignore it. */
- incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ incr_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
if (incr_bb->loop_father != data->current_loop
|| (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
continue;
parameters to IV. */
static bool
-find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
+find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv)
{
tree lhs;
struct loop *loop = data->current_loop;
iv->base = NULL_TREE;
iv->step = NULL_TREE;
- if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
return false;
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, GIMPLE_STMT_OPERAND (stmt, 1), iv, true))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
return false;
iv->base = expand_simple_operations (iv->base);
/* Finds general ivs in statement STMT. */
static void
-find_givs_in_stmt (struct ivopts_data *data, tree stmt)
+find_givs_in_stmt (struct ivopts_data *data, gimple stmt)
{
affine_iv iv;
if (!find_givs_in_stmt_scev (data, stmt, &iv))
return;
- set_iv (data, GIMPLE_STMT_OPERAND (stmt, 0), iv.base, iv.step);
+ set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
static void
find_givs_in_bb (struct ivopts_data *data, basic_block bb)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_givs_in_stmt (data, bsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_givs_in_stmt (data, gsi_stmt (bsi));
}
/* Finds general ivs. */
static struct iv_use *
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
- tree stmt, enum use_type use_type)
+ gimple stmt, enum use_type use_type)
{
struct iv_use *use = XCNEW (struct iv_use);
|| !is_gimple_reg (op))
return;
- bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
+ bb = gimple_bb (SSA_NAME_DEF_STMT (op));
if (bb
&& flow_bb_inside_loop_p (data->current_loop, bb))
return;
{
struct iv *iv;
struct iv *civ;
- tree stmt;
+ gimple stmt;
struct iv_use *use;
if (TREE_CODE (op) != SSA_NAME)
*civ = *iv;
stmt = SSA_NAME_DEF_STMT (op);
- gcc_assert (TREE_CODE (stmt) == PHI_NODE
- || TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
+ gcc_assert (gimple_code (stmt) == GIMPLE_PHI
+ || is_gimple_assign (stmt));
use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
iv->use_id = use->id;
return use;
}
-/* Given a condition *COND_P, checks whether it is a compare of an induction
- variable and an invariant. If this is the case, CONTROL_VAR is set
- to location of the iv, BOUND to the location of the invariant,
- IV_VAR and IV_BOUND are set to the corresponding induction variable
- descriptions, and true is returned. If this is not the case,
- CONTROL_VAR and BOUND are set to the arguments of the condition and
- false is returned. */
+/* Given a condition in statement STMT, checks whether it is a compare
+ of an induction variable and an invariant. If this is the case,
+ CONTROL_VAR is set to location of the iv, BOUND to the location of
+ the invariant, IV_VAR and IV_BOUND are set to the corresponding
+ induction variable descriptions, and true is returned. If this is not
+ the case, CONTROL_VAR and BOUND are set to the arguments of the
+ condition and false is returned. */
static bool
-extract_cond_operands (struct ivopts_data *data, tree *cond_p,
+extract_cond_operands (struct ivopts_data *data, gimple stmt,
tree **control_var, tree **bound,
struct iv **iv_var, struct iv **iv_bound)
{
- /* The nodes returned when COND has just one operand. Note that you should
- not modify anything in BOUND or IV_BOUND because of this. */
+ /* The objects returned when COND has constant operands. */
static struct iv const_iv;
static tree zero;
- tree cond = *cond_p;
tree *op0 = &zero, *op1 = &zero, *tmp_op;
struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
bool ret = false;
- zero = integer_zero_node;
- const_iv.step = integer_zero_node;
-
- if (TREE_CODE (cond) == SSA_NAME)
+ if (gimple_code (stmt) == GIMPLE_COND)
{
- op0 = cond_p;
- iv0 = get_iv (data, cond);
- ret = (iv0 && !integer_zerop (iv0->step));
- goto end;
+ op0 = gimple_cond_lhs_ptr (stmt);
+ op1 = gimple_cond_rhs_ptr (stmt);
}
-
- if (!COMPARISON_CLASS_P (cond))
+ else
{
- op0 = cond_p;
- goto end;
+ op0 = gimple_assign_rhs1_ptr (stmt);
+ op1 = gimple_assign_rhs2_ptr (stmt);
}
- op0 = &TREE_OPERAND (cond, 0);
- op1 = &TREE_OPERAND (cond, 1);
+ zero = integer_zero_node;
+ const_iv.step = integer_zero_node;
+
if (TREE_CODE (*op0) == SSA_NAME)
iv0 = get_iv (data, *op0);
if (TREE_CODE (*op1) == SSA_NAME)
return ret;
}
-/* Checks whether the condition *COND_P in STMT is interesting
- and if so, records it. */
+/* Checks whether the condition in STMT is interesting and if so,
+ records it. */
static void
-find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+find_interesting_uses_cond (struct ivopts_data *data, gimple stmt)
{
tree *var_p, *bound_p;
struct iv *var_iv, *civ;
- if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
+ if (!extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL))
{
find_interesting_uses_op (data, *var_p);
find_interesting_uses_op (data, *bound_p);
civ = XNEW (struct iv);
*civ = *var_iv;
- record_use (data, cond_p, civ, stmt, USE_COMPARE);
+ record_use (data, NULL, civ, stmt, USE_COMPARE);
}
/* Returns true if expression EXPR is obviously invariant in LOOP,
if (TREE_CODE (expr) == SSA_NAME)
{
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return false;
return true;
}
- if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
+ if (!EXPR_P (expr))
return false;
len = TREE_OPERAND_LENGTH (expr);
return true;
}
+/* Returns true if statement STMT is obviously invariant in LOOP,
+ i.e. if all its operands on the RHS are defined outside of the LOOP.
+ LOOP should not be the function body. */
+
+bool
+stmt_invariant_in_loop_p (struct loop *loop, gimple stmt)
+{
+ unsigned i;
+ tree lhs;
+
+ gcc_assert (loop_depth (loop) > 0);
+
+ lhs = gimple_get_lhs (stmt);
+ for (i = 0; i < gimple_num_ops (stmt); i++)
+ {
+ tree op = gimple_op (stmt, i);
+ if (op != lhs && !expr_invariant_in_loop_p (loop, op))
+ return false;
+ }
+
+ return true;
+}
+
/* Cumulates the steps of indices into DATA and replaces their values with the
initial ones. Returns false when the value of the index cannot be determined.
Callback for for_each_index. */
struct ifs_ivopts_data
{
struct ivopts_data *ivopts_data;
- tree stmt;
+ gimple stmt;
tree step;
};
reference out of the loop (in order to take its address in strength
reduction). In order for this to work we need both lower bound
and step to be loop invariants. */
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
+ /* Moreover, for a range, the size needs to be invariant as well. */
+ if (TREE_CODE (base) == ARRAY_RANGE_REF
+ && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))))
+ return false;
+
step = array_ref_element_size (base);
lbound = array_ref_low_bound (base);
if (integer_zerop (iv->step))
return true;
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
step = array_ref_element_size (base);
{
struct ivopts_data *data = (struct ivopts_data *) vdata;
find_interesting_uses_op (data, *idx);
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
find_interesting_uses_op (data, array_ref_element_size (base));
find_interesting_uses_op (data, array_ref_low_bound (base));
non-addressability may be uncovered again, causing ADDR_EXPRs
of inappropriate objects to be built. */
if (is_gimple_reg (TREE_OPERAND (expr, 0))
- || is_gimple_min_invariant (TREE_OPERAND (expr, 0)))
+ || !is_gimple_addressable (TREE_OPERAND (expr, 0)))
return true;
/* ... fall through ... */
case ARRAY_RANGE_REF:
return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
- case CONVERT_EXPR:
- case NON_LVALUE_EXPR:
- case NOP_EXPR:
+ CASE_CONVERT:
return true;
default:
/* Finds addresses in *OP_P inside STMT. */
static void
-find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
+find_interesting_uses_address (struct ivopts_data *data, gimple stmt, tree *op_p)
{
tree base = *op_p, step = build_int_cst (sizetype, 0);
struct iv *civ;
/* Do not play with volatile memory references. A bit too conservative,
perhaps, but safe. */
- if (stmt_ann (stmt)->has_volatile_ops)
+ if (gimple_has_volatile_ops (stmt))
goto fail;
/* Ignore bitfields for now. Not really something terribly complicated
/* Finds and records invariants used in STMT. */
static void
-find_invariants_stmt (struct ivopts_data *data, tree stmt)
+find_invariants_stmt (struct ivopts_data *data, gimple stmt)
{
ssa_op_iter iter;
use_operand_p use_p;
/* Finds interesting uses of induction variables in the statement STMT. */
static void
-find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
+find_interesting_uses_stmt (struct ivopts_data *data, gimple stmt)
{
struct iv *iv;
- tree op, lhs, rhs;
+ tree op, *lhs, *rhs;
ssa_op_iter iter;
use_operand_p use_p;
+ enum tree_code code;
find_invariants_stmt (data, stmt);
- if (TREE_CODE (stmt) == COND_EXPR)
+ if (gimple_code (stmt) == GIMPLE_COND)
{
- find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
+ find_interesting_uses_cond (data, stmt);
return;
}
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ if (is_gimple_assign (stmt))
{
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ lhs = gimple_assign_lhs_ptr (stmt);
+ rhs = gimple_assign_rhs1_ptr (stmt);
- if (TREE_CODE (lhs) == SSA_NAME)
+ if (TREE_CODE (*lhs) == SSA_NAME)
{
/* If the statement defines an induction variable, the uses are not
interesting by themselves. */
- iv = get_iv (data, lhs);
+ iv = get_iv (data, *lhs);
if (iv && !integer_zerop (iv->step))
return;
}
- switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
+ code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+ && (REFERENCE_CLASS_P (*rhs)
+ || is_gimple_val (*rhs)))
{
- case tcc_comparison:
- find_interesting_uses_cond (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 1));
- return;
+ if (REFERENCE_CLASS_P (*rhs))
+ find_interesting_uses_address (data, stmt, rhs);
+ else
+ find_interesting_uses_op (data, *rhs);
- case tcc_reference:
- find_interesting_uses_address (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 1));
- if (REFERENCE_CLASS_P (lhs))
- find_interesting_uses_address (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 0));
+ if (REFERENCE_CLASS_P (*lhs))
+ find_interesting_uses_address (data, stmt, lhs);
return;
-
- default: ;
}
-
- if (REFERENCE_CLASS_P (lhs)
- && is_gimple_val (rhs))
+ else if (TREE_CODE_CLASS (code) == tcc_comparison)
{
- find_interesting_uses_address (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 0));
- find_interesting_uses_op (data, rhs);
+ find_interesting_uses_cond (data, stmt);
return;
}
call (memory). */
}
- if (TREE_CODE (stmt) == PHI_NODE
- && bb_for_stmt (stmt) == data->current_loop->header)
+ if (gimple_code (stmt) == GIMPLE_PHI
+ && gimple_bb (stmt) == data->current_loop->header)
{
- lhs = PHI_RESULT (stmt);
- iv = get_iv (data, lhs);
+ iv = get_iv (data, PHI_RESULT (stmt));
if (iv && !integer_zerop (iv->step))
return;
static void
find_interesting_uses_outside (struct ivopts_data *data, edge exit)
{
- tree phi, def;
+ gimple phi;
+ gimple_stmt_iterator psi;
+ tree def;
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
if (is_gimple_reg (def))
find_interesting_uses_op (data, def);
find_interesting_uses (struct ivopts_data *data)
{
basic_block bb;
- block_stmt_iterator bsi;
- tree phi;
+ gimple_stmt_iterator bsi;
basic_block *body = get_loop_body (data->current_loop);
unsigned i;
struct version_info *info;
&& !flow_bb_inside_loop_p (data->current_loop, e->dest))
find_interesting_uses_outside (data, e);
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- find_interesting_uses_stmt (data, phi);
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_interesting_uses_stmt (data, bsi_stmt (bsi));
+ for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
}
if (dump_file && (dump_flags & TDF_DETAILS))
return fold_convert (orig_type, expr);
+ case MULT_EXPR:
+ op1 = TREE_OPERAND (expr, 1);
+ if (!cst_and_fits_in_hwi (op1))
+ return orig_expr;
+
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, false, false, &off0);
+ if (op0 == TREE_OPERAND (expr, 0))
+ return orig_expr;
+
+ *offset = off0 * int_cst_value (op1);
+ if (integer_zerop (op0))
+ expr = op0;
+ else
+ expr = fold_build2 (MULT_EXPR, type, op0, op1);
+
+ return fold_convert (orig_type, expr);
+
case ARRAY_REF:
+ case ARRAY_RANGE_REF:
if (!inside_addr)
return orig_expr;
static struct iv_cand *
add_candidate_1 (struct ivopts_data *data,
tree base, tree step, bool important, enum iv_position pos,
- struct iv_use *use, tree incremented_at)
+ struct iv_use *use, gimple incremented_at)
{
unsigned i;
struct iv_cand *cand = NULL;
{
orig_type = TREE_TYPE (base);
type = generic_type_for (orig_type);
- /* Don't convert the base to the generic type for pointers as the generic
- type is an integer type with the same size as the pointer type. */
- if (type != orig_type && !POINTER_TYPE_P (orig_type))
+ if (type != orig_type)
{
base = fold_convert (type, base);
step = fold_convert (type, step);
tree base, tree step, bool important, struct iv_use *use)
{
if (ip_normal_pos (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
+ add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL);
if (ip_end_pos (data->current_loop)
&& allow_ip_end_pos_p (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
+ add_candidate_1 (data, base, step, important, IP_END, use, NULL);
}
/* Add a standard "0 + 1 * iteration" iv candidate for a
static void
add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
{
- tree phi, def;
+ gimple phi;
+ tree def;
struct iv_cand *cand;
add_candidate (data, iv->base, iv->step, true, NULL);
/* The same, but with initial value zero. */
- add_candidate (data,
- build_int_cst (TREE_TYPE (iv->base), 0),
- iv->step, true, NULL);
+ if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
+ add_candidate (data, size_int (0), iv->step, true, NULL);
+ else
+ add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
+ iv->step, true, NULL);
phi = SSA_NAME_DEF_STMT (iv->ssa_name);
- if (TREE_CODE (phi) == PHI_NODE)
+ if (gimple_code (phi) == GIMPLE_PHI)
{
/* Additionally record the possibility of leaving the original iv
untouched. */
add_candidate (data, build_int_cst (basetype, 0),
iv->step, true, use);
- /* Third, try removing the constant offset. */
+ /* Third, try removing the constant offset. Make sure to even
+ add a candidate for &a[0] vs. (T *)&a. */
base = strip_offset (iv->base, &offset);
- if (offset)
+ if (offset
+ || base != iv->base)
add_candidate (data, base, iv->step, false, use);
}
/* Returns estimate on cost of computing SEQ. */
static unsigned
-seq_cost (rtx seq)
+seq_cost (rtx seq, bool speed)
{
unsigned cost = 0;
rtx set;
{
set = single_set (seq);
if (set)
- cost += rtx_cost (set, SET);
+ cost += rtx_cost (set, SET,speed);
else
cost++;
}
/* Determines cost of the computation of EXPR. */
static unsigned
-computation_cost (tree expr)
+computation_cost (tree expr, bool speed)
{
rtx seq, rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
/* Avoid using hard regs in ways which may be unsupported. */
int regno = LAST_VIRTUAL_REGISTER + 1;
+ enum function_frequency real_frequency = cfun->function_frequency;
+ cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
+ crtl->maybe_hot_insn_p = speed;
walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
start_sequence ();
rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
seq = get_insns ();
end_sequence ();
+ default_rtl_profile ();
+ cfun->function_frequency = real_frequency;
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (MEM_P (rslt))
- cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
+ cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type), speed);
return cost;
}
/* Returns variable containing the value of candidate CAND at statement AT. */
static tree
-var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
+var_at_stmt (struct loop *loop, struct iv_cand *cand, gimple stmt)
{
if (stmt_after_increment (loop, cand, stmt))
return cand->var_after;
tree suba, subb;
tree atype = TREE_TYPE (*a);
- if ((TREE_CODE (*a) == NOP_EXPR
- || TREE_CODE (*a) == CONVERT_EXPR))
+ if (CONVERT_EXPR_P (*a))
{
suba = TREE_OPERAND (*a, 0);
wider_type = TREE_TYPE (suba);
else
return atype;
- if ((TREE_CODE (*b) == NOP_EXPR
- || TREE_CODE (*b) == CONVERT_EXPR))
+ if (CONVERT_EXPR_P (*b))
{
subb = TREE_OPERAND (*b, 0);
if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
static bool
get_computation_aff (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at,
+ struct iv_use *use, struct iv_cand *cand, gimple at,
struct affine_tree_combination *aff)
{
tree ubase = use->iv->base;
static tree
get_computation_at (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at)
+ struct iv_use *use, struct iv_cand *cand, gimple at)
{
aff_tree aff;
tree type = TREE_TYPE (use->iv->base);
/* Returns cost of addition in MODE. */
static unsigned
-add_cost (enum machine_mode mode)
+add_cost (enum machine_mode mode, bool speed)
{
static unsigned costs[NUM_MACHINE_MODES];
rtx seq;
seq = get_insns ();
end_sequence ();
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (!cost)
cost = 1;
/* Returns cost of multiplication by constant CST in MODE. */
unsigned
-multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
+multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
{
static htab_t costs;
struct mbc_entry **cached, act;
seq = get_insns ();
end_sequence ();
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
static comp_cost
get_address_cost (bool symbol_present, bool var_present,
unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
- enum machine_mode mem_mode)
+ enum machine_mode mem_mode,
+ bool speed)
{
static bool initialized[MAX_MACHINE_MODE];
static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
{
base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
/* ??? We can run into trouble with some backends by presenting
- it with symbols which havn't been properly passed through
+ it with symbols which haven't been properly passed through
targetm.encode_section_info. By setting the local bit, we
enhance the probability of things working. */
SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
seq = get_insns ();
end_sequence ();
- acost = seq_cost (seq);
- acost += address_cost (addr, mem_mode);
+ acost = seq_cost (seq, speed);
+ acost += address_cost (addr, mem_mode, speed);
if (!acost)
acost = 1;
If VAR_PRESENT is true, try whether the mode with
SYMBOL_PRESENT = false is cheaper even with cost of addition, and
if this is the case, use it. */
- add_c = add_cost (Pmode);
+ add_c = add_cost (Pmode, speed);
for (i = 0; i < 8; i++)
{
var_p = i & 1;
&& multiplier_allowed_in_address_p (ratio, mem_mode));
if (ratio != 1 && !ratio_p)
- cost += multiply_by_cost (ratio, Pmode);
+ cost += multiply_by_cost (ratio, Pmode, speed);
if (s_offset && !offset_p && !symbol_present)
- cost += add_cost (Pmode);
+ cost += add_cost (Pmode, speed);
acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
/* Estimates cost of forcing expression EXPR into a variable. */
static comp_cost
-force_expr_to_var_cost (tree expr)
+force_expr_to_var_cost (tree expr, bool speed)
{
static bool costs_initialized = false;
- static unsigned integer_cost;
- static unsigned symbol_cost;
- static unsigned address_cost;
+ static unsigned integer_cost [2];
+ static unsigned symbol_cost [2];
+ static unsigned address_cost [2];
tree op0, op1;
comp_cost cost0, cost1, cost;
enum machine_mode mode;
tree type = build_pointer_type (integer_type_node);
tree var, addr;
rtx x;
+ int i;
var = create_tmp_var_raw (integer_type_node, "test_var");
TREE_STATIC (var) = 1;
x = produce_memory_decl_rtl (var, NULL);
SET_DECL_RTL (var, x);
- integer_cost = computation_cost (build_int_cst (integer_type_node,
- 2000));
-
addr = build1 (ADDR_EXPR, type, var);
- symbol_cost = computation_cost (addr) + 1;
- address_cost
- = computation_cost (build2 (POINTER_PLUS_EXPR, type,
- addr,
- build_int_cst (sizetype, 2000))) + 1;
- if (dump_file && (dump_flags & TDF_DETAILS))
+
+ for (i = 0; i < 2; i++)
{
- 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);
- fprintf (dump_file, " other %d\n", (int) target_spill_cost);
- fprintf (dump_file, "\n");
+ integer_cost[i] = computation_cost (build_int_cst (integer_type_node,
+ 2000), i);
+
+ symbol_cost[i] = computation_cost (addr, i) + 1;
+
+ address_cost[i]
+ = computation_cost (build2 (POINTER_PLUS_EXPR, type,
+ addr,
+ build_int_cst (sizetype, 2000)), i) + 1;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
+ fprintf (dump_file, " integer %d\n", (int) integer_cost[i]);
+ fprintf (dump_file, " symbol %d\n", (int) symbol_cost[i]);
+ fprintf (dump_file, " address %d\n", (int) address_cost[i]);
+ fprintf (dump_file, " other %d\n", (int) target_spill_cost[i]);
+ fprintf (dump_file, "\n");
+ }
}
costs_initialized = true;
if (is_gimple_min_invariant (expr))
{
if (TREE_CODE (expr) == INTEGER_CST)
- return new_cost (integer_cost, 0);
+ return new_cost (integer_cost [speed], 0);
if (TREE_CODE (expr) == ADDR_EXPR)
{
if (TREE_CODE (obj) == VAR_DECL
|| TREE_CODE (obj) == PARM_DECL
|| TREE_CODE (obj) == RESULT_DECL)
- return new_cost (symbol_cost, 0);
+ return new_cost (symbol_cost [speed], 0);
}
- return new_cost (address_cost, 0);
+ return new_cost (address_cost [speed], 0);
}
switch (TREE_CODE (expr))
if (is_gimple_val (op0))
cost0 = zero_cost;
else
- cost0 = force_expr_to_var_cost (op0);
+ cost0 = force_expr_to_var_cost (op0, speed);
if (is_gimple_val (op1))
cost1 = zero_cost;
else
- cost1 = force_expr_to_var_cost (op1);
+ cost1 = force_expr_to_var_cost (op1, speed);
+
+ break;
+
+ case NEGATE_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ STRIP_NOPS (op0);
+ op1 = NULL_TREE;
+
+ if (is_gimple_val (op0))
+ cost0 = zero_cost;
+ else
+ cost0 = force_expr_to_var_cost (op0, speed);
+ cost1 = zero_cost;
break;
default:
/* Just an arbitrary value, FIXME. */
- return new_cost (target_spill_cost, 0);
+ return new_cost (target_spill_cost[speed], 0);
}
mode = TYPE_MODE (TREE_TYPE (expr));
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
- cost = new_cost (add_cost (mode), 0);
+ case NEGATE_EXPR:
+ cost = new_cost (add_cost (mode, speed), 0);
break;
case MULT_EXPR:
if (cst_and_fits_in_hwi (op0))
- cost = new_cost (multiply_by_cost (int_cst_value (op0), mode), 0);
- else if (cst_and_fits_in_hwi (op1))
- cost = new_cost (multiply_by_cost (int_cst_value (op1), mode), 0);
+ cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
+ 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, 0);
+ return new_cost (target_spill_cost [speed], 0);
break;
default:
computations often are either loop invariant or at least can
be shared between several iv uses, so letting this grow without
limits would not give reasonable results. */
- if (cost.cost > target_spill_cost)
- cost.cost = target_spill_cost;
+ if (cost.cost > target_spill_cost [speed])
+ cost.cost = target_spill_cost [speed];
return cost;
}
walk_tree (&expr, find_depends, depends_on, NULL);
}
- return force_expr_to_var_cost (expr);
+ return force_expr_to_var_cost (expr, data->speed);
}
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
*var_present = true;
fd_ivopts_data = data;
walk_tree (&addr, find_depends, depends_on, NULL);
- return new_cost (target_spill_cost, 0);
+ return new_cost (target_spill_cost[data->speed], 0);
}
*offset += bitpos / BITS_PER_UNIT;
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
HOST_WIDE_INT diff = 0;
- comp_cost cost;
+ aff_tree aff_e1, aff_e2;
+ tree type;
gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
*symbol_present = false;
*var_present = true;
-
- cost = force_var_cost (data, e1, depends_on);
- cost = add_costs (cost, force_var_cost (data, e2, depends_on));
- cost.cost += add_cost (Pmode);
- return cost;
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
+
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Estimates cost of expressing difference E1 - E2 as
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- comp_cost cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
+ aff_tree aff_e1, aff_e2;
+ tree type;
e1 = strip_offset (e1, &off1);
e2 = strip_offset (e2, &off2);
STRIP_NOPS (e2);
if (TREE_CODE (e1) == ADDR_EXPR)
- return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
- depends_on);
+ return ptr_difference_cost (data, e1, e2, symbol_present, var_present,
+ offset, depends_on);
*symbol_present = false;
if (operand_equal_p (e1, e2, 0))
*var_present = false;
return zero_cost;
}
+
*var_present = true;
+
if (integer_zerop (e2))
return force_var_cost (data, e1, depends_on);
if (integer_zerop (e1))
{
- cost = force_var_cost (data, e2, depends_on);
- cost.cost += multiply_by_cost (-1, mode);
-
+ comp_cost cost = force_var_cost (data, e2, depends_on);
+ cost.cost += multiply_by_cost (-1, mode, data->speed);
return cost;
}
- cost = force_var_cost (data, e1, depends_on);
- cost = add_costs (cost, force_var_cost (data, e2, depends_on));
- cost.cost += add_cost (mode);
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
- return cost;
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Determines the cost of the computation by that USE is expressed
static comp_cost
get_computation_cost_at (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on, tree at)
+ bool address_p, bitmap *depends_on, gimple at)
{
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
HOST_WIDE_INT ratio, aratio;
bool var_present, symbol_present;
comp_cost cost;
- unsigned n_sums;
double_int rat;
+ bool speed = optimize_bb_for_speed_p (gimple_bb (at));
*depends_on = NULL;
return infinite_cost;
}
- if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
else
return infinite_cost;
+ STRIP_NOPS (cbase);
+ ctype = TREE_TYPE (cbase);
+
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
&symbol_present, &var_present, &offset,
depends_on);
}
+ else if (address_p
+ && !POINTER_TYPE_P (ctype)
+ && multiplier_allowed_in_address_p (ratio,
+ TYPE_MODE (TREE_TYPE (utype))))
+ {
+ cbase
+ = fold_build2 (MULT_EXPR, ctype, cbase, build_int_cst (ctype, ratio));
+ cost = difference_cost (data,
+ ubase, cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
+ }
else
{
cost = force_var_cost (data, cbase, depends_on);
- cost.cost += add_cost (TYPE_MODE (ctype));
+ cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
cost = add_costs (cost,
difference_cost (data,
ubase, build_int_cst (utype, 0),
offset -= ratio * cstepi;
/* Now the computation is in shape symbol + var1 + const + ratio * var2.
- (symbol/var/const parts may be omitted). If we are looking for an address,
- find the cost of addressing this. */
+ (symbol/var1/const parts may be omitted). If we are looking for an
+ address, find the cost of addressing this. */
if (address_p)
- return add_costs (cost, get_address_cost (symbol_present, var_present,
- offset, ratio,
- TYPE_MODE (TREE_TYPE (*use->op_p))));
+ return add_costs (cost,
+ get_address_cost (symbol_present, var_present,
+ offset, ratio,
+ TYPE_MODE (TREE_TYPE (utype)), speed));
/* Otherwise estimate the costs for computing the expression. */
- aratio = ratio > 0 ? ratio : -ratio;
if (!symbol_present && !var_present && !offset)
{
if (ratio != 1)
- cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
-
+ cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
return cost;
}
- if (aratio != 1)
- cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
-
- n_sums = 1;
- if (var_present
- /* Symbol + offset should be compile-time computable. */
- && (symbol_present || offset))
- n_sums++;
+ /* Symbol + offset should be compile-time computable so consider that they
+ are added once to the variable, if present. */
+ if (var_present && (symbol_present || offset))
+ cost.cost += add_cost (TYPE_MODE (ctype), speed)
+ / AVG_LOOP_NITER (data->current_loop);
/* Having offset does not affect runtime cost in case it is added to
symbol, but it increases complexity. */
if (offset)
cost.complexity++;
- cost.cost += n_sums * add_cost (TYPE_MODE (ctype));
- return cost;
+ cost.cost += add_cost (TYPE_MODE (ctype), speed);
+
+ aratio = ratio > 0 ? ratio : -ratio;
+ if (aratio != 1)
+ cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
fallback:
{
if (address_p)
comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
- return new_cost (computation_cost (comp), 0);
+ return new_cost (computation_cost (comp, speed), 0);
}
}
stores it to VAL. */
static void
-cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter,
+cand_value_at (struct loop *loop, struct iv_cand *cand, gimple at, tree niter,
aff_tree *val)
{
aff_tree step, delta, nit;
basic_block ex_bb;
edge exit;
- ex_bb = bb_for_stmt (use->stmt);
+ ex_bb = gimple_bb (use->stmt);
exit = EDGE_SUCC (ex_bb, 0);
if (flow_bb_inside_loop_p (loop, exit->dest))
exit = EDGE_SUCC (ex_bb, 1);
tree nit, period;
struct loop *loop = data->current_loop;
aff_tree bnd;
- double_int period_value, max_niter;
if (TREE_CODE (cand->iv->step) != INTEGER_CST)
return false;
- /* For now works only for exits that dominate the loop latch. TODO -- extend
- for other conditions inside loop body. */
- ex_bb = bb_for_stmt (use->stmt);
+ /* For now works only for exits that dominate the loop latch.
+ TODO: extend to other conditions inside loop body. */
+ ex_bb = gimple_bb (use->stmt);
if (use->stmt != last_stmt (ex_bb)
- || TREE_CODE (use->stmt) != COND_EXPR)
- return false;
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
+ || gimple_code (use->stmt) != GIMPLE_COND
+ || !dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
return false;
exit = EDGE_SUCC (ex_bb, 0);
if (!nit)
return false;
- /* Determine whether we may use the variable to test whether niter iterations
- elapsed. This is the case iff the period of the induction variable is
- greater than the number of iterations. */
+ /* Determine whether we can use the variable to test the exit condition.
+ This is the case iff the period of the induction variable is greater
+ than the number of iterations for which the exit condition is true. */
period = iv_period (cand->iv);
- if (!period)
- return false;
- /* Compare the period with the estimate on the number of iterations of the
- loop. */
- if (!estimated_loop_iterations (loop, true, &max_niter))
- return false;
- period_value = tree_to_double_int (period);
- if (double_int_ucmp (period_value, max_niter) <= 0)
+ /* If the number of iterations is constant, compare against it directly. */
+ if (TREE_CODE (nit) == INTEGER_CST)
+ {
+ if (!tree_int_cst_lt (nit, period))
+ return false;
+ }
+
+ /* If not, and if this is the only possible exit of the loop, see whether
+ we can get a conservative estimate on the number of iterations of the
+ entire loop and compare against that instead. */
+ else if (loop_only_exit_p (loop, exit))
+ {
+ double_int period_value, max_niter;
+ if (!estimated_loop_iterations (loop, true, &max_niter))
+ return false;
+ period_value = tree_to_double_int (period);
+ if (double_int_ucmp (max_niter, period_value) >= 0)
+ return false;
+ }
+
+ /* Otherwise, punt. */
+ else
return false;
cand_value_at (loop, cand, use->stmt, nit, &bnd);
+
*bound = aff_combination_to_tree (&bnd);
+ /* It is unlikely that computing the number of iterations using division
+ would be more profitable than keeping the original induction variable. */
+ if (expression_expensive_p (*bound))
+ return false;
return true;
}
/* 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->op_p, NULL, NULL, NULL, &cmp_iv);
+ ok = extract_cond_operands (data, use->stmt, NULL, NULL, NULL, &cmp_iv);
gcc_assert (ok);
express_cost = get_computation_cost (data, use, cand, false,
fd_ivopts_data = data;
walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
- /* Choose the better approach. */
- if (compare_costs (elim_cost, express_cost) < 0)
+ /* Choose the better approach, preferring the eliminated IV. */
+ if (compare_costs (elim_cost, express_cost) <= 0)
{
cost = elim_cost;
depends_on = depends_on_elim;
base = cand->iv->base;
cost_base = force_var_cost (data, base, NULL);
- cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
+ cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
cost = cost_step + cost_base.cost / AVG_LOOP_NITER (current_loop);
/* Prefer the original ivs unless we may gain something by replacing it.
- The reason is to makee debugging simpler; so this is not relevant for
+ The reason is to make debugging simpler; so this is not relevant for
artificial ivs created by other optimization passes. */
if (cand->pos != IP_ORIGINAL
|| DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
{
/* We add size to the cost, so that we prefer eliminating ivs
if possible. */
- return size + estimate_reg_pressure_cost (size, data->regs_used);
+ return size + estimate_reg_pressure_cost (size, data->regs_used, data->speed);
}
/* For each size of the induction variable set determine the penalty. */
determine_set_costs (struct ivopts_data *data)
{
unsigned j, n;
- tree phi, op;
+ gimple phi;
+ gimple_stmt_iterator psi;
+ tree op;
struct loop *loop = data->current_loop;
bitmap_iterator bi;
{
fprintf (dump_file, "Global costs:\n");
fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
- fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost);
- fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
+ fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost[data->speed]);
+ fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost[data->speed]);
}
n = 0;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
op = PHI_RESULT (phi);
if (!is_gimple_reg (op))
static comp_cost
iv_ca_cost (struct iv_ca *ivs)
{
- return (ivs->bad_uses ? infinite_cost : ivs->cost);
+ /* This was a conditional expression but it triggered a bug in
+ Sun C 5.5. */
+ if (ivs->bad_uses)
+ return infinite_cost;
+ else
+ return ivs->cost;
}
/* Returns true if all dependences of CP are among invariants in IVS. */
static void
create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
{
- block_stmt_iterator incr_pos;
+ gimple_stmt_iterator incr_pos;
tree base;
bool after = false;
switch (cand->pos)
{
case IP_NORMAL:
- incr_pos = bsi_last (ip_normal_pos (data->current_loop));
+ incr_pos = gsi_last_bb (ip_normal_pos (data->current_loop));
break;
case IP_END:
- incr_pos = bsi_last (ip_end_pos (data->current_loop));
+ incr_pos = gsi_last_bb (ip_end_pos (data->current_loop));
after = true;
break;
}
}
+/* Returns the phi-node in BB with result RESULT. */
+
+static gimple
+get_phi_with_result (basic_block bb, tree result)
+{
+ gimple_stmt_iterator i = gsi_start_phis (bb);
+
+ for (; !gsi_end_p (i); gsi_next (&i))
+ if (gimple_phi_result (gsi_stmt (i)) == result)
+ return gsi_stmt (i);
+
+ gcc_unreachable ();
+ return NULL;
+}
+
+
/* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
is true, remove also the ssa name defined by the statement. */
static void
-remove_statement (tree stmt, bool including_defined_name)
+remove_statement (gimple stmt, bool including_defined_name)
{
- if (TREE_CODE (stmt) == PHI_NODE)
+ if (gimple_code (stmt) == GIMPLE_PHI)
{
- remove_phi_node (stmt, NULL_TREE, including_defined_name);
+ gimple bb_phi = get_phi_with_result (gimple_bb (stmt),
+ gimple_phi_result (stmt));
+ gimple_stmt_iterator bsi = gsi_for_stmt (bb_phi);
+ remove_phi_node (&bsi, including_defined_name);
}
else
{
- block_stmt_iterator bsi = bsi_for_stmt (stmt);
-
- bsi_remove (&bsi, true);
+ gimple_stmt_iterator bsi = gsi_for_stmt (stmt);
+ gsi_remove (&bsi, true);
release_defs (stmt);
}
}
struct iv_use *use, struct iv_cand *cand)
{
tree comp;
- tree op, tgt, ass;
- block_stmt_iterator bsi;
+ tree op, tgt;
+ gimple ass;
+ gimple_stmt_iterator bsi;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
&& cand->incremented_at == use->stmt)
{
tree step, ctype, utype;
- enum tree_code incr_code = PLUS_EXPR;
+ enum tree_code incr_code = PLUS_EXPR, old_code;
- gcc_assert (TREE_CODE (use->stmt) == GIMPLE_MODIFY_STMT);
- gcc_assert (GIMPLE_STMT_OPERAND (use->stmt, 0) == cand->var_after);
+ gcc_assert (is_gimple_assign (use->stmt));
+ gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
step = cand->iv->step;
ctype = TREE_TYPE (step);
computations in the loop -- otherwise, the computation
we rely upon may be removed in remove_unused_ivs,
thus leading to ICE. */
- op = GIMPLE_STMT_OPERAND (use->stmt, 1);
- if (TREE_CODE (op) == PLUS_EXPR
- || TREE_CODE (op) == MINUS_EXPR
- || TREE_CODE (op) == POINTER_PLUS_EXPR)
+ old_code = gimple_assign_rhs_code (use->stmt);
+ if (old_code == PLUS_EXPR
+ || old_code == MINUS_EXPR
+ || old_code == POINTER_PLUS_EXPR)
{
- if (TREE_OPERAND (op, 0) == cand->var_before)
- op = TREE_OPERAND (op, 1);
- else if (TREE_CODE (op) != MINUS_EXPR
- && TREE_OPERAND (op, 1) == cand->var_before)
- op = TREE_OPERAND (op, 0);
+ if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs2 (use->stmt);
+ else if (old_code != MINUS_EXPR
+ && gimple_assign_rhs2 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs1 (use->stmt);
else
op = NULL_TREE;
}
gcc_assert (comp != NULL_TREE);
}
- switch (TREE_CODE (use->stmt))
+ switch (gimple_code (use->stmt))
{
- case PHI_NODE:
+ case GIMPLE_PHI:
tgt = PHI_RESULT (use->stmt);
/* If we should keep the biv, do not replace it. */
if (name_info (data, tgt)->preserve_biv)
return;
- bsi = bsi_after_labels (bb_for_stmt (use->stmt));
+ bsi = gsi_after_labels (gimple_bb (use->stmt));
break;
- case GIMPLE_MODIFY_STMT:
- tgt = GIMPLE_STMT_OPERAND (use->stmt, 0);
- bsi = bsi_for_stmt (use->stmt);
+ case GIMPLE_ASSIGN:
+ tgt = gimple_assign_lhs (use->stmt);
+ bsi = gsi_for_stmt (use->stmt);
break;
default:
gcc_unreachable ();
}
- op = force_gimple_operand_bsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
- true, BSI_SAME_STMT);
+ op = force_gimple_operand_gsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
+ true, GSI_SAME_STMT);
- if (TREE_CODE (use->stmt) == PHI_NODE)
+ if (gimple_code (use->stmt) == GIMPLE_PHI)
{
- ass = build_gimple_modify_stmt (tgt, op);
- bsi_insert_before (&bsi, ass, BSI_SAME_STMT);
+ ass = gimple_build_assign (tgt, op);
+ gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
remove_statement (use->stmt, false);
- SSA_NAME_DEF_STMT (tgt) = ass;
}
else
- GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
+ {
+ gimple_assign_set_rhs_from_tree (&bsi, op);
+ use->stmt = gsi_stmt (bsi);
+ }
}
/* Replaces ssa name in index IDX by its basic variable. Callback for
if (TREE_CODE (*idx) == SSA_NAME)
*idx = SSA_NAME_VAR (*idx);
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
op = &TREE_OPERAND (base, 2);
if (*op
return ref;
}
-/* Extract the alias analysis info for the memory reference REF. There are
- several ways how this information may be stored and what precisely is
- its semantics depending on the type of the reference, but there always is
- somewhere hidden one _DECL node that is used to determine the set of
- virtual operands for the reference. The code below deciphers this jungle
- and extracts this single useful piece of information. */
-
-static tree
-get_ref_tag (tree ref, tree orig)
-{
- tree var = get_base_address (ref);
- 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 aref;
-
- if (!var)
- return NULL_TREE;
-
- if (TREE_CODE (var) == INDIRECT_REF)
- {
- /* 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;
- if (tag)
- return tag;
- }
-
- var = SSA_NAME_VAR (var);
- tag = symbol_mem_tag (var);
- gcc_assert (tag != NULL_TREE);
- return tag;
- }
- else
- {
- if (!DECL_P (var))
- return NULL_TREE;
-
- tag = symbol_mem_tag (var);
- if (tag)
- return tag;
-
- return var;
- }
-}
-
/* Copies the reference information from OLD_REF to NEW_REF. */
static void
if (TREE_CODE (old_ref) == TARGET_MEM_REF)
copy_mem_ref_info (new_ref, old_ref);
else
- {
- TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
- TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
- }
+ TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
}
/* Rewrites USE (address that is an iv) using candidate CAND. */
struct iv_use *use, struct iv_cand *cand)
{
aff_tree aff;
- block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
tree ref;
bool ok;
gcc_assert (ok);
unshare_aff_combination (&aff);
- ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
+ ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, data->speed);
copy_ref_info (ref, *use->op_p);
*use->op_p = ref;
}
struct iv_use *use, struct iv_cand *cand)
{
tree comp, *var_p, op, bound;
- block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
enum tree_code compare;
struct cost_pair *cp = get_use_iv_cost (data, use, cand);
bool ok;
{
tree var = var_at_stmt (data->current_loop, cand, use->stmt);
tree var_type = TREE_TYPE (var);
+ gimple_seq stmts;
compare = iv_elimination_compare (data, use);
bound = unshare_expr (fold_convert (var_type, bound));
- op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE,
- true, BSI_SAME_STMT);
-
- *use->op_p = build2 (compare, boolean_type_node, var, op);
+ op = force_gimple_operand (bound, &stmts, true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (
+ loop_preheader_edge (data->current_loop),
+ stmts);
+
+ gimple_cond_set_lhs (use->stmt, var);
+ gimple_cond_set_code (use->stmt, compare);
+ gimple_cond_set_rhs (use->stmt, op);
return;
}
comp = get_computation (data->current_loop, use, cand);
gcc_assert (comp != NULL_TREE);
- ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
+ ok = extract_cond_operands (data, use->stmt, &var_p, NULL, NULL, NULL);
gcc_assert (ok);
- *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
- true, BSI_SAME_STMT);
+ *var_p = force_gimple_operand_gsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
+ true, GSI_SAME_STMT);
}
/* Rewrites USE using candidate CAND. */
static void
rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
{
- push_stmt_changes (&use->stmt);
-
switch (use->type)
{
case USE_NONLINEAR_EXPR:
default:
gcc_unreachable ();
}
-
- pop_stmt_changes (&use->stmt);
+
+ update_stmt (use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
gcc_assert (!data->niters);
data->current_loop = loop;
+ data->speed = optimize_loop_for_speed_p (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
{
fprintf (dump_file, " single exit %d -> %d, exit condition ",
exit->src->index, exit->dest->index);
- print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
+ print_gimple_stmt (dump_file, last_stmt (exit->src), 0, TDF_SLIM);
fprintf (dump_file, "\n");
}