/* 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 "vec.h"
-#include "hashtab.h"
-#include "hash-set.h"
-#include "machmode.h"
#include "hard-reg-set.h"
-#include "input.h"
#include "function.h"
#include "dominance.h"
#include "cfg.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
-#include "hash-map.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 "gimplify-me.h"
#include "gimple-ssa.h"
-#include "plugin-api.h"
-#include "ipa-ref.h"
#include "cgraph.h"
#include "tree-cfg.h"
#include "tree-phinodes.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. */
hash_map<edge, tree_niter_desc *> *niters;
/* 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. */
}
/* 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 (gphi *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. */
find_bivs (struct ivopts_data *data)
{
gphi *phi;
- tree step, type, base;
+ affine_iv iv;
+ tree step, type, base, stop;
bool found = false;
struct loop *loop = data->current_loop;
gphi_iterator psi;
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 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)
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;
}
+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:
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. */
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. */
XEXP (addr, 1) = gen_int_mode (off, address_mode);
if (memory_address_addr_space_p (mem_mode, addr, as))
break;
- /* For some TARGET, like ARM THUMB1, the offset should be nature
- aligned. Try an aligned offset if address_mode is not QImode. */
- off = (address_mode == QImode)
- ? 0
- : ((unsigned HOST_WIDE_INT) 1 << i)
- - GET_MODE_SIZE (address_mode);
+ /* 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);
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))
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);
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
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);
/* 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. */
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);
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;