/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
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 "ggc.h"
#include "insn-config.h"
#include "recog.h"
+#include "pointer-set.h"
#include "hashtab.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "cfgloop.h"
#include "params.h"
#include "langhooks.h"
+#include "tree-affine.h"
+#include "target.h"
/* The infinite cost. */
#define INFTY 10000000
bool preserve_biv; /* For the original biv, whether to preserve it. */
};
-/* Information attached to loop. */
-struct loop_data
-{
- unsigned regs_used; /* Number of registers used. */
-};
-
/* Types of uses. */
enum use_type
{
USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
- USE_OUTER, /* The induction variable is used outside the loop. */
USE_ADDRESS, /* Use in an address. */
USE_COMPARE /* Use is a compare. */
};
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. */
/* The currently optimized loop. */
struct loop *current_loop;
+ /* Number of registers used in it. */
+ unsigned regs_used;
+
/* Numbers of iterations for all exits of the current loop. */
- htab_t niters;
+ struct pointer_map_t *niters;
/* The size of version_info array allocated. */
unsigned version_info_size;
return VEC_index (iv_cand_p, data->iv_candidates, i);
}
-/* The data for LOOP. */
-
-static inline struct loop_data *
-loop_data (struct loop *loop)
-{
- return loop->aux;
-}
-
/* 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;
+ edge exit = single_exit (loop);
if (!exit)
return NULL;
fprintf (file, " generic\n");
break;
- case USE_OUTER:
- fprintf (file, " outside\n");
- break;
-
case USE_ADDRESS:
fprintf (file, " address\n");
break;
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");
return ver_info (data, SSA_NAME_VERSION (name));
}
-/* Checks whether there exists number X such that X * B = A, counting modulo
- 2^BITS. */
-
-static bool
-divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
- HOST_WIDE_INT *x)
-{
- unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- unsigned HOST_WIDE_INT inv, ex, val;
- unsigned i;
-
- a &= mask;
- b &= mask;
-
- /* First divide the whole equation by 2 as long as possible. */
- while (!(a & 1) && !(b & 1))
- {
- a >>= 1;
- b >>= 1;
- bits--;
- mask >>= 1;
- }
-
- if (!(b & 1))
- {
- /* If b is still even, a is odd and there is no such x. */
- return false;
- }
-
- /* Find the inverse of b. We compute it as
- b^(2^(bits - 1) - 1) (mod 2^bits). */
- inv = 1;
- ex = b;
- for (i = 0; i < bits - 1; i++)
- {
- inv = (inv * ex) & mask;
- ex = (ex * ex) & mask;
- }
-
- val = (a * inv) & mask;
-
- gcc_assert (((val * b) & mask) == a);
-
- if ((val >> (bits - 1)) & 1)
- val |= ~mask;
-
- *x = val;
-
- return true;
-}
-
/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
emitted in LOOP. */
}
}
-/* Element of the table in that we cache the numbers of iterations obtained
- from exits of the loop. */
+/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
-struct nfe_cache_elt
+static bool
+abnormal_ssa_name_p (tree exp)
{
- /* The edge for that the number of iterations is cached. */
- edge exit;
+ if (!exp)
+ return false;
- /* True if the # of iterations was successfully determined. */
- bool valid_p;
+ if (TREE_CODE (exp) != SSA_NAME)
+ return false;
- /* Description of # of iterations. */
- struct tree_niter_desc niter;
-};
+ return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
+}
-/* Hash function for nfe_cache_elt E. */
+/* Returns false if BASE or INDEX contains a ssa name that occurs in an
+ abnormal phi node. Callback for for_each_index. */
-static hashval_t
-nfe_hash (const void *e)
+static bool
+idx_contains_abnormal_ssa_name_p (tree base, tree *index,
+ void *data ATTRIBUTE_UNUSED)
{
- const struct nfe_cache_elt *elt = e;
+ if (TREE_CODE (base) == ARRAY_REF)
+ {
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
+ return false;
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
+ return false;
+ }
- return htab_hash_pointer (elt->exit);
+ return !abnormal_ssa_name_p (*index);
}
-/* Equality function for nfe_cache_elt E1 and edge E2. */
+/* Returns true if EXPR contains a ssa name that occurs in an
+ abnormal phi node. */
-static int
-nfe_eq (const void *e1, const void *e2)
+bool
+contains_abnormal_ssa_name_p (tree expr)
{
- const struct nfe_cache_elt *elt1 = e1;
+ enum tree_code code;
+ enum tree_code_class codeclass;
+
+ if (!expr)
+ return false;
+
+ code = TREE_CODE (expr);
+ codeclass = TREE_CODE_CLASS (code);
+
+ if (code == SSA_NAME)
+ return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
+
+ if (code == INTEGER_CST
+ || is_gimple_min_invariant (expr))
+ return false;
+
+ if (code == ADDR_EXPR)
+ return !for_each_index (&TREE_OPERAND (expr, 0),
+ idx_contains_abnormal_ssa_name_p,
+ NULL);
+
+ switch (codeclass)
+ {
+ case tcc_binary:
+ case tcc_comparison:
+ if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
+ return true;
+
+ /* Fallthru. */
+ case tcc_unary:
+ if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
+ return true;
+
+ break;
- return elt1->exit == e2;
+ default:
+ gcc_unreachable ();
+ }
+
+ return false;
}
-/* Returns structure describing number of iterations determined from
+/* Returns tree describing number of iterations determined from
EXIT of DATA->current_loop, or NULL if something goes wrong. */
-static struct tree_niter_desc *
+static tree
niter_for_exit (struct ivopts_data *data, edge exit)
{
- struct nfe_cache_elt *nfe_desc;
- PTR *slot;
+ struct tree_niter_desc desc;
+ tree niter;
+ void **slot;
- slot = htab_find_slot_with_hash (data->niters, exit,
- htab_hash_pointer (exit),
- INSERT);
-
- if (!*slot)
+ if (!data->niters)
{
- nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
- nfe_desc->exit = exit;
- nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
- exit, &nfe_desc->niter);
- *slot = nfe_desc;
+ data->niters = pointer_map_create ();
+ slot = NULL;
}
else
- nfe_desc = *slot;
+ slot = pointer_map_contains (data->niters, exit);
+
+ if (!slot)
+ {
+ /* Try to determine number of iterations. We must know it
+ unconditionally (i.e., without possibility of # of iterations
+ being zero). Also, we cannot safely work with ssa names that
+ appear in phi nodes on abnormal edges, so that we do not create
+ overlapping life ranges for them (PR 27283). */
+ if (number_of_iterations_exit (data->current_loop,
+ exit, &desc, true)
+ && integer_zerop (desc.may_be_zero)
+ && !contains_abnormal_ssa_name_p (desc.niter))
+ niter = desc.niter;
+ else
+ niter = NULL_TREE;
- if (!nfe_desc->valid_p)
- return NULL;
+ *pointer_map_insert (data->niters, exit) = niter;
+ }
+ else
+ niter = (tree) *slot;
- return &nfe_desc->niter;
+ return niter;
}
-/* Returns structure describing number of iterations determined from
+/* Returns tree describing number of iterations determined from
single dominating exit of DATA->current_loop, or NULL if something
goes wrong. */
-static struct tree_niter_desc *
+static tree
niter_for_single_dom_exit (struct ivopts_data *data)
{
edge exit = single_dom_exit (data->current_loop);
}
/* Initializes data structures used by the iv optimization pass, stored
- in DATA. LOOPS is the loop tree. */
+ in DATA. */
static void
-tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
+tree_ssa_iv_optimize_init (struct ivopts_data *data)
{
- unsigned i;
-
data->version_info_size = 2 * num_ssa_names;
- data->version_info = xcalloc (data->version_info_size,
- sizeof (struct version_info));
+ 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));
-
+ data->niters = NULL;
data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
determine_base_object (tree expr)
{
enum tree_code code = TREE_CODE (expr);
- tree base, obj, op0, op1;
+ tree base, obj;
+
+ /* If this is a pointer casted to any type, we need to determine
+ the base object for the pointer; so handle conversions before
+ throwing away non-pointer expressions. */
+ if (TREE_CODE (expr) == NOP_EXPR
+ || TREE_CODE (expr) == CONVERT_EXPR)
+ return determine_base_object (TREE_OPERAND (expr, 0));
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
return NULL_TREE;
if (TREE_CODE (base) == INDIRECT_REF)
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 POINTER_PLUS_EXPR:
+ return determine_base_object (TREE_OPERAND (expr, 0));
case PLUS_EXPR:
case MINUS_EXPR:
- op0 = determine_base_object (TREE_OPERAND (expr, 0));
- op1 = determine_base_object (TREE_OPERAND (expr, 1));
-
- if (!op1)
- return op0;
-
- if (!op0)
- return (code == PLUS_EXPR
- ? op1
- : fold (build1 (NEGATE_EXPR, ptr_type_node, op1)));
-
- return fold (build (code, ptr_type_node, op0, op1));
-
- case NOP_EXPR:
- case CONVERT_EXPR:
- return determine_base_object (TREE_OPERAND (expr, 0));
+ /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
+ gcc_unreachable ();
default:
return fold_convert (ptr_type_node, expr);
static struct iv *
alloc_iv (tree base, tree step)
{
- struct iv *iv = xcalloc (1, sizeof (struct iv));
-
- if (step && integer_zerop (step))
- step = NULL_TREE;
+ struct iv *iv = XCNEW (struct iv);
+ gcc_assert (step != NULL_TREE);
iv->base = base;
iv->base_object = determine_base_object (base);
get_iv (struct ivopts_data *data, tree var)
{
basic_block bb;
-
+ tree type = TREE_TYPE (var);
+
+ if (!POINTER_TYPE_P (type)
+ && !INTEGRAL_TYPE_P (type))
+ return NULL;
+
if (!name_info (data, var)->iv)
{
bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
if (!bb
|| !flow_bb_inside_loop_p (data->current_loop, bb))
- set_iv (data, var, var, NULL_TREE);
+ set_iv (data, var, var, build_int_cst (type, 0));
}
return name_info (data, var)->iv;
}
-/* 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;
-}
-
-/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
-
-static bool
-abnormal_ssa_name_p (tree exp)
-{
- if (!exp)
- return false;
-
- if (TREE_CODE (exp) != SSA_NAME)
- return false;
-
- return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
-}
-
-/* Returns false if BASE or INDEX contains a ssa name that occurs in an
- abnormal phi node. Callback for for_each_index. */
-
-static bool
-idx_contains_abnormal_ssa_name_p (tree base, tree *index,
- void *data ATTRIBUTE_UNUSED)
-{
- if (TREE_CODE (base) == ARRAY_REF)
- {
- if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
- return false;
- if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
- return false;
- }
-
- return !abnormal_ssa_name_p (*index);
-}
-
-/* Returns true if EXPR contains a ssa name that occurs in an
- abnormal phi node. */
-
-static bool
-contains_abnormal_ssa_name_p (tree expr)
-{
- enum tree_code code = TREE_CODE (expr);
- enum tree_code_class class = TREE_CODE_CLASS (code);
-
- if (code == SSA_NAME)
- return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
-
- if (code == INTEGER_CST
- || is_gimple_min_invariant (expr))
- return false;
-
- if (code == ADDR_EXPR)
- return !for_each_index (&TREE_OPERAND (expr, 0),
- idx_contains_abnormal_ssa_name_p,
- NULL);
-
- switch (class)
- {
- case tcc_binary:
- case tcc_comparison:
- if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
- return true;
-
- /* Fallthru. */
- case tcc_unary:
- if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
- return true;
-
- break;
-
- default:
- gcc_unreachable ();
- }
-
- return false;
+ return integer_zerop (iv.step) ? NULL_TREE : iv.step;
}
/* Finds basic ivs. */
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)
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
return false;
- lhs = TREE_OPERAND (stmt, 0);
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step))
+ if (!simple_iv (loop, stmt, GIMPLE_STMT_OPERAND (stmt, 1), iv, true))
return false;
+ iv->base = expand_simple_operations (iv->base);
- /* 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))
- return false;
-
- 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, GIMPLE_STMT_OPERAND (stmt, 0), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
- struct tree_niter_desc *niter;
-
- niter = niter_for_single_dom_exit (data);
+ tree niter = niter_for_single_dom_exit (data);
if (niter)
{
fprintf (dump_file, " number of iterations ");
- print_generic_expr (dump_file, niter->niter, TDF_SLIM);
- fprintf (dump_file, "\n");
-
- fprintf (dump_file, " may be zero if ");
- print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
- fprintf (dump_file, "\n");
- fprintf (dump_file, "\n");
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, "\n\n");
};
fprintf (dump_file, "Induction variables:\n\n");
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;
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
}
-/* Checks whether the use OP is interesting and if so, records it
- as TYPE. */
+/* Checks whether the use OP is interesting and if so, records it. */
static struct iv_use *
-find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
- enum use_type type)
+find_interesting_uses_op (struct ivopts_data *data, tree op)
{
struct iv *iv;
struct iv *civ;
{
use = iv_use (data, iv->use_id);
- gcc_assert (use->type == USE_NONLINEAR_EXPR
- || use->type == USE_OUTER);
-
- if (type == USE_NONLINEAR_EXPR)
- use->type = USE_NONLINEAR_EXPR;
+ gcc_assert (use->type == USE_NONLINEAR_EXPR);
return use;
}
- if (zero_p (iv->step))
+ if (integer_zerop (iv->step))
{
record_invariant (data, op, true);
return NULL;
}
iv->have_use_for = true;
- civ = xmalloc (sizeof (struct iv));
+ civ = XNEW (struct iv);
*civ = *iv;
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (TREE_CODE (stmt) == PHI_NODE
- || TREE_CODE (stmt) == MODIFY_EXPR);
+ || TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
- use = record_use (data, NULL, civ, stmt, type);
+ use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
iv->use_id = use->id;
return use;
}
-/* Checks whether the use OP is interesting and if so, records it. */
-
-static struct iv_use *
-find_interesting_uses_op (struct ivopts_data *data, tree op)
-{
- return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
-}
-
-/* Records a definition of induction variable OP that is used outside of the
- loop. */
-
-static struct iv_use *
-find_interesting_uses_outer (struct ivopts_data *data, tree op)
-{
- return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
-}
-
-/* Checks whether the condition *COND_P in STMT is interesting
- and if so, records it. */
+/* Given a condition *COND_P, checks whether it is a compare of an induction
+ variable and an invariant. If this is the case, CONTROL_VAR is set
+ to location of the iv, BOUND to the location of the invariant,
+ IV_VAR and IV_BOUND are set to the corresponding induction variable
+ descriptions, and true is returned. If this is not the case,
+ CONTROL_VAR and BOUND are set to the arguments of the condition and
+ false is returned. */
-static void
-find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+static bool
+extract_cond_operands (struct ivopts_data *data, tree *cond_p,
+ tree **control_var, tree **bound,
+ struct iv **iv_var, struct iv **iv_bound)
{
- tree *op0_p;
- tree *op1_p;
- struct iv *iv0 = NULL, *iv1 = NULL, *civ;
- struct iv const_iv;
- tree zero = integer_zero_node;
-
- const_iv.step = NULL_TREE;
+ /* The nodes returned when COND has just one operand. Note that you should
+ not modify anything in BOUND or IV_BOUND because of this. */
+ static struct iv const_iv;
+ static tree zero;
+ tree cond = *cond_p;
+ tree *op0 = &zero, *op1 = &zero, *tmp_op;
+ struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+ bool ret = false;
- if (TREE_CODE (*cond_p) != SSA_NAME
- && !COMPARISON_CLASS_P (*cond_p))
- return;
+ zero = integer_zero_node;
+ const_iv.step = integer_zero_node;
- if (TREE_CODE (*cond_p) == SSA_NAME)
+ if (TREE_CODE (cond) == SSA_NAME)
{
- op0_p = cond_p;
- op1_p = &zero;
+ op0 = cond_p;
+ iv0 = get_iv (data, cond);
+ ret = (iv0 && !integer_zerop (iv0->step));
+ goto end;
}
- else
+
+ if (!COMPARISON_CLASS_P (cond))
{
- op0_p = &TREE_OPERAND (*cond_p, 0);
- op1_p = &TREE_OPERAND (*cond_p, 1);
+ op0 = cond_p;
+ goto end;
}
- if (TREE_CODE (*op0_p) == SSA_NAME)
- iv0 = get_iv (data, *op0_p);
- else
- iv0 = &const_iv;
+ op0 = &TREE_OPERAND (cond, 0);
+ op1 = &TREE_OPERAND (cond, 1);
+ if (TREE_CODE (*op0) == SSA_NAME)
+ iv0 = get_iv (data, *op0);
+ if (TREE_CODE (*op1) == SSA_NAME)
+ iv1 = get_iv (data, *op1);
- if (TREE_CODE (*op1_p) == SSA_NAME)
- iv1 = get_iv (data, *op1_p);
- else
- iv1 = &const_iv;
+ /* Exactly one of the compared values must be an iv, and the other one must
+ be an invariant. */
+ if (!iv0 || !iv1)
+ goto end;
- if (/* When comparing with non-invariant value, we may not do any senseful
- induction variable elimination. */
- (!iv0 || !iv1)
- /* Eliminating condition based on two ivs would be nontrivial.
- ??? TODO -- it is not really important to handle this case. */
- || (!zero_p (iv0->step) && !zero_p (iv1->step)))
+ if (integer_zerop (iv0->step))
{
- find_interesting_uses_op (data, *op0_p);
- find_interesting_uses_op (data, *op1_p);
- return;
+ /* Control variable may be on the other side. */
+ tmp_op = op0; op0 = op1; op1 = tmp_op;
+ tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
}
+ ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
+
+end:
+ if (control_var)
+ *control_var = op0;;
+ if (iv_var)
+ *iv_var = iv0;;
+ if (bound)
+ *bound = op1;
+ if (iv_bound)
+ *iv_bound = iv1;
+
+ return ret;
+}
- if (zero_p (iv0->step) && zero_p (iv1->step))
+/* Checks whether the condition *COND_P in STMT is interesting
+ and if so, records it. */
+
+static void
+find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+{
+ tree *var_p, *bound_p;
+ struct iv *var_iv, *civ;
+
+ if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
{
- /* If both are invariants, this is a work for unswitching. */
+ find_interesting_uses_op (data, *var_p);
+ find_interesting_uses_op (data, *bound_p);
return;
}
- civ = xmalloc (sizeof (struct iv));
- *civ = zero_p (iv0->step) ? *iv1: *iv0;
+ civ = XNEW (struct iv);
+ *civ = *var_iv;
record_use (data, cond_p, civ, stmt, USE_COMPARE);
}
return true;
}
- if (!EXPR_P (expr))
+ if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
return false;
- len = TREE_CODE_LENGTH (TREE_CODE (expr));
+ len = TREE_OPERAND_LENGTH (expr);
for (i = 0; i < len; i++)
if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
return false;
{
struct ivopts_data *ivopts_data;
tree stmt;
- tree *step_p;
+ tree step;
};
static bool
idx_find_step (tree base, tree *idx, void *data)
{
- struct ifs_ivopts_data *dta = data;
+ struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
struct iv *iv;
- tree step, type, iv_type, iv_step, lbound, off;
+ tree step, iv_base, iv_step, lbound, off;
struct loop *loop = dta->ivopts_data->current_loop;
if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
if (!iv)
return false;
+ /* XXX We produce for a base of *D42 with iv->base being &x[0]
+ *&x[0], which is not folded and does not trigger the
+ ARRAY_REF path below. */
*idx = iv->base;
- if (!iv->step)
+ if (integer_zerop (iv->step))
return true;
- 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);
-
- 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);
+ step = build_int_cst (sizetype, 1);
- if (!iv_step)
+ iv_base = iv->base;
+ iv_step = iv->step;
+ if (!convert_affine_scev (dta->ivopts_data->current_loop,
+ sizetype, &iv_base, &iv_step, dta->stmt,
+ false))
{
/* The index might wrap. */
return false;
}
- step = fold_binary_to_constant (MULT_EXPR, type, 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);
+ step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
+ dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step);
return true;
}
static bool
idx_record_use (tree base, tree *idx,
- void *data)
+ void *vdata)
{
+ struct ivopts_data *data = (struct ivopts_data *) vdata;
find_interesting_uses_op (data, *idx);
if (TREE_CODE (base) == ARRAY_REF)
{
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. */
return false;
}
-/* Finds addresses in *OP_P inside STMT. */
+/* Return true if EXPR may be non-addressable. */
-static void
-find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
+static bool
+may_be_nonaddressable_p (tree expr)
{
- tree base = unshare_expr (*op_p), step = NULL;
+ switch (TREE_CODE (expr))
+ {
+ case COMPONENT_REF:
+ return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
+ || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ case VIEW_CONVERT_EXPR:
+ /* This kind of view-conversions may wrap non-addressable objects
+ and make them look addressable. After some processing the
+ non-addressability may be uncovered again, causing ADDR_EXPRs
+ of inappropriate objects to be built. */
+ return AGGREGATE_TYPE_P (TREE_TYPE (expr))
+ && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
+
+ default:
+ break;
+ }
+
+ return false;
+}
+
+/* Finds addresses in *OP_P inside STMT. */
+
+static void
+find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
+{
+ tree base = *op_p, step = build_int_cst (sizetype, 0);
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
/* Ignore bitfields for now. Not really something terribly complicated
to handle. TODO. */
- if (TREE_CODE (base) == COMPONENT_REF
- && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
+ if (TREE_CODE (base) == BIT_FIELD_REF)
+ goto fail;
+
+ if (may_be_nonaddressable_p (base))
goto fail;
if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base))
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))
- goto fail;
+ 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 (astep)
+ {
+ if (TMR_STEP (base))
+ astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
- gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+ step = fold_build2 (PLUS_EXPR, type, step, astep);
+ }
+ }
- if (TREE_CODE (base) == INDIRECT_REF)
- base = TREE_OPERAND (base, 0);
+ if (integer_zerop (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 = build_int_cst (sizetype, 0);
+ if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
+ || integer_zerop (ifs_ivopts_data.step))
+ goto fail;
+ step = ifs_ivopts_data.step;
+
+ gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
+ gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+
+ base = build_fold_addr_expr (base);
+
+ /* Substituting bases of IVs into the base expression might
+ have caused folding opportunities. */
+ if (TREE_CODE (base) == ADDR_EXPR)
+ {
+ tree *ref = &TREE_OPERAND (base, 0);
+ while (handled_component_p (*ref))
+ ref = &TREE_OPERAND (*ref, 0);
+ if (TREE_CODE (*ref) == INDIRECT_REF)
+ *ref = fold_indirect_ref (*ref);
+ }
+ }
civ = alloc_iv (base, step);
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
- {
- 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) == MODIFY_EXPR)
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
{
- lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ rhs = GIMPLE_STMT_OPERAND (stmt, 1);
if (TREE_CODE (lhs) == SSA_NAME)
{
iv = get_iv (data, lhs);
- if (iv && !zero_p (iv->step))
+ if (iv && !integer_zerop (iv->step))
return;
}
switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
{
case tcc_comparison:
- find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
+ find_interesting_uses_cond (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 1));
return;
case tcc_reference:
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
+ find_interesting_uses_address (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 1));
if (REFERENCE_CLASS_P (lhs))
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
+ find_interesting_uses_address (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 0));
return;
default: ;
if (REFERENCE_CLASS_P (lhs)
&& is_gimple_val (rhs))
{
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
+ find_interesting_uses_address (data, stmt,
+ &GIMPLE_STMT_OPERAND (stmt, 0));
find_interesting_uses_op (data, rhs);
return;
}
lhs = PHI_RESULT (stmt);
iv = get_iv (data, lhs);
- if (iv && !zero_p (iv->step))
+ if (iv && !integer_zerop (iv->step))
return;
}
- 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;
for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
{
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
- find_interesting_uses_outer (data, def);
+ if (is_gimple_reg (def))
+ find_interesting_uses_op (data, def);
}
}
}
/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
- is true, assume we are inside an address. */
+ 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 (tree expr, bool inside_addr, unsigned HOST_WIDE_INT *offset)
+strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
+ unsigned HOST_WIDE_INT *offset)
{
- tree op0 = NULL_TREE, op1 = NULL_TREE, step;
+ 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;
{
case INTEGER_CST:
if (!cst_and_fits_in_hwi (expr)
- || zero_p (expr))
+ || integer_zerop (expr))
return orig_expr;
*offset = int_cst_value (expr);
- return build_int_cst_type (orig_type, 0);
+ return build_int_cst (orig_type, 0);
case PLUS_EXPR:
case MINUS_EXPR:
op0 = TREE_OPERAND (expr, 0);
op1 = TREE_OPERAND (expr, 1);
- op0 = strip_offset (op0, false, &off0);
- op1 = strip_offset (op1, false, &off1);
+ 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))
+ if (integer_zerop (op1))
expr = op0;
- else if (zero_p (op0))
+ else if (integer_zerop (op0))
{
if (code == PLUS_EXPR)
expr = op1;
else
- expr = build1 (NEGATE_EXPR, type, op1);
+ expr = fold_build1 (NEGATE_EXPR, type, op1);
}
else
- expr = build2 (code, type, op0, op1);
+ expr = fold_build2 (code, type, op0, op1);
return fold_convert (orig_type, expr);
st = int_cst_value (step);
op1 = TREE_OPERAND (expr, 1);
- op1 = strip_offset (op1, false, &off1);
+ op1 = strip_offset_1 (op1, false, false, &off1);
*offset = off1 * st;
+
+ if (top_compref
+ && integer_zerop (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:
- inside_addr = true;
+ 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:
/* Default handling of expressions for that we want to recurse into
the first operand. */
op0 = TREE_OPERAND (expr, 0);
- op0 = strip_offset (op0, inside_addr, &off0);
+ op0 = strip_offset_1 (op0, inside_addr, false, &off0);
*offset += off0;
if (op0 == TREE_OPERAND (expr, 0)
if (op1)
TREE_OPERAND (expr, 1) = op1;
- return fold_convert (orig_type, expr);
+ /* 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 *. */
+ We return unsigned type with the same precision, which avoids problems
+ with overflows. */
static tree
generic_type_for (tree type)
{
if (POINTER_TYPE_P (type))
- return ptr_type_node;
+ return unsigned_type_for (type);
if (TYPE_UNSIGNED (type))
return type;
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 = (bitmap *) 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
if (type != orig_type)
{
base = fold_convert (type, base);
- if (step)
- step = fold_convert (type, step);
+ step = fold_convert (type, step);
}
}
if (!base && !step)
continue;
- if (!operand_equal_p (base, cand->iv->base, 0))
- continue;
-
- if (zero_p (cand->iv->step))
- {
- if (zero_p (step))
- break;
- }
- else
- {
- if (step && operand_equal_p (step, cand->iv->step, 0))
- break;
- }
+ if (operand_equal_p (base, cand->iv->base, 0)
+ && operand_equal_p (step, cand->iv->step, 0))
+ break;
}
if (i == n_iv_cands (data))
{
- cand = xcalloc (1, sizeof (struct iv_cand));
+ cand = XCNEW (struct iv_cand);
cand->id = i;
if (!base && !step)
cand->incremented_at = incremented_at;
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);
}
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
iv = ver_info (data, i)->iv;
- if (iv && iv->biv_p && !zero_p (iv->step))
+ if (iv && iv->biv_p && !integer_zerop (iv->step))
add_old_iv_candidates (data, iv);
}
}
add_iv_value_candidates (struct ivopts_data *data,
struct iv *iv, struct iv_use *use)
{
- add_candidate (data, iv->base, iv->step, false, use);
-
- /* The same, but with initial value zero. */
- add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
- 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;
unsigned HOST_WIDE_INT offset;
+ tree base;
- /* 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);
+ add_candidate (data, iv->base, iv->step, false, use);
- if (TREE_CODE (base) == INDIRECT_REF)
- base = TREE_OPERAND (base, 0);
- else
- base = build_addr (base);
- add_candidate (data, base, iv->step, false, use);
- }
- }
+ /* 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, true, use);
/* Third, try removing the constant offset. */
- abase = iv->base;
- base = strip_offset (abase, false, &offset);
+ base = strip_offset (iv->base, &offset);
if (offset)
add_candidate (data, base, iv->step, false, use);
}
-/* 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;
-
- /* We must know where we exit the loop and how many times does it roll. */
- 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);
-}
-
/* Adds candidates based on the uses. */
static void
{
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;
- case USE_OUTER:
- add_iv_value_candidates (data, use->iv, use);
-
- /* Additionally, add the pseudocandidate for the possibility to
- replace the final value by a direct computation. */
- add_iv_outer_candidates (data, use);
- break;
-
- case USE_ADDRESS:
- add_address_candidates (data, use->iv, use);
- break;
-
default:
gcc_unreachable ();
}
}
use->n_map_members = size;
- use->cost_map = xcalloc (size, sizeof (struct cost_pair));
+ use->cost_map = XCNEWVEC (struct cost_pair, size);
}
}
{
const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
x = gen_rtx_SYMBOL_REF (Pmode, name);
+ SET_SYMBOL_REF_DECL (x, obj);
+ x = gen_rtx_MEM (DECL_MODE (obj), x);
+ targetm.encode_section_info (obj, x, true);
}
else
- x = gen_raw_REG (Pmode, (*regno)++);
+ {
+ x = gen_raw_REG (Pmode, (*regno)++);
+ x = gen_rtx_MEM (DECL_MODE (obj), x);
+ }
- return gen_rtx_MEM (DECL_MODE (obj), x);
+ return x;
}
/* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
{
tree obj = NULL_TREE;
rtx x = NULL_RTX;
- int *regno = data;
+ int *regno = (int *) data;
switch (TREE_CODE (*expr_p))
{
expr_p = &TREE_OPERAND (*expr_p, 0))
continue;
obj = *expr_p;
- if (DECL_P (obj))
+ if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
x = produce_memory_decl_rtl (obj, regno);
break;
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. */
-static tree
-get_computation_at (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at)
+int
+tree_int_cst_sign_bit (tree t)
{
- tree ubase = use->iv->base;
- tree ustep = use->iv->step;
- tree cbase = cand->iv->base;
- tree cstep = cand->iv->step;
- tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
- tree uutype;
- tree expr, delta;
- tree ratio;
- unsigned HOST_WIDE_INT ustepi, cstepi;
- HOST_WIDE_INT ratioi;
+ unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
+ unsigned HOST_WIDE_INT w;
- if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
+ if (bitno < HOST_BITS_PER_WIDE_INT)
+ w = TREE_INT_CST_LOW (t);
+ else
{
- /* We do not have a precision to express the values of use. */
- return NULL_TREE;
+ w = TREE_INT_CST_HIGH (t);
+ bitno -= HOST_BITS_PER_WIDE_INT;
}
- expr = var_at_stmt (loop, cand, at);
+ return (w >> bitno) & 1;
+}
- if (TREE_TYPE (expr) != ctype)
- {
- /* This may happen with the original ivs. */
- expr = fold_convert (ctype, expr);
- }
+/* If we can prove that TOP = cst * BOT for some constant cst,
+ store cst to MUL and return true. Otherwise return false.
+ The returned value is always sign-extended, regardless of the
+ signedness of TOP and BOT. */
- if (TYPE_UNSIGNED (utype))
- uutype = utype;
- else
+static bool
+constant_multiple_of (tree top, tree bot, double_int *mul)
+{
+ tree mby;
+ enum tree_code code;
+ double_int res, p0, p1;
+ unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
+
+ STRIP_NOPS (top);
+ STRIP_NOPS (bot);
+
+ if (operand_equal_p (top, bot, 0))
{
- uutype = unsigned_type_for (utype);
- ubase = fold_convert (uutype, ubase);
- ustep = fold_convert (uutype, ustep);
+ *mul = double_int_one;
+ return true;
}
- if (uutype != ctype)
+ code = TREE_CODE (top);
+ switch (code)
{
- expr = fold_convert (uutype, expr);
- cbase = fold_convert (uutype, cbase);
- cstep = fold_convert (uutype, cstep);
+ case MULT_EXPR:
+ mby = TREE_OPERAND (top, 1);
+ if (TREE_CODE (mby) != INTEGER_CST)
+ return false;
+
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
+ return false;
+
+ *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
+ precision);
+ return true;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
+ || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
+ return false;
+
+ if (code == MINUS_EXPR)
+ p1 = double_int_neg (p1);
+ *mul = double_int_sext (double_int_add (p0, p1), precision);
+ return true;
+
+ case INTEGER_CST:
+ if (TREE_CODE (bot) != INTEGER_CST)
+ return false;
+
+ p0 = double_int_sext (tree_to_double_int (top), precision);
+ p1 = double_int_sext (tree_to_double_int (bot), precision);
+ if (double_int_zero_p (p1))
+ return false;
+ *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
+ precision);
+ return double_int_zero_p (res);
+
+ default:
+ return false;
}
+}
- if (!cst_and_fits_in_hwi (cstep)
- || !cst_and_fits_in_hwi (ustep))
- return NULL_TREE;
+/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
+ same precision that is at least as wide as the precision of TYPE, stores
+ BA to A and BB to B, and returns the type of BA. Otherwise, returns the
+ type of A and B. */
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
+static tree
+determine_common_wider_type (tree *a, tree *b)
+{
+ tree wider_type = NULL;
+ tree suba, subb;
+ tree atype = TREE_TYPE (*a);
- if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
+ if ((TREE_CODE (*a) == NOP_EXPR
+ || TREE_CODE (*a) == CONVERT_EXPR))
{
- /* 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;
+ suba = TREE_OPERAND (*a, 0);
+ wider_type = TREE_TYPE (suba);
+ if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
+ return atype;
}
+ else
+ return atype;
- /* 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 ((TREE_CODE (*b) == NOP_EXPR
+ || TREE_CODE (*b) == CONVERT_EXPR))
+ {
+ subb = TREE_OPERAND (*b, 0);
+ if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
+ return atype;
+ }
+ else
+ return atype;
- /* use = ubase - ratio * cbase + ratio * var.
+ *a = suba;
+ *b = subb;
+ return wider_type;
+}
- 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. */
+/* 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 cbase = cand->iv->base;
+ tree cstep = cand->iv->step, cstep_common;
+ tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+ tree common_type, var;
+ tree uutype;
+ aff_tree cbase_aff, var_aff;
+ double_int rat;
- if (ratioi == 1)
+ if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
- delta = fold (build2 (MINUS_EXPR, uutype, ubase, cbase));
- expr = fold (build2 (PLUS_EXPR, uutype, expr, delta));
+ /* We do not have a precision to express the values of use. */
+ return false;
}
- else if (ratioi == -1)
+
+ var = var_at_stmt (loop, cand, at);
+ uutype = unsigned_type_for (utype);
+
+ /* If the conversion is not noop, perform it. */
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
- delta = fold (build2 (PLUS_EXPR, uutype, ubase, cbase));
- expr = fold (build2 (MINUS_EXPR, uutype, delta, expr));
+ cstep = fold_convert (uutype, cstep);
+ cbase = fold_convert (uutype, cbase);
+ var = fold_convert (uutype, var);
}
- else
+
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ return false;
+
+ /* In case both UBASE and CBASE are shortened to UUTYPE from some common
+ type, we achieve better folding by computing their difference in this
+ wider type, and cast the result to UUTYPE. We do not need to worry about
+ overflows, as all the arithmetics will in the end be performed in UUTYPE
+ anyway. */
+ common_type = determine_common_wider_type (&ubase, &cbase);
+
+ /* use = ubase - ratio * cbase + ratio * var. */
+ tree_to_aff_combination (ubase, common_type, aff);
+ tree_to_aff_combination (cbase, common_type, &cbase_aff);
+ tree_to_aff_combination (var, uutype, &var_aff);
+
+ /* We need to shift the value if we are after the increment. */
+ if (stmt_after_increment (loop, cand, at))
{
- 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));
+ aff_tree cstep_aff;
+
+ if (common_type != uutype)
+ cstep_common = fold_convert (common_type, cstep);
+ else
+ cstep_common = cstep;
+
+ tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
+ aff_combination_add (&cbase_aff, &cstep_aff);
}
- return fold_convert (utype, expr);
+ aff_combination_scale (&cbase_aff, double_int_neg (rat));
+ aff_combination_add (aff, &cbase_aff);
+ if (common_type != uutype)
+ aff_combination_convert (aff, uutype);
+
+ aff_combination_scale (&var_aff, rat);
+ aff_combination_add (aff, &var_aff);
+
+ return true;
}
/* Determines the expression by that USE is expressed from induction variable
- CAND in LOOP. */
+ CAND at statement AT in LOOP. The computation is unshared. */
+
+static tree
+get_computation_at (struct loop *loop,
+ struct iv_use *use, struct iv_cand *cand, tree at)
+{
+ aff_tree aff;
+ tree type = TREE_TYPE (use->iv->base);
+
+ 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)
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 ();
static hashval_t
mbc_entry_hash (const void *entry)
{
- const struct mbc_entry *e = entry;
+ const struct mbc_entry *e = (const struct mbc_entry *) entry;
return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
}
static int
mbc_entry_eq (const void *entry1, const void *entry2)
{
- const struct mbc_entry *e1 = entry1;
- const struct mbc_entry *e2 = entry2;
+ const struct mbc_entry *e1 = (const struct mbc_entry *) entry1;
+ const struct mbc_entry *e2 = (const struct mbc_entry *) entry2;
return (e1->mode == e2->mode
&& e1->cst == e2->cst);
/* 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 an address. Test the
+ validity for a memory reference accessing memory of mode MODE. */
+
+bool
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
+{
+#define MAX_RATIO 128
+ static sbitmap valid_mult[MAX_MACHINE_MODE];
+
+ if (!valid_mult[mode])
+ {
+ rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+ rtx addr;
+ HOST_WIDE_INT i;
+
+ valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
+ sbitmap_zero (valid_mult[mode]);
+ addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
+ for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
+ {
+ XEXP (addr, 1) = gen_int_mode (i, Pmode);
+ if (memory_address_p (mode, addr))
+ SET_BIT (valid_mult[mode], i + MAX_RATIO);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " allowed multipliers:");
+ for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
+ if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
+ fprintf (dump_file, " %d", (int) i);
+ fprintf (dump_file, "\n");
+ fprintf (dump_file, "\n");
+ }
+ }
+
+ if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
+ return false;
+
+ return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
+}
+
/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
- variable is omitted. The created memory accesses MODE.
-
+ variable is omitted. Compute the cost for a memory reference that accesses
+ a memory location of mode MEM_MODE.
+
TODO -- there must be some better way. This all is quite crude. */
static unsigned
get_address_cost (bool symbol_present, bool var_present,
- unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
+ unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
+ enum machine_mode mem_mode)
{
-#define MAX_RATIO 128
- static sbitmap valid_mult;
- static HOST_WIDE_INT rat, off;
- static HOST_WIDE_INT min_offset, max_offset;
- static unsigned costs[2][2][2][2];
+ static bool initialized[MAX_MACHINE_MODE];
+ static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
+ static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
+ static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
unsigned cost, acost;
- rtx seq, addr, base;
bool offset_p, ratio_p;
- rtx reg1;
HOST_WIDE_INT s_offset;
unsigned HOST_WIDE_INT mask;
unsigned bits;
- if (!valid_mult)
+ if (!initialized[mem_mode])
{
HOST_WIDE_INT i;
+ HOST_WIDE_INT start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
+ int old_cse_not_expected;
+ unsigned sym_p, var_p, off_p, rat_p, add_c;
+ rtx seq, addr, base;
+ rtx reg0, reg1;
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
+ initialized[mem_mode] = true;
+
+ reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
- for (i = 1; i <= 1 << 20; i <<= 1)
+ for (i = start; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = GEN_INT (i);
- if (!memory_address_p (Pmode, addr))
+ XEXP (addr, 1) = gen_int_mode (i, Pmode);
+ if (!memory_address_p (mem_mode, addr))
break;
}
- max_offset = i >> 1;
- off = max_offset;
+ max_offset[mem_mode] = i == start ? 0 : i >> 1;
+ off[mem_mode] = max_offset[mem_mode];
- for (i = 1; i <= 1 << 20; i <<= 1)
+ for (i = start; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = GEN_INT (-i);
- if (!memory_address_p (Pmode, addr))
+ XEXP (addr, 1) = gen_int_mode (-i, Pmode);
+ if (!memory_address_p (mem_mode, addr))
break;
}
- min_offset = -(i >> 1);
+ min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "get_address_cost:\n");
- fprintf (dump_file, " min offset %d\n", (int) min_offset);
- fprintf (dump_file, " max offset %d\n", (int) max_offset);
+ fprintf (dump_file, " min offset %s %d\n",
+ GET_MODE_NAME (mem_mode),
+ (int) min_offset[mem_mode]);
+ fprintf (dump_file, " max offset %s %d\n",
+ GET_MODE_NAME (mem_mode),
+ (int) max_offset[mem_mode]);
}
- 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++)
+ rat[mem_mode] = 1;
+ for (i = 2; i <= MAX_RATIO; i++)
+ if (multiplier_allowed_in_address_p (i, mem_mode))
+ {
+ rat[mem_mode] = i;
+ break;
+ }
+
+ /* Compute the cost of various addressing modes. */
+ acost = 0;
+ reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+ reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
+
+ for (i = 0; i < 16; i++)
{
- XEXP (addr, 1) = GEN_INT (i);
- if (memory_address_p (Pmode, addr))
+ sym_p = i & 1;
+ var_p = (i >> 1) & 1;
+ off_p = (i >> 2) & 1;
+ rat_p = (i >> 3) & 1;
+
+ addr = reg0;
+ if (rat_p)
+ addr = gen_rtx_fmt_ee (MULT, Pmode, addr,
+ gen_int_mode (rat[mem_mode], Pmode));
+
+ if (var_p)
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+
+ if (sym_p)
{
- SET_BIT (valid_mult, i + MAX_RATIO);
- rat = i;
+ base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
+ /* ??? We can run into trouble with some backends by presenting
+ it with symbols which havn't been properly passed through
+ targetm.encode_section_info. By setting the local bit, we
+ enhance the probability of things working. */
+ SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
+
+ if (off_p)
+ base = gen_rtx_fmt_e (CONST, Pmode,
+ gen_rtx_fmt_ee (PLUS, Pmode,
+ base,
+ gen_int_mode (off[mem_mode],
+ Pmode)));
}
+ else if (off_p)
+ base = gen_int_mode (off[mem_mode], Pmode);
+ else
+ base = NULL_RTX;
+
+ if (base)
+ addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
+
+ start_sequence ();
+ /* To avoid splitting addressing modes, pretend that no cse will
+ follow. */
+ old_cse_not_expected = cse_not_expected;
+ cse_not_expected = true;
+ addr = memory_address (mem_mode, addr);
+ cse_not_expected = old_cse_not_expected;
+ seq = get_insns ();
+ end_sequence ();
+
+ acost = seq_cost (seq);
+ acost += address_cost (addr, mem_mode);
+
+ if (!acost)
+ acost = 1;
+ costs[mem_mode][sym_p][var_p][off_p][rat_p] = acost;
}
+ /* On some targets, it is quite expensive to load symbol to a register,
+ which makes addresses that contain symbols look much more expensive.
+ However, the symbol will have to be loaded in any case before the
+ loop (and quite likely we have it in register already), so it does not
+ make much sense to penalize them too heavily. So make some final
+ tweaks for the SYMBOL_PRESENT modes:
+
+ If VAR_PRESENT is false, and the mode obtained by changing symbol to
+ var is cheaper, use this mode with small penalty.
+ If VAR_PRESENT is true, try whether the mode with
+ SYMBOL_PRESENT = false is cheaper even with cost of addition, and
+ if this is the case, use it. */
+ add_c = add_cost (Pmode);
+ for (i = 0; i < 8; i++)
+ {
+ var_p = i & 1;
+ off_p = (i >> 1) & 1;
+ rat_p = (i >> 2) & 1;
+
+ acost = costs[mem_mode][0][1][off_p][rat_p] + 1;
+ if (var_p)
+ acost += add_c;
+
+ if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
+ costs[mem_mode][1][var_p][off_p][rat_p] = acost;
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, " 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, "Address costs:\n");
+
+ for (i = 0; i < 16; i++)
+ {
+ sym_p = i & 1;
+ var_p = (i >> 1) & 1;
+ off_p = (i >> 2) & 1;
+ rat_p = (i >> 3) & 1;
+
+ fprintf (dump_file, " ");
+ if (sym_p)
+ fprintf (dump_file, "sym + ");
+ if (var_p)
+ fprintf (dump_file, "var + ");
+ if (off_p)
+ fprintf (dump_file, "cst + ");
+ if (rat_p)
+ fprintf (dump_file, "rat * ");
+
+ acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
+ fprintf (dump_file, "index costs %d\n", acost);
+ }
fprintf (dump_file, "\n");
}
}
cost = 0;
offset_p = (s_offset != 0
- && min_offset <= s_offset && s_offset <= max_offset);
+ && min_offset[mem_mode] <= s_offset
+ && s_offset <= max_offset[mem_mode]);
ratio_p = (ratio != 1
- && -MAX_RATIO <= ratio && ratio <= MAX_RATIO
- && TEST_BIT (valid_mult, ratio + MAX_RATIO));
+ && multiplier_allowed_in_address_p (ratio, mem_mode));
if (ratio != 1 && !ratio_p)
cost += multiply_by_cost (ratio, Pmode);
if (s_offset && !offset_p && !symbol_present)
- {
- cost += add_cost (Pmode);
- var_present = true;
- }
-
- acost = costs[symbol_present][var_present][offset_p][ratio_p];
- if (!acost)
- {
- acost = 0;
-
- addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 1);
- if (ratio_p)
- addr = gen_rtx_fmt_ee (MULT, Pmode, addr, GEN_INT (rat));
-
- if (var_present)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
-
- if (symbol_present)
- {
- base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
- if (offset_p)
- base = gen_rtx_fmt_e (CONST, Pmode,
- gen_rtx_fmt_ee (PLUS, Pmode,
- base,
- GEN_INT (off)));
- }
- else if (offset_p)
- base = GEN_INT (off);
- else
- base = NULL_RTX;
-
- if (base)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
-
- start_sequence ();
- addr = memory_address (Pmode, addr);
- seq = get_insns ();
- end_sequence ();
-
- acost = seq_cost (seq);
- acost += address_cost (addr, Pmode);
-
- if (!acost)
- acost = 1;
- costs[symbol_present][var_present][offset_p][ratio_p] = acost;
- }
+ cost += add_cost (Pmode);
+ acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
return cost + acost;
}
-/* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
- the bitmap to that we should store it. */
+/* Estimates cost of forcing expression EXPR into a variable. */
-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;
-}
-
-/* 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)
+unsigned
+force_expr_to_var_cost (tree expr)
{
static bool costs_initialized = false;
static unsigned integer_cost;
if (!costs_initialized)
{
- tree var = create_tmp_var_raw (integer_type_node, "test_var");
- rtx x = gen_rtx_MEM (DECL_MODE (var),
- gen_rtx_SYMBOL_REF (Pmode, "test_var"));
- tree addr;
tree type = build_pointer_type (integer_type_node);
+ tree var, addr;
+ rtx x;
- integer_cost = computation_cost (build_int_cst_type (integer_type_node,
- 2000));
-
- SET_DECL_RTL (var, x);
+ var = create_tmp_var_raw (integer_type_node, "test_var");
TREE_STATIC (var) = 1;
+ x = produce_memory_decl_rtl (var, NULL);
+ SET_DECL_RTL (var, x);
+
+ integer_cost = computation_cost (build_int_cst (integer_type_node,
+ 2000));
+
addr = build1 (ADDR_EXPR, type, var);
symbol_cost = computation_cost (addr) + 1;
address_cost
- = computation_cost (build2 (PLUS_EXPR, type,
+ = computation_cost (build2 (POINTER_PLUS_EXPR, type,
addr,
- build_int_cst_type (type, 2000))) + 1;
+ build_int_cst (sizetype, 2000))) + 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "force_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);
STRIP_NOPS (expr);
- if (depends_on)
- {
- fd_ivopts_data = data;
- walk_tree (&expr, find_depends, depends_on, NULL);
- }
-
if (SSA_VAR_P (expr))
return 0;
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
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;
mode = TYPE_MODE (TREE_TYPE (expr));
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
cost = add_cost (mode);
return 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
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
- e1 = strip_offset (e1, false, &off1);
- e2 = strip_offset (e2, false, &off2);
+ e1 = strip_offset (e1, &off1);
+ e2 = strip_offset (e2, &off2);
*offset += off1 - off2;
STRIP_NOPS (e1);
return 0;
}
*var_present = true;
- if (zero_p (e2))
+ if (integer_zerop (e2))
return force_var_cost (data, e1, depends_on);
- if (zero_p (e1))
+ if (integer_zerop (e1))
{
cost = force_var_cost (data, e2, depends_on);
cost += multiply_by_cost (-1, mode);
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
tree utype = TREE_TYPE (ubase), ctype;
- unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
+ unsigned HOST_WIDE_INT cstepi, offset = 0;
HOST_WIDE_INT ratio, aratio;
bool var_present, symbol_present;
unsigned cost = 0, n_sums;
+ double_int rat;
*depends_on = NULL;
return INFTY;
}
- if (!cst_and_fits_in_hwi (ustep)
- || !cst_and_fits_in_hwi (cstep))
- return INFTY;
-
- if (TREE_CODE (ubase) == INTEGER_CST
- && !cst_and_fits_in_hwi (ubase))
- goto fallback;
-
- if (TREE_CODE (cbase) == INTEGER_CST
- && !cst_and_fits_in_hwi (cbase))
- goto fallback;
-
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
-
if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
}
- if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
+ /* CSTEPI is removed from the offset in case statement is after the
+ increment. If the step is not constant, we use zero instead.
+ This is a bit imprecise (there is the extra addition), but
+ redundancy elimination is likely to transform the code so that
+ it uses value of the variable before increment anyway,
+ so it is not that much unrealistic. */
+ if (cst_and_fits_in_hwi (cstep))
+ cstepi = int_cst_value (cstep);
+ else
+ cstepi = 0;
+
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ return INFTY;
+
+ if (double_int_fits_in_shwi_p (rat))
+ ratio = double_int_to_shwi (rat);
+ else
return INFTY;
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
(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,
(symbol/var/const parts may be omitted). If we are looking for an address,
find the cost of addressing this. */
if (address_p)
- return cost + get_address_cost (symbol_present, var_present, offset, ratio);
+ return cost + get_address_cost (symbol_present, var_present, offset, ratio,
+ TYPE_MODE (TREE_TYPE (*use->op_p)));
/* Otherwise estimate the costs for computing the expression. */
aratio = ratio > 0 ? ratio : -ratio;
return cost != INFTY;
}
-/* Computes value of induction variable IV in iteration NITER. */
+/* Computes value of candidate CAND at position AT in iteration NITER, and
+ stores it to VAL. */
-static tree
-iv_value (struct iv *iv, tree niter)
+static void
+cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter,
+ aff_tree *val)
{
- tree val;
+ aff_tree step, delta, nit;
+ struct iv *iv = cand->iv;
tree type = TREE_TYPE (iv->base);
- niter = fold_convert (type, niter);
- val = fold (build2 (MULT_EXPR, type, iv->step, niter));
-
- return fold (build2 (PLUS_EXPR, type, iv->base, val));
-}
-
-/* Computes value of candidate CAND at position AT in iteration NITER. */
-
-static tree
-cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
-{
- tree val = iv_value (cand->iv, niter);
- tree type = TREE_TYPE (cand->iv->base);
-
+ tree_to_aff_combination (iv->step, type, &step);
+ tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
+ aff_combination_convert (&nit, type);
+ aff_combination_mult (&nit, &step, &delta);
if (stmt_after_increment (loop, cand, at))
- val = fold (build2 (PLUS_EXPR, type, val, cand->iv->step));
+ aff_combination_add (&delta, &step);
- return val;
+ tree_to_aff_combination (iv->base, type, val);
+ aff_combination_add (val, &delta);
}
/* Returns period of induction variable iv. */
{
basic_block ex_bb;
edge exit;
- struct tree_niter_desc *niter;
tree nit, nit_type;
tree wider_type, period, per_type;
struct loop *loop = data->current_loop;
+ aff_tree bnd;
+ 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))
exit = EDGE_SUCC (ex_bb, 1);
if (flow_bb_inside_loop_p (loop, exit->dest))
- return false;
-
- niter = niter_for_exit (data, exit);
- if (!niter
- || !zero_p (niter->may_be_zero))
- return false;
-
- nit = niter->niter;
- nit_type = TREE_TYPE (nit);
-
- /* Determine whether we may use the variable to test whether niter iterations
- elapsed. This is the case iff the period of the induction variable is
- greater than the number of iterations. */
- period = iv_period (cand->iv);
- if (!period)
- return false;
- per_type = TREE_TYPE (period);
-
- wider_type = TREE_TYPE (period);
- if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
- wider_type = per_type;
- else
- wider_type = nit_type;
-
- if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
- fold_convert (wider_type, period),
- fold_convert (wider_type, nit)))))
- return false;
-
- *bound = cand_value_at (loop, cand, use->stmt, nit);
- return true;
-}
-
-/* Determines cost of basing replacement of USE on CAND in a condition. */
-
-static bool
-determine_use_iv_cost_condition (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
-{
- tree bound = NULL_TREE, op, cond;
- bitmap depends_on = NULL;
- unsigned cost;
-
- /* Only consider real candidates. */
- if (!cand->iv)
- {
- set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
- return false;
- }
-
- if (may_eliminate_iv (data, use, cand, &bound))
- {
- cost = force_var_cost (data, bound, &depends_on);
-
- set_use_iv_cost (data, use, cand, cost, depends_on, bound);
- return cost != INFTY;
- }
-
- /* The induction variable elimination failed; just express the original
- giv. If it is compared with an invariant, note that we cannot get
- rid of it. */
- cost = get_computation_cost (data, use, cand, false, &depends_on);
-
- cond = *use->op_p;
- if (TREE_CODE (cond) != SSA_NAME)
- {
- 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);
- }
- }
-
- 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 ivopts_data *data, struct iv_use *use,
- tree *value)
-{
- struct loop *loop = data->current_loop;
- edge exit;
- struct tree_niter_desc *niter;
+ return false;
- exit = single_dom_exit (loop);
- if (!exit)
+ nit = niter_for_exit (data, exit);
+ if (!nit)
return false;
- gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
- bb_for_stmt (use->stmt)));
+ nit_type = TREE_TYPE (nit);
- niter = niter_for_single_dom_exit (data);
- if (!niter
- || !zero_p (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;
- *value = iv_value (use->iv, niter->niter);
+ if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
+ fold_convert (wider_type, period),
+ fold_convert (wider_type, nit))))
+ return false;
+ cand_value_at (loop, cand, use->stmt, nit, &bnd);
+ *bound = aff_combination_to_tree (&bnd);
return true;
}
-/* Determines cost of replacing final value of USE using CAND. */
+/* Determines cost of basing replacement of USE on CAND in a condition. */
static bool
-determine_use_iv_cost_outer (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+determine_use_iv_cost_condition (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand)
{
- bitmap depends_on;
- unsigned cost;
- edge exit;
- 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;
- }
+ tree bound = NULL_TREE;
+ struct iv *cmp_iv;
+ bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
+ unsigned elim_cost, express_cost, cost;
+ bool ok;
+ /* Only consider real candidates. */
if (!cand->iv)
{
- if (!may_replace_final_value (data, use, &value))
- {
- set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
- return false;
- }
+ set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
+ return false;
+ }
- depends_on = NULL;
- cost = force_var_cost (data, value, &depends_on);
+ /* Try iv elimination. */
+ if (may_eliminate_iv (data, use, cand, &bound))
+ elim_cost = force_var_cost (data, bound, &depends_on_elim);
+ else
+ elim_cost = INFTY;
- cost /= AVG_LOOP_NITER (loop);
+ /* Try expressing the original giv. If it is compared with an invariant,
+ note that we cannot get rid of it. */
+ ok = extract_cond_operands (data, use->op_p, NULL, NULL, NULL, &cmp_iv);
+ gcc_assert (ok);
- set_use_iv_cost (data, use, cand, cost, depends_on, value);
- return cost != INFTY;
- }
+ express_cost = get_computation_cost (data, use, cand, false,
+ &depends_on_express);
+ fd_ivopts_data = data;
+ walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
- exit = single_dom_exit (loop);
- if (exit)
+ /* Choose the better approach. */
+ if (elim_cost < express_cost)
{
- /* If there is just a single exit, we may use value of the candidate
- after we take it to determine the value of use. */
- cost = get_computation_cost_at (data, use, cand, false, &depends_on,
- last_stmt (exit->src));
- if (cost != INFTY)
- cost /= AVG_LOOP_NITER (loop);
+ cost = elim_cost;
+ depends_on = depends_on_elim;
+ depends_on_elim = NULL;
}
else
{
- /* Otherwise we just need to compute the iv. */
- cost = get_computation_cost (data, use, cand, false, &depends_on);
+ cost = express_cost;
+ depends_on = depends_on_express;
+ depends_on_express = NULL;
+ bound = NULL_TREE;
}
-
- set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
+
+ set_use_iv_cost (data, use, cand, cost, depends_on, bound);
+
+ if (depends_on_elim)
+ BITMAP_FREE (depends_on_elim);
+ if (depends_on_express)
+ BITMAP_FREE (depends_on_express);
return cost != INFTY;
}
case USE_NONLINEAR_EXPR:
return determine_use_iv_cost_generic (data, use, cand);
- case USE_OUTER:
- return determine_use_iv_cost_outer (data, use, cand);
-
case USE_ADDRESS:
return determine_use_iv_cost_address (data, use, cand);
fprintf (dump_file, " %d\t%d\n", i, cand->cost);
}
-if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n");
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\n");
}
/* Calculates cost for having SIZE induction variables. */
static unsigned
ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
{
- return global_cost_for_size (size,
- loop_data (data->current_loop)->regs_used,
- n_iv_uses (data));
+ /* We add size to the cost, so that we prefer eliminating ivs
+ if possible. */
+ return size + estimate_reg_pressure_cost (size, data->regs_used);
}
/* For each size of the induction variable set determine the penalty. */
{
fprintf (dump_file, "Global costs:\n");
fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
- fprintf (dump_file, " target_small_cost %d\n", target_small_cost);
- fprintf (dump_file, " target_pres_cost %d\n", target_pres_cost);
+ fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost);
fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
}
n++;
}
- loop_data (loop)->regs_used = n;
+ data->regs_used = n;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " regs_used %d\n", n);
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)
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. */
+
+static void
+iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
+{
+ bitmap_iterator bi;
+ unsigned iid;
+
+ if (!invs)
+ return;
- if (deps)
+ 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;
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;
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->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;
}
gimple_add_tmp_var (cand->var_before);
- add_referenced_tmp_var (cand->var_before);
+ add_referenced_var (cand->var_before);
base = unshare_expr (cand->iv->base);
- 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);
}
{
if (TREE_CODE (stmt) == PHI_NODE)
{
- if (!including_defined_name)
- {
- /* Prevent the ssa name defined by the statement from being removed. */
- SET_PHI_RESULT (stmt, NULL);
- }
- remove_phi_node (stmt, NULL_TREE);
+ remove_phi_node (stmt, NULL_TREE, including_defined_name);
}
else
{
block_stmt_iterator bsi = bsi_for_stmt (stmt);
- bsi_remove (&bsi);
+ bsi_remove (&bsi, true);
+ release_defs (stmt);
}
}
{
tree comp;
tree op, stmts, tgt, ass;
- block_stmt_iterator bsi, pbsi;
+ block_stmt_iterator bsi;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
introduce a new computation (that might also need casting the
variable to unsigned and back). */
if (cand->pos == IP_ORIGINAL
- && TREE_CODE (use->stmt) == MODIFY_EXPR
- && TREE_OPERAND (use->stmt, 0) == cand->var_after)
- {
- op = TREE_OPERAND (use->stmt, 1);
-
- /* Be a bit careful. In case variable is expressed in some
- complicated way, rewrite it so that we may get rid of this
- complicated expression. */
- if ((TREE_CODE (op) == PLUS_EXPR
- || TREE_CODE (op) == MINUS_EXPR)
- && TREE_OPERAND (op, 0) == cand->var_before
- && TREE_CODE (TREE_OPERAND (op, 1)) == INTEGER_CST)
+ && cand->incremented_at == use->stmt)
+ {
+ tree step, ctype, utype;
+ enum tree_code incr_code = PLUS_EXPR;
+
+ gcc_assert (TREE_CODE (use->stmt) == GIMPLE_MODIFY_STMT);
+ gcc_assert (GIMPLE_STMT_OPERAND (use->stmt, 0) == cand->var_after);
+
+ step = cand->iv->step;
+ ctype = TREE_TYPE (step);
+ 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 = GIMPLE_STMT_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);
+ gcc_assert (comp != NULL_TREE);
}
- comp = unshare_expr (get_computation (data->current_loop,
- use, cand));
switch (TREE_CODE (use->stmt))
{
case PHI_NODE:
if (name_info (data, tgt)->preserve_biv)
return;
- pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
- while (!bsi_end_p (pbsi)
- && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
- {
- bsi = pbsi;
- bsi_next (&pbsi);
- }
+ bsi = bsi_after_labels (bb_for_stmt (use->stmt));
break;
- case MODIFY_EXPR:
- tgt = TREE_OPERAND (use->stmt, 0);
+ case GIMPLE_MODIFY_STMT:
+ tgt = GIMPLE_STMT_OPERAND (use->stmt, 0);
bsi = bsi_for_stmt (use->stmt);
break;
}
op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
+ if (stmts)
+ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
if (TREE_CODE (use->stmt) == PHI_NODE)
{
- if (stmts)
- bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
- ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
- bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
+ ass = build_gimple_modify_stmt (tgt, op);
+ bsi_insert_before (&bsi, ass, BSI_SAME_STMT);
remove_statement (use->stmt, false);
SSA_NAME_DEF_STMT (tgt) = ass;
}
else
- {
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
- TREE_OPERAND (use->stmt, 1) = op;
- }
+ GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
}
/* Replaces ssa name in index IDX by its basic variable. Callback for
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_name, copy, name;
- tree orig;
+ tree var = get_base_address (ref);
+ tree aref = NULL_TREE, tag, sv;
+ HOST_WIDE_INT offset, size, maxsize;
- var = bvar = get_base_address (*op);
+ 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;
+ }
+
+ 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;
+ /* If the base is a dereference of a pointer, first check its name memory
+ tag. If it does not have one, use its symbol memory 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 = symbol_mem_tag (var);
+ gcc_assert (tag != NULL_TREE);
+ return tag;
}
- else if (DECL_P (var))
- name = NULL_TREE;
- else
- goto do_rewrite;
-
- /* 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
- {
- tree tag = var_ann (var)->type_mem_tag;
- tree new_ptr = create_tmp_var (TREE_TYPE (with), "ruatmp");
- add_referenced_tmp_var (new_ptr);
- if (tag)
- var_ann (new_ptr)->type_mem_tag = tag;
- else
- add_type_alias (new_ptr, var);
- new_name = make_ssa_name (new_ptr, copy);
- }
-
- TREE_OPERAND (copy, 0) = new_name;
- update_stmt (copy);
- bsi_insert_before (bsi, copy, BSI_SAME_STMT);
- with = new_name;
+ {
+ if (!DECL_P (var))
+ return NULL_TREE;
-do_rewrite:
-
- 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);
+ tag = symbol_mem_tag (var);
+ if (tag)
+ return tag;
- *op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
+ return var;
+ }
+}
- /* Record the original reference, for purposes of alias analysis. */
- REF_ORIGINAL (*op) = orig;
+/* Copies the reference information from OLD_REF to NEW_REF. */
- /* Virtual operands in the original statement may have to be renamed
- because of the replacement. */
- mark_new_vars_to_rename (bsi_stmt (*bsi));
+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));
+ aff_tree aff;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
- tree stmts;
- tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
+ tree ref;
+ bool ok;
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+ gcc_assert (ok);
+ 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
rewrite_use_compare (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
- tree comp;
- tree *op_p, cond, op, stmts, bound;
+ tree comp, *var_p, op, bound;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
enum tree_code compare;
struct cost_pair *cp = get_use_iv_cost (data, use, cand);
-
+ bool ok;
+
bound = cp->value;
if (bound)
{
tree var_type = TREE_TYPE (var);
compare = iv_elimination_compare (data, use);
- bound = fold_convert (var_type, bound);
- op = force_gimple_operand (unshare_expr (bound), &stmts,
- true, NULL_TREE);
-
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ bound = unshare_expr (fold_convert (var_type, bound));
+ op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE);
*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));
-
- cond = *use->op_p;
- op_p = &TREE_OPERAND (cond, 0);
- if (TREE_CODE (*op_p) != SSA_NAME
- || zero_p (get_iv (data, *op_p)->step))
- op_p = &TREE_OPERAND (cond, 1);
-
- op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
-
- *op_p = op;
-}
-
-/* Ensure that operand *OP_P may be used at the end of EXIT without
- violating loop closed ssa form. */
-
-static void
-protect_loop_closed_ssa_form_use (edge exit, use_operand_p op_p)
-{
- basic_block def_bb;
- struct loop *def_loop;
- tree phi, use;
-
- use = USE_FROM_PTR (op_p);
- if (TREE_CODE (use) != SSA_NAME)
- return;
-
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
- if (!def_bb)
- return;
-
- def_loop = def_bb->loop_father;
- if (flow_bb_inside_loop_p (def_loop, exit->dest))
- return;
-
- /* Try finding a phi node that copies the value out of the loop. */
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
- if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == use)
- break;
-
- if (!phi)
- {
- /* Create such a phi node. */
- tree new_name = duplicate_ssa_name (use, NULL);
-
- phi = create_phi_node (new_name, exit->dest);
- SSA_NAME_DEF_STMT (new_name) = phi;
- add_phi_arg (phi, use, exit);
- }
-
- SET_USE (op_p, PHI_RESULT (phi));
-}
-
-/* Ensure that operands of STMT may be used at the end of EXIT without
- violating loop closed ssa form. */
-
-static void
-protect_loop_closed_ssa_form (edge exit, tree stmt)
-{
- use_optype uses;
- vuse_optype vuses;
- v_may_def_optype v_may_defs;
- unsigned i;
-
- 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));
-}
-
-/* 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
-compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
-{
- tree_stmt_iterator tsi;
- block_stmt_iterator bsi;
- tree phi, stmt, def, next;
-
- if (!single_pred_p (exit->dest))
- split_loop_exit_edge (exit);
-
- /* Ensure there is label in exit->dest, so that we can
- insert after it. */
- tree_block_label (exit->dest);
- bsi = bsi_after_labels (exit->dest);
-
- if (TREE_CODE (stmts) == STATEMENT_LIST)
- {
- for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
- {
- bsi_insert_after (&bsi, tsi_stmt (tsi), BSI_NEW_STMT);
- protect_loop_closed_ssa_form (exit, bsi_stmt (bsi));
- }
- }
- else
- {
- bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
- protect_loop_closed_ssa_form (exit, bsi_stmt (bsi));
- }
-
- if (!op)
- return;
-
- for (phi = phi_nodes (exit->dest); phi; phi = next)
- {
- next = PHI_CHAIN (phi);
-
- if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == op)
- {
- def = PHI_RESULT (phi);
- remove_statement (phi, false);
- stmt = build2 (MODIFY_EXPR, TREE_TYPE (op),
- def, op);
- SSA_NAME_DEF_STMT (def) = stmt;
- bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
- }
- }
-}
-
-/* Rewrites the final value of USE (that is only needed outside of the loop)
- using candidate CAND. */
-
-static void
-rewrite_use_outer (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
-{
- edge exit;
- tree value, op, stmts, tgt;
- tree phi;
-
- switch (TREE_CODE (use->stmt))
- {
- case PHI_NODE:
- tgt = PHI_RESULT (use->stmt);
- break;
- case MODIFY_EXPR:
- tgt = TREE_OPERAND (use->stmt, 0);
- break;
- default:
- gcc_unreachable ();
- }
-
- exit = single_dom_exit (data->current_loop);
-
- if (exit)
- {
- if (!cand->iv)
- {
- struct cost_pair *cp = get_use_iv_cost (data, use, cand);
- value = 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
- some computation to replace the final value, do nothing. */
- if (stmts && name_info (data, tgt)->preserve_biv)
- return;
-
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
- {
- use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
-
- if (USE_FROM_PTR (use_p) == tgt)
- SET_USE (use_p, op);
- }
-
- if (stmts)
- compute_phi_arg_on_exit (exit, stmts, op);
+ comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
- /* Enable removal of the statement. We cannot remove it directly,
- since we may still need the aliasing information attached to the
- ssa name defined by it. */
- name_info (data, tgt)->iv->have_use_for = false;
- return;
- }
-
- /* If the variable is going to be preserved anyway, there is nothing to
- do. */
- if (name_info (data, tgt)->preserve_biv)
- return;
+ ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
+ gcc_assert (ok);
- /* Otherwise we just need to compute the iv. */
- rewrite_use_nonlinear_expr (data, use, cand);
+ *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p));
}
/* Rewrites USE using candidate CAND. */
static void
-rewrite_use (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
{
+ push_stmt_changes (&use->stmt);
+
switch (use->type)
{
case USE_NONLINEAR_EXPR:
rewrite_use_nonlinear_expr (data, use, cand);
break;
- case USE_OUTER:
- rewrite_use_outer (data, use, cand);
- break;
-
case USE_ADDRESS:
rewrite_use_address (data, use, cand);
break;
default:
gcc_unreachable ();
}
- update_stmt (use->stmt);
+
+ pop_stmt_changes (&use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
info = ver_info (data, j);
if (info->iv
- && !zero_p (info->iv->step)
+ && !integer_zerop (info->iv->step)
&& !info->inv_id
&& !info->iv->have_use_for
&& !info->preserve_biv)
bitmap_iterator bi;
tree obj;
- htab_empty (data->niters);
+ if (data->niters)
+ {
+ pointer_map_destroy (data->niters);
+ data->niters = NULL;
+ }
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
if (cand->iv)
free (cand->iv);
+ if (cand->depends_on)
+ BITMAP_FREE (cand->depends_on);
free (cand);
}
VEC_truncate (iv_cand_p, data->iv_candidates, 0);
{
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;
loop tree. */
static void
-tree_ssa_iv_optimize_finalize (struct loops *loops, struct ivopts_data *data)
+tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
{
- unsigned i;
-
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- {
- free (loops->parray[i]->aux);
- loops->parray[i]->aux = NULL;
- }
-
free_loop_data (data);
free (data->version_info);
BITMAP_FREE (data->relevant);
BITMAP_FREE (data->important_candidates);
- htab_delete (data->niters);
VEC_free (tree, heap, decl_rtl_to_reset);
VEC_free (iv_use_p, heap, data->iv_uses);
struct iv_ca *iv_ca;
edge exit;
+ gcc_assert (!data->niters);
data->current_loop = loop;
if (dump_file && (dump_flags & TDF_DETAILS))
return changed;
}
-/* Main entry point. Optimizes induction variables in LOOPS. */
+/* Main entry point. Optimizes induction variables in loops. */
void
-tree_ssa_iv_optimize (struct loops *loops)
+tree_ssa_iv_optimize (void)
{
struct loop *loop;
struct ivopts_data data;
+ loop_iterator li;
- tree_ssa_iv_optimize_init (loops, &data);
+ tree_ssa_iv_optimize_init (&data);
/* Optimize the loops starting with the innermost ones. */
- loop = loops->tree_root;
- while (loop->inner)
- loop = loop->inner;
-
- /* Scan the loops, inner ones first. */
- while (loop != loops->tree_root)
+ FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
if (dump_file && (dump_flags & TDF_DETAILS))
flow_loop_dump (loop, dump_file, NULL, 1);
tree_ssa_iv_optimize_loop (&data, loop);
-
- if (loop->next)
- {
- loop = loop->next;
- while (loop->inner)
- loop = loop->inner;
- }
- else
- loop = loop->outer;
- }
-
- /* FIXME. IV opts introduces new aliases and call-clobbered
- variables, which need to be renamed. However, when we call the
- renamer, not all statements will be scanned for operands. In
- particular, the newly introduced aliases may appear in statements
- that are considered "unmodified", so the renamer will not get a
- chance to rename those operands.
-
- Work around this problem by forcing an operand re-scan on every
- statement. This will not be necessary once the new operand
- scanner is implemented. */
- if (need_ssa_update_p ())
- {
- basic_block bb;
- block_stmt_iterator si;
- FOR_EACH_BB (bb)
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- update_stmt (bsi_stmt (si));
}
- rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
- tree_ssa_iv_optimize_finalize (loops, &data);
+ tree_ssa_iv_optimize_finalize (&data);
}
OSDN Git Service
