/* 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
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;
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. */
contains_abnormal_ssa_name_p (tree expr)
{
enum tree_code code;
- enum tree_code_class class;
+ enum tree_code_class codeclass;
if (!expr)
return false;
code = TREE_CODE (expr);
- class = TREE_CODE_CLASS (code);
+ codeclass = TREE_CODE_CLASS (code);
if (code == SSA_NAME)
return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
idx_contains_abnormal_ssa_name_p,
NULL);
- switch (class)
+ switch (codeclass)
{
case tcc_binary:
case tcc_comparison:
return false;
}
-/* Element of the table in that we cache the numbers of iterations obtained
- from exits of the loop. */
-
-struct nfe_cache_elt
-{
- /* The edge for that the number of iterations is cached. */
- edge exit;
-
- /* Number of iterations corresponding to this exit, or NULL if it cannot be
- determined. */
- tree niter;
-};
-
-/* Hash function for nfe_cache_elt E. */
-
-static hashval_t
-nfe_hash (const void *e)
-{
- const struct nfe_cache_elt *elt = e;
-
- return htab_hash_pointer (elt->exit);
-}
-
-/* Equality function for nfe_cache_elt E1 and edge E2. */
-
-static int
-nfe_eq (const void *e1, const void *e2)
-{
- const struct nfe_cache_elt *elt1 = e1;
-
- return elt1->exit == e2;
-}
-
/* Returns tree describing number of iterations determined from
EXIT of DATA->current_loop, or NULL if something goes wrong. */
static tree
niter_for_exit (struct ivopts_data *data, edge exit)
{
- struct nfe_cache_elt *nfe_desc;
struct tree_niter_desc desc;
- PTR *slot;
-
- slot = htab_find_slot_with_hash (data->niters, exit,
- htab_hash_pointer (exit),
- INSERT);
+ tree niter;
+ void **slot;
- if (!*slot)
+ if (!data->niters)
{
- nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
- nfe_desc->exit = exit;
+ data->niters = pointer_map_create ();
+ slot = NULL;
+ }
+ else
+ 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
overlapping life ranges for them (PR 27283). */
if (number_of_iterations_exit (data->current_loop,
exit, &desc, true)
- && zero_p (desc.may_be_zero)
+ && integer_zerop (desc.may_be_zero)
&& !contains_abnormal_ssa_name_p (desc.niter))
- nfe_desc->niter = desc.niter;
+ niter = desc.niter;
else
- nfe_desc->niter = NULL_TREE;
+ niter = NULL_TREE;
+
+ *pointer_map_insert (data->niters, exit) = niter;
}
else
- nfe_desc = *slot;
+ niter = (tree) *slot;
- return nfe_desc->niter;
+ return niter;
}
/* Returns tree describing number of iterations determined from
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
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);
+ /* 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);
+ return integer_zerop (iv.step) ? NULL_TREE : iv.step;
}
/* Finds basic ivs. */
return use;
}
- if (zero_p (iv->step))
+ if (integer_zerop (iv->step))
{
record_invariant (data, op, true);
return NULL;
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;
+ /* 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;
- const_iv.step = NULL_TREE;
+ zero = integer_zero_node;
+ const_iv.step = integer_zero_node;
- if (TREE_CODE (*cond_p) != SSA_NAME
- && !COMPARISON_CLASS_P (*cond_p))
- return;
-
- 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);
+
+end:
+ if (control_var)
+ *control_var = op0;;
+ if (iv_var)
+ *iv_var = iv0;;
+ if (bound)
+ *bound = op1;
+ if (iv_bound)
+ *iv_bound = iv1;
- if (zero_p (iv0->step) && zero_p (iv1->step))
+ 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);
}
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_base, iv_step, lbound, off;
struct loop *loop = dta->ivopts_data->current_loop;
ARRAY_REF path below. */
*idx = iv->base;
- if (!iv->step)
+ if (integer_zerop (iv->step))
return true;
if (TREE_CODE (base) == ARRAY_REF)
}
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)
{
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;
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);
iv = get_iv (data, lhs);
- if (iv && !zero_p (iv->step))
+ if (iv && !integer_zerop (iv->step))
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 (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);
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);
}
}
{
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;
if (TREE_CODE (bot) != INTEGER_CST)
return false;
- p0 = double_int_sext (tree_to_double_int (bot), precision);
- p1 = double_int_sext (tree_to_double_int (top), precision);
+ 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),
}
}
-/* 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);
-}
-
-/* Convert COMB to TYPE. */
-
-static void
-aff_combination_convert (tree type, struct affine_tree_combination *comb)
-{
- unsigned prec = TYPE_PRECISION (type);
- unsigned i;
-
- /* If the precision of both types is the same, it suffices to change the type
- of the whole combination -- the elements are allowed to have another type
- equivalent wrto STRIP_NOPS. */
- if (prec == TYPE_PRECISION (comb->type))
- {
- comb->type = type;
- return;
- }
-
- comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
- comb->offset = comb->offset & comb->mask;
-
- /* The type of the elements can be different from comb->type only as
- much as what STRIP_NOPS would remove. We can just directly cast
- to TYPE. */
- for (i = 0; i < comb->n; i++)
- comb->elts[i] = fold_convert (type, comb->elts[i]);
- if (comb->rest)
- comb->rest = fold_convert (type, comb->rest);
-
- comb->type = type;
-}
-
-/* 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;
- }
- 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);
-}
-
-/* Makes tree from the affine combination COMB. */
-
-static tree
-aff_combination_to_tree (struct affine_tree_combination *comb)
-{
- tree type = comb->type;
- tree expr = comb->rest;
- unsigned i;
- unsigned HOST_WIDE_INT off, sgn;
-
- if (comb->n == 0 && comb->offset == 0)
- {
- if (expr)
- {
- /* Handle the special case produced by get_computation_aff when
- the type does not fit in HOST_WIDE_INT. */
- return fold_convert (type, expr);
- }
- else
- return build_int_cst (type, 0);
- }
-
- 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)
- {
- /* Offset is negative. */
- off = (-comb->offset) & comb->mask;
- sgn = comb->mask;
- }
- else
- {
- off = comb->offset;
- sgn = 1;
- }
- return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
- comb->mask);
-}
-
-/* Folds EXPR using the affine expressions framework. */
-
-static tree
-fold_affine_expr (tree expr)
-{
- tree type = TREE_TYPE (expr);
- struct affine_tree_combination comb;
-
- if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT)
- return expr;
-
- tree_to_aff_combination (expr, type, &comb);
- return aff_combination_to_tree (&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
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;
+ 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;
- }
-
- 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;
- }
-
- ratio = build_int_cst_type (uutype, ratioi);
+ cbase = fold_convert (uutype, cbase);
+ var = fold_convert (uutype, var);
}
- else
- {
- if (!constant_multiple_of (ustep_orig, cstep_orig, &rat))
- return false;
- ratio = double_int_to_tree (uutype, rat);
- /* Ratioi is only used to detect special cases when the multiplicative
- factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may
- set it to 0. */
- if (double_int_fits_in_shwi_p (rat))
- ratioi = double_int_to_shwi (rat);
- else
- ratioi = 0;
- }
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ 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
anyway. */
common_type = determine_common_wider_type (&ubase, &cbase);
- /* We may need to shift the value if we are after the increment. */
- if (stmt_after_increment (loop, cand, at))
- {
- if (uutype != common_type)
- cstep = fold_convert (common_type, cstep);
- cbase = fold_build2 (PLUS_EXPR, common_type, 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. */
+ /* 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);
- if (TYPE_PRECISION (common_type) > HOST_BITS_PER_WIDE_INT)
+ /* We need to shift the value if we are after the increment. */
+ if (stmt_after_increment (loop, cand, at))
{
- /* 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, common_type, ubase, cbase);
- if (uutype != common_type)
- delta = fold_convert (uutype, delta);
- expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
- }
- else if (ratioi == -1)
- {
- delta = fold_build2 (PLUS_EXPR, common_type, ubase, cbase);
- if (uutype != common_type)
- delta = fold_convert (uutype, delta);
- 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, common_type, cbase, ratio);
- delta = fold_build2 (MINUS_EXPR, common_type, ubase, delta);
- if (uutype != common_type)
- delta = fold_convert (uutype, 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, common_type, aff);
- tree_to_aff_combination (cbase, common_type, &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);
if (common_type != uutype)
- aff_combination_convert (uutype, aff);
- aff_combination_add (aff, &expr_aff);
+ 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);
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,
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;
+
+ 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));
- SET_DECL_RTL (var, x);
- TREE_STATIC (var) = 1;
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, 2000))) + 1;
+ build_int_cst (sizetype, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "force_expr_to_var_cost:\n");
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
mode = TYPE_MODE (TREE_TYPE (expr));
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
cost = add_cost (mode);
return 0;
}
*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);
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;
+ double_int rat;
*depends_on = NULL;
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
- {
- double_int rat;
-
- if (!constant_multiple_of (ustep, cstep, &rat))
- return INFTY;
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ return INFTY;
- if (double_int_fits_in_shwi_p (rat))
- ratio = double_int_to_shwi (rat);
- else
- return INFTY;
- }
+ if (double_int_fits_in_shwi_p (rat))
+ ratio = double_int_to_shwi (rat);
+ else
+ return INFTY;
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
return cost != INFTY;
}
-/* 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;
- 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 (!nit)
return false;
- 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 = fold_affine_expr (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;
+ unsigned elim_cost, express_cost, cost;
+ bool ok;
/* Only consider real candidates. */
if (!cand->iv)
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 /= AVG_LOOP_NITER (data->current_loop);
}
+ else
+ elim_cost = INFTY;
- /* 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 (elim_cost < express_cost)
{
- 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);
+ 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 cost != INFTY;
}
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);
}
{
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
thus leading to ICE. */
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 GIMPLE_MODIFY_STMT:
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_gimple (GIMPLE_MODIFY_STMT, 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);
- GIMPLE_STMT_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);
+ ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
+ gcc_assert (ok);
- *op_p = op;
+ *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))
{
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 = current_loops->tree_root;
- while (loop->inner)
- loop = loop->inner;
-
- /* Scan the loops, inner ones first. */
- while (loop != current_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
