struct iv
{
tree base; /* Initial value of the iv. */
+ tree base_object; /* A memory object to that the induction variable points. */
tree step; /* Step of the iv (constant only). */
tree ssa_name; /* The ssa name with the value. */
bool biv_p; /* Is it a biv? */
/* The candidates. */
varray_type iv_candidates;
+ /* A bitmap of important candidates. */
+ bitmap important_candidates;
+
/* Whether to consider just related and important candidates when replacing a
use. */
bool consider_all_candidates;
void
dump_iv (FILE *file, struct iv *iv)
{
- fprintf (file, "ssa name ");
- print_generic_expr (file, iv->ssa_name, TDF_SLIM);
- fprintf (file, "\n");
+ if (iv->ssa_name)
+ {
+ fprintf (file, "ssa name ");
+ print_generic_expr (file, iv->ssa_name, TDF_SLIM);
+ fprintf (file, "\n");
+ }
fprintf (file, " type ");
print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
fprintf (file, "\n");
}
+ if (iv->base_object)
+ {
+ fprintf (file, " base object ");
+ print_generic_expr (file, iv->base_object, TDF_SLIM);
+ fprintf (file, "\n");
+ }
+
if (iv->biv_p)
fprintf (file, " is a biv\n");
}
void
dump_use (FILE *file, struct iv_use *use)
{
- struct iv *iv = use->iv;
-
fprintf (file, "use %d\n", use->id);
switch (use->type)
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
- fprintf (file, " type ");
- print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
- fprintf (file, "\n");
-
- if (iv->step)
- {
- fprintf (file, " base ");
- print_generic_expr (file, iv->base, TDF_SLIM);
- fprintf (file, "\n");
-
- fprintf (file, " step ");
- print_generic_expr (file, iv->step, TDF_SLIM);
- fprintf (file, "\n");
- }
- else
- {
- fprintf (file, " invariant ");
- print_generic_expr (file, iv->base, TDF_SLIM);
- fprintf (file, "\n");
- }
+ dump_iv (file, use->iv);
fprintf (file, " related candidates ");
dump_bitmap (file, use->related_cands);
break;
}
- fprintf (file, " type ");
- print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
- fprintf (file, "\n");
-
- if (iv->step)
- {
- fprintf (file, " base ");
- print_generic_expr (file, iv->base, TDF_SLIM);
- fprintf (file, "\n");
-
- fprintf (file, " step ");
- print_generic_expr (file, iv->step, TDF_SLIM);
- fprintf (file, "\n");
- }
- else
- {
- fprintf (file, " invariant ");
- print_generic_expr (file, iv->base, TDF_SLIM);
- fprintf (file, "\n");
- }
+ dump_iv (file, iv);
}
/* Returns the info for ssa version VER. */
VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
}
+/* Returns a memory object to that EXPR points. In case we are able to
+ determine that it does not point to any such object, NULL is returned. */
+
+static tree
+determine_base_object (tree expr)
+{
+ enum tree_code code = TREE_CODE (expr);
+ tree base, obj, op0, op1;
+
+ if (!POINTER_TYPE_P (TREE_TYPE (expr)))
+ return NULL_TREE;
+
+ switch (code)
+ {
+ case INTEGER_CST:
+ return NULL_TREE;
+
+ case ADDR_EXPR:
+ obj = TREE_OPERAND (expr, 0);
+ base = get_base_address (obj);
+
+ if (!base)
+ return fold_convert (ptr_type_node, expr);
+
+ return fold (build1 (ADDR_EXPR, ptr_type_node, base));
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ op0 = determine_base_object (TREE_OPERAND (expr, 0));
+ op1 = determine_base_object (TREE_OPERAND (expr, 1));
+
+ if (!op1)
+ return op0;
+
+ if (!op0)
+ return (code == PLUS_EXPR
+ ? op1
+ : fold (build1 (NEGATE_EXPR, ptr_type_node, op1)));
+
+ return fold (build (code, ptr_type_node, op0, op1));
+
+ default:
+ return fold_convert (ptr_type_node, expr);
+ }
+}
+
/* Allocates an induction variable with given initial value BASE and step STEP
for loop LOOP. */
step = NULL_TREE;
iv->base = base;
+ iv->base_object = determine_base_object (base);
iv->step = step;
iv->biv_p = false;
iv->have_use_for = false;
use->op_p = use_p;
use->related_cands = BITMAP_XMALLOC ();
+ /* To avoid showing ssa name in the dumps, if it was not reset by the
+ caller. */
+ iv->ssa_name = NULL_TREE;
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
/* Returns true if expression EXPR is obviously invariant in LOOP,
i.e. if all its operands are defined outside of the LOOP. */
-static bool
+bool
expr_invariant_in_loop_p (struct loop *loop, tree expr)
{
basic_block def_bb;
s_offset = offset;
cost = 0;
- offset_p = (min_offset <= s_offset && s_offset <= max_offset);
+ offset_p = (s_offset != 0
+ && min_offset <= s_offset && s_offset <= max_offset);
ratio_p = (ratio != 1
&& -MAX_RATIO <= ratio && ratio <= MAX_RATIO
&& TEST_BIT (valid_mult, ratio + MAX_RATIO));
if (ratio_p)
addr = gen_rtx_fmt_ee (MULT, Pmode, addr, GEN_INT (rat));
+ if (var_present)
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, addr);
+
if (symbol_present)
{
base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
gen_rtx_fmt_ee (PLUS, Pmode,
base,
GEN_INT (off)));
- if (var_present)
- base = gen_rtx_fmt_ee (PLUS, Pmode, reg1, base);
- }
-
- else if (var_present)
- {
- base = reg1;
- if (offset_p)
- base = gen_rtx_fmt_ee (PLUS, Pmode, base, GEN_INT (off));
}
else if (offset_p)
base = GEN_INT (off);
return INFTY;
}
+ if (address_p)
+ {
+ /* Do not try to express address of an object with computation based
+ on address of a different object. This may cause problems in rtl
+ level alias analysis (that does not expect this to be happening,
+ as this is illegal in C), and would be unlikely to be useful
+ anyway. */
+ if (use->iv->base_object
+ && cand->iv->base_object
+ && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
+ return INFTY;
+ }
+
if (!cst_and_fits_in_hwi (ustep)
|| !cst_and_fits_in_hwi (cstep))
return INFTY;
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;
+ struct tree_niter_desc niter, new_niter;
tree wider_type, type, base;
-
- /* For now just very primitive -- we work just for the single exit condition,
- and are quite conservative about the possible overflows. TODO -- both of
- these can be improved. */
- exit = single_dom_exit (loop);
- if (!exit)
+
+ /* 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);
+ if (use->stmt != last_stmt (ex_bb)
+ || TREE_CODE (use->stmt) != COND_EXPR)
return false;
- if (use->stmt != last_stmt (exit->src))
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
return false;
- niter = &loop_data (loop)->niter;
- if (!niter->niter
- || !integer_nonzerop (niter->assumptions)
- || !integer_zerop (niter->may_be_zero))
+ exit = EDGE_SUCC (ex_bb, 0);
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ exit = EDGE_SUCC (ex_bb, 1);
+ 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))
return false;
if (exit->flags & EDGE_TRUE_VALUE)
else
*compare = NE_EXPR;
- *bound = cand_value_at (loop, cand, use->stmt, niter->niter);
+ *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. */
return false;
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),
+ 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))
return false;
else
{
asol = BITMAP_XMALLOC ();
- bitmap_a_and_b (asol, sol, use->related_cands);
+
+ bitmap_ior (asol, data->important_candidates, use->related_cands);
+ bitmap_and_into (asol, sol);
}
EXECUTE_IF_SET_IN_BITMAP (asol, 0, c, bi)
goto next_cand;
}
if (used_inv)
- bitmap_a_or_b (used_inv, used_inv, depends_on);
+ bitmap_ior_into (used_inv, depends_on);
}
cnd = acnd;
bitmap act_inv = BITMAP_XMALLOC ();
unsigned i;
struct cost_pair *cp;
+ bitmap_iterator bi;
+ struct iv_cand *cand;
+ bitmap depends_on;
bitmap_copy (best_ivs, ivs);
bitmap_copy (best_inv, inv);
- for (i = 0; i < use->n_map_members; i++)
+ /* First try important candidates. Only if it fails, try the specific ones.
+ Rationale -- in loops with many variables the best choice often is to use
+ just one generic biv. If we added here many ivs specific to the uses,
+ the optimization algorithm later would be likely to get stuck in a local
+ minimum, thus causing us to create too many ivs. The approach from
+ few ivs to more seems more likely to be successful -- starting from few
+ ivs, replacing an expensive use by a specific iv should always be a
+ win. */
+ EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
{
- cp = use->cost_map + i;
- if (cp->cost == INFTY)
+ cand = iv_cand (data, i);
+
+ if (get_use_iv_cost (data, use, cand, &depends_on) == INFTY)
continue;
bitmap_copy (act_ivs, ivs);
- bitmap_set_bit (act_ivs, cp->cand->id);
- if (cp->depends_on)
- bitmap_a_or_b (act_inv, inv, cp->depends_on);
+ bitmap_set_bit (act_ivs, cand->id);
+ if (depends_on)
+ bitmap_ior (act_inv, inv, depends_on);
else
bitmap_copy (act_inv, inv);
act_cost = set_cost_up_to (data, act_ivs, act_inv, use->id + 1);
}
}
+ if (best_cost == INFTY)
+ {
+ for (i = 0; i < use->n_map_members; i++)
+ {
+ cp = use->cost_map + i;
+ if (cp->cost == INFTY)
+ continue;
+
+ /* Already tried this. */
+ if (cp->cand->important)
+ continue;
+
+ bitmap_copy (act_ivs, ivs);
+ bitmap_set_bit (act_ivs, cp->cand->id);
+ if (cp->depends_on)
+ bitmap_ior (act_inv, inv, cp->depends_on);
+ else
+ bitmap_copy (act_inv, inv);
+ act_cost = set_cost_up_to (data, act_ivs, act_inv, use->id + 1);
+
+ if (act_cost < best_cost)
+ {
+ best_cost = act_cost;
+ bitmap_copy (best_ivs, act_ivs);
+ bitmap_copy (best_inv, act_inv);
+ }
+ }
+ }
+
bitmap_copy (ivs, best_ivs);
bitmap_copy (inv, best_inv);
bitmap inv = BITMAP_XMALLOC ();
struct iv_use *use;
+ data->important_candidates = BITMAP_XMALLOC ();
+ for (i = 0; i < n_iv_cands (data); i++)
+ {
+ struct iv_cand *cand = iv_cand (data, i);
+
+ if (cand->important)
+ bitmap_set_bit (data->important_candidates, i);
+ }
+
/* Set the upper bound. */
cost = get_initial_solution (data, set, inv);
if (cost == INFTY)
}
BITMAP_XFREE (inv);
+ BITMAP_XFREE (data->important_candidates);
return set;
}
}
else
{
- block_stmt_iterator bsi = stmt_for_bsi (stmt);
+ block_stmt_iterator bsi = bsi_for_stmt (stmt);
bsi_remove (&bsi);
}
case MODIFY_EXPR:
tgt = TREE_OPERAND (use->stmt, 0);
- bsi = stmt_for_bsi (use->stmt);
+ bsi = bsi_for_stmt (use->stmt);
break;
default:
{
tree comp = unshare_expr (get_computation (data->current_loop,
use, cand));
- block_stmt_iterator bsi = stmt_for_bsi (use->stmt);
+ block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
tree stmts;
tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
{
tree comp;
tree *op_p, cond, op, stmts, bound;
- block_stmt_iterator bsi = stmt_for_bsi (use->stmt);
+ block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
enum tree_code compare;
if (may_eliminate_iv (data->current_loop,
{
if (dump_file && (dump_flags & TDF_DETAILS))
flow_loop_dump (loop, dump_file, NULL, 1);
- if (tree_ssa_iv_optimize_loop (&data, loop))
- {
-#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
- verify_stmts ();
-#endif
- }
+
+ tree_ssa_iv_optimize_loop (&data, loop);
if (loop->next)
{
loop = loop->outer;
}
+#ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ verify_stmts ();
+#endif
+
tree_ssa_iv_optimize_finalize (loops, &data);
}
OSDN Git Service
