/* Induction variable optimizations.
- Copyright (C) 2003-2016 Free Software Foundation, Inc.
+ Copyright (C) 2003-2021 Free Software Foundation, Inc.
This file is part of GCC.
All of this is done loop by loop. Doing it globally is theoretically
possible, it might give a better performance and it might enable us
to decide costs more precisely, but getting all the interactions right
- would be complicated. */
+ would be complicated.
+
+ For the targets supporting low-overhead loops, IVOPTs has to take care of
+ the loops which will probably be transformed in RTL doloop optimization,
+ to try to make selected IV candidate set optimal. The process of doloop
+ support includes:
+
+ 1) Analyze the current loop will be transformed to doloop or not, find and
+ mark its compare type IV use as doloop use (iv_group field doloop_p), and
+ set flag doloop_use_p of ivopts_data to notify subsequent processings on
+ doloop. See analyze_and_mark_doloop_use and its callees for the details.
+ The target hook predict_doloop_p can be used for target specific checks.
+
+ 2) Add one doloop dedicated IV cand {(may_be_zero ? 1 : (niter + 1)), +, -1},
+ set flag doloop_p of iv_cand, step cost is set as zero and no extra cost
+ like biv. For cost determination between doloop IV cand and IV use, the
+ target hooks doloop_cost_for_generic and doloop_cost_for_address are
+ provided to add on extra costs for generic type and address type IV use.
+ Zero cost is assigned to the pair between doloop IV cand and doloop IV
+ use, and bound zero is set for IV elimination.
+
+ 3) With the cost setting in step 2), the current cost model based IV
+ selection algorithm will process as usual, pick up doloop dedicated IV if
+ profitable. */
#include "config.h"
#include "system.h"
#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
-#include "params.h"
#include "tree-affine.h"
#include "tree-ssa-propagate.h"
#include "tree-ssa-address.h"
#include "builtins.h"
#include "tree-vectorizer.h"
+#include "dbgcnt.h"
+
+/* For lang_hooks.types.type_for_mode. */
+#include "langhooks.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. */
/* The infinite cost. */
-#define INFTY 10000000
+#define INFTY 1000000000
/* Returns the expected number of loop iterations for LOOP.
The average trip count is computed from profile data if it
exists. */
static inline HOST_WIDE_INT
-avg_loop_niter (struct loop *loop)
+avg_loop_niter (class loop *loop)
{
HOST_WIDE_INT niter = estimated_stmt_executions_int (loop);
if (niter == -1)
{
niter = likely_max_stmt_executions_int (loop);
- if (niter == -1 || niter > PARAM_VALUE (PARAM_AVG_LOOP_NITER))
- return PARAM_VALUE (PARAM_AVG_LOOP_NITER);
+ if (niter == -1 || niter > param_avg_loop_niter)
+ return param_avg_loop_niter;
}
return niter;
enum use_type
{
USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
- USE_ADDRESS, /* Use in an address. */
+ USE_REF_ADDRESS, /* Use is an address for an explicit memory
+ reference. */
+ USE_PTR_ADDRESS, /* Use is a pointer argument to a function in
+ cases where the expansion of the function
+ will turn the argument into a normal address. */
USE_COMPARE /* Use is a compare. */
};
/* Cost of a computation. */
-struct comp_cost
+class comp_cost
{
+public:
comp_cost (): cost (0), complexity (0), scratch (0)
{}
- comp_cost (int cost, unsigned complexity, int scratch = 0)
+ comp_cost (int64_t cost, unsigned complexity, int64_t scratch = 0)
: cost (cost), complexity (complexity), scratch (scratch)
{}
/* Returns true if COST1 is smaller or equal than COST2. */
friend bool operator<= (comp_cost cost1, comp_cost cost2);
- int cost; /* The runtime cost. */
+ int64_t cost; /* The runtime cost. */
unsigned complexity; /* The estimate of the complexity of the code for
the computation (in no concrete units --
complexity field should be larger for more
complex expressions and addressing modes). */
- int scratch; /* Scratch used during cost computation. */
+ int64_t scratch; /* Scratch used during cost computation. */
};
static const comp_cost no_cost;
-static const comp_cost infinite_cost (INFTY, INFTY, INFTY);
+static const comp_cost infinite_cost (INFTY, 0, INFTY);
bool
comp_cost::infinite_cost_p ()
if (cost1.infinite_cost_p () || cost2.infinite_cost_p ())
return infinite_cost;
+ gcc_assert (cost1.cost + cost2.cost < infinite_cost.cost);
cost1.cost += cost2.cost;
cost1.complexity += cost2.complexity;
return infinite_cost;
gcc_assert (!cost2.infinite_cost_p ());
+ gcc_assert (cost1.cost - cost2.cost < infinite_cost.cost);
cost1.cost -= cost2.cost;
cost1.complexity -= cost2.complexity;
comp_cost
comp_cost::operator+= (HOST_WIDE_INT c)
{
+ if (c >= INFTY)
+ this->cost = INFTY;
+
if (infinite_cost_p ())
return *this;
+ gcc_assert (this->cost + c < infinite_cost.cost);
this->cost += c;
return *this;
if (infinite_cost_p ())
return *this;
+ gcc_assert (this->cost - c < infinite_cost.cost);
this->cost -= c;
return *this;
comp_cost
comp_cost::operator/= (HOST_WIDE_INT c)
{
+ gcc_assert (c != 0);
if (infinite_cost_p ())
return *this;
if (infinite_cost_p ())
return *this;
+ gcc_assert (this->cost * c < infinite_cost.cost);
this->cost *= c;
return *this;
struct iv_inv_expr_ent;
/* The candidate - cost pair. */
-struct cost_pair
+class cost_pair
{
+public:
struct iv_cand *cand; /* The candidate. */
comp_cost cost; /* The cost. */
- bitmap depends_on; /* The list of invariants that have to be
- preserved. */
+ enum tree_code comp; /* For iv elimination, the comparison. */
+ bitmap inv_vars; /* The list of invariant ssa_vars that have to be
+ preserved when representing iv_use with iv_cand. */
+ bitmap inv_exprs; /* The list of newly created invariant expressions
+ when representing iv_use with iv_cand. */
tree value; /* For final value elimination, the expression for
the final value of the iv. For iv elimination,
the new bound to compare with. */
- enum tree_code comp; /* For iv elimination, the comparison. */
- iv_inv_expr_ent *inv_expr; /* Loop invariant expression. */
};
/* Use. */
unsigned id; /* The id of the use. */
unsigned group_id; /* The group id the use belongs to. */
enum use_type type; /* Type of the use. */
+ tree mem_type; /* The memory type to use when testing whether an
+ address is legitimate, and what the address's
+ cost is. */
struct iv *iv; /* The induction variable it is based on. */
gimple *stmt; /* Statement in that it occurs. */
tree *op_p; /* The place where it occurs. */
tree addr_base; /* Base address with const offset stripped. */
- unsigned HOST_WIDE_INT addr_offset;
+ poly_uint64_pod addr_offset;
/* Const offset stripped from base address. */
};
/* Number of IV candidates in the cost_map. */
unsigned n_map_members;
/* The costs wrto the iv candidates. */
- struct cost_pair *cost_map;
+ class cost_pair *cost_map;
/* The selected candidate for the group. */
struct iv_cand *selected;
+ /* To indicate this is a doloop use group. */
+ bool doloop_p;
/* Uses in the group. */
vec<struct iv_use *> vuses;
};
unsigned cost_step; /* Cost of the candidate's increment operation. */
struct iv_use *ainc_use; /* For IP_{BEFORE,AFTER}_USE candidates, the place
where it is incremented. */
- bitmap depends_on; /* The list of invariants that are used in step of the
- biv. */
+ bitmap inv_vars; /* The list of invariant ssa_vars used in step of the
+ iv_cand. */
+ bitmap inv_exprs; /* If step is more complicated than a single ssa_var,
+ hanlde it as a new invariant expression which will
+ be hoisted out of loop. */
struct iv *orig_iv; /* The original iv if this cand is added from biv with
smaller type. */
+ bool doloop_p; /* Whether this is a doloop candidate. */
};
/* Hashtable entry for common candidate derived from iv uses. */
-struct iv_common_cand
+class iv_common_cand
{
+public:
tree base;
tree step;
/* IV uses from which this common candidate is derived. */
static inline bool equal (const iv_inv_expr_ent *, const iv_inv_expr_ent *);
};
+/* Return true if uses of type TYPE represent some form of address. */
+
+inline bool
+address_p (use_type type)
+{
+ return type == USE_REF_ADDRESS || type == USE_PTR_ADDRESS;
+}
+
/* Hash function for loop invariant expressions. */
inline hashval_t
struct ivopts_data
{
/* The currently optimized loop. */
- struct loop *current_loop;
- source_location loop_loc;
+ class loop *current_loop;
+ location_t loop_loc;
/* Numbers of iterations for all exits of the current loop. */
hash_map<edge, tree_niter_desc *> *niters;
by ivopt. */
hash_table<iv_inv_expr_hasher> *inv_expr_tab;
- /* Loop invariant expression id. */
- int max_inv_expr_id;
-
/* The bitmap of indices in version_info whose value was changed. */
bitmap relevant;
/* The common candidates. */
vec<iv_common_cand *> iv_common_cands;
- /* The maximum invariant id. */
- unsigned max_inv_id;
+ /* Hash map recording base object information of tree exp. */
+ hash_map<tree, tree> *base_object_map;
+
+ /* The maximum invariant variable id. */
+ unsigned max_inv_var_id;
+
+ /* The maximum invariant expression id. */
+ unsigned max_inv_expr_id;
/* Number of no_overflow BIVs which are not used in memory address. */
unsigned bivs_not_used_in_addr;
/* Whether the loop body can only be exited via single exit. */
bool loop_single_exit_p;
+
+ /* Whether the loop has doloop comparison use. */
+ bool doloop_use_p;
};
/* An assignment of iv candidates to uses. */
-struct iv_ca
+class iv_ca
{
+public:
/* The number of uses covered by the assignment. */
unsigned upto;
unsigned bad_groups;
/* Candidate assigned to a use, together with the related costs. */
- struct cost_pair **cand_for_group;
+ class cost_pair **cand_for_group;
/* Number of times each candidate is used. */
unsigned *n_cand_uses;
/* The number of candidates in the set. */
unsigned n_cands;
- /* Total number of registers needed. */
- unsigned n_regs;
+ /* The number of invariants needed, including both invariant variants and
+ invariant expressions. */
+ unsigned n_invs;
/* Total cost of expressing uses. */
comp_cost cand_use_cost;
/* Total cost of candidates. */
- unsigned cand_cost;
+ int64_t cand_cost;
- /* Number of times each invariant is used. */
- unsigned *n_invariant_uses;
+ /* Number of times each invariant variable is used. */
+ unsigned *n_inv_var_uses;
- /* Hash set with used invariant expression. */
- hash_map <iv_inv_expr_ent *, unsigned> *used_inv_exprs;
+ /* Number of times each invariant expression is used. */
+ unsigned *n_inv_expr_uses;
/* Total cost of the assignment. */
comp_cost cost;
struct iv_group *group;
/* An old assignment (for rollback purposes). */
- struct cost_pair *old_cp;
+ class cost_pair *old_cp;
/* A new assignment. */
- struct cost_pair *new_cp;
+ class cost_pair *new_cp;
/* Next change in the list. */
struct iv_ca_delta *next;
/* Bound on number of candidates below that all candidates are considered. */
#define CONSIDER_ALL_CANDIDATES_BOUND \
- ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
+ ((unsigned) param_iv_consider_all_candidates_bound)
/* If there are more iv occurrences, we just give up (it is quite unlikely that
optimizing such a loop would help, and it would take ages). */
#define MAX_CONSIDERED_GROUPS \
- ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
+ ((unsigned) 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))
+ ((unsigned) param_iv_always_prune_cand_set_bound)
/* The list of trees for that the decl_rtl field must be reset is stored
here. */
/* The single loop exit if it dominates the latch, NULL otherwise. */
edge
-single_dom_exit (struct loop *loop)
+single_dom_exit (class loop *loop)
{
edge exit = single_exit (loop);
{
fprintf (file, " Use %d.%d:\n", use->group_id, use->id);
fprintf (file, " At stmt:\t");
- print_gimple_stmt (file, use->stmt, 0, 0);
+ print_gimple_stmt (file, use->stmt, 0);
fprintf (file, " At pos:\t");
if (use->op_p)
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "Group %d:\n", group->id);
if (group->type == USE_NONLINEAR_EXPR)
fprintf (file, " Type:\tGENERIC\n");
- else if (group->type == USE_ADDRESS)
- fprintf (file, " Type:\tADDRESS\n");
+ else if (group->type == USE_REF_ADDRESS)
+ fprintf (file, " Type:\tREFERENCE ADDRESS\n");
+ else if (group->type == USE_PTR_ADDRESS)
+ fprintf (file, " Type:\tPOINTER ARGUMENT ADDRESS\n");
else
{
gcc_assert (group->type == USE_COMPARE);
struct iv *iv = cand->iv;
fprintf (file, "Candidate %d:\n", cand->id);
- if (cand->depends_on)
+ if (cand->inv_vars)
+ {
+ fprintf (file, " Depend on inv.vars: ");
+ dump_bitmap (file, cand->inv_vars);
+ }
+ if (cand->inv_exprs)
{
- fprintf (file, " Depend on: ");
- dump_bitmap (file, cand->depends_on);
+ fprintf (file, " Depend on inv.exprs: ");
+ dump_bitmap (file, cand->inv_exprs);
}
if (cand->var_before)
emitted in LOOP. */
static bool
-stmt_after_ip_normal_pos (struct loop *loop, gimple *stmt)
+stmt_after_ip_normal_pos (class loop *loop, gimple *stmt)
{
basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);
CAND is incremented in LOOP. */
static bool
-stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple *stmt)
+stmt_after_increment (class loop *loop, struct iv_cand *cand, gimple *stmt)
{
switch (cand->pos)
{
}
}
-/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
+/* walk_tree callback for contains_abnormal_ssa_name_p. */
-static bool
-abnormal_ssa_name_p (tree exp)
+static tree
+contains_abnormal_ssa_name_p_1 (tree *tp, int *walk_subtrees, void *)
{
- if (!exp)
- return false;
-
- if (TREE_CODE (exp) != SSA_NAME)
- return false;
+ if (TREE_CODE (*tp) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*tp))
+ return *tp;
- 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, tree *index,
- void *data ATTRIBUTE_UNUSED)
-{
- if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
- {
- if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
- return false;
- if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
- return false;
- }
+ if (!EXPR_P (*tp))
+ *walk_subtrees = 0;
- return !abnormal_ssa_name_p (*index);
+ return NULL_TREE;
}
/* Returns true if EXPR contains a ssa name that occurs in an
bool
contains_abnormal_ssa_name_p (tree expr)
{
- enum tree_code code;
- enum tree_code_class codeclass;
-
- if (!expr)
- return false;
-
- code = TREE_CODE (expr);
- codeclass = TREE_CODE_CLASS (code);
-
- if (code == SSA_NAME)
- return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
-
- if (code == INTEGER_CST
- || is_gimple_min_invariant (expr))
- return false;
-
- if (code == ADDR_EXPR)
- return !for_each_index (&TREE_OPERAND (expr, 0),
- idx_contains_abnormal_ssa_name_p,
- NULL);
-
- if (code == COND_EXPR)
- return contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0))
- || contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1))
- || contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 2));
-
- switch (codeclass)
- {
- case tcc_binary:
- case tcc_comparison:
- if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
- return true;
-
- /* Fallthru. */
- case tcc_unary:
- if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
- return true;
-
- break;
-
- default:
- gcc_unreachable ();
- }
-
- return false;
+ return walk_tree_without_duplicates
+ (&expr, contains_abnormal_ssa_name_p_1, NULL) != NULL_TREE;
}
/* Returns the structure describing number of iterations determined from
EXIT of DATA->current_loop, or NULL if something goes wrong. */
-static struct tree_niter_desc *
+static class tree_niter_desc *
niter_for_exit (struct ivopts_data *data, edge exit)
{
- struct tree_niter_desc *desc;
+ class tree_niter_desc *desc;
tree_niter_desc **slot;
if (!data->niters)
/* Try to determine number of iterations. We cannot safely work with ssa
names that appear in phi nodes on abnormal edges, so that we do not
create overlapping life ranges for them (PR 27283). */
- desc = XNEW (struct tree_niter_desc);
+ desc = XNEW (class tree_niter_desc);
if (!number_of_iterations_exit (data->current_loop,
exit, desc, true)
|| contains_abnormal_ssa_name_p (desc->niter))
single dominating exit of DATA->current_loop, or NULL if something
goes wrong. */
-static struct tree_niter_desc *
+static class tree_niter_desc *
niter_for_single_dom_exit (struct ivopts_data *data)
{
edge exit = single_dom_exit (data->current_loop);
data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
data->relevant = BITMAP_ALLOC (NULL);
data->important_candidates = BITMAP_ALLOC (NULL);
- data->max_inv_id = 0;
+ data->max_inv_var_id = 0;
+ data->max_inv_expr_id = 0;
data->niters = NULL;
data->vgroups.create (20);
data->vcands.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
- data->max_inv_expr_id = 0;
data->name_expansion_cache = NULL;
+ data->base_object_map = NULL;
data->iv_common_cand_tab = new hash_table<iv_common_cand_hasher> (10);
data->iv_common_cands.create (20);
decl_rtl_to_reset.create (20);
gcc_obstack_init (&data->iv_obstack);
}
-/* 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. */
+/* walk_tree callback for determine_base_object. */
static tree
-determine_base_object (tree expr)
+determine_base_object_1 (tree *tp, int *walk_subtrees, void *wdata)
{
- enum tree_code code = TREE_CODE (expr);
- tree base, obj;
-
- /* If this is a pointer casted to any type, we need to determine
- the base object for the pointer; so handle conversions before
- throwing away non-pointer expressions. */
- if (CONVERT_EXPR_P (expr))
- return determine_base_object (TREE_OPERAND (expr, 0));
-
- if (!POINTER_TYPE_P (TREE_TYPE (expr)))
- return NULL_TREE;
-
- switch (code)
+ tree_code code = TREE_CODE (*tp);
+ tree obj = NULL_TREE;
+ if (code == ADDR_EXPR)
{
- case INTEGER_CST:
- return NULL_TREE;
-
- case ADDR_EXPR:
- obj = TREE_OPERAND (expr, 0);
- base = get_base_address (obj);
-
+ tree base = get_base_address (TREE_OPERAND (*tp, 0));
if (!base)
- return expr;
-
- if (TREE_CODE (base) == MEM_REF)
- return determine_base_object (TREE_OPERAND (base, 0));
+ obj = *tp;
+ else if (TREE_CODE (base) != MEM_REF)
+ obj = fold_convert (ptr_type_node, build_fold_addr_expr (base));
+ }
+ else if (code == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*tp)))
+ obj = fold_convert (ptr_type_node, *tp);
- return fold_convert (ptr_type_node,
- build_fold_addr_expr (base));
+ if (!obj)
+ {
+ if (!EXPR_P (*tp))
+ *walk_subtrees = 0;
- case POINTER_PLUS_EXPR:
- return determine_base_object (TREE_OPERAND (expr, 0));
+ return NULL_TREE;
+ }
+ /* Record special node for multiple base objects and stop. */
+ if (*static_cast<tree *> (wdata))
+ {
+ *static_cast<tree *> (wdata) = integer_zero_node;
+ return integer_zero_node;
+ }
+ /* Record the base object and continue looking. */
+ *static_cast<tree *> (wdata) = obj;
+ return NULL_TREE;
+}
- case PLUS_EXPR:
- case MINUS_EXPR:
- /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
- gcc_unreachable ();
+/* Returns a memory object to that EXPR points with caching. Return NULL if we
+ are able to determine that it does not point to any such object; specially
+ return integer_zero_node if EXPR contains multiple base objects. */
- default:
- return fold_convert (ptr_type_node, expr);
+static tree
+determine_base_object (struct ivopts_data *data, tree expr)
+{
+ tree *slot, obj = NULL_TREE;
+ if (data->base_object_map)
+ {
+ if ((slot = data->base_object_map->get(expr)) != NULL)
+ return *slot;
}
+ else
+ data->base_object_map = new hash_map<tree, tree>;
+
+ (void) walk_tree_without_duplicates (&expr, determine_base_object_1, &obj);
+ data->base_object_map->put (expr, obj);
+ return obj;
}
/* Return true if address expression with non-DECL_P operand appears
|| contain_complex_addr_expr (expr))
{
aff_tree comb;
- tree_to_aff_combination (expr, TREE_TYPE (base), &comb);
+ tree_to_aff_combination (expr, TREE_TYPE (expr), &comb);
base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb));
}
iv->base = base;
- iv->base_object = determine_base_object (base);
+ iv->base_object = determine_base_object (data, base);
iv->step = step;
iv->biv_p = false;
iv->nonlin_use = NULL;
if (!bb
|| !flow_bb_inside_loop_p (data->current_loop, bb))
- set_iv (data, var, var, build_int_cst (type, 0), true);
+ {
+ if (POINTER_TYPE_P (type))
+ type = sizetype;
+ set_iv (data, var, var, build_int_cst (type, 0), true);
+ }
}
return name_info (data, var)->iv;
affine_iv iv;
tree step, type, base, stop;
bool found = false;
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
gphi_iterator psi;
for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
gimple *def;
tree var;
struct iv *iv, *incr_iv;
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
basic_block incr_bb;
gphi_iterator psi;
find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
{
tree lhs, stop;
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
iv->base = NULL_TREE;
iv->step = NULL_TREE;
return false;
/* If STMT could throw, then do not consider STMT as defining a GIV.
- While this will suppress optimizations, we can not safely delete this
+ While this will suppress optimizations, we cannot safely delete this
GIV and associated statements, even if it appears it is not used. */
- if (stmt_could_throw_p (stmt))
+ if (stmt_could_throw_p (cfun, stmt))
return false;
return true;
static void
find_givs (struct ivopts_data *data)
{
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
basic_block *body = get_loop_body_in_dom_order (loop);
unsigned i;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- struct tree_niter_desc *niter = niter_for_single_dom_exit (data);
+ class tree_niter_desc *niter = niter_for_single_dom_exit (data);
if (niter)
{
/* Records a use of TYPE at *USE_P in STMT whose value is IV in GROUP.
For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
- is the const offset stripped from IV base; for other types use, both
- are zero by default. */
+ is the const offset stripped from IV base and MEM_TYPE is the type
+ of the memory being addressed. For uses of other types, ADDR_BASE
+ and ADDR_OFFSET are zero by default and MEM_TYPE is NULL_TREE. */
static struct iv_use *
record_use (struct iv_group *group, tree *use_p, struct iv *iv,
- gimple *stmt, enum use_type type, tree addr_base,
- unsigned HOST_WIDE_INT addr_offset)
+ gimple *stmt, enum use_type type, tree mem_type,
+ tree addr_base, poly_uint64 addr_offset)
{
struct iv_use *use = XCNEW (struct iv_use);
use->id = group->vuses.length ();
use->group_id = group->id;
use->type = type;
+ use->mem_type = mem_type;
use->iv = iv;
use->stmt = stmt;
use->op_p = use_p;
info->name = op;
info->has_nonlin_use |= nonlinear_use;
if (!info->inv_id)
- info->inv_id = ++data->max_inv_id;
+ info->inv_id = ++data->max_inv_var_id;
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
}
-static tree
-strip_offset (tree expr, unsigned HOST_WIDE_INT *offset);
-
/* Record a group of TYPE. */
static struct iv_group *
group->type = type;
group->related_cands = BITMAP_ALLOC (NULL);
group->vuses.create (1);
+ group->doloop_p = false;
data->vgroups.safe_push (group);
return group;
}
/* Record a use of TYPE at *USE_P in STMT whose value is IV in a group.
- New group will be created if there is no existing group for the use. */
+ New group will be created if there is no existing group for the use.
+ MEM_TYPE is the type of memory being addressed, or NULL if this
+ isn't an address reference. */
static struct iv_use *
record_group_use (struct ivopts_data *data, tree *use_p,
- struct iv *iv, gimple *stmt, enum use_type type)
+ struct iv *iv, gimple *stmt, enum use_type type,
+ tree mem_type)
{
tree addr_base = NULL;
struct iv_group *group = NULL;
- unsigned HOST_WIDE_INT addr_offset = 0;
+ poly_uint64 addr_offset = 0;
/* Record non address type use in a new group. */
- if (type == USE_ADDRESS && iv->base_object)
+ if (address_p (type))
{
unsigned int i;
group = data->vgroups[i];
use = group->vuses[0];
- if (use->type != USE_ADDRESS || !use->iv->base_object)
+ if (!address_p (use->type))
continue;
/* Check if it has the same stripped base and step. */
if (!group)
group = record_group (data, type);
- return record_use (group, use_p, iv, stmt, type, addr_base, addr_offset);
+ return record_use (group, use_p, iv, stmt, type, mem_type,
+ addr_base, addr_offset);
}
/* Checks whether the use OP is interesting and if so, records it. */
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (gimple_code (stmt) == GIMPLE_PHI || is_gimple_assign (stmt));
- use = record_group_use (data, NULL, iv, stmt, USE_NONLINEAR_EXPR);
+ use = record_group_use (data, NULL, iv, stmt, USE_NONLINEAR_EXPR, NULL_TREE);
iv->nonlin_use = use;
return use;
}
+/* Indicate how compare type iv_use can be handled. */
+enum comp_iv_rewrite
+{
+ COMP_IV_NA,
+ /* We may rewrite compare type iv_use by expressing value of the iv_use. */
+ COMP_IV_EXPR,
+ /* We may rewrite compare type iv_uses on both sides of comparison by
+ expressing value of each iv_use. */
+ COMP_IV_EXPR_2,
+ /* We may rewrite compare type iv_use by expressing value of the iv_use
+ or by eliminating it with other iv_cand. */
+ COMP_IV_ELIM
+};
+
/* Given a condition in statement STMT, checks whether it is a compare
of an induction variable and an invariant. If this is the case,
CONTROL_VAR is set to location of the iv, BOUND to the location of
the case, CONTROL_VAR and BOUND are set to the arguments of the
condition and false is returned. */
-static bool
+static enum comp_iv_rewrite
extract_cond_operands (struct ivopts_data *data, gimple *stmt,
tree **control_var, tree **bound,
struct iv **iv_var, struct iv **iv_bound)
static tree zero;
tree *op0 = &zero, *op1 = &zero;
struct iv *iv0 = &const_iv, *iv1 = &const_iv;
- bool ret = false;
+ enum comp_iv_rewrite rewrite_type = COMP_IV_NA;
if (gimple_code (stmt) == GIMPLE_COND)
{
if (TREE_CODE (*op1) == SSA_NAME)
iv1 = get_iv (data, *op1);
- /* Exactly one of the compared values must be an iv, and the other one must
- be an invariant. */
- if (!iv0 || !iv1)
+ /* If both sides of comparison are IVs. We can express ivs on both end. */
+ if (iv0 && iv1 && !integer_zerop (iv0->step) && !integer_zerop (iv1->step))
+ {
+ rewrite_type = COMP_IV_EXPR_2;
+ goto end;
+ }
+
+ /* If none side of comparison is IV. */
+ if ((!iv0 || integer_zerop (iv0->step))
+ && (!iv1 || integer_zerop (iv1->step)))
goto end;
- if (integer_zerop (iv0->step))
+ /* Control variable may be on the other side. */
+ if (!iv0 || integer_zerop (iv0->step))
{
- /* Control variable may be on the other side. */
std::swap (op0, op1);
std::swap (iv0, iv1);
}
- ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
+ /* If one side is IV and the other side isn't loop invariant. */
+ if (!iv1)
+ rewrite_type = COMP_IV_EXPR;
+ /* If one side is IV and the other side is loop invariant. */
+ else if (!integer_zerop (iv0->step) && integer_zerop (iv1->step))
+ rewrite_type = COMP_IV_ELIM;
end:
if (control_var)
if (iv_bound)
*iv_bound = iv1;
- return ret;
+ return rewrite_type;
}
/* Checks whether the condition in STMT is interesting and if so,
find_interesting_uses_cond (struct ivopts_data *data, gimple *stmt)
{
tree *var_p, *bound_p;
- struct iv *var_iv;
+ struct iv *var_iv, *bound_iv;
+ enum comp_iv_rewrite ret;
- if (!extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL))
+ ret = extract_cond_operands (data, stmt,
+ &var_p, &bound_p, &var_iv, &bound_iv);
+ if (ret == COMP_IV_NA)
{
find_interesting_uses_op (data, *var_p);
find_interesting_uses_op (data, *bound_p);
return;
}
- record_group_use (data, NULL, var_iv, stmt, USE_COMPARE);
+ record_group_use (data, var_p, var_iv, stmt, USE_COMPARE, NULL_TREE);
+ /* Record compare type iv_use for iv on the other side of comparison. */
+ if (ret == COMP_IV_EXPR_2)
+ record_group_use (data, bound_p, bound_iv, stmt, USE_COMPARE, NULL_TREE);
}
/* Returns the outermost loop EXPR is obviously invariant in
outside of the returned loop. Returns NULL if EXPR is not
even obviously invariant in LOOP. */
-struct loop *
-outermost_invariant_loop_for_expr (struct loop *loop, tree expr)
+class loop *
+outermost_invariant_loop_for_expr (class loop *loop, tree expr)
{
basic_block def_bb;
unsigned i, len;
len = TREE_OPERAND_LENGTH (expr);
for (i = 0; i < len; i++)
{
- struct loop *ivloop;
+ class loop *ivloop;
if (!TREE_OPERAND (expr, i))
continue;
should not be the function body. */
bool
-expr_invariant_in_loop_p (struct loop *loop, tree expr)
+expr_invariant_in_loop_p (class loop *loop, tree expr)
{
basic_block def_bb;
unsigned i, len;
struct iv *iv;
bool use_overflow_semantics = false;
tree step, iv_base, iv_step, lbound, off;
- struct loop *loop = dta->ivopts_data->current_loop;
+ class loop *loop = dta->ivopts_data->current_loop;
/* If base is a component ref, require that the offset of the reference
be invariant. */
if (TREE_CODE (bot) != INTEGER_CST)
return false;
- p0 = widest_int::from (top, SIGNED);
- p1 = widest_int::from (bot, SIGNED);
+ p0 = widest_int::from (wi::to_wide (top), SIGNED);
+ p1 = widest_int::from (wi::to_wide (bot), SIGNED);
if (p1 == 0)
return false;
*mul = wi::sext (wi::divmod_trunc (p0, p1, SIGNED, &res), precision);
return res == 0;
default:
+ if (POLY_INT_CST_P (top)
+ && POLY_INT_CST_P (bot)
+ && constant_multiple_p (wi::to_poly_widest (top),
+ wi::to_poly_widest (bot), mul))
+ return true;
+
return false;
}
}
{
switch (TREE_CODE (expr))
{
+ case VAR_DECL:
+ /* Check if it's a register variable. */
+ return DECL_HARD_REGISTER (expr);
+
case TARGET_MEM_REF:
/* TARGET_MEM_REFs are translated directly to valid MEMs on the
target, thus they are always addressable. */
}
civ = alloc_iv (data, base, step);
- record_group_use (data, op_p, civ, stmt, USE_ADDRESS);
+ /* Fail if base object of this memory reference is unknown. */
+ if (civ->base_object == NULL_TREE)
+ goto fail;
+
+ record_group_use (data, op_p, civ, stmt, USE_REF_ADDRESS, TREE_TYPE (*op_p));
return;
fail:
}
}
+/* CALL calls an internal function. If operand *OP_P will become an
+ address when the call is expanded, return the type of the memory
+ being addressed, otherwise return null. */
+
+static tree
+get_mem_type_for_internal_fn (gcall *call, tree *op_p)
+{
+ switch (gimple_call_internal_fn (call))
+ {
+ case IFN_MASK_LOAD:
+ case IFN_MASK_LOAD_LANES:
+ case IFN_LEN_LOAD:
+ if (op_p == gimple_call_arg_ptr (call, 0))
+ return TREE_TYPE (gimple_call_lhs (call));
+ return NULL_TREE;
+
+ case IFN_MASK_STORE:
+ case IFN_MASK_STORE_LANES:
+ case IFN_LEN_STORE:
+ if (op_p == gimple_call_arg_ptr (call, 0))
+ return TREE_TYPE (gimple_call_arg (call, 3));
+ return NULL_TREE;
+
+ default:
+ return NULL_TREE;
+ }
+}
+
+/* IV is a (non-address) iv that describes operand *OP_P of STMT.
+ Return true if the operand will become an address when STMT
+ is expanded and record the associated address use if so. */
+
+static bool
+find_address_like_use (struct ivopts_data *data, gimple *stmt, tree *op_p,
+ struct iv *iv)
+{
+ /* Fail if base object of this memory reference is unknown. */
+ if (iv->base_object == NULL_TREE)
+ return false;
+
+ tree mem_type = NULL_TREE;
+ if (gcall *call = dyn_cast <gcall *> (stmt))
+ if (gimple_call_internal_p (call))
+ mem_type = get_mem_type_for_internal_fn (call, op_p);
+ if (mem_type)
+ {
+ iv = alloc_iv (data, iv->base, iv->step);
+ record_group_use (data, op_p, iv, stmt, USE_PTR_ADDRESS, mem_type);
+ return true;
+ }
+ return false;
+}
+
/* Finds interesting uses of induction variables in the statement STMT. */
static void
if (!iv)
continue;
- find_interesting_uses_op (data, op);
+ if (!find_address_like_use (data, stmt, use_p->use, iv))
+ find_interesting_uses_op (data, op);
}
}
}
}
-/* Compute maximum offset of [base + offset] addressing mode
- for memory reference represented by USE. */
+/* Return TRUE if OFFSET is within the range of [base + offset] addressing
+ mode for memory reference represented by USE. */
+
+static GTY (()) vec<rtx, va_gc> *addr_list;
-static HOST_WIDE_INT
-compute_max_addr_offset (struct iv_use *use)
+static bool
+addr_offset_valid_p (struct iv_use *use, poly_int64 offset)
{
- 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));
+ unsigned list_index;
+ addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (use->iv->base));
+ machine_mode addr_mode, mem_mode = TYPE_MODE (use->mem_type);
- 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;
- }
+ if (list_index >= vec_safe_length (addr_list))
+ vec_safe_grow_cleared (addr_list, list_index + MAX_MACHINE_MODE, true);
- 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--)
+ addr = (*addr_list)[list_index];
+ if (!addr)
{
- off = (HOST_WIDE_INT_1U << 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 = (HOST_WIDE_INT_1U << 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;
- }
+ 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);
+ (*addr_list)[list_index] = addr;
}
- if (i == 0)
- off = 0;
+ else
+ addr_mode = GET_MODE (addr);
- max_offset_list[list_index] = off;
- return off;
+ XEXP (addr, 1) = gen_int_mode (offset, addr_mode);
+ return (memory_address_addr_space_p (mem_mode, addr, as));
}
/* Comparison function to sort group in ascending order of addr_offset. */
const struct iv_use *const *u1 = (const struct iv_use *const *) a;
const struct iv_use *const *u2 = (const struct iv_use *const *) b;
- if ((*u1)->addr_offset != (*u2)->addr_offset)
- return (*u1)->addr_offset < (*u2)->addr_offset ? -1 : 1;
- else
- return 0;
+ return compare_sizes_for_sort ((*u1)->addr_offset, (*u2)->addr_offset);
}
/* Check if small groups should be split. Return true if no group
if (group->vuses.length () == 1)
continue;
- gcc_assert (group->type == USE_ADDRESS);
+ gcc_assert (address_p (group->type));
if (group->vuses.length () == 2)
{
- if (group->vuses[0]->addr_offset > group->vuses[1]->addr_offset)
+ if (compare_sizes_for_sort (group->vuses[0]->addr_offset,
+ group->vuses[1]->addr_offset) > 0)
std::swap (group->vuses[0], group->vuses[1]);
}
else
distinct = 1;
for (pre = group->vuses[0], j = 1; j < group->vuses.length (); j++)
{
- if (group->vuses[j]->addr_offset != pre->addr_offset)
+ if (maybe_ne (group->vuses[j]->addr_offset, pre->addr_offset))
{
pre = group->vuses[j];
distinct++;
split_address_groups (struct ivopts_data *data)
{
unsigned int i, j;
- HOST_WIDE_INT max_offset = -1;
-
- /* Reset max offset to split all small groups. */
- if (split_small_address_groups_p (data))
- max_offset = 0;
+ /* Always split group. */
+ bool split_p = split_small_address_groups_p (data);
for (i = 0; i < data->vgroups.length (); i++)
{
+ struct iv_group *new_group = NULL;
struct iv_group *group = data->vgroups[i];
struct iv_use *use = group->vuses[0];
if (group->vuses.length () == 1)
continue;
- if (max_offset != 0)
- max_offset = compute_max_addr_offset (use);
+ gcc_assert (address_p (use->type));
- for (j = 1; j < group->vuses.length (); j++)
+ for (j = 1; j < group->vuses.length ();)
{
struct iv_use *next = group->vuses[j];
+ poly_int64 offset = next->addr_offset - use->addr_offset;
- /* Only uses with offset that can fit in offset part against
- the first use can be grouped together. */
- if (next->addr_offset - use->addr_offset
- > (unsigned HOST_WIDE_INT) max_offset)
- break;
+ /* Split group if aksed to, or the offset against the first
+ use can't fit in offset part of addressing mode. IV uses
+ having the same offset are still kept in one group. */
+ if (maybe_ne (offset, 0)
+ && (split_p || !addr_offset_valid_p (use, offset)))
+ {
+ if (!new_group)
+ new_group = record_group (data, group->type);
+ group->vuses.ordered_remove (j);
+ new_group->vuses.safe_push (next);
+ continue;
+ }
next->id = j;
next->group_id = group->id;
- }
- /* Split group. */
- if (j < group->vuses.length ())
- {
- struct iv_group *new_group = record_group (data, group->type);
- new_group->vuses.safe_splice (group->vuses);
- new_group->vuses.block_remove (0, j);
- group->vuses.truncate (j);
+ j++;
}
}
}
if (!is_gimple_debug (gsi_stmt (bsi)))
find_interesting_uses_stmt (data, gsi_stmt (bsi));
}
+ free (body);
split_address_groups (data);
if (dump_file && (dump_flags & TDF_DETAILS))
{
- bitmap_iterator bi;
-
- fprintf (dump_file, "\n<Invariant Vars>:\n");
- EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
- {
- struct version_info *info = ver_info (data, i);
- if (info->inv_id)
- {
- fprintf (dump_file, "Inv %d:\t", info->inv_id);
- print_generic_expr (dump_file, info->name, TDF_SLIM);
- fprintf (dump_file, "%s\n",
- info->has_nonlin_use ? "" : "\t(eliminable)");
- }
- }
-
fprintf (dump_file, "\n<IV Groups>:\n");
dump_groups (dump_file, data);
fprintf (dump_file, "\n");
}
-
- free (body);
}
/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
static tree
strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
- HOST_WIDE_INT *offset)
+ poly_int64 *offset)
{
tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
enum tree_code code;
tree type, orig_type = TREE_TYPE (expr);
- HOST_WIDE_INT off0, off1, st;
+ poly_int64 off0, off1;
+ HOST_WIDE_INT st;
tree orig_expr = expr;
STRIP_NOPS (expr);
switch (code)
{
- case INTEGER_CST:
- if (!cst_and_fits_in_hwi (expr)
- || integer_zerop (expr))
- return orig_expr;
-
- *offset = int_cst_value (expr);
- return build_int_cst (orig_type, 0);
-
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
break;
default:
+ if (ptrdiff_tree_p (expr, offset) && maybe_ne (*offset, 0))
+ return build_int_cst (orig_type, 0);
return orig_expr;
}
/* Strips constant offsets from EXPR and stores them to OFFSET. */
-static tree
-strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
+tree
+strip_offset (tree expr, poly_uint64_pod *offset)
{
- HOST_WIDE_INT off;
+ poly_int64 off;
tree core = strip_offset_1 (expr, false, false, &off);
*offset = off;
return core;
return unsigned_type_for (type);
}
-/* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
- the bitmap to that we should store it. */
+/* Private data for walk_tree. */
+
+struct walk_tree_data
+{
+ bitmap *inv_vars;
+ struct ivopts_data *idata;
+};
+
+/* Callback function for walk_tree, it records invariants and symbol
+ reference in *EXPR_P. DATA is the structure storing result info. */
-static struct ivopts_data *fd_ivopts_data;
static tree
-find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
+find_inv_vars_cb (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
{
- bitmap *depends_on = (bitmap *) data;
+ tree op = *expr_p;
struct version_info *info;
+ struct walk_tree_data *wdata = (struct walk_tree_data*) data;
- if (TREE_CODE (*expr_p) != SSA_NAME)
+ if (TREE_CODE (op) != SSA_NAME)
return NULL_TREE;
- info = name_info (fd_ivopts_data, *expr_p);
+ info = name_info (wdata->idata, op);
+ /* Because we expand simple operations when finding IVs, loop invariant
+ variable that isn't referred by the original loop could be used now.
+ Record such invariant variables here. */
+ if (!info->iv)
+ {
+ struct ivopts_data *idata = wdata->idata;
+ basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (op));
+
+ if (!bb || !flow_bb_inside_loop_p (idata->current_loop, bb))
+ {
+ tree steptype = TREE_TYPE (op);
+ if (POINTER_TYPE_P (steptype))
+ steptype = sizetype;
+ set_iv (idata, op, op, build_int_cst (steptype, 0), true);
+ record_invariant (idata, op, false);
+ }
+ }
if (!info->inv_id || info->has_nonlin_use)
return NULL_TREE;
- if (!*depends_on)
- *depends_on = BITMAP_ALLOC (NULL);
- bitmap_set_bit (*depends_on, info->inv_id);
+ if (!*wdata->inv_vars)
+ *wdata->inv_vars = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (*wdata->inv_vars, info->inv_id);
return NULL_TREE;
}
+/* Records invariants in *EXPR_P. INV_VARS is the bitmap to that we should
+ store it. */
+
+static inline void
+find_inv_vars (struct ivopts_data *data, tree *expr_p, bitmap *inv_vars)
+{
+ struct walk_tree_data wdata;
+
+ if (!inv_vars)
+ return;
+
+ wdata.idata = data;
+ wdata.inv_vars = inv_vars;
+ walk_tree (expr_p, find_inv_vars_cb, &wdata, NULL);
+}
+
+/* Get entry from invariant expr hash table for INV_EXPR. New entry
+ will be recorded if it doesn't exist yet. Given below two exprs:
+ inv_expr + cst1, inv_expr + cst2
+ It's hard to make decision whether constant part should be stripped
+ or not. We choose to not strip based on below facts:
+ 1) We need to count ADD cost for constant part if it's stripped,
+ which isn't always trivial where this functions is called.
+ 2) Stripping constant away may be conflict with following loop
+ invariant hoisting pass.
+ 3) Not stripping constant away results in more invariant exprs,
+ which usually leads to decision preferring lower reg pressure. */
+
+static iv_inv_expr_ent *
+get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
+{
+ STRIP_NOPS (inv_expr);
+
+ if (poly_int_tree_p (inv_expr)
+ || TREE_CODE (inv_expr) == SSA_NAME)
+ return NULL;
+
+ /* Don't strip constant part away as we used to. */
+
+ /* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent. */
+ struct iv_inv_expr_ent ent;
+ ent.expr = inv_expr;
+ ent.hash = iterative_hash_expr (inv_expr, 0);
+ struct iv_inv_expr_ent **slot = data->inv_expr_tab->find_slot (&ent, INSERT);
+
+ if (!*slot)
+ {
+ *slot = XNEW (struct iv_inv_expr_ent);
+ (*slot)->expr = inv_expr;
+ (*slot)->hash = ent.hash;
+ (*slot)->id = ++data->max_inv_expr_id;
+ }
+
+ return *slot;
+}
+
/* 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
replacement of the final value of the iv by a direct computation. */
static struct iv_cand *
-add_candidate_1 (struct ivopts_data *data,
- tree base, tree step, bool important, enum iv_position pos,
- struct iv_use *use, gimple *incremented_at,
- struct iv *orig_iv = NULL)
+add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
+ enum iv_position pos, struct iv_use *use,
+ gimple *incremented_at, struct iv *orig_iv = NULL,
+ bool doloop = false)
{
unsigned i;
struct iv_cand *cand = NULL;
cand->pos = pos;
if (pos != IP_ORIGINAL)
{
- cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
+ if (doloop)
+ cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "doloop");
+ else
+ cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
cand->var_after = cand->var_before;
}
cand->important = important;
cand->incremented_at = incremented_at;
+ cand->doloop_p = doloop;
data->vcands.safe_push (cand);
- if (TREE_CODE (step) != INTEGER_CST)
+ if (!poly_int_tree_p (step))
{
- fd_ivopts_data = data;
- walk_tree (&step, find_depends, &cand->depends_on, NULL);
+ find_inv_vars (data, &step, &cand->inv_vars);
+
+ iv_inv_expr_ent *inv_expr = get_loop_invariant_expr (data, step);
+ /* Share bitmap between inv_vars and inv_exprs for cand. */
+ if (inv_expr != NULL)
+ {
+ cand->inv_exprs = cand->inv_vars;
+ cand->inv_vars = NULL;
+ if (cand->inv_exprs)
+ bitmap_clear (cand->inv_exprs);
+ else
+ cand->inv_exprs = BITMAP_ALLOC (NULL);
+
+ bitmap_set_bit (cand->inv_exprs, inv_expr->id);
+ }
}
if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
}
cand->important |= important;
+ cand->doloop_p |= doloop;
/* Relate candidate to the group for which it is added. */
if (use)
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. */
+ less freedom to scheduler. So we allow IP_END only if IP_NORMAL 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)
+allow_ip_end_pos_p (class loop *loop)
{
if (!ip_normal_pos (loop))
return true;
statement. */
if (use_bb->loop_father != data->current_loop
|| !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
- || stmt_could_throw_p (use->stmt)
+ || stmt_can_throw_internal (cfun, use->stmt)
|| !cst_and_fits_in_hwi (step))
return;
cstepi = int_cst_value (step);
- mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
+ mem_mode = TYPE_MODE (use->mem_type);
if (((USE_LOAD_PRE_INCREMENT (mem_mode)
|| USE_STORE_PRE_INCREMENT (mem_mode))
- && GET_MODE_SIZE (mem_mode) == cstepi)
+ && known_eq (GET_MODE_SIZE (mem_mode), cstepi))
|| ((USE_LOAD_PRE_DECREMENT (mem_mode)
|| USE_STORE_PRE_DECREMENT (mem_mode))
- && GET_MODE_SIZE (mem_mode) == -cstepi))
+ && known_eq (GET_MODE_SIZE (mem_mode), -cstepi)))
{
enum tree_code code = MINUS_EXPR;
tree new_base;
}
if (((USE_LOAD_POST_INCREMENT (mem_mode)
|| USE_STORE_POST_INCREMENT (mem_mode))
- && GET_MODE_SIZE (mem_mode) == cstepi)
+ && known_eq (GET_MODE_SIZE (mem_mode), cstepi))
|| ((USE_LOAD_POST_DECREMENT (mem_mode)
|| USE_STORE_POST_DECREMENT (mem_mode))
- && GET_MODE_SIZE (mem_mode) == -cstepi))
+ && known_eq (GET_MODE_SIZE (mem_mode), -cstepi)))
{
add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
use->stmt);
the end of loop. */
static void
-add_candidate (struct ivopts_data *data,
- tree base, tree step, bool important, struct iv_use *use,
- struct iv *orig_iv = NULL)
+add_candidate (struct ivopts_data *data, tree base, tree step, bool important,
+ struct iv_use *use, struct iv *orig_iv = NULL,
+ bool doloop = false)
{
if (ip_normal_pos (data->current_loop))
- add_candidate_1 (data, base, step, important,
- IP_NORMAL, use, NULL, orig_iv);
- if (ip_end_pos (data->current_loop)
+ add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL, orig_iv,
+ doloop);
+ /* Exclude doloop candidate here since it requires decrement then comparison
+ and jump, the IP_END position doesn't match. */
+ if (!doloop && 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, orig_iv);
}
record_common_cand (struct ivopts_data *data, tree base,
tree step, struct iv_use *use)
{
- struct iv_common_cand ent;
- struct iv_common_cand **slot;
+ class iv_common_cand ent;
+ class iv_common_cand **slot;
ent.base = base;
ent.step = step;
common_cand_cmp (const void *p1, const void *p2)
{
unsigned n1, n2;
- const struct iv_common_cand *const *const ccand1
- = (const struct iv_common_cand *const *)p1;
- const struct iv_common_cand *const *const ccand2
- = (const struct iv_common_cand *const *)p2;
+ const class iv_common_cand *const *const ccand1
+ = (const class iv_common_cand *const *)p1;
+ const class iv_common_cand *const *const ccand2
+ = (const class iv_common_cand *const *)p2;
n1 = (*ccand1)->uses.length ();
n2 = (*ccand2)->uses.length ();
data->iv_common_cands.qsort (common_cand_cmp);
for (i = 0; i < data->iv_common_cands.length (); i++)
{
- struct iv_common_cand *ptr = data->iv_common_cands[i];
+ class iv_common_cand *ptr = data->iv_common_cands[i];
/* Only add IV candidate if it's derived from multiple uses. */
if (ptr->uses.length () <= 1)
static void
add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
{
- unsigned HOST_WIDE_INT offset;
+ poly_uint64 offset;
tree base;
- tree basetype;
struct iv *iv = use->iv;
+ tree basetype = TREE_TYPE (iv->base);
+
+ /* Don't add candidate for iv_use with non integer, pointer or non-mode
+ precision types, instead, add candidate for the corresponding scev in
+ unsigned type with the same precision. See PR93674 for more info. */
+ if ((TREE_CODE (basetype) != INTEGER_TYPE && !POINTER_TYPE_P (basetype))
+ || !type_has_mode_precision_p (basetype))
+ {
+ basetype = lang_hooks.types.type_for_mode (TYPE_MODE (basetype),
+ TYPE_UNSIGNED (basetype));
+ add_candidate (data, fold_convert (basetype, iv->base),
+ fold_convert (basetype, iv->step), false, NULL);
+ return;
+ }
add_candidate (data, iv->base, iv->step, false, use);
basetype = sizetype;
record_common_cand (data, build_int_cst (basetype, 0), iv->step, use);
+ /* Compare the cost of an address with an unscaled index with the cost of
+ an address with a scaled index and add candidate if useful. */
+ poly_int64 step;
+ if (use != NULL
+ && poly_int_tree_p (iv->step, &step)
+ && address_p (use->type))
+ {
+ poly_int64 new_step;
+ unsigned int fact = preferred_mem_scale_factor
+ (use->iv->base,
+ TYPE_MODE (use->mem_type),
+ optimize_loop_for_speed_p (data->current_loop));
+
+ if (fact != 1
+ && multiple_p (step, fact, &new_step))
+ add_candidate (data, size_int (0),
+ wide_int_to_tree (sizetype, new_step),
+ true, NULL);
+ }
+
/* Record common candidate with constant offset stripped in base.
Like the use itself, we also add candidate directly for it. */
base = strip_offset (iv->base, &offset);
- if (offset || base != iv->base)
+ if (maybe_ne (offset, 0U) || base != iv->base)
{
record_common_cand (data, base, iv->step, use);
add_candidate (data, base, iv->step, false, use);
}
/* Record common candidate with base_object removed in base. */
- if (iv->base_object != NULL)
+ base = iv->base;
+ STRIP_NOPS (base);
+ if (iv->base_object != NULL && TREE_CODE (base) == POINTER_PLUS_EXPR)
{
- unsigned i;
- aff_tree aff_base;
- tree step, base_object = iv->base_object;
+ tree step = iv->step;
- base = iv->base;
- step = iv->step;
- STRIP_NOPS (base);
STRIP_NOPS (step);
- STRIP_NOPS (base_object);
- tree_to_aff_combination (base, TREE_TYPE (base), &aff_base);
- for (i = 0; i < aff_base.n; i++)
- {
- if (aff_base.elts[i].coef != 1)
- continue;
-
- if (operand_equal_p (aff_base.elts[i].val, base_object, 0))
- break;
- }
- if (i < aff_base.n)
- {
- aff_combination_remove_elt (&aff_base, i);
- base = aff_combination_to_tree (&aff_base);
- basetype = TREE_TYPE (base);
- if (POINTER_TYPE_P (basetype))
- basetype = sizetype;
-
- step = fold_convert (basetype, step);
- record_common_cand (data, base, step, use);
- /* Also record common candidate with offset stripped. */
- base = strip_offset (base, &offset);
- if (offset)
- record_common_cand (data, base, step, use);
- }
+ base = TREE_OPERAND (base, 1);
+ step = fold_convert (sizetype, step);
+ record_common_cand (data, base, step, use);
+ /* Also record common candidate with offset stripped. */
+ base = strip_offset (base, &offset);
+ if (maybe_ne (offset, 0U))
+ record_common_cand (data, base, step, use);
}
/* At last, add auto-incremental candidates. Make such variables
important since other iv uses with same base object may be based
on it. */
- if (use != NULL && use->type == USE_ADDRESS)
+ if (use != NULL && address_p (use->type))
add_autoinc_candidates (data, iv->base, iv->step, true, use);
}
}
group->n_map_members = size;
- group->cost_map = XCNEWVEC (struct cost_pair, size);
+ group->cost_map = XCNEWVEC (class cost_pair, size);
}
}
/* Sets cost of (GROUP, CAND) 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. */
+ on invariants INV_VARS and that the value used in expressing it is
+ VALUE, and in case of iv elimination the comparison operator is COMP. */
static void
set_group_iv_cost (struct ivopts_data *data,
struct iv_group *group, struct iv_cand *cand,
- comp_cost cost, bitmap depends_on, tree value,
- enum tree_code comp, iv_inv_expr_ent *inv_expr)
+ comp_cost cost, bitmap inv_vars, tree value,
+ enum tree_code comp, bitmap inv_exprs)
{
unsigned i, s;
if (cost.infinite_cost_p ())
{
- BITMAP_FREE (depends_on);
+ BITMAP_FREE (inv_vars);
+ BITMAP_FREE (inv_exprs);
return;
}
{
group->cost_map[cand->id].cand = cand;
group->cost_map[cand->id].cost = cost;
- group->cost_map[cand->id].depends_on = depends_on;
+ group->cost_map[cand->id].inv_vars = inv_vars;
+ group->cost_map[cand->id].inv_exprs = inv_exprs;
group->cost_map[cand->id].value = value;
group->cost_map[cand->id].comp = comp;
- group->cost_map[cand->id].inv_expr = inv_expr;
return;
}
found:
group->cost_map[i].cand = cand;
group->cost_map[i].cost = cost;
- group->cost_map[i].depends_on = depends_on;
+ group->cost_map[i].inv_vars = inv_vars;
+ group->cost_map[i].inv_exprs = inv_exprs;
group->cost_map[i].value = value;
group->cost_map[i].comp = comp;
- group->cost_map[i].inv_expr = inv_expr;
}
/* Gets cost of (GROUP, CAND) pair. */
-static struct cost_pair *
+static class cost_pair *
get_group_iv_cost (struct ivopts_data *data, struct iv_group *group,
struct iv_cand *cand)
{
unsigned i, s;
- struct cost_pair *ret;
+ class cost_pair *ret;
if (!cand)
return NULL;
return NULL_TREE;
}
-/* Determines cost of the computation of EXPR. */
+/* Predict whether the given loop will be transformed in the RTL
+ doloop_optimize pass. Attempt to duplicate some doloop_optimize checks.
+ This is only for target independent checks, see targetm.predict_doloop_p
+ for the target dependent ones.
-static unsigned
-computation_cost (tree expr, bool speed)
+ Note that according to some initial investigation, some checks like costly
+ niter check and invalid stmt scanning don't have much gains among general
+ cases, so keep this as simple as possible first.
+
+ Some RTL specific checks seems unable to be checked in gimple, if any new
+ checks or easy checks _are_ missing here, please add them. */
+
+static bool
+generic_predict_doloop_p (struct ivopts_data *data)
{
- rtx_insn *seq;
- rtx rslt;
- tree type = TREE_TYPE (expr);
- unsigned cost;
- /* Avoid using hard regs in ways which may be unsupported. */
- int regno = LAST_VIRTUAL_REGISTER + 1;
- struct cgraph_node *node = cgraph_node::get (current_function_decl);
- enum node_frequency real_frequency = node->frequency;
+ class loop *loop = data->current_loop;
- node->frequency = NODE_FREQUENCY_NORMAL;
- crtl->maybe_hot_insn_p = speed;
- walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
- start_sequence ();
- rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
+ /* Call target hook for target dependent checks. */
+ if (!targetm.predict_doloop_p (loop))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Predict doloop failure due to"
+ " target specific checks.\n");
+ return false;
+ }
+
+ /* Similar to doloop_optimize, check iteration description to know it's
+ suitable or not. Keep it as simple as possible, feel free to extend it
+ if you find any multiple exits cases matter. */
+ edge exit = single_dom_exit (loop);
+ class tree_niter_desc *niter_desc;
+ if (!exit || !(niter_desc = niter_for_exit (data, exit)))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Predict doloop failure due to"
+ " unexpected niters.\n");
+ return false;
+ }
+
+ /* Similar to doloop_optimize, check whether iteration count too small
+ and not profitable. */
+ HOST_WIDE_INT est_niter = get_estimated_loop_iterations_int (loop);
+ if (est_niter == -1)
+ est_niter = get_likely_max_loop_iterations_int (loop);
+ if (est_niter >= 0 && est_niter < 3)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Predict doloop failure due to"
+ " too few iterations (%u).\n",
+ (unsigned int) est_niter);
+ return false;
+ }
+
+ return true;
+}
+
+/* Determines cost of the computation of EXPR. */
+
+static unsigned
+computation_cost (tree expr, bool speed)
+{
+ rtx_insn *seq;
+ rtx rslt;
+ tree type = TREE_TYPE (expr);
+ unsigned cost;
+ /* Avoid using hard regs in ways which may be unsupported. */
+ int regno = LAST_VIRTUAL_REGISTER + 1;
+ struct cgraph_node *node = cgraph_node::get (current_function_decl);
+ enum node_frequency real_frequency = node->frequency;
+
+ node->frequency = NODE_FREQUENCY_NORMAL;
+ crtl->maybe_hot_insn_p = speed;
+ walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
+ start_sequence ();
+ rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
seq = get_insns ();
end_sequence ();
default_rtl_profile ();
/* Returns variable containing the value of candidate CAND at statement AT. */
static tree
-var_at_stmt (struct loop *loop, struct iv_cand *cand, gimple *stmt)
+var_at_stmt (class loop *loop, struct iv_cand *cand, gimple *stmt)
{
if (stmt_after_increment (loop, cand, stmt))
return cand->var_after;
}
/* Determines the expression by that USE is expressed from induction variable
- CAND at statement AT in LOOP. The expression is stored in a decomposed
- form into AFF. Returns false if USE cannot be expressed using CAND. */
+ CAND at statement AT in LOOP. The expression is stored in two parts in a
+ decomposed form. The invariant part is stored in AFF_INV; while variant
+ part in AFF_VAR. Store ratio of CAND.step over USE.step in PRAT if it's
+ non-null. Returns false if USE cannot be expressed using CAND. */
static bool
-get_computation_aff (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, gimple *at,
- struct aff_tree *aff)
-{
- tree ubase = use->iv->base;
- tree ustep = use->iv->step;
- tree cbase = cand->iv->base;
- tree cstep = cand->iv->step, cstep_common;
+get_computation_aff_1 (class loop *loop, gimple *at, struct iv_use *use,
+ struct iv_cand *cand, class aff_tree *aff_inv,
+ class aff_tree *aff_var, widest_int *prat = NULL)
+{
+ tree ubase = use->iv->base, ustep = use->iv->step;
+ tree cbase = cand->iv->base, cstep = cand->iv->step;
+ tree common_type, uutype, var, cstep_common;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
- tree common_type, var;
- tree uutype;
- aff_tree cbase_aff, var_aff;
+ aff_tree aff_cbase;
widest_int rat;
+ /* We must have a precision to express the values of use. */
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
- {
- /* We do not have a precision to express the values of use. */
- return false;
- }
+ return false;
var = var_at_stmt (loop, cand, at);
uutype = unsigned_type_for (utype);
if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
if (cand->orig_iv != NULL && CONVERT_EXPR_P (cbase)
- && (CONVERT_EXPR_P (cstep) || TREE_CODE (cstep) == INTEGER_CST))
+ && (CONVERT_EXPR_P (cstep) || poly_int_tree_p (cstep)))
{
tree inner_base, inner_step, inner_type;
inner_base = TREE_OPERAND (cbase, 0);
cstep = inner_step;
}
}
- cstep = fold_convert (uutype, cstep);
cbase = fold_convert (uutype, cbase);
+ cstep = fold_convert (uutype, cstep);
var = fold_convert (uutype, var);
}
else if (!constant_multiple_of (ustep, cstep, &rat))
return false;
+ if (prat)
+ *prat = rat;
+
/* In case both UBASE and CBASE are shortened to UUTYPE from some common
type, we achieve better folding by computing their difference in this
wider type, and cast the result to UUTYPE. We do not need to worry about
common_type = determine_common_wider_type (&ubase, &cbase);
/* use = ubase - ratio * cbase + ratio * var. */
- tree_to_aff_combination (ubase, common_type, aff);
- tree_to_aff_combination (cbase, common_type, &cbase_aff);
- tree_to_aff_combination (var, uutype, &var_aff);
+ tree_to_aff_combination (ubase, common_type, aff_inv);
+ tree_to_aff_combination (cbase, common_type, &aff_cbase);
+ tree_to_aff_combination (var, uutype, aff_var);
/* We need to shift the value if we are after the increment. */
if (stmt_after_increment (loop, cand, at))
cstep_common = cstep;
tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
- aff_combination_add (&cbase_aff, &cstep_aff);
+ aff_combination_add (&aff_cbase, &cstep_aff);
}
- aff_combination_scale (&cbase_aff, -rat);
- aff_combination_add (aff, &cbase_aff);
+ aff_combination_scale (&aff_cbase, -rat);
+ aff_combination_add (aff_inv, &aff_cbase);
if (common_type != uutype)
- aff_combination_convert (aff, uutype);
+ aff_combination_convert (aff_inv, uutype);
- aff_combination_scale (&var_aff, rat);
- aff_combination_add (aff, &var_aff);
+ aff_combination_scale (aff_var, rat);
+ return true;
+}
+/* Determines the expression by that USE is expressed from induction variable
+ CAND at statement AT in LOOP. The expression is stored in a decomposed
+ form into AFF. Returns false if USE cannot be expressed using CAND. */
+
+static bool
+get_computation_aff (class loop *loop, gimple *at, struct iv_use *use,
+ struct iv_cand *cand, class aff_tree *aff)
+{
+ aff_tree aff_var;
+
+ if (!get_computation_aff_1 (loop, at, use, cand, aff, &aff_var))
+ return false;
+
+ aff_combination_add (aff, &aff_var);
return true;
}
tree base_type = TREE_TYPE (use->iv->base);
tree type;
- if (use->type == USE_ADDRESS)
+ if (use->type == USE_REF_ADDRESS)
{
/* The base_type may be a void pointer. Create a pointer type based on
the mem_ref instead. */
CAND at statement AT in LOOP. The computation is unshared. */
static tree
-get_computation_at (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, gimple *at)
+get_computation_at (class loop *loop, gimple *at,
+ struct iv_use *use, struct iv_cand *cand)
{
aff_tree aff;
tree type = get_use_type (use);
- if (!get_computation_aff (loop, use, cand, at, &aff))
+ if (!get_computation_aff (loop, at, use, cand, &aff))
return NULL_TREE;
unshare_aff_combination (&aff);
return fold_convert (type, aff_combination_to_tree (&aff));
}
-/* Determines the expression by that USE is expressed from induction variable
- CAND in LOOP. The computation is unshared. */
+/* Like get_computation_at, but try harder, even if the computation
+ is more expensive. Intended for debug stmts. */
static tree
-get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
+get_debug_computation_at (class loop *loop, gimple *at,
+ struct iv_use *use, struct iv_cand *cand)
{
- return get_computation_at (loop, use, cand, use->stmt);
-}
+ if (tree ret = get_computation_at (loop, at, use, cand))
+ return ret;
-/* Adjust the cost COST for being in loop setup rather than loop body.
- If we're optimizing for space, the loop setup overhead is constant;
- if we're optimizing for speed, amortize it over the per-iteration cost. */
-static unsigned
-adjust_setup_cost (struct ivopts_data *data, unsigned cost)
-{
- if (cost == INFTY)
- return cost;
- else if (optimize_loop_for_speed_p (data->current_loop))
- return cost / avg_loop_niter (data->current_loop);
- else
- return cost;
-}
+ tree ubase = use->iv->base, ustep = use->iv->step;
+ tree cbase = cand->iv->base, cstep = cand->iv->step;
+ tree var;
+ tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+ widest_int rat;
-/* Returns true if multiplying by RATIO is allowed in an address. Test the
- validity for a memory reference accessing memory of mode MODE in
- address space AS. */
+ /* We must have a precision to express the values of use. */
+ if (TYPE_PRECISION (utype) >= TYPE_PRECISION (ctype))
+ return NULL_TREE;
+ /* Try to handle the case that get_computation_at doesn't,
+ try to express
+ use = ubase + (var - cbase) / ratio. */
+ if (!constant_multiple_of (cstep, fold_convert (TREE_TYPE (cstep), ustep),
+ &rat))
+ return NULL_TREE;
-bool
-multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, machine_mode mode,
- addr_space_t as)
-{
-#define MAX_RATIO 128
- unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mode;
- static vec<sbitmap> valid_mult_list;
- sbitmap valid_mult;
-
- if (data_index >= valid_mult_list.length ())
- valid_mult_list.safe_grow_cleared (data_index + 1);
-
- valid_mult = valid_mult_list[data_index];
- if (!valid_mult)
- {
- 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;
- HOST_WIDE_INT i;
-
- valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
- bitmap_clear (valid_mult);
- scaled = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
- addr = gen_rtx_fmt_ee (PLUS, address_mode, scaled, reg2);
- for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
- {
- XEXP (scaled, 1) = gen_int_mode (i, address_mode);
- if (memory_address_addr_space_p (mode, addr, as)
- || memory_address_addr_space_p (mode, scaled, as))
- bitmap_set_bit (valid_mult, i + MAX_RATIO);
- }
+ bool neg_p = false;
+ if (wi::neg_p (rat))
+ {
+ if (TYPE_UNSIGNED (ctype))
+ return NULL_TREE;
+ neg_p = true;
+ rat = wi::neg (rat);
+ }
+
+ /* If both IVs can wrap around and CAND doesn't have a power of two step,
+ it is unsafe. Consider uint16_t CAND with step 9, when wrapping around,
+ the values will be ... 0xfff0, 0xfff9, 2, 11 ... and when use is say
+ uint8_t with step 3, those values divided by 3 cast to uint8_t will be
+ ... 0x50, 0x53, 0, 3 ... rather than expected 0x50, 0x53, 0x56, 0x59. */
+ if (!use->iv->no_overflow
+ && !cand->iv->no_overflow
+ && !integer_pow2p (cstep))
+ return NULL_TREE;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " allowed multipliers:");
- for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
- if (bitmap_bit_p (valid_mult, i + MAX_RATIO))
- fprintf (dump_file, " %d", (int) i);
- fprintf (dump_file, "\n");
- fprintf (dump_file, "\n");
- }
+ int bits = wi::exact_log2 (rat);
+ if (bits == -1)
+ bits = wi::floor_log2 (rat) + 1;
+ if (!cand->iv->no_overflow
+ && TYPE_PRECISION (utype) + bits > TYPE_PRECISION (ctype))
+ return NULL_TREE;
+
+ var = var_at_stmt (loop, cand, at);
- valid_mult_list[data_index] = valid_mult;
+ if (POINTER_TYPE_P (ctype))
+ {
+ ctype = unsigned_type_for (ctype);
+ cbase = fold_convert (ctype, cbase);
+ cstep = fold_convert (ctype, cstep);
+ var = fold_convert (ctype, var);
}
- if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
- return false;
+ if (stmt_after_increment (loop, cand, at))
+ var = fold_build2 (MINUS_EXPR, TREE_TYPE (var), var,
+ unshare_expr (cstep));
- return bitmap_bit_p (valid_mult, ratio + MAX_RATIO);
+ var = fold_build2 (MINUS_EXPR, TREE_TYPE (var), var, cbase);
+ var = fold_build2 (EXACT_DIV_EXPR, TREE_TYPE (var), var,
+ wide_int_to_tree (TREE_TYPE (var), rat));
+ if (POINTER_TYPE_P (utype))
+ {
+ var = fold_convert (sizetype, var);
+ if (neg_p)
+ var = fold_build1 (NEGATE_EXPR, sizetype, var);
+ var = fold_build2 (POINTER_PLUS_EXPR, utype, ubase, var);
+ }
+ else
+ {
+ var = fold_convert (utype, var);
+ var = fold_build2 (neg_p ? MINUS_EXPR : PLUS_EXPR, utype,
+ ubase, var);
+ }
+ return var;
}
-/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
- If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
- variable is omitted. Compute the cost for a memory reference that accesses
- a memory location of mode MEM_MODE in address space AS.
-
- MAY_AUTOINC is set to true if the autoincrement (increasing index by
- size of MEM_MODE / RATIO) is available. To make this determination, we
- look at the size of the increment to be made, which is given in CSTEP.
- CSTEP may be zero if the step is unknown.
- STMT_AFTER_INC is true iff the statement we're looking at is after the
- increment of the original biv.
-
- TODO -- there must be some better way. This all is quite crude. */
-
-enum ainc_type
-{
- AINC_PRE_INC, /* Pre increment. */
- AINC_PRE_DEC, /* Pre decrement. */
- AINC_POST_INC, /* Post increment. */
- AINC_POST_DEC, /* Post decrement. */
- AINC_NONE /* Also the number of auto increment types. */
-};
-
-struct address_cost_data
-{
- HOST_WIDE_INT min_offset, max_offset;
- unsigned costs[2][2][2][2];
- unsigned ainc_costs[AINC_NONE];
-};
-
-
-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, machine_mode mem_mode,
- addr_space_t as, bool speed,
- bool stmt_after_inc, bool *may_autoinc)
+/* Adjust the cost COST for being in loop setup rather than loop body.
+ If we're optimizing for space, the loop setup overhead is constant;
+ if we're optimizing for speed, amortize it over the per-iteration cost.
+ If ROUND_UP_P is true, the result is round up rather than to zero when
+ optimizing for speed. */
+static int64_t
+adjust_setup_cost (struct ivopts_data *data, int64_t cost,
+ bool round_up_p = false)
{
- 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;
- static bool has_preinc[MAX_MACHINE_MODE], has_postinc[MAX_MACHINE_MODE];
- static bool has_predec[MAX_MACHINE_MODE], has_postdec[MAX_MACHINE_MODE];
- unsigned cost, acost, complexity;
- enum ainc_type autoinc_type;
- bool offset_p, ratio_p, autoinc;
- HOST_WIDE_INT s_offset, autoinc_offset, msize;
- unsigned HOST_WIDE_INT mask;
- unsigned bits;
-
- if (data_index >= address_cost_data_list.length ())
- address_cost_data_list.safe_grow_cleared (data_index + 1);
-
- data = address_cost_data_list[data_index];
- if (!data)
- {
- HOST_WIDE_INT i;
- HOST_WIDE_INT rat, off = 0;
- int old_cse_not_expected, width;
- unsigned sym_p, var_p, off_p, rat_p, add_c;
- rtx_insn *seq;
- rtx addr, base;
- rtx reg0, reg1;
-
- data = (address_cost_data *) xcalloc (1, sizeof (*data));
-
- reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
-
- width = GET_MODE_BITSIZE (address_mode) - 1;
- if (width > (HOST_BITS_PER_WIDE_INT - 1))
- width = HOST_BITS_PER_WIDE_INT - 1;
- addr = gen_rtx_fmt_ee (PLUS, address_mode, reg1, NULL_RTX);
-
- for (i = width; i >= 0; i--)
- {
- off = -(HOST_WIDE_INT_1U << i);
- XEXP (addr, 1) = gen_int_mode (off, address_mode);
- if (memory_address_addr_space_p (mem_mode, addr, as))
- break;
- }
- data->min_offset = (i == -1? 0 : off);
-
- for (i = width; i >= 0; i--)
- {
- off = (HOST_WIDE_INT_1U << i) - 1;
- 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
- ? (HOST_WIDE_INT_1U << 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;
- data->max_offset = off;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "get_address_cost:\n");
- fprintf (dump_file, " min offset %s " HOST_WIDE_INT_PRINT_DEC "\n",
- GET_MODE_NAME (mem_mode),
- data->min_offset);
- fprintf (dump_file, " max offset %s " HOST_WIDE_INT_PRINT_DEC "\n",
- GET_MODE_NAME (mem_mode),
- data->max_offset);
- }
-
- rat = 1;
- for (i = 2; i <= MAX_RATIO; i++)
- if (multiplier_allowed_in_address_p (i, mem_mode, as))
- {
- rat = i;
- break;
- }
-
- /* Compute the cost of various addressing modes. */
- acost = 0;
- reg0 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
- reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
-
- if (USE_LOAD_PRE_DECREMENT (mem_mode)
- || USE_STORE_PRE_DECREMENT (mem_mode))
- {
- addr = gen_rtx_PRE_DEC (address_mode, reg0);
- has_predec[mem_mode]
- = memory_address_addr_space_p (mem_mode, addr, as);
-
- if (has_predec[mem_mode])
- data->ainc_costs[AINC_PRE_DEC]
- = address_cost (addr, mem_mode, as, speed);
- }
- if (USE_LOAD_POST_DECREMENT (mem_mode)
- || USE_STORE_POST_DECREMENT (mem_mode))
- {
- addr = gen_rtx_POST_DEC (address_mode, reg0);
- has_postdec[mem_mode]
- = memory_address_addr_space_p (mem_mode, addr, as);
-
- if (has_postdec[mem_mode])
- data->ainc_costs[AINC_POST_DEC]
- = address_cost (addr, mem_mode, as, speed);
- }
- if (USE_LOAD_PRE_INCREMENT (mem_mode)
- || USE_STORE_PRE_DECREMENT (mem_mode))
- {
- addr = gen_rtx_PRE_INC (address_mode, reg0);
- has_preinc[mem_mode]
- = memory_address_addr_space_p (mem_mode, addr, as);
-
- if (has_preinc[mem_mode])
- data->ainc_costs[AINC_PRE_INC]
- = address_cost (addr, mem_mode, as, speed);
- }
- if (USE_LOAD_POST_INCREMENT (mem_mode)
- || USE_STORE_POST_INCREMENT (mem_mode))
- {
- addr = gen_rtx_POST_INC (address_mode, reg0);
- has_postinc[mem_mode]
- = memory_address_addr_space_p (mem_mode, addr, as);
-
- if (has_postinc[mem_mode])
- data->ainc_costs[AINC_POST_INC]
- = address_cost (addr, mem_mode, as, speed);
- }
- for (i = 0; i < 16; i++)
- {
- sym_p = i & 1;
- var_p = (i >> 1) & 1;
- off_p = (i >> 2) & 1;
- rat_p = (i >> 3) & 1;
-
- addr = reg0;
- if (rat_p)
- addr = gen_rtx_fmt_ee (MULT, address_mode, addr,
- gen_int_mode (rat, address_mode));
-
- if (var_p)
- addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, reg1);
-
- if (sym_p)
- {
- base = gen_rtx_SYMBOL_REF (address_mode, ggc_strdup (""));
- /* ??? We can run into trouble with some backends by presenting
- it with symbols which haven't been properly passed through
- targetm.encode_section_info. By setting the local bit, we
- enhance the probability of things working. */
- SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
-
- if (off_p)
- base = gen_rtx_fmt_e (CONST, address_mode,
- gen_rtx_fmt_ee
- (PLUS, address_mode, base,
- gen_int_mode (off, address_mode)));
- }
- else if (off_p)
- base = gen_int_mode (off, address_mode);
- else
- base = NULL_RTX;
-
- if (base)
- addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, base);
-
- start_sequence ();
- /* To avoid splitting addressing modes, pretend that no cse will
- follow. */
- old_cse_not_expected = cse_not_expected;
- cse_not_expected = true;
- addr = memory_address_addr_space (mem_mode, addr, as);
- cse_not_expected = old_cse_not_expected;
- seq = get_insns ();
- end_sequence ();
-
- acost = seq_cost (seq, speed);
- acost += address_cost (addr, mem_mode, as, speed);
-
- if (!acost)
- acost = 1;
- data->costs[sym_p][var_p][off_p][rat_p] = acost;
- }
-
- /* On some targets, it is quite expensive to load symbol to a register,
- which makes addresses that contain symbols look much more expensive.
- However, the symbol will have to be loaded in any case before the
- loop (and quite likely we have it in register already), so it does not
- make much sense to penalize them too heavily. So make some final
- tweaks for the SYMBOL_PRESENT modes:
-
- If VAR_PRESENT is false, and the mode obtained by changing symbol to
- var is cheaper, use this mode with small penalty.
- If VAR_PRESENT is true, try whether the mode with
- SYMBOL_PRESENT = false is cheaper even with cost of addition, and
- if this is the case, use it. */
- add_c = add_cost (speed, address_mode);
- for (i = 0; i < 8; i++)
- {
- var_p = i & 1;
- off_p = (i >> 1) & 1;
- rat_p = (i >> 2) & 1;
-
- acost = data->costs[0][1][off_p][rat_p] + 1;
- if (var_p)
- acost += add_c;
-
- if (acost < data->costs[1][var_p][off_p][rat_p])
- data->costs[1][var_p][off_p][rat_p] = acost;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "<Address Costs>:\n");
-
- for (i = 0; i < 16; i++)
- {
- sym_p = i & 1;
- var_p = (i >> 1) & 1;
- off_p = (i >> 2) & 1;
- rat_p = (i >> 3) & 1;
-
- fprintf (dump_file, " ");
- if (sym_p)
- fprintf (dump_file, "sym + ");
- if (var_p)
- fprintf (dump_file, "var + ");
- if (off_p)
- fprintf (dump_file, "cst + ");
- if (rat_p)
- fprintf (dump_file, "rat * ");
-
- acost = data->costs[sym_p][var_p][off_p][rat_p];
- fprintf (dump_file, "index costs %d\n", acost);
- }
- if (has_predec[mem_mode] || has_postdec[mem_mode]
- || has_preinc[mem_mode] || has_postinc[mem_mode])
- fprintf (dump_file, " May include autoinc/dec\n");
- fprintf (dump_file, "\n");
- }
-
- address_cost_data_list[data_index] = data;
- }
-
- bits = GET_MODE_BITSIZE (address_mode);
- mask = ~(HOST_WIDE_INT_M1U << (bits - 1) << 1);
- offset &= mask;
- if ((offset >> (bits - 1) & 1))
- offset |= ~mask;
- s_offset = offset;
-
- autoinc = false;
- autoinc_type = AINC_NONE;
- msize = GET_MODE_SIZE (mem_mode);
- autoinc_offset = offset;
- if (stmt_after_inc)
- autoinc_offset += ratio * cstep;
- if (symbol_present || var_present || ratio != 1)
- autoinc = false;
- else
+ if (cost == INFTY)
+ return cost;
+ else if (optimize_loop_for_speed_p (data->current_loop))
{
- if (has_postinc[mem_mode] && autoinc_offset == 0
- && msize == cstep)
- autoinc_type = AINC_POST_INC;
- else if (has_postdec[mem_mode] && autoinc_offset == 0
- && msize == -cstep)
- autoinc_type = AINC_POST_DEC;
- else if (has_preinc[mem_mode] && autoinc_offset == msize
- && msize == cstep)
- autoinc_type = AINC_PRE_INC;
- else if (has_predec[mem_mode] && autoinc_offset == -msize
- && msize == -cstep)
- autoinc_type = AINC_PRE_DEC;
-
- if (autoinc_type != AINC_NONE)
- autoinc = true;
- }
-
- cost = 0;
- offset_p = (s_offset != 0
- && data->min_offset <= s_offset
- && s_offset <= data->max_offset);
- ratio_p = (ratio != 1
- && multiplier_allowed_in_address_p (ratio, mem_mode, as));
-
- if (ratio != 1 && !ratio_p)
- cost += mult_by_coeff_cost (ratio, address_mode, speed);
-
- if (s_offset && !offset_p && !symbol_present)
- cost += add_cost (speed, address_mode);
-
- if (may_autoinc)
- *may_autoinc = autoinc;
- if (autoinc)
- acost = data->ainc_costs[autoinc_type];
+ int64_t niters = (int64_t) avg_loop_niter (data->current_loop);
+ return (cost + (round_up_p ? niters - 1 : 0)) / niters;
+ }
else
- acost = data->costs[symbol_present][var_present][offset_p][ratio_p];
- complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
- return comp_cost (cost + acost, complexity);
+ return cost;
}
- /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
- EXPR operand holding the shift. COST0 and COST1 are the costs for
- calculating the operands of EXPR. Returns true if successful, and returns
- the cost in COST. */
+/* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
+ EXPR operand holding the shift. COST0 and COST1 are the costs for
+ calculating the operands of EXPR. Returns true if successful, and returns
+ the cost in COST. */
static bool
-get_shiftadd_cost (tree expr, machine_mode mode, comp_cost cost0,
+get_shiftadd_cost (tree expr, scalar_int_mode mode, comp_cost cost0,
comp_cost cost1, tree mult, bool speed, comp_cost *cost)
{
comp_cost res;
tree op0, op1;
comp_cost cost0, cost1, cost;
machine_mode mode;
+ scalar_int_mode int_mode;
if (!costs_initialized)
{
if (is_gimple_min_invariant (expr))
{
- if (TREE_CODE (expr) == INTEGER_CST)
+ if (poly_int_tree_p (expr))
return comp_cost (integer_cost [speed], 0);
if (TREE_CODE (expr) == ADDR_EXPR)
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
+ case TRUNC_DIV_EXPR:
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ case LSHIFT_EXPR:
+ case RSHIFT_EXPR:
op0 = TREE_OPERAND (expr, 0);
op1 = TREE_OPERAND (expr, 1);
STRIP_NOPS (op0);
CASE_CONVERT:
case NEGATE_EXPR:
+ case BIT_NOT_EXPR:
op0 = TREE_OPERAND (expr, 0);
STRIP_NOPS (op0);
op1 = NULL_TREE;
break;
+ /* See add_iv_candidate_for_doloop, for doloop may_be_zero case, we
+ introduce COND_EXPR for IV base, need to support better cost estimation
+ for this COND_EXPR and tcc_comparison. */
+ case COND_EXPR:
+ op0 = TREE_OPERAND (expr, 1);
+ STRIP_NOPS (op0);
+ op1 = TREE_OPERAND (expr, 2);
+ STRIP_NOPS (op1);
+ break;
+ case LT_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ case EQ_EXPR:
+ case NE_EXPR:
+ case UNORDERED_EXPR:
+ case ORDERED_EXPR:
+ case UNLT_EXPR:
+ case UNLE_EXPR:
+ case UNGT_EXPR:
+ case UNGE_EXPR:
+ case UNEQ_EXPR:
+ case LTGT_EXPR:
+ case MAX_EXPR:
+ case MIN_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ STRIP_NOPS (op0);
+ op1 = TREE_OPERAND (expr, 1);
+ STRIP_NOPS (op1);
+ break;
default:
/* Just an arbitrary value, FIXME. */
mult = op0;
if (mult != NULL_TREE
+ && is_a <scalar_int_mode> (mode, &int_mode)
&& cst_and_fits_in_hwi (TREE_OPERAND (mult, 1))
- && get_shiftadd_cost (expr, mode, cost0, cost1, mult,
+ && get_shiftadd_cost (expr, int_mode, cost0, cost1, mult,
speed, &sa_cost))
return sa_cost;
}
return comp_cost (target_spill_cost [speed], 0);
break;
+ case TRUNC_DIV_EXPR:
+ /* Division by power of two is usually cheap, so we allow it. Forbid
+ anything else. */
+ if (integer_pow2p (TREE_OPERAND (expr, 1)))
+ cost = comp_cost (add_cost (speed, mode), 0);
+ else
+ cost = comp_cost (target_spill_cost[speed], 0);
+ break;
+
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ case BIT_NOT_EXPR:
+ case LSHIFT_EXPR:
+ case RSHIFT_EXPR:
+ cost = comp_cost (add_cost (speed, mode), 0);
+ break;
+ case COND_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ STRIP_NOPS (op0);
+ if (op0 == NULL_TREE || TREE_CODE (op0) == SSA_NAME
+ || CONSTANT_CLASS_P (op0))
+ cost = no_cost;
+ else
+ cost = force_expr_to_var_cost (op0, speed);
+ break;
+ case LT_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ case EQ_EXPR:
+ case NE_EXPR:
+ case UNORDERED_EXPR:
+ case ORDERED_EXPR:
+ case UNLT_EXPR:
+ case UNLE_EXPR:
+ case UNGT_EXPR:
+ case UNGE_EXPR:
+ case UNEQ_EXPR:
+ case LTGT_EXPR:
+ case MAX_EXPR:
+ case MIN_EXPR:
+ /* Simply use add cost for now, FIXME if there is some more accurate cost
+ evaluation way. */
+ cost = comp_cost (add_cost (speed, mode), 0);
+ break;
+
default:
gcc_unreachable ();
}
cost += cost0;
- cost += cost1;
-
- /* Bound the cost by target_spill_cost. The parts of complicated
- computations often are either loop invariant or at least can
- be shared between several iv uses, so letting this grow without
- limits would not give reasonable results. */
- if (cost.cost > (int) target_spill_cost [speed])
- cost.cost = target_spill_cost [speed];
-
- return cost;
-}
-
-/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
- invariants the computation depends on. */
-
-static comp_cost
-force_var_cost (struct ivopts_data *data,
- tree expr, bitmap *depends_on)
-{
- if (depends_on)
- {
- fd_ivopts_data = data;
- walk_tree (&expr, find_depends, depends_on, NULL);
- }
-
- return force_expr_to_var_cost (expr, data->speed);
-}
-
-/* Estimates cost of expressing address ADDR as var + symbol + offset. The
- value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
- to false if the corresponding part is missing. DEPENDS_ON is a set of the
- invariants the computation depends on. */
-
-static comp_cost
-split_address_cost (struct ivopts_data *data,
- tree addr, bool *symbol_present, bool *var_present,
- unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
-{
- tree core;
- HOST_WIDE_INT bitsize;
- HOST_WIDE_INT bitpos;
- tree toffset;
- machine_mode mode;
- int unsignedp, reversep, volatilep;
-
- core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
- &unsignedp, &reversep, &volatilep);
-
- if (toffset != 0
- || bitpos % BITS_PER_UNIT != 0
- || reversep
- || !VAR_P (core))
- {
- *symbol_present = false;
- *var_present = true;
- fd_ivopts_data = data;
- if (depends_on)
- walk_tree (&addr, find_depends, depends_on, NULL);
-
- return comp_cost (target_spill_cost[data->speed], 0);
- }
-
- *offset += bitpos / BITS_PER_UNIT;
- if (TREE_STATIC (core)
- || DECL_EXTERNAL (core))
- {
- *symbol_present = true;
- *var_present = false;
- return no_cost;
- }
-
- *symbol_present = false;
- *var_present = true;
- return no_cost;
-}
-
-/* Estimates cost of expressing difference of addresses E1 - E2 as
- var + symbol + offset. The value of offset is added to OFFSET,
- SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
- part is missing. DEPENDS_ON is a set of the invariants the computation
- depends on. */
-
-static comp_cost
-ptr_difference_cost (struct ivopts_data *data,
- tree e1, tree e2, bool *symbol_present, bool *var_present,
- unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
-{
- HOST_WIDE_INT diff = 0;
- aff_tree aff_e1, aff_e2;
- tree type;
-
- gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
-
- if (ptr_difference_const (e1, e2, &diff))
- {
- *offset += diff;
- *symbol_present = false;
- *var_present = false;
- return no_cost;
- }
-
- if (integer_zerop (e2))
- return split_address_cost (data, TREE_OPERAND (e1, 0),
- symbol_present, var_present, offset, depends_on);
-
- *symbol_present = false;
- *var_present = true;
-
- type = signed_type_for (TREE_TYPE (e1));
- tree_to_aff_combination (e1, type, &aff_e1);
- tree_to_aff_combination (e2, type, &aff_e2);
- aff_combination_scale (&aff_e2, -1);
- aff_combination_add (&aff_e1, &aff_e2);
-
- return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
-}
-
-/* Estimates cost of expressing difference E1 - E2 as
- var + symbol + offset. The value of offset is added to OFFSET,
- SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
- part is missing. DEPENDS_ON is a set of the invariants the computation
- depends on. */
-
-static comp_cost
-difference_cost (struct ivopts_data *data,
- tree e1, tree e2, bool *symbol_present, bool *var_present,
- unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
-{
- machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
- unsigned HOST_WIDE_INT off1, off2;
- aff_tree aff_e1, aff_e2;
- tree type;
-
- e1 = strip_offset (e1, &off1);
- e2 = strip_offset (e2, &off2);
- *offset += off1 - off2;
-
- STRIP_NOPS (e1);
- STRIP_NOPS (e2);
-
- if (TREE_CODE (e1) == ADDR_EXPR)
- return ptr_difference_cost (data, e1, e2, symbol_present, var_present,
- offset, depends_on);
- *symbol_present = false;
-
- if (operand_equal_p (e1, e2, 0))
- {
- *var_present = false;
- return no_cost;
- }
-
- *var_present = true;
-
- if (integer_zerop (e2))
- return force_var_cost (data, e1, depends_on);
-
- if (integer_zerop (e1))
- {
- comp_cost cost = force_var_cost (data, e2, depends_on);
- cost += mult_by_coeff_cost (-1, mode, data->speed);
- return cost;
- }
-
- type = signed_type_for (TREE_TYPE (e1));
- tree_to_aff_combination (e1, type, &aff_e1);
- tree_to_aff_combination (e2, type, &aff_e2);
- aff_combination_scale (&aff_e2, -1);
- aff_combination_add (&aff_e1, &aff_e2);
-
- return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
-}
-
-/* Returns true if AFF1 and AFF2 are identical. */
-
-static bool
-compare_aff_trees (aff_tree *aff1, aff_tree *aff2)
-{
- unsigned i;
-
- if (aff1->n != aff2->n)
- return false;
-
- for (i = 0; i < aff1->n; i++)
- {
- if (aff1->elts[i].coef != aff2->elts[i].coef)
- return false;
-
- if (!operand_equal_p (aff1->elts[i].val, aff2->elts[i].val, 0))
- return false;
- }
- return true;
+ cost += cost1;
+ return cost;
}
-/* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent. */
+/* Estimates cost of forcing EXPR into a variable. INV_VARS is a set of the
+ invariants the computation depends on. */
-static iv_inv_expr_ent *
-record_inv_expr (struct ivopts_data *data, tree expr)
+static comp_cost
+force_var_cost (struct ivopts_data *data, tree expr, bitmap *inv_vars)
{
- struct iv_inv_expr_ent ent;
- struct iv_inv_expr_ent **slot;
-
- ent.expr = expr;
- ent.hash = iterative_hash_expr (expr, 0);
- slot = data->inv_expr_tab->find_slot (&ent, INSERT);
-
- if (!*slot)
- {
- *slot = XNEW (struct iv_inv_expr_ent);
- (*slot)->expr = expr;
- (*slot)->hash = ent.hash;
- (*slot)->id = data->max_inv_expr_id++;
- }
+ if (!expr)
+ return no_cost;
- return *slot;
+ find_inv_vars (data, &expr, inv_vars);
+ return force_expr_to_var_cost (expr, data->speed);
}
-/* Returns the invariant expression if expression UBASE - RATIO * CBASE
- requires a new compiler generated temporary. Returns -1 otherwise.
- ADDRESS_P is a flag indicating if the expression is for address
- computation. */
+/* Returns cost of auto-modifying address expression in shape base + offset.
+ AINC_STEP is step size of the address IV. AINC_OFFSET is offset of the
+ address expression. The address expression has ADDR_MODE in addr space
+ AS. The memory access has MEM_MODE. SPEED means we are optimizing for
+ speed or size. */
-static iv_inv_expr_ent *
-get_loop_invariant_expr (struct ivopts_data *data, tree ubase,
- tree cbase, HOST_WIDE_INT ratio,
- bool address_p)
+enum ainc_type
{
- aff_tree ubase_aff, cbase_aff;
- tree expr, ub, cb;
+ AINC_PRE_INC, /* Pre increment. */
+ AINC_PRE_DEC, /* Pre decrement. */
+ AINC_POST_INC, /* Post increment. */
+ AINC_POST_DEC, /* Post decrement. */
+ AINC_NONE /* Also the number of auto increment types. */
+};
- STRIP_NOPS (ubase);
- STRIP_NOPS (cbase);
- ub = ubase;
- cb = cbase;
+struct ainc_cost_data
+{
+ int64_t costs[AINC_NONE];
+};
- if ((TREE_CODE (ubase) == INTEGER_CST)
- && (TREE_CODE (cbase) == INTEGER_CST))
- return NULL;
+static comp_cost
+get_address_cost_ainc (poly_int64 ainc_step, poly_int64 ainc_offset,
+ machine_mode addr_mode, machine_mode mem_mode,
+ addr_space_t as, bool speed)
+{
+ if (!USE_LOAD_PRE_DECREMENT (mem_mode)
+ && !USE_STORE_PRE_DECREMENT (mem_mode)
+ && !USE_LOAD_POST_DECREMENT (mem_mode)
+ && !USE_STORE_POST_DECREMENT (mem_mode)
+ && !USE_LOAD_PRE_INCREMENT (mem_mode)
+ && !USE_STORE_PRE_INCREMENT (mem_mode)
+ && !USE_LOAD_POST_INCREMENT (mem_mode)
+ && !USE_STORE_POST_INCREMENT (mem_mode))
+ return infinite_cost;
- /* Strips the constant part. */
- if (TREE_CODE (ubase) == PLUS_EXPR
- || TREE_CODE (ubase) == MINUS_EXPR
- || TREE_CODE (ubase) == POINTER_PLUS_EXPR)
+ static vec<ainc_cost_data *> ainc_cost_data_list;
+ unsigned idx = (unsigned) as * MAX_MACHINE_MODE + (unsigned) mem_mode;
+ if (idx >= ainc_cost_data_list.length ())
{
- if (TREE_CODE (TREE_OPERAND (ubase, 1)) == INTEGER_CST)
- ubase = TREE_OPERAND (ubase, 0);
- }
+ unsigned nsize = ((unsigned) as + 1) *MAX_MACHINE_MODE;
- /* Strips the constant part. */
- if (TREE_CODE (cbase) == PLUS_EXPR
- || TREE_CODE (cbase) == MINUS_EXPR
- || TREE_CODE (cbase) == POINTER_PLUS_EXPR)
- {
- if (TREE_CODE (TREE_OPERAND (cbase, 1)) == INTEGER_CST)
- cbase = TREE_OPERAND (cbase, 0);
+ gcc_assert (nsize > idx);
+ ainc_cost_data_list.safe_grow_cleared (nsize, true);
}
- if (address_p)
+ ainc_cost_data *data = ainc_cost_data_list[idx];
+ if (data == NULL)
{
- if (((TREE_CODE (ubase) == SSA_NAME)
- || (TREE_CODE (ubase) == ADDR_EXPR
- && is_gimple_min_invariant (ubase)))
- && (TREE_CODE (cbase) == INTEGER_CST))
- return NULL;
+ rtx reg = gen_raw_REG (addr_mode, LAST_VIRTUAL_REGISTER + 1);
- if (((TREE_CODE (cbase) == SSA_NAME)
- || (TREE_CODE (cbase) == ADDR_EXPR
- && is_gimple_min_invariant (cbase)))
- && (TREE_CODE (ubase) == INTEGER_CST))
- return NULL;
+ data = (ainc_cost_data *) xcalloc (1, sizeof (*data));
+ data->costs[AINC_PRE_DEC] = INFTY;
+ data->costs[AINC_POST_DEC] = INFTY;
+ data->costs[AINC_PRE_INC] = INFTY;
+ data->costs[AINC_POST_INC] = INFTY;
+ if (USE_LOAD_PRE_DECREMENT (mem_mode)
+ || USE_STORE_PRE_DECREMENT (mem_mode))
+ {
+ rtx addr = gen_rtx_PRE_DEC (addr_mode, reg);
+
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ data->costs[AINC_PRE_DEC]
+ = address_cost (addr, mem_mode, as, speed);
+ }
+ if (USE_LOAD_POST_DECREMENT (mem_mode)
+ || USE_STORE_POST_DECREMENT (mem_mode))
+ {
+ rtx addr = gen_rtx_POST_DEC (addr_mode, reg);
+
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ data->costs[AINC_POST_DEC]
+ = address_cost (addr, mem_mode, as, speed);
+ }
+ if (USE_LOAD_PRE_INCREMENT (mem_mode)
+ || USE_STORE_PRE_INCREMENT (mem_mode))
+ {
+ rtx addr = gen_rtx_PRE_INC (addr_mode, reg);
+
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ data->costs[AINC_PRE_INC]
+ = address_cost (addr, mem_mode, as, speed);
+ }
+ if (USE_LOAD_POST_INCREMENT (mem_mode)
+ || USE_STORE_POST_INCREMENT (mem_mode))
+ {
+ rtx addr = gen_rtx_POST_INC (addr_mode, reg);
+
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ data->costs[AINC_POST_INC]
+ = address_cost (addr, mem_mode, as, speed);
+ }
+ ainc_cost_data_list[idx] = data;
}
- if (ratio == 1)
- {
- if (operand_equal_p (ubase, cbase, 0))
- return NULL;
+ poly_int64 msize = GET_MODE_SIZE (mem_mode);
+ if (known_eq (ainc_offset, 0) && known_eq (msize, ainc_step))
+ return comp_cost (data->costs[AINC_POST_INC], 0);
+ if (known_eq (ainc_offset, 0) && known_eq (msize, -ainc_step))
+ return comp_cost (data->costs[AINC_POST_DEC], 0);
+ if (known_eq (ainc_offset, msize) && known_eq (msize, ainc_step))
+ return comp_cost (data->costs[AINC_PRE_INC], 0);
+ if (known_eq (ainc_offset, -msize) && known_eq (msize, -ainc_step))
+ return comp_cost (data->costs[AINC_PRE_DEC], 0);
- if (TREE_CODE (ubase) == ADDR_EXPR
- && TREE_CODE (cbase) == ADDR_EXPR)
+ return infinite_cost;
+}
+
+/* Return cost of computing USE's address expression by using CAND.
+ AFF_INV and AFF_VAR represent invariant and variant parts of the
+ address expression, respectively. If AFF_INV is simple, store
+ the loop invariant variables which are depended by it in INV_VARS;
+ if AFF_INV is complicated, handle it as a new invariant expression
+ and record it in INV_EXPR. RATIO indicates multiple times between
+ steps of USE and CAND. If CAN_AUTOINC is nonNULL, store boolean
+ value to it indicating if this is an auto-increment address. */
+
+static comp_cost
+get_address_cost (struct ivopts_data *data, struct iv_use *use,
+ struct iv_cand *cand, aff_tree *aff_inv,
+ aff_tree *aff_var, HOST_WIDE_INT ratio,
+ bitmap *inv_vars, iv_inv_expr_ent **inv_expr,
+ bool *can_autoinc, bool speed)
+{
+ rtx addr;
+ bool simple_inv = true;
+ tree comp_inv = NULL_TREE, type = aff_var->type;
+ comp_cost var_cost = no_cost, cost = no_cost;
+ struct mem_address parts = {NULL_TREE, integer_one_node,
+ NULL_TREE, NULL_TREE, NULL_TREE};
+ machine_mode addr_mode = TYPE_MODE (type);
+ machine_mode mem_mode = TYPE_MODE (use->mem_type);
+ addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (use->iv->base));
+ /* Only true if ratio != 1. */
+ bool ok_with_ratio_p = false;
+ bool ok_without_ratio_p = false;
+
+ if (!aff_combination_const_p (aff_inv))
+ {
+ parts.index = integer_one_node;
+ /* Addressing mode "base + index". */
+ ok_without_ratio_p = valid_mem_ref_p (mem_mode, as, &parts);
+ if (ratio != 1)
+ {
+ parts.step = wide_int_to_tree (type, ratio);
+ /* Addressing mode "base + index << scale". */
+ ok_with_ratio_p = valid_mem_ref_p (mem_mode, as, &parts);
+ if (!ok_with_ratio_p)
+ parts.step = NULL_TREE;
+ }
+ if (ok_with_ratio_p || ok_without_ratio_p)
{
- tree usym, csym;
+ if (maybe_ne (aff_inv->offset, 0))
+ {
+ parts.offset = wide_int_to_tree (sizetype, aff_inv->offset);
+ /* Addressing mode "base + index [<< scale] + offset". */
+ if (!valid_mem_ref_p (mem_mode, as, &parts))
+ parts.offset = NULL_TREE;
+ else
+ aff_inv->offset = 0;
+ }
- usym = TREE_OPERAND (ubase, 0);
- csym = TREE_OPERAND (cbase, 0);
- if (TREE_CODE (usym) == ARRAY_REF)
+ move_fixed_address_to_symbol (&parts, aff_inv);
+ /* Base is fixed address and is moved to symbol part. */
+ if (parts.symbol != NULL_TREE && aff_combination_zero_p (aff_inv))
+ parts.base = NULL_TREE;
+
+ /* Addressing mode "symbol + base + index [<< scale] [+ offset]". */
+ if (parts.symbol != NULL_TREE
+ && !valid_mem_ref_p (mem_mode, as, &parts))
{
- tree ind = TREE_OPERAND (usym, 1);
- if (TREE_CODE (ind) == INTEGER_CST
- && tree_fits_shwi_p (ind)
- && tree_to_shwi (ind) == 0)
- usym = TREE_OPERAND (usym, 0);
+ aff_combination_add_elt (aff_inv, parts.symbol, 1);
+ parts.symbol = NULL_TREE;
+ /* Reset SIMPLE_INV since symbol address needs to be computed
+ outside of address expression in this case. */
+ simple_inv = false;
+ /* Symbol part is moved back to base part, it can't be NULL. */
+ parts.base = integer_one_node;
}
- if (TREE_CODE (csym) == ARRAY_REF)
+ }
+ else
+ parts.index = NULL_TREE;
+ }
+ else
+ {
+ poly_int64 ainc_step;
+ if (can_autoinc
+ && ratio == 1
+ && ptrdiff_tree_p (cand->iv->step, &ainc_step))
+ {
+ poly_int64 ainc_offset = (aff_inv->offset).force_shwi ();
+
+ if (stmt_after_increment (data->current_loop, cand, use->stmt))
+ ainc_offset += ainc_step;
+ cost = get_address_cost_ainc (ainc_step, ainc_offset,
+ addr_mode, mem_mode, as, speed);
+ if (!cost.infinite_cost_p ())
{
- tree ind = TREE_OPERAND (csym, 1);
- if (TREE_CODE (ind) == INTEGER_CST
- && tree_fits_shwi_p (ind)
- && tree_to_shwi (ind) == 0)
- csym = TREE_OPERAND (csym, 0);
+ *can_autoinc = true;
+ return cost;
}
- if (operand_equal_p (usym, csym, 0))
- return NULL;
+ cost = no_cost;
+ }
+ if (!aff_combination_zero_p (aff_inv))
+ {
+ parts.offset = wide_int_to_tree (sizetype, aff_inv->offset);
+ /* Addressing mode "base + offset". */
+ if (!valid_mem_ref_p (mem_mode, as, &parts))
+ parts.offset = NULL_TREE;
+ else
+ aff_inv->offset = 0;
}
- /* Now do more complex comparison */
- tree_to_aff_combination (ubase, TREE_TYPE (ubase), &ubase_aff);
- tree_to_aff_combination (cbase, TREE_TYPE (cbase), &cbase_aff);
- if (compare_aff_trees (&ubase_aff, &cbase_aff))
- return NULL;
}
- tree_to_aff_combination (ub, TREE_TYPE (ub), &ubase_aff);
- tree_to_aff_combination (cb, TREE_TYPE (cb), &cbase_aff);
+ if (simple_inv)
+ simple_inv = (aff_inv == NULL
+ || aff_combination_const_p (aff_inv)
+ || aff_combination_singleton_var_p (aff_inv));
+ if (!aff_combination_zero_p (aff_inv))
+ comp_inv = aff_combination_to_tree (aff_inv);
+ if (comp_inv != NULL_TREE)
+ cost = force_var_cost (data, comp_inv, inv_vars);
+ if (ratio != 1 && parts.step == NULL_TREE)
+ var_cost += mult_by_coeff_cost (ratio, addr_mode, speed);
+ if (comp_inv != NULL_TREE && parts.index == NULL_TREE)
+ var_cost += add_cost (speed, addr_mode);
+
+ if (comp_inv && inv_expr && !simple_inv)
+ {
+ *inv_expr = get_loop_invariant_expr (data, comp_inv);
+ /* Clear depends on. */
+ if (*inv_expr != NULL && inv_vars && *inv_vars)
+ bitmap_clear (*inv_vars);
+
+ /* Cost of small invariant expression adjusted against loop niters
+ is usually zero, which makes it difficult to be differentiated
+ from candidate based on loop invariant variables. Secondly, the
+ generated invariant expression may not be hoisted out of loop by
+ following pass. We penalize the cost by rounding up in order to
+ neutralize such effects. */
+ cost.cost = adjust_setup_cost (data, cost.cost, true);
+ cost.scratch = cost.cost;
+ }
+
+ cost += var_cost;
+ addr = addr_for_mem_ref (&parts, as, false);
+ gcc_assert (memory_address_addr_space_p (mem_mode, addr, as));
+ cost += address_cost (addr, mem_mode, as, speed);
+
+ if (parts.symbol != NULL_TREE)
+ cost.complexity += 1;
+ /* Don't increase the complexity of adding a scaled index if it's
+ the only kind of index that the target allows. */
+ if (parts.step != NULL_TREE && ok_without_ratio_p)
+ cost.complexity += 1;
+ if (parts.base != NULL_TREE && parts.index != NULL_TREE)
+ cost.complexity += 1;
+ if (parts.offset != NULL_TREE && !integer_zerop (parts.offset))
+ cost.complexity += 1;
- aff_combination_scale (&cbase_aff, -1 * ratio);
- aff_combination_add (&ubase_aff, &cbase_aff);
- expr = aff_combination_to_tree (&ubase_aff);
- return record_inv_expr (data, expr);
+ return cost;
}
/* Scale (multiply) the computed COST (except scratch part that should be
- hoisted out a loop) by header->frequency / AT->frequency,
- which makes expected cost more accurate. */
+ hoisted out a loop) by header->frequency / AT->frequency, which makes
+ expected cost more accurate. */
static comp_cost
-get_scaled_computation_cost_at (ivopts_data *data, gimple *at, iv_cand *cand,
- comp_cost cost)
+get_scaled_computation_cost_at (ivopts_data *data, gimple *at, comp_cost cost)
{
- int loop_freq = data->current_loop->header->frequency;
- int bb_freq = gimple_bb (at)->frequency;
- if (loop_freq != 0)
- {
- gcc_assert (cost.scratch <= cost.cost);
- int scaled_cost
- = cost.scratch + (cost.cost - cost.scratch) * bb_freq / loop_freq;
+ if (data->speed
+ && data->current_loop->header->count.to_frequency (cfun) > 0)
+ {
+ basic_block bb = gimple_bb (at);
+ gcc_assert (cost.scratch <= cost.cost);
+ int scale_factor = (int)(intptr_t) bb->aux;
+ if (scale_factor == 1)
+ return cost;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Scaling iv_use based on cand %d "
- "by %2.2f: %d (scratch: %d) -> %d (%d/%d)\n",
- cand->id, 1.0f * bb_freq / loop_freq, cost.cost,
- cost.scratch, scaled_cost, bb_freq, loop_freq);
+ int64_t scaled_cost
+ = cost.scratch + (cost.cost - cost.scratch) * scale_factor;
- cost.cost = scaled_cost;
- }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Scaling cost based on bb prob by %2.2f: "
+ "%" PRId64 " (scratch: %" PRId64 ") -> %" PRId64 "\n",
+ 1.0f * scale_factor, cost.cost, cost.scratch, scaled_cost);
+
+ cost.cost = scaled_cost;
+ }
return cost;
}
/* Determines the cost of the computation by that USE is expressed
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
- register. A set of invariants we depend on is stored in
- DEPENDS_ON. AT is the statement at that the value is computed.
+ register. A set of invariants we depend on is stored in INV_VARS.
If CAN_AUTOINC is nonnull, use it to record whether autoinc
- addressing is likely. */
+ addressing is likely. If INV_EXPR is nonnull, record invariant
+ expr entry in it. */
static comp_cost
-get_computation_cost_at (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on, gimple *at,
- bool *can_autoinc,
- iv_inv_expr_ent **inv_expr)
+get_computation_cost (struct ivopts_data *data, struct iv_use *use,
+ struct iv_cand *cand, bool address_p, bitmap *inv_vars,
+ bool *can_autoinc, iv_inv_expr_ent **inv_expr)
{
- tree ubase = use->iv->base, ustep = use->iv->step;
- tree cbase, cstep;
- tree utype = TREE_TYPE (ubase), ctype;
- unsigned HOST_WIDE_INT cstepi, offset = 0;
+ gimple *at = use->stmt;
+ tree ubase = use->iv->base, cbase = cand->iv->base;
+ tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+ tree comp_inv = NULL_TREE;
HOST_WIDE_INT ratio, aratio;
- bool var_present, symbol_present, stmt_is_after_inc;
comp_cost cost;
widest_int rat;
+ aff_tree aff_inv, aff_var;
bool speed = optimize_bb_for_speed_p (gimple_bb (at));
- machine_mode mem_mode = (address_p
- ? TYPE_MODE (TREE_TYPE (*use->op_p))
- : VOIDmode);
- if (depends_on)
- *depends_on = NULL;
-
- /* Only consider real candidates. */
- if (!cand->iv)
- return infinite_cost;
-
- cbase = cand->iv->base;
- cstep = cand->iv->step;
- ctype = TREE_TYPE (cbase);
+ if (inv_vars)
+ *inv_vars = NULL;
+ if (can_autoinc)
+ *can_autoinc = false;
+ if (inv_expr)
+ *inv_expr = NULL;
+ /* Check if we have enough precision to express the values of use. */
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
- {
- /* We do not have a precision to express the values of use. */
- return infinite_cost;
- }
+ return infinite_cost;
if (address_p
|| (use->iv->base_object
return infinite_cost;
}
- if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
- {
- /* TODO -- add direct handling of this case. */
- goto fallback;
- }
-
- /* CSTEPI is removed from the offset in case statement is after the
- increment. If the step is not constant, we use zero instead.
- This is a bit imprecise (there is the extra addition), but
- redundancy elimination is likely to transform the code so that
- it uses value of the variable before increment anyway,
- so it is not that much unrealistic. */
- if (cst_and_fits_in_hwi (cstep))
- cstepi = int_cst_value (cstep);
- else
- cstepi = 0;
-
- if (!constant_multiple_of (ustep, cstep, &rat))
- return infinite_cost;
-
- if (wi::fits_shwi_p (rat))
- ratio = rat.to_shwi ();
- else
+ if (!get_computation_aff_1 (data->current_loop, at, use,
+ cand, &aff_inv, &aff_var, &rat)
+ || !wi::fits_shwi_p (rat))
return infinite_cost;
- STRIP_NOPS (cbase);
- ctype = TREE_TYPE (cbase);
-
- stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
-
- /* 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
-
- (also holds in the case ratio == -1, TODO. */
-
- if (cst_and_fits_in_hwi (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,
- depends_on);
- cost /= avg_loop_niter (data->current_loop);
- }
- else if (ratio == 1)
- {
- tree real_cbase = cbase;
-
- /* Check to see if any adjustment is needed. */
- if (cstepi == 0 && stmt_is_after_inc)
- {
- aff_tree real_cbase_aff;
- aff_tree cstep_aff;
-
- tree_to_aff_combination (cbase, TREE_TYPE (real_cbase),
- &real_cbase_aff);
- tree_to_aff_combination (cstep, TREE_TYPE (cstep), &cstep_aff);
-
- aff_combination_add (&real_cbase_aff, &cstep_aff);
- real_cbase = aff_combination_to_tree (&real_cbase_aff);
- }
-
- cost = difference_cost (data,
- ubase, real_cbase,
- &symbol_present, &var_present, &offset,
- depends_on);
- cost /= avg_loop_niter (data->current_loop);
- }
- else if (address_p
- && !POINTER_TYPE_P (ctype)
- && multiplier_allowed_in_address_p
- (ratio, mem_mode,
- TYPE_ADDR_SPACE (TREE_TYPE (utype))))
- {
- tree real_cbase = cbase;
-
- if (cstepi == 0 && stmt_is_after_inc)
- {
- if (POINTER_TYPE_P (ctype))
- real_cbase = fold_build2 (POINTER_PLUS_EXPR, ctype, cbase, cstep);
- else
- real_cbase = fold_build2 (PLUS_EXPR, ctype, cbase, cstep);
- }
- real_cbase = fold_build2 (MULT_EXPR, ctype, real_cbase,
- build_int_cst (ctype, ratio));
- cost = difference_cost (data,
- ubase, real_cbase,
- &symbol_present, &var_present, &offset,
- depends_on);
- cost /= avg_loop_niter (data->current_loop);
- }
- else
+ ratio = rat.to_shwi ();
+ if (address_p)
{
- cost = force_var_cost (data, cbase, depends_on);
- cost += difference_cost (data, ubase, build_int_cst (utype, 0),
- &symbol_present, &var_present, &offset,
- depends_on);
- cost /= avg_loop_niter (data->current_loop);
- cost += add_cost (data->speed, TYPE_MODE (ctype));
+ cost = get_address_cost (data, use, cand, &aff_inv, &aff_var, ratio,
+ inv_vars, inv_expr, can_autoinc, speed);
+ cost = get_scaled_computation_cost_at (data, at, cost);
+ /* For doloop IV cand, add on the extra cost. */
+ cost += cand->doloop_p ? targetm.doloop_cost_for_address : 0;
+ return cost;
}
- /* Record setup cost in scratch field. */
- cost.scratch = cost.cost;
+ bool simple_inv = (aff_combination_const_p (&aff_inv)
+ || aff_combination_singleton_var_p (&aff_inv));
+ tree signed_type = signed_type_for (aff_combination_type (&aff_inv));
+ aff_combination_convert (&aff_inv, signed_type);
+ if (!aff_combination_zero_p (&aff_inv))
+ comp_inv = aff_combination_to_tree (&aff_inv);
- if (inv_expr && depends_on && *depends_on)
+ cost = force_var_cost (data, comp_inv, inv_vars);
+ if (comp_inv && inv_expr && !simple_inv)
{
- *inv_expr = get_loop_invariant_expr (data, ubase, cbase, ratio,
- address_p);
+ *inv_expr = get_loop_invariant_expr (data, comp_inv);
/* Clear depends on. */
- if (*inv_expr != NULL)
- bitmap_clear (*depends_on);
- }
+ if (*inv_expr != NULL && inv_vars && *inv_vars)
+ bitmap_clear (*inv_vars);
- /* If we are after the increment, the value of the candidate is higher by
- one iteration. */
- if (stmt_is_after_inc)
- offset -= ratio * cstepi;
-
- /* Now the computation is in shape symbol + var1 + const + ratio * var2.
- (symbol/var1/const parts may be omitted). If we are looking for an
- address, find the cost of addressing this. */
- if (address_p)
- {
- cost += get_address_cost (symbol_present, var_present,
- offset, ratio, cstepi,
- mem_mode,
- TYPE_ADDR_SPACE (TREE_TYPE (utype)),
- speed, stmt_is_after_inc, can_autoinc);
- return get_scaled_computation_cost_at (data, at, cand, cost);
+ cost.cost = adjust_setup_cost (data, cost.cost);
+ /* Record setup cost in scratch field. */
+ cost.scratch = cost.cost;
}
+ /* Cost of constant integer can be covered when adding invariant part to
+ variant part. */
+ else if (comp_inv && CONSTANT_CLASS_P (comp_inv))
+ cost = no_cost;
- /* Otherwise estimate the costs for computing the expression. */
- if (!symbol_present && !var_present && !offset)
+ /* Need type narrowing to represent use with cand. */
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
- if (ratio != 1)
- cost += mult_by_coeff_cost (ratio, TYPE_MODE (ctype), speed);
- return get_scaled_computation_cost_at (data, at, cand, cost);
+ machine_mode outer_mode = TYPE_MODE (utype);
+ machine_mode inner_mode = TYPE_MODE (ctype);
+ cost += comp_cost (convert_cost (outer_mode, inner_mode, speed), 0);
}
- /* Symbol + offset should be compile-time computable so consider that they
- are added once to the variable, if present. */
- if (var_present && (symbol_present || offset))
- cost += adjust_setup_cost (data,
- add_cost (speed, TYPE_MODE (ctype)));
-
- /* Having offset does not affect runtime cost in case it is added to
- symbol, but it increases complexity. */
- if (offset)
- cost.complexity++;
-
- cost += add_cost (speed, TYPE_MODE (ctype));
-
- aratio = ratio > 0 ? ratio : -ratio;
- if (aratio != 1)
- cost += mult_by_coeff_cost (aratio, TYPE_MODE (ctype), speed);
-
- return get_scaled_computation_cost_at (data, at, cand, cost);
-
-fallback:
- if (can_autoinc)
- *can_autoinc = false;
-
- /* Just get the expression, expand it and measure the cost. */
- tree comp = get_computation_at (data->current_loop, use, cand, at);
-
- if (!comp)
- return infinite_cost;
+ /* Turn a + i * (-c) into a - i * c. */
+ if (ratio < 0 && comp_inv && !integer_zerop (comp_inv))
+ aratio = -ratio;
+ else
+ aratio = ratio;
- if (address_p)
- comp = build_simple_mem_ref (comp);
+ if (ratio != 1)
+ cost += mult_by_coeff_cost (aratio, TYPE_MODE (utype), speed);
- cost = comp_cost (computation_cost (comp, speed), 0);
+ /* TODO: We may also need to check if we can compute a + i * 4 in one
+ instruction. */
+ /* Need to add up the invariant and variant parts. */
+ if (comp_inv && !integer_zerop (comp_inv))
+ cost += add_cost (speed, TYPE_MODE (utype));
- return get_scaled_computation_cost_at (data, at, cand, cost);
-}
+ cost = get_scaled_computation_cost_at (data, at, cost);
-/* Determines the cost of the computation by that USE is expressed
- from induction variable CAND. If ADDRESS_P is true, we just need
- to create an address from it, otherwise we want to get it into
- register. A set of invariants we depend on is stored in
- DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
- autoinc addressing is likely. */
+ /* For doloop IV cand, add on the extra cost. */
+ if (cand->doloop_p && use->type == USE_NONLINEAR_EXPR)
+ cost += targetm.doloop_cost_for_generic;
-static comp_cost
-get_computation_cost (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on,
- bool *can_autoinc, iv_inv_expr_ent **inv_expr)
-{
- return get_computation_cost_at (data,
- use, cand, address_p, depends_on, use->stmt,
- can_autoinc, inv_expr);
+ return cost;
}
/* Determines cost of computing the use in GROUP with CAND in a generic
{
comp_cost cost;
iv_inv_expr_ent *inv_expr = NULL;
- bitmap depends_on = NULL;
+ bitmap inv_vars = NULL, inv_exprs = NULL;
struct iv_use *use = group->vuses[0];
/* The simple case first -- if we need to express value of the preserved
cost = no_cost;
else
cost = get_computation_cost (data, use, cand, false,
- &depends_on, NULL, &inv_expr);
+ &inv_vars, NULL, &inv_expr);
- set_group_iv_cost (data, group, cand, cost, depends_on,
- NULL_TREE, ERROR_MARK, inv_expr);
+ if (inv_expr)
+ {
+ inv_exprs = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (inv_exprs, inv_expr->id);
+ }
+ set_group_iv_cost (data, group, cand, cost, inv_vars,
+ NULL_TREE, ERROR_MARK, inv_exprs);
return !cost.infinite_cost_p ();
}
struct iv_group *group, struct iv_cand *cand)
{
unsigned i;
- bitmap depends_on;
+ bitmap inv_vars = NULL, inv_exprs = NULL;
bool can_autoinc;
iv_inv_expr_ent *inv_expr = NULL;
struct iv_use *use = group->vuses[0];
comp_cost sum_cost = no_cost, cost;
cost = get_computation_cost (data, use, cand, true,
- &depends_on, &can_autoinc, &inv_expr);
+ &inv_vars, &can_autoinc, &inv_expr);
+ if (inv_expr)
+ {
+ inv_exprs = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (inv_exprs, inv_expr->id);
+ }
sum_cost = cost;
if (!sum_cost.infinite_cost_p () && cand->ainc_use == use)
{
same cost as the first iv_use, but the cost really depends on the
offset and where the iv_use is. */
cost = get_computation_cost (data, next, cand, true,
- NULL, &can_autoinc, NULL);
+ NULL, &can_autoinc, &inv_expr);
+ if (inv_expr)
+ {
+ if (!inv_exprs)
+ inv_exprs = BITMAP_ALLOC (NULL);
+
+ bitmap_set_bit (inv_exprs, inv_expr->id);
+ }
sum_cost += cost;
}
- set_group_iv_cost (data, group, cand, sum_cost, depends_on,
- NULL_TREE, ERROR_MARK, inv_expr);
+ set_group_iv_cost (data, group, cand, sum_cost, inv_vars,
+ NULL_TREE, ERROR_MARK, inv_exprs);
return !sum_cost.infinite_cost_p ();
}
stores it to VAL. */
static void
-cand_value_at (struct loop *loop, struct iv_cand *cand, gimple *at, tree niter,
+cand_value_at (class loop *loop, struct iv_cand *cand, gimple *at, tree niter,
aff_tree *val)
{
aff_tree step, delta, nit;
static enum tree_code
iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
{
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
basic_block ex_bb;
edge exit;
static bool
iv_elimination_compare_lt (struct ivopts_data *data,
struct iv_cand *cand, enum tree_code *comp_p,
- struct tree_niter_desc *niter)
+ class tree_niter_desc *niter)
{
tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset;
- struct aff_tree nit, tmpa, tmpb;
+ class aff_tree nit, tmpa, tmpb;
enum tree_code comp;
HOST_WIDE_INT step;
aff_combination_scale (&tmpa, -1);
aff_combination_add (&tmpb, &tmpa);
aff_combination_add (&tmpb, &nit);
- if (tmpb.n != 0 || tmpb.offset != 1)
+ if (tmpb.n != 0 || maybe_ne (tmpb.offset, 1))
return false;
/* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
basic_block ex_bb;
edge exit;
tree period;
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
aff_tree bnd;
- struct tree_niter_desc *desc = NULL;
+ class tree_niter_desc *desc = NULL;
if (TREE_CODE (cand->iv->step) != INTEGER_CST)
return false;
}
}
+ /* For doloop IV cand, the bound would be zero. It's safe whether
+ may_be_zero set or not. */
+ if (cand->doloop_p)
+ {
+ *bound = build_int_cst (TREE_TYPE (cand->iv->base), 0);
+ *comp = iv_elimination_compare (data, use);
+ return true;
+ }
+
cand_value_at (loop, cand, use->stmt, desc->niter, &bnd);
*bound = fold_convert (TREE_TYPE (cand->iv->base),
return false;
/* Sometimes, it is possible to handle the situation that the number of
- iterations may be zero unless additional assumtions by using <
+ iterations may be zero unless additional assumptions by using <
instead of != in the exit condition.
TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
{
tree bound = NULL_TREE;
struct iv *cmp_iv;
- bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
- comp_cost elim_cost, express_cost, cost, bound_cost;
- bool ok;
- iv_inv_expr_ent *elim_inv_expr = NULL, *express_inv_expr = NULL, *inv_expr;
+ bitmap inv_exprs = NULL;
+ bitmap inv_vars_elim = NULL, inv_vars_express = NULL, inv_vars;
+ comp_cost elim_cost = infinite_cost, express_cost, cost, bound_cost;
+ enum comp_iv_rewrite rewrite_type;
+ iv_inv_expr_ent *inv_expr_elim = NULL, *inv_expr_express = NULL, *inv_expr;
tree *control_var, *bound_cst;
enum tree_code comp = ERROR_MARK;
struct iv_use *use = group->vuses[0];
- gcc_assert (cand->iv);
+ /* Extract condition operands. */
+ rewrite_type = extract_cond_operands (data, use->stmt, &control_var,
+ &bound_cst, NULL, &cmp_iv);
+ gcc_assert (rewrite_type != COMP_IV_NA);
/* Try iv elimination. */
- if (may_eliminate_iv (data, use, cand, &bound, &comp))
+ if (rewrite_type == COMP_IV_ELIM
+ && may_eliminate_iv (data, use, cand, &bound, &comp))
{
- elim_cost = force_var_cost (data, bound, &depends_on_elim);
+ elim_cost = force_var_cost (data, bound, &inv_vars_elim);
if (elim_cost.cost == 0)
elim_cost.cost = parm_decl_cost (data, bound);
else if (TREE_CODE (bound) == INTEGER_CST)
elim_cost.cost = 0;
/* If we replace a loop condition 'i < n' with 'p < base + n',
- depends_on_elim will have 'base' and 'n' set, which implies
- that both 'base' and 'n' will be live during the loop. More likely,
+ inv_vars_elim will have 'base' and 'n' set, which implies that both
+ 'base' and 'n' will be live during the loop. More likely,
'base + n' will be loop invariant, resulting in only one live value
- during the loop. So in that case we clear depends_on_elim and set
- elim_inv_expr_id instead. */
- if (depends_on_elim && bitmap_count_bits (depends_on_elim) > 1)
+ during the loop. So in that case we clear inv_vars_elim and set
+ inv_expr_elim instead. */
+ if (inv_vars_elim && bitmap_count_bits (inv_vars_elim) > 1)
{
- elim_inv_expr = record_inv_expr (data, bound);
- bitmap_clear (depends_on_elim);
+ inv_expr_elim = get_loop_invariant_expr (data, bound);
+ bitmap_clear (inv_vars_elim);
}
/* The bound is a loop invariant, so it will be only computed
once. */
elim_cost.cost = adjust_setup_cost (data, elim_cost.cost);
}
- else
- elim_cost = infinite_cost;
-
- /* Try expressing the original giv. If it is compared with an invariant,
- note that we cannot get rid of it. */
- ok = extract_cond_operands (data, use->stmt, &control_var, &bound_cst,
- NULL, &cmp_iv);
- gcc_assert (ok);
/* When the condition is a comparison of the candidate IV against
zero, prefer this IV.
elim_cost -= 1;
express_cost = get_computation_cost (data, use, cand, false,
- &depends_on_express, NULL,
- &express_inv_expr);
- fd_ivopts_data = data;
- walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
+ &inv_vars_express, NULL,
+ &inv_expr_express);
+ if (cmp_iv != NULL)
+ find_inv_vars (data, &cmp_iv->base, &inv_vars_express);
/* Count the cost of the original bound as well. */
bound_cost = force_var_cost (data, *bound_cst, NULL);
if (elim_cost <= express_cost)
{
cost = elim_cost;
- depends_on = depends_on_elim;
- depends_on_elim = NULL;
- inv_expr = elim_inv_expr;
+ inv_vars = inv_vars_elim;
+ inv_vars_elim = NULL;
+ inv_expr = inv_expr_elim;
+ /* For doloop candidate/use pair, adjust to zero cost. */
+ if (group->doloop_p && cand->doloop_p && elim_cost.cost > no_cost.cost)
+ cost = no_cost;
}
else
{
cost = express_cost;
- depends_on = depends_on_express;
- depends_on_express = NULL;
+ inv_vars = inv_vars_express;
+ inv_vars_express = NULL;
bound = NULL_TREE;
comp = ERROR_MARK;
- inv_expr = express_inv_expr;
+ inv_expr = inv_expr_express;
}
+ if (inv_expr)
+ {
+ inv_exprs = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (inv_exprs, inv_expr->id);
+ }
set_group_iv_cost (data, group, cand, cost,
- depends_on, bound, comp, inv_expr);
+ inv_vars, bound, comp, inv_exprs);
- if (depends_on_elim)
- BITMAP_FREE (depends_on_elim);
- if (depends_on_express)
- BITMAP_FREE (depends_on_express);
+ if (inv_vars_elim)
+ BITMAP_FREE (inv_vars_elim);
+ if (inv_vars_express)
+ BITMAP_FREE (inv_vars_express);
return !cost.infinite_cost_p ();
}
case USE_NONLINEAR_EXPR:
return determine_group_iv_cost_generic (data, group, cand);
- case USE_ADDRESS:
+ case USE_REF_ADDRESS:
+ case USE_PTR_ADDRESS:
return determine_group_iv_cost_address (data, group, cand);
case USE_COMPARE:
autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use,
struct iv_cand *cand)
{
- bitmap depends_on;
- bool can_autoinc;
- comp_cost cost;
-
- if (use->type != USE_ADDRESS)
+ if (!address_p (use->type))
return false;
- cost = get_computation_cost (data, use, cand, true, &depends_on,
- &can_autoinc, NULL);
+ bool can_autoinc = false;
+ get_computation_cost (data, use, cand, true, NULL, &can_autoinc, NULL);
+ return can_autoinc;
+}
+
+/* Examine IP_ORIGINAL candidates to see if they are incremented next to a
+ use that allows autoincrement, and set their AINC_USE if possible. */
+
+static void
+set_autoinc_for_original_candidates (struct ivopts_data *data)
+{
+ unsigned i, j;
+
+ for (i = 0; i < data->vcands.length (); i++)
+ {
+ struct iv_cand *cand = data->vcands[i];
+ struct iv_use *closest_before = NULL;
+ struct iv_use *closest_after = NULL;
+ if (cand->pos != IP_ORIGINAL)
+ continue;
+
+ for (j = 0; j < data->vgroups.length (); j++)
+ {
+ struct iv_group *group = data->vgroups[j];
+ struct iv_use *use = group->vuses[0];
+ unsigned uid = gimple_uid (use->stmt);
+
+ if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at))
+ continue;
+
+ if (uid < gimple_uid (cand->incremented_at)
+ && (closest_before == NULL
+ || uid > gimple_uid (closest_before->stmt)))
+ closest_before = use;
+
+ if (uid > gimple_uid (cand->incremented_at)
+ && (closest_after == NULL
+ || uid < gimple_uid (closest_after->stmt)))
+ closest_after = use;
+ }
+
+ if (closest_before != NULL
+ && autoinc_possible_for_pair (data, closest_before, cand))
+ cand->ainc_use = closest_before;
+ else if (closest_after != NULL
+ && autoinc_possible_for_pair (data, closest_after, cand))
+ cand->ainc_use = closest_after;
+ }
+}
+
+/* Relate compare use with all candidates. */
+
+static void
+relate_compare_use_with_all_cands (struct ivopts_data *data)
+{
+ unsigned i, count = data->vcands.length ();
+ for (i = 0; i < data->vgroups.length (); i++)
+ {
+ struct iv_group *group = data->vgroups[i];
+
+ if (group->type == USE_COMPARE)
+ bitmap_set_range (group->related_cands, 0, count);
+ }
+}
+
+/* If PREFERRED_MODE is suitable and profitable, use the preferred
+ PREFERRED_MODE to compute doloop iv base from niter: base = niter + 1. */
+
+static tree
+compute_doloop_base_on_mode (machine_mode preferred_mode, tree niter,
+ const widest_int &iterations_max)
+{
+ tree ntype = TREE_TYPE (niter);
+ tree pref_type = lang_hooks.types.type_for_mode (preferred_mode, 1);
+ if (!pref_type)
+ return fold_build2 (PLUS_EXPR, ntype, unshare_expr (niter),
+ build_int_cst (ntype, 1));
+
+ gcc_assert (TREE_CODE (pref_type) == INTEGER_TYPE);
+
+ int prec = TYPE_PRECISION (ntype);
+ int pref_prec = TYPE_PRECISION (pref_type);
- BITMAP_FREE (depends_on);
+ tree base;
+
+ /* Check if the PREFERRED_MODED is able to present niter. */
+ if (pref_prec > prec
+ || wi::ltu_p (iterations_max,
+ widest_int::from (wi::max_value (pref_prec, UNSIGNED),
+ UNSIGNED)))
+ {
+ /* No wrap, it is safe to use preferred type after niter + 1. */
+ if (wi::ltu_p (iterations_max,
+ widest_int::from (wi::max_value (prec, UNSIGNED),
+ UNSIGNED)))
+ {
+ /* This could help to optimize "-1 +1" pair when niter looks
+ like "n-1": n is in original mode. "base = (n - 1) + 1"
+ in PREFERRED_MODED: it could be base = (PREFERRED_TYPE)n. */
+ base = fold_build2 (PLUS_EXPR, ntype, unshare_expr (niter),
+ build_int_cst (ntype, 1));
+ base = fold_convert (pref_type, base);
+ }
- return !cost.infinite_cost_p () && can_autoinc;
+ /* To avoid wrap, convert niter to preferred type before plus 1. */
+ else
+ {
+ niter = fold_convert (pref_type, niter);
+ base = fold_build2 (PLUS_EXPR, pref_type, unshare_expr (niter),
+ build_int_cst (pref_type, 1));
+ }
+ }
+ else
+ base = fold_build2 (PLUS_EXPR, ntype, unshare_expr (niter),
+ build_int_cst (ntype, 1));
+ return base;
}
-/* Examine IP_ORIGINAL candidates to see if they are incremented next to a
- use that allows autoincrement, and set their AINC_USE if possible. */
+/* Add one doloop dedicated IV candidate:
+ - Base is (may_be_zero ? 1 : (niter + 1)).
+ - Step is -1. */
static void
-set_autoinc_for_original_candidates (struct ivopts_data *data)
+add_iv_candidate_for_doloop (struct ivopts_data *data)
{
- unsigned i, j;
+ tree_niter_desc *niter_desc = niter_for_single_dom_exit (data);
+ gcc_assert (niter_desc && niter_desc->assumptions);
- for (i = 0; i < data->vcands.length (); i++)
- {
- struct iv_cand *cand = data->vcands[i];
- struct iv_use *closest_before = NULL;
- struct iv_use *closest_after = NULL;
- if (cand->pos != IP_ORIGINAL)
- continue;
+ tree niter = niter_desc->niter;
+ tree ntype = TREE_TYPE (niter);
+ gcc_assert (TREE_CODE (ntype) == INTEGER_TYPE);
- for (j = 0; j < data->vgroups.length (); j++)
+ tree may_be_zero = niter_desc->may_be_zero;
+ if (may_be_zero && integer_zerop (may_be_zero))
+ may_be_zero = NULL_TREE;
+ if (may_be_zero)
+ {
+ if (COMPARISON_CLASS_P (may_be_zero))
{
- struct iv_group *group = data->vgroups[j];
- struct iv_use *use = group->vuses[0];
- unsigned uid = gimple_uid (use->stmt);
+ niter = fold_build3 (COND_EXPR, ntype, may_be_zero,
+ build_int_cst (ntype, 0),
+ rewrite_to_non_trapping_overflow (niter));
+ }
+ /* Don't try to obtain the iteration count expression when may_be_zero is
+ integer_nonzerop (actually iteration count is one) or else. */
+ else
+ return;
+ }
- if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at))
- continue;
+ machine_mode mode = TYPE_MODE (ntype);
+ machine_mode pref_mode = targetm.preferred_doloop_mode (mode);
- if (uid < gimple_uid (cand->incremented_at)
- && (closest_before == NULL
- || uid > gimple_uid (closest_before->stmt)))
- closest_before = use;
+ tree base;
+ if (mode != pref_mode)
+ {
+ base = compute_doloop_base_on_mode (pref_mode, niter, niter_desc->max);
+ ntype = TREE_TYPE (base);
+ }
+ else
+ base = fold_build2 (PLUS_EXPR, ntype, unshare_expr (niter),
+ build_int_cst (ntype, 1));
- if (uid > gimple_uid (cand->incremented_at)
- && (closest_after == NULL
- || uid < gimple_uid (closest_after->stmt)))
- closest_after = use;
- }
- if (closest_before != NULL
- && autoinc_possible_for_pair (data, closest_before, cand))
- cand->ainc_use = closest_before;
- else if (closest_after != NULL
- && autoinc_possible_for_pair (data, closest_after, cand))
- cand->ainc_use = closest_after;
- }
+ add_candidate (data, base, build_int_cst (ntype, -1), true, NULL, NULL, true);
}
/* Finds the candidates for the induction variables. */
/* Add commonly used ivs. */
add_standard_iv_candidates (data);
+ /* Add doloop dedicated ivs. */
+ if (data->doloop_use_p)
+ add_iv_candidate_for_doloop (data);
+
/* Add old induction variables. */
add_iv_candidate_for_bivs (data);
/* Record the important candidates. */
record_important_candidates (data);
+ /* Relate compare iv_use with all candidates. */
+ if (!data->consider_all_candidates)
+ relate_compare_use_with_all_cands (data);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
unsigned i;
if (dump_file && (dump_flags & TDF_DETAILS))
{
+ bitmap_iterator bi;
+
+ /* Dump invariant variables. */
+ fprintf (dump_file, "\n<Invariant Vars>:\n");
+ EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
+ {
+ struct version_info *info = ver_info (data, i);
+ if (info->inv_id)
+ {
+ fprintf (dump_file, "Inv %d:\t", info->inv_id);
+ print_generic_expr (dump_file, info->name, TDF_SLIM);
+ fprintf (dump_file, "%s\n",
+ info->has_nonlin_use ? "" : "\t(eliminable)");
+ }
+ }
+
+ /* Dump invariant expressions. */
fprintf (dump_file, "\n<Invariant Expressions>:\n");
auto_vec <iv_inv_expr_ent *> list (data->inv_expr_tab->elements ());
for (i = 0; i < list.length (); ++i)
{
- fprintf (dump_file, "inv_expr %d: \t", i);
+ fprintf (dump_file, "inv_expr %d: \t", list[i]->id);
print_generic_expr (dump_file, list[i]->expr, TDF_SLIM);
fprintf (dump_file, "\n");
}
group = data->vgroups[i];
fprintf (dump_file, "Group %d:\n", i);
- fprintf (dump_file, " cand\tcost\tcompl.\tinv.ex.\tdepends on\n");
+ fprintf (dump_file, " cand\tcost\tcompl.\tinv.expr.\tinv.vars\n");
for (j = 0; j < group->n_map_members; j++)
{
if (!group->cost_map[j].cand
|| group->cost_map[j].cost.infinite_cost_p ())
continue;
- fprintf (dump_file, " %d\t%d\t%d\t",
+ fprintf (dump_file, " %d\t%" PRId64 "\t%d\t",
group->cost_map[j].cand->id,
group->cost_map[j].cost.cost,
group->cost_map[j].cost.complexity);
- if (group->cost_map[j].inv_expr != NULL)
- fprintf (dump_file, "%d\t",
- group->cost_map[j].inv_expr->id);
+ if (!group->cost_map[j].inv_exprs
+ || bitmap_empty_p (group->cost_map[j].inv_exprs))
+ fprintf (dump_file, "NIL;\t");
else
- fprintf (dump_file, "\t");
- if (group->cost_map[j].depends_on)
bitmap_print (dump_file,
- group->cost_map[j].depends_on, "","");
- fprintf (dump_file, "\n");
+ group->cost_map[j].inv_exprs, "", ";\t");
+ if (!group->cost_map[j].inv_vars
+ || bitmap_empty_p (group->cost_map[j].inv_vars))
+ fprintf (dump_file, "NIL;\n");
+ else
+ bitmap_print (dump_file,
+ group->cost_map[j].inv_vars, "", "\n");
}
fprintf (dump_file, "\n");
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
comp_cost cost_base;
- unsigned cost, cost_step;
+ int64_t cost, cost_step;
tree base;
- if (!cand->iv)
- {
- cand->cost = 0;
- return;
- }
+ gcc_assert (cand->iv != NULL);
/* There are two costs associated with the candidate -- its increment
and its initialization. The second is almost negligible for any loop
or a const set. */
if (cost_base.cost == 0)
cost_base.cost = COSTS_N_INSNS (1);
- cost_step = add_cost (data->speed, TYPE_MODE (TREE_TYPE (base)));
-
+ /* Doloop decrement should be considered as zero cost. */
+ if (cand->doloop_p)
+ cost_step = 0;
+ else
+ cost_step = add_cost (data->speed, TYPE_MODE (TREE_TYPE (base)));
cost = cost_step + adjust_setup_cost (data, cost_base.cost);
/* Prefer the original ivs unless we may gain something by replacing it.
The reason is to make debugging simpler; so this is not relevant for
artificial ivs created by other optimization passes. */
- if (cand->pos != IP_ORIGINAL
- || !SSA_NAME_VAR (cand->var_before)
- || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
+ if ((cand->pos != IP_ORIGINAL
+ || !SSA_NAME_VAR (cand->var_before)
+ || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
+ /* Prefer doloop as well. */
+ && !cand->doloop_p)
cost++;
/* Prefer not to insert statements into latch unless there are some
fprintf (dump_file, "\n");
}
-/* Calculates cost for having SIZE induction variables. */
+/* Estimate register pressure for loop having N_INVS invariants and N_CANDS
+ induction variables. Note N_INVS includes both invariant variables and
+ invariant expressions. */
static unsigned
-ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
+ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs,
+ unsigned n_cands)
{
- /* We add size to the cost, so that we prefer eliminating ivs
- if possible. */
- return size + estimate_reg_pressure_cost (size, data->regs_used, data->speed,
- data->body_includes_call);
+ unsigned cost;
+ unsigned n_old = data->regs_used, n_new = n_invs + n_cands;
+ unsigned regs_needed = n_new + n_old, available_regs = target_avail_regs;
+ bool speed = data->speed;
+
+ /* If there is a call in the loop body, the call-clobbered registers
+ are not available for loop invariants. */
+ if (data->body_includes_call)
+ available_regs = available_regs - target_clobbered_regs;
+
+ /* If we have enough registers. */
+ if (regs_needed + target_res_regs < available_regs)
+ cost = n_new;
+ /* If close to running out of registers, try to preserve them. */
+ else if (regs_needed <= available_regs)
+ cost = target_reg_cost [speed] * regs_needed;
+ /* If we run out of available registers but the number of candidates
+ does not, we penalize extra registers using target_spill_cost. */
+ else if (n_cands <= available_regs)
+ cost = target_reg_cost [speed] * available_regs
+ + target_spill_cost [speed] * (regs_needed - available_regs);
+ /* If the number of candidates runs out available registers, we penalize
+ extra candidate registers using target_spill_cost * 2. Because it is
+ more expensive to spill induction variable than invariant. */
+ else
+ cost = target_reg_cost [speed] * available_regs
+ + target_spill_cost [speed] * (n_cands - available_regs) * 2
+ + target_spill_cost [speed] * (regs_needed - n_cands);
+
+ /* Finally, add the number of candidates, so that we prefer eliminating
+ induction variables if possible. */
+ return cost + n_cands;
}
/* For each size of the induction variable set determine the penalty. */
gphi *phi;
gphi_iterator psi;
tree op;
- struct loop *loop = data->current_loop;
+ class loop *loop = data->current_loop;
bitmap_iterator bi;
if (dump_file && (dump_flags & TDF_DETAILS))
if (get_iv (data, op))
continue;
+ if (!POINTER_TYPE_P (TREE_TYPE (op))
+ && !INTEGRAL_TYPE_P (TREE_TYPE (op)))
+ continue;
+
n++;
}
fprintf (dump_file, " ivs\tcost\n");
for (j = 0; j <= 2 * target_avail_regs; j++)
fprintf (dump_file, " %d\t%d\n", j,
- ivopts_global_cost_for_size (data, j));
+ ivopts_estimate_reg_pressure (data, 0, j));
fprintf (dump_file, "\n");
}
}
/* Returns true if A is a cheaper cost pair than B. */
static bool
-cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
+cheaper_cost_pair (class cost_pair *a, class cost_pair *b)
{
if (!a)
return false;
return false;
}
+/* Compare if A is a more expensive cost pair than B. Return 1, 0 and -1
+ for more expensive, equal and cheaper respectively. */
+
+static int
+compare_cost_pair (class cost_pair *a, class cost_pair *b)
+{
+ if (cheaper_cost_pair (a, b))
+ return -1;
+ if (cheaper_cost_pair (b, a))
+ return 1;
+
+ return 0;
+}
/* Returns candidate by that USE is expressed in IVS. */
-static struct cost_pair *
-iv_ca_cand_for_group (struct iv_ca *ivs, struct iv_group *group)
+static class cost_pair *
+iv_ca_cand_for_group (class iv_ca *ivs, struct iv_group *group)
{
return ivs->cand_for_group[group->id];
}
/* Computes the cost field of IVS structure. */
static void
-iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
+iv_ca_recount_cost (struct ivopts_data *data, class iv_ca *ivs)
{
comp_cost cost = ivs->cand_use_cost;
cost += ivs->cand_cost;
-
- cost += ivopts_global_cost_for_size (data,
- ivs->n_regs
- + ivs->used_inv_exprs->elements ());
-
+ cost += ivopts_estimate_reg_pressure (data, ivs->n_invs, ivs->n_cands);
ivs->cost = cost;
}
-/* Remove invariants in set INVS to set IVS. */
+/* Remove use of invariants in set INVS by decreasing counter in N_INV_USES
+ and IVS. */
static void
-iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
+iv_ca_set_remove_invs (class iv_ca *ivs, bitmap invs, unsigned *n_inv_uses)
{
bitmap_iterator bi;
unsigned iid;
if (!invs)
return;
+ gcc_assert (n_inv_uses != NULL);
EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
{
- ivs->n_invariant_uses[iid]--;
- if (ivs->n_invariant_uses[iid] == 0)
- ivs->n_regs--;
+ n_inv_uses[iid]--;
+ if (n_inv_uses[iid] == 0)
+ ivs->n_invs--;
}
}
/* 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,
+iv_ca_set_no_cp (struct ivopts_data *data, class iv_ca *ivs,
struct iv_group *group)
{
unsigned gid = group->id, cid;
- struct cost_pair *cp;
+ class cost_pair *cp;
cp = ivs->cand_for_group[gid];
if (!cp)
if (ivs->n_cand_uses[cid] == 0)
{
bitmap_clear_bit (ivs->cands, cid);
- /* Do not count the pseudocandidates. */
- if (cp->cand->iv)
- ivs->n_regs--;
- ivs->n_cands--;
+ if (!cp->cand->doloop_p || !targetm.have_count_reg_decr_p)
+ ivs->n_cands--;
ivs->cand_cost -= cp->cand->cost;
-
- iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
+ iv_ca_set_remove_invs (ivs, cp->cand->inv_vars, ivs->n_inv_var_uses);
+ iv_ca_set_remove_invs (ivs, cp->cand->inv_exprs, ivs->n_inv_expr_uses);
}
ivs->cand_use_cost -= cp->cost;
-
- iv_ca_set_remove_invariants (ivs, cp->depends_on);
-
- if (cp->inv_expr != NULL)
- {
- unsigned *slot = ivs->used_inv_exprs->get (cp->inv_expr);
- --(*slot);
- if (*slot == 0)
- ivs->used_inv_exprs->remove (cp->inv_expr);
- }
+ iv_ca_set_remove_invs (ivs, cp->inv_vars, ivs->n_inv_var_uses);
+ iv_ca_set_remove_invs (ivs, cp->inv_exprs, ivs->n_inv_expr_uses);
iv_ca_recount_cost (data, ivs);
}
-/* Add invariants in set INVS to set IVS. */
+/* Add use of invariants in set INVS by increasing counter in N_INV_USES and
+ IVS. */
static void
-iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
+iv_ca_set_add_invs (class iv_ca *ivs, bitmap invs, unsigned *n_inv_uses)
{
bitmap_iterator bi;
unsigned iid;
if (!invs)
return;
+ gcc_assert (n_inv_uses != NULL);
EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
{
- ivs->n_invariant_uses[iid]++;
- if (ivs->n_invariant_uses[iid] == 1)
- ivs->n_regs++;
+ n_inv_uses[iid]++;
+ if (n_inv_uses[iid] == 1)
+ ivs->n_invs++;
}
}
/* Set cost pair for GROUP in set IVS to CP. */
static void
-iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_group *group, struct cost_pair *cp)
+iv_ca_set_cp (struct ivopts_data *data, class iv_ca *ivs,
+ struct iv_group *group, class cost_pair *cp)
{
unsigned gid = group->id, cid;
if (ivs->n_cand_uses[cid] == 1)
{
bitmap_set_bit (ivs->cands, cid);
- /* Do not count the pseudocandidates. */
- if (cp->cand->iv)
- ivs->n_regs++;
- ivs->n_cands++;
+ if (!cp->cand->doloop_p || !targetm.have_count_reg_decr_p)
+ ivs->n_cands++;
ivs->cand_cost += cp->cand->cost;
-
- iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
+ iv_ca_set_add_invs (ivs, cp->cand->inv_vars, ivs->n_inv_var_uses);
+ iv_ca_set_add_invs (ivs, cp->cand->inv_exprs, ivs->n_inv_expr_uses);
}
ivs->cand_use_cost += cp->cost;
- iv_ca_set_add_invariants (ivs, cp->depends_on);
-
- if (cp->inv_expr != NULL)
- {
- unsigned *slot = &ivs->used_inv_exprs->get_or_insert (cp->inv_expr);
- ++(*slot);
- }
+ iv_ca_set_add_invs (ivs, cp->inv_vars, ivs->n_inv_var_uses);
+ iv_ca_set_add_invs (ivs, cp->inv_exprs, ivs->n_inv_expr_uses);
iv_ca_recount_cost (data, ivs);
}
}
set IVS don't give any result. */
static void
-iv_ca_add_group (struct ivopts_data *data, struct iv_ca *ivs,
+iv_ca_add_group (struct ivopts_data *data, class iv_ca *ivs,
struct iv_group *group)
{
- struct cost_pair *best_cp = NULL, *cp;
+ class cost_pair *best_cp = NULL, *cp;
bitmap_iterator bi;
unsigned i;
struct iv_cand *cand;
/* Get cost for assignment IVS. */
static comp_cost
-iv_ca_cost (struct iv_ca *ivs)
+iv_ca_cost (class iv_ca *ivs)
{
/* This was a conditional expression but it triggered a bug in
Sun C 5.5. */
return ivs->cost;
}
-/* Returns true if all dependences of CP are among invariants in IVS. */
+/* Compare if applying NEW_CP to GROUP for IVS introduces more invariants
+ than OLD_CP. Return 1, 0 and -1 for more, equal and fewer invariants
+ respectively. */
-static bool
-iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
+static int
+iv_ca_compare_deps (struct ivopts_data *data, class iv_ca *ivs,
+ struct iv_group *group, class cost_pair *old_cp,
+ class cost_pair *new_cp)
{
- unsigned i;
- bitmap_iterator bi;
-
- if (!cp->depends_on)
- return true;
+ gcc_assert (old_cp && new_cp && old_cp != new_cp);
+ unsigned old_n_invs = ivs->n_invs;
+ iv_ca_set_cp (data, ivs, group, new_cp);
+ unsigned new_n_invs = ivs->n_invs;
+ iv_ca_set_cp (data, ivs, group, old_cp);
- EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
- {
- if (ivs->n_invariant_uses[i] == 0)
- return false;
- }
-
- return true;
+ return new_n_invs > old_n_invs ? 1 : (new_n_invs < old_n_invs ? -1 : 0);
}
/* Creates change of expressing GROUP by NEW_CP instead of OLD_CP and chains
it before NEXT. */
static struct iv_ca_delta *
-iv_ca_delta_add (struct iv_group *group, struct cost_pair *old_cp,
- struct cost_pair *new_cp, struct iv_ca_delta *next)
+iv_ca_delta_add (struct iv_group *group, class cost_pair *old_cp,
+ class cost_pair *new_cp, struct iv_ca_delta *next)
{
struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
reverted instead. */
static void
-iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
+iv_ca_delta_commit (struct ivopts_data *data, class iv_ca *ivs,
struct iv_ca_delta *delta, bool forward)
{
- struct cost_pair *from, *to;
+ class cost_pair *from, *to;
struct iv_ca_delta *act;
if (!forward)
/* Returns true if CAND is used in IVS. */
static bool
-iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
+iv_ca_cand_used_p (class 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)
+iv_ca_n_cands (class iv_ca *ivs)
{
return ivs->n_cands;
}
/* Allocates new iv candidates assignment. */
-static struct iv_ca *
+static class iv_ca *
iv_ca_new (struct ivopts_data *data)
{
- struct iv_ca *nw = XNEW (struct iv_ca);
+ class iv_ca *nw = XNEW (class iv_ca);
nw->upto = 0;
nw->bad_groups = 0;
- nw->cand_for_group = XCNEWVEC (struct cost_pair *,
+ nw->cand_for_group = XCNEWVEC (class cost_pair *,
data->vgroups.length ());
nw->n_cand_uses = XCNEWVEC (unsigned, data->vcands.length ());
nw->cands = BITMAP_ALLOC (NULL);
nw->n_cands = 0;
- nw->n_regs = 0;
+ nw->n_invs = 0;
nw->cand_use_cost = no_cost;
nw->cand_cost = 0;
- nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
- nw->used_inv_exprs = new hash_map <iv_inv_expr_ent *, unsigned> (13);
+ nw->n_inv_var_uses = XCNEWVEC (unsigned, data->max_inv_var_id + 1);
+ nw->n_inv_expr_uses = XCNEWVEC (unsigned, data->max_inv_expr_id + 1);
nw->cost = no_cost;
return nw;
/* Free memory occupied by the set IVS. */
static void
-iv_ca_free (struct iv_ca **ivs)
+iv_ca_free (class iv_ca **ivs)
{
free ((*ivs)->cand_for_group);
free ((*ivs)->n_cand_uses);
BITMAP_FREE ((*ivs)->cands);
- free ((*ivs)->n_invariant_uses);
- delete ((*ivs)->used_inv_exprs);
+ free ((*ivs)->n_inv_var_uses);
+ free ((*ivs)->n_inv_expr_uses);
free (*ivs);
*ivs = NULL;
}
/* Dumps IVS to FILE. */
static void
-iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
+iv_ca_dump (struct ivopts_data *data, FILE *file, class iv_ca *ivs)
{
unsigned i;
comp_cost cost = iv_ca_cost (ivs);
- fprintf (file, " cost: %d (complexity %d)\n", cost.cost,
+ fprintf (file, " cost: %" PRId64 " (complexity %d)\n", cost.cost,
cost.complexity);
- fprintf (file, " cand_cost: %d\n cand_group_cost: %d (complexity %d)\n",
- ivs->cand_cost, ivs->cand_use_cost.cost,
- ivs->cand_use_cost.complexity);
+ fprintf (file, " reg_cost: %d\n",
+ ivopts_estimate_reg_pressure (data, ivs->n_invs, ivs->n_cands));
+ fprintf (file, " cand_cost: %" PRId64 "\n cand_group_cost: "
+ "%" PRId64 " (complexity %d)\n", ivs->cand_cost,
+ ivs->cand_use_cost.cost, ivs->cand_use_cost.complexity);
bitmap_print (file, ivs->cands, " candidates: ","\n");
for (i = 0; i < ivs->upto; i++)
{
struct iv_group *group = data->vgroups[i];
- struct cost_pair *cp = iv_ca_cand_for_group (ivs, group);
+ class cost_pair *cp = iv_ca_cand_for_group (ivs, group);
if (cp)
- fprintf (file, " group:%d --> iv_cand:%d, cost=(%d,%d)\n",
- group->id, cp->cand->id, cp->cost.cost,
- cp->cost.complexity);
+ fprintf (file, " group:%d --> iv_cand:%d, cost=("
+ "%" PRId64 ",%d)\n", group->id, cp->cand->id,
+ cp->cost.cost, cp->cost.complexity);
else
fprintf (file, " group:%d --> ??\n", group->id);
}
const char *pref = "";
fprintf (file, " invariant variables: ");
- for (i = 1; i <= data->max_inv_id; i++)
- if (ivs->n_invariant_uses[i])
+ for (i = 1; i <= data->max_inv_var_id; i++)
+ if (ivs->n_inv_var_uses[i])
{
fprintf (file, "%s%d", pref, i);
pref = ", ";
pref = "";
fprintf (file, "\n invariant expressions: ");
- for (hash_map<iv_inv_expr_ent *, unsigned>::iterator it
- = ivs->used_inv_exprs->begin (); it != ivs->used_inv_exprs->end (); ++it)
- {
- fprintf (file, "%s%d", pref, (*it).first->id);
+ for (i = 1; i <= data->max_inv_expr_id; i++)
+ if (ivs->n_inv_expr_uses[i])
+ {
+ fprintf (file, "%s%d", pref, i);
pref = ", ";
- }
+ }
fprintf (file, "\n\n");
}
the function will try to find a solution with mimimal iv candidates. */
static comp_cost
-iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
+iv_ca_extend (struct ivopts_data *data, class iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta,
unsigned *n_ivs, bool min_ncand)
{
unsigned i;
comp_cost cost;
struct iv_group *group;
- struct cost_pair *old_cp, *new_cp;
+ class cost_pair *old_cp, *new_cp;
*delta = NULL;
for (i = 0; i < ivs->upto; i++)
if (!new_cp)
continue;
- if (!min_ncand && !iv_ca_has_deps (ivs, new_cp))
- continue;
+ if (!min_ncand)
+ {
+ int cmp_invs = iv_ca_compare_deps (data, ivs, group, old_cp, new_cp);
+ /* Skip if new_cp depends on more invariants. */
+ if (cmp_invs > 0)
+ continue;
- if (!min_ncand && !cheaper_cost_pair (new_cp, old_cp))
- continue;
+ int cmp_cost = compare_cost_pair (new_cp, old_cp);
+ /* Skip if new_cp is not cheaper. */
+ if (cmp_cost > 0 || (cmp_cost == 0 && cmp_invs == 0))
+ continue;
+ }
*delta = iv_ca_delta_add (group, old_cp, new_cp, *delta);
}
the candidate with which we start narrowing. */
static comp_cost
-iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
+iv_ca_narrow (struct ivopts_data *data, class iv_ca *ivs,
struct iv_cand *cand, struct iv_cand *start,
struct iv_ca_delta **delta)
{
unsigned i, ci;
struct iv_group *group;
- struct cost_pair *old_cp, *new_cp, *cp;
+ class cost_pair *old_cp, *new_cp, *cp;
bitmap_iterator bi;
struct iv_cand *cnd;
comp_cost cost, best_cost, acost;
differences in DELTA. */
static comp_cost
-iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
+iv_ca_prune (struct ivopts_data *data, class iv_ca *ivs,
struct iv_cand *except_cand, struct iv_ca_delta **delta)
{
bitmap_iterator bi;
cheaper local cost for GROUP than BEST_CP. Return pointer to
the corresponding cost_pair, otherwise just return BEST_CP. */
-static struct cost_pair*
+static class cost_pair*
cheaper_cost_with_cand (struct ivopts_data *data, struct iv_group *group,
unsigned int cand_idx, struct iv_cand *old_cand,
- struct cost_pair *best_cp)
+ class cost_pair *best_cp)
{
struct iv_cand *cand;
- struct cost_pair *cp;
+ class cost_pair *cp;
gcc_assert (old_cand != NULL && best_cp != NULL);
if (cand_idx == old_cand->id)
candidate replacement in list DELTA. */
static comp_cost
-iv_ca_replace (struct ivopts_data *data, struct iv_ca *ivs,
+iv_ca_replace (struct ivopts_data *data, class iv_ca *ivs,
struct iv_ca_delta **delta)
{
bitmap_iterator bi, bj;
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;
+ class cost_pair *old_cp, *best_cp = NULL;
*delta = NULL;
orig_cost = iv_ca_cost (ivs);
based on any memory object. */
static bool
-try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
+try_add_cand_for (struct ivopts_data *data, class iv_ca *ivs,
struct iv_group *group, bool originalp)
{
comp_cost best_cost, act_cost;
bitmap_iterator bi;
struct iv_cand *cand;
struct iv_ca_delta *best_delta = NULL, *act_delta;
- struct cost_pair *cp;
+ class cost_pair *cp;
iv_ca_add_group (data, ivs, group);
best_cost = iv_ca_cost (ivs);
/* Finds an initial assignment of candidates to uses. */
-static struct iv_ca *
+static class iv_ca *
get_initial_solution (struct ivopts_data *data, bool originalp)
{
unsigned i;
- struct iv_ca *ivs = iv_ca_new (data);
+ class iv_ca *ivs = iv_ca_new (data);
for (i = 0; i < data->vgroups.length (); i++)
if (!try_add_cand_for (data, ivs, data->vgroups[i], originalp))
static bool
try_improve_iv_set (struct ivopts_data *data,
- struct iv_ca *ivs, bool *try_replace_p)
+ class iv_ca *ivs, bool *try_replace_p)
{
unsigned i, n_ivs;
comp_cost acost, best_cost = iv_ca_cost (ivs);
}
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;
+ return best_cost == iv_ca_cost (ivs);
}
/* Attempts to find the optimal set of induction variables. We do simple
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 struct iv_ca *
+static class iv_ca *
find_optimal_iv_set_1 (struct ivopts_data *data, bool originalp)
{
- struct iv_ca *set;
+ class iv_ca *set;
bool try_replace_p = true;
/* Get the initial solution. */
}
}
+ /* If the set has infinite_cost, it can't be optimal. */
+ if (iv_ca_cost (set).infinite_cost_p ())
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Overflow to infinite cost in try_improve_iv_set.\n");
+ iv_ca_free (&set);
+ }
return set;
}
-static struct iv_ca *
+static class iv_ca *
find_optimal_iv_set (struct ivopts_data *data)
{
unsigned i;
comp_cost cost, origcost;
- struct iv_ca *set, *origset;
+ class iv_ca *set, *origset;
/* Determine the cost based on a strategy that starts with original IVs,
and try again using a strategy that prefers candidates not based
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "Original cost %d (complexity %d)\n\n",
+ fprintf (dump_file, "Original cost %" PRId64 " (complexity %d)\n\n",
origcost.cost, origcost.complexity);
- fprintf (dump_file, "Final cost %d (complexity %d)\n\n",
+ fprintf (dump_file, "Final cost %" PRId64 " (complexity %d)\n\n",
cost.cost, cost.complexity);
}
struct iv_group *group;
bool after = false;
- if (!cand->iv)
- return;
+ gcc_assert (cand->iv != NULL);
switch (cand->pos)
{
/* Creates new induction variables described in SET. */
static void
-create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
+create_new_ivs (struct ivopts_data *data, class iv_ca *set)
{
unsigned i;
struct iv_cand *cand;
LOCATION_LINE (data->loop_loc));
fprintf (dump_file, ", " HOST_WIDE_INT_PRINT_DEC " avg niters",
avg_loop_niter (data->current_loop));
- fprintf (dump_file, ", " HOST_WIDE_INT_PRINT_UNSIGNED " expressions",
- (unsigned HOST_WIDE_INT) set->used_inv_exprs->elements ());
fprintf (dump_file, ", %lu IVs:\n", bitmap_count_bits (set->cands));
EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
{
rewrite_use_nonlinear_expr (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp;
- tree op, tgt;
gassign *ass;
gimple_stmt_iterator bsi;
+ tree comp, type = get_use_type (use), tgt;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
+ tree op = NULL_TREE;
enum tree_code stmt_code;
gcc_assert (is_gimple_assign (use->stmt));
op = gimple_assign_rhs2 (use->stmt);
else if (gimple_assign_rhs2 (use->stmt) == cand->var_before)
op = gimple_assign_rhs1 (use->stmt);
- else
- op = NULL_TREE;
}
- else
- op = NULL_TREE;
- if (op && expr_invariant_in_loop_p (data->current_loop, op))
- return;
+ if (op != NULL_TREE)
+ {
+ if (expr_invariant_in_loop_p (data->current_loop, op))
+ return;
+ if (TREE_CODE (op) == SSA_NAME)
+ {
+ struct iv *iv = get_iv (data, op);
+ if (iv != NULL && integer_zerop (iv->step))
+ return;
+ }
+ }
}
- comp = get_computation (data->current_loop, use, cand);
- gcc_assert (comp != NULL_TREE);
-
switch (gimple_code (use->stmt))
{
case GIMPLE_PHI:
gcc_unreachable ();
}
- if (!valid_gimple_rhs_p (comp)
- || (gimple_code (use->stmt) != GIMPLE_PHI
- /* We can't allow re-allocating the stmt as it might be pointed
- to still. */
- && (get_gimple_rhs_num_ops (TREE_CODE (comp))
- >= gimple_num_ops (gsi_stmt (bsi)))))
+ aff_tree aff_inv, aff_var;
+ if (!get_computation_aff_1 (data->current_loop, use->stmt,
+ use, cand, &aff_inv, &aff_var))
+ gcc_unreachable ();
+
+ unshare_aff_combination (&aff_inv);
+ unshare_aff_combination (&aff_var);
+ /* Prefer CSE opportunity than loop invariant by adding offset at last
+ so that iv_uses have different offsets can be CSEed. */
+ poly_widest_int offset = aff_inv.offset;
+ aff_inv.offset = 0;
+
+ gimple_seq stmt_list = NULL, seq = NULL;
+ tree comp_op1 = aff_combination_to_tree (&aff_inv);
+ tree comp_op2 = aff_combination_to_tree (&aff_var);
+ gcc_assert (comp_op1 && comp_op2);
+
+ comp_op1 = force_gimple_operand (comp_op1, &seq, true, NULL);
+ gimple_seq_add_seq (&stmt_list, seq);
+ comp_op2 = force_gimple_operand (comp_op2, &seq, true, NULL);
+ gimple_seq_add_seq (&stmt_list, seq);
+
+ if (POINTER_TYPE_P (TREE_TYPE (comp_op2)))
+ std::swap (comp_op1, comp_op2);
+
+ if (POINTER_TYPE_P (TREE_TYPE (comp_op1)))
+ {
+ comp = fold_build_pointer_plus (comp_op1,
+ fold_convert (sizetype, comp_op2));
+ comp = fold_build_pointer_plus (comp,
+ wide_int_to_tree (sizetype, offset));
+ }
+ else
+ {
+ comp = fold_build2 (PLUS_EXPR, TREE_TYPE (comp_op1), comp_op1,
+ fold_convert (TREE_TYPE (comp_op1), comp_op2));
+ comp = fold_build2 (PLUS_EXPR, TREE_TYPE (comp_op1), comp,
+ wide_int_to_tree (TREE_TYPE (comp_op1), offset));
+ }
+
+ comp = fold_convert (type, comp);
+ comp = force_gimple_operand (comp, &seq, false, NULL);
+ gimple_seq_add_seq (&stmt_list, seq);
+ if (gimple_code (use->stmt) != GIMPLE_PHI
+ /* We can't allow re-allocating the stmt as it might be pointed
+ to still. */
+ && (get_gimple_rhs_num_ops (TREE_CODE (comp))
+ >= gimple_num_ops (gsi_stmt (bsi))))
{
- comp = force_gimple_operand_gsi (&bsi, comp, true, NULL_TREE,
- true, GSI_SAME_STMT);
+ comp = force_gimple_operand (comp, &seq, true, NULL);
+ gimple_seq_add_seq (&stmt_list, seq);
if (POINTER_TYPE_P (TREE_TYPE (tgt)))
{
duplicate_ssa_name_ptr_info (comp, SSA_NAME_PTR_INFO (tgt));
}
}
+ gsi_insert_seq_before (&bsi, stmt_list, GSI_SAME_STMT);
if (gimple_code (use->stmt) == GIMPLE_PHI)
{
ass = gimple_build_assign (tgt, comp);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Reordering \n");
- print_gimple_stmt (dump_file, iv_update, 0, 0);
- print_gimple_stmt (dump_file, use->stmt, 0, 0);
+ print_gimple_stmt (dump_file, iv_update, 0);
+ print_gimple_stmt (dump_file, use->stmt, 0);
fprintf (dump_file, "\n");
}
cand->incremented_at = use->stmt;
}
+/* Return the alias pointer type that should be used for a MEM_REF
+ associated with USE, which has type USE_PTR_ADDRESS. */
+
+static tree
+get_alias_ptr_type_for_ptr_address (iv_use *use)
+{
+ gcall *call = as_a <gcall *> (use->stmt);
+ switch (gimple_call_internal_fn (call))
+ {
+ case IFN_MASK_LOAD:
+ case IFN_MASK_STORE:
+ case IFN_MASK_LOAD_LANES:
+ case IFN_MASK_STORE_LANES:
+ case IFN_LEN_LOAD:
+ case IFN_LEN_STORE:
+ /* The second argument contains the correct alias type. */
+ gcc_assert (use->op_p = gimple_call_arg_ptr (call, 0));
+ return TREE_TYPE (gimple_call_arg (call, 1));
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+
/* Rewrites USE (address that is an iv) using candidate CAND. */
static void
struct iv_use *use, struct iv_cand *cand)
{
aff_tree aff;
- gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
- tree base_hint = NULL_TREE;
- tree ref, iv;
bool ok;
adjust_iv_update_pos (cand, use);
- ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+ ok = get_computation_aff (data->current_loop, use->stmt, use, cand, &aff);
gcc_assert (ok);
unshare_aff_combination (&aff);
based on an object, the base of the reference is in some subexpression
of the use -- but these will use pointer types, so they are recognized
by the create_mem_ref heuristics anyway. */
- if (cand->iv->base_object)
- base_hint = var_at_stmt (data->current_loop, cand, use->stmt);
-
- iv = var_at_stmt (data->current_loop, cand, use->stmt);
- ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff,
- reference_alias_ptr_type (*use->op_p),
- iv, base_hint, data->speed);
- copy_ref_info (ref, *use->op_p);
+ tree iv = var_at_stmt (data->current_loop, cand, use->stmt);
+ tree base_hint = (cand->iv->base_object) ? iv : NULL_TREE;
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+ tree type = use->mem_type;
+ tree alias_ptr_type;
+ if (use->type == USE_PTR_ADDRESS)
+ alias_ptr_type = get_alias_ptr_type_for_ptr_address (use);
+ else
+ {
+ gcc_assert (type == TREE_TYPE (*use->op_p));
+ unsigned int align = get_object_alignment (*use->op_p);
+ if (align != TYPE_ALIGN (type))
+ type = build_aligned_type (type, align);
+ alias_ptr_type = reference_alias_ptr_type (*use->op_p);
+ }
+ tree ref = create_mem_ref (&bsi, type, &aff, alias_ptr_type,
+ iv, base_hint, data->speed);
+
+ if (use->type == USE_PTR_ADDRESS)
+ {
+ ref = fold_build1 (ADDR_EXPR, build_pointer_type (use->mem_type), ref);
+ ref = fold_convert (get_use_type (use), ref);
+ ref = force_gimple_operand_gsi (&bsi, ref, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ }
+ else
+ copy_ref_info (ref, *use->op_p);
+
*use->op_p = ref;
}
rewrite_use_compare (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp, *var_p, op, bound;
+ tree comp, op, bound;
gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
enum tree_code compare;
struct iv_group *group = data->vgroups[use->group_id];
- struct cost_pair *cp = get_group_iv_cost (data, group, cand);
- bool ok;
+ class cost_pair *cp = get_group_iv_cost (data, group, cand);
bound = cp->value;
if (bound)
/* The induction variable elimination failed; just express the original
giv. */
- comp = get_computation (data->current_loop, use, cand);
+ comp = get_computation_at (data->current_loop, use->stmt, use, cand);
gcc_assert (comp != NULL_TREE);
-
- ok = extract_cond_operands (data, use->stmt, &var_p, NULL, NULL, NULL);
- gcc_assert (ok);
-
- *var_p = force_gimple_operand_gsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
- true, GSI_SAME_STMT);
+ gcc_assert (use->op_p != NULL);
+ *use->op_p = force_gimple_operand_gsi (&bsi, comp, true,
+ SSA_NAME_VAR (*use->op_p),
+ true, GSI_SAME_STMT);
}
/* Rewrite the groups using the selected induction variables. */
update_stmt (group->vuses[j]->stmt);
}
}
- else if (group->type == USE_ADDRESS)
+ else if (address_p (group->type))
{
for (j = 0; j < group->vuses.length (); j++)
{
/* Removes the ivs that are not used after rewriting. */
static void
-remove_unused_ivs (struct ivopts_data *data)
+remove_unused_ivs (struct ivopts_data *data, bitmap toremove)
{
unsigned j;
bitmap_iterator bi;
- bitmap toremove = BITMAP_ALLOC (NULL);
/* Figure out an order in which to release SSA DEFs so that we don't
release something that we'd have to propagate into a debug stmt
tree def = info->iv->ssa_name;
- if (MAY_HAVE_DEBUG_STMTS && SSA_NAME_DEF_STMT (def))
+ if (MAY_HAVE_DEBUG_BIND_STMTS && SSA_NAME_DEF_STMT (def))
{
imm_use_iterator imm_iter;
use_operand_p use_p;
count++;
if (count > 1)
- BREAK_FROM_IMM_USE_STMT (imm_iter);
+ break;
}
if (!count)
struct iv_use dummy_use;
struct iv_cand *best_cand = NULL, *cand;
unsigned i, best_pref = 0, cand_pref;
+ tree comp = NULL_TREE;
memset (&dummy_use, 0, sizeof (dummy_use));
dummy_use.iv = info->iv;
? 1 : 0;
if (best_cand == NULL || best_pref < cand_pref)
{
- best_cand = cand;
- best_pref = cand_pref;
+ tree this_comp
+ = get_debug_computation_at (data->current_loop,
+ SSA_NAME_DEF_STMT (def),
+ &dummy_use, cand);
+ if (this_comp)
+ {
+ best_cand = cand;
+ best_pref = cand_pref;
+ comp = this_comp;
+ }
}
}
if (!best_cand)
continue;
- tree comp = get_computation_at (data->current_loop,
- &dummy_use, best_cand,
- SSA_NAME_DEF_STMT (def));
- if (!comp)
- continue;
-
+ comp = unshare_expr (comp);
if (count > 1)
{
tree vexpr = make_node (DEBUG_EXPR_DECL);
}
}
}
-
- release_defs_bitset (toremove);
-
- BITMAP_FREE (toremove);
}
-/* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
+/* Frees memory occupied by class tree_niter_desc in *VALUE. Callback
for hash_map::traverse. */
bool
BITMAP_FREE (group->related_cands);
for (j = 0; j < group->n_map_members; j++)
- if (group->cost_map[j].depends_on)
- BITMAP_FREE (group->cost_map[j].depends_on);
+ {
+ if (group->cost_map[j].inv_vars)
+ BITMAP_FREE (group->cost_map[j].inv_vars);
+ if (group->cost_map[j].inv_exprs)
+ BITMAP_FREE (group->cost_map[j].inv_exprs);
+ }
free (group->cost_map);
free (group);
{
struct iv_cand *cand = data->vcands[i];
- if (cand->depends_on)
- BITMAP_FREE (cand->depends_on);
+ if (cand->inv_vars)
+ BITMAP_FREE (cand->inv_vars);
+ if (cand->inv_exprs)
+ BITMAP_FREE (cand->inv_exprs);
free (cand);
}
data->vcands.truncate (0);
data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
}
- data->max_inv_id = 0;
+ data->max_inv_var_id = 0;
+ data->max_inv_expr_id = 0;
FOR_EACH_VEC_ELT (decl_rtl_to_reset, i, obj)
SET_DECL_RTL (obj, NULL_RTX);
decl_rtl_to_reset.truncate (0);
data->inv_expr_tab->empty ();
- data->max_inv_expr_id = 0;
data->iv_common_cand_tab->empty ();
data->iv_common_cands.truncate (0);
delete data->inv_expr_tab;
data->inv_expr_tab = NULL;
free_affine_expand_cache (&data->name_expansion_cache);
+ if (data->base_object_map)
+ delete data->base_object_map;
delete data->iv_common_cand_tab;
data->iv_common_cand_tab = NULL;
data->iv_common_cands.release ();
return false;
}
+/* Determine cost scaling factor for basic blocks in loop. */
+#define COST_SCALING_FACTOR_BOUND (20)
+
+static void
+determine_scaling_factor (struct ivopts_data *data, basic_block *body)
+{
+ int lfreq = data->current_loop->header->count.to_frequency (cfun);
+ if (!data->speed || lfreq <= 0)
+ return;
+
+ int max_freq = lfreq;
+ for (unsigned i = 0; i < data->current_loop->num_nodes; i++)
+ {
+ body[i]->aux = (void *)(intptr_t) 1;
+ if (max_freq < body[i]->count.to_frequency (cfun))
+ max_freq = body[i]->count.to_frequency (cfun);
+ }
+ if (max_freq > lfreq)
+ {
+ int divisor, factor;
+ /* Check if scaling factor itself needs to be scaled by the bound. This
+ is to avoid overflow when scaling cost according to profile info. */
+ if (max_freq / lfreq > COST_SCALING_FACTOR_BOUND)
+ {
+ divisor = max_freq;
+ factor = COST_SCALING_FACTOR_BOUND;
+ }
+ else
+ {
+ divisor = lfreq;
+ factor = 1;
+ }
+ for (unsigned i = 0; i < data->current_loop->num_nodes; i++)
+ {
+ int bfreq = body[i]->count.to_frequency (cfun);
+ if (bfreq <= lfreq)
+ continue;
+
+ body[i]->aux = (void*)(intptr_t) (factor * bfreq / divisor);
+ }
+ }
+}
+
+/* Find doloop comparison use and set its doloop_p on if found. */
+
+static bool
+find_doloop_use (struct ivopts_data *data)
+{
+ struct loop *loop = data->current_loop;
+
+ for (unsigned i = 0; i < data->vgroups.length (); i++)
+ {
+ struct iv_group *group = data->vgroups[i];
+ if (group->type == USE_COMPARE)
+ {
+ gcc_assert (group->vuses.length () == 1);
+ struct iv_use *use = group->vuses[0];
+ gimple *stmt = use->stmt;
+ if (gimple_code (stmt) == GIMPLE_COND)
+ {
+ basic_block bb = gimple_bb (stmt);
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+ /* This comparison is used for loop latch. Require latch is empty
+ for now. */
+ if ((loop->latch == true_edge->dest
+ || loop->latch == false_edge->dest)
+ && empty_block_p (loop->latch))
+ {
+ group->doloop_p = true;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Doloop cmp iv use: ");
+ print_gimple_stmt (dump_file, stmt, TDF_DETAILS);
+ }
+ return true;
+ }
+ }
+ }
+ }
+
+ return false;
+}
+
+/* For the targets which support doloop, to predict whether later RTL doloop
+ transformation will perform on this loop, further detect the doloop use and
+ mark the flag doloop_use_p if predicted. */
+
+void
+analyze_and_mark_doloop_use (struct ivopts_data *data)
+{
+ data->doloop_use_p = false;
+
+ if (!flag_branch_on_count_reg)
+ return;
+
+ if (data->current_loop->unroll == USHRT_MAX)
+ return;
+
+ if (!generic_predict_doloop_p (data))
+ return;
+
+ if (find_doloop_use (data))
+ {
+ data->doloop_use_p = true;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ struct loop *loop = data->current_loop;
+ fprintf (dump_file,
+ "Predict loop %d can perform"
+ " doloop optimization later.\n",
+ loop->num);
+ flow_loop_dump (loop, dump_file, NULL, 1);
+ }
+ }
+}
+
/* Optimizes the LOOP. Returns true if anything changed. */
static bool
-tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
+tree_ssa_iv_optimize_loop (struct ivopts_data *data, class loop *loop,
+ bitmap toremove)
{
bool changed = false;
- struct iv_ca *iv_ca;
+ class iv_ca *iv_ca;
edge exit = single_dom_exit (loop);
basic_block *body;
gcc_assert (!data->niters);
data->current_loop = loop;
- data->loop_loc = find_loop_location (loop);
+ data->loop_loc = find_loop_location (loop).get_location_t ();
data->speed = optimize_loop_for_speed_p (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
body = get_loop_body (loop);
data->body_includes_call = loop_body_includes_call (body, loop->num_nodes);
renumber_gimple_stmt_uids_in_blocks (body, loop->num_nodes);
- free (body);
- data->loop_single_exit_p = exit != NULL && loop_only_exit_p (loop, exit);
+ data->loop_single_exit_p
+ = exit != NULL && loop_only_exit_p (loop, body, exit);
/* For each ssa name determines whether it behaves as an induction variable
in some loop. */
if (data->vgroups.length () > MAX_CONSIDERED_GROUPS)
goto finish;
+ /* Determine cost scaling factor for basic blocks in loop. */
+ determine_scaling_factor (data, body);
+
+ /* Analyze doloop possibility and mark the doloop use if predicted. */
+ analyze_and_mark_doloop_use (data);
+
/* Finds candidates for the induction variables (item 2). */
find_iv_candidates (data);
/* Find the optimal set of induction variables (item 3, part 2). */
iv_ca = find_optimal_iv_set (data);
+ /* Cleanup basic block aux field. */
+ for (unsigned i = 0; i < data->current_loop->num_nodes; i++)
+ body[i]->aux = NULL;
if (!iv_ca)
goto finish;
changed = true;
rewrite_groups (data);
/* Remove the ivs that are unused after rewriting. */
- remove_unused_ivs (data);
-
- /* 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. */
- scev_reset ();
+ remove_unused_ivs (data, toremove);
finish:
+ free (body);
free_loop_data (data);
return changed;
void
tree_ssa_iv_optimize (void)
{
- struct loop *loop;
struct ivopts_data data;
+ auto_bitmap toremove;
tree_ssa_iv_optimize_init (&data);
/* Optimize the loops starting with the innermost ones. */
- FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+ for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
{
+ if (!dbg_cnt (ivopts_loop))
+ continue;
+
if (dump_file && (dump_flags & TDF_DETAILS))
flow_loop_dump (loop, dump_file, NULL, 1);
- tree_ssa_iv_optimize_loop (&data, loop);
+ tree_ssa_iv_optimize_loop (&data, loop, toremove);
}
+ /* Remove eliminated IV defs. */
+ release_defs_bitset (toremove);
+
+ /* 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. */
+ scev_reset_htab ();
+ /* Likewise niter and control-IV information. */
+ free_numbers_of_iterations_estimates (cfun);
+
tree_ssa_iv_optimize_finalize (&data);
}
+
+#include "gt-tree-ssa-loop-ivopts.h"
projects / thirdparty / gcc.git / blobdiff