/* Induction variable optimizations.
- Copyright (C) 2003-2014 Free Software Foundation, Inc.
+ Copyright (C) 2003-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
#include "stor-layout.h"
#include "tm_p.h"
+#include "predict.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
-#include "pointer-set.h"
-#include "hash-table.h"
#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "tree-eh.h"
#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
+#include "rtl.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "tree-dfa.h"
#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-pass.h"
-#include "insn-config.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
-#include "cfgloop.h"
#include "params.h"
#include "langhooks.h"
#include "tree-affine.h"
#include "target.h"
#include "tree-inline.h"
#include "tree-ssa-propagate.h"
-#include "expmed.h"
#include "tree-ssa-address.h"
#include "builtins.h"
+#include "tree-vectorizer.h"
/* FIXME: Expressions are expanded to RTL in this pass to determine the
cost of different addressing modes. This should be moved to a TBD
interface between the GIMPLE and RTL worlds. */
-#include "expr.h"
#include "recog.h"
/* The infinite cost. */
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. */
+ unsigned use_id; /* The identifier in the use if it is the case. */
bool biv_p; /* Is it a biv? */
bool have_use_for; /* Do we already have a use for it? */
- unsigned use_id; /* The identifier in the use if it is the case. */
+ bool no_overflow; /* True if the iv doesn't overflow. */
};
/* Per-ssa version information (induction variable descriptions, etc.). */
struct iv_use
{
unsigned id; /* The id of the use. */
+ unsigned sub_id; /* The id of the sub use. */
enum use_type type; /* Type of the use. */
struct iv *iv; /* The induction variable it is based on. */
gimple stmt; /* Statement in that it occurs. */
struct iv_cand *selected;
/* The selected candidate. */
+
+ struct iv_use *next; /* The next sub use. */
+ tree addr_base; /* Base address with const offset stripped. */
+ unsigned HOST_WIDE_INT addr_offset;
+ /* Const offset stripped from base address. */
};
/* The position where the iv is computed. */
/* Hashtable helpers. */
-struct iv_inv_expr_hasher : typed_free_remove <iv_inv_expr_ent>
+struct iv_inv_expr_hasher : free_ptr_hash <iv_inv_expr_ent>
{
- typedef iv_inv_expr_ent value_type;
- typedef iv_inv_expr_ent compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const iv_inv_expr_ent *);
+ static inline bool equal (const iv_inv_expr_ent *, const iv_inv_expr_ent *);
};
/* Hash function for loop invariant expressions. */
inline hashval_t
-iv_inv_expr_hasher::hash (const value_type *expr)
+iv_inv_expr_hasher::hash (const iv_inv_expr_ent *expr)
{
return expr->hash;
}
/* Hash table equality function for expressions. */
inline bool
-iv_inv_expr_hasher::equal (const value_type *expr1, const compare_type *expr2)
+iv_inv_expr_hasher::equal (const iv_inv_expr_ent *expr1,
+ const iv_inv_expr_ent *expr2)
{
return expr1->hash == expr2->hash
&& operand_equal_p (expr1->expr, expr2->expr, 0);
{
/* The currently optimized loop. */
struct loop *current_loop;
+ source_location loop_loc;
/* Numbers of iterations for all exits of the current loop. */
- struct pointer_map_t *niters;
+ hash_map<edge, tree_niter_desc *> *niters;
/* Number of registers used in it. */
unsigned regs_used;
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* Cache used by tree_to_aff_combination_expand. */
+ hash_map<tree, name_expansion *> *name_expansion_cache;
+
/* The maximum invariant id. */
unsigned max_inv_id;
/* Dumps information about the induction variable IV to FILE. */
void
-dump_iv (FILE *file, struct iv *iv)
+dump_iv (FILE *file, struct iv *iv, bool dump_name)
{
- if (iv->ssa_name)
+ if (iv->ssa_name && dump_name)
{
fprintf (file, "ssa name ");
print_generic_expr (file, iv->ssa_name, TDF_SLIM);
void
dump_use (FILE *file, struct iv_use *use)
{
- fprintf (file, "use %d\n", use->id);
+ fprintf (file, "use %d", use->id);
+ if (use->sub_id)
+ fprintf (file, ".%d", use->sub_id);
+
+ fprintf (file, "\n");
switch (use->type)
{
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
- dump_iv (file, use->iv);
+ dump_iv (file, use->iv, false);
if (use->related_cands)
{
for (i = 0; i < n_iv_uses (data); i++)
{
use = iv_use (data, i);
-
- dump_use (file, use);
+ do
+ {
+ dump_use (file, use);
+ use = use->next;
+ }
+ while (use);
fprintf (file, "\n");
}
}
break;
}
- dump_iv (file, iv);
+ dump_iv (file, iv, false);
}
/* Returns the info for ssa version VER. */
niter_for_exit (struct ivopts_data *data, edge exit)
{
struct tree_niter_desc *desc;
- void **slot;
+ tree_niter_desc **slot;
if (!data->niters)
{
- data->niters = pointer_map_create ();
+ data->niters = new hash_map<edge, tree_niter_desc *>;
slot = NULL;
}
else
- slot = pointer_map_contains (data->niters, exit);
+ slot = data->niters->get (exit);
if (!slot)
{
XDELETE (desc);
desc = NULL;
}
- slot = pointer_map_insert (data->niters, exit);
- *slot = desc;
+ data->niters->put (exit, desc);
}
else
- desc = (struct tree_niter_desc *) *slot;
+ desc = *slot;
return desc;
}
data->iv_candidates.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->inv_expr_id = 0;
+ data->name_expansion_cache = NULL;
decl_rtl_to_reset.create (20);
}
}
/* Allocates an induction variable with given initial value BASE and step STEP
- for loop LOOP. */
+ for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. */
static struct iv *
-alloc_iv (tree base, tree step)
+alloc_iv (tree base, tree step, bool no_overflow = false)
{
tree expr = base;
struct iv *iv = XCNEW (struct iv);
iv->have_use_for = false;
iv->use_id = 0;
iv->ssa_name = NULL_TREE;
+ iv->no_overflow = no_overflow;
return iv;
}
-/* Sets STEP and BASE for induction variable IV. */
+/* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
+ doesn't overflow. */
static void
-set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
+set_iv (struct ivopts_data *data, tree iv, tree base, tree step,
+ bool no_overflow)
{
struct version_info *info = name_info (data, iv);
gcc_assert (!info->iv);
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
- info->iv = alloc_iv (base, step);
+ info->iv = alloc_iv (base, step, no_overflow);
info->iv->ssa_name = iv;
}
if (!bb
|| !flow_bb_inside_loop_p (data->current_loop, bb))
- set_iv (data, var, var, build_int_cst (type, 0));
+ set_iv (data, var, var, build_int_cst (type, 0), true);
}
return name_info (data, var)->iv;
}
-/* Determines the step of a biv defined in PHI. Returns NULL if PHI does
- not define a simple affine biv with nonzero step. */
+/* Return the first non-invariant ssa var found in EXPR. */
static tree
-determine_biv_step (gimple phi)
+extract_single_var_from_expr (tree expr)
{
- struct loop *loop = gimple_bb (phi)->loop_father;
- tree name = PHI_RESULT (phi);
- affine_iv iv;
+ int i, n;
+ tree tmp;
+ enum tree_code code;
- if (virtual_operand_p (name))
- return NULL_TREE;
+ if (!expr || is_gimple_min_invariant (expr))
+ return NULL;
- if (!simple_iv (loop, loop, name, &iv, true))
- return NULL_TREE;
+ code = TREE_CODE (expr);
+ if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
+ {
+ n = TREE_OPERAND_LENGTH (expr);
+ for (i = 0; i < n; i++)
+ {
+ tmp = extract_single_var_from_expr (TREE_OPERAND (expr, i));
- return integer_zerop (iv.step) ? NULL_TREE : iv.step;
+ if (tmp)
+ return tmp;
+ }
+ }
+ return (TREE_CODE (expr) == SSA_NAME) ? expr : NULL;
}
/* Finds basic ivs. */
static bool
find_bivs (struct ivopts_data *data)
{
- gimple phi;
- tree step, type, base;
+ gphi *phi;
+ affine_iv iv;
+ tree step, type, base, stop;
bool found = false;
struct loop *loop = data->current_loop;
- gimple_stmt_iterator psi;
+ gphi_iterator psi;
for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
- phi = gsi_stmt (psi);
+ phi = psi.phi ();
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
continue;
- step = determine_biv_step (phi);
- if (!step)
+ if (virtual_operand_p (PHI_RESULT (phi)))
continue;
+ if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
+ continue;
+
+ if (integer_zerop (iv.step))
+ continue;
+
+ step = iv.step;
base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
- base = expand_simple_operations (base);
+ /* Stop expanding iv base at the first ssa var referred by iv step.
+ Ideally we should stop at any ssa var, because that's expensive
+ and unusual to happen, we just do it on the first one.
+
+ See PR64705 for the rationale. */
+ stop = extract_single_var_from_expr (step);
+ base = expand_simple_operations (base, stop);
if (contains_abnormal_ssa_name_p (base)
|| contains_abnormal_ssa_name_p (step))
continue;
step = fold_convert (type, step);
}
- set_iv (data, PHI_RESULT (phi), base, step);
+ set_iv (data, PHI_RESULT (phi), base, step, iv.no_overflow);
found = true;
}
static void
mark_bivs (struct ivopts_data *data)
{
- gimple phi, def;
+ gphi *phi;
+ gimple def;
tree var;
struct iv *iv, *incr_iv;
struct loop *loop = data->current_loop;
basic_block incr_bb;
- gimple_stmt_iterator psi;
+ gphi_iterator psi;
for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
- phi = gsi_stmt (psi);
+ phi = psi.phi ();
iv = get_iv (data, PHI_RESULT (phi));
if (!iv)
static bool
find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv)
{
- tree lhs;
+ tree lhs, stop;
struct loop *loop = data->current_loop;
iv->base = NULL_TREE;
if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
return false;
- iv->base = expand_simple_operations (iv->base);
+ /* Stop expanding iv base at the first ssa var referred by iv step.
+ Ideally we should stop at any ssa var, because that's expensive
+ and unusual to happen, we just do it on the first one.
+
+ See PR64705 for the rationale. */
+ stop = extract_single_var_from_expr (iv->step);
+ iv->base = expand_simple_operations (iv->base, stop);
if (contains_abnormal_ssa_name_p (iv->base)
|| contains_abnormal_ssa_name_p (iv->step))
return false;
- /* If STMT could throw, then do not consider STMT as defining a GIV.
+ /* If STMT could throw, then do not consider STMT as defining a GIV.
While this will suppress optimizations, we can not safely delete this
GIV and associated statements, even if it appears it is not used. */
if (stmt_could_throw_p (stmt))
if (!find_givs_in_stmt_scev (data, stmt, &iv))
return;
- set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step);
+ set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step, iv.no_overflow);
}
/* Finds general ivs in basic block BB. */
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);
+ dump_iv (dump_file, ver_info (data, i)->iv, true);
}
}
return true;
}
-/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
+/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.
+ For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
+ is the const offset stripped from IV base. For uses of other types,
+ ADDR_BASE and ADDR_OFFSET are zero by default. */
static struct iv_use *
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
- gimple stmt, enum use_type use_type)
+ gimple stmt, enum use_type use_type, tree addr_base = NULL,
+ unsigned HOST_WIDE_INT addr_offset = 0)
{
struct iv_use *use = XCNEW (struct iv_use);
use->id = n_iv_uses (data);
+ use->sub_id = 0;
use->type = use_type;
use->iv = iv;
use->stmt = stmt;
use->op_p = use_p;
use->related_cands = BITMAP_ALLOC (NULL);
+ use->next = NULL;
+ use->addr_base = addr_base;
+ use->addr_offset = addr_offset;
+
+ data->iv_uses.safe_push (use);
+
+ return use;
+}
+
+/* Records a sub use of type USE_TYPE at *USE_P in STMT whose value is IV.
+ The sub use is recorded under the one whose use id is ID_GROUP. */
+
+static struct iv_use *
+record_sub_use (struct ivopts_data *data, tree *use_p,
+ struct iv *iv, gimple stmt, enum use_type use_type,
+ tree addr_base, unsigned HOST_WIDE_INT addr_offset,
+ unsigned int id_group)
+{
+ struct iv_use *use = XCNEW (struct iv_use);
+ struct iv_use *group = iv_use (data, id_group);
+
+ use->id = group->id;
+ use->sub_id = 0;
+ use->type = use_type;
+ use->iv = iv;
+ use->stmt = stmt;
+ use->op_p = use_p;
+ use->related_cands = NULL;
+ use->addr_base = addr_base;
+ use->addr_offset = addr_offset;
+
+ /* Sub use list is maintained in offset ascending order. */
+ if (addr_offset <= group->addr_offset)
+ {
+ use->related_cands = group->related_cands;
+ group->related_cands = NULL;
+ use->next = group;
+ data->iv_uses[id_group] = use;
+ }
+ else
+ {
+ struct iv_use *pre;
+ do
+ {
+ pre = group;
+ group = group->next;
+ }
+ while (group && addr_offset > group->addr_offset);
+ use->next = pre->next;
+ pre->next = use;
+ }
/* 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);
-
- data->iv_uses.safe_push (use);
-
return use;
}
/* The objects returned when COND has constant operands. */
static struct iv const_iv;
static tree zero;
- tree *op0 = &zero, *op1 = &zero, *tmp_op;
- struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+ tree *op0 = &zero, *op1 = &zero;
+ struct iv *iv0 = &const_iv, *iv1 = &const_iv;
bool ret = false;
if (gimple_code (stmt) == GIMPLE_COND)
{
- op0 = gimple_cond_lhs_ptr (stmt);
- op1 = gimple_cond_rhs_ptr (stmt);
+ gcond *cond_stmt = as_a <gcond *> (stmt);
+ op0 = gimple_cond_lhs_ptr (cond_stmt);
+ op1 = gimple_cond_rhs_ptr (cond_stmt);
}
else
{
if (integer_zerop (iv0->step))
{
/* Control variable may be on the other side. */
- tmp_op = op0; op0 = op1; op1 = tmp_op;
- tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
+ std::swap (op0, op1);
+ std::swap (iv0, iv1);
}
ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
end:
if (control_var)
- *control_var = op0;;
+ *control_var = op0;
if (iv_var)
- *iv_var = iv0;;
+ *iv_var = iv0;
if (bound)
*bound = op1;
if (iv_bound)
{
struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
struct iv *iv;
+ bool use_overflow_semantics = false;
tree step, iv_base, iv_step, lbound, off;
struct loop *loop = dta->ivopts_data->current_loop;
iv_base = iv->base;
iv_step = iv->step;
+ if (iv->no_overflow && nowrap_type_p (TREE_TYPE (iv_step)))
+ use_overflow_semantics = true;
+
if (!convert_affine_scev (dta->ivopts_data->current_loop,
sizetype, &iv_base, &iv_step, dta->stmt,
- false))
+ use_overflow_semantics))
{
/* The index might wrap. */
return false;
return false;
unsigned int align = TYPE_ALIGN (TREE_TYPE (ref));
+ if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref))) > align)
+ align = GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref)));
unsigned HOST_WIDE_INT bitpos;
unsigned int ref_align;
return false;
}
+static tree
+strip_offset (tree expr, unsigned HOST_WIDE_INT *offset);
+
+/* Record a use of type USE_TYPE at *USE_P in STMT whose value is IV.
+ If there is an existing use which has same stripped iv base and step,
+ this function records this one as a sub use to that; otherwise records
+ it as a normal one. */
+
+static struct iv_use *
+record_group_use (struct ivopts_data *data, tree *use_p,
+ struct iv *iv, gimple stmt, enum use_type use_type)
+{
+ unsigned int i;
+ struct iv_use *use;
+ tree addr_base;
+ unsigned HOST_WIDE_INT addr_offset;
+
+ /* Only support sub use for address type uses, that is, with base
+ object. */
+ if (!iv->base_object)
+ return record_use (data, use_p, iv, stmt, use_type);
+
+ addr_base = strip_offset (iv->base, &addr_offset);
+ for (i = 0; i < n_iv_uses (data); i++)
+ {
+ use = iv_use (data, i);
+ if (use->type != USE_ADDRESS || !use->iv->base_object)
+ continue;
+
+ /* Check if it has the same stripped base and step. */
+ if (operand_equal_p (iv->base_object, use->iv->base_object, 0)
+ && operand_equal_p (iv->step, use->iv->step, 0)
+ && operand_equal_p (addr_base, use->addr_base, 0))
+ break;
+ }
+
+ if (i == n_iv_uses (data))
+ return record_use (data, use_p, iv, stmt,
+ use_type, addr_base, addr_offset);
+ else
+ return record_sub_use (data, use_p, iv, stmt,
+ use_type, addr_base, addr_offset, i);
+}
+
/* Finds addresses in *OP_P inside STMT. */
static void
}
civ = alloc_iv (base, step);
- record_use (data, op_p, civ, stmt, USE_ADDRESS);
+ record_group_use (data, op_p, civ, stmt, USE_ADDRESS);
return;
fail:
static void
find_interesting_uses_outside (struct ivopts_data *data, edge exit)
{
- gimple phi;
- gimple_stmt_iterator psi;
+ gphi *phi;
+ gphi_iterator psi;
tree def;
for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
{
- phi = gsi_stmt (psi);
+ phi = psi.phi ();
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
if (!virtual_operand_p (def))
find_interesting_uses_op (data, def);
free (body);
}
+/* Compute maximum offset of [base + offset] addressing mode
+ for memory reference represented by USE. */
+
+static HOST_WIDE_INT
+compute_max_addr_offset (struct iv_use *use)
+{
+ int width;
+ rtx reg, addr;
+ HOST_WIDE_INT i, off;
+ unsigned list_index, num;
+ addr_space_t as;
+ machine_mode mem_mode, addr_mode;
+ static vec<HOST_WIDE_INT> max_offset_list;
+
+ as = TYPE_ADDR_SPACE (TREE_TYPE (use->iv->base));
+ mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
+
+ num = max_offset_list.length ();
+ list_index = (unsigned) as * MAX_MACHINE_MODE + (unsigned) mem_mode;
+ if (list_index >= num)
+ {
+ max_offset_list.safe_grow (list_index + MAX_MACHINE_MODE);
+ for (; num < max_offset_list.length (); num++)
+ max_offset_list[num] = -1;
+ }
+
+ off = max_offset_list[list_index];
+ if (off != -1)
+ return off;
+
+ addr_mode = targetm.addr_space.address_mode (as);
+ reg = gen_raw_REG (addr_mode, LAST_VIRTUAL_REGISTER + 1);
+ addr = gen_rtx_fmt_ee (PLUS, addr_mode, reg, NULL_RTX);
+
+ width = GET_MODE_BITSIZE (addr_mode) - 1;
+ if (width > (HOST_BITS_PER_WIDE_INT - 1))
+ width = HOST_BITS_PER_WIDE_INT - 1;
+
+ for (i = width; i > 0; i--)
+ {
+ off = ((unsigned HOST_WIDE_INT) 1 << i) - 1;
+ XEXP (addr, 1) = gen_int_mode (off, addr_mode);
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ break;
+
+ /* For some strict-alignment targets, the offset must be naturally
+ aligned. Try an aligned offset if mem_mode is not QImode. */
+ off = ((unsigned HOST_WIDE_INT) 1 << i);
+ if (off > GET_MODE_SIZE (mem_mode) && mem_mode != QImode)
+ {
+ off -= GET_MODE_SIZE (mem_mode);
+ XEXP (addr, 1) = gen_int_mode (off, addr_mode);
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ break;
+ }
+ }
+ if (i == 0)
+ off = 0;
+
+ max_offset_list[list_index] = off;
+ return off;
+}
+
+/* Check if all small groups should be split. Return true if and
+ only if:
+
+ 1) At least one groups contain two uses with different offsets.
+ 2) No group contains more than two uses with different offsets.
+
+ Return false otherwise. We want to split such groups because:
+
+ 1) Small groups don't have much benefit and may interfer with
+ general candidate selection.
+ 2) Size for problem with only small groups is usually small and
+ general algorithm can handle it well.
+
+ TODO -- Above claim may not hold when auto increment is supported. */
+
+static bool
+split_all_small_groups (struct ivopts_data *data)
+{
+ bool split_p = false;
+ unsigned int i, n, distinct;
+ struct iv_use *pre, *use;
+
+ n = n_iv_uses (data);
+ for (i = 0; i < n; i++)
+ {
+ use = iv_use (data, i);
+ if (!use->next)
+ continue;
+
+ distinct = 1;
+ gcc_assert (use->type == USE_ADDRESS);
+ for (pre = use, use = use->next; use; pre = use, use = use->next)
+ {
+ if (pre->addr_offset != use->addr_offset)
+ distinct++;
+
+ if (distinct > 2)
+ return false;
+ }
+ if (distinct == 2)
+ split_p = true;
+ }
+
+ return split_p;
+}
+
+/* For each group of address type uses, this function further groups
+ these uses according to the maximum offset supported by target's
+ [base + offset] addressing mode. */
+
+static void
+group_address_uses (struct ivopts_data *data)
+{
+ HOST_WIDE_INT max_offset = -1;
+ unsigned int i, n, sub_id;
+ struct iv_use *pre, *use;
+ unsigned HOST_WIDE_INT addr_offset_first;
+
+ /* Reset max offset to split all small groups. */
+ if (split_all_small_groups (data))
+ max_offset = 0;
+
+ n = n_iv_uses (data);
+ for (i = 0; i < n; i++)
+ {
+ use = iv_use (data, i);
+ if (!use->next)
+ continue;
+
+ gcc_assert (use->type == USE_ADDRESS);
+ if (max_offset != 0)
+ max_offset = compute_max_addr_offset (use);
+
+ while (use)
+ {
+ sub_id = 0;
+ addr_offset_first = use->addr_offset;
+ /* Only uses with offset that can fit in offset part against
+ the first use can be grouped together. */
+ for (pre = use, use = use->next;
+ use && (use->addr_offset - addr_offset_first
+ <= (unsigned HOST_WIDE_INT) max_offset);
+ pre = use, use = use->next)
+ {
+ use->id = pre->id;
+ use->sub_id = ++sub_id;
+ }
+
+ /* Break the list and create new group. */
+ if (use)
+ {
+ pre->next = NULL;
+ use->id = n_iv_uses (data);
+ use->related_cands = BITMAP_ALLOC (NULL);
+ data->iv_uses.safe_push (use);
+ }
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ dump_uses (dump_file, data);
+}
+
/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
is true, assume we are inside an address. If TOP_COMPREF is true, assume
we are at the top-level of the processed address. */
bool important, struct iv_use *use)
{
basic_block use_bb = gimple_bb (use->stmt);
- enum machine_mode mem_mode;
+ machine_mode mem_mode;
unsigned HOST_WIDE_INT cstepi;
/* If we insert the increment in any position other than the standard
add_candidate (struct ivopts_data *data,
tree base, tree step, bool important, struct iv_use *use)
{
+ gcc_assert (use == NULL || use->sub_id == 0);
+
if (ip_normal_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL);
if (ip_end_pos (data->current_loop)
return cost;
}
+/* Returns true if COST is infinite. */
+
+static bool
+infinite_cost_p (comp_cost cost)
+{
+ return cost.cost == INFTY;
+}
+
/* Adds costs COST1 and COST2. */
static comp_cost
add_costs (comp_cost cost1, comp_cost cost2)
{
+ if (infinite_cost_p (cost1) || infinite_cost_p (cost2))
+ return infinite_cost;
+
cost1.cost += cost2.cost;
cost1.complexity += cost2.complexity;
return cost1.cost - cost2.cost;
}
-/* Returns true if COST is infinite. */
-
-static bool
-infinite_cost_p (comp_cost cost)
-{
- return cost.cost == INFTY;
-}
-
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
on invariants DEPENDS_ON and that the value used in expressing it
is VALUE, and in case of iv elimination the comparison operator is COMP. */
return NULL;
}
-/* Returns estimate on cost of computing SEQ. */
-
-static unsigned
-seq_cost (rtx seq, bool speed)
-{
- unsigned cost = 0;
- rtx set;
-
- for (; seq; seq = NEXT_INSN (seq))
- {
- set = single_set (seq);
- if (set)
- cost += set_src_cost (SET_SRC (set), speed);
- else
- cost++;
- }
-
- return cost;
-}
-
/* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
static rtx
produce_memory_decl_rtl (tree obj, int *regno)
{
addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj));
- enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ machine_mode address_mode = targetm.addr_space.address_mode (as);
rtx x;
gcc_assert (obj);
static unsigned
computation_cost (tree expr, bool speed)
{
- rtx seq, rslt;
+ rtx_insn *seq;
+ rtx rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
/* Avoid using hard regs in ways which may be unsupported. */
bool
-multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode,
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, machine_mode mode,
addr_space_t as)
{
#define MAX_RATIO 128
valid_mult = valid_mult_list[data_index];
if (!valid_mult)
{
- enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ machine_mode address_mode = targetm.addr_space.address_mode (as);
rtx reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
rtx reg2 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
rtx addr, scaled;
static comp_cost
get_address_cost (bool symbol_present, bool var_present,
unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
- HOST_WIDE_INT cstep, enum machine_mode mem_mode,
+ HOST_WIDE_INT cstep, machine_mode mem_mode,
addr_space_t as, bool speed,
bool stmt_after_inc, bool *may_autoinc)
{
- enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ machine_mode address_mode = targetm.addr_space.address_mode (as);
static vec<address_cost_data> address_cost_data_list;
unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mem_mode;
address_cost_data data;
HOST_WIDE_INT rat, off = 0;
int old_cse_not_expected, width;
unsigned sym_p, var_p, off_p, rat_p, add_c;
- rtx seq, addr, base;
+ rtx_insn *seq;
+ rtx addr, base;
rtx reg0, reg1;
data = (address_cost_data) xcalloc (1, sizeof (*data));
XEXP (addr, 1) = gen_int_mode (off, address_mode);
if (memory_address_addr_space_p (mem_mode, addr, as))
break;
+ /* For some strict-alignment targets, the offset must be naturally
+ aligned. Try an aligned offset if mem_mode is not QImode. */
+ off = mem_mode != QImode
+ ? ((unsigned HOST_WIDE_INT) 1 << i)
+ - GET_MODE_SIZE (mem_mode)
+ : 0;
+ if (off > 0)
+ {
+ XEXP (addr, 1) = gen_int_mode (off, address_mode);
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ break;
+ }
}
if (i == -1)
off = 0;
the cost in COST. */
static bool
-get_shiftadd_cost (tree expr, enum machine_mode mode, comp_cost cost0,
+get_shiftadd_cost (tree expr, machine_mode mode, comp_cost cost0,
comp_cost cost1, tree mult, bool speed, comp_cost *cost)
{
comp_cost res;
tree multop = TREE_OPERAND (mult, 0);
int m = exact_log2 (int_cst_value (cst));
int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode));
- int sa_cost;
- bool equal_p = false;
+ int as_cost, sa_cost;
+ bool mult_in_op1;
if (!(m >= 0 && m < maxm))
return false;
- if (operand_equal_p (op1, mult, 0))
- equal_p = true;
+ mult_in_op1 = operand_equal_p (op1, mult, 0);
+ as_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
+
+ /* If the target has a cheap shift-and-add or shift-and-sub instruction,
+ use that in preference to a shift insn followed by an add insn. */
sa_cost = (TREE_CODE (expr) != MINUS_EXPR
? shiftadd_cost (speed, mode, m)
- : (equal_p
+ : (mult_in_op1
? shiftsub1_cost (speed, mode, m)
: shiftsub0_cost (speed, mode, m)));
- res = new_cost (sa_cost, 0);
- res = add_costs (res, equal_p ? cost0 : cost1);
+
+ res = new_cost (MIN (as_cost, sa_cost), 0);
+ res = add_costs (res, mult_in_op1 ? cost0 : cost1);
STRIP_NOPS (multop);
if (!is_gimple_val (multop))
static unsigned address_cost [2];
tree op0, op1;
comp_cost cost0, cost1, cost;
- enum machine_mode mode;
+ machine_mode mode;
if (!costs_initialized)
{
HOST_WIDE_INT bitsize;
HOST_WIDE_INT bitpos;
tree toffset;
- enum machine_mode mode;
+ machine_mode mode;
int unsignedp, volatilep;
core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
+ machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
aff_tree aff_e1, aff_e2;
tree type;
comp_cost cost;
widest_int rat;
bool speed = optimize_bb_for_speed_p (gimple_bb (at));
- enum machine_mode mem_mode = (address_p
+ machine_mode mem_mode = (address_p
? TYPE_MODE (TREE_TYPE (*use->op_p))
: VOIDmode);
if (cst_and_fits_in_hwi (cbase))
{
- offset = - ratio * int_cst_value (cbase);
+ offset = - ratio * (unsigned HOST_WIDE_INT) int_cst_value (cbase);
cost = difference_cost (data,
ubase, build_int_cst (utype, 0),
&symbol_present, &var_present, &offset,
cost.cost += add_cost (data->speed, TYPE_MODE (ctype));
}
- if (inv_expr_id)
+ /* Set of invariants depended on by sub use has already been computed
+ for the first use in the group. */
+ if (use->sub_id)
+ {
+ cost.cost = 0;
+ if (depends_on && *depends_on)
+ bitmap_clear (*depends_on);
+ }
+ else if (inv_expr_id)
{
*inv_expr_id =
get_loop_invariant_expr_id (data, ubase, cbase, ratio, address_p);
bitmap depends_on;
bool can_autoinc;
int inv_expr_id = -1;
+ struct iv_use *sub_use;
+ comp_cost sub_cost;
comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on,
&can_autoinc, &inv_expr_id);
else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
cost = infinite_cost;
}
+ for (sub_use = use->next;
+ sub_use && !infinite_cost_p (cost);
+ sub_use = sub_use->next)
+ {
+ sub_cost = get_computation_cost (data, sub_use, cand, true, &depends_on,
+ &can_autoinc, &inv_expr_id);
+ cost = add_costs (cost, sub_cost);
+ }
+
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE, ERROR_MARK,
inv_expr_id);
return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
-static tree
-strip_wrap_conserving_type_conversions (tree exp)
-{
- while (tree_ssa_useless_type_conversion (exp)
- && (nowrap_type_p (TREE_TYPE (exp))
- == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp, 0)))))
- exp = TREE_OPERAND (exp, 0);
- return exp;
-}
-
-/* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
- check for an exact match. */
-
-static bool
-expr_equal_p (tree e, tree what)
-{
- gimple stmt;
- enum tree_code code;
-
- e = strip_wrap_conserving_type_conversions (e);
- what = strip_wrap_conserving_type_conversions (what);
-
- code = TREE_CODE (what);
- if (TREE_TYPE (e) != TREE_TYPE (what))
- return false;
-
- if (operand_equal_p (e, what, 0))
- return true;
-
- if (TREE_CODE (e) != SSA_NAME)
- return false;
-
- stmt = SSA_NAME_DEF_STMT (e);
- if (gimple_code (stmt) != GIMPLE_ASSIGN
- || gimple_assign_rhs_code (stmt) != code)
- return false;
-
- switch (get_gimple_rhs_class (code))
- {
- case GIMPLE_BINARY_RHS:
- if (!expr_equal_p (gimple_assign_rhs2 (stmt), TREE_OPERAND (what, 1)))
- return false;
- /* Fallthru. */
-
- case GIMPLE_UNARY_RHS:
- case GIMPLE_SINGLE_RHS:
- return expr_equal_p (gimple_assign_rhs1 (stmt), TREE_OPERAND (what, 0));
- default:
- return false;
- }
-}
-
/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
we only detect the situation that BASE = SOMETHING + OFFSET, where the
calculation is performed in non-wrapping type.
TODO: More generally, we could test for the situation that
BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
- This would require knowing the sign of OFFSET.
-
- Also, we only look for the first addition in the computation of BASE.
- More complex analysis would be better, but introducing it just for
- this optimization seems like an overkill. */
+ This would require knowing the sign of OFFSET. */
static bool
-difference_cannot_overflow_p (tree base, tree offset)
+difference_cannot_overflow_p (struct ivopts_data *data, tree base, tree offset)
{
enum tree_code code;
tree e1, e2;
+ aff_tree aff_e1, aff_e2, aff_offset;
if (!nowrap_type_p (TREE_TYPE (base)))
return false;
e2 = TREE_OPERAND (base, 1);
}
- /* TODO: deeper inspection may be necessary to prove the equality. */
+ /* Use affine expansion as deeper inspection to prove the equality. */
+ tree_to_aff_combination_expand (e2, TREE_TYPE (e2),
+ &aff_e2, &data->name_expansion_cache);
+ tree_to_aff_combination_expand (offset, TREE_TYPE (offset),
+ &aff_offset, &data->name_expansion_cache);
+ aff_combination_scale (&aff_offset, -1);
switch (code)
{
case PLUS_EXPR:
- return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ if (aff_combination_zero_p (&aff_e2))
+ return true;
+
+ tree_to_aff_combination_expand (e1, TREE_TYPE (e1),
+ &aff_e1, &data->name_expansion_cache);
+ aff_combination_add (&aff_e1, &aff_offset);
+ return aff_combination_zero_p (&aff_e1);
+
case POINTER_PLUS_EXPR:
- return expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ return aff_combination_zero_p (&aff_e2);
default:
return false;
offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
cand->iv->step,
fold_convert (TREE_TYPE (cand->iv->step), a));
- if (!difference_cannot_overflow_p (cand->iv->base, offset))
+ if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
return false;
/* Determine the new comparison operator. */
determine_set_costs (struct ivopts_data *data)
{
unsigned j, n;
- gimple phi;
- gimple_stmt_iterator psi;
+ gphi *phi;
+ gphi_iterator psi;
tree op;
struct loop *loop = data->current_loop;
bitmap_iterator bi;
n = 0;
for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
- phi = gsi_stmt (psi);
+ phi = psi.phi ();
op = PHI_RESULT (phi);
if (virtual_operand_p (op))
}
/* Extend set IVS by expressing USE by some of the candidates in it
- if possible. All important candidates will be considered
- if IMPORTANT_CANDIDATES is true. */
+ if possible. Consider all important candidates if candidates in
+ set IVS don't give any result. */
static void
iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_use *use, bool important_candidates)
+ struct iv_use *use)
{
struct cost_pair *best_cp = NULL, *cp;
bitmap_iterator bi;
- bitmap cands;
unsigned i;
+ struct iv_cand *cand;
gcc_assert (ivs->upto >= use->id);
+ ivs->upto++;
+ ivs->bad_uses++;
- if (ivs->upto == use->id)
- {
- ivs->upto++;
- ivs->bad_uses++;
- }
-
- cands = (important_candidates ? data->important_candidates : ivs->cands);
- EXECUTE_IF_SET_IN_BITMAP (cands, 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
{
- struct iv_cand *cand = iv_cand (data, i);
-
+ cand = iv_cand (data, i);
cp = get_use_iv_cost (data, use, cand);
-
if (cheaper_cost_pair (cp, best_cp))
best_cp = cp;
}
+
+ if (best_cp == NULL)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
+ {
+ cand = iv_cand (data, i);
+ cp = get_use_iv_cost (data, use, cand);
+ if (cheaper_cost_pair (cp, best_cp))
+ best_cp = cp;
+ }
+ }
iv_ca_set_cp (data, ivs, use, best_cp);
}
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)
{
act->next_change = prev;
prev = act;
- tmp = act->old_cp;
- act->old_cp = act->new_cp;
- act->new_cp = tmp;
+ std::swap (act->old_cp, act->new_cp);
}
return prev;
return best_cost;
}
+/* Check if CAND_IDX is a candidate other than OLD_CAND and has
+ cheaper local cost for USE than BEST_CP. Return pointer to
+ the corresponding cost_pair, otherwise just return BEST_CP. */
+
+static struct cost_pair*
+cheaper_cost_with_cand (struct ivopts_data *data, struct iv_use *use,
+ unsigned int cand_idx, struct iv_cand *old_cand,
+ struct cost_pair *best_cp)
+{
+ struct iv_cand *cand;
+ struct cost_pair *cp;
+
+ gcc_assert (old_cand != NULL && best_cp != NULL);
+ if (cand_idx == old_cand->id)
+ return best_cp;
+
+ cand = iv_cand (data, cand_idx);
+ cp = get_use_iv_cost (data, use, cand);
+ if (cp != NULL && cheaper_cost_pair (cp, best_cp))
+ return cp;
+
+ return best_cp;
+}
+
+/* Try breaking local optimal fixed-point for IVS by replacing candidates
+ which are used by more than one iv uses. For each of those candidates,
+ this function tries to represent iv uses under that candidate using
+ other ones with lower local cost, then tries to prune the new set.
+ If the new set has lower cost, It returns the new cost after recording
+ candidate replacement in list DELTA. */
+
+static comp_cost
+iv_ca_replace (struct ivopts_data *data, struct iv_ca *ivs,
+ struct iv_ca_delta **delta)
+{
+ bitmap_iterator bi, bj;
+ unsigned int i, j, k;
+ struct iv_use *use;
+ struct iv_cand *cand;
+ comp_cost orig_cost, acost;
+ struct iv_ca_delta *act_delta, *tmp_delta;
+ struct cost_pair *old_cp, *best_cp = NULL;
+
+ *delta = NULL;
+ orig_cost = iv_ca_cost (ivs);
+
+ EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+ {
+ if (ivs->n_cand_uses[i] == 1
+ || ivs->n_cand_uses[i] > ALWAYS_PRUNE_CAND_SET_BOUND)
+ continue;
+
+ cand = iv_cand (data, i);
+
+ act_delta = NULL;
+ /* Represent uses under current candidate using other ones with
+ lower local cost. */
+ for (j = 0; j < ivs->upto; j++)
+ {
+ use = iv_use (data, j);
+ old_cp = iv_ca_cand_for_use (ivs, use);
+
+ if (old_cp->cand != cand)
+ continue;
+
+ best_cp = old_cp;
+ if (data->consider_all_candidates)
+ for (k = 0; k < n_iv_cands (data); k++)
+ best_cp = cheaper_cost_with_cand (data, use, k,
+ old_cp->cand, best_cp);
+ else
+ EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, k, bj)
+ best_cp = cheaper_cost_with_cand (data, use, k,
+ old_cp->cand, best_cp);
+
+ if (best_cp == old_cp)
+ continue;
+
+ act_delta = iv_ca_delta_add (use, old_cp, best_cp, act_delta);
+ }
+ /* No need for further prune. */
+ if (!act_delta)
+ continue;
+
+ /* Prune the new candidate set. */
+ iv_ca_delta_commit (data, ivs, act_delta, true);
+ acost = iv_ca_prune (data, ivs, NULL, &tmp_delta);
+ iv_ca_delta_commit (data, ivs, act_delta, false);
+ act_delta = iv_ca_delta_join (act_delta, tmp_delta);
+
+ if (compare_costs (acost, orig_cost) < 0)
+ {
+ *delta = act_delta;
+ return acost;
+ }
+ else
+ iv_ca_delta_free (&act_delta);
+ }
+
+ return orig_cost;
+}
+
/* Tries to extend the sets IVS in the best possible way in order
to express the USE. If ORIGINALP is true, prefer candidates from
the original set of IVs, otherwise favor important candidates not
struct iv_ca_delta *best_delta = NULL, *act_delta;
struct cost_pair *cp;
- iv_ca_add_use (data, ivs, use, false);
+ iv_ca_add_use (data, ivs, use);
best_cost = iv_ca_cost (ivs);
-
cp = iv_ca_cand_for_use (ivs, use);
- if (!cp)
- {
- ivs->upto--;
- ivs->bad_uses--;
- iv_ca_add_use (data, ivs, use, true);
- best_cost = iv_ca_cost (ivs);
- cp = iv_ca_cand_for_use (ivs, use);
- }
if (cp)
{
best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
return ivs;
}
-/* Tries to improve set of induction variables IVS. */
+/* Tries to improve set of induction variables IVS. TRY_REPLACE_P
+ points to a bool variable, this function tries to break local
+ optimal fixed-point by replacing candidates in IVS if it's true. */
static bool
-try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
+try_improve_iv_set (struct ivopts_data *data,
+ struct iv_ca *ivs, bool *try_replace_p)
{
unsigned i, n_ivs;
comp_cost acost, best_cost = iv_ca_cost (ivs);
/* Try removing the candidates from the set instead. */
best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
- /* Nothing more we can do. */
+ if (!best_delta && *try_replace_p)
+ {
+ *try_replace_p = false;
+ /* So far candidate selecting algorithm tends to choose fewer IVs
+ so that it can handle cases in which loops have many variables
+ but the best choice is often to use only one general biv. One
+ weakness is it can't handle opposite cases, in which different
+ candidates should be chosen with respect to each use. To solve
+ the problem, we replace candidates in a manner described by the
+ comments of iv_ca_replace, thus give general algorithm a chance
+ to break local optimal fixed-point in these cases. */
+ best_cost = iv_ca_replace (data, ivs, &best_delta);
+ }
+
if (!best_delta)
return false;
}
find_optimal_iv_set_1 (struct ivopts_data *data, bool originalp)
{
struct iv_ca *set;
+ bool try_replace_p = true;
/* Get the initial solution. */
set = get_initial_solution (data, originalp);
iv_ca_dump (data, dump_file, set);
}
- while (try_improve_iv_set (data, set))
+ while (try_improve_iv_set (data, set, &try_replace_p))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "\nSelected IV set: \n");
+ fprintf (dump_file, "Selected IV set for loop %d",
+ data->current_loop->num);
+ if (data->loop_loc != UNKNOWN_LOCATION)
+ fprintf (dump_file, " at %s:%d", LOCATION_FILE (data->loop_loc),
+ LOCATION_LINE (data->loop_loc));
+ fprintf (dump_file, ", %lu IVs:\n", bitmap_count_bits (set->cands));
EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
{
cand = iv_cand (data, i);
{
tree comp;
tree op, tgt;
- gimple ass;
+ gassign *ass;
gimple_stmt_iterator bsi;
/* An important special case -- if we are asked to express value of
/* Rewrites USE (address that is an iv) using candidate CAND. */
static void
-rewrite_use_address (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+rewrite_use_address_1 (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand)
{
aff_tree aff;
gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
*use->op_p = ref;
}
+/* Rewrites USE (address that is an iv) using candidate CAND. If it's the
+ first use of a group, rewrites sub uses in the group too. */
+
+static void
+rewrite_use_address (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand)
+{
+ struct iv_use *next;
+
+ gcc_assert (use->sub_id == 0);
+ rewrite_use_address_1 (data, use, cand);
+ update_stmt (use->stmt);
+
+ for (next = use->next; next != NULL; next = next->next)
+ {
+ rewrite_use_address_1 (data, next, cand);
+ update_stmt (next->stmt);
+ }
+
+ return;
+}
+
/* Rewrites USE (the condition such that one of the arguments is an iv) using
candidate CAND. */
loop_preheader_edge (data->current_loop),
stmts);
- gimple_cond_set_lhs (use->stmt, var);
- gimple_cond_set_code (use->stmt, compare);
- gimple_cond_set_rhs (use->stmt, op);
+ gcond *cond_stmt = as_a <gcond *> (use->stmt);
+ gimple_cond_set_lhs (cond_stmt, var);
+ gimple_cond_set_code (cond_stmt, compare);
+ gimple_cond_set_rhs (cond_stmt, op);
return;
}
DECL_MODE (vexpr) = DECL_MODE (SSA_NAME_VAR (def));
else
DECL_MODE (vexpr) = TYPE_MODE (TREE_TYPE (vexpr));
- gimple def_temp = gimple_build_debug_bind (vexpr, comp, NULL);
+ gdebug *def_temp
+ = gimple_build_debug_bind (vexpr, comp, NULL);
gimple_stmt_iterator gsi;
if (gimple_code (SSA_NAME_DEF_STMT (def)) == GIMPLE_PHI)
}
/* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
- for pointer_map_traverse. */
+ for hash_map::traverse. */
-static bool
-free_tree_niter_desc (const void *key ATTRIBUTE_UNUSED, void **value,
- void *data ATTRIBUTE_UNUSED)
+bool
+free_tree_niter_desc (edge const &, tree_niter_desc *const &value, void *)
{
- struct tree_niter_desc *const niter = (struct tree_niter_desc *) *value;
-
- free (niter);
+ free (value);
return true;
}
if (data->niters)
{
- pointer_map_traverse (data->niters, free_tree_niter_desc, NULL);
- pointer_map_destroy (data->niters);
+ data->niters->traverse<void *, free_tree_niter_desc> (NULL);
+ delete data->niters;
data->niters = NULL;
}
for (i = 0; i < n_iv_uses (data); i++)
{
struct iv_use *use = iv_use (data, i);
+ struct iv_use *pre = use, *sub = use->next;
+
+ while (sub)
+ {
+ gcc_assert (sub->related_cands == NULL);
+ gcc_assert (sub->n_map_members == 0 && sub->cost_map == NULL);
+
+ free (sub->iv);
+ pre = sub;
+ sub = sub->next;
+ free (pre);
+ }
free (use->iv);
BITMAP_FREE (use->related_cands);
data->iv_candidates.release ();
delete data->inv_expr_tab;
data->inv_expr_tab = NULL;
+ free_affine_expand_cache (&data->name_expansion_cache);
}
/* Returns true if the loop body BODY includes any function calls. */
gcc_assert (!data->niters);
data->current_loop = loop;
+ data->loop_loc = find_loop_location (loop);
data->speed = optimize_loop_for_speed_p (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "Processing loop %d\n", loop->num);
+ fprintf (dump_file, "Processing loop %d", loop->num);
+ if (data->loop_loc != UNKNOWN_LOCATION)
+ fprintf (dump_file, " at %s:%d", LOCATION_FILE (data->loop_loc),
+ LOCATION_LINE (data->loop_loc));
+ fprintf (dump_file, "\n");
if (exit)
{
/* Finds interesting uses (item 1). */
find_interesting_uses (data);
+ group_address_uses (data);
if (n_iv_uses (data) > MAX_CONSIDERED_USES)
goto finish;
projects / gcc.git / blobdiff