/* Induction variable optimizations.
- Copyright (C) 2003 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
{
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? */
/* Information attached to loop. */
struct loop_data
{
- struct tree_niter_desc niter;
- /* Number of iterations. */
-
unsigned regs_used; /* Number of registers used. */
};
struct iv *iv; /* The induction variable it is based on. */
tree stmt; /* Statement in that it occurs. */
tree *op_p; /* The place where it occurs. */
- bitmap related_cands; /* The set of "related" iv candidates. */
+ bitmap related_cands; /* The set of "related" iv candidates, plus the common
+ important ones. */
unsigned n_map_members; /* Number of candidates in the cost_map list. */
struct cost_pair *cost_map;
/* 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. */
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;
};
+/* An assignment of iv candidates to uses. */
+
+struct iv_ca
+{
+ /* The number of uses covered by the assignment. */
+ unsigned upto;
+
+ /* Number of uses that cannot be expressed by the candidates in the set. */
+ unsigned bad_uses;
+
+ /* Candidate assigned to a use, together with the related costs. */
+ struct cost_pair **cand_for_use;
+
+ /* Number of times each candidate is used. */
+ unsigned *n_cand_uses;
+
+ /* The candidates used. */
+ bitmap cands;
+
+ /* The number of candidates in the set. */
+ unsigned n_cands;
+
+ /* Total number of registers needed. */
+ unsigned n_regs;
+
+ /* Total cost of expressing uses. */
+ unsigned cand_use_cost;
+
+ /* Total cost of candidates. */
+ unsigned cand_cost;
+
+ /* Number of times each invariant is used. */
+ unsigned *n_invariant_uses;
+
+ /* Total cost of the assignment. */
+ unsigned cost;
+};
+
+/* Difference of two iv candidate assignments. */
+
+struct iv_ca_delta
+{
+ /* Changed use. */
+ struct iv_use *use;
+
+ /* An old assignment (for rollback purposes). */
+ struct cost_pair *old_cp;
+
+ /* A new assignment. */
+ struct cost_pair *new_cp;
+
+ /* Next change in the list. */
+ struct iv_ca_delta *next_change;
+};
+
/* Bound on number of candidates below that all candidates are considered. */
#define CONSIDER_ALL_CANDIDATES_BOUND \
#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. */
void
dump_iv (FILE *file, struct iv *iv)
{
- fprintf (file, "ssa name ");
- print_generic_expr (file, iv->ssa_name, TDF_SLIM);
+ 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->step)
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)
break;
default:
- abort ();
+ gcc_unreachable ();
}
- fprintf (file, " in statement ");
- print_generic_expr (file, use->stmt, TDF_SLIM);
- fprintf (file, "\n");
-
- fprintf (file, " at position ");
- if (use->op_p)
- print_generic_expr (file, *use->op_p, TDF_SLIM);
- fprintf (file, "\n");
+ fprintf (file, " in statement ");
+ print_generic_expr (file, use->stmt, TDF_SLIM);
+ fprintf (file, "\n");
- if (iv->step)
- {
- fprintf (file, " base ");
- print_generic_expr (file, iv->base, TDF_SLIM);
- fprintf (file, "\n");
+ fprintf (file, " at position ");
+ if (use->op_p)
+ print_generic_expr (file, *use->op_p, 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);
+ if (use->related_cands)
+ {
+ fprintf (file, " related candidates ");
+ dump_bitmap (file, use->related_cands);
+ }
}
/* Dumps information about the uses to FILE. */
break;
}
- 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. */
val = (a * inv) & mask;
- if (((val * b) & mask) != a)
- abort ();
+ gcc_assert (((val * b) & mask) == a);
if ((val >> (bits - 1)) & 1)
val |= ~mask;
{
basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
- if (!bb)
- abort ();
+ gcc_assert (bb);
if (sbb == loop->latch)
return true;
return stmt_after_ip_original_pos (cand, stmt);
default:
- abort ();
+ gcc_unreachable ();
+ }
+}
+
+/* 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
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->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])
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 expr;
+
+ if (TREE_CODE (base) == INDIRECT_REF)
+ return determine_base_object (TREE_OPERAND (base, 0));
+
+ 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));
+
+ case NOP_EXPR:
+ case CONVERT_EXPR:
+ return determine_base_object (TREE_OPERAND (expr, 0));
+
+ 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;
{
struct version_info *info = name_info (data, iv);
- if (info->iv)
- abort ();
+ gcc_assert (!info->iv);
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
info->iv = alloc_iv (base, step);
return step;
}
-/* Returns false if INDEX is a ssa name that occurs in an
+/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
+
+static bool
+abnormal_ssa_name_p (tree exp)
+{
+ if (!exp)
+ return false;
+
+ if (TREE_CODE (exp) != SSA_NAME)
+ return false;
+
+ return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
+}
+
+/* Returns false if BASE or INDEX contains a ssa name that occurs in an
abnormal phi node. Callback for for_each_index. */
static bool
-idx_contains_abnormal_ssa_name_p (tree base ATTRIBUTE_UNUSED, tree *index,
+idx_contains_abnormal_ssa_name_p (tree base, tree *index,
void *data ATTRIBUTE_UNUSED)
{
- if (TREE_CODE (*index) != SSA_NAME)
- return true;
+ if (TREE_CODE (base) == ARRAY_REF)
+ {
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
+ return false;
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
+ return false;
+ }
- return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*index) == 0;
+ return !abnormal_ssa_name_p (*index);
}
/* Returns true if EXPR contains a ssa name that occurs in an
contains_abnormal_ssa_name_p (tree expr)
{
enum tree_code code = TREE_CODE (expr);
- char class = TREE_CODE_CLASS (code);
+ enum tree_code_class class = TREE_CODE_CLASS (code);
if (code == SSA_NAME)
return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
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);
switch (class)
{
- case '2':
+ case tcc_binary:
+ case tcc_comparison:
if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
return true;
/* Fallthru. */
- case '1':
+ case tcc_unary:
if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
return true;
break;
default:
- abort ();
+ gcc_unreachable ();
}
return false;
bool found = false;
struct loop *loop = data->current_loop;
- for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
{
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
continue;
struct loop *loop = data->current_loop;
basic_block incr_bb;
- for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
{
iv = get_iv (data, PHI_RESULT (phi));
if (!iv)
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))
return false;
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");
};
fprintf (dump_file, "Induction variables:\n\n");
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
if (ver_info (data, i)->iv)
dump_iv (dump_file, ver_info (data, i)->iv);
- });
+ }
}
return true;
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. */
+ iv->ssa_name = NULL_TREE;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
{
use = iv_use (data, iv->use_id);
- if (use->type != USE_NONLINEAR_EXPR
- && use->type != USE_OUTER)
- abort ();
+ gcc_assert (use->type == USE_NONLINEAR_EXPR
+ || use->type == USE_OUTER);
if (type == USE_NONLINEAR_EXPR)
use->type = USE_NONLINEAR_EXPR;
*civ = *iv;
stmt = SSA_NAME_DEF_STMT (op);
- if (TREE_CODE (stmt) != PHI_NODE
- && TREE_CODE (stmt) != MODIFY_EXPR)
- abort ();
+ gcc_assert (TREE_CODE (stmt) == PHI_NODE
+ || TREE_CODE (stmt) == MODIFY_EXPR);
use = record_use (data, NULL, civ, stmt, type);
iv->use_id = use->id;
record_use (data, cond_p, civ, stmt, USE_COMPARE);
}
+/* Returns true if expression EXPR is obviously invariant in LOOP,
+ i.e. if all its operands are defined outside of the LOOP. */
+
+bool
+expr_invariant_in_loop_p (struct loop *loop, tree expr)
+{
+ basic_block def_bb;
+ unsigned i, len;
+
+ if (is_gimple_min_invariant (expr))
+ return true;
+
+ if (TREE_CODE (expr) == SSA_NAME)
+ {
+ def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb))
+ return false;
+
+ return true;
+ }
+
+ if (!EXPR_P (expr))
+ return false;
+
+ 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 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 *dta = data;
struct iv *iv;
- tree step, type, iv_type, iv_step;
-
+ tree step, type, iv_type, iv_step, lbound, off;
+ struct loop *loop = dta->ivopts_data->current_loop;
+
+ if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
+ || TREE_CODE (base) == ALIGN_INDIRECT_REF)
+ return false;
+
+ /* If base is a component ref, require that the offset of the reference
+ be invariant. */
+ if (TREE_CODE (base) == COMPONENT_REF)
+ {
+ off = component_ref_field_offset (base);
+ return expr_invariant_in_loop_p (loop, off);
+ }
+
+ /* If base is array, first check whether we will be able to move the
+ 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)
+ {
+ step = array_ref_element_size (base);
+ lbound = array_ref_low_bound (base);
+
+ if (!expr_invariant_in_loop_p (loop, step)
+ || !expr_invariant_in_loop_p (loop, lbound))
+ return false;
+ }
+
if (TREE_CODE (*idx) != SSA_NAME)
return true;
iv_type = TREE_TYPE (iv->base);
type = build_pointer_type (TREE_TYPE (base));
if (TREE_CODE (base) == ARRAY_REF)
- step = array_ref_element_size (base);
+ {
+ step = array_ref_element_size (base);
+
+ /* We only handle addresses whose step is an integer constant. */
+ if (TREE_CODE (step) != INTEGER_CST)
+ return false;
+ }
else
/* The step for pointer arithmetics already is 1 byte. */
step = build_int_cst (type, 1);
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;
}
object is passed to it in DATA. */
static bool
-idx_record_use (tree base ATTRIBUTE_UNUSED, tree *idx,
+idx_record_use (tree base, tree *idx,
void *data)
{
find_interesting_uses_op (data, *idx);
+ if (TREE_CODE (base) == ARRAY_REF)
+ {
+ find_interesting_uses_op (data, array_ref_element_size (base));
+ find_interesting_uses_op (data, array_ref_low_bound (base));
+ }
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;
|| zero_p (step))
goto fail;
+ gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
+ gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+
if (TREE_CODE (base) == INDIRECT_REF)
base = TREE_OPERAND (base, 0);
else
switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
{
- case '<':
+ case tcc_comparison:
find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
return;
- case 'r':
+ case tcc_reference:
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
- if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
+ if (REFERENCE_CLASS_P (lhs))
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
return;
default: ;
}
- if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
+ if (REFERENCE_CLASS_P (lhs)
+ && is_gimple_val (rhs))
{
find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
find_interesting_uses_op (data, rhs);
return;
}
+
+ /* TODO -- we should also handle address uses of type
+
+ memory = call (whatever);
+
+ and
+
+ call (memory). */
}
if (TREE_CODE (stmt) == PHI_NODE
{
tree phi, def;
- for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
{
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
find_interesting_uses_outer (data, def);
for (i = 0; i < data->current_loop->num_nodes; i++)
{
+ edge_iterator ei;
bb = body[i];
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR
&& !flow_bb_inside_loop_p (data->current_loop, e->dest))
find_interesting_uses_outside (data, e);
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 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));
if (dump_file && (dump_flags & TDF_DETAILS))
{
+ bitmap_iterator bi;
+
fprintf (dump_file, "\n");
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
info = ver_info (data, i);
if (info->inv_id)
fprintf (dump_file, " is invariant (%d)%s\n",
info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
}
- });
+ }
fprintf (dump_file, "\n");
}
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);
}
build_int_cst (unsigned_intSI_type_node, 1),
true, NULL);
- /* The same for a long type if it is still fast enought. */
+ /* The same for a long type if it is still fast enough. */
if (BITS_PER_WORD > 32)
add_candidate (data,
build_int_cst (unsigned_intDI_type_node, 0),
{
unsigned i;
struct iv *iv;
+ bitmap_iterator bi;
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
iv = ver_info (data, i)->iv;
if (iv && iv->biv_p && !zero_p (iv->step))
add_old_iv_candidates (data, iv);
- });
+ }
}
/* Adds candidates based on the value of the induction variable IV and USE. */
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);
if (base != TREE_OPERAND (iv->base, 0))
{
+ gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
+ gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+
if (TREE_CODE (base) == INDIRECT_REF)
base = TREE_OPERAND (base, 0);
else
/* 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
a direct computation. */
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);
break;
default:
- abort ();
+ gcc_unreachable ();
+ }
+ }
+}
+
+/* Record important candidates and add them to related_cands bitmaps
+ if needed. */
+
+static void
+record_important_candidates (struct ivopts_data *data)
+{
+ unsigned i;
+ struct iv_use *use;
+
+ 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);
+ }
+
+ data->consider_all_candidates = (n_iv_cands (data)
+ <= CONSIDER_ALL_CANDIDATES_BOUND);
+
+ if (data->consider_all_candidates)
+ {
+ /* We will not need "related_cands" bitmaps in this case,
+ so release them to decrease peak memory consumption. */
+ for (i = 0; i < n_iv_uses (data); i++)
+ {
+ use = iv_use (data, i);
+ BITMAP_FREE (use->related_cands);
}
}
+ else
+ {
+ /* Add important candidates to the related_cands bitmaps. */
+ for (i = 0; i < n_iv_uses (data); i++)
+ bitmap_ior_into (iv_use (data, i)->related_cands,
+ data->important_candidates);
+ }
}
/* Finds the candidates for the induction variables. */
/* Add induction variables derived from uses. */
add_derived_ivs_candidates (data);
+
+ /* Record the important candidates. */
+ record_important_candidates (data);
}
/* Allocates the data structure mapping the (use, candidate) pairs to costs.
static void
alloc_use_cost_map (struct ivopts_data *data)
{
- unsigned i, n_imp = 0, size, j;
-
- if (!data->consider_all_candidates)
- {
- for (i = 0; i < n_iv_cands (data); i++)
- {
- struct iv_cand *cand = iv_cand (data, i);
- if (cand->important)
- n_imp++;
- }
- }
+ unsigned i, size, s, j;
for (i = 0; i < n_iv_uses (data); i++)
{
struct iv_use *use = iv_use (data, i);
+ bitmap_iterator bi;
if (data->consider_all_candidates)
- {
- size = n_iv_cands (data);
- use->n_map_members = size;
- }
+ size = n_iv_cands (data);
else
{
- size = n_imp;
- EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, size++);
- use->n_map_members = 0;
+ s = 0;
+ EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
+ {
+ s++;
+ }
+
+ /* Round up to the power of two, so that moduling by it is fast. */
+ for (size = 1; size < s; size <<= 1)
+ continue;
}
+ use->n_map_members = size;
use->cost_map = xcalloc (size, sizeof (struct cost_pair));
}
}
struct iv_use *use, struct iv_cand *cand, unsigned cost,
bitmap depends_on)
{
- if (cost == INFTY
- && depends_on)
+ unsigned i, s;
+
+ if (cost == INFTY)
{
- BITMAP_XFREE (depends_on);
- depends_on = NULL;
+ BITMAP_FREE (depends_on);
+ return;
}
if (data->consider_all_candidates)
return;
}
- if (cost == INFTY)
- return;
-
- use->cost_map[use->n_map_members].cand = cand;
- use->cost_map[use->n_map_members].cost = cost;
- use->cost_map[use->n_map_members].depends_on = depends_on;
- use->n_map_members++;
+ /* n_map_members is a power of two, so this computes modulo. */
+ s = cand->id & (use->n_map_members - 1);
+ for (i = s; i < use->n_map_members; i++)
+ if (!use->cost_map[i].cand)
+ goto found;
+ for (i = 0; i < s; i++)
+ if (!use->cost_map[i].cand)
+ goto found;
+
+ gcc_unreachable ();
+
+found:
+ use->cost_map[i].cand = cand;
+ use->cost_map[i].cost = cost;
+ use->cost_map[i].depends_on = depends_on;
}
-/* Gets cost of (USE, CANDIDATE) pair. Stores the bitmap of dependencies to
- DEPENDS_ON. */
+/* Gets cost of (USE, CANDIDATE) pair. */
-static unsigned
-get_use_iv_cost (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand, bitmap *depends_on)
+static struct cost_pair *
+get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
+ struct iv_cand *cand)
{
- unsigned i;
+ unsigned i, s;
+ struct cost_pair *ret;
if (!cand)
- return INFTY;
+ return NULL;
if (data->consider_all_candidates)
- i = cand->id;
- else
{
- for (i = 0; i < use->n_map_members; i++)
- if (use->cost_map[i].cand == cand)
- break;
+ ret = use->cost_map + cand->id;
+ if (!ret->cand)
+ return NULL;
- if (i == use->n_map_members)
- return INFTY;
+ return ret;
}
+
+ /* n_map_members is a power of two, so this computes modulo. */
+ s = cand->id & (use->n_map_members - 1);
+ for (i = s; i < use->n_map_members; i++)
+ if (use->cost_map[i].cand == cand)
+ return use->cost_map + i;
- if (depends_on)
- *depends_on = use->cost_map[i].depends_on;
- return use->cost_map[i].cost;
+ for (i = 0; i < s; i++)
+ if (use->cost_map[i].cand == cand)
+ return use->cost_map + i;
+
+ return NULL;
}
/* Returns estimate on cost of computing SEQ. */
{
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 ();
get_computation_at (struct loop *loop,
struct iv_use *use, struct iv_cand *cand, tree at)
{
- tree ubase = unsave_expr_now (use->iv->base);
- tree ustep = unsave_expr_now (use->iv->step);
- tree cbase = unsave_expr_now (cand->iv->base);
- tree cstep = unsave_expr_now (cand->iv->step);
+ tree ubase = use->iv->base;
+ tree ustep = use->iv->step;
+ tree cbase = cand->iv->base;
+ tree cstep = cand->iv->step;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
tree uutype;
tree expr, delta;
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
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, addr, reg1);
+
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);
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;
-}
-
-/* Peels a single layer of ADDR. If DIFF is not NULL, do it only if the
- offset is constant and add the offset to DIFF. */
-
-static tree
-peel_address (tree addr, unsigned HOST_WIDE_INT *diff)
-{
- tree off, size;
- HOST_WIDE_INT bit_offset;
-
- switch (TREE_CODE (addr))
+ switch (TREE_CODE (expr))
{
- case SSA_NAME:
- case INDIRECT_REF:
- case BIT_FIELD_REF:
- case VAR_DECL:
- case PARM_DECL:
- case RESULT_DECL:
- case STRING_CST:
- case REALPART_EXPR:
- case IMAGPART_EXPR:
- return NULL_TREE;
-
- case COMPONENT_REF:
- off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (addr, 1));
- bit_offset = TREE_INT_CST_LOW (off);
+ 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 (bit_offset % BITS_PER_UNIT)
- abort ();
-
- if (diff)
- *diff += bit_offset / BITS_PER_UNIT;
-
- return TREE_OPERAND (addr, 0);
-
- case ARRAY_REF:
- off = TREE_OPERAND (addr, 1);
-
- if (diff)
- {
- if (!cst_and_fits_in_hwi (off))
- return NULL_TREE;
-
- size = TYPE_SIZE_UNIT (TREE_TYPE (addr));
- if (!cst_and_fits_in_hwi (size))
- return NULL_TREE;
+ if (is_gimple_val (op0))
+ cost0 = 0;
+ else
+ cost0 = force_var_cost (data, op0, NULL);
- *diff += TREE_INT_CST_LOW (off) * TREE_INT_CST_LOW (size);
- }
+ if (is_gimple_val (op1))
+ cost1 = 0;
+ else
+ cost1 = force_var_cost (data, op1, NULL);
- return TREE_OPERAND (addr, 0);
+ break;
default:
- abort ();
+ /* Just an arbitrary value, FIXME. */
+ return target_spill_cost;
}
-}
-
-/* Checks whether E1 and E2 have constant difference, and if they do,
- store it in *DIFF. */
-
-static bool
-ptr_difference_const (tree e1, tree e2, unsigned HOST_WIDE_INT *diff)
-{
- int d1 = 0, d2 = 0;
- tree x;
- unsigned HOST_WIDE_INT delta1 = 0, delta2 = 0;
- /* Find depths of E1 and E2. */
- for (x = e1; x; x = peel_address (x, NULL))
- d1++;
- for (x = e2; x; x = peel_address (x, NULL))
- d2++;
+ mode = TYPE_MODE (TREE_TYPE (expr));
+ switch (TREE_CODE (expr))
+ {
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ cost = add_cost (mode);
+ break;
- for (; e1 && d1 > d2; e1 = peel_address (e1, &delta1))
- d1--;
- for (; e2 && d2 > d1; e2 = peel_address (e2, &delta2))
- d2--;
+ 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;
- while (e1 && e2 && !operand_equal_p (e1, e2, 0))
- {
- e1 = peel_address (e1, &delta1);
- e2 = peel_address (e2, &delta1);
+ default:
+ gcc_unreachable ();
}
- if (!e1 || !e2)
- return false;
+ cost += cost0;
+ cost += cost1;
- *diff = delta1 - delta2;
- return true;
+ /* 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
tree addr, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- tree core = addr;
-
- while (core
- && TREE_CODE (core) != VAR_DECL)
- core = peel_address (core, offset);
+ tree core;
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree toffset;
+ enum machine_mode mode;
+ int unsignedp, volatilep;
+
+ core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
+ &unsignedp, &volatilep, false);
- if (!core)
+ if (toffset != 0
+ || bitpos % BITS_PER_UNIT != 0
+ || TREE_CODE (core) != VAR_DECL)
{
*symbol_present = false;
*var_present = true;
fd_ivopts_data = data;
walk_tree (&addr, find_depends, depends_on, NULL);
return target_spill_cost;
- }
-
+ }
+
+ *offset += bitpos / BITS_PER_UNIT;
if (TREE_STATIC (core)
|| DECL_EXTERNAL (core))
{
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- unsigned HOST_WIDE_INT diff = 0;
+ HOST_WIDE_INT diff = 0;
unsigned cost;
- if (TREE_CODE (e1) != ADDR_EXPR)
- abort ();
+ 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,
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;
(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;
/* Determines cost of basing replacement of USE on CAND in a generic
expression. */
-static void
+static bool
determine_use_iv_cost_generic (struct ivopts_data *data,
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;
}
/* Determines cost of basing replacement of USE on CAND in an address. */
-static void
+static bool
determine_use_iv_cost_address (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
set_use_iv_cost (data, use, cand, cost, depends_on);
+
+ return cost != INFTY;
}
/* Computes value of induction variable IV in iteration NITER. */
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;
-
- /* 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)
+ 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. */
+ 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;
- if (exit->flags & EDGE_TRUE_VALUE)
- *compare = EQ_EXPR;
- else
- *compare = NE_EXPR;
+ niter = niter_for_exit (data, exit);
+ if (!niter
+ || !zero_p (niter->may_be_zero))
+ return false;
- *bound = cand_value_at (loop, cand, use->stmt, niter->niter);
+ nit = niter->niter;
+ nit_type = TREE_TYPE (nit);
- /* 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;
}
/* Determines cost of basing replacement of USE on CAND in a condition. */
-static void
+static bool
determine_use_iv_cost_condition (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
if (!cand->iv)
{
set_use_iv_cost (data, use, cand, INFTY, NULL);
- return;
+ 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);
set_use_iv_cost (data, use, cand, cost, depends_on);
- return;
+ return cost != INFTY;
}
/* The induction variable elimination failed; just express the original
record_invariant (data, TREE_OPERAND (*use->op_p, 1), true);
}
- determine_use_iv_cost_generic (data, use, cand);
+ return determine_use_iv_cost_generic (data, use, cand);
}
/* Checks whether it is possible to replace the final value of USE by
a direct computation. If so, the formula is stored to *VALUE. */
static bool
-may_replace_final_value (struct 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;
if (!exit)
return false;
- if (!dominated_by_p (CDI_DOMINATORS, exit->src,
- bb_for_stmt (use->stmt)))
- abort ();
+ 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);
/* Determines cost of replacing final value of USE using CAND. */
-static void
+static bool
determine_use_iv_cost_outer (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
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;
+ return false;
}
depends_on = NULL;
cost /= AVG_LOOP_NITER (loop);
set_use_iv_cost (data, use, cand, cost, depends_on);
- return;
+ return cost != INFTY;
}
exit = single_dom_exit (loop);
}
set_use_iv_cost (data, use, cand, cost, depends_on);
+
+ return cost != INFTY;
}
-/* Determines cost of basing replacement of USE on CAND. */
+/* Determines cost of basing replacement of USE on CAND. Returns false
+ if USE cannot be based on CAND. */
-static void
+static bool
determine_use_iv_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
switch (use->type)
{
case USE_NONLINEAR_EXPR:
- determine_use_iv_cost_generic (data, use, cand);
- break;
+ return determine_use_iv_cost_generic (data, use, cand);
case USE_OUTER:
- determine_use_iv_cost_outer (data, use, cand);
- break;
+ return determine_use_iv_cost_outer (data, use, cand);
case USE_ADDRESS:
- determine_use_iv_cost_address (data, use, cand);
- break;
+ return determine_use_iv_cost_address (data, use, cand);
case USE_COMPARE:
- determine_use_iv_cost_condition (data, use, cand);
- break;
+ return determine_use_iv_cost_condition (data, use, cand);
default:
- abort ();
+ gcc_unreachable ();
}
}
unsigned i, j;
struct iv_use *use;
struct iv_cand *cand;
-
- data->consider_all_candidates = (n_iv_cands (data)
- <= CONSIDER_ALL_CANDIDATES_BOUND);
+ bitmap to_clear = BITMAP_ALLOC (NULL);
alloc_use_cost_map (data);
- if (!data->consider_all_candidates)
- {
- /* Add the important candidate entries. */
- for (j = 0; j < n_iv_cands (data); j++)
- {
- cand = iv_cand (data, j);
- if (!cand->important)
- continue;
- for (i = 0; i < n_iv_uses (data); i++)
- {
- use = iv_use (data, i);
- determine_use_iv_cost (data, use, cand);
- }
- }
- }
-
for (i = 0; i < n_iv_uses (data); i++)
{
use = iv_use (data, i);
}
else
{
- EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j,
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
{
cand = iv_cand (data, j);
- if (!cand->important)
- determine_use_iv_cost (data, use, cand);
- });
+ if (!determine_use_iv_cost (data, use, cand))
+ bitmap_set_bit (to_clear, j);
+ }
+
+ /* Remove the candidates for that the cost is infinite from
+ the list of related candidates. */
+ bitmap_and_compl_into (use->related_cands, to_clear);
+ bitmap_clear (to_clear);
}
}
+ BITMAP_FREE (to_clear);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Use-candidate costs:\n");
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. */
unsigned j, n;
tree phi, op;
struct loop *loop = data->current_loop;
+ bitmap_iterator bi;
/* We use the following model (definitely improvable, especially the
cost function -- TODO):
}
n = 0;
- for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
{
op = PHI_RESULT (phi);
n++;
}
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j,
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
{
struct version_info *info = ver_info (data, j);
if (info->inv_id && info->has_nonlin_use)
n++;
- });
+ }
loop_data (loop)->regs_used = n;
if (dump_file && (dump_flags & TDF_DETAILS))
}
}
-/* Finds a best candidate for USE and stores it to CAND. The candidates are
- taken from the set SOL and they may depend on invariants in the set INV.
- The really used candidate and invariants are noted to USED_IVS and
- USED_INV. */
+/* Returns true if A is a cheaper cost pair than B. */
-static unsigned
-find_best_candidate (struct ivopts_data *data,
- struct iv_use *use, bitmap sol, bitmap inv,
- bitmap used_ivs, bitmap used_inv, struct iv_cand **cand)
+static bool
+cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
{
- unsigned c, d;
- unsigned best_cost = INFTY, cost;
- struct iv_cand *cnd = NULL, *acnd;
- bitmap depends_on = NULL, asol;
+ if (!a)
+ return false;
- if (data->consider_all_candidates)
- asol = sol;
- else
- {
- asol = BITMAP_XMALLOC ();
- bitmap_a_and_b (asol, sol, use->related_cands);
- }
+ if (!b)
+ return true;
- EXECUTE_IF_SET_IN_BITMAP (asol, 0, c,
+ if (a->cost < b->cost)
+ return true;
+
+ if (a->cost > b->cost)
+ return false;
+
+ /* In case the costs are the same, prefer the cheaper candidate. */
+ if (a->cand->cost < b->cand->cost)
+ return true;
+
+ return false;
+}
+
+/* Computes the cost field of IVS structure. */
+
+static void
+iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
+{
+ unsigned cost = 0;
+
+ cost += ivs->cand_use_cost;
+ cost += ivs->cand_cost;
+ cost += ivopts_global_cost_for_size (data, ivs->n_regs);
+
+ ivs->cost = cost;
+}
+
+/* Set USE not to be expressed by any candidate in IVS. */
+
+static void
+iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_use *use)
+{
+ unsigned uid = use->id, cid, iid;
+ bitmap deps;
+ struct cost_pair *cp;
+ bitmap_iterator bi;
+
+ cp = ivs->cand_for_use[uid];
+ if (!cp)
+ return;
+ cid = cp->cand->id;
+
+ ivs->bad_uses++;
+ ivs->cand_for_use[uid] = NULL;
+ ivs->n_cand_uses[cid]--;
+
+ if (ivs->n_cand_uses[cid] == 0)
{
- acnd = iv_cand (data, c);
- cost = get_use_iv_cost (data, use, acnd, &depends_on);
+ bitmap_clear_bit (ivs->cands, cid);
+ /* Do not count the pseudocandidates. */
+ if (cp->cand->iv)
+ ivs->n_regs--;
+ ivs->n_cands--;
+ ivs->cand_cost -= cp->cand->cost;
+ }
+
+ ivs->cand_use_cost -= cp->cost;
+
+ deps = cp->depends_on;
- if (cost == INFTY)
- goto next_cand;
- if (cost > best_cost)
- goto next_cand;
- if (cost == best_cost)
+ if (deps)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (deps, 0, iid, bi)
{
- /* Prefer the cheaper iv. */
- if (acnd->cost >= cnd->cost)
- goto next_cand;
+ ivs->n_invariant_uses[iid]--;
+ if (ivs->n_invariant_uses[iid] == 0)
+ ivs->n_regs--;
}
+ }
+
+ iv_ca_recount_cost (data, ivs);
+}
+
+/* Set cost pair for USE in set IVS to CP. */
- if (depends_on)
+static void
+iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_use *use, struct cost_pair *cp)
+{
+ unsigned uid = use->id, cid, iid;
+ bitmap deps;
+ bitmap_iterator bi;
+
+ if (ivs->cand_for_use[uid] == cp)
+ return;
+
+ if (ivs->cand_for_use[uid])
+ iv_ca_set_no_cp (data, ivs, use);
+
+ if (cp)
+ {
+ cid = cp->cand->id;
+
+ ivs->bad_uses--;
+ ivs->cand_for_use[uid] = cp;
+ ivs->n_cand_uses[cid]++;
+ if (ivs->n_cand_uses[cid] == 1)
{
- EXECUTE_IF_AND_COMPL_IN_BITMAP (depends_on, inv, 0, d,
- goto next_cand);
- if (used_inv)
- bitmap_a_or_b (used_inv, used_inv, depends_on);
+ bitmap_set_bit (ivs->cands, cid);
+ /* Do not count the pseudocandidates. */
+ if (cp->cand->iv)
+ ivs->n_regs++;
+ ivs->n_cands++;
+ ivs->cand_cost += cp->cand->cost;
}
- cnd = acnd;
- best_cost = cost;
-next_cand: ;
- });
+ ivs->cand_use_cost += cp->cost;
- if (cnd && used_ivs)
- bitmap_set_bit (used_ivs, cnd->id);
+ deps = cp->depends_on;
- if (cand)
- *cand = cnd;
+ if (deps)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (deps, 0, iid, bi)
+ {
+ ivs->n_invariant_uses[iid]++;
+ if (ivs->n_invariant_uses[iid] == 1)
+ ivs->n_regs++;
+ }
+ }
+
+ iv_ca_recount_cost (data, ivs);
+ }
+}
- if (!data->consider_all_candidates)
- BITMAP_XFREE (asol);
+/* Extend set IVS by expressing USE by some of the candidates in it
+ if possible. */
- return best_cost;
+static void
+iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_use *use)
+{
+ struct cost_pair *best_cp = NULL, *cp;
+ bitmap_iterator bi;
+ unsigned i;
+
+ gcc_assert (ivs->upto >= use->id);
+
+ if (ivs->upto == use->id)
+ {
+ ivs->upto++;
+ ivs->bad_uses++;
+ }
+
+ EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+ {
+ cp = get_use_iv_cost (data, use, iv_cand (data, i));
+
+ if (cheaper_cost_pair (cp, best_cp))
+ best_cp = cp;
+ }
+
+ iv_ca_set_cp (data, ivs, use, best_cp);
}
-/* Returns cost of set of ivs SOL + invariants INV. Removes unnecessary
- induction variable candidates and invariants from the sets. Only
- uses 0 .. MAX_USE - 1 are taken into account. */
+/* Get cost for assignment IVS. */
static unsigned
-set_cost_up_to (struct ivopts_data *data, bitmap sol, bitmap inv,
- unsigned max_use)
+iv_ca_cost (struct iv_ca *ivs)
+{
+ return (ivs->bad_uses ? INFTY : ivs->cost);
+}
+
+/* Returns true if all dependences of CP are among invariants in IVS. */
+
+static bool
+iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
{
unsigned i;
- unsigned cost = 0, size = 0, acost;
+ bitmap_iterator bi;
+
+ if (!cp->depends_on)
+ return true;
+
+ EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
+ {
+ if (ivs->n_invariant_uses[i] == 0)
+ return false;
+ }
+
+ return true;
+}
+
+/* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
+ it before NEXT_CHANGE. */
+
+static struct iv_ca_delta *
+iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
+ struct cost_pair *new_cp, struct iv_ca_delta *next_change)
+{
+ struct iv_ca_delta *change = xmalloc (sizeof (struct iv_ca_delta));
+
+ change->use = use;
+ change->old_cp = old_cp;
+ change->new_cp = new_cp;
+ change->next_change = next_change;
+
+ 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 *
+iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
+{
+ 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. */
+
+static void
+iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_ca_delta *delta, bool forward)
+{
+ struct cost_pair *from, *to;
+ struct iv_ca_delta *act;
+
+ if (!forward)
+ delta = iv_ca_delta_reverse (delta);
+
+ 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. */
+
+static bool
+iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
+{
+ 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
+iv_ca_delta_free (struct iv_ca_delta **delta)
+{
+ struct iv_ca_delta *act, *next;
+
+ for (act = *delta; act; act = next)
+ {
+ next = act->next_change;
+ free (act);
+ }
+
+ *delta = NULL;
+}
+
+/* Allocates new iv candidates assignment. */
+
+static struct iv_ca *
+iv_ca_new (struct ivopts_data *data)
+{
+ struct iv_ca *nw = xmalloc (sizeof (struct iv_ca));
+
+ nw->upto = 0;
+ nw->bad_uses = 0;
+ nw->cand_for_use = xcalloc (n_iv_uses (data), sizeof (struct cost_pair *));
+ nw->n_cand_uses = xcalloc (n_iv_cands (data), sizeof (unsigned));
+ nw->cands = BITMAP_ALLOC (NULL);
+ nw->n_cands = 0;
+ nw->n_regs = 0;
+ nw->cand_use_cost = 0;
+ nw->cand_cost = 0;
+ nw->n_invariant_uses = xcalloc (data->max_inv_id + 1, sizeof (unsigned));
+ nw->cost = 0;
+
+ return nw;
+}
+
+/* Free memory occupied by the set IVS. */
+
+static void
+iv_ca_free (struct iv_ca **ivs)
+{
+ free ((*ivs)->cand_for_use);
+ free ((*ivs)->n_cand_uses);
+ BITMAP_FREE ((*ivs)->cands);
+ free ((*ivs)->n_invariant_uses);
+ free (*ivs);
+ *ivs = NULL;
+}
+
+/* Dumps IVS to FILE. */
+
+static void
+iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
+{
+ const char *pref = " invariants ";
+ unsigned i;
+
+ fprintf (file, " cost %d\n", iv_ca_cost (ivs));
+ bitmap_print (file, ivs->cands, " candidates ","\n");
+
+ for (i = 1; i <= data->max_inv_id; i++)
+ if (ivs->n_invariant_uses[i])
+ {
+ fprintf (file, "%s%d", pref, i);
+ pref = ", ";
+ }
+ fprintf (file, "\n");
+}
+
+/* Try changing candidate in IVS to CAND for each use. Return cost of the
+ 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,
+ unsigned *n_ivs)
+{
+ unsigned i, cost;
struct iv_use *use;
- struct iv_cand *cand;
- bitmap used_ivs = BITMAP_XMALLOC (), used_inv = BITMAP_XMALLOC ();
+ struct cost_pair *old_cp, *new_cp;
- for (i = 0; i < max_use; i++)
+ *delta = NULL;
+ for (i = 0; i < ivs->upto; i++)
{
use = iv_use (data, i);
- acost = find_best_candidate (data, use, sol, inv,
- used_ivs, used_inv, NULL);
- if (acost == INFTY)
- {
- BITMAP_XFREE (used_ivs);
- BITMAP_XFREE (used_inv);
- return INFTY;
- }
- cost += acost;
+ old_cp = iv_ca_cand_for_use (ivs, use);
+
+ if (old_cp
+ && old_cp->cand == cand)
+ continue;
+
+ new_cp = get_use_iv_cost (data, use, cand);
+ if (!new_cp)
+ continue;
+
+ if (!iv_ca_has_deps (ivs, new_cp))
+ continue;
+
+ if (!cheaper_cost_pair (new_cp, old_cp))
+ continue;
+
+ *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
}
- EXECUTE_IF_SET_IN_BITMAP (used_ivs, 0, i,
+ 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 narrowing set IVS by removing CAND. Return the cost of
+ the new set and store the differences in DELTA. */
+
+static unsigned
+iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_cand *cand, struct iv_ca_delta **delta)
+{
+ unsigned i, ci;
+ struct iv_use *use;
+ struct cost_pair *old_cp, *new_cp, *cp;
+ bitmap_iterator bi;
+ struct iv_cand *cnd;
+ unsigned cost;
+
+ *delta = NULL;
+ for (i = 0; i < n_iv_uses (data); i++)
{
- cand = iv_cand (data, i);
+ use = iv_use (data, i);
- /* Do not count the pseudocandidates. */
- if (cand->iv)
- size++;
+ old_cp = iv_ca_cand_for_use (ivs, use);
+ if (old_cp->cand != cand)
+ continue;
+
+ new_cp = NULL;
+
+ if (data->consider_all_candidates)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
+ {
+ if (ci == cand->id)
+ continue;
+
+ cnd = iv_cand (data, ci);
+
+ cp = get_use_iv_cost (data, use, cnd);
+ if (!cp)
+ continue;
+ if (!iv_ca_has_deps (ivs, cp))
+ continue;
+
+ if (!cheaper_cost_pair (cp, new_cp))
+ continue;
- cost += cand->cost;
- });
- EXECUTE_IF_SET_IN_BITMAP (used_inv, 0, i, size++);
- cost += ivopts_global_cost_for_size (data, size);
+ new_cp = cp;
+ }
+ }
+ else
+ {
+ EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
+ {
+ if (ci == cand->id)
+ continue;
+
+ cnd = iv_cand (data, ci);
+
+ cp = get_use_iv_cost (data, use, cnd);
+ if (!cp)
+ continue;
+ if (!iv_ca_has_deps (ivs, cp))
+ continue;
+
+ if (!cheaper_cost_pair (cp, new_cp))
+ continue;
- bitmap_copy (sol, used_ivs);
- bitmap_copy (inv, used_inv);
+ new_cp = cp;
+ }
+ }
- BITMAP_XFREE (used_ivs);
- BITMAP_XFREE (used_inv);
+ if (!new_cp)
+ {
+ iv_ca_delta_free (delta);
+ return INFTY;
+ }
+
+ *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
+ }
+
+ iv_ca_delta_commit (data, ivs, *delta, true);
+ cost = iv_ca_cost (ivs);
+ iv_ca_delta_commit (data, ivs, *delta, false);
return cost;
}
-/* Computes cost of set of ivs SOL + invariants INV. Removes unnecessary
- induction variable candidates and invariants from the sets. */
+/* 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
-set_cost (struct ivopts_data *data, bitmap sol, bitmap inv)
+iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_cand *except_cand, struct iv_ca_delta **delta)
{
- return set_cost_up_to (data, sol, inv, n_iv_uses (data));
+ 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 and INV in the best possible way in order
+/* Tries to extend the sets IVS in the best possible way in order
to express the USE. */
static bool
-try_add_cand_for (struct ivopts_data *data, bitmap ivs, bitmap inv,
+try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use)
{
- unsigned best_cost = set_cost_up_to (data, ivs, inv, use->id + 1), act_cost;
- bitmap best_ivs = BITMAP_XMALLOC ();
- bitmap best_inv = BITMAP_XMALLOC ();
- bitmap act_ivs = BITMAP_XMALLOC ();
- bitmap act_inv = BITMAP_XMALLOC ();
+ unsigned best_cost, act_cost;
unsigned i;
+ bitmap_iterator bi;
+ struct iv_cand *cand;
+ struct iv_ca_delta *best_delta = NULL, *act_delta;
struct cost_pair *cp;
- bitmap_copy (best_ivs, ivs);
- bitmap_copy (best_inv, inv);
+ iv_ca_add_use (data, ivs, use);
+ best_cost = iv_ca_cost (ivs);
- for (i = 0; i < use->n_map_members; i++)
+ cp = iv_ca_cand_for_use (ivs, use);
+ if (cp)
{
- cp = use->cost_map + i;
- if (cp->cost == INFTY)
+ best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
+ iv_ca_set_no_cp (data, ivs, use);
+ }
+
+ /* 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)
+ {
+ cand = iv_cand (data, i);
+
+ if (iv_ca_cand_used_p (ivs, cand))
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);
- else
- bitmap_copy (act_inv, inv);
- act_cost = set_cost_up_to (data, act_ivs, act_inv, use->id + 1);
+ cp = get_use_iv_cost (data, use, cand);
+ if (!cp)
+ continue;
+
+ iv_ca_set_cp (data, ivs, use, cp);
+ 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);
if (act_cost < best_cost)
{
best_cost = act_cost;
- bitmap_copy (best_ivs, act_ivs);
- bitmap_copy (best_inv, act_inv);
+
+ iv_ca_delta_free (&best_delta);
+ best_delta = act_delta;
}
+ else
+ iv_ca_delta_free (&act_delta);
}
- bitmap_copy (ivs, best_ivs);
- bitmap_copy (inv, best_inv);
+ if (best_cost == INFTY)
+ {
+ for (i = 0; i < use->n_map_members; i++)
+ {
+ cp = use->cost_map + i;
+ cand = cp->cand;
+ if (!cand)
+ continue;
+
+ /* Already tried this. */
+ if (cand->important)
+ continue;
+
+ if (iv_ca_cand_used_p (ivs, cand))
+ continue;
+
+ act_delta = NULL;
+ iv_ca_set_cp (data, ivs, use, cp);
+ 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);
+
+ if (act_cost < best_cost)
+ {
+ best_cost = act_cost;
+
+ if (best_delta)
+ iv_ca_delta_free (&best_delta);
+ best_delta = act_delta;
+ }
+ else
+ iv_ca_delta_free (&act_delta);
+ }
+ }
- BITMAP_XFREE (best_ivs);
- BITMAP_XFREE (best_inv);
- BITMAP_XFREE (act_ivs);
- BITMAP_XFREE (act_inv);
+ iv_ca_delta_commit (data, ivs, best_delta, true);
+ iv_ca_delta_free (&best_delta);
return (best_cost != INFTY);
}
-/* Finds an initial set of IVS and invariants INV. We do this by simply
- choosing the best candidate for each use. */
+/* Finds an initial assignment of candidates to uses. */
-static unsigned
-get_initial_solution (struct ivopts_data *data, bitmap ivs, bitmap inv)
+static struct iv_ca *
+get_initial_solution (struct ivopts_data *data)
{
+ struct iv_ca *ivs = iv_ca_new (data);
unsigned i;
for (i = 0; i < n_iv_uses (data); i++)
- if (!try_add_cand_for (data, ivs, inv, iv_use (data, i)))
- return INFTY;
+ if (!try_add_cand_for (data, ivs, iv_use (data, i)))
+ {
+ iv_ca_free (&ivs);
+ return NULL;
+ }
- return set_cost (data, ivs, inv);
+ return ivs;
}
-/* Tries to improve set of induction variables IVS and invariants INV to get
- it better than COST. */
+/* Tries to improve set of induction variables IVS. */
static bool
-try_improve_iv_set (struct ivopts_data *data,
- bitmap ivs, bitmap inv, unsigned *cost)
+try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned i, acost;
- bitmap new_ivs = BITMAP_XMALLOC (), new_inv = BITMAP_XMALLOC ();
- bitmap best_new_ivs = NULL, best_new_inv = NULL;
+ 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++)
{
- bitmap_copy (new_ivs, ivs);
- bitmap_copy (new_inv, inv);
-
- if (bitmap_bit_p (ivs, i))
- bitmap_clear_bit (new_ivs, i);
- else
- bitmap_set_bit (new_ivs, i);
-
- acost = set_cost (data, new_ivs, new_inv);
- if (acost >= *cost)
+ cand = iv_cand (data, i);
+
+ if (iv_ca_cand_used_p (ivs, cand))
continue;
- if (!best_new_ivs)
- {
- best_new_ivs = BITMAP_XMALLOC ();
- best_new_inv = BITMAP_XMALLOC ();
- }
-
- *cost = acost;
- bitmap_copy (best_new_ivs, new_ivs);
- bitmap_copy (best_new_inv, new_inv);
- }
-
- /* Ditto for invariants. */
- for (i = 1; i <= data->max_inv_id; i++)
- {
- if (ver_info (data, i)->has_nonlin_use)
+ acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
+ if (!act_delta)
continue;
- bitmap_copy (new_ivs, ivs);
- bitmap_copy (new_inv, inv);
-
- if (bitmap_bit_p (inv, i))
- bitmap_clear_bit (new_inv, i);
- else
- bitmap_set_bit (new_inv, i);
-
- acost = set_cost (data, new_ivs, new_inv);
- if (acost >= *cost)
- 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 (!best_new_ivs)
+ if (acost < best_cost)
{
- best_new_ivs = BITMAP_XMALLOC ();
- best_new_inv = BITMAP_XMALLOC ();
+ best_cost = acost;
+ iv_ca_delta_free (&best_delta);
+ best_delta = act_delta;
}
-
- *cost = acost;
- bitmap_copy (best_new_ivs, new_ivs);
- bitmap_copy (best_new_inv, new_inv);
+ else
+ iv_ca_delta_free (&act_delta);
}
- BITMAP_XFREE (new_ivs);
- BITMAP_XFREE (new_inv);
+ if (!best_delta)
+ {
+ /* Try removing the candidates from the set instead. */
+ best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
- if (!best_new_ivs)
- return false;
+ /* Nothing more we can do. */
+ if (!best_delta)
+ return false;
+ }
- bitmap_copy (ivs, best_new_ivs);
- bitmap_copy (inv, best_new_inv);
- BITMAP_XFREE (best_new_ivs);
- BITMAP_XFREE (best_new_inv);
+ 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;
}
greedy heuristic -- we try to replace at most one candidate in the selected
solution and remove the unused ivs while this improves the cost. */
-static bitmap
+static struct iv_ca *
find_optimal_iv_set (struct ivopts_data *data)
{
- unsigned cost, i;
- bitmap set = BITMAP_XMALLOC ();
- bitmap inv = BITMAP_XMALLOC ();
+ unsigned i;
+ struct iv_ca *set;
struct iv_use *use;
- /* Set the upper bound. */
- cost = get_initial_solution (data, set, inv);
- if (cost == INFTY)
+ /* Get the initial solution. */
+ set = get_initial_solution (data);
+ if (!set)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
- BITMAP_XFREE (inv);
- BITMAP_XFREE (set);
return NULL;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "Initial set of candidates (cost %d): ", cost);
- bitmap_print (dump_file, set, "", "");
- fprintf (dump_file, " invariants ");
- bitmap_print (dump_file, inv, "", "");
- fprintf (dump_file, "\n");
+ fprintf (dump_file, "Initial set of candidates:\n");
+ iv_ca_dump (data, dump_file, set);
}
- while (try_improve_iv_set (data, set, inv, &cost))
+ while (try_improve_iv_set (data, set))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "Improved to (cost %d): ", cost);
- bitmap_print (dump_file, set, "", "");
- fprintf (dump_file, " invariants ");
- bitmap_print (dump_file, inv, "", "");
- fprintf (dump_file, "\n");
+ fprintf (dump_file, "Improved to:\n");
+ iv_ca_dump (data, dump_file, set);
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Final cost %d\n\n", cost);
+ fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
for (i = 0; i < n_iv_uses (data); i++)
{
use = iv_use (data, i);
- find_best_candidate (data, use, set, inv, NULL, NULL, &use->selected);
+ use->selected = iv_ca_cand_for_use (set, use)->cand;
}
- BITMAP_XFREE (inv);
-
return set;
}
/* Creates new induction variables described in SET. */
static void
-create_new_ivs (struct ivopts_data *data, bitmap set)
+create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
{
unsigned i;
struct iv_cand *cand;
+ bitmap_iterator bi;
- EXECUTE_IF_SET_IN_BITMAP (set, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
{
cand = iv_cand (data, i);
create_new_iv (data, cand);
- });
+ }
}
/* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
/* 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
{
- block_stmt_iterator bsi = stmt_for_bsi (stmt);
+ block_stmt_iterator bsi = bsi_for_stmt (stmt);
bsi_remove (&bsi);
}
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;
-
- if (TREE_CODE (use->stmt) == PHI_NODE)
+
+ /* 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:
tgt = PHI_RESULT (use->stmt);
/* If we should keep the biv, do not replace it. */
bsi = pbsi;
bsi_next (&pbsi);
}
- }
- else if (TREE_CODE (use->stmt) == MODIFY_EXPR)
- {
+ break;
+
+ case MODIFY_EXPR:
tgt = TREE_OPERAND (use->stmt, 0);
- bsi = stmt_for_bsi (use->stmt);
+ bsi = bsi_for_stmt (use->stmt);
+ break;
+
+ default:
+ gcc_unreachable ();
}
- else
- abort ();
op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
for_each_index. */
static bool
-idx_remove_ssa_names (tree base ATTRIBUTE_UNUSED, tree *idx,
+idx_remove_ssa_names (tree base, tree *idx,
void *data ATTRIBUTE_UNUSED)
{
+ tree *op;
+
if (TREE_CODE (*idx) == SSA_NAME)
*idx = SSA_NAME_VAR (*idx);
+
+ if (TREE_CODE (base) == ARRAY_REF)
+ {
+ op = &TREE_OPERAND (base, 2);
+ if (*op
+ && TREE_CODE (*op) == SSA_NAME)
+ *op = SSA_NAME_VAR (*op);
+ op = &TREE_OPERAND (base, 3);
+ if (*op
+ && TREE_CODE (*op) == SSA_NAME)
+ *op = SSA_NAME_VAR (*op);
+ }
+
return true;
}
static void
rewrite_address_base (block_stmt_iterator *bsi, tree *op, tree with)
{
- tree var = get_base_address (*op), new_var, new_name, copy, name;
+ tree bvar, var, new_var, new_name, copy, name;
tree orig;
+ var = bvar = get_base_address (*op);
+
if (!var || TREE_CODE (with) != SSA_NAME)
goto do_rewrite;
+ gcc_assert (TREE_CODE (var) != ALIGN_INDIRECT_REF);
+ gcc_assert (TREE_CODE (var) != MISALIGNED_INDIRECT_REF);
if (TREE_CODE (var) == INDIRECT_REF)
var = TREE_OPERAND (var, 0);
if (TREE_CODE (var) == SSA_NAME)
do_rewrite:
orig = NULL_TREE;
+ gcc_assert (TREE_CODE (*op) != ALIGN_INDIRECT_REF);
+ gcc_assert (TREE_CODE (*op) != MISALIGNED_INDIRECT_REF);
+
if (TREE_CODE (*op) == INDIRECT_REF)
orig = REF_ORIGINAL (*op);
if (!orig)
orig = unshare_and_remove_ssa_names (*op);
*op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
+
/* Record the original reference, for purposes of alias analysis. */
REF_ORIGINAL (*op) = orig;
}
{
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,
- 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;
}
return;
/* Try finding a phi node that copies the value out of the loop. */
- for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == use)
break;
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 (exit->dest->pred->pred_next)
+ 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)
{
tree value, op, stmts, tgt;
tree phi;
- if (TREE_CODE (use->stmt) == PHI_NODE)
- tgt = PHI_RESULT (use->stmt);
- else if (TREE_CODE (use->stmt) == MODIFY_EXPR)
- tgt = TREE_OPERAND (use->stmt, 0);
- else
- abort ();
+ switch (TREE_CODE (use->stmt))
+ {
+ case PHI_NODE:
+ tgt = PHI_RESULT (use->stmt);
+ break;
+ case MODIFY_EXPR:
+ tgt = TREE_OPERAND (use->stmt, 0);
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
exit = single_dom_exit (data->current_loop);
if (exit)
{
if (!cand->iv)
{
- if (!may_replace_final_value (data->current_loop, use, &value))
- abort ();
+ bool ok = may_replace_final_value (data, use, &value);
+ gcc_assert (ok);
}
else
value = get_computation_at (data->current_loop,
use, cand, last_stmt (exit->src));
+ value = unshare_expr (value);
op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
/* If we will preserve the iv anyway and we would need to perform
if (stmts && name_info (data, tgt)->preserve_biv)
return;
- for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
{
use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
break;
default:
- abort ();
+ gcc_unreachable ();
}
modify_stmt (use->stmt);
}
{
use = iv_use (data, i);
cand = use->selected;
- if (!cand)
- abort ();
+ gcc_assert (cand);
rewrite_use (data, use, cand);
}
remove_unused_ivs (struct ivopts_data *data)
{
unsigned j;
+ bitmap_iterator bi;
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j,
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
{
struct version_info *info;
&& !info->iv->have_use_for
&& !info->preserve_biv)
remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
- });
+ }
}
/* Frees data allocated by the optimization of a single loop. */
free_loop_data (struct ivopts_data *data)
{
unsigned i, j;
+ bitmap_iterator bi;
+
+ htab_empty (data->niters);
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
struct version_info *info;
info->has_nonlin_use = false;
info->preserve_biv = false;
info->inv_id = 0;
- });
+ }
bitmap_clear (data->relevant);
+ bitmap_clear (data->important_candidates);
for (i = 0; i < n_iv_uses (data); i++)
{
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_FREE (data->relevant);
+ BITMAP_FREE (data->important_candidates);
+ htab_delete (data->niters);
VARRAY_FREE (decl_rtl_to_reset);
VARRAY_FREE (data->iv_uses);
tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
{
bool changed = false;
- bitmap iv_set;
+ struct iv_ca *iv_ca;
edge exit;
data->current_loop = loop;
determine_set_costs (data);
/* Find the optimal set of induction variables (item 3, part 2). */
- iv_set = find_optimal_iv_set (data);
- if (!iv_set)
+ iv_ca = find_optimal_iv_set (data);
+ if (!iv_ca)
goto finish;
changed = true;
/* Create the new induction variables (item 4, part 1). */
- create_new_ivs (data, iv_set);
+ create_new_ivs (data, iv_ca);
+ iv_ca_free (&iv_ca);
/* Rewrite the uses (item 4, part 2). */
rewrite_uses (data);
/* Remove the ivs that are unused after rewriting. */
remove_unused_ivs (data);
- loop_commit_inserts ();
-
- BITMAP_XFREE (iv_set);
-
/* 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. */
{
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
