/* Induction variable optimizations.
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
this. */
#define AVG_LOOP_NITER(LOOP) 5
-/* Just to shorten the ugly names. */
-#define EXEC_BINARY nondestructive_fold_binary_to_constant
-#define EXEC_UNARY nondestructive_fold_unary_to_constant
/* Representation of the induction variable. */
struct iv
/* Information attached to loop. */
struct loop_data
{
- struct tree_niter_desc niter;
- /* Number of iterations. */
-
unsigned regs_used; /* Number of registers used. */
};
/* The currently optimized loop. */
struct loop *current_loop;
+ /* Numbers of iterations for all exits of the current loop. */
+ htab_t niters;
+
/* The size of version_info array allocated. */
unsigned version_info_size;
/* The candidates used. */
bitmap cands;
+ /* The number of candidates in the set. */
+ unsigned n_cands;
+
/* Total number of registers needed. */
unsigned n_regs;
#define MAX_CONSIDERED_USES \
((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
+/* If there are at most this number of ivs in the set, try removing unnecessary
+ ivs from the set always. */
+
+#define ALWAYS_PRUNE_CAND_SET_BOUND \
+ ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
+
/* The list of trees for that the decl_rtl field must be reset is stored
here. */
dump_iv (file, use->iv);
- fprintf (file, " related candidates ");
- dump_bitmap (file, use->related_cands);
+ if (use->related_cands)
+ {
+ fprintf (file, " related candidates ");
+ dump_bitmap (file, use->related_cands);
+ }
}
/* Dumps information about the uses to FILE. */
}
}
+/* Element of the table in that we cache the numbers of iterations obtained
+ from exits of the loop. */
+
+struct nfe_cache_elt
+{
+ /* The edge for that the number of iterations is cached. */
+ edge exit;
+
+ /* True if the # of iterations was successfully determined. */
+ bool valid_p;
+
+ /* Description of # of iterations. */
+ struct tree_niter_desc niter;
+};
+
+/* Hash function for nfe_cache_elt E. */
+
+static hashval_t
+nfe_hash (const void *e)
+{
+ const struct nfe_cache_elt *elt = e;
+
+ return htab_hash_pointer (elt->exit);
+}
+
+/* Equality function for nfe_cache_elt E1 and edge E2. */
+
+static int
+nfe_eq (const void *e1, const void *e2)
+{
+ const struct nfe_cache_elt *elt1 = e1;
+
+ return elt1->exit == e2;
+}
+
+/* Returns structure describing number of iterations determined from
+ EXIT of DATA->current_loop, or NULL if something goes wrong. */
+
+static struct tree_niter_desc *
+niter_for_exit (struct ivopts_data *data, edge exit)
+{
+ struct nfe_cache_elt *nfe_desc;
+ PTR *slot;
+
+ slot = htab_find_slot_with_hash (data->niters, exit,
+ htab_hash_pointer (exit),
+ INSERT);
+
+ if (!*slot)
+ {
+ 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);
+ *slot = nfe_desc;
+ }
+ else
+ nfe_desc = *slot;
+
+ if (!nfe_desc->valid_p)
+ return NULL;
+
+ return &nfe_desc->niter;
+}
+
+/* Returns structure describing number of iterations determined from
+ single dominating exit of DATA->current_loop, or NULL if something
+ goes wrong. */
+
+static struct tree_niter_desc *
+niter_for_single_dom_exit (struct ivopts_data *data)
+{
+ edge exit = single_dom_exit (data->current_loop);
+
+ if (!exit)
+ return NULL;
+
+ return niter_for_exit (data, exit);
+}
+
/* Initializes data structures used by the iv optimization pass, stored
in DATA. LOOPS is the loop tree. */
data->version_info_size = 2 * num_ssa_names;
data->version_info = xcalloc (data->version_info_size,
sizeof (struct version_info));
- data->relevant = BITMAP_XMALLOC ();
- data->important_candidates = BITMAP_XMALLOC ();
+ 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])
base = get_base_address (obj);
if (!base)
- return fold_convert (ptr_type_node, expr);
+ return expr;
+
+ if (TREE_CODE (base) == INDIRECT_REF)
+ return determine_base_object (TREE_OPERAND (base, 0));
return fold (build1 (ADDR_EXPR, ptr_type_node, base));
return fold (build (code, ptr_type_node, op0, op1));
+ case NOP_EXPR:
+ case CONVERT_EXPR:
+ return determine_base_object (TREE_OPERAND (expr, 0));
+
default:
return fold_convert (ptr_type_node, expr);
}
return false;
if (code == ADDR_EXPR)
- return !for_each_index (&TREE_OPERAND (expr, 1),
+ return !for_each_index (&TREE_OPERAND (expr, 0),
idx_contains_abnormal_ssa_name_p,
NULL);
free (body);
}
-/* Determine the number of iterations of the current loop. */
-
-static void
-determine_number_of_iterations (struct ivopts_data *data)
-{
- struct loop *loop = data->current_loop;
- edge exit = single_dom_exit (loop);
-
- if (!exit)
- return;
-
- number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
-}
-
/* For each ssa name defined in LOOP determines whether it is an induction
variable and if so, its initial value and step. */
find_induction_variables (struct ivopts_data *data)
{
unsigned i;
- struct loop *loop = data->current_loop;
bitmap_iterator bi;
if (!find_bivs (data))
find_givs (data);
mark_bivs (data);
- determine_number_of_iterations (data);
if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (loop_data (loop)->niter.niter)
+ struct tree_niter_desc *niter;
+
+ niter = niter_for_single_dom_exit (data);
+
+ if (niter)
{
fprintf (dump_file, " number of iterations ");
- print_generic_expr (dump_file, loop_data (loop)->niter.niter,
- TDF_SLIM);
+ print_generic_expr (dump_file, niter->niter, TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, " may be zero if ");
- print_generic_expr (dump_file, loop_data (loop)->niter.may_be_zero,
- TDF_SLIM);
- fprintf (dump_file, "\n");
-
- fprintf (dump_file, " bogus unless ");
- print_generic_expr (dump_file, loop_data (loop)->niter.assumptions,
- TDF_SLIM);
+ print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
};
use->iv = iv;
use->stmt = stmt;
use->op_p = use_p;
- use->related_cands = BITMAP_XMALLOC ();
+ use->related_cands = BITMAP_ALLOC (NULL);
/* To avoid showing ssa name in the dumps, if it was not reset by the
caller. */
if (!EXPR_P (expr))
return false;
- len = first_rtl_op (TREE_CODE (expr));
+ len = TREE_CODE_LENGTH (TREE_CODE (expr));
for (i = 0; i < len; i++)
if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
return false;
return false;
/* If base is a component ref, require that the offset of the reference
- is invariant. */
+ be invariant. */
if (TREE_CODE (base) == COMPONENT_REF)
{
off = component_ref_field_offset (base);
return false;
}
- step = EXEC_BINARY (MULT_EXPR, type, step, iv_step);
+ step = fold_binary_to_constant (MULT_EXPR, type, step, iv_step);
if (!*dta->step_p)
*dta->step_p = step;
else
- *dta->step_p = EXEC_BINARY (PLUS_EXPR, type, *dta->step_p, step);
+ *dta->step_p = fold_binary_to_constant (PLUS_EXPR, type,
+ *dta->step_p, step);
return true;
}
return true;
}
+/* Returns true if memory reference REF may be unaligned. */
+
+static bool
+may_be_unaligned_p (tree ref)
+{
+ tree base;
+ tree base_type;
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree toffset;
+ enum machine_mode mode;
+ int unsignedp, volatilep;
+ unsigned base_align;
+
+ /* The test below is basically copy of what expr.c:normal_inner_ref
+ does to check whether the object must be loaded by parts when
+ STRICT_ALIGNMENT is true. */
+ base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
+ &unsignedp, &volatilep, true);
+ base_type = TREE_TYPE (base);
+ base_align = TYPE_ALIGN (base_type);
+
+ if (mode != BLKmode
+ && (base_align < GET_MODE_ALIGNMENT (mode)
+ || bitpos % GET_MODE_ALIGNMENT (mode) != 0
+ || bitpos % BITS_PER_UNIT != 0))
+ return true;
+
+ return false;
+}
+
/* Finds addresses in *OP_P inside STMT. */
static void
&& DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
goto fail;
+ if (STRICT_ALIGNMENT
+ && may_be_unaligned_p (base))
+ goto fail;
+
ifs_ivopts_data.ivopts_data = data;
ifs_ivopts_data.stmt = stmt;
ifs_ivopts_data.step_p = &step;
free (body);
}
+/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
+ is true, assume we are inside an address. */
+
+static tree
+strip_offset (tree expr, bool inside_addr, unsigned HOST_WIDE_INT *offset)
+{
+ tree op0 = NULL_TREE, op1 = NULL_TREE, step;
+ enum tree_code code;
+ tree type, orig_type = TREE_TYPE (expr);
+ unsigned HOST_WIDE_INT off0, off1, st;
+ tree orig_expr = expr;
+
+ STRIP_NOPS (expr);
+ type = TREE_TYPE (expr);
+ code = TREE_CODE (expr);
+ *offset = 0;
+
+ switch (code)
+ {
+ case INTEGER_CST:
+ if (!cst_and_fits_in_hwi (expr)
+ || zero_p (expr))
+ return orig_expr;
+
+ *offset = int_cst_value (expr);
+ return build_int_cst_type (orig_type, 0);
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+
+ op0 = strip_offset (op0, false, &off0);
+ op1 = strip_offset (op1, false, &off1);
+
+ *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
+ if (op0 == TREE_OPERAND (expr, 0)
+ && op1 == TREE_OPERAND (expr, 1))
+ return orig_expr;
+
+ if (zero_p (op1))
+ expr = op0;
+ else if (zero_p (op0))
+ {
+ if (code == PLUS_EXPR)
+ expr = op1;
+ else
+ expr = build1 (NEGATE_EXPR, type, op1);
+ }
+ else
+ expr = build2 (code, type, op0, op1);
+
+ return fold_convert (orig_type, expr);
+
+ case ARRAY_REF:
+ if (!inside_addr)
+ return orig_expr;
+
+ step = array_ref_element_size (expr);
+ if (!cst_and_fits_in_hwi (step))
+ break;
+
+ st = int_cst_value (step);
+ op1 = TREE_OPERAND (expr, 1);
+ op1 = strip_offset (op1, false, &off1);
+ *offset = off1 * st;
+ break;
+
+ case COMPONENT_REF:
+ if (!inside_addr)
+ return orig_expr;
+ break;
+
+ case ADDR_EXPR:
+ inside_addr = true;
+ break;
+
+ default:
+ return orig_expr;
+ }
+
+ /* Default handling of expressions for that we want to recurse into
+ the first operand. */
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset (op0, inside_addr, &off0);
+ *offset += off0;
+
+ if (op0 == TREE_OPERAND (expr, 0)
+ && (!op1 || op1 == TREE_OPERAND (expr, 1)))
+ return orig_expr;
+
+ expr = copy_node (expr);
+ TREE_OPERAND (expr, 0) = op0;
+ if (op1)
+ TREE_OPERAND (expr, 1) = op1;
+
+ return fold_convert (orig_type, expr);
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. If both BASE and STEP are NULL, we add a pseudocandidate for the
return cand;
}
+/* Returns true if incrementing the induction variable at the end of the LOOP
+ is allowed.
+
+ The purpose is to avoid splitting latch edge with a biv increment, thus
+ creating a jump, possibly confusing other optimization passes and leaving
+ less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
+ is not available (so we do not have a better alternative), or if the latch
+ edge is already nonempty. */
+
+static bool
+allow_ip_end_pos_p (struct loop *loop)
+{
+ if (!ip_normal_pos (loop))
+ return true;
+
+ if (!empty_block_p (ip_end_pos (loop)))
+ return true;
+
+ return false;
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. The candidate computation is scheduled on all available positions. */
{
if (ip_normal_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
- if (ip_end_pos (data->current_loop))
+ 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_address_candidates (struct ivopts_data *data,
struct iv *iv, struct iv_use *use)
{
- tree base, abase, tmp, *act;
+ tree base, abase;
+ unsigned HOST_WIDE_INT offset;
/* First, the trivial choices. */
add_iv_value_candidates (data, iv, use);
/* Third, try removing the constant offset. */
abase = iv->base;
- while (TREE_CODE (abase) == PLUS_EXPR
- && TREE_CODE (TREE_OPERAND (abase, 1)) != INTEGER_CST)
- abase = TREE_OPERAND (abase, 0);
- /* We found the offset, so make the copy of the non-shared part and
- remove it. */
- if (TREE_CODE (abase) == PLUS_EXPR)
- {
- tmp = iv->base;
- act = &base;
-
- for (tmp = iv->base; tmp != abase; tmp = TREE_OPERAND (tmp, 0))
- {
- *act = build2 (PLUS_EXPR, TREE_TYPE (tmp),
- NULL_TREE, TREE_OPERAND (tmp, 1));
- act = &TREE_OPERAND (*act, 0);
- }
- *act = TREE_OPERAND (tmp, 0);
-
- add_candidate (data, base, iv->step, false, use);
- }
+ base = strip_offset (abase, false, &offset);
+ if (offset)
+ add_candidate (data, base, iv->step, false, use);
}
/* Possibly adds pseudocandidate for replacing the final value of USE by
add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
{
struct tree_niter_desc *niter;
- struct loop *loop = data->current_loop;
/* We must know where we exit the loop and how many times does it roll. */
- if (!single_dom_exit (loop))
- return;
-
- niter = &loop_data (loop)->niter;
- if (!niter->niter
- || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
- || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
+ 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);
for (i = 0; i < n_iv_uses (data); i++)
{
use = iv_use (data, i);
- BITMAP_XFREE (use->related_cands);
+ BITMAP_FREE (use->related_cands);
}
}
else
if (cost == INFTY)
{
- if (depends_on)
- BITMAP_XFREE (depends_on);
+ BITMAP_FREE (depends_on);
return;
}
{
case ADDR_EXPR:
for (expr_p = &TREE_OPERAND (*expr_p, 0);
- (handled_component_p (*expr_p)
- || TREE_CODE (*expr_p) == REALPART_EXPR
- || TREE_CODE (*expr_p) == IMAGPART_EXPR);
- expr_p = &TREE_OPERAND (*expr_p, 0));
+ handled_component_p (*expr_p);
+ expr_p = &TREE_OPERAND (*expr_p, 0))
+ continue;
obj = *expr_p;
if (DECL_P (obj))
x = produce_memory_decl_rtl (obj, regno);
rtx seq, rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
- int regno = 0;
+ /* Avoid using hard regs in ways which may be unsupported. */
+ int regno = LAST_VIRTUAL_REGISTER + 1;
walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
start_sequence ();
if (stmt_after_increment (loop, cand, at))
cbase = fold (build2 (PLUS_EXPR, uutype, cbase, cstep));
- /* 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. */
+ /* 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 (ratioi == 1)
{
delta = fold (build2 (PLUS_EXPR, uutype, ubase, cbase));
expr = fold (build2 (MINUS_EXPR, uutype, delta, expr));
}
- else if (TREE_CODE (cbase) == INTEGER_CST)
+ else
{
ratio = build_int_cst_type (uutype, ratioi);
delta = fold (build2 (MULT_EXPR, uutype, ratio, cbase));
expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
expr = fold (build2 (PLUS_EXPR, uutype, delta, expr));
}
- else
- {
- expr = fold (build2 (MINUS_EXPR, uutype, expr, cbase));
- ratio = build_int_cst_type (uutype, ratioi);
- expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
- expr = fold (build2 (PLUS_EXPR, uutype, ubase, expr));
- }
return fold_convert (utype, expr);
}
return get_computation_at (loop, use, cand, use->stmt);
}
-/* Strips constant offsets from EXPR and adds them to OFFSET. */
-
-static void
-strip_offset (tree *expr, unsigned HOST_WIDE_INT *offset)
-{
- tree op0, op1;
- enum tree_code code;
-
- while (1)
- {
- if (cst_and_fits_in_hwi (*expr))
- {
- *offset += int_cst_value (*expr);
- *expr = integer_zero_node;
- return;
- }
-
- code = TREE_CODE (*expr);
-
- if (code != PLUS_EXPR && code != MINUS_EXPR)
- return;
-
- op0 = TREE_OPERAND (*expr, 0);
- op1 = TREE_OPERAND (*expr, 1);
-
- if (cst_and_fits_in_hwi (op1))
- {
- if (code == PLUS_EXPR)
- *offset += int_cst_value (op1);
- else
- *offset -= int_cst_value (op1);
-
- *expr = op0;
- continue;
- }
-
- if (code != PLUS_EXPR)
- return;
-
- if (!cst_and_fits_in_hwi (op0))
- return;
-
- *offset += int_cst_value (op0);
- *expr = op1;
- }
-}
-
/* Returns cost of addition in MODE. */
static unsigned
addr = gen_rtx_fmt_ee (MULT, Pmode, addr, GEN_INT (rat));
if (var_present)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, addr);
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
if (symbol_present)
{
base = NULL_RTX;
if (base)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, base, addr);
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
start_sequence ();
addr = memory_address (Pmode, addr);
return NULL_TREE;
if (!*depends_on)
- *depends_on = BITMAP_XMALLOC ();
+ *depends_on = BITMAP_ALLOC (NULL);
bitmap_set_bit (*depends_on, info->inv_id);
return NULL_TREE;
}
-/* Estimates cost of forcing EXPR into variable. DEPENDS_ON is a set of the
+/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
invariants the computation depends on. */
static unsigned
static unsigned integer_cost;
static unsigned symbol_cost;
static unsigned address_cost;
+ tree op0, op1;
+ unsigned cost0, cost1, cost;
+ enum machine_mode mode;
if (!costs_initialized)
{
costs_initialized = true;
}
+ STRIP_NOPS (expr);
+
if (depends_on)
{
fd_ivopts_data = data;
return address_cost;
}
- /* Just an arbitrary value, FIXME. */
- return target_spill_cost;
+ switch (TREE_CODE (expr))
+ {
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ case MULT_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+ STRIP_NOPS (op0);
+ STRIP_NOPS (op1);
+
+ if (is_gimple_val (op0))
+ cost0 = 0;
+ else
+ cost0 = force_var_cost (data, op0, NULL);
+
+ if (is_gimple_val (op1))
+ cost1 = 0;
+ else
+ cost1 = force_var_cost (data, op1, NULL);
+
+ break;
+
+ default:
+ /* Just an arbitrary value, FIXME. */
+ return target_spill_cost;
+ }
+
+ mode = TYPE_MODE (TREE_TYPE (expr));
+ switch (TREE_CODE (expr))
+ {
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ cost = add_cost (mode);
+ break;
+
+ case MULT_EXPR:
+ if (cst_and_fits_in_hwi (op0))
+ cost = multiply_by_cost (int_cst_value (op0), mode);
+ else if (cst_and_fits_in_hwi (op1))
+ cost = multiply_by_cost (int_cst_value (op1), mode);
+ else
+ return target_spill_cost;
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
+ cost += cost0;
+ cost += cost1;
+
+ /* Bound the cost by target_spill_cost. The parts of complicated
+ 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. */
+ return cost < target_spill_cost ? cost : target_spill_cost;
}
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
int unsignedp, volatilep;
core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
- &unsignedp, &volatilep);
+ &unsignedp, &volatilep, false);
if (toffset != 0
|| bitpos % BITS_PER_UNIT != 0
gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
- if (TREE_CODE (e2) == ADDR_EXPR
- && ptr_difference_const (TREE_OPERAND (e1, 0),
- TREE_OPERAND (e2, 0), &diff))
+ if (ptr_difference_const (e1, e2, &diff))
{
*offset += diff;
*symbol_present = false;
{
unsigned cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
+ unsigned HOST_WIDE_INT off1, off2;
+
+ e1 = strip_offset (e1, false, &off1);
+ e2 = strip_offset (e2, false, &off2);
+ *offset += off1 - off2;
- strip_offset (&e1, offset);
- *offset = -*offset;
- strip_offset (&e2, offset);
- *offset = -*offset;
+ STRIP_NOPS (e1);
+ STRIP_NOPS (e2);
if (TREE_CODE (e1) == ADDR_EXPR)
return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
(symbol/var/const parts may be omitted). If we are looking for an address,
find the cost of addressing this. */
if (address_p)
- return get_address_cost (symbol_present, var_present, offset, ratio);
+ return cost + get_address_cost (symbol_present, var_present, offset, ratio);
/* Otherwise estimate the costs for computing the expression. */
aratio = ratio > 0 ? ratio : -ratio;
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost = get_computation_cost (data, use, cand, false, &depends_on);
+ unsigned cost;
+
+ /* 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);
+ return true;
+ }
+ cost = get_computation_cost (data, use, cand, false, &depends_on);
set_use_iv_cost (data, use, cand, cost, depends_on);
return cost != INFTY;
return val;
}
+/* Returns period of induction variable iv. */
+
+static tree
+iv_period (struct iv *iv)
+{
+ tree step = iv->step, period, type;
+ tree pow2div;
+
+ gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
+
+ /* Period of the iv is gcd (step, type range). Since type range is power
+ of two, it suffices to determine the maximum power of two that divides
+ step. */
+ pow2div = num_ending_zeros (step);
+ type = unsigned_type_for (TREE_TYPE (step));
+
+ period = build_low_bits_mask (type,
+ (TYPE_PRECISION (type)
+ - tree_low_cst (pow2div, 1)));
+
+ return period;
+}
+
/* Check whether it is possible to express the condition in USE by comparison
of candidate CAND. If so, store the comparison code to COMPARE and the
value compared with to BOUND. */
static bool
-may_eliminate_iv (struct loop *loop,
+may_eliminate_iv (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
enum tree_code *compare, tree *bound)
{
basic_block ex_bb;
edge exit;
- struct tree_niter_desc niter, new_niter;
- tree wider_type, type, base;
+ struct tree_niter_desc *niter;
+ tree nit, nit_type;
+ tree wider_type, period, per_type;
+ struct loop *loop = data->current_loop;
/* For now works only for exits that dominate the loop latch. TODO -- extend
for other conditions inside loop body. */
if (flow_bb_inside_loop_p (loop, exit->dest))
return false;
- niter.niter = NULL_TREE;
- number_of_iterations_exit (loop, exit, &niter);
- if (!niter.niter
- || !integer_nonzerop (niter.assumptions)
- || !integer_zerop (niter.may_be_zero))
+ niter = niter_for_exit (data, exit);
+ if (!niter
+ || !zero_p (niter->may_be_zero))
return false;
- if (exit->flags & EDGE_TRUE_VALUE)
- *compare = EQ_EXPR;
- else
- *compare = NE_EXPR;
+ nit = niter->niter;
+ nit_type = TREE_TYPE (nit);
- *bound = cand_value_at (loop, cand, use->stmt, niter.niter);
-
- /* Let us check there is not some problem with overflows, by checking that
- the number of iterations is unchanged. */
- base = cand->iv->base;
- type = TREE_TYPE (base);
- if (stmt_after_increment (loop, cand, use->stmt))
- base = fold (build2 (PLUS_EXPR, type, base, cand->iv->step));
-
- new_niter.niter = NULL_TREE;
- number_of_iterations_cond (TREE_TYPE (cand->iv->base), base,
- cand->iv->step, NE_EXPR, *bound, NULL_TREE,
- &new_niter);
- if (!new_niter.niter
- || !integer_nonzerop (new_niter.assumptions)
- || !integer_zerop (new_niter.may_be_zero))
+ /* 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. */
+ period = iv_period (cand->iv);
+ if (!period)
return false;
+ per_type = TREE_TYPE (period);
- wider_type = TREE_TYPE (new_niter.niter);
- if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter.niter)))
- wider_type = TREE_TYPE (niter.niter);
- if (!operand_equal_p (fold_convert (wider_type, niter.niter),
- fold_convert (wider_type, new_niter.niter), 0))
+ wider_type = TREE_TYPE (period);
+ if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
+ wider_type = per_type;
+ 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)))))
return false;
+ if (exit->flags & EDGE_TRUE_VALUE)
+ *compare = EQ_EXPR;
+ else
+ *compare = NE_EXPR;
+
+ *bound = cand_value_at (loop, cand, use->stmt, nit);
return true;
}
return false;
}
- if (may_eliminate_iv (data->current_loop, use, cand, &compare, &bound))
+ if (may_eliminate_iv (data, use, cand, &compare, &bound))
{
bitmap depends_on = NULL;
unsigned cost = force_var_cost (data, bound, &depends_on);
a direct computation. If so, the formula is stored to *VALUE. */
static bool
-may_replace_final_value (struct loop *loop, struct iv_use *use, tree *value)
+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;
gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
bb_for_stmt (use->stmt)));
- niter = &loop_data (loop)->niter;
- if (!niter->niter
- || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
- || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
+ niter = niter_for_single_dom_exit (data);
+ if (!niter
+ || !zero_p (niter->may_be_zero))
return false;
*value = iv_value (use->iv, niter->niter);
edge exit;
tree value;
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);
+ return true;
+ }
+
if (!cand->iv)
{
- if (!may_replace_final_value (loop, use, &value))
+ if (!may_replace_final_value (data, use, &value))
{
set_use_iv_cost (data, use, cand, INFTY, NULL);
return false;
unsigned i, j;
struct iv_use *use;
struct iv_cand *cand;
- bitmap to_clear = BITMAP_XMALLOC ();
+ bitmap to_clear = BITMAP_ALLOC (NULL);
alloc_use_cost_map (data);
}
}
- BITMAP_XFREE (to_clear);
+ BITMAP_FREE (to_clear);
if (dump_file && (dump_flags & TDF_DETAILS))
{
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
unsigned cost_base, cost_step;
- tree base, last;
- basic_block bb;
+ tree base;
if (!cand->iv)
{
cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
- /* Prefer the original iv unless we may gain something by replacing it. */
- if (cand->pos == IP_ORIGINAL)
+ /* Prefer the original iv unless we may gain something by replacing it;
+ this is not really relevant for artificial ivs created by other
+ passes. */
+ if (cand->pos == IP_ORIGINAL
+ && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
cand->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)
- {
- bb = ip_end_pos (data->current_loop);
- last = last_stmt (bb);
-
- if (!last
- || TREE_CODE (last) == LABEL_EXPR)
- cand->cost++;
- }
+ if (cand->pos == IP_END
+ && empty_block_p (ip_end_pos (data->current_loop)))
+ cand->cost++;
}
/* Determines costs of computation of the candidates. */
/* Do not count the pseudocandidates. */
if (cp->cand->iv)
ivs->n_regs--;
+ ivs->n_cands--;
ivs->cand_cost -= cp->cand->cost;
}
/* Do not count the pseudocandidates. */
if (cp->cand->iv)
ivs->n_regs++;
+ ivs->n_cands++;
ivs->cand_cost += cp->cand->cost;
}
return change;
}
+/* Joins two lists of changes L1 and L2. Destructive -- old lists
+ are rewritten. */
+
+static struct iv_ca_delta *
+iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
+{
+ struct iv_ca_delta *last;
+
+ if (!l2)
+ return l1;
+
+ if (!l1)
+ return l2;
+
+ for (last = l1; last->next_change; last = last->next_change)
+ continue;
+ last->next_change = l2;
+
+ return l1;
+}
+
/* Returns candidate by that USE is expressed in IVS. */
static struct cost_pair *
return ivs->cand_for_use[use->id];
}
+/* Reverse the list of changes DELTA, forming the inverse to it. */
+
+static struct iv_ca_delta *
+iv_ca_delta_reverse (struct iv_ca_delta *delta)
+{
+ struct iv_ca_delta *act, *next, *prev = NULL;
+ struct cost_pair *tmp;
+
+ for (act = delta; act; act = next)
+ {
+ next = act->next_change;
+ act->next_change = prev;
+ prev = act;
+
+ tmp = act->old_cp;
+ act->old_cp = act->new_cp;
+ act->new_cp = tmp;
+ }
+
+ return prev;
+}
+
/* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
reverted instead. */
struct iv_ca_delta *delta, bool forward)
{
struct cost_pair *from, *to;
+ struct iv_ca_delta *act;
- for (; delta; delta = delta->next_change)
- {
- if (forward)
- {
- from = delta->old_cp;
- to = delta->new_cp;
- }
- else
- {
- from = delta->new_cp;
- to = delta->old_cp;
- }
+ if (!forward)
+ delta = iv_ca_delta_reverse (delta);
- gcc_assert (iv_ca_cand_for_use (ivs, delta->use) == from);
- iv_ca_set_cp (data, ivs, delta->use, to);
+ for (act = delta; act; act = act->next_change)
+ {
+ from = act->old_cp;
+ to = act->new_cp;
+ gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
+ iv_ca_set_cp (data, ivs, act->use, to);
}
+
+ if (!forward)
+ iv_ca_delta_reverse (delta);
}
/* Returns true if CAND is used in IVS. */
return ivs->n_cand_uses[cand->id] > 0;
}
+/* Returns number of induction variable candidates in the set IVS. */
+
+static unsigned
+iv_ca_n_cands (struct iv_ca *ivs)
+{
+ return ivs->n_cands;
+}
+
/* Free the list of changes DELTA. */
static void
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->cands = BITMAP_XMALLOC ();
+ nw->cands = BITMAP_ALLOC (NULL);
+ nw->n_cands = 0;
nw->n_regs = 0;
nw->cand_use_cost = 0;
nw->cand_cost = 0;
{
free ((*ivs)->cand_for_use);
free ((*ivs)->n_cand_uses);
- BITMAP_XFREE ((*ivs)->cands);
+ BITMAP_FREE ((*ivs)->cands);
free ((*ivs)->n_invariant_uses);
free (*ivs);
*ivs = NULL;
}
/* Try changing candidate in IVS to CAND for each use. Return cost of the
- new set, and store differences in DELTA. */
+ new set, and store differences in DELTA. Number of induction variables
+ in the new set is stored to N_IVS. */
static unsigned
iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_cand *cand, struct iv_ca_delta **delta)
+ struct iv_cand *cand, struct iv_ca_delta **delta,
+ unsigned *n_ivs)
{
unsigned i, cost;
struct iv_use *use;
iv_ca_delta_commit (data, ivs, *delta, true);
cost = iv_ca_cost (ivs);
+ if (n_ivs)
+ *n_ivs = iv_ca_n_cands (ivs);
iv_ca_delta_commit (data, ivs, *delta, false);
return cost;
}
-/* Try narowing set IVS by removing CAND. Return the cost of
+/* Try narrowing set IVS by removing CAND. Return the cost of
the new set and store the differences in DELTA. */
static unsigned
return cost;
}
+/* Try optimizing the set of candidates IVS by removing candidates different
+ from to EXCEPT_CAND from it. Return cost of the new set, and store
+ differences in DELTA. */
+
+static unsigned
+iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_cand *except_cand, struct iv_ca_delta **delta)
+{
+ bitmap_iterator bi;
+ struct iv_ca_delta *act_delta, *best_delta;
+ unsigned i, best_cost, acost;
+ struct iv_cand *cand;
+
+ best_delta = NULL;
+ best_cost = iv_ca_cost (ivs);
+
+ EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+ {
+ cand = iv_cand (data, i);
+
+ if (cand == except_cand)
+ continue;
+
+ acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+
+ if (acost < best_cost)
+ {
+ best_cost = acost;
+ iv_ca_delta_free (&best_delta);
+ best_delta = act_delta;
+ }
+ else
+ iv_ca_delta_free (&act_delta);
+ }
+
+ if (!best_delta)
+ {
+ *delta = NULL;
+ return best_cost;
+ }
+
+ /* Recurse to possibly remove other unnecessary ivs. */
+ iv_ca_delta_commit (data, ivs, best_delta, true);
+ best_cost = iv_ca_prune (data, ivs, except_cand, delta);
+ iv_ca_delta_commit (data, ivs, best_delta, false);
+ *delta = iv_ca_delta_join (best_delta, *delta);
+ return best_cost;
+}
+
/* Tries to extend the sets IVS in the best possible way in order
to express the USE. */
continue;
iv_ca_set_cp (data, ivs, use, cp);
- act_cost = iv_ca_extend (data, ivs, cand, &act_delta);
+ act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
act_delta = NULL;
iv_ca_set_cp (data, ivs, use, cp);
- act_cost = iv_ca_extend (data, ivs, cand, &act_delta);
+ act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
cp, act_delta);
static bool
try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned i, acost, best_cost = iv_ca_cost (ivs);
- struct iv_ca_delta *best_delta = NULL, *act_delta;
+ unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
+ struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
struct iv_cand *cand;
- /* Try altering the set of induction variables by one. */
+ /* Try extending the set of induction variables by one. */
for (i = 0; i < n_iv_cands (data); i++)
{
cand = iv_cand (data, i);
if (iv_ca_cand_used_p (ivs, cand))
- acost = iv_ca_narrow (data, ivs, cand, &act_delta);
- else
- acost = iv_ca_extend (data, ivs, cand, &act_delta);
+ continue;
+
+ acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
+ if (!act_delta)
+ continue;
+
+ /* If we successfully added the candidate and the set is small enough,
+ try optimizing it by removing other candidates. */
+ if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
+ {
+ iv_ca_delta_commit (data, ivs, act_delta, true);
+ acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
+ iv_ca_delta_commit (data, ivs, act_delta, false);
+ act_delta = iv_ca_delta_join (act_delta, tmp_delta);
+ }
if (acost < best_cost)
{
best_cost = acost;
- if (best_delta)
- iv_ca_delta_free (&best_delta);
+ iv_ca_delta_free (&best_delta);
best_delta = act_delta;
}
else
}
if (!best_delta)
- return false;
+ {
+ /* Try removing the candidates from the set instead. */
+ best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
+
+ /* Nothing more we can do. */
+ if (!best_delta)
+ return false;
+ }
iv_ca_delta_commit (data, ivs, best_delta, true);
+ gcc_assert (best_cost == iv_ca_cost (ivs));
iv_ca_delta_free (&best_delta);
return true;
}
/* Prevent the ssa name defined by the statement from being removed. */
SET_PHI_RESULT (stmt, NULL);
}
- remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
+ remove_phi_node (stmt, NULL_TREE);
}
else
{
rewrite_use_nonlinear_expr (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp = unshare_expr (get_computation (data->current_loop,
- use, cand));
+ tree comp;
tree op, stmts, tgt, ass;
block_stmt_iterator bsi, pbsi;
-
+
+ /* An important special case -- if we are asked to express value of
+ the original iv by itself, just exit; there is no need to
+ 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)
+ {
+ op = TREE_OPERAND (use->stmt, 1);
+
+ /* 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)
+ return;
+ }
+
+ comp = unshare_expr (get_computation (data->current_loop,
+ use, cand));
switch (TREE_CODE (use->stmt))
{
case PHI_NODE:
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
enum tree_code compare;
- if (may_eliminate_iv (data->current_loop,
- use, cand, &compare, &bound))
+ if (may_eliminate_iv (data, use, cand, &compare, &bound))
{
+ tree var = var_at_stmt (data->current_loop, cand, use->stmt);
+ tree var_type = TREE_TYPE (var);
+
+ bound = fold_convert (var_type, bound);
op = force_gimple_operand (unshare_expr (bound), &stmts,
true, NULL_TREE);
if (stmts)
bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
- *use->op_p = build2 (compare, boolean_type_node,
- var_at_stmt (data->current_loop,
- cand, use->stmt), op);
+ *use->op_p = build2 (compare, boolean_type_node, var, op);
modify_stmt (use->stmt);
return;
}
phi = create_phi_node (new_name, exit->dest);
SSA_NAME_DEF_STMT (new_name) = phi;
- add_phi_arg (&phi, use, exit);
+ add_phi_arg (phi, use, exit);
}
SET_USE (op_p, PHI_RESULT (phi));
block_stmt_iterator bsi;
tree phi, stmt, def, next;
- if (EDGE_COUNT (exit->dest->preds) > 1)
+ if (!single_pred_p (exit->dest))
split_loop_exit_edge (exit);
if (TREE_CODE (stmts) == STATEMENT_LIST)
for (phi = phi_nodes (exit->dest); phi; phi = next)
{
- next = TREE_CHAIN (phi);
+ next = PHI_CHAIN (phi);
if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == op)
{
{
if (!cand->iv)
{
- bool ok = may_replace_final_value (data->current_loop, use, &value);
+ bool ok = may_replace_final_value (data, use, &value);
gcc_assert (ok);
}
else
unsigned i, j;
bitmap_iterator bi;
+ htab_empty (data->niters);
+
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
struct version_info *info;
struct iv_use *use = iv_use (data, i);
free (use->iv);
- BITMAP_XFREE (use->related_cands);
+ BITMAP_FREE (use->related_cands);
for (j = 0; j < use->n_map_members; j++)
if (use->cost_map[j].depends_on)
- BITMAP_XFREE (use->cost_map[j].depends_on);
+ BITMAP_FREE (use->cost_map[j].depends_on);
free (use->cost_map);
free (use);
}
free_loop_data (data);
free (data->version_info);
- BITMAP_XFREE (data->relevant);
- BITMAP_XFREE (data->important_candidates);
+ BITMAP_FREE (data->relevant);
+ BITMAP_FREE (data->important_candidates);
+ htab_delete (data->niters);
VARRAY_FREE (decl_rtl_to_reset);
VARRAY_FREE (data->iv_uses);
/* Remove the ivs that are unused after rewriting. */
remove_unused_ivs (data);
- loop_commit_inserts ();
-
/* We have changed the structure of induction variables; it might happen
that definitions in the scev database refer to some of them that were
eliminated. */
OSDN Git Service
