/* Induction variable optimizations.
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* 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 "tree-scalar-evolution.h"
#include "cfgloop.h"
#include "params.h"
+#include "langhooks.h"
/* The infinite cost. */
#define INFTY 10000000
/* Information attached to loop. */
struct loop_data
{
- struct tree_niter_desc niter;
- /* Number of iterations. */
-
unsigned regs_used; /* Number of registers used. */
};
unsigned cost; /* The cost. */
bitmap depends_on; /* The list of invariants that have to be
preserved. */
+ tree value; /* For final value elimination, the expression for
+ the final value of the iv. For iv elimination,
+ the new bound to compare with. */
};
/* Use. */
to replace the final value of an iv by direct
computation of the value. */
unsigned cost; /* Cost of the candidate. */
+ bitmap depends_on; /* The list of invariants that are used in step of the
+ biv. */
};
/* The data used by the induction variable optimizations. */
+typedef struct iv_use *iv_use_p;
+DEF_VEC_P(iv_use_p);
+DEF_VEC_ALLOC_P(iv_use_p,heap);
+
+typedef struct iv_cand *iv_cand_p;
+DEF_VEC_P(iv_cand_p);
+DEF_VEC_ALLOC_P(iv_cand_p,heap);
+
struct ivopts_data
{
/* The currently optimized loop. */
struct loop *current_loop;
+ /* Numbers of iterations for all exits of the current loop. */
+ htab_t niters;
+
/* The size of version_info array allocated. */
unsigned version_info_size;
unsigned max_inv_id;
/* The uses of induction variables. */
- varray_type iv_uses;
+ VEC(iv_use_p,heap) *iv_uses;
/* The candidates. */
- varray_type iv_candidates;
+ VEC(iv_cand_p,heap) *iv_candidates;
/* A bitmap of important candidates. */
bitmap important_candidates;
/* The candidates used. */
bitmap cands;
+ /* The number of candidates in the set. */
+ unsigned n_cands;
+
/* Total number of registers needed. */
unsigned n_regs;
#define MAX_CONSIDERED_USES \
((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
+/* If there are at most this number of ivs in the set, try removing unnecessary
+ ivs from the set always. */
+
+#define ALWAYS_PRUNE_CAND_SET_BOUND \
+ ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
+
/* The list of trees for that the decl_rtl field must be reset is stored
here. */
-static varray_type decl_rtl_to_reset;
+static VEC(tree,heap) *decl_rtl_to_reset;
/* Number of uses recorded in DATA. */
static inline unsigned
n_iv_uses (struct ivopts_data *data)
{
- return VARRAY_ACTIVE_SIZE (data->iv_uses);
+ return VEC_length (iv_use_p, data->iv_uses);
}
/* Ith use recorded in DATA. */
static inline struct iv_use *
iv_use (struct ivopts_data *data, unsigned i)
{
- return VARRAY_GENERIC_PTR_NOGC (data->iv_uses, i);
+ return VEC_index (iv_use_p, data->iv_uses, i);
}
/* Number of candidates recorded in DATA. */
static inline unsigned
n_iv_cands (struct ivopts_data *data)
{
- return VARRAY_ACTIVE_SIZE (data->iv_candidates);
+ return VEC_length (iv_cand_p, data->iv_candidates);
}
/* Ith candidate recorded in DATA. */
static inline struct iv_cand *
iv_cand (struct ivopts_data *data, unsigned i)
{
- return VARRAY_GENERIC_PTR_NOGC (data->iv_candidates, i);
+ return VEC_index (iv_cand_p, data->iv_candidates, i);
}
/* The data for LOOP. */
/* The single loop exit if it dominates the latch, NULL otherwise. */
-static edge
+edge
single_dom_exit (struct loop *loop)
{
edge exit = loop->single_exit;
dump_iv (file, use->iv);
- fprintf (file, " related candidates ");
- dump_bitmap (file, use->related_cands);
+ if (use->related_cands)
+ {
+ fprintf (file, " related candidates ");
+ dump_bitmap (file, use->related_cands);
+ }
}
/* Dumps information about the uses to FILE. */
fprintf (file, "candidate %d%s\n",
cand->id, cand->important ? " (important)" : "");
+ if (cand->depends_on)
+ {
+ fprintf (file, " depends on ");
+ dump_bitmap (file, cand->depends_on);
+ }
+
if (!iv)
{
fprintf (file, " final value replacement\n");
}
}
+/* 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;
+
+ /* True if the # of iterations was successfully determined. */
+ bool valid_p;
+
+ /* Description of # of iterations. */
+ struct tree_niter_desc 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 structure describing number of iterations determined from
+ EXIT of DATA->current_loop, or NULL if something goes wrong. */
+
+static struct tree_niter_desc *
+niter_for_exit (struct ivopts_data *data, edge exit)
+{
+ struct nfe_cache_elt *nfe_desc;
+ PTR *slot;
+
+ slot = htab_find_slot_with_hash (data->niters, exit,
+ htab_hash_pointer (exit),
+ INSERT);
+
+ if (!*slot)
+ {
+ 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;
+ }
+ else
+ nfe_desc = *slot;
+
+ if (!nfe_desc->valid_p)
+ return NULL;
+
+ return &nfe_desc->niter;
+}
+
+/* Returns structure describing number of iterations determined from
+ single dominating exit of DATA->current_loop, or NULL if something
+ goes wrong. */
+
+static struct tree_niter_desc *
+niter_for_single_dom_exit (struct ivopts_data *data)
+{
+ edge exit = single_dom_exit (data->current_loop);
+
+ if (!exit)
+ return NULL;
+
+ return niter_for_exit (data, exit);
+}
+
/* Initializes data structures used by the iv optimization pass, stored
in DATA. LOOPS is the loop tree. */
unsigned i;
data->version_info_size = 2 * num_ssa_names;
- data->version_info = xcalloc (data->version_info_size,
- sizeof (struct version_info));
- data->relevant = BITMAP_XMALLOC ();
- data->important_candidates = BITMAP_XMALLOC ();
+ data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
+ data->relevant = BITMAP_ALLOC (NULL);
+ data->important_candidates = BITMAP_ALLOC (NULL);
data->max_inv_id = 0;
+ data->niters = htab_create (10, nfe_hash, nfe_eq, free);
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
- VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_uses, 20, "iv_uses");
- VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_candidates, 20, "iv_candidates");
- VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
+ 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);
}
/* Returns a memory object to that EXPR points. In case we are able to
base = get_base_address (obj);
if (!base)
- return fold_convert (ptr_type_node, expr);
+ return expr;
if (TREE_CODE (base) == INDIRECT_REF)
- return fold_convert (ptr_type_node, TREE_OPERAND (base, 0));
+ return determine_base_object (TREE_OPERAND (base, 0));
- return fold (build1 (ADDR_EXPR, ptr_type_node, base));
+ return fold_convert (ptr_type_node,
+ build_fold_addr_expr (base));
case PLUS_EXPR:
case MINUS_EXPR:
if (!op0)
return (code == PLUS_EXPR
? op1
- : fold (build1 (NEGATE_EXPR, ptr_type_node, op1)));
+ : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
+
+ return fold_build2 (code, ptr_type_node, op0, op1);
- return fold (build (code, ptr_type_node, op0, op1));
+ case NOP_EXPR:
+ case CONVERT_EXPR:
+ return determine_base_object (TREE_OPERAND (expr, 0));
default:
return fold_convert (ptr_type_node, expr);
static struct iv *
alloc_iv (tree base, tree step)
{
- struct iv *iv = xcalloc (1, sizeof (struct iv));
+ struct iv *iv = XCNEW (struct iv);
if (step && integer_zerop (step))
step = NULL_TREE;
return name_info (data, var)->iv;
}
-/* Determines the step of a biv defined in PHI. */
+/* Determines the step of a biv defined in PHI. Returns NULL if PHI does
+ not define a simple affine biv with nonzero step. */
static tree
determine_biv_step (tree phi)
{
struct loop *loop = bb_for_stmt (phi)->loop_father;
- tree name = PHI_RESULT (phi), base, step;
- tree type = TREE_TYPE (name);
+ tree name = PHI_RESULT (phi);
+ affine_iv iv;
if (!is_gimple_reg (name))
return NULL_TREE;
- if (!simple_iv (loop, phi, name, &base, &step))
+ if (!simple_iv (loop, phi, name, &iv, true))
return NULL_TREE;
- if (!step)
- return build_int_cst (type, 0);
-
- return step;
+ 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
contains_abnormal_ssa_name_p (tree expr)
{
- enum tree_code code = TREE_CODE (expr);
- enum tree_code_class class = TREE_CODE_CLASS (code);
-
+ 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;
return false;
if (code == ADDR_EXPR)
- return !for_each_index (&TREE_OPERAND (expr, 1),
+ return !for_each_index (&TREE_OPERAND (expr, 0),
idx_contains_abnormal_ssa_name_p,
NULL);
continue;
step = determine_biv_step (phi);
-
if (!step)
continue;
- if (cst_and_fits_in_hwi (step)
- && int_cst_value (step) == 0)
- continue;
base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
- if (contains_abnormal_ssa_name_p (base))
+ base = expand_simple_operations (base);
+ if (contains_abnormal_ssa_name_p (base)
+ || contains_abnormal_ssa_name_p (step))
continue;
type = TREE_TYPE (PHI_RESULT (phi));
base = fold_convert (type, base);
- step = fold_convert (type, step);
-
- /* FIXME: We do not handle induction variables whose step does
- not satisfy cst_and_fits_in_hwi. */
- if (!cst_and_fits_in_hwi (step))
- continue;
+ if (step)
+ step = fold_convert (type, step);
set_iv (data, PHI_RESULT (phi), base, step);
found = true;
}
/* Checks whether STMT defines a linear induction variable and stores its
- parameters to BASE and STEP. */
+ parameters to IV. */
static bool
-find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt,
- tree *base, tree *step)
+find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
{
tree lhs;
struct loop *loop = data->current_loop;
- *base = NULL_TREE;
- *step = NULL_TREE;
+ iv->base = NULL_TREE;
+ iv->step = NULL_TREE;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step))
- return false;
-
- /* FIXME: We do not handle induction variables whose step does
- not satisfy cst_and_fits_in_hwi. */
- if (!zero_p (*step)
- && !cst_and_fits_in_hwi (*step))
+ if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true))
return false;
+ iv->base = expand_simple_operations (iv->base);
- if (contains_abnormal_ssa_name_p (*base))
+ if (contains_abnormal_ssa_name_p (iv->base)
+ || contains_abnormal_ssa_name_p (iv->step))
return false;
return true;
static void
find_givs_in_stmt (struct ivopts_data *data, tree stmt)
{
- tree base, step;
+ affine_iv iv;
- if (!find_givs_in_stmt_scev (data, stmt, &base, &step))
+ if (!find_givs_in_stmt_scev (data, stmt, &iv))
return;
- set_iv (data, TREE_OPERAND (stmt, 0), base, step);
+ set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
free (body);
}
-/* Determine the number of iterations of the current loop. */
-
-static void
-determine_number_of_iterations (struct ivopts_data *data)
-{
- struct loop *loop = data->current_loop;
- edge exit = single_dom_exit (loop);
-
- if (!exit)
- return;
-
- number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
-}
-
/* For each ssa name defined in LOOP determines whether it is an induction
variable and if so, its initial value and step. */
find_induction_variables (struct ivopts_data *data)
{
unsigned i;
- struct loop *loop = data->current_loop;
bitmap_iterator bi;
if (!find_bivs (data))
find_givs (data);
mark_bivs (data);
- determine_number_of_iterations (data);
if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (loop_data (loop)->niter.niter)
+ struct tree_niter_desc *niter;
+
+ niter = niter_for_single_dom_exit (data);
+
+ if (niter)
{
fprintf (dump_file, " number of iterations ");
- print_generic_expr (dump_file, loop_data (loop)->niter.niter,
- TDF_SLIM);
+ 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, loop_data (loop)->niter.may_be_zero,
- TDF_SLIM);
- fprintf (dump_file, "\n");
-
- fprintf (dump_file, " bogus unless ");
- print_generic_expr (dump_file, loop_data (loop)->niter.assumptions,
- TDF_SLIM);
+ print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
};
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
tree stmt, enum use_type use_type)
{
- struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
+ struct iv_use *use = XCNEW (struct iv_use);
use->id = n_iv_uses (data);
use->type = use_type;
use->iv = iv;
use->stmt = stmt;
use->op_p = use_p;
- use->related_cands = BITMAP_XMALLOC ();
+ use->related_cands = BITMAP_ALLOC (NULL);
/* To avoid showing ssa name in the dumps, if it was not reset by the
caller. */
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
- VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_uses, use);
+ VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
return use;
}
}
iv->have_use_for = true;
- civ = xmalloc (sizeof (struct iv));
+ civ = XNEW (struct iv);
*civ = *iv;
stmt = SSA_NAME_DEF_STMT (op);
const_iv.step = NULL_TREE;
- if (integer_zerop (*cond_p)
- || integer_nonzerop (*cond_p))
+ if (TREE_CODE (*cond_p) != SSA_NAME
+ && !COMPARISON_CLASS_P (*cond_p))
return;
if (TREE_CODE (*cond_p) == SSA_NAME)
return;
}
- civ = xmalloc (sizeof (struct iv));
+ civ = XNEW (struct iv);
*civ = zero_p (iv0->step) ? *iv1: *iv0;
record_use (data, cond_p, civ, stmt, USE_COMPARE);
}
if (!EXPR_P (expr))
return false;
- len = first_rtl_op (TREE_CODE (expr));
+ len = TREE_CODE_LENGTH (TREE_CODE (expr));
for (i = 0; i < len; i++)
if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
return false;
{
struct ifs_ivopts_data *dta = data;
struct iv *iv;
- tree step, type, iv_type, iv_step, lbound, off;
+ tree step, iv_step, lbound, off;
struct loop *loop = dta->ivopts_data->current_loop;
if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
if (!iv->step)
return true;
- iv_type = TREE_TYPE (iv->base);
- type = build_pointer_type (TREE_TYPE (base));
if (TREE_CODE (base) == ARRAY_REF)
{
step = array_ref_element_size (base);
}
else
/* The step for pointer arithmetics already is 1 byte. */
- step = build_int_cst (type, 1);
+ step = build_int_cst (sizetype, 1);
- if (TYPE_PRECISION (iv_type) < TYPE_PRECISION (type))
- iv_step = can_count_iv_in_wider_type (dta->ivopts_data->current_loop,
- type, iv->base, iv->step, dta->stmt);
- else
- iv_step = fold_convert (iv_type, iv->step);
+ /* 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)
{
return false;
}
- step = fold_binary_to_constant (MULT_EXPR, type, step, iv_step);
+ step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
if (!*dta->step_p)
*dta->step_p = step;
else
- *dta->step_p = fold_binary_to_constant (PLUS_EXPR, type,
- *dta->step_p, step);
+ *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
return true;
}
return true;
}
+/* Returns true if memory reference REF may be unaligned. */
+
+static bool
+may_be_unaligned_p (tree ref)
+{
+ 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
+ && (base_align < GET_MODE_ALIGNMENT (mode)
+ || bitpos % GET_MODE_ALIGNMENT (mode) != 0
+ || bitpos % BITS_PER_UNIT != 0))
+ return true;
+
+ 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 = unshare_expr (*op_p), step = NULL;
+ tree base = *op_p, step = NULL;
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
+ /* Do not play with volatile memory references. A bit too conservative,
+ perhaps, but safe. */
+ if (stmt_ann (stmt)->has_volatile_ops)
+ goto fail;
+
/* 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;
- ifs_ivopts_data.ivopts_data = data;
- ifs_ivopts_data.stmt = stmt;
- ifs_ivopts_data.step_p = &step;
- if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
- || zero_p (step))
+ if (STRICT_ALIGNMENT
+ && may_be_unaligned_p (base))
goto fail;
- gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+ base = unshare_expr (base);
+
+ if (TREE_CODE (base) == TARGET_MEM_REF)
+ {
+ tree type = build_pointer_type (TREE_TYPE (base));
+ tree astep;
+
+ if (TMR_BASE (base)
+ && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
+ {
+ civ = get_iv (data, TMR_BASE (base));
+ if (!civ)
+ goto fail;
+
+ TMR_BASE (base) = civ->base;
+ step = civ->step;
+ }
+ if (TMR_INDEX (base)
+ && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
+ {
+ civ = get_iv (data, TMR_INDEX (base));
+ if (!civ)
+ goto fail;
+
+ TMR_INDEX (base) = civ->base;
+ astep = civ->step;
- if (TREE_CODE (base) == INDIRECT_REF)
- base = TREE_OPERAND (base, 0);
+ if (astep)
+ {
+ 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;
+ }
+ }
+
+ if (zero_p (step))
+ goto fail;
+ base = tree_mem_ref_addr (type, base);
+ }
else
- base = build_addr (base);
+ {
+ ifs_ivopts_data.ivopts_data = data;
+ ifs_ivopts_data.stmt = stmt;
+ ifs_ivopts_data.step_p = &step;
+ if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
+ || zero_p (step))
+ goto fail;
+
+ gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
+ gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+
+ base = build_fold_addr_expr (base);
+ }
civ = alloc_iv (base, step);
record_use (data, op_p, civ, stmt, USE_ADDRESS);
static void
find_invariants_stmt (struct ivopts_data *data, tree stmt)
{
- use_optype uses = NULL;
- unsigned i, n;
+ ssa_op_iter iter;
+ use_operand_p use_p;
tree op;
- if (TREE_CODE (stmt) == PHI_NODE)
- n = PHI_NUM_ARGS (stmt);
- else
- {
- get_stmt_operands (stmt);
- uses = STMT_USE_OPS (stmt);
- n = NUM_USES (uses);
- }
-
- for (i = 0; i < n; i++)
+ FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
{
- if (TREE_CODE (stmt) == PHI_NODE)
- op = PHI_ARG_DEF (stmt, i);
- else
- op = USE_OP (uses, i);
-
+ op = USE_FROM_PTR (use_p);
record_invariant (data, op, false);
}
}
{
struct iv *iv;
tree op, lhs, rhs;
- use_optype uses = NULL;
- unsigned i, n;
+ ssa_op_iter iter;
+ use_operand_p use_p;
find_invariants_stmt (data, stmt);
return;
}
- if (TREE_CODE (stmt) == PHI_NODE)
- n = PHI_NUM_ARGS (stmt);
- else
- {
- uses = STMT_USE_OPS (stmt);
- n = NUM_USES (uses);
- }
-
- for (i = 0; i < n; i++)
+ FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
{
- if (TREE_CODE (stmt) == PHI_NODE)
- op = PHI_ARG_DEF (stmt, i);
- else
- op = USE_OP (uses, i);
+ op = USE_FROM_PTR (use_p);
if (TREE_CODE (op) != SSA_NAME)
continue;
free (body);
}
+/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
+ is true, assume we are inside an address. If TOP_COMPREF is true, assume
+ we are at the top-level of the processed address. */
+
+static tree
+strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
+ unsigned HOST_WIDE_INT *offset)
+{
+ tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
+ enum tree_code code;
+ tree type, orig_type = TREE_TYPE (expr);
+ unsigned HOST_WIDE_INT off0, off1, st;
+ tree orig_expr = expr;
+
+ STRIP_NOPS (expr);
+
+ type = TREE_TYPE (expr);
+ code = TREE_CODE (expr);
+ *offset = 0;
+
+ switch (code)
+ {
+ case INTEGER_CST:
+ if (!cst_and_fits_in_hwi (expr)
+ || zero_p (expr))
+ return orig_expr;
+
+ *offset = int_cst_value (expr);
+ return build_int_cst_type (orig_type, 0);
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+
+ op0 = strip_offset_1 (op0, false, false, &off0);
+ op1 = strip_offset_1 (op1, false, false, &off1);
+
+ *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
+ if (op0 == TREE_OPERAND (expr, 0)
+ && op1 == TREE_OPERAND (expr, 1))
+ return orig_expr;
+
+ if (zero_p (op1))
+ expr = op0;
+ else if (zero_p (op0))
+ {
+ if (code == PLUS_EXPR)
+ expr = op1;
+ else
+ expr = fold_build1 (NEGATE_EXPR, type, op1);
+ }
+ else
+ expr = fold_build2 (code, type, op0, op1);
+
+ return fold_convert (orig_type, expr);
+
+ case ARRAY_REF:
+ if (!inside_addr)
+ return orig_expr;
+
+ step = array_ref_element_size (expr);
+ if (!cst_and_fits_in_hwi (step))
+ break;
+
+ st = int_cst_value (step);
+ op1 = TREE_OPERAND (expr, 1);
+ op1 = strip_offset_1 (op1, false, false, &off1);
+ *offset = off1 * st;
+
+ if (top_compref
+ && zero_p (op1))
+ {
+ /* Strip the component reference completely. */
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
+ *offset += off0;
+ return op0;
+ }
+ break;
+
+ case COMPONENT_REF:
+ if (!inside_addr)
+ return orig_expr;
+
+ tmp = component_ref_field_offset (expr);
+ if (top_compref
+ && cst_and_fits_in_hwi (tmp))
+ {
+ /* Strip the component reference completely. */
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
+ *offset = off0 + int_cst_value (tmp);
+ return op0;
+ }
+ break;
+
+ case ADDR_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, true, true, &off0);
+ *offset += off0;
+
+ if (op0 == TREE_OPERAND (expr, 0))
+ return orig_expr;
+
+ expr = build_fold_addr_expr (op0);
+ return fold_convert (orig_type, expr);
+
+ case INDIRECT_REF:
+ inside_addr = false;
+ break;
+
+ default:
+ return orig_expr;
+ }
+
+ /* Default handling of expressions for that we want to recurse into
+ the first operand. */
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, inside_addr, false, &off0);
+ *offset += off0;
+
+ if (op0 == TREE_OPERAND (expr, 0)
+ && (!op1 || op1 == TREE_OPERAND (expr, 1)))
+ return orig_expr;
+
+ expr = copy_node (expr);
+ TREE_OPERAND (expr, 0) = op0;
+ if (op1)
+ TREE_OPERAND (expr, 1) = op1;
+
+ /* Inside address, we might strip the top level component references,
+ thus changing type of the expression. Handling of ADDR_EXPR
+ will fix that. */
+ expr = fold_convert (orig_type, expr);
+
+ return expr;
+}
+
+/* Strips constant offsets from EXPR and stores them to OFFSET. */
+
+static tree
+strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
+{
+ return strip_offset_1 (expr, false, false, offset);
+}
+
+/* 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 *. */
+
+static tree
+generic_type_for (tree type)
+{
+ if (POINTER_TYPE_P (type))
+ return ptr_type_node;
+
+ if (TYPE_UNSIGNED (type))
+ return type;
+
+ return unsigned_type_for (type);
+}
+
+/* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
+ the bitmap to that we should store it. */
+
+static struct ivopts_data *fd_ivopts_data;
+static tree
+find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
+{
+ bitmap *depends_on = data;
+ struct version_info *info;
+
+ if (TREE_CODE (*expr_p) != SSA_NAME)
+ return NULL_TREE;
+ info = name_info (fd_ivopts_data, *expr_p);
+
+ if (!info->inv_id || info->has_nonlin_use)
+ return NULL_TREE;
+
+ if (!*depends_on)
+ *depends_on = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (*depends_on, info->inv_id);
+
+ return NULL_TREE;
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. If both BASE and STEP are NULL, we add a pseudocandidate for the
{
unsigned i;
struct iv_cand *cand = NULL;
- tree type;
+ tree type, orig_type;
if (base)
{
- type = TREE_TYPE (base);
- if (!TYPE_UNSIGNED (type))
+ orig_type = TREE_TYPE (base);
+ type = generic_type_for (orig_type);
+ if (type != orig_type)
{
- type = unsigned_type_for (type);
base = fold_convert (type, base);
if (step)
step = fold_convert (type, step);
if (i == n_iv_cands (data))
{
- cand = xcalloc (1, sizeof (struct iv_cand));
+ cand = XCNEW (struct iv_cand);
cand->id = i;
if (!base && !step)
}
cand->important = important;
cand->incremented_at = incremented_at;
- VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_candidates, cand);
+ VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
+
+ if (step
+ && TREE_CODE (step) != INTEGER_CST)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&step, find_depends, &cand->depends_on, NULL);
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
dump_cand (dump_file, cand);
return cand;
}
+/* Returns true if incrementing the induction variable at the end of the LOOP
+ is allowed.
+
+ The purpose is to avoid splitting latch edge with a biv increment, thus
+ creating a jump, possibly confusing other optimization passes and leaving
+ less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
+ is not available (so we do not have a better alternative), or if the latch
+ edge is already nonempty. */
+
+static bool
+allow_ip_end_pos_p (struct loop *loop)
+{
+ if (!ip_normal_pos (loop))
+ return true;
+
+ if (!empty_block_p (ip_end_pos (loop)))
+ return true;
+
+ return false;
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. The candidate computation is scheduled on all available positions. */
{
if (ip_normal_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
- if (ip_end_pos (data->current_loop))
+ if (ip_end_pos (data->current_loop)
+ && allow_ip_end_pos_p (data->current_loop))
add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
}
+/* Add a standard "0 + 1 * iteration" iv candidate for a
+ type with SIZE bits. */
+
+static void
+add_standard_iv_candidates_for_size (struct ivopts_data *data,
+ unsigned int size)
+{
+ tree type = lang_hooks.types.type_for_size (size, true);
+ add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
+ true, NULL);
+}
+
/* Adds standard iv candidates. */
static void
add_standard_iv_candidates (struct ivopts_data *data)
{
- /* Add 0 + 1 * iteration candidate. */
- add_candidate (data,
- build_int_cst (unsigned_intSI_type_node, 0),
- build_int_cst (unsigned_intSI_type_node, 1),
- true, NULL);
+ add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
- /* The same for a long type if it is still fast enough. */
- if (BITS_PER_WORD > 32)
- add_candidate (data,
- build_int_cst (unsigned_intDI_type_node, 0),
- build_int_cst (unsigned_intDI_type_node, 1),
- true, NULL);
+ /* The same for a double-integer type if it is still fast enough. */
+ if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
+ add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
}
add_iv_value_candidates (struct ivopts_data *data,
struct iv *iv, struct iv_use *use)
{
+ unsigned HOST_WIDE_INT offset;
+ tree base;
+
add_candidate (data, iv->base, iv->step, false, use);
- /* The same, but with initial value zero. */
+ /* The same, but with initial value zero. Make such variable important,
+ since it is generic enough so that possibly many uses may be based
+ on it. */
add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
- iv->step, false, use);
+ iv->step, true, use);
+
+ /* Third, try removing the constant offset. */
+ base = strip_offset (iv->base, &offset);
+ if (offset)
+ add_candidate (data, base, iv->step, false, use);
}
-/* Adds candidates based on the address IV and USE. */
-
-static void
-add_address_candidates (struct ivopts_data *data,
- struct iv *iv, struct iv_use *use)
-{
- tree base, abase, tmp, *act;
-
- /* First, the trivial choices. */
- add_iv_value_candidates (data, iv, use);
-
- /* Second, try removing the COMPONENT_REFs. */
- if (TREE_CODE (iv->base) == ADDR_EXPR)
- {
- base = TREE_OPERAND (iv->base, 0);
- while (TREE_CODE (base) == COMPONENT_REF
- || (TREE_CODE (base) == ARRAY_REF
- && TREE_CODE (TREE_OPERAND (base, 1)) == INTEGER_CST))
- base = TREE_OPERAND (base, 0);
-
- if (base != TREE_OPERAND (iv->base, 0))
- {
- gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
-
- if (TREE_CODE (base) == INDIRECT_REF)
- base = TREE_OPERAND (base, 0);
- else
- base = build_addr (base);
- add_candidate (data, base, iv->step, false, use);
- }
- }
-
- /* Third, try removing the constant offset. */
- abase = iv->base;
- while (TREE_CODE (abase) == PLUS_EXPR
- && TREE_CODE (TREE_OPERAND (abase, 1)) != INTEGER_CST)
- abase = TREE_OPERAND (abase, 0);
- /* We found the offset, so make the copy of the non-shared part and
- remove it. */
- if (TREE_CODE (abase) == PLUS_EXPR)
- {
- tmp = iv->base;
- act = &base;
-
- for (tmp = iv->base; tmp != abase; tmp = TREE_OPERAND (tmp, 0))
- {
- *act = build2 (PLUS_EXPR, TREE_TYPE (tmp),
- NULL_TREE, TREE_OPERAND (tmp, 1));
- act = &TREE_OPERAND (*act, 0);
- }
- *act = TREE_OPERAND (tmp, 0);
-
- add_candidate (data, base, iv->step, false, use);
- }
-}
-
-/* Possibly adds pseudocandidate for replacing the final value of USE by
- a direct computation. */
+/* Possibly adds pseudocandidate for replacing the final value of USE by
+ a direct computation. */
static void
add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
{
struct tree_niter_desc *niter;
- struct loop *loop = data->current_loop;
/* We must know where we exit the loop and how many times does it roll. */
- if (!single_dom_exit (loop))
- return;
-
- niter = &loop_data (loop)->niter;
- if (!niter->niter
- || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
- || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
+ niter = niter_for_single_dom_exit (data);
+ if (!niter
+ || !zero_p (niter->may_be_zero))
return;
add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
{
case USE_NONLINEAR_EXPR:
case USE_COMPARE:
+ case USE_ADDRESS:
/* Just add the ivs based on the value of the iv used here. */
add_iv_value_candidates (data, use->iv, use);
break;
add_iv_outer_candidates (data, use);
break;
- case USE_ADDRESS:
- add_address_candidates (data, use->iv, use);
- break;
-
default:
gcc_unreachable ();
}
for (i = 0; i < n_iv_uses (data); i++)
{
use = iv_use (data, i);
- BITMAP_XFREE (use->related_cands);
+ BITMAP_FREE (use->related_cands);
}
}
else
}
use->n_map_members = size;
- use->cost_map = xcalloc (size, sizeof (struct cost_pair));
+ use->cost_map = XCNEWVEC (struct cost_pair, size);
}
}
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
- on invariants DEPENDS_ON. */
+ 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)
+ bitmap depends_on, tree value)
{
unsigned i, s;
if (cost == INFTY)
{
- BITMAP_XFREE (depends_on);
+ BITMAP_FREE (depends_on);
return;
}
use->cost_map[cand->id].cand = cand;
use->cost_map[cand->id].cost = cost;
use->cost_map[cand->id].depends_on = depends_on;
+ use->cost_map[cand->id].value = value;
return;
}
use->cost_map[i].cand = cand;
use->cost_map[i].cost = cost;
use->cost_map[i].depends_on = depends_on;
+ use->cost_map[i].value = value;
}
/* Gets cost of (USE, CANDIDATE) pair. */
produce_memory_decl_rtl (tree obj, int *regno)
{
rtx x;
- if (!obj)
- abort ();
+
+ gcc_assert (obj);
if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
{
const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
{
case ADDR_EXPR:
for (expr_p = &TREE_OPERAND (*expr_p, 0);
- (handled_component_p (*expr_p)
- || TREE_CODE (*expr_p) == REALPART_EXPR
- || TREE_CODE (*expr_p) == IMAGPART_EXPR);
- expr_p = &TREE_OPERAND (*expr_p, 0));
+ handled_component_p (*expr_p);
+ expr_p = &TREE_OPERAND (*expr_p, 0))
+ continue;
obj = *expr_p;
if (DECL_P (obj))
x = produce_memory_decl_rtl (obj, regno);
if (x)
{
- VARRAY_PUSH_GENERIC_PTR_NOGC (decl_rtl_to_reset, obj);
+ VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
SET_DECL_RTL (obj, x);
}
rtx seq, rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
- int regno = 0;
+ /* Avoid using hard regs in ways which may be unsupported. */
+ int regno = LAST_VIRTUAL_REGISTER + 1;
walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
start_sequence ();
end_sequence ();
cost = seq_cost (seq);
- if (GET_CODE (rslt) == MEM)
+ if (MEM_P (rslt))
cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
return cost;
return cand->var_before;
}
-/* Determines the expression by that USE is expressed from induction variable
- CAND at statement AT in LOOP. */
+/* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
+ but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
+
+int
+tree_int_cst_sign_bit (tree t)
+{
+ unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
+ unsigned HOST_WIDE_INT w;
+
+ if (bitno < HOST_BITS_PER_WIDE_INT)
+ w = TREE_INT_CST_LOW (t);
+ 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
-get_computation_at (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at)
+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;
+ }
+ 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;
+
+ /* 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);
+
+ 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);
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+ CAND at statement AT in LOOP. The expression is stored in a decomposed
+ form into AFF. Returns false if USE cannot be expressed using CAND. */
+
+static bool
+get_computation_aff (struct loop *loop,
+ struct iv_use *use, struct iv_cand *cand, tree at,
+ struct affine_tree_combination *aff)
{
tree ubase = use->iv->base;
tree ustep = use->iv->step;
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;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
/* We do not have a precision to express the values of use. */
- return NULL_TREE;
+ return false;
}
expr = var_at_stmt (loop, cand, at);
expr = fold_convert (uutype, expr);
cbase = fold_convert (uutype, cbase);
cstep = fold_convert (uutype, cstep);
- }
- if (!cst_and_fits_in_hwi (cstep)
- || !cst_and_fits_in_hwi (ustep))
- return NULL_TREE;
-
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
-
- 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 NULL_TREE;
+ /* 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;
}
- /* We may 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));
+ 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);
- /* use = ubase + ratio * (var - cbase). If either cbase is a constant
- or |ratio| == 1, it is better to handle this like
-
- ubase - ratio * cbase + ratio * var. */
+ 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 (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));
- }
- else if (TREE_CODE (cbase) == INTEGER_CST)
- {
ratio = build_int_cst_type (uutype, ratioi);
- delta = fold (build2 (MULT_EXPR, uutype, ratio, cbase));
- delta = fold (build2 (MINUS_EXPR, uutype, ubase, delta));
- expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
- expr = fold (build2 (PLUS_EXPR, uutype, delta, expr));
}
else
{
- expr = fold (build2 (MINUS_EXPR, uutype, expr, cbase));
- ratio = build_int_cst_type (uutype, ratioi);
- expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
- expr = fold (build2 (PLUS_EXPR, uutype, ubase, expr));
- }
+ ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
+ if (!ratio)
+ return false;
- return fold_convert (utype, expr);
-}
+ /* 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;
+ }
-/* Determines the expression by that USE is expressed from induction variable
- CAND in LOOP. */
+ /* We may 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);
-static tree
-get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
-{
- return get_computation_at (loop, use, cand, use->stmt);
-}
+ /* use = ubase - ratio * cbase + ratio * var.
-/* Strips constant offsets from EXPR and adds them to OFFSET. */
+ 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. */
-static void
-strip_offset (tree *expr, unsigned HOST_WIDE_INT *offset)
-{
- tree op0, op1;
- enum tree_code code;
-
- while (1)
+ if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
{
- if (cst_and_fits_in_hwi (*expr))
+ /* 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)
{
- *offset += int_cst_value (*expr);
- *expr = integer_zero_node;
- return;
+ 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);
+ }
+ 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);
}
- code = TREE_CODE (*expr);
-
- if (code != PLUS_EXPR && code != MINUS_EXPR)
- return;
+ aff->type = uutype;
+ aff->n = 0;
+ aff->offset = 0;
+ aff->mask = 0;
+ aff->rest = expr;
+ return true;
+ }
- op0 = TREE_OPERAND (*expr, 0);
- op1 = TREE_OPERAND (*expr, 1);
+ /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
+ possible to compute ratioi. */
+ gcc_assert (ratioi);
- if (cst_and_fits_in_hwi (op1))
- {
- if (code == PLUS_EXPR)
- *offset += int_cst_value (op1);
- else
- *offset -= int_cst_value (op1);
+ 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_add (aff, &cbase_aff);
+ aff_combination_add (aff, &expr_aff);
- *expr = op0;
- continue;
- }
+ return true;
+}
- if (code != PLUS_EXPR)
- return;
+/* Determines the expression by that USE is expressed from induction variable
+ CAND at statement AT in LOOP. The computation is unshared. */
- if (!cst_and_fits_in_hwi (op0))
- return;
+static tree
+get_computation_at (struct loop *loop,
+ struct iv_use *use, struct iv_cand *cand, tree at)
+{
+ struct affine_tree_combination aff;
+ tree type = TREE_TYPE (use->iv->base);
- *offset += int_cst_value (op0);
- *expr = op1;
- }
+ if (!get_computation_aff (loop, use, cand, at, &aff))
+ return NULL_TREE;
+ unshare_aff_combination (&aff);
+ return fold_convert (type, aff_combination_to_tree (&aff));
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+ CAND in LOOP. The computation is unshared. */
+
+static tree
+get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
+{
+ return get_computation_at (loop, use, cand, use->stmt);
}
/* Returns cost of addition in MODE. */
start_sequence ();
force_operand (gen_rtx_fmt_ee (PLUS, mode,
- gen_raw_REG (mode, FIRST_PSEUDO_REGISTER),
- gen_raw_REG (mode, FIRST_PSEUDO_REGISTER + 1)),
+ gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+ gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
NULL_RTX);
seq = get_insns ();
end_sequence ();
/* Returns cost of multiplication by constant CST in MODE. */
-static unsigned
+unsigned
multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
{
static htab_t costs;
if (*cached)
return (*cached)->cost;
- *cached = xmalloc (sizeof (struct mbc_entry));
+ *cached = XNEW (struct mbc_entry);
(*cached)->mode = mode;
(*cached)->cst = cst;
start_sequence ();
- expand_mult (mode, gen_raw_REG (mode, FIRST_PSEUDO_REGISTER), GEN_INT (cst),
- NULL_RTX, 0);
+ expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+ gen_int_mode (cst, mode), NULL_RTX, 0);
seq = get_insns ();
end_sequence ();
return cost;
}
+/* Returns true if multiplying by RATIO is allowed in address. */
+
+bool
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
+{
+#define MAX_RATIO 128
+ static sbitmap valid_mult;
+
+ if (!valid_mult)
+ {
+ 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);
+ 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 (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))
+ 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);
+}
+
/* 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.
get_address_cost (bool symbol_present, bool var_present,
unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
{
-#define MAX_RATIO 128
- static sbitmap valid_mult;
+ 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 HOST_WIDE_INT mask;
unsigned bits;
- if (!valid_mult)
+ if (!initialized)
{
HOST_WIDE_INT i;
+ initialized = true;
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
+ 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)
{
- XEXP (addr, 1) = GEN_INT (i);
+ XEXP (addr, 1) = gen_int_mode (i, Pmode);
if (!memory_address_p (Pmode, addr))
break;
}
for (i = 1; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = GEN_INT (-i);
+ XEXP (addr, 1) = gen_int_mode (-i, Pmode);
if (!memory_address_p (Pmode, addr))
break;
}
fprintf (dump_file, " max offset %d\n", (int) max_offset);
}
- valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
- sbitmap_zero (valid_mult);
rat = 1;
- addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
- for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
- {
- XEXP (addr, 1) = GEN_INT (i);
- if (memory_address_p (Pmode, addr))
- {
- SET_BIT (valid_mult, i + MAX_RATIO);
- rat = i;
- }
- }
-
- 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))
- fprintf (dump_file, " %d", (int) i);
- fprintf (dump_file, "\n");
- fprintf (dump_file, "\n");
- }
+ for (i = 2; i <= MAX_RATIO; i++)
+ if (multiplier_allowed_in_address_p (i))
+ {
+ rat = i;
+ break;
+ }
}
bits = GET_MODE_BITSIZE (Pmode);
offset_p = (s_offset != 0
&& min_offset <= s_offset && s_offset <= max_offset);
ratio_p = (ratio != 1
- && -MAX_RATIO <= ratio && ratio <= MAX_RATIO
- && TEST_BIT (valid_mult, ratio + MAX_RATIO));
+ && multiplier_allowed_in_address_p (ratio));
if (ratio != 1 && !ratio_p)
cost += multiply_by_cost (ratio, Pmode);
acost = costs[symbol_present][var_present][offset_p][ratio_p];
if (!acost)
{
+ int old_cse_not_expected;
acost = 0;
- addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 1);
+ 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 (rat));
+ 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);
base = gen_rtx_fmt_e (CONST, Pmode,
gen_rtx_fmt_ee (PLUS, Pmode,
base,
- GEN_INT (off)));
+ gen_int_mode (off, Pmode)));
}
else if (offset_p)
- base = GEN_INT (off);
+ base = gen_int_mode (off, Pmode);
else
base = NULL_RTX;
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 ();
return cost + acost;
}
-/* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
- the bitmap to that we should store it. */
-
-static struct ivopts_data *fd_ivopts_data;
-static tree
-find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
-{
- bitmap *depends_on = data;
- struct version_info *info;
-
- if (TREE_CODE (*expr_p) != SSA_NAME)
- return NULL_TREE;
- info = name_info (fd_ivopts_data, *expr_p);
-
- if (!info->inv_id || info->has_nonlin_use)
- return NULL_TREE;
-
- if (!*depends_on)
- *depends_on = BITMAP_XMALLOC ();
- bitmap_set_bit (*depends_on, info->inv_id);
-
- return NULL_TREE;
-}
-
-/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
- invariants the computation depends on. */
+/* Estimates cost of forcing expression EXPR into a variable. */
-static unsigned
-force_var_cost (struct ivopts_data *data,
- tree expr, bitmap *depends_on)
+unsigned
+force_expr_to_var_cost (tree expr)
{
static bool costs_initialized = false;
static unsigned integer_cost;
build_int_cst_type (type, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "force_var_cost:\n");
+ fprintf (dump_file, "force_expr_to_var_cost:\n");
fprintf (dump_file, " integer %d\n", (int) integer_cost);
fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
fprintf (dump_file, " address %d\n", (int) address_cost);
costs_initialized = true;
}
- if (depends_on)
- {
- fd_ivopts_data = data;
- walk_tree (&expr, find_depends, depends_on, NULL);
- }
+ STRIP_NOPS (expr);
if (SSA_VAR_P (expr))
return 0;
case MULT_EXPR:
op0 = TREE_OPERAND (expr, 0);
op1 = TREE_OPERAND (expr, 1);
+ STRIP_NOPS (op0);
+ STRIP_NOPS (op1);
if (is_gimple_val (op0))
cost0 = 0;
else
- cost0 = force_var_cost (data, op0, NULL);
+ cost0 = force_expr_to_var_cost (op0);
if (is_gimple_val (op1))
cost1 = 0;
else
- cost1 = force_var_cost (data, op1, NULL);
+ cost1 = force_expr_to_var_cost (op1);
break;
return cost < target_spill_cost ? cost : target_spill_cost;
}
+/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
+ invariants the computation depends on. */
+
+static unsigned
+force_var_cost (struct ivopts_data *data,
+ tree expr, bitmap *depends_on)
+{
+ if (depends_on)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&expr, find_depends, depends_on, NULL);
+ }
+
+ return force_expr_to_var_cost (expr);
+}
+
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
to false if the corresponding part is missing. DEPENDS_ON is a set of the
int unsignedp, volatilep;
core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
- &unsignedp, &volatilep);
+ &unsignedp, &volatilep, false);
if (toffset != 0
|| bitpos % BITS_PER_UNIT != 0
{
unsigned cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
+ unsigned HOST_WIDE_INT off1, off2;
- strip_offset (&e1, offset);
- *offset = -*offset;
- strip_offset (&e2, offset);
- *offset = -*offset;
+ e1 = strip_offset (e1, &off1);
+ e2 = strip_offset (e2, &off2);
+ *offset += off1 - off2;
+
+ STRIP_NOPS (e1);
+ STRIP_NOPS (e2);
if (TREE_CODE (e1) == ADDR_EXPR)
return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
return INFTY;
}
- if (!cst_and_fits_in_hwi (ustep)
- || !cst_and_fits_in_hwi (cstep))
- return INFTY;
+ if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
+ {
+ /* TODO -- add direct handling of this case. */
+ goto fallback;
+ }
+
+ /* CSTEPI is removed from the offset in case statement is after the
+ increment. If the step is not constant, we use zero instead.
+ This is a bit imprecise (there is the extra addition), but
+ redundancy elimination is likely to transform the code so that
+ it uses value of the variable before increment anyway,
+ so it is not that much unrealistic. */
+ if (cst_and_fits_in_hwi (cstep))
+ cstepi = int_cst_value (cstep);
+ else
+ cstepi = 0;
- if (TREE_CODE (ubase) == INTEGER_CST
- && !cst_and_fits_in_hwi (ubase))
- goto fallback;
+ if (cst_and_fits_in_hwi (ustep)
+ && cst_and_fits_in_hwi (cstep))
+ {
+ ustepi = int_cst_value (ustep);
- if (TREE_CODE (cbase) == INTEGER_CST
- && !cst_and_fits_in_hwi (cbase))
- goto fallback;
+ if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
+ return INFTY;
+ }
+ else
+ {
+ tree rat;
+
+ rat = constant_multiple_of (utype, ustep, cstep);
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
+ if (!rat)
+ return INFTY;
- if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
- {
- /* TODO -- add direct handling of this case. */
- goto fallback;
+ 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 (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
- return INFTY;
-
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
(also holds in the case ratio == -1, TODO. */
- if (TREE_CODE (cbase) == INTEGER_CST)
+ if (cst_and_fits_in_hwi (cbase))
{
offset = - ratio * int_cst_value (cbase);
cost += difference_cost (data,
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost = get_computation_cost (data, use, cand, false, &depends_on);
+ unsigned cost;
- set_use_iv_cost (data, use, cand, cost, depends_on);
+ /* 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
+ cost of increment twice -- once at this use and once in the cost of
+ the candidate. */
+ if (cand->pos == IP_ORIGINAL
+ && cand->incremented_at == use->stmt)
+ {
+ set_use_iv_cost (data, use, cand, 0, 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;
}
bitmap depends_on;
unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
- set_use_iv_cost (data, use, cand, cost, depends_on);
+ set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return cost != INFTY;
}
tree type = TREE_TYPE (iv->base);
niter = fold_convert (type, niter);
- val = fold (build2 (MULT_EXPR, type, iv->step, niter));
+ val = fold_build2 (MULT_EXPR, type, iv->step, niter);
- return fold (build2 (PLUS_EXPR, type, iv->base, val));
+ return fold_build2 (PLUS_EXPR, type, iv->base, val);
}
/* Computes value of candidate CAND at position AT in iteration NITER. */
tree type = TREE_TYPE (cand->iv->base);
if (stmt_after_increment (loop, cand, at))
- val = fold (build2 (PLUS_EXPR, type, val, cand->iv->step));
+ val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
return val;
}
+/* Returns period of induction variable iv. */
+
+static tree
+iv_period (struct iv *iv)
+{
+ tree step = iv->step, period, type;
+ tree pow2div;
+
+ gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
+
+ /* Period of the iv is gcd (step, type range). Since type range is power
+ of two, it suffices to determine the maximum power of two that divides
+ step. */
+ pow2div = num_ending_zeros (step);
+ type = unsigned_type_for (TREE_TYPE (step));
+
+ period = build_low_bits_mask (type,
+ (TYPE_PRECISION (type)
+ - tree_low_cst (pow2div, 1)));
+
+ return period;
+}
+
+/* Returns the comparison operator used when eliminating the iv USE. */
+
+static enum tree_code
+iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
+{
+ struct loop *loop = data->current_loop;
+ basic_block ex_bb;
+ edge exit;
+
+ ex_bb = bb_for_stmt (use->stmt);
+ exit = EDGE_SUCC (ex_bb, 0);
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ exit = EDGE_SUCC (ex_bb, 1);
+
+ return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
+}
+
/* Check whether it is possible to express the condition in USE by comparison
- of candidate CAND. If so, store the comparison code to COMPARE and the
- value compared with to BOUND. */
+ of candidate CAND. If so, store the value compared with to BOUND. */
static bool
-may_eliminate_iv (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand,
- enum tree_code *compare, tree *bound)
+may_eliminate_iv (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand, tree *bound)
{
basic_block ex_bb;
edge exit;
- struct tree_niter_desc niter, new_niter;
- tree wider_type, type, base;
+ struct tree_niter_desc *niter;
+ tree nit, nit_type;
+ tree wider_type, period, per_type;
+ struct loop *loop = data->current_loop;
+ if (TREE_CODE (cand->iv->step) != INTEGER_CST)
+ return false;
+
/* For now works only for exits that dominate the loop latch. TODO -- extend
for other conditions inside loop body. */
ex_bb = bb_for_stmt (use->stmt);
if (flow_bb_inside_loop_p (loop, exit->dest))
return false;
- niter.niter = NULL_TREE;
- number_of_iterations_exit (loop, exit, &niter);
- if (!niter.niter
- || !integer_nonzerop (niter.assumptions)
- || !integer_zerop (niter.may_be_zero))
+ niter = niter_for_exit (data, exit);
+ if (!niter
+ || !zero_p (niter->may_be_zero))
return false;
- if (exit->flags & EDGE_TRUE_VALUE)
- *compare = EQ_EXPR;
- else
- *compare = NE_EXPR;
-
- *bound = cand_value_at (loop, cand, use->stmt, niter.niter);
+ nit = niter->niter;
+ nit_type = TREE_TYPE (nit);
- /* Let us check there is not some problem with overflows, by checking that
- the number of iterations is unchanged. */
- base = cand->iv->base;
- type = TREE_TYPE (base);
- if (stmt_after_increment (loop, cand, use->stmt))
- base = fold (build2 (PLUS_EXPR, type, base, cand->iv->step));
-
- new_niter.niter = NULL_TREE;
- number_of_iterations_cond (TREE_TYPE (cand->iv->base), base,
- cand->iv->step, NE_EXPR, *bound, NULL_TREE,
- &new_niter);
- if (!new_niter.niter
- || !integer_nonzerop (new_niter.assumptions)
- || !integer_zerop (new_niter.may_be_zero))
+ /* 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;
- wider_type = TREE_TYPE (new_niter.niter);
- if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter.niter)))
- wider_type = TREE_TYPE (niter.niter);
- if (!operand_equal_p (fold_convert (wider_type, niter.niter),
- fold_convert (wider_type, new_niter.niter), 0))
+ if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
+ fold_convert (wider_type, period),
+ fold_convert (wider_type, nit))))
return false;
+ *bound = cand_value_at (loop, cand, use->stmt, nit);
return true;
}
determine_use_iv_cost_condition (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree bound;
- enum tree_code compare;
+ tree bound = NULL_TREE, op, cond;
+ bitmap depends_on = NULL;
+ unsigned cost;
/* Only consider real candidates. */
if (!cand->iv)
{
- set_use_iv_cost (data, use, cand, INFTY, NULL);
+ set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
return false;
}
- if (may_eliminate_iv (data->current_loop, use, cand, &compare, &bound))
+ if (may_eliminate_iv (data, use, cand, &bound))
{
- bitmap depends_on = NULL;
- unsigned cost = force_var_cost (data, bound, &depends_on);
+ cost = force_var_cost (data, bound, &depends_on);
- set_use_iv_cost (data, use, cand, cost, depends_on);
+ set_use_iv_cost (data, use, cand, cost, depends_on, bound);
return 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. */
- if (TREE_CODE (*use->op_p) == SSA_NAME)
- record_invariant (data, *use->op_p, true);
- else
+ cost = get_computation_cost (data, use, cand, false, &depends_on);
+
+ cond = *use->op_p;
+ if (TREE_CODE (cond) != SSA_NAME)
{
- record_invariant (data, TREE_OPERAND (*use->op_p, 0), true);
- record_invariant (data, TREE_OPERAND (*use->op_p, 1), true);
+ 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);
+ }
}
- return determine_use_iv_cost_generic (data, use, cand);
+ set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
+ return cost != INFTY;
}
/* Checks whether it is possible to replace the final value of USE by
a direct computation. If so, the formula is stored to *VALUE. */
static bool
-may_replace_final_value (struct loop *loop, struct iv_use *use, tree *value)
+may_replace_final_value (struct ivopts_data *data, struct iv_use *use,
+ tree *value)
{
+ struct loop *loop = data->current_loop;
edge exit;
struct tree_niter_desc *niter;
gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
bb_for_stmt (use->stmt)));
- niter = &loop_data (loop)->niter;
- if (!niter->niter
- || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
- || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
+ niter = niter_for_single_dom_exit (data);
+ if (!niter
+ || !zero_p (niter->may_be_zero))
return false;
*value = iv_value (use->iv, niter->niter);
bitmap depends_on;
unsigned cost;
edge exit;
- tree value;
+ tree value = NULL_TREE;
struct loop *loop = data->current_loop;
-
+
+ /* 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
+ cost of increment twice -- once at this use and once in the cost of
+ the candidate. */
+ if (cand->pos == IP_ORIGINAL
+ && cand->incremented_at == use->stmt)
+ {
+ set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
+ return true;
+ }
+
if (!cand->iv)
{
- if (!may_replace_final_value (loop, use, &value))
+ if (!may_replace_final_value (data, use, &value))
{
- set_use_iv_cost (data, use, cand, INFTY, NULL);
+ set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
return false;
}
cost /= AVG_LOOP_NITER (loop);
- set_use_iv_cost (data, use, cand, cost, depends_on);
+ set_use_iv_cost (data, use, cand, cost, depends_on, value);
return cost != INFTY;
}
cost = get_computation_cost (data, use, cand, false, &depends_on);
}
- set_use_iv_cost (data, use, cand, cost, depends_on);
+ set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return cost != INFTY;
}
unsigned i, j;
struct iv_use *use;
struct iv_cand *cand;
- bitmap to_clear = BITMAP_XMALLOC ();
+ bitmap to_clear = BITMAP_ALLOC (NULL);
alloc_use_cost_map (data);
}
}
- BITMAP_XFREE (to_clear);
+ BITMAP_FREE (to_clear);
if (dump_file && (dump_flags & TDF_DETAILS))
{
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
unsigned cost_base, cost_step;
- tree base, last;
- basic_block bb;
+ tree base;
if (!cand->iv)
{
cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
- /* Prefer the original iv unless we may gain something by replacing it. */
- if (cand->pos == IP_ORIGINAL)
+ /* 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 not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
- if (cand->pos == IP_END)
- {
- bb = ip_end_pos (data->current_loop);
- last = last_stmt (bb);
-
- if (!last
- || TREE_CODE (last) == LABEL_EXPR)
- cand->cost++;
- }
+ if (cand->pos == IP_END
+ && empty_block_p (ip_end_pos (data->current_loop)))
+ cand->cost++;
}
/* Determines costs of computation of the candidates. */
ivs->cost = cost;
}
+/* Remove invariants in set INVS to set IVS. */
+
+static void
+iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
+{
+ bitmap_iterator bi;
+ unsigned iid;
+
+ if (!invs)
+ return;
+
+ EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
+ {
+ ivs->n_invariant_uses[iid]--;
+ if (ivs->n_invariant_uses[iid] == 0)
+ ivs->n_regs--;
+ }
+}
+
/* Set USE not to be expressed by any candidate in IVS. */
static void
iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use)
{
- unsigned uid = use->id, cid, iid;
- bitmap deps;
+ unsigned uid = use->id, cid;
struct cost_pair *cp;
- bitmap_iterator bi;
cp = ivs->cand_for_use[uid];
if (!cp)
/* Do not count the pseudocandidates. */
if (cp->cand->iv)
ivs->n_regs--;
+ ivs->n_cands--;
ivs->cand_cost -= cp->cand->cost;
+
+ iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
}
ivs->cand_use_cost -= cp->cost;
- deps = cp->depends_on;
+ iv_ca_set_remove_invariants (ivs, cp->depends_on);
+ iv_ca_recount_cost (data, ivs);
+}
+
+/* Add invariants in set INVS to set IVS. */
- if (deps)
+static void
+iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
+{
+ bitmap_iterator bi;
+ unsigned iid;
+
+ if (!invs)
+ return;
+
+ EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
{
- EXECUTE_IF_SET_IN_BITMAP (deps, 0, iid, bi)
- {
- ivs->n_invariant_uses[iid]--;
- if (ivs->n_invariant_uses[iid] == 0)
- ivs->n_regs--;
- }
+ ivs->n_invariant_uses[iid]++;
+ if (ivs->n_invariant_uses[iid] == 1)
+ ivs->n_regs++;
}
-
- iv_ca_recount_cost (data, ivs);
}
/* Set cost pair for USE in set IVS to CP. */
iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use, struct cost_pair *cp)
{
- unsigned uid = use->id, cid, iid;
- bitmap deps;
- bitmap_iterator bi;
+ unsigned uid = use->id, cid;
if (ivs->cand_for_use[uid] == cp)
return;
/* Do not count the pseudocandidates. */
if (cp->cand->iv)
ivs->n_regs++;
+ ivs->n_cands++;
ivs->cand_cost += cp->cand->cost;
- }
- ivs->cand_use_cost += cp->cost;
-
- deps = cp->depends_on;
-
- if (deps)
- {
- EXECUTE_IF_SET_IN_BITMAP (deps, 0, iid, bi)
- {
- ivs->n_invariant_uses[iid]++;
- if (ivs->n_invariant_uses[iid] == 1)
- ivs->n_regs++;
- }
+ iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
}
+ ivs->cand_use_cost += cp->cost;
+ iv_ca_set_add_invariants (ivs, cp->depends_on);
iv_ca_recount_cost (data, ivs);
}
}
iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
struct cost_pair *new_cp, struct iv_ca_delta *next_change)
{
- struct iv_ca_delta *change = xmalloc (sizeof (struct iv_ca_delta));
+ struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
change->use = use;
change->old_cp = old_cp;
return change;
}
+/* Joins two lists of changes L1 and L2. Destructive -- old lists
+ are rewritten. */
+
+static struct iv_ca_delta *
+iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
+{
+ struct iv_ca_delta *last;
+
+ if (!l2)
+ return l1;
+
+ if (!l1)
+ return l2;
+
+ for (last = l1; last->next_change; last = last->next_change)
+ continue;
+ last->next_change = l2;
+
+ return l1;
+}
+
/* Returns candidate by that USE is expressed in IVS. */
static struct cost_pair *
return ivs->cand_for_use[use->id];
}
+/* Reverse the list of changes DELTA, forming the inverse to it. */
+
+static struct iv_ca_delta *
+iv_ca_delta_reverse (struct iv_ca_delta *delta)
+{
+ struct iv_ca_delta *act, *next, *prev = NULL;
+ struct cost_pair *tmp;
+
+ for (act = delta; act; act = next)
+ {
+ next = act->next_change;
+ act->next_change = prev;
+ prev = act;
+
+ tmp = act->old_cp;
+ act->old_cp = act->new_cp;
+ act->new_cp = tmp;
+ }
+
+ return prev;
+}
+
/* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
reverted instead. */
struct iv_ca_delta *delta, bool forward)
{
struct cost_pair *from, *to;
+ struct iv_ca_delta *act;
- for (; delta; delta = delta->next_change)
- {
- if (forward)
- {
- from = delta->old_cp;
- to = delta->new_cp;
- }
- else
- {
- from = delta->new_cp;
- to = delta->old_cp;
- }
+ if (!forward)
+ delta = iv_ca_delta_reverse (delta);
- gcc_assert (iv_ca_cand_for_use (ivs, delta->use) == from);
- iv_ca_set_cp (data, ivs, delta->use, to);
+ for (act = delta; act; act = act->next_change)
+ {
+ from = act->old_cp;
+ to = act->new_cp;
+ gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
+ iv_ca_set_cp (data, ivs, act->use, to);
}
+
+ if (!forward)
+ iv_ca_delta_reverse (delta);
}
/* Returns true if CAND is used in IVS. */
return ivs->n_cand_uses[cand->id] > 0;
}
+/* Returns number of induction variable candidates in the set IVS. */
+
+static unsigned
+iv_ca_n_cands (struct iv_ca *ivs)
+{
+ return ivs->n_cands;
+}
+
/* Free the list of changes DELTA. */
static void
static struct iv_ca *
iv_ca_new (struct ivopts_data *data)
{
- struct iv_ca *nw = xmalloc (sizeof (struct iv_ca));
+ struct iv_ca *nw = XNEW (struct iv_ca);
nw->upto = 0;
nw->bad_uses = 0;
- nw->cand_for_use = xcalloc (n_iv_uses (data), sizeof (struct cost_pair *));
- nw->n_cand_uses = xcalloc (n_iv_cands (data), sizeof (unsigned));
- nw->cands = BITMAP_XMALLOC ();
+ nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
+ nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
+ nw->cands = BITMAP_ALLOC (NULL);
+ nw->n_cands = 0;
nw->n_regs = 0;
nw->cand_use_cost = 0;
nw->cand_cost = 0;
- nw->n_invariant_uses = xcalloc (data->max_inv_id + 1, sizeof (unsigned));
+ nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
nw->cost = 0;
return nw;
{
free ((*ivs)->cand_for_use);
free ((*ivs)->n_cand_uses);
- BITMAP_XFREE ((*ivs)->cands);
+ BITMAP_FREE ((*ivs)->cands);
free ((*ivs)->n_invariant_uses);
free (*ivs);
*ivs = NULL;
}
/* Try changing candidate in IVS to CAND for each use. Return cost of the
- new set, and store differences in DELTA. */
+ new set, and store differences in DELTA. Number of induction variables
+ in the new set is stored to N_IVS. */
static unsigned
iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_cand *cand, struct iv_ca_delta **delta)
+ struct iv_cand *cand, struct iv_ca_delta **delta,
+ unsigned *n_ivs)
{
unsigned i, cost;
struct iv_use *use;
iv_ca_delta_commit (data, ivs, *delta, true);
cost = iv_ca_cost (ivs);
+ if (n_ivs)
+ *n_ivs = iv_ca_n_cands (ivs);
iv_ca_delta_commit (data, ivs, *delta, false);
return cost;
return cost;
}
+/* Try optimizing the set of candidates IVS by removing candidates different
+ from to EXCEPT_CAND from it. Return cost of the new set, and store
+ differences in DELTA. */
+
+static unsigned
+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;
+ struct iv_cand *cand;
+
+ best_delta = NULL;
+ best_cost = iv_ca_cost (ivs);
+
+ EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+ {
+ cand = iv_cand (data, i);
+
+ if (cand == except_cand)
+ continue;
+
+ acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+
+ if (acost < best_cost)
+ {
+ best_cost = acost;
+ iv_ca_delta_free (&best_delta);
+ best_delta = act_delta;
+ }
+ else
+ iv_ca_delta_free (&act_delta);
+ }
+
+ if (!best_delta)
+ {
+ *delta = NULL;
+ return best_cost;
+ }
+
+ /* Recurse to possibly remove other unnecessary ivs. */
+ iv_ca_delta_commit (data, ivs, best_delta, true);
+ best_cost = iv_ca_prune (data, ivs, except_cand, delta);
+ iv_ca_delta_commit (data, ivs, best_delta, false);
+ *delta = iv_ca_delta_join (best_delta, *delta);
+ return best_cost;
+}
+
/* Tries to extend the sets IVS in the best possible way in order
to express the USE. */
continue;
iv_ca_set_cp (data, ivs, use, cp);
- act_cost = iv_ca_extend (data, ivs, cand, &act_delta);
+ act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
act_delta = NULL;
iv_ca_set_cp (data, ivs, use, cp);
- act_cost = iv_ca_extend (data, ivs, cand, &act_delta);
+ act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
cp, act_delta);
static bool
try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned i, acost, best_cost = iv_ca_cost (ivs);
- struct iv_ca_delta *best_delta = NULL, *act_delta;
+ unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
+ struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
struct iv_cand *cand;
- /* Try altering the set of induction variables by one. */
+ /* Try extending the set of induction variables by one. */
for (i = 0; i < n_iv_cands (data); i++)
{
cand = iv_cand (data, i);
if (iv_ca_cand_used_p (ivs, cand))
- acost = iv_ca_narrow (data, ivs, cand, &act_delta);
- else
- acost = iv_ca_extend (data, ivs, cand, &act_delta);
+ continue;
+
+ acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
+ if (!act_delta)
+ continue;
+
+ /* If we successfully added the candidate and the set is small enough,
+ try optimizing it by removing other candidates. */
+ if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
+ {
+ iv_ca_delta_commit (data, ivs, act_delta, true);
+ acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
+ iv_ca_delta_commit (data, ivs, act_delta, false);
+ act_delta = iv_ca_delta_join (act_delta, tmp_delta);
+ }
if (acost < best_cost)
{
best_cost = acost;
- if (best_delta)
- iv_ca_delta_free (&best_delta);
+ iv_ca_delta_free (&best_delta);
best_delta = act_delta;
}
else
}
if (!best_delta)
- return false;
+ {
+ /* Try removing the candidates from the set instead. */
+ best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
+
+ /* Nothing more we can do. */
+ if (!best_delta)
+ return false;
+ }
iv_ca_delta_commit (data, ivs, best_delta, true);
+ gcc_assert (best_cost == iv_ca_cost (ivs));
iv_ca_delta_free (&best_delta);
return true;
}
base = unshare_expr (cand->iv->base);
- create_iv (base, cand->iv->step, cand->var_before, data->current_loop,
+ create_iv (base, unshare_expr (cand->iv->step),
+ cand->var_before, data->current_loop,
&incr_pos, after, &cand->var_before, &cand->var_after);
}
/* Prevent the ssa name defined by the statement from being removed. */
SET_PHI_RESULT (stmt, NULL);
}
- remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
+ remove_phi_node (stmt, NULL_TREE);
}
else
{
block_stmt_iterator bsi = bsi_for_stmt (stmt);
- bsi_remove (&bsi);
+ bsi_remove (&bsi, true);
}
}
rewrite_use_nonlinear_expr (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp = unshare_expr (get_computation (data->current_loop,
- use, cand));
+ tree comp;
tree op, stmts, tgt, ass;
block_stmt_iterator bsi, pbsi;
-
+
+ /* An important special case -- if we are asked to express value of
+ the original iv by itself, just exit; there is no need to
+ introduce a new computation (that might also need casting the
+ variable to unsigned and back). */
+ if (cand->pos == IP_ORIGINAL
+ && cand->incremented_at == use->stmt)
+ {
+ 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);
+
+ step = cand->iv->step;
+ ctype = TREE_TYPE (step);
+ utype = TREE_TYPE (cand->var_after);
+ if (TREE_CODE (step) == NEGATE_EXPR)
+ {
+ incr_code = MINUS_EXPR;
+ step = TREE_OPERAND (step, 0);
+ }
+
+ /* Check whether we may leave the computation unchanged.
+ This is the case only if it does not rely on other
+ 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);
+ if (TREE_CODE (op) == PLUS_EXPR
+ || TREE_CODE (op) == MINUS_EXPR)
+ {
+ if (TREE_OPERAND (op, 0) == cand->var_before)
+ op = TREE_OPERAND (op, 1);
+ else if (TREE_CODE (op) == PLUS_EXPR
+ && TREE_OPERAND (op, 1) == cand->var_before)
+ op = TREE_OPERAND (op, 0);
+ else
+ op = NULL_TREE;
+ }
+ else
+ op = NULL_TREE;
+
+ if (op
+ && (TREE_CODE (op) == INTEGER_CST
+ || operand_equal_p (op, step, 0)))
+ return;
+
+ /* Otherwise, add the necessary computations to express
+ the iv. */
+ op = fold_convert (ctype, cand->var_before);
+ comp = fold_convert (utype,
+ build2 (incr_code, ctype, op,
+ unshare_expr (step)));
+ }
+ else
+ comp = get_computation (data->current_loop, use, cand);
+
switch (TREE_CODE (use->stmt))
{
case PHI_NODE:
return ref;
}
-/* Rewrites base of memory access OP with expression WITH in statement
- pointed to by BSI. */
+/* Extract the alias analysis info for the memory reference REF. There are
+ several ways how this information may be stored and what precisely is
+ its semantics depending on the type of the reference, but there always is
+ somewhere hidden one _DECL node that is used to determine the set of
+ virtual operands for the reference. The code below deciphers this jungle
+ and extracts this single useful piece of information. */
-static void
-rewrite_address_base (block_stmt_iterator *bsi, tree *op, tree with)
+static tree
+get_ref_tag (tree ref, tree orig)
{
- tree bvar, var, new_var, new_name, copy, name;
- tree orig;
+ tree var = get_base_address (ref);
+ tree aref = NULL_TREE, tag, sv;
+ HOST_WIDE_INT offset, size, maxsize;
+
+ for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
+ {
+ aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
+ if (ref)
+ break;
+ }
- var = bvar = get_base_address (*op);
+ if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
+ return unshare_expr (sv);
- if (!var || TREE_CODE (with) != SSA_NAME)
- goto do_rewrite;
+ if (!var)
+ return NULL_TREE;
- gcc_assert (TREE_CODE (var) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (var) != MISALIGNED_INDIRECT_REF);
if (TREE_CODE (var) == INDIRECT_REF)
- var = TREE_OPERAND (var, 0);
- if (TREE_CODE (var) == SSA_NAME)
{
- name = var;
+ /* In case the base is a dereference of a pointer, first check its name
+ mem tag, and if it does not have one, use type mem tag. */
+ var = TREE_OPERAND (var, 0);
+ if (TREE_CODE (var) != SSA_NAME)
+ return NULL_TREE;
+
+ if (SSA_NAME_PTR_INFO (var))
+ {
+ tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
+ if (tag)
+ return tag;
+ }
+
var = SSA_NAME_VAR (var);
+ tag = var_ann (var)->type_mem_tag;
+ gcc_assert (tag != NULL_TREE);
+ return tag;
}
- else if (DECL_P (var))
- name = NULL_TREE;
else
- goto do_rewrite;
-
- if (var_ann (var)->type_mem_tag)
- var = var_ann (var)->type_mem_tag;
-
- /* We need to add a memory tag for the variable. But we do not want
- to add it to the temporary used for the computations, since this leads
- to problems in redundancy elimination when there are common parts
- in two computations referring to the different arrays. So we copy
- the variable to a new temporary. */
- copy = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, with);
- if (name)
- new_name = duplicate_ssa_name (name, copy);
- else
- {
- new_var = create_tmp_var (TREE_TYPE (with), "ruatmp");
- add_referenced_tmp_var (new_var);
- var_ann (new_var)->type_mem_tag = var;
- new_name = make_ssa_name (new_var, copy);
- }
- TREE_OPERAND (copy, 0) = new_name;
- bsi_insert_before (bsi, copy, BSI_SAME_STMT);
- with = new_name;
+ {
+ if (!DECL_P (var))
+ return NULL_TREE;
-do_rewrite:
+ tag = var_ann (var)->type_mem_tag;
+ if (tag)
+ return tag;
- orig = NULL_TREE;
- gcc_assert (TREE_CODE (*op) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (*op) != MISALIGNED_INDIRECT_REF);
-
- if (TREE_CODE (*op) == INDIRECT_REF)
- orig = REF_ORIGINAL (*op);
- if (!orig)
- orig = unshare_and_remove_ssa_names (*op);
+ return var;
+ }
+}
- *op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
+/* Copies the reference information from OLD_REF to NEW_REF. */
- /* Record the original reference, for purposes of alias analysis. */
- REF_ORIGINAL (*op) = orig;
+static void
+copy_ref_info (tree new_ref, tree old_ref)
+{
+ if (TREE_CODE (old_ref) == TARGET_MEM_REF)
+ copy_mem_ref_info (new_ref, old_ref);
+ else
+ {
+ TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
+ TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
+ }
}
/* Rewrites USE (address that is an iv) using candidate CAND. */
rewrite_use_address (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp = unshare_expr (get_computation (data->current_loop,
- use, cand));
+ struct affine_tree_combination aff;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
- tree stmts;
- tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
+ tree ref;
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+ unshare_aff_combination (&aff);
- rewrite_address_base (&bsi, use->op_p, op);
+ ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
+ copy_ref_info (ref, *use->op_p);
+ *use->op_p = ref;
}
/* Rewrites USE (the condition such that one of the arguments is an iv) using
tree *op_p, cond, op, stmts, 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);
- if (may_eliminate_iv (data->current_loop,
- use, cand, &compare, &bound))
+ bound = cp->value;
+ if (bound)
{
+ tree var = var_at_stmt (data->current_loop, cand, use->stmt);
+ 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);
- *use->op_p = build2 (compare, boolean_type_node,
- var_at_stmt (data->current_loop,
- cand, use->stmt), op);
- modify_stmt (use->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 = unshare_expr (get_computation (data->current_loop, use, cand));
+ comp = get_computation (data->current_loop, use, cand);
cond = *use->op_p;
op_p = &TREE_OPERAND (cond, 0);
phi = create_phi_node (new_name, exit->dest);
SSA_NAME_DEF_STMT (new_name) = phi;
- add_phi_arg (&phi, use, exit);
+ add_phi_arg (phi, use, exit);
}
SET_USE (op_p, PHI_RESULT (phi));
static void
protect_loop_closed_ssa_form (edge exit, tree stmt)
{
- use_optype uses;
- vuse_optype vuses;
- v_may_def_optype v_may_defs;
- unsigned i;
+ ssa_op_iter iter;
+ use_operand_p use_p;
- get_stmt_operands (stmt);
-
- uses = STMT_USE_OPS (stmt);
- for (i = 0; i < NUM_USES (uses); i++)
- protect_loop_closed_ssa_form_use (exit, USE_OP_PTR (uses, i));
-
- vuses = STMT_VUSE_OPS (stmt);
- for (i = 0; i < NUM_VUSES (vuses); i++)
- protect_loop_closed_ssa_form_use (exit, VUSE_OP_PTR (vuses, i));
-
- v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
- protect_loop_closed_ssa_form_use (exit, V_MAY_DEF_OP_PTR (v_may_defs, i));
+ 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. */
-static void
+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 (EDGE_COUNT (exit->dest->preds) > 1)
+ 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))
- protect_loop_closed_ssa_form (exit, tsi_stmt (tsi));
+ {
+ tree stmt = tsi_stmt (tsi);
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
+ protect_loop_closed_ssa_form (exit, stmt);
+ }
}
else
- protect_loop_closed_ssa_form (exit, stmts);
-
- /* 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);
- bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
+ {
+ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ protect_loop_closed_ssa_form (exit, stmts);
+ }
if (!op)
return;
stmt = build2 (MODIFY_EXPR, TREE_TYPE (op),
def, op);
SSA_NAME_DEF_STMT (def) = stmt;
- bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
}
}
}
{
if (!cand->iv)
{
- bool ok = may_replace_final_value (data->current_loop, use, &value);
- gcc_assert (ok);
+ struct cost_pair *cp = get_use_iv_cost (data, use, cand);
+ value = unshare_expr (cp->value);
}
else
value = get_computation_at (data->current_loop,
use, cand, last_stmt (exit->src));
- value = unshare_expr (value);
op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
/* If we will preserve the iv anyway and we would need to perform
default:
gcc_unreachable ();
}
- modify_stmt (use->stmt);
+ mark_new_vars_to_rename (use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
{
unsigned i, j;
bitmap_iterator bi;
+ tree obj;
+
+ htab_empty (data->niters);
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
struct iv_use *use = iv_use (data, i);
free (use->iv);
- BITMAP_XFREE (use->related_cands);
+ BITMAP_FREE (use->related_cands);
for (j = 0; j < use->n_map_members; j++)
if (use->cost_map[j].depends_on)
- BITMAP_XFREE (use->cost_map[j].depends_on);
+ BITMAP_FREE (use->cost_map[j].depends_on);
free (use->cost_map);
free (use);
}
- VARRAY_POP_ALL (data->iv_uses);
+ VEC_truncate (iv_use_p, data->iv_uses, 0);
for (i = 0; i < n_iv_cands (data); i++)
{
if (cand->iv)
free (cand->iv);
+ if (cand->depends_on)
+ BITMAP_FREE (cand->depends_on);
free (cand);
}
- VARRAY_POP_ALL (data->iv_candidates);
+ VEC_truncate (iv_cand_p, data->iv_candidates, 0);
if (data->version_info_size < num_ssa_names)
{
data->version_info_size = 2 * num_ssa_names;
free (data->version_info);
- data->version_info = xcalloc (data->version_info_size,
- sizeof (struct version_info));
+ data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
}
data->max_inv_id = 0;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (decl_rtl_to_reset); i++)
- {
- tree obj = VARRAY_GENERIC_PTR_NOGC (decl_rtl_to_reset, i);
+ for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
+ SET_DECL_RTL (obj, NULL_RTX);
- SET_DECL_RTL (obj, NULL_RTX);
- }
- VARRAY_POP_ALL (decl_rtl_to_reset);
+ VEC_truncate (tree, decl_rtl_to_reset, 0);
}
/* Finalizes data structures used by the iv optimization pass. LOOPS is the
free_loop_data (data);
free (data->version_info);
- BITMAP_XFREE (data->relevant);
- BITMAP_XFREE (data->important_candidates);
+ BITMAP_FREE (data->relevant);
+ BITMAP_FREE (data->important_candidates);
+ htab_delete (data->niters);
- VARRAY_FREE (decl_rtl_to_reset);
- VARRAY_FREE (data->iv_uses);
- VARRAY_FREE (data->iv_candidates);
+ VEC_free (tree, heap, decl_rtl_to_reset);
+ VEC_free (iv_use_p, heap, data->iv_uses);
+ VEC_free (iv_cand_p, heap, data->iv_candidates);
}
/* Optimizes the LOOP. Returns true if anything changed. */
/* Remove the ivs that are unused after rewriting. */
remove_unused_ivs (data);
- loop_commit_inserts ();
-
/* We have changed the structure of induction variables; it might happen
that definitions in the scev database refer to some of them that were
eliminated. */
while (loop->inner)
loop = loop->inner;
-#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
- verify_stmts ();
-#endif
-
/* Scan the loops, inner ones first. */
while (loop != loops->tree_root)
{
loop = loop->outer;
}
-#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
- verify_stmts ();
-#endif
-
tree_ssa_iv_optimize_finalize (loops, &data);
}
OSDN Git Service
