/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
+Free Software Foundation; either version 3, or (at your option) any
later version.
GCC is distributed in the hope that it will be useful, but WITHOUT
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This pass tries to find the optimal set of induction variables for the loop.
It optimizes just the basic linear induction variables (although adding
#include "ggc.h"
#include "insn-config.h"
#include "recog.h"
+#include "pointer-set.h"
#include "hashtab.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "cfgloop.h"
#include "params.h"
#include "langhooks.h"
+#include "tree-affine.h"
+#include "target.h"
/* The infinite cost. */
#define INFTY 10000000
USE_COMPARE /* Use is a compare. */
};
+/* Cost of a computation. */
+typedef struct
+{
+ unsigned 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). */
+} comp_cost;
+
+static const comp_cost zero_cost = {0, 0};
+static const comp_cost infinite_cost = {INFTY, INFTY};
+
/* The candidate - cost pair. */
struct cost_pair
{
struct iv_cand *cand; /* The candidate. */
- unsigned cost; /* The cost. */
+ comp_cost cost; /* The cost. */
bitmap depends_on; /* The list of invariants that have to be
preserved. */
tree value; /* For final value elimination, the expression for
unsigned regs_used;
/* Numbers of iterations for all exits of the current loop. */
- htab_t niters;
+ struct pointer_map_t *niters;
/* The size of version_info array allocated. */
unsigned version_info_size;
unsigned n_regs;
/* Total cost of expressing uses. */
- unsigned cand_use_cost;
+ comp_cost cand_use_cost;
/* Total cost of candidates. */
unsigned cand_cost;
unsigned *n_invariant_uses;
/* Total cost of the assignment. */
- unsigned cost;
+ comp_cost cost;
};
/* Difference of two iv candidate assignments. */
edge
single_dom_exit (struct loop *loop)
{
- edge exit = loop->single_exit;
+ edge exit = single_exit (loop);
if (!exit)
return NULL;
return ver_info (data, SSA_NAME_VERSION (name));
}
-/* Checks whether there exists number X such that X * B = A, counting modulo
- 2^BITS. */
-
-static bool
-divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
- HOST_WIDE_INT *x)
-{
- unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- unsigned HOST_WIDE_INT inv, ex, val;
- unsigned i;
-
- a &= mask;
- b &= mask;
-
- /* First divide the whole equation by 2 as long as possible. */
- while (!(a & 1) && !(b & 1))
- {
- a >>= 1;
- b >>= 1;
- bits--;
- mask >>= 1;
- }
-
- if (!(b & 1))
- {
- /* If b is still even, a is odd and there is no such x. */
- return false;
- }
-
- /* Find the inverse of b. We compute it as
- b^(2^(bits - 1) - 1) (mod 2^bits). */
- inv = 1;
- ex = b;
- for (i = 0; i < bits - 1; i++)
- {
- inv = (inv * ex) & mask;
- ex = (ex * ex) & mask;
- }
-
- val = (a * inv) & mask;
-
- gcc_assert (((val * b) & mask) == a);
-
- if ((val >> (bits - 1)) & 1)
- val |= ~mask;
-
- *x = val;
-
- return true;
-}
-
/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
emitted in LOOP. */
}
}
-/* Element of the table in that we cache the numbers of iterations obtained
- from exits of the loop. */
+/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
-struct nfe_cache_elt
+static bool
+abnormal_ssa_name_p (tree exp)
{
- /* The edge for that the number of iterations is cached. */
- edge exit;
+ if (!exp)
+ return false;
- /* True if the # of iterations was successfully determined. */
- bool valid_p;
+ if (TREE_CODE (exp) != SSA_NAME)
+ return false;
- /* Description of # of iterations. */
- struct tree_niter_desc niter;
-};
+ return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
+}
-/* Hash function for nfe_cache_elt E. */
+/* Returns false if BASE or INDEX contains a ssa name that occurs in an
+ abnormal phi node. Callback for for_each_index. */
-static hashval_t
-nfe_hash (const void *e)
+static bool
+idx_contains_abnormal_ssa_name_p (tree base, tree *index,
+ void *data ATTRIBUTE_UNUSED)
{
- const struct nfe_cache_elt *elt = e;
+ if (TREE_CODE (base) == ARRAY_REF)
+ {
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
+ return false;
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
+ return false;
+ }
- return htab_hash_pointer (elt->exit);
+ return !abnormal_ssa_name_p (*index);
}
-/* Equality function for nfe_cache_elt E1 and edge E2. */
+/* Returns true if EXPR contains a ssa name that occurs in an
+ abnormal phi node. */
-static int
-nfe_eq (const void *e1, const void *e2)
+bool
+contains_abnormal_ssa_name_p (tree expr)
{
- const struct nfe_cache_elt *elt1 = e1;
+ 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);
+
+ 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;
- return elt1->exit == e2;
+ default:
+ gcc_unreachable ();
+ }
+
+ return false;
}
-/* Returns structure describing number of iterations determined from
+/* Returns tree describing number of iterations determined from
EXIT of DATA->current_loop, or NULL if something goes wrong. */
-static struct tree_niter_desc *
+static tree
niter_for_exit (struct ivopts_data *data, edge exit)
{
- struct nfe_cache_elt *nfe_desc;
- PTR *slot;
+ struct tree_niter_desc desc;
+ tree niter;
+ void **slot;
- slot = htab_find_slot_with_hash (data->niters, exit,
- htab_hash_pointer (exit),
- INSERT);
-
- if (!*slot)
+ if (!data->niters)
{
- nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
- nfe_desc->exit = exit;
- nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
- exit, &nfe_desc->niter,
- true);
- *slot = nfe_desc;
+ data->niters = pointer_map_create ();
+ slot = NULL;
}
else
- nfe_desc = *slot;
+ slot = pointer_map_contains (data->niters, exit);
+
+ if (!slot)
+ {
+ /* Try to determine number of iterations. We must know it
+ unconditionally (i.e., without possibility of # of iterations
+ being zero). Also, 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). */
+ if (number_of_iterations_exit (data->current_loop,
+ exit, &desc, true)
+ && integer_zerop (desc.may_be_zero)
+ && !contains_abnormal_ssa_name_p (desc.niter))
+ niter = desc.niter;
+ else
+ niter = NULL_TREE;
- if (!nfe_desc->valid_p)
- return NULL;
+ *pointer_map_insert (data->niters, exit) = niter;
+ }
+ else
+ niter = (tree) *slot;
- return &nfe_desc->niter;
+ return niter;
}
-/* Returns structure describing number of iterations determined from
+/* Returns tree describing number of iterations determined from
single dominating exit of DATA->current_loop, or NULL if something
goes wrong. */
-static struct tree_niter_desc *
+static tree
niter_for_single_dom_exit (struct ivopts_data *data)
{
edge exit = single_dom_exit (data->current_loop);
data->relevant = BITMAP_ALLOC (NULL);
data->important_candidates = BITMAP_ALLOC (NULL);
data->max_inv_id = 0;
- data->niters = htab_create (10, nfe_hash, nfe_eq, free);
+ data->niters = NULL;
data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
determine_base_object (tree expr)
{
enum tree_code code = TREE_CODE (expr);
- tree base, obj, op0, op1;
+ 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 (TREE_CODE (expr) == NOP_EXPR
+ || TREE_CODE (expr) == CONVERT_EXPR)
+ return determine_base_object (TREE_OPERAND (expr, 0));
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
return NULL_TREE;
return fold_convert (ptr_type_node,
build_fold_addr_expr (base));
+ case POINTER_PLUS_EXPR:
+ return determine_base_object (TREE_OPERAND (expr, 0));
+
case PLUS_EXPR:
case MINUS_EXPR:
- op0 = determine_base_object (TREE_OPERAND (expr, 0));
- op1 = determine_base_object (TREE_OPERAND (expr, 1));
-
- if (!op1)
- return op0;
-
- if (!op0)
- return (code == PLUS_EXPR
- ? op1
- : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
-
- return fold_build2 (code, ptr_type_node, op0, op1);
-
- case NOP_EXPR:
- case CONVERT_EXPR:
- return determine_base_object (TREE_OPERAND (expr, 0));
+ /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
+ gcc_unreachable ();
default:
return fold_convert (ptr_type_node, expr);
alloc_iv (tree base, tree step)
{
struct iv *iv = XCNEW (struct iv);
-
- if (step && integer_zerop (step))
- step = NULL_TREE;
+ gcc_assert (step != NULL_TREE);
iv->base = base;
iv->base_object = determine_base_object (base);
get_iv (struct ivopts_data *data, tree var)
{
basic_block bb;
-
+ tree type = TREE_TYPE (var);
+
+ if (!POINTER_TYPE_P (type)
+ && !INTEGRAL_TYPE_P (type))
+ return NULL;
+
if (!name_info (data, var)->iv)
{
bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
if (!bb
|| !flow_bb_inside_loop_p (data->current_loop, bb))
- set_iv (data, var, var, NULL_TREE);
+ set_iv (data, var, var, build_int_cst (type, 0));
}
return name_info (data, var)->iv;
if (!simple_iv (loop, phi, name, &iv, true))
return NULL_TREE;
- return (zero_p (iv.step) ? NULL_TREE : iv.step);
-}
-
-/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
-
-static bool
-abnormal_ssa_name_p (tree exp)
-{
- if (!exp)
- return false;
-
- if (TREE_CODE (exp) != SSA_NAME)
- return false;
-
- return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
-}
-
-/* Returns false if BASE or INDEX contains a ssa name that occurs in an
- abnormal phi node. Callback for for_each_index. */
-
-static bool
-idx_contains_abnormal_ssa_name_p (tree base, tree *index,
- void *data ATTRIBUTE_UNUSED)
-{
- if (TREE_CODE (base) == ARRAY_REF)
- {
- if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
- return false;
- if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
- return false;
- }
-
- return !abnormal_ssa_name_p (*index);
-}
-
-/* Returns true if EXPR contains a ssa name that occurs in an
- abnormal phi node. */
-
-static bool
-contains_abnormal_ssa_name_p (tree expr)
-{
- enum tree_code code;
- enum tree_code_class class;
-
- if (!expr)
- return false;
-
- code = TREE_CODE (expr);
- class = 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);
-
- switch (class)
- {
- 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 integer_zerop (iv.step) ? NULL_TREE : iv.step;
}
/* Finds basic ivs. */
iv->base = NULL_TREE;
iv->step = NULL_TREE;
- if (TREE_CODE (stmt) != MODIFY_EXPR)
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
return false;
- lhs = TREE_OPERAND (stmt, 0);
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true))
+ if (!simple_iv (loop, stmt, GIMPLE_STMT_OPERAND (stmt, 1), iv, true))
return false;
iv->base = expand_simple_operations (iv->base);
if (!find_givs_in_stmt_scev (data, stmt, &iv))
return;
- set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
+ set_iv (data, GIMPLE_STMT_OPERAND (stmt, 0), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
- struct tree_niter_desc *niter;
-
- niter = niter_for_single_dom_exit (data);
+ tree niter = niter_for_single_dom_exit (data);
if (niter)
{
fprintf (dump_file, " number of iterations ");
- print_generic_expr (dump_file, niter->niter, TDF_SLIM);
- fprintf (dump_file, "\n");
-
- fprintf (dump_file, " may be zero if ");
- print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
- fprintf (dump_file, "\n");
- fprintf (dump_file, "\n");
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, "\n\n");
};
fprintf (dump_file, "Induction variables:\n\n");
return use;
}
- if (zero_p (iv->step))
+ if (integer_zerop (iv->step))
{
record_invariant (data, op, true);
return NULL;
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (TREE_CODE (stmt) == PHI_NODE
- || TREE_CODE (stmt) == MODIFY_EXPR);
+ || TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
iv->use_id = use->id;
return use;
}
-/* Checks whether the condition *COND_P in STMT is interesting
- and if so, records it. */
+/* Given a condition *COND_P, 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 invariant,
+ IV_VAR and IV_BOUND are set to the corresponding induction variable
+ descriptions, and true is returned. If this is not the case,
+ CONTROL_VAR and BOUND are set to the arguments of the condition and
+ false is returned. */
-static void
-find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+static bool
+extract_cond_operands (struct ivopts_data *data, tree *cond_p,
+ tree **control_var, tree **bound,
+ struct iv **iv_var, struct iv **iv_bound)
{
- tree *op0_p;
- tree *op1_p;
- struct iv *iv0 = NULL, *iv1 = NULL, *civ;
- struct iv const_iv;
- tree zero = integer_zero_node;
-
- const_iv.step = NULL_TREE;
+ /* The nodes returned when COND has just one operand. Note that you should
+ not modify anything in BOUND or IV_BOUND because of this. */
+ static struct iv const_iv;
+ static tree zero;
+ tree cond = *cond_p;
+ tree *op0 = &zero, *op1 = &zero, *tmp_op;
+ struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+ bool ret = false;
- if (TREE_CODE (*cond_p) != SSA_NAME
- && !COMPARISON_CLASS_P (*cond_p))
- return;
+ zero = integer_zero_node;
+ const_iv.step = integer_zero_node;
- if (TREE_CODE (*cond_p) == SSA_NAME)
+ if (TREE_CODE (cond) == SSA_NAME)
{
- op0_p = cond_p;
- op1_p = &zero;
+ op0 = cond_p;
+ iv0 = get_iv (data, cond);
+ ret = (iv0 && !integer_zerop (iv0->step));
+ goto end;
}
- else
+
+ if (!COMPARISON_CLASS_P (cond))
{
- op0_p = &TREE_OPERAND (*cond_p, 0);
- op1_p = &TREE_OPERAND (*cond_p, 1);
+ op0 = cond_p;
+ goto end;
}
- if (TREE_CODE (*op0_p) == SSA_NAME)
- iv0 = get_iv (data, *op0_p);
- else
- iv0 = &const_iv;
+ op0 = &TREE_OPERAND (cond, 0);
+ op1 = &TREE_OPERAND (cond, 1);
+ if (TREE_CODE (*op0) == SSA_NAME)
+ iv0 = get_iv (data, *op0);
+ if (TREE_CODE (*op1) == SSA_NAME)
+ iv1 = get_iv (data, *op1);
- if (TREE_CODE (*op1_p) == SSA_NAME)
- iv1 = get_iv (data, *op1_p);
- else
- iv1 = &const_iv;
+ /* Exactly one of the compared values must be an iv, and the other one must
+ be an invariant. */
+ if (!iv0 || !iv1)
+ goto end;
- if (/* When comparing with non-invariant value, we may not do any senseful
- induction variable elimination. */
- (!iv0 || !iv1)
- /* Eliminating condition based on two ivs would be nontrivial.
- ??? TODO -- it is not really important to handle this case. */
- || (!zero_p (iv0->step) && !zero_p (iv1->step)))
+ if (integer_zerop (iv0->step))
{
- find_interesting_uses_op (data, *op0_p);
- find_interesting_uses_op (data, *op1_p);
- return;
+ /* Control variable may be on the other side. */
+ tmp_op = op0; op0 = op1; op1 = tmp_op;
+ tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
}
+ ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
- if (zero_p (iv0->step) && zero_p (iv1->step))
+end:
+ if (control_var)
+ *control_var = op0;;
+ if (iv_var)
+ *iv_var = iv0;;
+ if (bound)
+ *bound = op1;
+ if (iv_bound)
+ *iv_bound = iv1;
+
+ return ret;
+}
+
+/* Checks whether the condition *COND_P in STMT is interesting
+ and if so, records it. */
+
+static void
+find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+{
+ tree *var_p, *bound_p;
+ struct iv *var_iv, *civ;
+
+ if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
{
- /* If both are invariants, this is a work for unswitching. */
+ find_interesting_uses_op (data, *var_p);
+ find_interesting_uses_op (data, *bound_p);
return;
}
civ = XNEW (struct iv);
- *civ = zero_p (iv0->step) ? *iv1: *iv0;
+ *civ = *var_iv;
record_use (data, cond_p, civ, stmt, USE_COMPARE);
}
/* Returns true if expression EXPR is obviously invariant in LOOP,
- i.e. if all its operands are defined outside of the LOOP. */
+ i.e. if all its operands are defined outside of the LOOP. LOOP
+ should not be the function body. */
bool
expr_invariant_in_loop_p (struct loop *loop, tree expr)
basic_block def_bb;
unsigned i, len;
+ gcc_assert (loop_depth (loop) > 0);
+
if (is_gimple_min_invariant (expr))
return true;
return true;
}
- if (!EXPR_P (expr))
+ if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
return false;
- len = TREE_CODE_LENGTH (TREE_CODE (expr));
+ len = TREE_OPERAND_LENGTH (expr);
for (i = 0; i < len; i++)
if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
return false;
{
struct ivopts_data *ivopts_data;
tree stmt;
- tree *step_p;
+ tree step;
};
static bool
idx_find_step (tree base, tree *idx, void *data)
{
- struct ifs_ivopts_data *dta = data;
+ struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
struct iv *iv;
- tree step, iv_step, lbound, off;
+ tree step, iv_base, iv_step, lbound, off;
struct loop *loop = dta->ivopts_data->current_loop;
if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
if (!iv)
return false;
+ /* XXX We produce for a base of *D42 with iv->base being &x[0]
+ *&x[0], which is not folded and does not trigger the
+ ARRAY_REF path below. */
*idx = iv->base;
- if (!iv->step)
+ if (integer_zerop (iv->step))
return true;
if (TREE_CODE (base) == ARRAY_REF)
/* The step for pointer arithmetics already is 1 byte. */
step = build_int_cst (sizetype, 1);
- /* FIXME: convert_step should not be used outside chrec_convert: fix
- this by calling chrec_convert. */
- iv_step = convert_step (dta->ivopts_data->current_loop,
- sizetype, iv->base, iv->step, dta->stmt);
-
- if (!iv_step)
+ iv_base = iv->base;
+ iv_step = iv->step;
+ if (!convert_affine_scev (dta->ivopts_data->current_loop,
+ sizetype, &iv_base, &iv_step, dta->stmt,
+ false))
{
/* The index might wrap. */
return false;
}
step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
-
- if (!*dta->step_p)
- *dta->step_p = step;
- else
- *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
+ dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step);
return true;
}
static bool
idx_record_use (tree base, tree *idx,
- void *data)
+ void *vdata)
{
+ struct ivopts_data *data = (struct ivopts_data *) vdata;
find_interesting_uses_op (data, *idx);
if (TREE_CODE (base) == ARRAY_REF)
{
return true;
}
-/* Returns true if memory reference REF may be unaligned. */
+/* If we can prove that TOP = cst * BOT for some constant cst,
+ store cst to MUL and return true. Otherwise return false.
+ The returned value is always sign-extended, regardless of the
+ signedness of TOP and BOT. */
static bool
-may_be_unaligned_p (tree ref)
+constant_multiple_of (tree top, tree bot, double_int *mul)
{
- tree base;
- tree base_type;
- HOST_WIDE_INT bitsize;
- HOST_WIDE_INT bitpos;
- tree toffset;
- enum machine_mode mode;
- int unsignedp, volatilep;
- unsigned base_align;
-
- /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
- thus they are not misaligned. */
- if (TREE_CODE (ref) == TARGET_MEM_REF)
- return false;
-
- /* The test below is basically copy of what expr.c:normal_inner_ref
- does to check whether the object must be loaded by parts when
- STRICT_ALIGNMENT is true. */
- base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
- &unsignedp, &volatilep, true);
- base_type = TREE_TYPE (base);
- base_align = TYPE_ALIGN (base_type);
+ tree mby;
+ enum tree_code code;
+ double_int res, p0, p1;
+ unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
- if (mode != BLKmode
- && (base_align < GET_MODE_ALIGNMENT (mode)
- || bitpos % GET_MODE_ALIGNMENT (mode) != 0
- || bitpos % BITS_PER_UNIT != 0))
- return true;
+ STRIP_NOPS (top);
+ STRIP_NOPS (bot);
- return false;
-}
+ if (operand_equal_p (top, bot, 0))
+ {
+ *mul = double_int_one;
+ return true;
+ }
-/* Finds addresses in *OP_P inside STMT. */
+ code = TREE_CODE (top);
+ switch (code)
+ {
+ case MULT_EXPR:
+ mby = TREE_OPERAND (top, 1);
+ if (TREE_CODE (mby) != INTEGER_CST)
+ return false;
+
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
+ return false;
+
+ *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
+ precision);
+ return true;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
+ || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
+ return false;
+
+ if (code == MINUS_EXPR)
+ p1 = double_int_neg (p1);
+ *mul = double_int_sext (double_int_add (p0, p1), precision);
+ return true;
+
+ case INTEGER_CST:
+ if (TREE_CODE (bot) != INTEGER_CST)
+ return false;
+
+ p0 = double_int_sext (tree_to_double_int (top), precision);
+ p1 = double_int_sext (tree_to_double_int (bot), precision);
+ if (double_int_zero_p (p1))
+ return false;
+ *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
+ precision);
+ return double_int_zero_p (res);
+
+ default:
+ return false;
+ }
+}
+
+/* Returns true if memory reference REF with step STEP may be unaligned. */
+
+static bool
+may_be_unaligned_p (tree ref, tree step)
+{
+ tree base;
+ tree base_type;
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree toffset;
+ enum machine_mode mode;
+ int unsignedp, volatilep;
+ unsigned base_align;
+
+ /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
+ thus they are not misaligned. */
+ if (TREE_CODE (ref) == TARGET_MEM_REF)
+ return false;
+
+ /* The test below is basically copy of what expr.c:normal_inner_ref
+ does to check whether the object must be loaded by parts when
+ STRICT_ALIGNMENT is true. */
+ base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
+ &unsignedp, &volatilep, true);
+ base_type = TREE_TYPE (base);
+ base_align = TYPE_ALIGN (base_type);
+
+ if (mode != BLKmode)
+ {
+ double_int mul;
+ tree al = build_int_cst (TREE_TYPE (step),
+ GET_MODE_ALIGNMENT (mode) / BITS_PER_UNIT);
+
+ if (base_align < GET_MODE_ALIGNMENT (mode)
+ || bitpos % GET_MODE_ALIGNMENT (mode) != 0
+ || bitpos % BITS_PER_UNIT != 0)
+ return true;
+
+ if (!constant_multiple_of (step, al, &mul))
+ return true;
+ }
+
+ return false;
+}
+
+/* Return true if EXPR may be non-addressable. */
+
+static bool
+may_be_nonaddressable_p (tree expr)
+{
+ switch (TREE_CODE (expr))
+ {
+ case TARGET_MEM_REF:
+ /* TARGET_MEM_REFs are translated directly to valid MEMs on the
+ target, thus they are always addressable. */
+ return false;
+
+ case COMPONENT_REF:
+ return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
+ || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ case VIEW_CONVERT_EXPR:
+ /* This kind of view-conversions may wrap non-addressable objects
+ and make them look addressable. After some processing the
+ non-addressability may be uncovered again, causing ADDR_EXPRs
+ of inappropriate objects to be built. */
+ if (AGGREGATE_TYPE_P (TREE_TYPE (expr))
+ && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))))
+ return true;
+
+ /* ... fall through ... */
+
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ case CONVERT_EXPR:
+ case NON_LVALUE_EXPR:
+ case NOP_EXPR:
+ return true;
+
+ default:
+ break;
+ }
+
+ return false;
+}
+
+/* Finds addresses in *OP_P inside STMT. */
static void
find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
{
- tree base = *op_p, step = NULL;
+ tree base = *op_p, step = build_int_cst (sizetype, 0);
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
/* Ignore bitfields for now. Not really something terribly complicated
to handle. TODO. */
- if (TREE_CODE (base) == COMPONENT_REF
- && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
- goto fail;
-
- if (STRICT_ALIGNMENT
- && may_be_unaligned_p (base))
+ if (TREE_CODE (base) == BIT_FIELD_REF)
goto fail;
base = unshare_expr (base);
if (TMR_STEP (base))
astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
- if (step)
- step = fold_build2 (PLUS_EXPR, type, step, astep);
- else
- step = astep;
+ step = fold_build2 (PLUS_EXPR, type, step, astep);
}
}
- if (zero_p (step))
+ if (integer_zerop (step))
goto fail;
base = tree_mem_ref_addr (type, base);
}
{
ifs_ivopts_data.ivopts_data = data;
ifs_ivopts_data.stmt = stmt;
- ifs_ivopts_data.step_p = &step;
+ ifs_ivopts_data.step = build_int_cst (sizetype, 0);
if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
- || zero_p (step))
+ || integer_zerop (ifs_ivopts_data.step))
goto fail;
+ step = ifs_ivopts_data.step;
gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+ /* Check that the base expression is addressable. This needs
+ to be done after substituting bases of IVs into it. */
+ if (may_be_nonaddressable_p (base))
+ goto fail;
+
+ /* Moreover, on strict alignment platforms, check that it is
+ sufficiently aligned. */
+ if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
+ goto fail;
+
base = build_fold_addr_expr (base);
+
+ /* Substituting bases of IVs into the base expression might
+ have caused folding opportunities. */
+ if (TREE_CODE (base) == ADDR_EXPR)
+ {
+ tree *ref = &TREE_OPERAND (base, 0);
+ while (handled_component_p (*ref))
+ ref = &TREE_OPERAND (*ref, 0);
+ if (TREE_CODE (*ref) == INDIRECT_REF)
+ *ref = fold_indirect_ref (*ref);
+ }
}
civ = alloc_iv (base, step);
return;
}
- if (TREE_CODE (stmt) == MODIFY_EXPR)
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
{
- lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ rhs = GIMPLE_STMT_OPERAND (stmt, 1);
if (TREE_CODE (lhs) == SSA_NAME)
{
iv = get_iv (data, lhs);
- if (iv && !zero_p (iv->step))
+ if (iv && !integer_zerop (iv->step))
return;
}
switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
{
case tcc_comparison:
- find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
+ find_interesting_uses_cond (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 1));
return;
case tcc_reference:
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
+ find_interesting_uses_address (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 1));
if (REFERENCE_CLASS_P (lhs))
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
+ find_interesting_uses_address (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 0));
return;
default: ;
if (REFERENCE_CLASS_P (lhs)
&& is_gimple_val (rhs))
{
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
+ find_interesting_uses_address (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 0));
find_interesting_uses_op (data, rhs);
return;
}
lhs = PHI_RESULT (stmt);
iv = get_iv (data, lhs);
- if (iv && !zero_p (iv->step))
+ if (iv && !integer_zerop (iv->step))
return;
}
for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
{
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
- find_interesting_uses_op (data, def);
+ if (is_gimple_reg (def))
+ find_interesting_uses_op (data, def);
}
}
{
case INTEGER_CST:
if (!cst_and_fits_in_hwi (expr)
- || zero_p (expr))
+ || integer_zerop (expr))
return orig_expr;
*offset = int_cst_value (expr);
- return build_int_cst_type (orig_type, 0);
+ return build_int_cst (orig_type, 0);
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
op0 = TREE_OPERAND (expr, 0);
op0 = strip_offset_1 (op0, false, false, &off0);
op1 = strip_offset_1 (op1, false, false, &off1);
- *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
+ *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
if (op0 == TREE_OPERAND (expr, 0)
&& op1 == TREE_OPERAND (expr, 1))
return orig_expr;
- if (zero_p (op1))
+ if (integer_zerop (op1))
expr = op0;
- else if (zero_p (op0))
+ else if (integer_zerop (op0))
{
- if (code == PLUS_EXPR)
- expr = op1;
- else
+ if (code == MINUS_EXPR)
expr = fold_build1 (NEGATE_EXPR, type, op1);
+ else
+ expr = op1;
}
else
expr = fold_build2 (code, type, op0, op1);
*offset = off1 * st;
if (top_compref
- && zero_p (op1))
+ && integer_zerop (op1))
{
/* Strip the component reference completely. */
op0 = TREE_OPERAND (expr, 0);
}
/* Returns variant of TYPE that can be used as base for different uses.
- For integer types, we return unsigned variant of the type, which
- avoids problems with overflows. For pointer types, we return void *. */
+ We return unsigned type with the same precision, which avoids problems
+ with overflows. */
static tree
generic_type_for (tree type)
{
if (POINTER_TYPE_P (type))
- return ptr_type_node;
+ return unsigned_type_for (type);
if (TYPE_UNSIGNED (type))
return type;
static tree
find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
{
- bitmap *depends_on = data;
+ bitmap *depends_on = (bitmap *) data;
struct version_info *info;
if (TREE_CODE (*expr_p) != SSA_NAME)
if (type != orig_type)
{
base = fold_convert (type, base);
- if (step)
- step = fold_convert (type, step);
+ step = fold_convert (type, step);
}
}
if (!base && !step)
continue;
- if (!operand_equal_p (base, cand->iv->base, 0))
- continue;
-
- if (zero_p (cand->iv->step))
- {
- if (zero_p (step))
- break;
- }
- else
- {
- if (step && operand_equal_p (step, cand->iv->step, 0))
- break;
- }
+ if (operand_equal_p (base, cand->iv->base, 0)
+ && operand_equal_p (step, cand->iv->step, 0))
+ break;
}
if (i == n_iv_cands (data))
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
iv = ver_info (data, i)->iv;
- if (iv && iv->biv_p && !zero_p (iv->step))
+ if (iv && iv->biv_p && !integer_zerop (iv->step))
add_old_iv_candidates (data, iv);
}
}
}
}
+/* Returns description of computation cost of expression whose runtime
+ cost is RUNTIME and complexity corresponds to COMPLEXITY. */
+
+static comp_cost
+new_cost (unsigned runtime, unsigned complexity)
+{
+ comp_cost cost;
+
+ cost.cost = runtime;
+ cost.complexity = complexity;
+
+ return cost;
+}
+
+/* Adds costs COST1 and COST2. */
+
+static comp_cost
+add_costs (comp_cost cost1, comp_cost cost2)
+{
+ cost1.cost += cost2.cost;
+ cost1.complexity += cost2.complexity;
+
+ return cost1;
+}
+/* Subtracts costs COST1 and COST2. */
+
+static comp_cost
+sub_costs (comp_cost cost1, comp_cost cost2)
+{
+ cost1.cost -= cost2.cost;
+ cost1.complexity -= cost2.complexity;
+
+ return cost1;
+}
+
+/* Returns a negative number if COST1 < COST2, a positive number if
+ COST1 > COST2, and 0 if COST1 = COST2. */
+
+static int
+compare_costs (comp_cost cost1, comp_cost cost2)
+{
+ if (cost1.cost == cost2.cost)
+ return cost1.complexity - cost2.complexity;
+
+ return cost1.cost - cost2.cost;
+}
+
+/* Returns true if COST is infinite. */
+
+static bool
+infinite_cost_p (comp_cost cost)
+{
+ return cost.cost == INFTY;
+}
+
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
on invariants DEPENDS_ON and that the value used in expressing it
is VALUE.*/
static void
set_use_iv_cost (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand, unsigned cost,
- bitmap depends_on, tree value)
+ struct iv_use *use, struct iv_cand *cand,
+ comp_cost cost, bitmap depends_on, tree value)
{
unsigned i, s;
- if (cost == INFTY)
+ if (infinite_cost_p (cost))
{
BITMAP_FREE (depends_on);
return;
{
const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
x = gen_rtx_SYMBOL_REF (Pmode, name);
+ SET_SYMBOL_REF_DECL (x, obj);
+ x = gen_rtx_MEM (DECL_MODE (obj), x);
+ targetm.encode_section_info (obj, x, true);
}
else
- x = gen_raw_REG (Pmode, (*regno)++);
+ {
+ x = gen_raw_REG (Pmode, (*regno)++);
+ x = gen_rtx_MEM (DECL_MODE (obj), x);
+ }
- return gen_rtx_MEM (DECL_MODE (obj), x);
+ return x;
}
/* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
{
tree obj = NULL_TREE;
rtx x = NULL_RTX;
- int *regno = data;
+ int *regno = (int *) data;
switch (TREE_CODE (*expr_p))
{
but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
int
-tree_int_cst_sign_bit (tree t)
+tree_int_cst_sign_bit (const_tree t)
{
unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
unsigned HOST_WIDE_INT w;
else
{
w = TREE_INT_CST_HIGH (t);
- bitno -= HOST_BITS_PER_WIDE_INT;
- }
-
- return (w >> bitno) & 1;
-}
-
-/* If we can prove that TOP = cst * BOT for some constant cst in TYPE,
- return cst. Otherwise return NULL_TREE. */
-
-static tree
-constant_multiple_of (tree type, tree top, tree bot)
-{
- tree res, mby, p0, p1;
- enum tree_code code;
- bool negate;
-
- STRIP_NOPS (top);
- STRIP_NOPS (bot);
-
- if (operand_equal_p (top, bot, 0))
- return build_int_cst (type, 1);
-
- code = TREE_CODE (top);
- switch (code)
- {
- case MULT_EXPR:
- mby = TREE_OPERAND (top, 1);
- if (TREE_CODE (mby) != INTEGER_CST)
- return NULL_TREE;
-
- res = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
- if (!res)
- return NULL_TREE;
-
- return fold_binary_to_constant (MULT_EXPR, type, res,
- fold_convert (type, mby));
-
- case PLUS_EXPR:
- case MINUS_EXPR:
- p0 = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
- if (!p0)
- return NULL_TREE;
- p1 = constant_multiple_of (type, TREE_OPERAND (top, 1), bot);
- if (!p1)
- return NULL_TREE;
-
- return fold_binary_to_constant (code, type, p0, p1);
-
- case INTEGER_CST:
- if (TREE_CODE (bot) != INTEGER_CST)
- return NULL_TREE;
-
- bot = fold_convert (type, bot);
- top = fold_convert (type, top);
-
- /* If BOT seems to be negative, try dividing by -BOT instead, and negate
- the result afterwards. */
- if (tree_int_cst_sign_bit (bot))
- {
- negate = true;
- bot = fold_unary_to_constant (NEGATE_EXPR, type, bot);
- }
- else
- negate = false;
-
- /* Ditto for TOP. */
- if (tree_int_cst_sign_bit (top))
- {
- negate = !negate;
- top = fold_unary_to_constant (NEGATE_EXPR, type, top);
- }
-
- if (!zero_p (fold_binary_to_constant (TRUNC_MOD_EXPR, type, top, bot)))
- return NULL_TREE;
-
- res = fold_binary_to_constant (EXACT_DIV_EXPR, type, top, bot);
- if (negate)
- res = fold_unary_to_constant (NEGATE_EXPR, type, res);
- return res;
-
- default:
- return NULL_TREE;
- }
-}
-
-/* Sets COMB to CST. */
-
-static void
-aff_combination_const (struct affine_tree_combination *comb, tree type,
- unsigned HOST_WIDE_INT cst)
-{
- unsigned prec = TYPE_PRECISION (type);
-
- comb->type = type;
- comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
-
- comb->n = 0;
- comb->rest = NULL_TREE;
- comb->offset = cst & comb->mask;
-}
-
-/* Sets COMB to single element ELT. */
-
-static void
-aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
-{
- unsigned prec = TYPE_PRECISION (type);
-
- comb->type = type;
- comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
-
- comb->n = 1;
- comb->elts[0] = elt;
- comb->coefs[0] = 1;
- comb->rest = NULL_TREE;
- comb->offset = 0;
-}
-
-/* Scales COMB by SCALE. */
-
-static void
-aff_combination_scale (struct affine_tree_combination *comb,
- unsigned HOST_WIDE_INT scale)
-{
- unsigned i, j;
-
- if (scale == 1)
- return;
-
- if (scale == 0)
- {
- aff_combination_const (comb, comb->type, 0);
- return;
- }
-
- comb->offset = (scale * comb->offset) & comb->mask;
- for (i = 0, j = 0; i < comb->n; i++)
- {
- comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
- comb->elts[j] = comb->elts[i];
- if (comb->coefs[j] != 0)
- j++;
- }
- comb->n = j;
-
- if (comb->rest)
- {
- if (comb->n < MAX_AFF_ELTS)
- {
- comb->coefs[comb->n] = scale;
- comb->elts[comb->n] = comb->rest;
- comb->rest = NULL_TREE;
- comb->n++;
- }
- else
- comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
- build_int_cst_type (comb->type, scale));
- }
-}
-
-/* Adds ELT * SCALE to COMB. */
-
-static void
-aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
- unsigned HOST_WIDE_INT scale)
-{
- unsigned i;
-
- if (scale == 0)
- return;
-
- for (i = 0; i < comb->n; i++)
- if (operand_equal_p (comb->elts[i], elt, 0))
- {
- comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
- if (comb->coefs[i])
- return;
-
- comb->n--;
- comb->coefs[i] = comb->coefs[comb->n];
- comb->elts[i] = comb->elts[comb->n];
-
- if (comb->rest)
- {
- gcc_assert (comb->n == MAX_AFF_ELTS - 1);
- comb->coefs[comb->n] = 1;
- comb->elts[comb->n] = comb->rest;
- comb->rest = NULL_TREE;
- comb->n++;
- }
- return;
- }
- if (comb->n < MAX_AFF_ELTS)
- {
- comb->coefs[comb->n] = scale;
- comb->elts[comb->n] = elt;
- comb->n++;
- return;
- }
-
- if (scale == 1)
- elt = fold_convert (comb->type, elt);
- else
- elt = fold_build2 (MULT_EXPR, comb->type,
- fold_convert (comb->type, elt),
- build_int_cst_type (comb->type, scale));
-
- if (comb->rest)
- comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
- else
- comb->rest = elt;
-}
-
-/* Adds COMB2 to COMB1. */
-
-static void
-aff_combination_add (struct affine_tree_combination *comb1,
- struct affine_tree_combination *comb2)
-{
- unsigned i;
-
- comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
- for (i = 0; i < comb2->n; i++)
- aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
- if (comb2->rest)
- aff_combination_add_elt (comb1, comb2->rest, 1);
-}
-
-/* Splits EXPR into an affine combination of parts. */
-
-static void
-tree_to_aff_combination (tree expr, tree type,
- struct affine_tree_combination *comb)
-{
- struct affine_tree_combination tmp;
- enum tree_code code;
- tree cst, core, toffset;
- HOST_WIDE_INT bitpos, bitsize;
- enum machine_mode mode;
- int unsignedp, volatilep;
-
- STRIP_NOPS (expr);
-
- code = TREE_CODE (expr);
- switch (code)
- {
- case INTEGER_CST:
- aff_combination_const (comb, type, int_cst_value (expr));
- return;
-
- case PLUS_EXPR:
- case MINUS_EXPR:
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
- if (code == MINUS_EXPR)
- aff_combination_scale (&tmp, -1);
- aff_combination_add (comb, &tmp);
- return;
-
- case MULT_EXPR:
- cst = TREE_OPERAND (expr, 1);
- if (TREE_CODE (cst) != INTEGER_CST)
- break;
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- aff_combination_scale (comb, int_cst_value (cst));
- return;
-
- case NEGATE_EXPR:
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- aff_combination_scale (comb, -1);
- return;
-
- case ADDR_EXPR:
- core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
- &toffset, &mode, &unsignedp, &volatilep,
- false);
- if (bitpos % BITS_PER_UNIT != 0)
- break;
- aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
- core = build_fold_addr_expr (core);
- if (TREE_CODE (core) == ADDR_EXPR)
- aff_combination_add_elt (comb, core, 1);
- else
- {
- tree_to_aff_combination (core, type, &tmp);
- aff_combination_add (comb, &tmp);
- }
- if (toffset)
- {
- tree_to_aff_combination (toffset, type, &tmp);
- aff_combination_add (comb, &tmp);
- }
- return;
-
- default:
- break;
- }
-
- aff_combination_elt (comb, type, expr);
-}
-
-/* Creates EXPR + ELT * SCALE in TYPE. MASK is the mask for width of TYPE. */
-
-static tree
-add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
- unsigned HOST_WIDE_INT mask)
-{
- enum tree_code code;
-
- scale &= mask;
- elt = fold_convert (type, elt);
-
- if (scale == 1)
- {
- if (!expr)
- return elt;
-
- return fold_build2 (PLUS_EXPR, type, expr, elt);
- }
-
- if (scale == mask)
- {
- if (!expr)
- return fold_build1 (NEGATE_EXPR, type, elt);
-
- return fold_build2 (MINUS_EXPR, type, expr, elt);
- }
-
- if (!expr)
- return fold_build2 (MULT_EXPR, type, elt,
- build_int_cst_type (type, scale));
-
- if ((scale | (mask >> 1)) == mask)
- {
- /* Scale is negative. */
- code = MINUS_EXPR;
- scale = (-scale) & mask;
+ bitno -= HOST_BITS_PER_WIDE_INT;
}
- else
- code = PLUS_EXPR;
-
- elt = fold_build2 (MULT_EXPR, type, elt,
- build_int_cst_type (type, scale));
- return fold_build2 (code, type, expr, elt);
-}
-
-/* Copies the tree elements of COMB to ensure that they are not shared. */
-
-static void
-unshare_aff_combination (struct affine_tree_combination *comb)
-{
- unsigned i;
- for (i = 0; i < comb->n; i++)
- comb->elts[i] = unshare_expr (comb->elts[i]);
- if (comb->rest)
- comb->rest = unshare_expr (comb->rest);
+ return (w >> bitno) & 1;
}
-/* Makes tree from the affine combination COMB. */
+/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
+ same precision that is at least as wide as the precision of TYPE, stores
+ BA to A and BB to B, and returns the type of BA. Otherwise, returns the
+ type of A and B. */
static tree
-aff_combination_to_tree (struct affine_tree_combination *comb)
+determine_common_wider_type (tree *a, tree *b)
{
- tree type = comb->type;
- tree expr = comb->rest;
- unsigned i;
- unsigned HOST_WIDE_INT off, sgn;
-
- /* Handle the special case produced by get_computation_aff when
- the type does not fit in HOST_WIDE_INT. */
- if (comb->n == 0 && comb->offset == 0)
- return fold_convert (type, expr);
+ tree wider_type = NULL;
+ tree suba, subb;
+ tree atype = TREE_TYPE (*a);
- gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
-
- for (i = 0; i < comb->n; i++)
- expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
- comb->mask);
-
- if ((comb->offset | (comb->mask >> 1)) == comb->mask)
+ if ((TREE_CODE (*a) == NOP_EXPR
+ || TREE_CODE (*a) == CONVERT_EXPR))
{
- /* Offset is negative. */
- off = (-comb->offset) & comb->mask;
- sgn = comb->mask;
+ suba = TREE_OPERAND (*a, 0);
+ wider_type = TREE_TYPE (suba);
+ if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
+ return atype;
}
else
+ return atype;
+
+ if ((TREE_CODE (*b) == NOP_EXPR
+ || TREE_CODE (*b) == CONVERT_EXPR))
{
- off = comb->offset;
- sgn = 1;
+ subb = TREE_OPERAND (*b, 0);
+ if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
+ return atype;
}
- return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
- comb->mask);
+ else
+ return atype;
+
+ *a = suba;
+ *b = subb;
+ return wider_type;
}
/* Determines the expression by that USE is expressed from induction variable
tree ubase = use->iv->base;
tree ustep = use->iv->step;
tree cbase = cand->iv->base;
- tree cstep = cand->iv->step;
+ tree cstep = cand->iv->step, cstep_common;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+ tree common_type, var;
tree uutype;
- tree expr, delta;
- tree ratio;
- unsigned HOST_WIDE_INT ustepi, cstepi;
- HOST_WIDE_INT ratioi;
- struct affine_tree_combination cbase_aff, expr_aff;
- tree cstep_orig = cstep, ustep_orig = ustep;
+ aff_tree cbase_aff, var_aff;
+ double_int rat;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
return false;
}
- expr = var_at_stmt (loop, cand, at);
-
- if (TREE_TYPE (expr) != ctype)
- {
- /* This may happen with the original ivs. */
- expr = fold_convert (ctype, expr);
- }
-
- if (TYPE_UNSIGNED (utype))
- uutype = utype;
- else
- {
- uutype = unsigned_type_for (utype);
- ubase = fold_convert (uutype, ubase);
- ustep = fold_convert (uutype, ustep);
- }
+ var = var_at_stmt (loop, cand, at);
+ uutype = unsigned_type_for (utype);
- if (uutype != ctype)
+ /* If the conversion is not noop, perform it. */
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
- expr = fold_convert (uutype, expr);
- cbase = fold_convert (uutype, cbase);
cstep = fold_convert (uutype, cstep);
-
- /* If the conversion is not noop, we must take it into account when
- considering the value of the step. */
- if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
- cstep_orig = cstep;
+ cbase = fold_convert (uutype, cbase);
+ var = fold_convert (uutype, var);
}
- if (cst_and_fits_in_hwi (cstep_orig)
- && cst_and_fits_in_hwi (ustep_orig))
- {
- ustepi = int_cst_value (ustep_orig);
- cstepi = int_cst_value (cstep_orig);
-
- if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
- {
- /* TODO maybe consider case when ustep divides cstep and the ratio is
- a power of 2 (so that the division is fast to execute)? We would
- need to be much more careful with overflows etc. then. */
- return false;
- }
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ return false;
- ratio = build_int_cst_type (uutype, ratioi);
- }
- else
- {
- ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
- if (!ratio)
- return false;
+ /* 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
+ overflows, as all the arithmetics will in the end be performed in UUTYPE
+ anyway. */
+ common_type = determine_common_wider_type (&ubase, &cbase);
- /* Ratioi is only used to detect special cases when the multiplicative
- factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
- we may set it to 0. We prefer cst_and_fits_in_hwi/int_cst_value
- to integer_onep/integer_all_onesp, since the former ignores
- TREE_OVERFLOW. */
- if (cst_and_fits_in_hwi (ratio))
- ratioi = int_cst_value (ratio);
- else if (integer_onep (ratio))
- ratioi = 1;
- else if (integer_all_onesp (ratio))
- ratioi = -1;
- else
- ratioi = 0;
- }
+ /* 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);
- /* We may need to shift the value if we are after the increment. */
+ /* We need to shift the value if we are after the increment. */
if (stmt_after_increment (loop, cand, at))
- cbase = fold_build2 (PLUS_EXPR, uutype, cbase, cstep);
-
- /* use = ubase - ratio * cbase + ratio * var.
-
- In general case ubase + ratio * (var - cbase) could be better (one less
- multiplication), but often it is possible to eliminate redundant parts
- of computations from (ubase - ratio * cbase) term, and if it does not
- happen, fold is able to apply the distributive law to obtain this form
- anyway. */
-
- if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
{
- /* Let's compute in trees and just return the result in AFF. This case
- should not be very common, and fold itself is not that bad either,
- so making the aff. functions more complicated to handle this case
- is not that urgent. */
- if (ratioi == 1)
- {
- delta = fold_build2 (MINUS_EXPR, uutype, ubase, cbase);
- expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
- }
- else if (ratioi == -1)
- {
- delta = fold_build2 (PLUS_EXPR, uutype, ubase, cbase);
- expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
- }
+ aff_tree cstep_aff;
+
+ if (common_type != uutype)
+ cstep_common = fold_convert (common_type, cstep);
else
- {
- delta = fold_build2 (MULT_EXPR, uutype, cbase, ratio);
- delta = fold_build2 (MINUS_EXPR, uutype, ubase, delta);
- expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
- expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
- }
+ cstep_common = cstep;
- aff->type = uutype;
- aff->n = 0;
- aff->offset = 0;
- aff->mask = 0;
- aff->rest = expr;
- return true;
+ tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
+ aff_combination_add (&cbase_aff, &cstep_aff);
}
- /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
- possible to compute ratioi. */
- gcc_assert (ratioi);
-
- tree_to_aff_combination (ubase, uutype, aff);
- tree_to_aff_combination (cbase, uutype, &cbase_aff);
- tree_to_aff_combination (expr, uutype, &expr_aff);
- aff_combination_scale (&cbase_aff, -ratioi);
- aff_combination_scale (&expr_aff, ratioi);
+ aff_combination_scale (&cbase_aff, double_int_neg (rat));
aff_combination_add (aff, &cbase_aff);
- aff_combination_add (aff, &expr_aff);
+ if (common_type != uutype)
+ aff_combination_convert (aff, uutype);
+
+ aff_combination_scale (&var_aff, rat);
+ aff_combination_add (aff, &var_aff);
return true;
}
get_computation_at (struct loop *loop,
struct iv_use *use, struct iv_cand *cand, tree at)
{
- struct affine_tree_combination aff;
+ aff_tree aff;
tree type = TREE_TYPE (use->iv->base);
if (!get_computation_aff (loop, use, cand, at, &aff))
static hashval_t
mbc_entry_hash (const void *entry)
{
- const struct mbc_entry *e = entry;
+ const struct mbc_entry *e = (const struct mbc_entry *) entry;
return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
}
static int
mbc_entry_eq (const void *entry1, const void *entry2)
{
- const struct mbc_entry *e1 = entry1;
- const struct mbc_entry *e2 = entry2;
+ const struct mbc_entry *e1 = (const struct mbc_entry *) entry1;
+ const struct mbc_entry *e2 = (const struct mbc_entry *) entry2;
return (e1->mode == e2->mode
&& e1->cst == e2->cst);
return cost;
}
-/* Returns true if multiplying by RATIO is allowed in address. */
+/* Returns true if multiplying by RATIO is allowed in an address. Test the
+ validity for a memory reference accessing memory of mode MODE. */
bool
-multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
{
#define MAX_RATIO 128
- static sbitmap valid_mult;
+ static sbitmap valid_mult[MAX_MACHINE_MODE];
- if (!valid_mult)
+ if (!valid_mult[mode])
{
rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
rtx addr;
HOST_WIDE_INT i;
- valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
- sbitmap_zero (valid_mult);
+ valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
+ sbitmap_zero (valid_mult[mode]);
addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
{
XEXP (addr, 1) = gen_int_mode (i, Pmode);
- if (memory_address_p (Pmode, addr))
- SET_BIT (valid_mult, i + MAX_RATIO);
+ if (memory_address_p (mode, addr))
+ SET_BIT (valid_mult[mode], i + MAX_RATIO);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " allowed multipliers:");
for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
- if (TEST_BIT (valid_mult, i + MAX_RATIO))
+ if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
fprintf (dump_file, " %d", (int) i);
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
return false;
- return TEST_BIT (valid_mult, ratio + MAX_RATIO);
+ return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
}
/* 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. The created memory accesses MODE.
-
+ variable is omitted. Compute the cost for a memory reference that accesses
+ a memory location of mode MEM_MODE.
+
TODO -- there must be some better way. This all is quite crude. */
-static unsigned
+static comp_cost
get_address_cost (bool symbol_present, bool var_present,
- unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
-{
- static bool initialized = false;
- static HOST_WIDE_INT rat, off;
- static HOST_WIDE_INT min_offset, max_offset;
- static unsigned costs[2][2][2][2];
- unsigned cost, acost;
- rtx seq, addr, base;
+ unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
+ enum machine_mode mem_mode)
+{
+ static bool initialized[MAX_MACHINE_MODE];
+ static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
+ static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
+ static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
+ unsigned cost, acost, complexity;
bool offset_p, ratio_p;
- rtx reg1;
HOST_WIDE_INT s_offset;
unsigned HOST_WIDE_INT mask;
unsigned bits;
- if (!initialized)
+ if (!initialized[mem_mode])
{
HOST_WIDE_INT i;
- initialized = true;
+ HOST_WIDE_INT start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
+ int old_cse_not_expected;
+ unsigned sym_p, var_p, off_p, rat_p, add_c;
+ rtx seq, addr, base;
+ rtx reg0, reg1;
+
+ initialized[mem_mode] = true;
reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
- for (i = 1; i <= 1 << 20; i <<= 1)
+ for (i = start; i <= 1 << 20; i <<= 1)
{
XEXP (addr, 1) = gen_int_mode (i, Pmode);
- if (!memory_address_p (Pmode, addr))
+ if (!memory_address_p (mem_mode, addr))
break;
}
- max_offset = i >> 1;
- off = max_offset;
+ max_offset[mem_mode] = i == start ? 0 : i >> 1;
+ off[mem_mode] = max_offset[mem_mode];
- for (i = 1; i <= 1 << 20; i <<= 1)
+ for (i = start; i <= 1 << 20; i <<= 1)
{
XEXP (addr, 1) = gen_int_mode (-i, Pmode);
- if (!memory_address_p (Pmode, addr))
+ if (!memory_address_p (mem_mode, addr))
break;
}
- min_offset = -(i >> 1);
+ min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "get_address_cost:\n");
- fprintf (dump_file, " min offset %d\n", (int) min_offset);
- fprintf (dump_file, " max offset %d\n", (int) max_offset);
+ fprintf (dump_file, " min offset %s %d\n",
+ GET_MODE_NAME (mem_mode),
+ (int) min_offset[mem_mode]);
+ fprintf (dump_file, " max offset %s %d\n",
+ GET_MODE_NAME (mem_mode),
+ (int) max_offset[mem_mode]);
}
- rat = 1;
+ rat[mem_mode] = 1;
for (i = 2; i <= MAX_RATIO; i++)
- if (multiplier_allowed_in_address_p (i))
+ if (multiplier_allowed_in_address_p (i, mem_mode))
{
- rat = i;
+ rat[mem_mode] = i;
break;
}
+
+ /* Compute the cost of various addressing modes. */
+ acost = 0;
+ reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+ reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
+
+ 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, Pmode, addr,
+ gen_int_mode (rat[mem_mode], Pmode));
+
+ if (var_p)
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+
+ if (sym_p)
+ {
+ base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
+ /* ??? We can run into trouble with some backends by presenting
+ it with symbols which havn'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, Pmode,
+ gen_rtx_fmt_ee (PLUS, Pmode,
+ base,
+ gen_int_mode (off[mem_mode],
+ Pmode)));
+ }
+ else if (off_p)
+ base = gen_int_mode (off[mem_mode], Pmode);
+ else
+ base = NULL_RTX;
+
+ if (base)
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, 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 (mem_mode, addr);
+ cse_not_expected = old_cse_not_expected;
+ seq = get_insns ();
+ end_sequence ();
+
+ acost = seq_cost (seq);
+ acost += address_cost (addr, mem_mode);
+
+ if (!acost)
+ acost = 1;
+ costs[mem_mode][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 (Pmode);
+ for (i = 0; i < 8; i++)
+ {
+ var_p = i & 1;
+ off_p = (i >> 1) & 1;
+ rat_p = (i >> 2) & 1;
+
+ acost = costs[mem_mode][0][1][off_p][rat_p] + 1;
+ if (var_p)
+ acost += add_c;
+
+ if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
+ costs[mem_mode][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 = costs[mem_mode][sym_p][var_p][off_p][rat_p];
+ fprintf (dump_file, "index costs %d\n", acost);
+ }
+ fprintf (dump_file, "\n");
+ }
}
bits = GET_MODE_BITSIZE (Pmode);
cost = 0;
offset_p = (s_offset != 0
- && min_offset <= s_offset && s_offset <= max_offset);
+ && min_offset[mem_mode] <= s_offset
+ && s_offset <= max_offset[mem_mode]);
ratio_p = (ratio != 1
- && multiplier_allowed_in_address_p (ratio));
+ && multiplier_allowed_in_address_p (ratio, mem_mode));
if (ratio != 1 && !ratio_p)
cost += multiply_by_cost (ratio, Pmode);
if (s_offset && !offset_p && !symbol_present)
- {
- cost += add_cost (Pmode);
- var_present = true;
- }
-
- acost = costs[symbol_present][var_present][offset_p][ratio_p];
- if (!acost)
- {
- int old_cse_not_expected;
- acost = 0;
-
- addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
- reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
- if (ratio_p)
- addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));
-
- if (var_present)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+ cost += add_cost (Pmode);
- if (symbol_present)
- {
- base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
- if (offset_p)
- base = gen_rtx_fmt_e (CONST, Pmode,
- gen_rtx_fmt_ee (PLUS, Pmode,
- base,
- gen_int_mode (off, Pmode)));
- }
- else if (offset_p)
- base = gen_int_mode (off, Pmode);
- else
- base = NULL_RTX;
-
- if (base)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, 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 (Pmode, addr);
- cse_not_expected = old_cse_not_expected;
- seq = get_insns ();
- end_sequence ();
-
- acost = seq_cost (seq);
- acost += address_cost (addr, Pmode);
-
- if (!acost)
- acost = 1;
- costs[symbol_present][var_present][offset_p][ratio_p] = acost;
- }
-
- return cost + acost;
+ acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
+ complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
+ return new_cost (cost + acost, complexity);
}
/* Estimates cost of forcing expression EXPR into a variable. */
-unsigned
+static comp_cost
force_expr_to_var_cost (tree expr)
{
static bool costs_initialized = false;
static unsigned symbol_cost;
static unsigned address_cost;
tree op0, op1;
- unsigned cost0, cost1, cost;
+ comp_cost cost0, cost1, cost;
enum machine_mode mode;
if (!costs_initialized)
{
- tree var = create_tmp_var_raw (integer_type_node, "test_var");
- rtx x = gen_rtx_MEM (DECL_MODE (var),
- gen_rtx_SYMBOL_REF (Pmode, "test_var"));
- tree addr;
tree type = build_pointer_type (integer_type_node);
+ tree var, addr;
+ rtx x;
- integer_cost = computation_cost (build_int_cst_type (integer_type_node,
- 2000));
-
- SET_DECL_RTL (var, x);
+ var = create_tmp_var_raw (integer_type_node, "test_var");
TREE_STATIC (var) = 1;
+ x = produce_memory_decl_rtl (var, NULL);
+ SET_DECL_RTL (var, x);
+
+ integer_cost = computation_cost (build_int_cst (integer_type_node,
+ 2000));
+
addr = build1 (ADDR_EXPR, type, var);
symbol_cost = computation_cost (addr) + 1;
address_cost
- = computation_cost (build2 (PLUS_EXPR, type,
+ = computation_cost (build2 (POINTER_PLUS_EXPR, type,
addr,
- build_int_cst_type (type, 2000))) + 1;
+ build_int_cst (sizetype, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "force_expr_to_var_cost:\n");
STRIP_NOPS (expr);
if (SSA_VAR_P (expr))
- return 0;
+ return zero_cost;
if (TREE_INVARIANT (expr))
{
if (TREE_CODE (expr) == INTEGER_CST)
- return integer_cost;
+ return new_cost (integer_cost, 0);
if (TREE_CODE (expr) == ADDR_EXPR)
{
if (TREE_CODE (obj) == VAR_DECL
|| TREE_CODE (obj) == PARM_DECL
|| TREE_CODE (obj) == RESULT_DECL)
- return symbol_cost;
+ return new_cost (symbol_cost, 0);
}
- return address_cost;
+ return new_cost (address_cost, 0);
}
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
STRIP_NOPS (op1);
if (is_gimple_val (op0))
- cost0 = 0;
+ cost0 = zero_cost;
else
cost0 = force_expr_to_var_cost (op0);
if (is_gimple_val (op1))
- cost1 = 0;
+ cost1 = zero_cost;
else
cost1 = force_expr_to_var_cost (op1);
default:
/* Just an arbitrary value, FIXME. */
- return target_spill_cost;
+ return new_cost (target_spill_cost, 0);
}
mode = TYPE_MODE (TREE_TYPE (expr));
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
- cost = add_cost (mode);
+ cost = new_cost (add_cost (mode), 0);
break;
case MULT_EXPR:
if (cst_and_fits_in_hwi (op0))
- cost = multiply_by_cost (int_cst_value (op0), mode);
+ cost = new_cost (multiply_by_cost (int_cst_value (op0), mode), 0);
else if (cst_and_fits_in_hwi (op1))
- cost = multiply_by_cost (int_cst_value (op1), mode);
+ cost = new_cost (multiply_by_cost (int_cst_value (op1), mode), 0);
else
- return target_spill_cost;
+ return new_cost (target_spill_cost, 0);
break;
default:
gcc_unreachable ();
}
- cost += cost0;
- cost += cost1;
+ cost = add_costs (cost, cost0);
+ cost = add_costs (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. */
- return cost < target_spill_cost ? cost : target_spill_cost;
+ if (cost.cost > target_spill_cost)
+ cost.cost = target_spill_cost;
+
+ return cost;
}
/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
invariants the computation depends on. */
-static unsigned
+static comp_cost
force_var_cost (struct ivopts_data *data,
tree expr, bitmap *depends_on)
{
to false if the corresponding part is missing. DEPENDS_ON is a set of the
invariants the computation depends on. */
-static unsigned
+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)
*var_present = true;
fd_ivopts_data = data;
walk_tree (&addr, find_depends, depends_on, NULL);
- return target_spill_cost;
+ return new_cost (target_spill_cost, 0);
}
*offset += bitpos / BITS_PER_UNIT;
{
*symbol_present = true;
*var_present = false;
- return 0;
+ return zero_cost;
}
*symbol_present = false;
*var_present = true;
- return 0;
+ return zero_cost;
}
/* Estimates cost of expressing difference of addresses E1 - E2 as
part is missing. DEPENDS_ON is a set of the invariants the computation
depends on. */
-static unsigned
+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;
- unsigned cost;
+ comp_cost cost;
gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
*offset += diff;
*symbol_present = false;
*var_present = false;
- return 0;
+ return zero_cost;
}
- if (e2 == integer_zero_node)
+ if (integer_zerop (e2))
return split_address_cost (data, TREE_OPERAND (e1, 0),
symbol_present, var_present, offset, depends_on);
*var_present = true;
cost = force_var_cost (data, e1, depends_on);
- cost += force_var_cost (data, e2, depends_on);
- cost += add_cost (Pmode);
+ cost = add_costs (cost, force_var_cost (data, e2, depends_on));
+ cost.cost += add_cost (Pmode);
return cost;
}
part is missing. DEPENDS_ON is a set of the invariants the computation
depends on. */
-static unsigned
+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)
{
- unsigned cost;
+ comp_cost cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
if (operand_equal_p (e1, e2, 0))
{
*var_present = false;
- return 0;
+ return zero_cost;
}
*var_present = true;
- if (zero_p (e2))
+ if (integer_zerop (e2))
return force_var_cost (data, e1, depends_on);
- if (zero_p (e1))
+ if (integer_zerop (e1))
{
cost = force_var_cost (data, e2, depends_on);
- cost += multiply_by_cost (-1, mode);
+ cost.cost += multiply_by_cost (-1, mode);
return cost;
}
cost = force_var_cost (data, e1, depends_on);
- cost += force_var_cost (data, e2, depends_on);
- cost += add_cost (mode);
+ cost = add_costs (cost, force_var_cost (data, e2, depends_on));
+ cost.cost += add_cost (mode);
return cost;
}
register. A set of invariants we depend on is stored in
DEPENDS_ON. AT is the statement at that the value is computed. */
-static unsigned
+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, tree at)
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
tree utype = TREE_TYPE (ubase), ctype;
- unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
+ unsigned HOST_WIDE_INT cstepi, offset = 0;
HOST_WIDE_INT ratio, aratio;
bool var_present, symbol_present;
- unsigned cost = 0, n_sums;
+ comp_cost cost;
+ unsigned n_sums;
+ double_int rat;
*depends_on = NULL;
/* Only consider real candidates. */
if (!cand->iv)
- return INFTY;
+ return infinite_cost;
cbase = cand->iv->base;
cstep = cand->iv->step;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
/* We do not have a precision to express the values of use. */
- return INFTY;
+ return infinite_cost;
}
if (address_p)
if (use->iv->base_object
&& cand->iv->base_object
&& !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
- return INFTY;
+ return infinite_cost;
}
if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
else
cstepi = 0;
- if (cst_and_fits_in_hwi (ustep)
- && cst_and_fits_in_hwi (cstep))
- {
- ustepi = int_cst_value (ustep);
-
- if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
- return INFTY;
- }
- else
- {
- tree rat;
-
- rat = constant_multiple_of (utype, ustep, cstep);
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ return infinite_cost;
- if (!rat)
- return INFTY;
-
- if (cst_and_fits_in_hwi (rat))
- ratio = int_cst_value (rat);
- else if (integer_onep (rat))
- ratio = 1;
- else if (integer_all_onesp (rat))
- ratio = -1;
- else
- return INFTY;
- }
+ if (double_int_fits_in_shwi_p (rat))
+ ratio = double_int_to_shwi (rat);
+ else
+ return infinite_cost;
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
if (cst_and_fits_in_hwi (cbase))
{
offset = - ratio * int_cst_value (cbase);
- cost += difference_cost (data,
- ubase, integer_zero_node,
- &symbol_present, &var_present, &offset,
- depends_on);
+ cost = difference_cost (data,
+ ubase, build_int_cst (utype, 0),
+ &symbol_present, &var_present, &offset,
+ depends_on);
}
else if (ratio == 1)
{
- cost += difference_cost (data,
- ubase, cbase,
- &symbol_present, &var_present, &offset,
- depends_on);
+ cost = difference_cost (data,
+ ubase, cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
}
else
{
- cost += force_var_cost (data, cbase, depends_on);
- cost += add_cost (TYPE_MODE (ctype));
- cost += difference_cost (data,
- ubase, integer_zero_node,
- &symbol_present, &var_present, &offset,
- depends_on);
+ cost = force_var_cost (data, cbase, depends_on);
+ cost.cost += add_cost (TYPE_MODE (ctype));
+ cost = add_costs (cost,
+ difference_cost (data,
+ ubase, build_int_cst (utype, 0),
+ &symbol_present, &var_present,
+ &offset, depends_on));
}
/* If we are after the increment, the value of the candidate is higher by
(symbol/var/const parts may be omitted). If we are looking for an address,
find the cost of addressing this. */
if (address_p)
- return cost + get_address_cost (symbol_present, var_present, offset, ratio);
+ return add_costs (cost, get_address_cost (symbol_present, var_present,
+ offset, ratio,
+ TYPE_MODE (TREE_TYPE (*use->op_p))));
/* Otherwise estimate the costs for computing the expression. */
aratio = ratio > 0 ? ratio : -ratio;
if (!symbol_present && !var_present && !offset)
{
if (ratio != 1)
- cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
+ cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
return cost;
}
if (aratio != 1)
- cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
+ cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
n_sums = 1;
if (var_present
&& (symbol_present || offset))
n_sums++;
- return cost + n_sums * add_cost (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.cost += n_sums * add_cost (TYPE_MODE (ctype));
+ return cost;
fallback:
{
tree comp = get_computation_at (data->current_loop, use, cand, at);
if (!comp)
- return INFTY;
+ return infinite_cost;
if (address_p)
comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
- return computation_cost (comp);
+ return new_cost (computation_cost (comp), 0);
}
}
register. A set of invariants we depend on is stored in
DEPENDS_ON. */
-static unsigned
+static comp_cost
get_computation_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
bool address_p, bitmap *depends_on)
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost;
+ comp_cost cost;
/* The simple case first -- if we need to express value of the preserved
original biv, the cost is 0. This also prevents us from counting the
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
- set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
+ set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE);
return true;
}
cost = get_computation_cost (data, use, cand, false, &depends_on);
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
- return cost != INFTY;
+ return !infinite_cost_p (cost);
}
/* Determines cost of basing replacement of USE on CAND in an address. */
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
+ comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on);
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
- return cost != INFTY;
+ return !infinite_cost_p (cost);
}
-/* Computes value of induction variable IV in iteration NITER. */
+/* Computes value of candidate CAND at position AT in iteration NITER, and
+ stores it to VAL. */
-static tree
-iv_value (struct iv *iv, tree niter)
+static void
+cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter,
+ aff_tree *val)
{
- tree val;
+ aff_tree step, delta, nit;
+ struct iv *iv = cand->iv;
tree type = TREE_TYPE (iv->base);
- niter = fold_convert (type, niter);
- val = fold_build2 (MULT_EXPR, type, iv->step, niter);
-
- return fold_build2 (PLUS_EXPR, type, iv->base, val);
-}
-
-/* Computes value of candidate CAND at position AT in iteration NITER. */
-
-static tree
-cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
-{
- tree val = iv_value (cand->iv, niter);
- tree type = TREE_TYPE (cand->iv->base);
-
+ tree_to_aff_combination (iv->step, type, &step);
+ tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
+ aff_combination_convert (&nit, type);
+ aff_combination_mult (&nit, &step, &delta);
if (stmt_after_increment (loop, cand, at))
- val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
+ aff_combination_add (&delta, &step);
- return val;
+ tree_to_aff_combination (iv->base, type, val);
+ aff_combination_add (val, &delta);
}
/* Returns period of induction variable iv. */
{
basic_block ex_bb;
edge exit;
- struct tree_niter_desc *niter;
- tree nit, nit_type;
- tree wider_type, period, per_type;
+ tree nit, period;
struct loop *loop = data->current_loop;
-
+ aff_tree bnd;
+ double_int period_value, max_niter;
+
if (TREE_CODE (cand->iv->step) != INTEGER_CST)
return false;
if (flow_bb_inside_loop_p (loop, exit->dest))
return false;
- niter = niter_for_exit (data, exit);
- if (!niter
- || !zero_p (niter->may_be_zero))
+ nit = niter_for_exit (data, exit);
+ if (!nit)
return false;
- nit = niter->niter;
- nit_type = TREE_TYPE (nit);
-
/* Determine whether we may use the variable to test whether niter iterations
elapsed. This is the case iff the period of the induction variable is
greater than the number of iterations. */
period = iv_period (cand->iv);
if (!period)
return false;
- per_type = TREE_TYPE (period);
-
- wider_type = TREE_TYPE (period);
- if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
- wider_type = per_type;
- else
- wider_type = nit_type;
- if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
- fold_convert (wider_type, period),
- fold_convert (wider_type, nit))))
+ /* Compare the period with the estimate on the number of iterations of the
+ loop. */
+ if (!estimated_loop_iterations (loop, true, &max_niter))
+ return false;
+ period_value = tree_to_double_int (period);
+ if (double_int_ucmp (period_value, max_niter) <= 0)
return false;
- *bound = cand_value_at (loop, cand, use->stmt, nit);
+ cand_value_at (loop, cand, use->stmt, nit, &bnd);
+ *bound = aff_combination_to_tree (&bnd);
return true;
}
determine_use_iv_cost_condition (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree bound = NULL_TREE, op, cond;
- bitmap depends_on = NULL;
- unsigned cost;
+ 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;
+ bool ok;
/* Only consider real candidates. */
if (!cand->iv)
{
- set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
+ set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE);
return false;
}
+ /* Try iv elimination. */
if (may_eliminate_iv (data, use, cand, &bound))
{
- cost = force_var_cost (data, bound, &depends_on);
-
- set_use_iv_cost (data, use, cand, cost, depends_on, bound);
- return cost != INFTY;
+ elim_cost = force_var_cost (data, bound, &depends_on_elim);
+ /* The bound is a loop invariant, so it will be only computed
+ once. */
+ elim_cost.cost /= AVG_LOOP_NITER (data->current_loop);
}
+ else
+ elim_cost = infinite_cost;
- /* The induction variable elimination failed; just express the original
- giv. If it is compared with an invariant, note that we cannot get
- rid of it. */
- cost = get_computation_cost (data, use, cand, false, &depends_on);
+ /* 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->op_p, NULL, NULL, NULL, &cmp_iv);
+ gcc_assert (ok);
+
+ express_cost = get_computation_cost (data, use, cand, false,
+ &depends_on_express);
+ fd_ivopts_data = data;
+ walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
- cond = *use->op_p;
- if (TREE_CODE (cond) != SSA_NAME)
+ /* Choose the better approach. */
+ if (compare_costs (elim_cost, express_cost) < 0)
{
- op = TREE_OPERAND (cond, 0);
- if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step))
- op = TREE_OPERAND (cond, 1);
- if (TREE_CODE (op) == SSA_NAME)
- {
- op = get_iv (data, op)->base;
- fd_ivopts_data = data;
- walk_tree (&op, find_depends, &depends_on, NULL);
- }
+ cost = elim_cost;
+ depends_on = depends_on_elim;
+ depends_on_elim = NULL;
+ }
+ else
+ {
+ cost = express_cost;
+ depends_on = depends_on_express;
+ depends_on_express = NULL;
+ bound = NULL_TREE;
}
- set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
- return cost != INFTY;
+ set_use_iv_cost (data, use, cand, cost, depends_on, bound);
+
+ if (depends_on_elim)
+ BITMAP_FREE (depends_on_elim);
+ if (depends_on_express)
+ BITMAP_FREE (depends_on_express);
+
+ return !infinite_cost_p (cost);
}
/* Determines cost of basing replacement of USE on CAND. Returns false
use = iv_use (data, i);
fprintf (dump_file, "Use %d:\n", i);
- fprintf (dump_file, " cand\tcost\tdepends on\n");
+ fprintf (dump_file, " cand\tcost\tcompl.\tdepends on\n");
for (j = 0; j < use->n_map_members; j++)
{
if (!use->cost_map[j].cand
- || use->cost_map[j].cost == INFTY)
+ || infinite_cost_p (use->cost_map[j].cost))
continue;
- fprintf (dump_file, " %d\t%d\t",
+ fprintf (dump_file, " %d\t%d\t%d\t",
use->cost_map[j].cand->id,
- use->cost_map[j].cost);
+ use->cost_map[j].cost.cost,
+ use->cost_map[j].cost.complexity);
if (use->cost_map[j].depends_on)
bitmap_print (dump_file,
use->cost_map[j].depends_on, "","");
static void
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
- unsigned cost_base, cost_step;
+ comp_cost cost_base;
+ unsigned cost, cost_step;
tree base;
if (!cand->iv)
cost_base = force_var_cost (data, base, NULL);
cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
- cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
+ cost = cost_step + cost_base.cost / AVG_LOOP_NITER (current_loop);
- /* Prefer the original iv unless we may gain something by replacing it;
- this is not really relevant for artificial ivs created by other
- passes. */
- if (cand->pos == IP_ORIGINAL
- && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
- cand->cost--;
+ /* Prefer the original ivs unless we may gain something by replacing it.
+ The reason is to makee debugging simpler; so this is not relevant for
+ artificial ivs created by other optimization passes. */
+ if (cand->pos != IP_ORIGINAL
+ || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
+ cost++;
/* Prefer not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
if (cand->pos == IP_END
&& empty_block_p (ip_end_pos (data->current_loop)))
- cand->cost++;
+ cost++;
+
+ cand->cost = cost;
}
/* Determines costs of computation of the candidates. */
fprintf (dump_file, " %d\t%d\n", i, cand->cost);
}
-if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n");
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\n");
}
/* Calculates cost for having SIZE induction variables. */
static unsigned
ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
{
- return global_cost_for_size (size, data->regs_used, n_iv_uses (data));
+ /* We add size to the cost, so that we prefer eliminating ivs
+ if possible. */
+ return size + estimate_reg_pressure_cost (size, data->regs_used);
}
/* For each size of the induction variable set determine the penalty. */
{
fprintf (dump_file, "Global costs:\n");
fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
- fprintf (dump_file, " target_small_cost %d\n", target_small_cost);
- fprintf (dump_file, " target_pres_cost %d\n", target_pres_cost);
+ fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost);
fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
}
static bool
cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
{
+ int cmp;
+
if (!a)
return false;
if (!b)
return true;
- if (a->cost < b->cost)
+ cmp = compare_costs (a->cost, b->cost);
+ if (cmp < 0)
return true;
- if (a->cost > b->cost)
+ if (cmp > 0)
return false;
/* In case the costs are the same, prefer the cheaper candidate. */
static void
iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned cost = 0;
-
- cost += ivs->cand_use_cost;
- cost += ivs->cand_cost;
- cost += ivopts_global_cost_for_size (data, ivs->n_regs);
+ comp_cost cost = ivs->cand_use_cost;
+ cost.cost += ivs->cand_cost;
+ cost.cost += ivopts_global_cost_for_size (data, ivs->n_regs);
ivs->cost = cost;
}
iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
}
- ivs->cand_use_cost -= cp->cost;
+ ivs->cand_use_cost = sub_costs (ivs->cand_use_cost, cp->cost);
iv_ca_set_remove_invariants (ivs, cp->depends_on);
iv_ca_recount_cost (data, ivs);
iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
}
- ivs->cand_use_cost += cp->cost;
+ ivs->cand_use_cost = add_costs (ivs->cand_use_cost, cp->cost);
iv_ca_set_add_invariants (ivs, cp->depends_on);
iv_ca_recount_cost (data, ivs);
}
/* Get cost for assignment IVS. */
-static unsigned
+static comp_cost
iv_ca_cost (struct iv_ca *ivs)
{
- return (ivs->bad_uses ? INFTY : ivs->cost);
+ return (ivs->bad_uses ? infinite_cost : ivs->cost);
}
/* Returns true if all dependences of CP are among invariants in IVS. */
nw->cands = BITMAP_ALLOC (NULL);
nw->n_cands = 0;
nw->n_regs = 0;
- nw->cand_use_cost = 0;
+ nw->cand_use_cost = zero_cost;
nw->cand_cost = 0;
nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
- nw->cost = 0;
+ nw->cost = zero_cost;
return nw;
}
{
const char *pref = " invariants ";
unsigned i;
+ comp_cost cost = iv_ca_cost (ivs);
- fprintf (file, " cost %d\n", iv_ca_cost (ivs));
+ fprintf (file, " cost %d (complexity %d)\n", cost.cost, cost.complexity);
bitmap_print (file, ivs->cands, " candidates ","\n");
for (i = 1; i <= data->max_inv_id; i++)
new set, and store differences in DELTA. Number of induction variables
in the new set is stored to N_IVS. */
-static unsigned
+static comp_cost
iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta,
unsigned *n_ivs)
{
- unsigned i, cost;
+ unsigned i;
+ comp_cost cost;
struct iv_use *use;
struct cost_pair *old_cp, *new_cp;
/* Try narrowing set IVS by removing CAND. Return the cost of
the new set and store the differences in DELTA. */
-static unsigned
+static comp_cost
iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta)
{
struct cost_pair *old_cp, *new_cp, *cp;
bitmap_iterator bi;
struct iv_cand *cnd;
- unsigned cost;
+ comp_cost cost;
*delta = NULL;
for (i = 0; i < n_iv_uses (data); i++)
if (!new_cp)
{
iv_ca_delta_free (delta);
- return INFTY;
+ return infinite_cost;
}
*delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
from to EXCEPT_CAND from it. Return cost of the new set, and store
differences in DELTA. */
-static unsigned
+static comp_cost
iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *except_cand, struct iv_ca_delta **delta)
{
bitmap_iterator bi;
struct iv_ca_delta *act_delta, *best_delta;
- unsigned i, best_cost, acost;
+ unsigned i;
+ comp_cost best_cost, acost;
struct iv_cand *cand;
best_delta = NULL;
acost = iv_ca_narrow (data, ivs, cand, &act_delta);
- if (acost < best_cost)
+ if (compare_costs (acost, best_cost) < 0)
{
best_cost = acost;
iv_ca_delta_free (&best_delta);
try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use)
{
- unsigned best_cost, act_cost;
+ comp_cost best_cost, act_cost;
unsigned i;
bitmap_iterator bi;
struct iv_cand *cand;
iv_ca_set_no_cp (data, ivs, use);
}
- /* First try important candidates. Only if it fails, try the specific ones.
- Rationale -- in loops with many variables the best choice often is to use
- just one generic biv. If we added here many ivs specific to the uses,
- the optimization algorithm later would be likely to get stuck in a local
- minimum, thus causing us to create too many ivs. The approach from
- few ivs to more seems more likely to be successful -- starting from few
- ivs, replacing an expensive use by a specific iv should always be a
- win. */
+ /* First try important candidates not based on any memory object. Only if
+ this fails, try the specific ones. Rationale -- in loops with many
+ variables the best choice often is to use just one generic biv. If we
+ added here many ivs specific to the uses, the optimization algorithm later
+ would be likely to get stuck in a local minimum, thus causing us to create
+ too many ivs. The approach from few ivs to more seems more likely to be
+ successful -- starting from few ivs, replacing an expensive use by a
+ specific iv should always be a win. */
EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
{
cand = iv_cand (data, i);
+ if (cand->iv->base_object != NULL_TREE)
+ continue;
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
- if (act_cost < best_cost)
+ if (compare_costs (act_cost, best_cost) < 0)
{
best_cost = act_cost;
iv_ca_delta_free (&act_delta);
}
- if (best_cost == INFTY)
+ if (infinite_cost_p (best_cost))
{
for (i = 0; i < use->n_map_members; i++)
{
continue;
/* Already tried this. */
- if (cand->important)
+ if (cand->important && cand->iv->base_object == NULL_TREE)
continue;
if (iv_ca_cand_used_p (ivs, cand))
act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
cp, act_delta);
- if (act_cost < best_cost)
+ if (compare_costs (act_cost, best_cost) < 0)
{
best_cost = act_cost;
iv_ca_delta_commit (data, ivs, best_delta, true);
iv_ca_delta_free (&best_delta);
- return (best_cost != INFTY);
+ return !infinite_cost_p (best_cost);
}
/* Finds an initial assignment of candidates to uses. */
static bool
try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
+ unsigned i, n_ivs;
+ comp_cost acost, best_cost = iv_ca_cost (ivs);
struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
struct iv_cand *cand;
act_delta = iv_ca_delta_join (act_delta, tmp_delta);
}
- if (acost < best_cost)
+ if (compare_costs (acost, best_cost) < 0)
{
best_cost = acost;
iv_ca_delta_free (&best_delta);
}
iv_ca_delta_commit (data, ivs, best_delta, true);
- gcc_assert (best_cost == iv_ca_cost (ivs));
+ gcc_assert (compare_costs (best_cost, iv_ca_cost (ivs)) == 0);
iv_ca_delta_free (&best_delta);
return true;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
+ {
+ comp_cost cost = iv_ca_cost (set);
+ fprintf (dump_file, "Final cost %d (complexity %d)\n\n", cost.cost, cost.complexity);
+ }
for (i = 0; i < n_iv_uses (data); i++)
{
}
gimple_add_tmp_var (cand->var_before);
- add_referenced_tmp_var (cand->var_before);
+ add_referenced_var (cand->var_before);
base = unshare_expr (cand->iv->base);
{
if (TREE_CODE (stmt) == PHI_NODE)
{
- if (!including_defined_name)
- {
- /* Prevent the ssa name defined by the statement from being removed. */
- SET_PHI_RESULT (stmt, NULL);
- }
- remove_phi_node (stmt, NULL_TREE);
+ remove_phi_node (stmt, NULL_TREE, including_defined_name);
}
else
{
block_stmt_iterator bsi = bsi_for_stmt (stmt);
bsi_remove (&bsi, true);
+ release_defs (stmt);
}
}
struct iv_use *use, struct iv_cand *cand)
{
tree comp;
- tree op, stmts, tgt, ass;
- block_stmt_iterator bsi, pbsi;
+ tree op, tgt, ass;
+ block_stmt_iterator bsi;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
tree step, ctype, utype;
enum tree_code incr_code = PLUS_EXPR;
- gcc_assert (TREE_CODE (use->stmt) == MODIFY_EXPR);
- gcc_assert (TREE_OPERAND (use->stmt, 0) == cand->var_after);
+ gcc_assert (TREE_CODE (use->stmt) == GIMPLE_MODIFY_STMT);
+ gcc_assert (GIMPLE_STMT_OPERAND (use->stmt, 0) == cand->var_after);
step = cand->iv->step;
ctype = TREE_TYPE (step);
computations in the loop -- otherwise, the computation
we rely upon may be removed in remove_unused_ivs,
thus leading to ICE. */
- op = TREE_OPERAND (use->stmt, 1);
+ op = GIMPLE_STMT_OPERAND (use->stmt, 1);
if (TREE_CODE (op) == PLUS_EXPR
- || TREE_CODE (op) == MINUS_EXPR)
+ || TREE_CODE (op) == MINUS_EXPR
+ || TREE_CODE (op) == POINTER_PLUS_EXPR)
{
if (TREE_OPERAND (op, 0) == cand->var_before)
op = TREE_OPERAND (op, 1);
- else if (TREE_CODE (op) == PLUS_EXPR
+ else if (TREE_CODE (op) != MINUS_EXPR
&& TREE_OPERAND (op, 1) == cand->var_before)
op = TREE_OPERAND (op, 0);
else
unshare_expr (step)));
}
else
- comp = get_computation (data->current_loop, use, cand);
+ {
+ comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
+ }
switch (TREE_CODE (use->stmt))
{
if (name_info (data, tgt)->preserve_biv)
return;
- pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
- while (!bsi_end_p (pbsi)
- && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
- {
- bsi = pbsi;
- bsi_next (&pbsi);
- }
+ bsi = bsi_after_labels (bb_for_stmt (use->stmt));
break;
- case MODIFY_EXPR:
- tgt = TREE_OPERAND (use->stmt, 0);
+ case GIMPLE_MODIFY_STMT:
+ tgt = GIMPLE_STMT_OPERAND (use->stmt, 0);
bsi = bsi_for_stmt (use->stmt);
break;
gcc_unreachable ();
}
- op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
+ op = force_gimple_operand_bsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
+ true, BSI_SAME_STMT);
if (TREE_CODE (use->stmt) == PHI_NODE)
{
- if (stmts)
- bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
- ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
- bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
+ ass = build_gimple_modify_stmt (tgt, op);
+ bsi_insert_before (&bsi, ass, BSI_SAME_STMT);
remove_statement (use->stmt, false);
SSA_NAME_DEF_STMT (tgt) = ass;
}
else
- {
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
- TREE_OPERAND (use->stmt, 1) = op;
- }
+ GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
}
/* Replaces ssa name in index IDX by its basic variable. Callback for
}
if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
- return unshare_expr (sv);
+ return aref;
if (!var)
return NULL_TREE;
}
var = SSA_NAME_VAR (var);
- tag = var_ann (var)->symbol_mem_tag;
+ tag = symbol_mem_tag (var);
gcc_assert (tag != NULL_TREE);
return tag;
}
if (!DECL_P (var))
return NULL_TREE;
- tag = var_ann (var)->symbol_mem_tag;
+ tag = symbol_mem_tag (var);
if (tag)
return tag;
rewrite_use_address (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- struct affine_tree_combination aff;
+ aff_tree aff;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
tree ref;
+ bool ok;
- get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+ ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+ gcc_assert (ok);
unshare_aff_combination (&aff);
ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
rewrite_use_compare (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp;
- tree *op_p, cond, op, stmts, bound;
+ tree comp, *var_p, op, bound;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
enum tree_code compare;
struct cost_pair *cp = get_use_iv_cost (data, use, cand);
-
+ bool ok;
+
bound = cp->value;
if (bound)
{
tree var_type = TREE_TYPE (var);
compare = iv_elimination_compare (data, use);
- bound = fold_convert (var_type, bound);
- op = force_gimple_operand (unshare_expr (bound), &stmts,
- true, NULL_TREE);
-
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ bound = unshare_expr (fold_convert (var_type, bound));
+ op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE,
+ true, BSI_SAME_STMT);
*use->op_p = build2 (compare, boolean_type_node, var, op);
- update_stmt (use->stmt);
return;
}
/* The induction variable elimination failed; just express the original
giv. */
comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
- cond = *use->op_p;
- op_p = &TREE_OPERAND (cond, 0);
- if (TREE_CODE (*op_p) != SSA_NAME
- || zero_p (get_iv (data, *op_p)->step))
- op_p = &TREE_OPERAND (cond, 1);
-
- op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
-
- *op_p = op;
-}
-
-/* Ensure that operand *OP_P may be used at the end of EXIT without
- violating loop closed ssa form. */
-
-static void
-protect_loop_closed_ssa_form_use (edge exit, use_operand_p op_p)
-{
- basic_block def_bb;
- struct loop *def_loop;
- tree phi, use;
-
- use = USE_FROM_PTR (op_p);
- if (TREE_CODE (use) != SSA_NAME)
- return;
-
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
- if (!def_bb)
- return;
-
- def_loop = def_bb->loop_father;
- if (flow_bb_inside_loop_p (def_loop, exit->dest))
- return;
-
- /* Try finding a phi node that copies the value out of the loop. */
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
- if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == use)
- break;
-
- if (!phi)
- {
- /* Create such a phi node. */
- tree new_name = duplicate_ssa_name (use, NULL);
-
- phi = create_phi_node (new_name, exit->dest);
- SSA_NAME_DEF_STMT (new_name) = phi;
- add_phi_arg (phi, use, exit);
- }
-
- SET_USE (op_p, PHI_RESULT (phi));
-}
-
-/* Ensure that operands of STMT may be used at the end of EXIT without
- violating loop closed ssa form. */
-
-static void
-protect_loop_closed_ssa_form (edge exit, tree stmt)
-{
- ssa_op_iter iter;
- use_operand_p use_p;
-
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- protect_loop_closed_ssa_form_use (exit, use_p);
-}
-
-/* STMTS compute a value of a phi argument OP on EXIT of a loop. Arrange things
- so that they are emitted on the correct place, and so that the loop closed
- ssa form is preserved. */
-
-void
-compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
-{
- tree_stmt_iterator tsi;
- block_stmt_iterator bsi;
- tree phi, stmt, def, next;
-
- if (!single_pred_p (exit->dest))
- split_loop_exit_edge (exit);
-
- /* Ensure there is label in exit->dest, so that we can
- insert after it. */
- tree_block_label (exit->dest);
- bsi = bsi_after_labels (exit->dest);
-
- if (TREE_CODE (stmts) == STATEMENT_LIST)
- {
- for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
- {
- tree stmt = tsi_stmt (tsi);
- bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
- protect_loop_closed_ssa_form (exit, stmt);
- }
- }
- else
- {
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
- protect_loop_closed_ssa_form (exit, stmts);
- }
-
- if (!op)
- return;
-
- for (phi = phi_nodes (exit->dest); phi; phi = next)
- {
- next = PHI_CHAIN (phi);
+ ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
+ gcc_assert (ok);
- if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == op)
- {
- def = PHI_RESULT (phi);
- remove_statement (phi, false);
- stmt = build2 (MODIFY_EXPR, TREE_TYPE (op),
- def, op);
- SSA_NAME_DEF_STMT (def) = stmt;
- bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
- }
- }
+ *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
+ true, BSI_SAME_STMT);
}
/* Rewrites USE using candidate CAND. */
static void
-rewrite_use (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
{
+ push_stmt_changes (&use->stmt);
+
switch (use->type)
{
case USE_NONLINEAR_EXPR:
default:
gcc_unreachable ();
}
- mark_new_vars_to_rename (use->stmt);
+
+ pop_stmt_changes (&use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
info = ver_info (data, j);
if (info->iv
- && !zero_p (info->iv->step)
+ && !integer_zerop (info->iv->step)
&& !info->inv_id
&& !info->iv->have_use_for
&& !info->preserve_biv)
bitmap_iterator bi;
tree obj;
- htab_empty (data->niters);
+ if (data->niters)
+ {
+ pointer_map_destroy (data->niters);
+ data->niters = NULL;
+ }
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
free (data->version_info);
BITMAP_FREE (data->relevant);
BITMAP_FREE (data->important_candidates);
- htab_delete (data->niters);
VEC_free (tree, heap, decl_rtl_to_reset);
VEC_free (iv_use_p, heap, data->iv_uses);
struct iv_ca *iv_ca;
edge exit;
+ gcc_assert (!data->niters);
data->current_loop = loop;
if (dump_file && (dump_flags & TDF_DETAILS))
return changed;
}
-/* Main entry point. Optimizes induction variables in LOOPS. */
+/* Main entry point. Optimizes induction variables in loops. */
void
-tree_ssa_iv_optimize (struct loops *loops)
+tree_ssa_iv_optimize (void)
{
struct loop *loop;
struct ivopts_data data;
+ loop_iterator li;
tree_ssa_iv_optimize_init (&data);
/* Optimize the loops starting with the innermost ones. */
- loop = loops->tree_root;
- while (loop->inner)
- loop = loop->inner;
-
- /* Scan the loops, inner ones first. */
- while (loop != loops->tree_root)
+ FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
if (dump_file && (dump_flags & TDF_DETAILS))
flow_loop_dump (loop, dump_file, NULL, 1);
tree_ssa_iv_optimize_loop (&data, loop);
-
- if (loop->next)
- {
- loop = loop->next;
- while (loop->inner)
- loop = loop->inner;
- }
- else
- loop = loop->outer;
}
tree_ssa_iv_optimize_finalize (&data);
OSDN Git Service
