/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
-
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
+ Free Software Foundation, Inc.
+
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
+Free Software Foundation; either version 3, or (at your option) any
later version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This pass tries to find the optimal set of induction variables for the loop.
It optimizes just the basic linear induction variables (although adding
4) The trees are transformed to use the new variables, the dead code is
removed.
-
+
All of this is done loop by loop. Doing it globally is theoretically
possible, it might give a better performance and it might enable us
to decide costs more precisely, but getting all the interactions right
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
-#include "varray.h"
-#include "expr.h"
#include "tree-pass.h"
#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"
+#include "tree-inline.h"
+#include "tree-ssa-propagate.h"
+
+/* FIXME: add_cost and zero_cost defined in exprmed.h conflict with local uses.
+ */
+#include "expmed.h"
+#undef add_cost
+#undef zero_cost
+
+/* FIXME: Expressions are expanded to RTL in this pass to determine the
+ cost of different addressing modes. This should be moved to a TBD
+ interface between the GIMPLE and RTL worlds. */
+#include "expr.h"
/* The infinite cost. */
#define INFTY 10000000
-/* The expected number of loop iterations. TODO -- use profiling instead of
- this. */
#define AVG_LOOP_NITER(LOOP) 5
+/* Returns the expected number of loop iterations for LOOP.
+ The average trip count is computed from profile data if it
+ exists. */
+
+static inline HOST_WIDE_INT
+avg_loop_niter (struct loop *loop)
+{
+ HOST_WIDE_INT niter = max_stmt_executions_int (loop, false);
+ if (niter == -1)
+ return AVG_LOOP_NITER (loop);
+
+ return niter;
+}
/* Representation of the induction variable. */
struct iv
struct iv *iv; /* Induction variable description. */
bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
an expression that is not an induction variable. */
- unsigned inv_id; /* Id of an invariant. */
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. */
+ unsigned inv_id; /* Id of an invariant. */
};
/* 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. */
};
+/* Cost of a computation. */
+typedef struct
+{
+ int cost; /* The runtime cost. */
+ unsigned complexity; /* The estimate of the complexity of the code for
+ the computation (in no concrete units --
+ complexity field should be larger for more
+ complex expressions and addressing modes). */
+} comp_cost;
+
+static const comp_cost zero_cost = {0, 0};
+static const comp_cost infinite_cost = {INFTY, INFTY};
+
/* The candidate - cost pair. */
struct cost_pair
{
struct iv_cand *cand; /* The candidate. */
- unsigned cost; /* The cost. */
+ comp_cost cost; /* The cost. */
bitmap depends_on; /* The list of invariants that have to be
preserved. */
+ tree value; /* For final value elimination, the expression for
+ the final value of the iv. For iv elimination,
+ the new bound to compare with. */
+ enum tree_code comp; /* For iv elimination, the comparison. */
+ int inv_expr_id; /* Loop invariant expression id. */
};
/* Use. */
unsigned id; /* The id of the use. */
enum use_type type; /* Type of the use. */
struct iv *iv; /* The induction variable it is based on. */
- tree stmt; /* Statement in that it occurs. */
+ gimple stmt; /* Statement in that it occurs. */
tree *op_p; /* The place where it occurs. */
bitmap related_cands; /* The set of "related" iv candidates, plus the common
important ones. */
{
IP_NORMAL, /* At the end, just before the exit condition. */
IP_END, /* At the end of the latch block. */
+ IP_BEFORE_USE, /* Immediately before a specific use. */
+ IP_AFTER_USE, /* Immediately after a specific use. */
IP_ORIGINAL /* The original biv. */
};
unsigned id; /* The number of the candidate. */
bool important; /* Whether this is an "important" candidate, i.e. such
that it should be considered by all uses. */
- enum iv_position pos; /* Where it is computed. */
- tree incremented_at; /* For original biv, the statement where it is
+ ENUM_BITFIELD(iv_position) pos : 8; /* Where it is computed. */
+ gimple incremented_at;/* For original biv, the statement where it is
incremented. */
tree var_before; /* The variable used for it before increment. */
tree var_after; /* The variable used for it after increment. */
to replace the final value of an iv by direct
computation of the value. */
unsigned cost; /* Cost of the candidate. */
+ unsigned cost_step; /* Cost of the candidate's increment operation. */
+ struct iv_use *ainc_use; /* For IP_{BEFORE,AFTER}_USE candidates, the place
+ where it is incremented. */
+ bitmap depends_on; /* The list of invariants that are used in step of the
+ biv. */
+};
+
+/* Loop invariant expression hashtable entry. */
+struct iv_inv_expr_ent
+{
+ tree expr;
+ int id;
+ hashval_t hash;
};
/* The data used by the induction variable optimizations. */
+typedef struct iv_use *iv_use_p;
+DEF_VEC_P(iv_use_p);
+DEF_VEC_ALLOC_P(iv_use_p,heap);
+
+typedef struct iv_cand *iv_cand_p;
+DEF_VEC_P(iv_cand_p);
+DEF_VEC_ALLOC_P(iv_cand_p,heap);
+
struct ivopts_data
{
/* The currently optimized loop. */
struct loop *current_loop;
/* Numbers of iterations for all exits of the current loop. */
- htab_t niters;
+ struct pointer_map_t *niters;
+
+ /* Number of registers used in it. */
+ unsigned regs_used;
/* The size of version_info array allocated. */
unsigned version_info_size;
/* The array of information for the ssa names. */
struct version_info *version_info;
+ /* The hashtable of loop invariant expressions created
+ by ivopt. */
+ htab_t inv_expr_tab;
+
+ /* Loop invariant expression id. */
+ int inv_expr_id;
+
/* The bitmap of indices in version_info whose value was changed. */
bitmap relevant;
- /* The maximum invariant id. */
- unsigned max_inv_id;
-
/* The uses of induction variables. */
- varray_type iv_uses;
+ VEC(iv_use_p,heap) *iv_uses;
/* The candidates. */
- varray_type iv_candidates;
+ VEC(iv_cand_p,heap) *iv_candidates;
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* The maximum invariant id. */
+ unsigned max_inv_id;
+
/* Whether to consider just related and important candidates when replacing a
use. */
bool consider_all_candidates;
+
+ /* Are we optimizing for speed? */
+ bool speed;
+
+ /* Whether the loop body includes any function calls. */
+ bool body_includes_call;
+
+ /* Whether the loop body can only be exited via single exit. */
+ bool loop_single_exit_p;
};
/* An assignment of iv candidates to uses. */
unsigned n_regs;
/* Total cost of expressing uses. */
- unsigned cand_use_cost;
+ comp_cost cand_use_cost;
/* Total cost of candidates. */
unsigned cand_cost;
/* Number of times each invariant is used. */
unsigned *n_invariant_uses;
+ /* The array holding the number of uses of each loop
+ invariant expressions created by ivopt. */
+ unsigned *used_inv_expr;
+
+ /* The number of created loop invariants. */
+ unsigned num_used_inv_expr;
+
/* Total cost of the assignment. */
- unsigned cost;
+ comp_cost cost;
};
/* Difference of two iv candidate assignments. */
/* The list of trees for that the decl_rtl field must be reset is stored
here. */
-static varray_type decl_rtl_to_reset;
+static VEC(tree,heap) *decl_rtl_to_reset;
+
+static comp_cost force_expr_to_var_cost (tree, bool);
/* Number of uses recorded in DATA. */
static inline unsigned
n_iv_uses (struct ivopts_data *data)
{
- return VARRAY_ACTIVE_SIZE (data->iv_uses);
+ return VEC_length (iv_use_p, data->iv_uses);
}
/* Ith use recorded in DATA. */
static inline struct iv_use *
iv_use (struct ivopts_data *data, unsigned i)
{
- return VARRAY_GENERIC_PTR_NOGC (data->iv_uses, i);
+ return VEC_index (iv_use_p, data->iv_uses, i);
}
/* Number of candidates recorded in DATA. */
static inline unsigned
n_iv_cands (struct ivopts_data *data)
{
- return VARRAY_ACTIVE_SIZE (data->iv_candidates);
+ return VEC_length (iv_cand_p, data->iv_candidates);
}
/* Ith candidate recorded in DATA. */
static inline struct iv_cand *
iv_cand (struct ivopts_data *data, unsigned i)
{
- return VARRAY_GENERIC_PTR_NOGC (data->iv_candidates, i);
-}
-
-/* The data for LOOP. */
-
-static inline struct loop_data *
-loop_data (struct loop *loop)
-{
- return loop->aux;
+ return VEC_index (iv_cand_p, data->iv_candidates, i);
}
/* 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, " in statement ");
- print_generic_expr (file, use->stmt, TDF_SLIM);
+ print_gimple_stmt (file, use->stmt, 0, 0);
fprintf (file, "\n");
fprintf (file, " at position ");
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;
}
+ if (cand->var_before)
+ {
+ fprintf (file, " var_before ");
+ print_generic_expr (file, cand->var_before, TDF_SLIM);
+ fprintf (file, "\n");
+ }
+ if (cand->var_after)
+ {
+ fprintf (file, " var_after ");
+ print_generic_expr (file, cand->var_after, TDF_SLIM);
+ fprintf (file, "\n");
+ }
+
switch (cand->pos)
{
case IP_NORMAL:
fprintf (file, " incremented before exit test\n");
break;
+ case IP_BEFORE_USE:
+ fprintf (file, " incremented before use %d\n", cand->ainc_use->id);
+ break;
+
+ case IP_AFTER_USE:
+ fprintf (file, " incremented after use %d\n", cand->ainc_use->id);
+ break;
+
case IP_END:
fprintf (file, " incremented at end\n");
break;
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. */
static bool
-stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
+stmt_after_ip_normal_pos (struct loop *loop, gimple stmt)
{
- basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
+ basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);
gcc_assert (bb);
}
/* Returns true if STMT if after the place where the original induction
- variable CAND is incremented. */
+ variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
+ if the positions are identical. */
static bool
-stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
+stmt_after_inc_pos (struct iv_cand *cand, gimple stmt, bool true_if_equal)
{
- basic_block cand_bb = bb_for_stmt (cand->incremented_at);
- basic_block stmt_bb = bb_for_stmt (stmt);
- block_stmt_iterator bsi;
+ basic_block cand_bb = gimple_bb (cand->incremented_at);
+ basic_block stmt_bb = gimple_bb (stmt);
if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
return false;
if (stmt_bb != cand_bb)
return true;
- /* Scan the block from the end, since the original ivs are usually
- incremented at the end of the loop body. */
- for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
- {
- if (bsi_stmt (bsi) == cand->incremented_at)
- return false;
- if (bsi_stmt (bsi) == stmt)
- return true;
- }
+ if (true_if_equal
+ && gimple_uid (stmt) == gimple_uid (cand->incremented_at))
+ return true;
+ return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
}
/* Returns true if STMT if after the place where the induction variable
CAND is incremented in LOOP. */
static bool
-stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
+stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple stmt)
{
switch (cand->pos)
{
return stmt_after_ip_normal_pos (loop, stmt);
case IP_ORIGINAL:
- return stmt_after_ip_original_pos (cand, stmt);
+ case IP_AFTER_USE:
+ return stmt_after_inc_pos (cand, stmt, false);
+
+ case IP_BEFORE_USE:
+ return stmt_after_inc_pos (cand, stmt, true);
default:
gcc_unreachable ();
}
}
-/* 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 || TREE_CODE (base) == ARRAY_RANGE_REF)
+ {
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
+ return false;
+ if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
+ return false;
+ }
- 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);
+
+ if (code == COND_EXPR)
+ return contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0))
+ || contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1))
+ || contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 2));
+
+ switch (codeclass)
+ {
+ case tcc_binary:
+ case tcc_comparison:
+ if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
+ return true;
+
+ /* Fallthru. */
+ case tcc_unary:
+ if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
+ return true;
+
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
- return elt1->exit == e2;
+ return false;
}
-/* Returns structure describing number of iterations determined from
+/* Returns the structure describing number of iterations determined from
EXIT of DATA->current_loop, or NULL if something goes wrong. */
static struct tree_niter_desc *
niter_for_exit (struct ivopts_data *data, edge exit)
{
- struct nfe_cache_elt *nfe_desc;
- PTR *slot;
+ struct tree_niter_desc *desc;
+ 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 (!nfe_desc->valid_p)
- return NULL;
+ if (!slot)
+ {
+ /* Try to determine number of iterations. We cannot safely work with ssa
+ names that appear in phi nodes on abnormal edges, so that we do not
+ create overlapping life ranges for them (PR 27283). */
+ desc = XNEW (struct tree_niter_desc);
+ if (!number_of_iterations_exit (data->current_loop,
+ exit, desc, true)
+ || contains_abnormal_ssa_name_p (desc->niter))
+ {
+ XDELETE (desc);
+ desc = NULL;
+ }
+ slot = pointer_map_insert (data->niters, exit);
+ *slot = desc;
+ }
+ else
+ desc = (struct tree_niter_desc *) *slot;
- return &nfe_desc->niter;
+ return desc;
}
-/* Returns structure describing number of iterations determined from
+/* Returns the structure describing number of iterations determined from
single dominating exit of DATA->current_loop, or NULL if something
goes wrong. */
return niter_for_exit (data, exit);
}
+/* Hash table equality function for expressions. */
+
+static int
+htab_inv_expr_eq (const void *ent1, const void *ent2)
+{
+ const struct iv_inv_expr_ent *expr1 =
+ (const struct iv_inv_expr_ent *)ent1;
+ const struct iv_inv_expr_ent *expr2 =
+ (const struct iv_inv_expr_ent *)ent2;
+
+ return expr1->hash == expr2->hash
+ && operand_equal_p (expr1->expr, expr2->expr, 0);
+}
+
+/* Hash function for loop invariant expressions. */
+
+static hashval_t
+htab_inv_expr_hash (const void *ent)
+{
+ const struct iv_inv_expr_ent *expr =
+ (const struct iv_inv_expr_ent *)ent;
+ return expr->hash;
+}
+
/* 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));
-
- VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_uses, 20, "iv_uses");
- VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_candidates, 20, "iv_candidates");
- VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
+ data->niters = NULL;
+ data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
+ data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
+ data->inv_expr_tab = htab_create (10, htab_inv_expr_hash,
+ htab_inv_expr_eq, free);
+ data->inv_expr_id = 0;
+ decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
}
/* Returns a memory object to that EXPR points. In case we are able to
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 (CONVERT_EXPR_P (expr))
+ return determine_base_object (TREE_OPERAND (expr, 0));
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
return NULL_TREE;
if (!base)
return expr;
- if (TREE_CODE (base) == INDIRECT_REF)
+ if (TREE_CODE (base) == MEM_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));
+ bb = gimple_bb (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)
+determine_biv_step (gimple phi)
{
- struct loop *loop = bb_for_stmt (phi)->loop_father;
- tree name = PHI_RESULT (phi), base, step;
- tree type = TREE_TYPE (name);
+ struct loop *loop = gimple_bb (phi)->loop_father;
+ 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, loop, name, &iv, true))
return NULL_TREE;
- if (!step)
- return build_int_cst (type, 0);
-
- return step;
+ return integer_zerop (iv.step) ? NULL_TREE : iv.step;
}
-/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
+/* Finds basic ivs. */
static bool
-abnormal_ssa_name_p (tree exp)
+find_bivs (struct ivopts_data *data)
{
- if (!exp)
- return false;
+ gimple phi;
+ tree step, type, base;
+ bool found = false;
+ struct loop *loop = data->current_loop;
+ gimple_stmt_iterator psi;
- if (TREE_CODE (exp) != SSA_NAME)
- return false;
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = gsi_stmt (psi);
- return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
-}
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
+ continue;
-/* Returns false if BASE or INDEX contains a ssa name that occurs in an
- abnormal phi node. Callback for for_each_index. */
+ step = determine_biv_step (phi);
+ if (!step)
+ continue;
-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;
+ base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+ 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);
+ if (step)
+ {
+ if (POINTER_TYPE_P (type))
+ step = convert_to_ptrofftype (step);
+ else
+ step = fold_convert (type, step);
+ }
+
+ set_iv (data, PHI_RESULT (phi), base, step);
+ found = true;
}
- return !abnormal_ssa_name_p (*index);
+ return found;
}
-/* Returns true if EXPR contains a ssa name that occurs in an
- abnormal phi node. */
+/* Marks basic ivs. */
-static bool
-contains_abnormal_ssa_name_p (tree expr)
+static void
+mark_bivs (struct ivopts_data *data)
{
- 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;
+ gimple phi;
+ tree var;
+ struct iv *iv, *incr_iv;
+ struct loop *loop = data->current_loop;
+ basic_block incr_bb;
+ gimple_stmt_iterator psi;
- if (code == INTEGER_CST
- || is_gimple_min_invariant (expr))
- return false;
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = gsi_stmt (psi);
- 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;
-}
-
-/* Finds basic ivs. */
-
-static bool
-find_bivs (struct ivopts_data *data)
-{
- tree phi, step, type, base;
- bool found = false;
- struct loop *loop = data->current_loop;
-
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
- {
- if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
- 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))
- 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;
-
- set_iv (data, PHI_RESULT (phi), base, step);
- found = true;
- }
-
- return found;
-}
-
-/* Marks basic ivs. */
-
-static void
-mark_bivs (struct ivopts_data *data)
-{
- tree phi, var;
- struct iv *iv, *incr_iv;
- struct loop *loop = data->current_loop;
- basic_block incr_bb;
-
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
- {
- iv = get_iv (data, PHI_RESULT (phi));
- if (!iv)
- continue;
+ iv = get_iv (data, PHI_RESULT (phi));
+ if (!iv)
+ continue;
var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
incr_iv = get_iv (data, var);
continue;
/* If the increment is in the subloop, ignore it. */
- incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ incr_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
if (incr_bb->loop_father != data->current_loop
|| (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
continue;
}
/* 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, gimple 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 (gimple_code (stmt) != GIMPLE_ASSIGN)
return false;
- lhs = TREE_OPERAND (stmt, 0);
+ lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, 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))
+ if (contains_abnormal_ssa_name_p (iv->base)
+ || contains_abnormal_ssa_name_p (iv->step))
return false;
- if (contains_abnormal_ssa_name_p (*base))
+ /* If STMT could throw, then do not consider STMT as defining a GIV.
+ While this will suppress optimizations, we can not safely delete this
+ GIV and associated statements, even if it appears it is not used. */
+ if (stmt_could_throw_p (stmt))
return false;
return true;
/* Finds general ivs in statement STMT. */
static void
-find_givs_in_stmt (struct ivopts_data *data, tree stmt)
+find_givs_in_stmt (struct ivopts_data *data, gimple 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_assign_lhs (stmt), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
static void
find_givs_in_bb (struct ivopts_data *data, basic_block bb)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_givs_in_stmt (data, bsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_givs_in_stmt (data, gsi_stmt (bsi));
}
/* Finds general ivs. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
- struct tree_niter_desc *niter;
-
- niter = niter_for_single_dom_exit (data);
+ struct tree_niter_desc *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");
+ if (!integer_zerop (niter->may_be_zero))
+ {
+ fprintf (dump_file, "; zero if ");
+ print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
+ }
+ fprintf (dump_file, "\n\n");
};
-
+
fprintf (dump_file, "Induction variables:\n\n");
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
static struct iv_use *
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
- tree stmt, enum use_type use_type)
+ gimple 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;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
- VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_uses, use);
+ VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
return use;
}
|| !is_gimple_reg (op))
return;
- bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
+ bb = gimple_bb (SSA_NAME_DEF_STMT (op));
if (bb
&& flow_bb_inside_loop_p (data->current_loop, bb))
return;
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;
- tree stmt;
+ gimple stmt;
struct iv_use *use;
if (TREE_CODE (op) != SSA_NAME)
iv = get_iv (data, op);
if (!iv)
return NULL;
-
+
if (iv->have_use_for)
{
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);
+ gcc_assert (gimple_code (stmt) == GIMPLE_PHI
+ || is_gimple_assign (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 in statement STMT, checks whether it is a compare
+ of an induction variable and an invariant. If this is the case,
+ CONTROL_VAR is set to location of the iv, BOUND to the location of
+ the 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, gimple stmt,
+ tree **control_var, tree **bound,
+ struct iv **iv_var, struct iv **iv_bound)
{
- tree *op0_p;
- tree *op1_p;
- struct iv *iv0 = NULL, *iv1 = NULL, *civ;
- struct iv const_iv;
- tree zero = integer_zero_node;
+ /* The objects returned when COND has constant operands. */
+ static struct iv const_iv;
+ static tree zero;
+ tree *op0 = &zero, *op1 = &zero, *tmp_op;
+ struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+ bool ret = false;
- const_iv.step = NULL_TREE;
-
- if (integer_zerop (*cond_p)
- || integer_nonzerop (*cond_p))
- return;
-
- if (TREE_CODE (*cond_p) == SSA_NAME)
+ if (gimple_code (stmt) == GIMPLE_COND)
{
- op0_p = cond_p;
- op1_p = &zero;
+ op0 = gimple_cond_lhs_ptr (stmt);
+ op1 = gimple_cond_rhs_ptr (stmt);
}
else
{
- op0_p = &TREE_OPERAND (*cond_p, 0);
- op1_p = &TREE_OPERAND (*cond_p, 1);
+ op0 = gimple_assign_rhs1_ptr (stmt);
+ op1 = gimple_assign_rhs2_ptr (stmt);
}
- if (TREE_CODE (*op0_p) == SSA_NAME)
- iv0 = get_iv (data, *op0_p);
- else
- iv0 = &const_iv;
+ zero = integer_zero_node;
+ const_iv.step = integer_zero_node;
- if (TREE_CODE (*op1_p) == SSA_NAME)
- iv1 = get_iv (data, *op1_p);
- else
- iv1 = &const_iv;
+ if (TREE_CODE (*op0) == SSA_NAME)
+ iv0 = get_iv (data, *op0);
+ if (TREE_CODE (*op1) == SSA_NAME)
+ iv1 = get_iv (data, *op1);
+
+ /* Exactly one of the compared values must be an iv, and the other one must
+ be an invariant. */
+ if (!iv0 || !iv1)
+ 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;
+}
+
+/* Checks whether the condition in STMT is interesting and if so,
+ records it. */
+
+static void
+find_interesting_uses_cond (struct ivopts_data *data, gimple stmt)
+{
+ tree *var_p, *bound_p;
+ struct iv *var_iv, *civ;
- if (zero_p (iv0->step) && zero_p (iv1->step))
+ if (!extract_cond_operands (data, stmt, &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;
- record_use (data, cond_p, civ, stmt, USE_COMPARE);
+ civ = XNEW (struct iv);
+ *civ = *var_iv;
+ record_use (data, NULL, civ, stmt, USE_COMPARE);
}
/* Returns true if expression EXPR is obviously invariant in LOOP,
- i.e. if all its operands are defined outside of the LOOP. */
+ i.e. if all its operands are defined outside of the LOOP. LOOP
+ should not be the function body. */
bool
expr_invariant_in_loop_p (struct loop *loop, tree expr)
basic_block def_bb;
unsigned i, len;
+ gcc_assert (loop_depth (loop) > 0);
+
if (is_gimple_min_invariant (expr))
return true;
if (TREE_CODE (expr) == SSA_NAME)
{
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return false;
if (!EXPR_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;
return true;
}
+/* Returns true if statement STMT is obviously invariant in LOOP,
+ i.e. if all its operands on the RHS are defined outside of the LOOP.
+ LOOP should not be the function body. */
+
+bool
+stmt_invariant_in_loop_p (struct loop *loop, gimple stmt)
+{
+ unsigned i;
+ tree lhs;
+
+ gcc_assert (loop_depth (loop) > 0);
+
+ lhs = gimple_get_lhs (stmt);
+ for (i = 0; i < gimple_num_ops (stmt); i++)
+ {
+ tree op = gimple_op (stmt, i);
+ if (op != lhs && !expr_invariant_in_loop_p (loop, op))
+ return false;
+ }
+
+ return true;
+}
+
/* Cumulates the steps of indices into DATA and replaces their values with the
initial ones. Returns false when the value of the index cannot be determined.
Callback for for_each_index. */
struct ifs_ivopts_data
{
struct ivopts_data *ivopts_data;
- tree stmt;
- tree *step_p;
+ gimple stmt;
+ 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
- || TREE_CODE (base) == ALIGN_INDIRECT_REF)
- return false;
-
/* If base is a component ref, require that the offset of the reference
be invariant. */
if (TREE_CODE (base) == COMPONENT_REF)
reference out of the loop (in order to take its address in strength
reduction). In order for this to work we need both lower bound
and step to be loop invariants. */
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
+ /* Moreover, for a range, the size needs to be invariant as well. */
+ if (TREE_CODE (base) == ARRAY_RANGE_REF
+ && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))))
+ return false;
+
step = array_ref_element_size (base);
lbound = array_ref_low_bound (base);
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)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_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 = size_one_node;
- 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)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
find_interesting_uses_op (data, array_ref_element_size (base));
find_interesting_uses_op (data, array_ref_low_bound (base));
return true;
}
-/* Returns true if memory reference REF may be unaligned. */
+/* If we can prove that TOP = cst * BOT for some constant cst,
+ store cst to MUL and return true. Otherwise return false.
+ The returned value is always sign-extended, regardless of the
+ signedness of TOP and BOT. */
+
+static bool
+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))
+ {
+ *mul = double_int_one;
+ return true;
+ }
+
+ code = TREE_CODE (top);
+ switch (code)
+ {
+ case MULT_EXPR:
+ mby = TREE_OPERAND (top, 1);
+ if (TREE_CODE (mby) != INTEGER_CST)
+ return false;
+
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
+ return false;
+
+ *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
+ precision);
+ return true;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
+ || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
+ return false;
+
+ if (code == MINUS_EXPR)
+ p1 = double_int_neg (p1);
+ *mul = double_int_sext (double_int_add (p0, p1), precision);
+ return true;
+
+ case INTEGER_CST:
+ if (TREE_CODE (bot) != INTEGER_CST)
+ return false;
+
+ p0 = double_int_sext (tree_to_double_int (top), precision);
+ p1 = double_int_sext (tree_to_double_int (bot), precision);
+ if (double_int_zero_p (p1))
+ return false;
+ *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
+ precision);
+ return double_int_zero_p (res);
+
+ default:
+ return false;
+ }
+}
+
+/* Returns true if memory reference REF with step STEP may be unaligned. */
static bool
-may_be_unaligned_p (tree ref)
+may_be_unaligned_p (tree ref, tree step)
{
tree base;
tree base_type;
int unsignedp, volatilep;
unsigned base_align;
+ /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
+ thus they are not misaligned. */
+ if (TREE_CODE (ref) == TARGET_MEM_REF)
+ return false;
+
/* The test below is basically copy of what expr.c:normal_inner_ref
does to check whether the object must be loaded by parts when
STRICT_ALIGNMENT is true. */
base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
&unsignedp, &volatilep, true);
base_type = TREE_TYPE (base);
- base_align = TYPE_ALIGN (base_type);
+ base_align = get_object_alignment (base);
+ base_align = MAX (base_align, TYPE_ALIGN (base_type));
- if (mode != BLKmode
- && (base_align < GET_MODE_ALIGNMENT (mode)
- || bitpos % GET_MODE_ALIGNMENT (mode) != 0
- || bitpos % BITS_PER_UNIT != 0))
- return true;
+ if (mode != BLKmode)
+ {
+ unsigned mode_align = GET_MODE_ALIGNMENT (mode);
+
+ if (base_align < mode_align
+ || (bitpos % mode_align) != 0
+ || (bitpos % BITS_PER_UNIT) != 0)
+ return true;
+
+ if (toffset
+ && (highest_pow2_factor (toffset) * BITS_PER_UNIT) < mode_align)
+ return true;
+
+ if ((highest_pow2_factor (step) * BITS_PER_UNIT) < mode_align)
+ return true;
+ }
+
+ return false;
+}
+
+/* Return true if EXPR may be non-addressable. */
+
+bool
+may_be_nonaddressable_p (tree expr)
+{
+ switch (TREE_CODE (expr))
+ {
+ case TARGET_MEM_REF:
+ /* TARGET_MEM_REFs are translated directly to valid MEMs on the
+ target, thus they are always addressable. */
+ return false;
+
+ case COMPONENT_REF:
+ return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
+ || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ case VIEW_CONVERT_EXPR:
+ /* This kind of view-conversions may wrap non-addressable objects
+ and make them look addressable. After some processing the
+ non-addressability may be uncovered again, causing ADDR_EXPRs
+ of inappropriate objects to be built. */
+ if (is_gimple_reg (TREE_OPERAND (expr, 0))
+ || !is_gimple_addressable (TREE_OPERAND (expr, 0)))
+ return true;
+
+ /* ... fall through ... */
+
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ CASE_CONVERT:
+ return true;
+
+ default:
+ break;
+ }
return false;
}
/* Finds addresses in *OP_P inside STMT. */
static void
-find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
+find_interesting_uses_address (struct ivopts_data *data, gimple stmt, tree *op_p)
{
- tree base = unshare_expr (*op_p), step = NULL;
+ tree base = *op_p, step = size_zero_node;
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
+ /* Do not play with volatile memory references. A bit too conservative,
+ perhaps, but safe. */
+ if (gimple_has_volatile_ops (stmt))
+ goto fail;
+
/* Ignore bitfields for now. Not really something terribly complicated
to handle. TODO. */
- if (TREE_CODE (base) == COMPONENT_REF
- && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
+ if (TREE_CODE (base) == BIT_FIELD_REF)
goto fail;
- if (STRICT_ALIGNMENT
- && may_be_unaligned_p (base))
- goto fail;
+ base = unshare_expr (base);
- ifs_ivopts_data.ivopts_data = data;
- ifs_ivopts_data.stmt = stmt;
- ifs_ivopts_data.step_p = &step;
- if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
- || zero_p (step))
- goto fail;
+ 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_INDEX2 (base)
+ && TREE_CODE (TMR_INDEX2 (base)) == SSA_NAME)
+ {
+ civ = get_iv (data, TMR_INDEX2 (base));
+ if (!civ)
+ goto fail;
+
+ TMR_INDEX2 (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 = size_zero_node;
+ if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
+ || integer_zerop (ifs_ivopts_data.step))
+ goto fail;
+ step = ifs_ivopts_data.step;
+
+ /* Check that the base expression is addressable. This needs
+ to be done after substituting bases of IVs into it. */
+ if (may_be_nonaddressable_p (base))
+ goto fail;
+
+ /* Moreover, on strict alignment platforms, check that it is
+ sufficiently aligned. */
+ if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
+ goto fail;
+
+ base = build_fold_addr_expr (base);
+
+ /* Substituting bases of IVs into the base expression might
+ have caused folding opportunities. */
+ if (TREE_CODE (base) == ADDR_EXPR)
+ {
+ tree *ref = &TREE_OPERAND (base, 0);
+ while (handled_component_p (*ref))
+ ref = &TREE_OPERAND (*ref, 0);
+ if (TREE_CODE (*ref) == MEM_REF)
+ {
+ tree tem = fold_binary (MEM_REF, TREE_TYPE (*ref),
+ TREE_OPERAND (*ref, 0),
+ TREE_OPERAND (*ref, 1));
+ if (tem)
+ *ref = tem;
+ }
+ }
+ }
civ = alloc_iv (base, step);
record_use (data, op_p, civ, stmt, USE_ADDRESS);
/* Finds and records invariants used in STMT. */
static void
-find_invariants_stmt (struct ivopts_data *data, tree stmt)
+find_invariants_stmt (struct ivopts_data *data, gimple 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);
}
}
/* Finds interesting uses of induction variables in the statement STMT. */
static void
-find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
+find_interesting_uses_stmt (struct ivopts_data *data, gimple stmt)
{
struct iv *iv;
- tree op, lhs, rhs;
- use_optype uses = NULL;
- unsigned i, n;
+ tree op, *lhs, *rhs;
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ enum tree_code code;
find_invariants_stmt (data, stmt);
- if (TREE_CODE (stmt) == COND_EXPR)
+ if (gimple_code (stmt) == GIMPLE_COND)
{
- find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
+ find_interesting_uses_cond (data, stmt);
return;
}
- if (TREE_CODE (stmt) == MODIFY_EXPR)
+ if (is_gimple_assign (stmt))
{
- lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
+ lhs = gimple_assign_lhs_ptr (stmt);
+ rhs = gimple_assign_rhs1_ptr (stmt);
- if (TREE_CODE (lhs) == SSA_NAME)
+ if (TREE_CODE (*lhs) == SSA_NAME)
{
/* If the statement defines an induction variable, the uses are not
interesting by themselves. */
- iv = get_iv (data, lhs);
+ 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)))
+ code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+ && (REFERENCE_CLASS_P (*rhs)
+ || is_gimple_val (*rhs)))
{
- case tcc_comparison:
- find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
- return;
+ if (REFERENCE_CLASS_P (*rhs))
+ find_interesting_uses_address (data, stmt, rhs);
+ else
+ find_interesting_uses_op (data, *rhs);
- case tcc_reference:
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
- if (REFERENCE_CLASS_P (lhs))
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
+ if (REFERENCE_CLASS_P (*lhs))
+ find_interesting_uses_address (data, stmt, lhs);
return;
-
- default: ;
}
-
- if (REFERENCE_CLASS_P (lhs)
- && is_gimple_val (rhs))
+ else if (TREE_CODE_CLASS (code) == tcc_comparison)
{
- find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
- find_interesting_uses_op (data, rhs);
+ find_interesting_uses_cond (data, stmt);
return;
}
call (memory). */
}
- if (TREE_CODE (stmt) == PHI_NODE
- && bb_for_stmt (stmt) == data->current_loop->header)
+ if (gimple_code (stmt) == GIMPLE_PHI
+ && gimple_bb (stmt) == data->current_loop->header)
{
- lhs = PHI_RESULT (stmt);
- iv = get_iv (data, lhs);
+ iv = get_iv (data, PHI_RESULT (stmt));
- 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;
static void
find_interesting_uses_outside (struct ivopts_data *data, edge exit)
{
- tree phi, def;
+ gimple phi;
+ gimple_stmt_iterator psi;
+ tree def;
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
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);
}
}
find_interesting_uses (struct ivopts_data *data)
{
basic_block bb;
- block_stmt_iterator bsi;
- tree phi;
+ gimple_stmt_iterator bsi;
basic_block *body = get_loop_body (data->current_loop);
unsigned i;
struct version_info *info;
&& !flow_bb_inside_loop_p (data->current_loop, e->dest))
find_interesting_uses_outside (data, e);
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- find_interesting_uses_stmt (data, phi);
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_interesting_uses_stmt (data, bsi_stmt (bsi));
+ for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ if (!is_gimple_debug (gsi_stmt (bsi)))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
}
if (dump_file && (dump_flags & TDF_DETAILS))
}
/* 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 POINTER_PLUS_EXPR:
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);
+ *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
if (op0 == TREE_OPERAND (expr, 0)
&& op1 == TREE_OPERAND (expr, 1))
return orig_expr;
- if (zero_p (op1))
+ if (integer_zerop (op1))
expr = op0;
- else if (zero_p (op0))
+ else if (integer_zerop (op0))
{
- if (code == PLUS_EXPR)
- expr = op1;
+ if (code == MINUS_EXPR)
+ expr = fold_build1 (NEGATE_EXPR, type, op1);
else
- expr = build1 (NEGATE_EXPR, type, op1);
+ expr = op1;
}
else
- expr = build2 (code, type, op0, op1);
+ expr = fold_build2 (code, type, op0, op1);
+
+ return fold_convert (orig_type, expr);
+
+ case MULT_EXPR:
+ op1 = TREE_OPERAND (expr, 1);
+ if (!cst_and_fits_in_hwi (op1))
+ return orig_expr;
+
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, false, false, &off0);
+ if (op0 == TREE_OPERAND (expr, 0))
+ return orig_expr;
+
+ *offset = off0 * int_cst_value (op1);
+ if (integer_zerop (op0))
+ expr = op0;
+ else
+ expr = fold_build2 (MULT_EXPR, type, op0, op1);
return fold_convert (orig_type, expr);
case ARRAY_REF:
+ case ARRAY_RANGE_REF:
if (!inside_addr)
return orig_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 MEM_REF:
+ /* ??? Offset operand? */
+ 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
static struct iv_cand *
add_candidate_1 (struct ivopts_data *data,
tree base, tree step, bool important, enum iv_position pos,
- struct iv_use *use, tree incremented_at)
+ struct iv_use *use, gimple incremented_at)
{
unsigned i;
struct iv_cand *cand = NULL;
tree type, orig_type;
-
- if (base)
+
+ /* For non-original variables, make sure their values are computed in a type
+ that does not invoke undefined behavior on overflows (since in general,
+ we cannot prove that these induction variables are non-wrapping). */
+ if (pos != IP_ORIGINAL)
{
orig_type = TREE_TYPE (base);
type = generic_type_for (orig_type);
if (type != orig_type)
{
base = fold_convert (type, base);
- if (step)
- step = fold_convert (type, step);
+ step = fold_convert (type, step);
}
}
if (cand->pos != pos)
continue;
- if (cand->incremented_at != incremented_at)
+ if (cand->incremented_at != incremented_at
+ || ((pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+ && cand->ainc_use != use))
continue;
if (!cand->iv)
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)
+ && (TYPE_PRECISION (TREE_TYPE (base))
+ == TYPE_PRECISION (TREE_TYPE (cand->iv->base))))
+ 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->important = important;
cand->incremented_at = incremented_at;
- VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_candidates, cand);
+ VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
+
+ if (step
+ && TREE_CODE (step) != INTEGER_CST)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&step, find_depends, &cand->depends_on, NULL);
+ }
+
+ if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+ cand->ainc_use = use;
+ else
+ cand->ainc_use = NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_cand (dump_file, cand);
return false;
}
+/* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
+ Important field is set to IMPORTANT. */
+
+static void
+add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
+ bool important, struct iv_use *use)
+{
+ basic_block use_bb = gimple_bb (use->stmt);
+ enum machine_mode mem_mode;
+ unsigned HOST_WIDE_INT cstepi;
+
+ /* If we insert the increment in any position other than the standard
+ ones, we must ensure that it is incremented once per iteration.
+ It must not be in an inner nested loop, or one side of an if
+ statement. */
+ if (use_bb->loop_father != data->current_loop
+ || !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
+ || stmt_could_throw_p (use->stmt)
+ || !cst_and_fits_in_hwi (step))
+ return;
+
+ cstepi = int_cst_value (step);
+
+ mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
+ if ((HAVE_PRE_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+ || (HAVE_PRE_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+ {
+ enum tree_code code = MINUS_EXPR;
+ tree new_base;
+ tree new_step = step;
+
+ if (POINTER_TYPE_P (TREE_TYPE (base)))
+ {
+ new_step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
+ code = POINTER_PLUS_EXPR;
+ }
+ else
+ new_step = fold_convert (TREE_TYPE (base), new_step);
+ new_base = fold_build2 (code, TREE_TYPE (base), base, new_step);
+ add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
+ use->stmt);
+ }
+ if ((HAVE_POST_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+ || (HAVE_POST_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+ {
+ add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
+ use->stmt);
+ }
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. The candidate computation is scheduled on all available positions. */
static void
-add_candidate (struct ivopts_data *data,
+add_candidate (struct ivopts_data *data,
tree base, tree step, bool important, struct iv_use *use)
{
if (ip_normal_pos (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
+ add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL);
if (ip_end_pos (data->current_loop)
&& allow_ip_end_pos_p (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
+ add_candidate_1 (data, base, step, important, IP_END, use, NULL);
+
+ if (use != NULL && use->type == USE_ADDRESS)
+ add_autoinc_candidates (data, base, step, important, use);
}
/* Add a standard "0 + 1 * iteration" iv candidate for a
static void
add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
{
- tree phi, def;
+ gimple phi;
+ tree def;
struct iv_cand *cand;
add_candidate (data, iv->base, iv->step, true, NULL);
/* The same, but with initial value zero. */
- add_candidate (data,
- build_int_cst (TREE_TYPE (iv->base), 0),
- iv->step, true, NULL);
+ if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
+ add_candidate (data, size_int (0), iv->step, true, NULL);
+ else
+ add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
+ iv->step, true, NULL);
phi = SSA_NAME_DEF_STMT (iv->ssa_name);
- if (TREE_CODE (phi) == PHI_NODE)
+ if (gimple_code (phi) == GIMPLE_PHI)
{
/* Additionally record the possibility of leaving the original iv
untouched. */
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;
+ tree basetype;
- /* First, the trivial choices. */
- add_iv_value_candidates (data, iv, use);
-
- /* Second, try removing the COMPONENT_REFs. */
- if (TREE_CODE (iv->base) == ADDR_EXPR)
- {
- base = TREE_OPERAND (iv->base, 0);
- while (TREE_CODE (base) == COMPONENT_REF
- || (TREE_CODE (base) == ARRAY_REF
- && TREE_CODE (TREE_OPERAND (base, 1)) == INTEGER_CST))
- base = TREE_OPERAND (base, 0);
-
- if (base != TREE_OPERAND (iv->base, 0))
- {
- gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
-
- if (TREE_CODE (base) == INDIRECT_REF)
- base = TREE_OPERAND (base, 0);
- else
- base = build_addr (base);
- add_candidate (data, base, iv->step, false, use);
- }
- }
+ add_candidate (data, iv->base, iv->step, false, use);
- /* Third, try removing the constant offset. */
- abase = iv->base;
- base = strip_offset (abase, false, &offset);
- if (offset)
+ /* 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. */
+ basetype = TREE_TYPE (iv->base);
+ if (POINTER_TYPE_P (basetype))
+ basetype = sizetype;
+ add_candidate (data, build_int_cst (basetype, 0),
+ iv->step, true, use);
+
+ /* Third, try removing the constant offset. Make sure to even
+ add a candidate for &a[0] vs. (T *)&a. */
+ base = strip_offset (iv->base, &offset);
+ if (offset
+ || base != iv->base)
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 ();
}
}
}
-/* Finds the candidates for the induction variables. */
-
-static void
-find_iv_candidates (struct ivopts_data *data)
-{
- /* Add commonly used ivs. */
- add_standard_iv_candidates (data);
-
- /* Add old induction variables. */
- add_old_ivs_candidates (data);
-
- /* Add induction variables derived from uses. */
- add_derived_ivs_candidates (data);
-
- /* Record the important candidates. */
- record_important_candidates (data);
-}
-
/* Allocates the data structure mapping the (use, candidate) pairs to costs.
If consider_all_candidates is true, we use a two-dimensional array, otherwise
we allocate a simple list to every use. */
}
use->n_map_members = size;
- use->cost_map = xcalloc (size, sizeof (struct cost_pair));
+ use->cost_map = XCNEWVEC (struct cost_pair, size);
}
}
+/* Returns description of computation cost of expression whose runtime
+ cost is RUNTIME and complexity corresponds to COMPLEXITY. */
+
+static comp_cost
+new_cost (unsigned runtime, unsigned complexity)
+{
+ comp_cost cost;
+
+ cost.cost = runtime;
+ cost.complexity = complexity;
+
+ return cost;
+}
+
+/* Adds costs COST1 and COST2. */
+
+static comp_cost
+add_costs (comp_cost cost1, comp_cost cost2)
+{
+ cost1.cost += cost2.cost;
+ cost1.complexity += cost2.complexity;
+
+ return cost1;
+}
+/* Subtracts costs COST1 and COST2. */
+
+static comp_cost
+sub_costs (comp_cost cost1, comp_cost cost2)
+{
+ cost1.cost -= cost2.cost;
+ cost1.complexity -= cost2.complexity;
+
+ return cost1;
+}
+
+/* Returns a negative number if COST1 < COST2, a positive number if
+ COST1 > COST2, and 0 if COST1 = COST2. */
+
+static int
+compare_costs (comp_cost cost1, comp_cost cost2)
+{
+ if (cost1.cost == cost2.cost)
+ return cost1.complexity - cost2.complexity;
+
+ return cost1.cost - cost2.cost;
+}
+
+/* Returns true if COST is infinite. */
+
+static bool
+infinite_cost_p (comp_cost cost)
+{
+ return cost.cost == INFTY;
+}
+
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
- on invariants DEPENDS_ON. */
+ on invariants DEPENDS_ON and that the value used in expressing it
+ is VALUE, and in case of iv elimination the comparison operator is COMP. */
static void
set_use_iv_cost (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand, unsigned cost,
- bitmap depends_on)
+ struct iv_use *use, struct iv_cand *cand,
+ comp_cost cost, bitmap depends_on, tree value,
+ enum tree_code comp, int inv_expr_id)
{
unsigned i, s;
- if (cost == INFTY)
+ if (infinite_cost_p (cost))
{
BITMAP_FREE (depends_on);
return;
use->cost_map[cand->id].cand = cand;
use->cost_map[cand->id].cost = cost;
use->cost_map[cand->id].depends_on = depends_on;
+ use->cost_map[cand->id].value = value;
+ use->cost_map[cand->id].comp = comp;
+ use->cost_map[cand->id].inv_expr_id = inv_expr_id;
return;
}
use->cost_map[i].cand = cand;
use->cost_map[i].cost = cost;
use->cost_map[i].depends_on = depends_on;
+ use->cost_map[i].value = value;
+ use->cost_map[i].comp = comp;
+ use->cost_map[i].inv_expr_id = inv_expr_id;
}
/* Gets cost of (USE, CANDIDATE) pair. */
return ret;
}
-
+
/* n_map_members is a power of two, so this computes modulo. */
s = cand->id & (use->n_map_members - 1);
for (i = s; i < use->n_map_members; i++)
/* Returns estimate on cost of computing SEQ. */
static unsigned
-seq_cost (rtx seq)
+seq_cost (rtx seq, bool speed)
{
unsigned cost = 0;
rtx set;
{
set = single_set (seq);
if (set)
- cost += rtx_cost (set, SET);
+ cost += set_src_cost (SET_SRC (set), speed);
else
cost++;
}
static rtx
produce_memory_decl_rtl (tree obj, int *regno)
{
+ addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj));
+ enum machine_mode address_mode = targetm.addr_space.address_mode (as);
rtx x;
-
+
gcc_assert (obj);
if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
{
const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
- x = gen_rtx_SYMBOL_REF (Pmode, name);
+ x = gen_rtx_SYMBOL_REF (address_mode, name);
+ SET_SYMBOL_REF_DECL (x, obj);
+ x = gen_rtx_MEM (DECL_MODE (obj), x);
+ set_mem_addr_space (x, as);
+ targetm.encode_section_info (obj, x, true);
}
else
- x = gen_raw_REG (Pmode, (*regno)++);
+ {
+ x = gen_raw_REG (address_mode, (*regno)++);
+ x = gen_rtx_MEM (DECL_MODE (obj), x);
+ set_mem_addr_space (x, as);
+ }
- 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;
if (x)
{
- VARRAY_PUSH_GENERIC_PTR_NOGC (decl_rtl_to_reset, obj);
+ VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
SET_DECL_RTL (obj, x);
}
/* Determines cost of the computation of EXPR. */
static unsigned
-computation_cost (tree expr)
+computation_cost (tree expr, bool speed)
{
rtx seq, rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
/* Avoid using hard regs in ways which may be unsupported. */
int regno = LAST_VIRTUAL_REGISTER + 1;
+ struct cgraph_node *node = cgraph_get_node (current_function_decl);
+ enum node_frequency real_frequency = node->frequency;
+ node->frequency = NODE_FREQUENCY_NORMAL;
+ crtl->maybe_hot_insn_p = speed;
walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
start_sequence ();
rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
seq = get_insns ();
end_sequence ();
+ default_rtl_profile ();
+ node->frequency = real_frequency;
- cost = seq_cost (seq);
- if (GET_CODE (rslt) == MEM)
- cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
+ cost = seq_cost (seq, speed);
+ if (MEM_P (rslt))
+ cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type),
+ TYPE_ADDR_SPACE (type), speed);
+ else if (!REG_P (rslt))
+ cost += set_src_cost (rslt, speed);
return cost;
}
/* Returns variable containing the value of candidate CAND at statement AT. */
static tree
-var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
+var_at_stmt (struct loop *loop, struct iv_cand *cand, gimple stmt)
{
if (stmt_after_increment (loop, cand, stmt))
return cand->var_after;
return cand->var_before;
}
-/* Determines the expression by that USE is expressed from induction variable
- CAND at statement AT in LOOP. */
+/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
+ same precision that is at least as wide as the precision of TYPE, stores
+ BA to A and BB to B, and returns the type of BA. Otherwise, returns the
+ type of A and B. */
static tree
-get_computation_at (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at)
+determine_common_wider_type (tree *a, tree *b)
+{
+ tree wider_type = NULL;
+ tree suba, subb;
+ tree atype = TREE_TYPE (*a);
+
+ if (CONVERT_EXPR_P (*a))
+ {
+ suba = TREE_OPERAND (*a, 0);
+ wider_type = TREE_TYPE (suba);
+ if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
+ return atype;
+ }
+ else
+ return atype;
+
+ if (CONVERT_EXPR_P (*b))
+ {
+ subb = TREE_OPERAND (*b, 0);
+ if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
+ return atype;
+ }
+ else
+ return atype;
+
+ *a = suba;
+ *b = subb;
+ return wider_type;
+}
+
+/* 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, gimple 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;
+ tree cstep = cand->iv->step, cstep_common;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+ tree common_type, var;
tree uutype;
- tree expr, delta;
- tree ratio;
- unsigned HOST_WIDE_INT ustepi, cstepi;
- HOST_WIDE_INT ratioi;
+ aff_tree cbase_aff, var_aff;
+ double_int rat;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
/* We do not have a precision to express the values of use. */
- return NULL_TREE;
- }
-
- expr = var_at_stmt (loop, cand, at);
-
- if (TREE_TYPE (expr) != ctype)
- {
- /* This may happen with the original ivs. */
- expr = fold_convert (ctype, expr);
+ return false;
}
- if (TYPE_UNSIGNED (utype))
- uutype = utype;
- else
- {
- uutype = unsigned_type_for (utype);
- ubase = fold_convert (uutype, ubase);
- ustep = fold_convert (uutype, ustep);
- }
+ var = var_at_stmt (loop, cand, at);
+ uutype = unsigned_type_for (utype);
- if (uutype != ctype)
+ /* If the conversion is not noop, perform it. */
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
- expr = fold_convert (uutype, expr);
- cbase = fold_convert (uutype, cbase);
cstep = fold_convert (uutype, cstep);
+ cbase = fold_convert (uutype, cbase);
+ var = fold_convert (uutype, var);
}
- if (!cst_and_fits_in_hwi (cstep)
- || !cst_and_fits_in_hwi (ustep))
- return NULL_TREE;
+ 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);
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
+ /* use = ubase - ratio * cbase + ratio * var. */
+ tree_to_aff_combination (ubase, common_type, aff);
+ tree_to_aff_combination (cbase, common_type, &cbase_aff);
+ tree_to_aff_combination (var, uutype, &var_aff);
- if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
+ /* We need to shift the value if we are after the increment. */
+ if (stmt_after_increment (loop, cand, at))
{
- /* 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;
+ 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);
}
- /* 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));
+ aff_combination_scale (&cbase_aff, double_int_neg (rat));
+ aff_combination_add (aff, &cbase_aff);
+ if (common_type != uutype)
+ aff_combination_convert (aff, uutype);
- /* use = ubase - ratio * cbase + ratio * var.
+ aff_combination_scale (&var_aff, rat);
+ aff_combination_add (aff, &var_aff);
- 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. */
+ return true;
+}
- if (ratioi == 1)
- {
- delta = fold (build2 (MINUS_EXPR, uutype, ubase, cbase));
- expr = fold (build2 (PLUS_EXPR, uutype, expr, delta));
- }
- else if (ratioi == -1)
- {
- delta = fold (build2 (PLUS_EXPR, uutype, ubase, cbase));
- expr = fold (build2 (MINUS_EXPR, uutype, delta, expr));
- }
- else
- {
- 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));
- }
+/* Determines the expression by that USE is expressed from induction variable
+ CAND at statement AT in LOOP. The computation is unshared. */
+
+static tree
+get_computation_at (struct loop *loop,
+ struct iv_use *use, struct iv_cand *cand, gimple at)
+{
+ aff_tree aff;
+ tree type = TREE_TYPE (use->iv->base);
- return fold_convert (utype, expr);
+ 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. */
+ CAND in LOOP. The computation is unshared. */
static tree
get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
return get_computation_at (loop, use, cand, use->stmt);
}
+/* Adjust the cost COST for being in loop setup rather than loop body.
+ If we're optimizing for space, the loop setup overhead is constant;
+ if we're optimizing for speed, amortize it over the per-iteration cost. */
+static unsigned
+adjust_setup_cost (struct ivopts_data *data, unsigned cost)
+{
+ if (cost == INFTY)
+ return cost;
+ else if (optimize_loop_for_speed_p (data->current_loop))
+ return cost / avg_loop_niter (data->current_loop);
+ else
+ return cost;
+}
+
/* Returns cost of addition in MODE. */
static unsigned
-add_cost (enum machine_mode mode)
+add_cost (enum machine_mode mode, bool speed)
{
static unsigned costs[NUM_MACHINE_MODES];
rtx seq;
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 ();
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (!cost)
cost = 1;
costs[mode] = cost;
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Addition in %s costs %d\n",
GET_MODE_NAME (mode), cost);
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
-multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
+unsigned
+multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
{
static htab_t costs;
struct mbc_entry **cached, act;
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 ();
-
- cost = seq_cost (seq);
+
+ cost = seq_cost (seq, speed);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
return cost;
}
-/* 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.
-
- TODO -- there must be some better way. This all is quite crude. */
+/* Returns true if multiplying by RATIO is allowed in an address. Test the
+ validity for a memory reference accessing memory of mode MODE in
+ address space AS. */
-static unsigned
-get_address_cost (bool symbol_present, bool var_present,
- unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
+DEF_VEC_P (sbitmap);
+DEF_VEC_ALLOC_P (sbitmap, heap);
+
+bool
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode,
+ addr_space_t as)
{
#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];
- 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;
+ unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mode;
+ static VEC (sbitmap, heap) *valid_mult_list;
+ sbitmap valid_mult;
+ if (data_index >= VEC_length (sbitmap, valid_mult_list))
+ VEC_safe_grow_cleared (sbitmap, heap, valid_mult_list, data_index + 1);
+
+ valid_mult = VEC_index (sbitmap, valid_mult_list, data_index);
if (!valid_mult)
{
+ enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ rtx reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
+ rtx addr;
HOST_WIDE_INT i;
- reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
-
- addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
- for (i = 1; i <= 1 << 20; i <<= 1)
- {
- XEXP (addr, 1) = GEN_INT (i);
- if (!memory_address_p (Pmode, addr))
- break;
- }
- max_offset = i >> 1;
- off = max_offset;
-
- for (i = 1; i <= 1 << 20; i <<= 1)
- {
- XEXP (addr, 1) = GEN_INT (-i);
- if (!memory_address_p (Pmode, addr))
- break;
- }
- min_offset = -(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);
- }
-
valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
sbitmap_zero (valid_mult);
- rat = 1;
- addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
+ addr = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
{
- XEXP (addr, 1) = GEN_INT (i);
- if (memory_address_p (Pmode, addr))
- {
- SET_BIT (valid_mult, i + MAX_RATIO);
- rat = i;
- }
+ XEXP (addr, 1) = gen_int_mode (i, address_mode);
+ if (memory_address_addr_space_p (mode, addr, as))
+ SET_BIT (valid_mult, i + MAX_RATIO);
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
}
+
+ VEC_replace (sbitmap, valid_mult_list, data_index, valid_mult);
}
- bits = GET_MODE_BITSIZE (Pmode);
- mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- offset &= mask;
- if ((offset >> (bits - 1) & 1))
- offset |= ~mask;
- s_offset = offset;
+ if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
+ return false;
- cost = 0;
- offset_p = (s_offset != 0
- && min_offset <= s_offset && s_offset <= max_offset);
- ratio_p = (ratio != 1
- && -MAX_RATIO <= ratio && ratio <= MAX_RATIO
- && TEST_BIT (valid_mult, ratio + MAX_RATIO));
+ return TEST_BIT (valid_mult, ratio + MAX_RATIO);
+}
- if (ratio != 1 && !ratio_p)
- cost += multiply_by_cost (ratio, Pmode);
+/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
+ If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
+ variable is omitted. Compute the cost for a memory reference that accesses
+ a memory location of mode MEM_MODE in address space AS.
- if (s_offset && !offset_p && !symbol_present)
- {
- cost += add_cost (Pmode);
- var_present = true;
- }
+ MAY_AUTOINC is set to true if the autoincrement (increasing index by
+ size of MEM_MODE / RATIO) is available. To make this determination, we
+ look at the size of the increment to be made, which is given in CSTEP.
+ CSTEP may be zero if the step is unknown.
+ STMT_AFTER_INC is true iff the statement we're looking at is after the
+ increment of the original biv.
+
+ TODO -- there must be some better way. This all is quite crude. */
+
+typedef struct
+{
+ HOST_WIDE_INT min_offset, max_offset;
+ unsigned costs[2][2][2][2];
+} *address_cost_data;
+
+DEF_VEC_P (address_cost_data);
+DEF_VEC_ALLOC_P (address_cost_data, heap);
- acost = costs[symbol_present][var_present][offset_p][ratio_p];
- if (!acost)
+static comp_cost
+get_address_cost (bool symbol_present, bool var_present,
+ unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
+ HOST_WIDE_INT cstep, enum machine_mode mem_mode,
+ addr_space_t as, bool speed,
+ bool stmt_after_inc, bool *may_autoinc)
+{
+ enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ static VEC(address_cost_data, heap) *address_cost_data_list;
+ unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mem_mode;
+ address_cost_data data;
+ static bool has_preinc[MAX_MACHINE_MODE], has_postinc[MAX_MACHINE_MODE];
+ static bool has_predec[MAX_MACHINE_MODE], has_postdec[MAX_MACHINE_MODE];
+ unsigned cost, acost, complexity;
+ bool offset_p, ratio_p, autoinc;
+ HOST_WIDE_INT s_offset, autoinc_offset, msize;
+ unsigned HOST_WIDE_INT mask;
+ unsigned bits;
+
+ if (data_index >= VEC_length (address_cost_data, address_cost_data_list))
+ VEC_safe_grow_cleared (address_cost_data, heap, address_cost_data_list,
+ data_index + 1);
+
+ data = VEC_index (address_cost_data, address_cost_data_list, data_index);
+ if (!data)
{
+ HOST_WIDE_INT i;
+ HOST_WIDE_INT rat, off = 0;
+ int old_cse_not_expected, width;
+ unsigned sym_p, var_p, off_p, rat_p, add_c;
+ rtx seq, addr, base;
+ rtx reg0, reg1;
+
+ data = (address_cost_data) xcalloc (1, sizeof (*data));
+
+ reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
+
+ width = GET_MODE_BITSIZE (address_mode) - 1;
+ if (width > (HOST_BITS_PER_WIDE_INT - 1))
+ width = HOST_BITS_PER_WIDE_INT - 1;
+ addr = gen_rtx_fmt_ee (PLUS, address_mode, reg1, NULL_RTX);
+
+ for (i = width; i >= 0; i--)
+ {
+ off = -((HOST_WIDE_INT) 1 << i);
+ XEXP (addr, 1) = gen_int_mode (off, address_mode);
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ break;
+ }
+ data->min_offset = (i == -1? 0 : off);
+
+ for (i = width; i >= 0; i--)
+ {
+ off = ((HOST_WIDE_INT) 1 << i) - 1;
+ XEXP (addr, 1) = gen_int_mode (off, address_mode);
+ if (memory_address_addr_space_p (mem_mode, addr, as))
+ break;
+ }
+ if (i == -1)
+ off = 0;
+ data->max_offset = off;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "get_address_cost:\n");
+ fprintf (dump_file, " min offset %s " HOST_WIDE_INT_PRINT_DEC "\n",
+ GET_MODE_NAME (mem_mode),
+ data->min_offset);
+ fprintf (dump_file, " max offset %s " HOST_WIDE_INT_PRINT_DEC "\n",
+ GET_MODE_NAME (mem_mode),
+ data->max_offset);
+ }
+
+ rat = 1;
+ for (i = 2; i <= MAX_RATIO; i++)
+ if (multiplier_allowed_in_address_p (i, mem_mode, as))
+ {
+ rat = i;
+ break;
+ }
+
+ /* Compute the cost of various addressing modes. */
acost = 0;
-
- 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));
+ reg0 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
+ reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
+
+ if (HAVE_PRE_DECREMENT)
+ {
+ addr = gen_rtx_PRE_DEC (address_mode, reg0);
+ has_predec[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ if (HAVE_POST_DECREMENT)
+ {
+ addr = gen_rtx_POST_DEC (address_mode, reg0);
+ has_postdec[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ if (HAVE_PRE_INCREMENT)
+ {
+ addr = gen_rtx_PRE_INC (address_mode, reg0);
+ has_preinc[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ if (HAVE_POST_INCREMENT)
+ {
+ addr = gen_rtx_POST_INC (address_mode, reg0);
+ has_postinc[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ 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;
- if (var_present)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+ addr = reg0;
+ if (rat_p)
+ addr = gen_rtx_fmt_ee (MULT, address_mode, addr,
+ gen_int_mode (rat, address_mode));
+
+ if (var_p)
+ addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, reg1);
+
+ if (sym_p)
+ {
+ base = gen_rtx_SYMBOL_REF (address_mode, ggc_strdup (""));
+ /* ??? We can run into trouble with some backends by presenting
+ it with symbols which haven't been properly passed through
+ targetm.encode_section_info. By setting the local bit, we
+ enhance the probability of things working. */
+ SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
+
+ if (off_p)
+ base = gen_rtx_fmt_e (CONST, address_mode,
+ gen_rtx_fmt_ee
+ (PLUS, address_mode, base,
+ gen_int_mode (off, address_mode)));
+ }
+ else if (off_p)
+ base = gen_int_mode (off, address_mode);
+ else
+ base = NULL_RTX;
+
+ if (base)
+ addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, base);
+
+ start_sequence ();
+ /* To avoid splitting addressing modes, pretend that no cse will
+ follow. */
+ old_cse_not_expected = cse_not_expected;
+ cse_not_expected = true;
+ addr = memory_address_addr_space (mem_mode, addr, as);
+ cse_not_expected = old_cse_not_expected;
+ seq = get_insns ();
+ end_sequence ();
+
+ acost = seq_cost (seq, speed);
+ acost += address_cost (addr, mem_mode, as, speed);
+
+ if (!acost)
+ acost = 1;
+ data->costs[sym_p][var_p][off_p][rat_p] = acost;
+ }
- if (symbol_present)
+ /* 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 (address_mode, speed);
+ for (i = 0; i < 8; i++)
{
- 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)));
+ var_p = i & 1;
+ off_p = (i >> 1) & 1;
+ rat_p = (i >> 2) & 1;
+
+ acost = data->costs[0][1][off_p][rat_p] + 1;
+ if (var_p)
+ acost += add_c;
+
+ if (acost < data->costs[1][var_p][off_p][rat_p])
+ data->costs[1][var_p][off_p][rat_p] = acost;
}
- 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;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Address costs:\n");
+
+ for (i = 0; i < 16; i++)
+ {
+ sym_p = i & 1;
+ var_p = (i >> 1) & 1;
+ off_p = (i >> 2) & 1;
+ rat_p = (i >> 3) & 1;
+
+ fprintf (dump_file, " ");
+ if (sym_p)
+ fprintf (dump_file, "sym + ");
+ if (var_p)
+ fprintf (dump_file, "var + ");
+ if (off_p)
+ fprintf (dump_file, "cst + ");
+ if (rat_p)
+ fprintf (dump_file, "rat * ");
+
+ acost = data->costs[sym_p][var_p][off_p][rat_p];
+ fprintf (dump_file, "index costs %d\n", acost);
+ }
+ if (has_predec[mem_mode] || has_postdec[mem_mode]
+ || has_preinc[mem_mode] || has_postinc[mem_mode])
+ fprintf (dump_file, " May include autoinc/dec\n");
+ fprintf (dump_file, "\n");
+ }
+
+ VEC_replace (address_cost_data, address_cost_data_list,
+ data_index, data);
}
- return cost + acost;
-}
+ bits = GET_MODE_BITSIZE (address_mode);
+ mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
+ offset &= mask;
+ if ((offset >> (bits - 1) & 1))
+ offset |= ~mask;
+ s_offset = offset;
-/* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
- the bitmap to that we should store it. */
+ autoinc = false;
+ msize = GET_MODE_SIZE (mem_mode);
+ autoinc_offset = offset;
+ if (stmt_after_inc)
+ autoinc_offset += ratio * cstep;
+ if (symbol_present || var_present || ratio != 1)
+ autoinc = false;
+ else if ((has_postinc[mem_mode] && autoinc_offset == 0
+ && msize == cstep)
+ || (has_postdec[mem_mode] && autoinc_offset == 0
+ && msize == -cstep)
+ || (has_preinc[mem_mode] && autoinc_offset == msize
+ && msize == cstep)
+ || (has_predec[mem_mode] && autoinc_offset == -msize
+ && msize == -cstep))
+ autoinc = true;
-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;
+ cost = 0;
+ offset_p = (s_offset != 0
+ && data->min_offset <= s_offset
+ && s_offset <= data->max_offset);
+ ratio_p = (ratio != 1
+ && multiplier_allowed_in_address_p (ratio, mem_mode, as));
- if (TREE_CODE (*expr_p) != SSA_NAME)
- return NULL_TREE;
- info = name_info (fd_ivopts_data, *expr_p);
+ if (ratio != 1 && !ratio_p)
+ cost += multiply_by_cost (ratio, address_mode, speed);
- if (!info->inv_id || info->has_nonlin_use)
- return NULL_TREE;
+ if (s_offset && !offset_p && !symbol_present)
+ cost += add_cost (address_mode, speed);
- if (!*depends_on)
- *depends_on = BITMAP_ALLOC (NULL);
- bitmap_set_bit (*depends_on, info->inv_id);
+ if (may_autoinc)
+ *may_autoinc = autoinc;
+ acost = data->costs[symbol_present][var_present][offset_p][ratio_p];
+ complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
+ return new_cost (cost + acost, complexity);
+}
- return NULL_TREE;
+ /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
+ the EXPR operand holding the shift. COST0 and COST1 are the costs for
+ calculating the operands of EXPR. Returns true if successful, and returns
+ the cost in COST. */
+
+static bool
+get_shiftadd_cost (tree expr, enum machine_mode mode, comp_cost cost0,
+ comp_cost cost1, tree mult, bool speed, comp_cost *cost)
+{
+ comp_cost res;
+ tree op1 = TREE_OPERAND (expr, 1);
+ tree cst = TREE_OPERAND (mult, 1);
+ tree multop = TREE_OPERAND (mult, 0);
+ int m = exact_log2 (int_cst_value (cst));
+ int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode));
+ int sa_cost;
+
+ if (!(m >= 0 && m < maxm))
+ return false;
+
+ sa_cost = (TREE_CODE (expr) != MINUS_EXPR
+ ? shiftadd_cost[speed][mode][m]
+ : (mult == op1
+ ? shiftsub1_cost[speed][mode][m]
+ : shiftsub0_cost[speed][mode][m]));
+ res = new_cost (sa_cost, 0);
+ res = add_costs (res, mult == op1 ? cost0 : cost1);
+
+ STRIP_NOPS (multop);
+ if (!is_gimple_val (multop))
+ res = add_costs (res, force_expr_to_var_cost (multop, speed));
+
+ *cost = res;
+ return true;
}
-/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
- invariants the computation depends on. */
+/* Estimates cost of forcing expression EXPR into a variable. */
-static unsigned
-force_var_cost (struct ivopts_data *data,
- tree expr, bitmap *depends_on)
+static comp_cost
+force_expr_to_var_cost (tree expr, bool speed)
{
static bool costs_initialized = false;
- static unsigned integer_cost;
- static unsigned symbol_cost;
- static unsigned address_cost;
+ static unsigned integer_cost [2];
+ static unsigned symbol_cost [2];
+ static unsigned address_cost [2];
tree op0, op1;
- unsigned cost0, cost1, cost;
+ comp_cost cost0, cost1, cost;
enum machine_mode mode;
if (!costs_initialized)
{
- tree var = create_tmp_var_raw (integer_type_node, "test_var");
- rtx x = gen_rtx_MEM (DECL_MODE (var),
- gen_rtx_SYMBOL_REF (Pmode, "test_var"));
- tree addr;
tree type = build_pointer_type (integer_type_node);
+ tree var, addr;
+ rtx x;
+ int i;
- 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);
+
addr = build1 (ADDR_EXPR, type, var);
- symbol_cost = computation_cost (addr) + 1;
- address_cost
- = computation_cost (build2 (PLUS_EXPR, type,
- addr,
- build_int_cst_type (type, 2000))) + 1;
- if (dump_file && (dump_flags & TDF_DETAILS))
+
+ for (i = 0; i < 2; i++)
{
- fprintf (dump_file, "force_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);
- fprintf (dump_file, " other %d\n", (int) target_spill_cost);
- fprintf (dump_file, "\n");
+ integer_cost[i] = computation_cost (build_int_cst (integer_type_node,
+ 2000), i);
+
+ symbol_cost[i] = computation_cost (addr, i) + 1;
+
+ address_cost[i]
+ = computation_cost (fold_build_pointer_plus_hwi (addr, 2000), i) + 1;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
+ fprintf (dump_file, " integer %d\n", (int) integer_cost[i]);
+ fprintf (dump_file, " symbol %d\n", (int) symbol_cost[i]);
+ fprintf (dump_file, " address %d\n", (int) address_cost[i]);
+ fprintf (dump_file, " other %d\n", (int) target_spill_cost[i]);
+ fprintf (dump_file, "\n");
+ }
}
costs_initialized = true;
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;
+ return zero_cost;
- if (TREE_INVARIANT (expr))
+ if (is_gimple_min_invariant (expr))
{
if (TREE_CODE (expr) == INTEGER_CST)
- return integer_cost;
+ return new_cost (integer_cost [speed], 0);
if (TREE_CODE (expr) == ADDR_EXPR)
{
if (TREE_CODE (obj) == VAR_DECL
|| TREE_CODE (obj) == PARM_DECL
|| TREE_CODE (obj) == RESULT_DECL)
- return symbol_cost;
+ return new_cost (symbol_cost [speed], 0);
}
- return address_cost;
+ return new_cost (address_cost [speed], 0);
}
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
STRIP_NOPS (op1);
if (is_gimple_val (op0))
- cost0 = 0;
+ cost0 = zero_cost;
else
- cost0 = force_var_cost (data, op0, NULL);
+ cost0 = force_expr_to_var_cost (op0, speed);
if (is_gimple_val (op1))
- cost1 = 0;
+ cost1 = zero_cost;
else
- cost1 = force_var_cost (data, op1, NULL);
+ cost1 = force_expr_to_var_cost (op1, speed);
break;
+ case NEGATE_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ STRIP_NOPS (op0);
+ op1 = NULL_TREE;
+
+ if (is_gimple_val (op0))
+ cost0 = zero_cost;
+ else
+ cost0 = force_expr_to_var_cost (op0, speed);
+
+ cost1 = zero_cost;
+ break;
+
default:
/* Just an arbitrary value, FIXME. */
- return target_spill_cost;
+ return new_cost (target_spill_cost[speed], 0);
}
mode = TYPE_MODE (TREE_TYPE (expr));
switch (TREE_CODE (expr))
{
+ case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
- cost = add_cost (mode);
+ case NEGATE_EXPR:
+ cost = new_cost (add_cost (mode, speed), 0);
+ if (TREE_CODE (expr) != NEGATE_EXPR)
+ {
+ tree mult = NULL_TREE;
+ comp_cost sa_cost;
+ if (TREE_CODE (op1) == MULT_EXPR)
+ mult = op1;
+ else if (TREE_CODE (op0) == MULT_EXPR)
+ mult = op0;
+
+ if (mult != NULL_TREE
+ && cst_and_fits_in_hwi (TREE_OPERAND (mult, 1))
+ && get_shiftadd_cost (expr, mode, cost0, cost1, mult, speed,
+ &sa_cost))
+ return sa_cost;
+ }
break;
case MULT_EXPR:
if (cst_and_fits_in_hwi (op0))
- cost = multiply_by_cost (int_cst_value (op0), mode);
+ cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
else if (cst_and_fits_in_hwi (op1))
- cost = multiply_by_cost (int_cst_value (op1), mode);
+ cost = new_cost (multiply_by_cost (int_cst_value (op1), mode, speed), 0);
else
- return target_spill_cost;
+ return new_cost (target_spill_cost [speed], 0);
break;
default:
gcc_unreachable ();
}
- cost += cost0;
- cost += cost1;
+ cost = add_costs (cost, cost0);
+ cost = add_costs (cost, cost1);
/* Bound the cost by target_spill_cost. The parts of complicated
computations often are either loop invariant or at least can
be shared between several iv uses, so letting this grow without
limits would not give reasonable results. */
- return cost < target_spill_cost ? cost : target_spill_cost;
+ if (cost.cost > (int) target_spill_cost [speed])
+ cost.cost = target_spill_cost [speed];
+
+ return cost;
+}
+
+/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
+ invariants the computation depends on. */
+
+static comp_cost
+force_var_cost (struct ivopts_data *data,
+ tree expr, bitmap *depends_on)
+{
+ if (depends_on)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&expr, find_depends, depends_on, NULL);
+ }
+
+ return force_expr_to_var_cost (expr, data->speed);
}
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
to false if the corresponding part is missing. DEPENDS_ON is a set of the
invariants the computation depends on. */
-static unsigned
+static comp_cost
split_address_cost (struct ivopts_data *data,
tree addr, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
tree toffset;
enum machine_mode mode;
int unsignedp, volatilep;
-
+
core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
&unsignedp, &volatilep, false);
*var_present = true;
fd_ivopts_data = data;
walk_tree (&addr, find_depends, depends_on, NULL);
- return target_spill_cost;
+ return new_cost (target_spill_cost[data->speed], 0);
}
*offset += bitpos / BITS_PER_UNIT;
{
*symbol_present = true;
*var_present = false;
- return 0;
+ return zero_cost;
}
-
+
*symbol_present = false;
*var_present = true;
- return 0;
+ return zero_cost;
}
/* Estimates cost of expressing difference of addresses E1 - E2 as
part is missing. DEPENDS_ON is a set of the invariants the computation
depends on. */
-static unsigned
+static comp_cost
ptr_difference_cost (struct ivopts_data *data,
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
HOST_WIDE_INT diff = 0;
- unsigned cost;
+ aff_tree aff_e1, aff_e2;
+ tree type;
gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
*offset += diff;
*symbol_present = false;
*var_present = false;
- return 0;
+ return zero_cost;
}
- if (e2 == integer_zero_node)
+ if (integer_zerop (e2))
return split_address_cost (data, TREE_OPERAND (e1, 0),
symbol_present, var_present, offset, depends_on);
*symbol_present = false;
*var_present = true;
-
- cost = force_var_cost (data, e1, depends_on);
- cost += force_var_cost (data, e2, depends_on);
- cost += add_cost (Pmode);
- return cost;
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
+
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Estimates cost of expressing difference E1 - E2 as
part is missing. DEPENDS_ON is a set of the invariants the computation
depends on. */
-static unsigned
+static comp_cost
difference_cost (struct ivopts_data *data,
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- unsigned cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
+ aff_tree aff_e1, aff_e2;
+ tree type;
- e1 = strip_offset (e1, false, &off1);
- e2 = strip_offset (e2, false, &off2);
+ e1 = strip_offset (e1, &off1);
+ e2 = strip_offset (e2, &off2);
*offset += off1 - off2;
STRIP_NOPS (e1);
STRIP_NOPS (e2);
if (TREE_CODE (e1) == ADDR_EXPR)
- return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
- depends_on);
+ return ptr_difference_cost (data, e1, e2, symbol_present, var_present,
+ offset, depends_on);
*symbol_present = false;
if (operand_equal_p (e1, e2, 0))
{
*var_present = false;
- return 0;
+ return zero_cost;
}
+
*var_present = true;
- if (zero_p (e2))
+
+ if (integer_zerop (e2))
return force_var_cost (data, e1, depends_on);
- if (zero_p (e1))
+ if (integer_zerop (e1))
{
- cost = force_var_cost (data, e2, depends_on);
- cost += multiply_by_cost (-1, mode);
-
+ comp_cost cost = force_var_cost (data, e2, depends_on);
+ cost.cost += multiply_by_cost (-1, mode, data->speed);
return cost;
}
- cost = force_var_cost (data, e1, depends_on);
- cost += force_var_cost (data, e2, depends_on);
- cost += add_cost (mode);
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
- return cost;
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
+}
+
+/* Returns true if AFF1 and AFF2 are identical. */
+
+static bool
+compare_aff_trees (aff_tree *aff1, aff_tree *aff2)
+{
+ unsigned i;
+
+ if (aff1->n != aff2->n)
+ return false;
+
+ for (i = 0; i < aff1->n; i++)
+ {
+ if (double_int_cmp (aff1->elts[i].coef, aff2->elts[i].coef, 0) != 0)
+ return false;
+
+ if (!operand_equal_p (aff1->elts[i].val, aff2->elts[i].val, 0))
+ return false;
+ }
+ return true;
}
+/* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id. */
+
+static int
+get_expr_id (struct ivopts_data *data, tree expr)
+{
+ struct iv_inv_expr_ent ent;
+ struct iv_inv_expr_ent **slot;
+
+ ent.expr = expr;
+ ent.hash = iterative_hash_expr (expr, 0);
+ slot = (struct iv_inv_expr_ent **) htab_find_slot (data->inv_expr_tab,
+ &ent, INSERT);
+ if (*slot)
+ return (*slot)->id;
+
+ *slot = XNEW (struct iv_inv_expr_ent);
+ (*slot)->expr = expr;
+ (*slot)->hash = ent.hash;
+ (*slot)->id = data->inv_expr_id++;
+ return (*slot)->id;
+}
+
+/* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
+ requires a new compiler generated temporary. Returns -1 otherwise.
+ ADDRESS_P is a flag indicating if the expression is for address
+ computation. */
+
+static int
+get_loop_invariant_expr_id (struct ivopts_data *data, tree ubase,
+ tree cbase, HOST_WIDE_INT ratio,
+ bool address_p)
+{
+ aff_tree ubase_aff, cbase_aff;
+ tree expr, ub, cb;
+
+ STRIP_NOPS (ubase);
+ STRIP_NOPS (cbase);
+ ub = ubase;
+ cb = cbase;
+
+ if ((TREE_CODE (ubase) == INTEGER_CST)
+ && (TREE_CODE (cbase) == INTEGER_CST))
+ return -1;
+
+ /* Strips the constant part. */
+ if (TREE_CODE (ubase) == PLUS_EXPR
+ || TREE_CODE (ubase) == MINUS_EXPR
+ || TREE_CODE (ubase) == POINTER_PLUS_EXPR)
+ {
+ if (TREE_CODE (TREE_OPERAND (ubase, 1)) == INTEGER_CST)
+ ubase = TREE_OPERAND (ubase, 0);
+ }
+
+ /* Strips the constant part. */
+ if (TREE_CODE (cbase) == PLUS_EXPR
+ || TREE_CODE (cbase) == MINUS_EXPR
+ || TREE_CODE (cbase) == POINTER_PLUS_EXPR)
+ {
+ if (TREE_CODE (TREE_OPERAND (cbase, 1)) == INTEGER_CST)
+ cbase = TREE_OPERAND (cbase, 0);
+ }
+
+ if (address_p)
+ {
+ if (((TREE_CODE (ubase) == SSA_NAME)
+ || (TREE_CODE (ubase) == ADDR_EXPR
+ && is_gimple_min_invariant (ubase)))
+ && (TREE_CODE (cbase) == INTEGER_CST))
+ return -1;
+
+ if (((TREE_CODE (cbase) == SSA_NAME)
+ || (TREE_CODE (cbase) == ADDR_EXPR
+ && is_gimple_min_invariant (cbase)))
+ && (TREE_CODE (ubase) == INTEGER_CST))
+ return -1;
+ }
+
+ if (ratio == 1)
+ {
+ if(operand_equal_p (ubase, cbase, 0))
+ return -1;
+
+ if (TREE_CODE (ubase) == ADDR_EXPR
+ && TREE_CODE (cbase) == ADDR_EXPR)
+ {
+ tree usym, csym;
+
+ usym = TREE_OPERAND (ubase, 0);
+ csym = TREE_OPERAND (cbase, 0);
+ if (TREE_CODE (usym) == ARRAY_REF)
+ {
+ tree ind = TREE_OPERAND (usym, 1);
+ if (TREE_CODE (ind) == INTEGER_CST
+ && host_integerp (ind, 0)
+ && TREE_INT_CST_LOW (ind) == 0)
+ usym = TREE_OPERAND (usym, 0);
+ }
+ if (TREE_CODE (csym) == ARRAY_REF)
+ {
+ tree ind = TREE_OPERAND (csym, 1);
+ if (TREE_CODE (ind) == INTEGER_CST
+ && host_integerp (ind, 0)
+ && TREE_INT_CST_LOW (ind) == 0)
+ csym = TREE_OPERAND (csym, 0);
+ }
+ if (operand_equal_p (usym, csym, 0))
+ return -1;
+ }
+ /* Now do more complex comparison */
+ tree_to_aff_combination (ubase, TREE_TYPE (ubase), &ubase_aff);
+ tree_to_aff_combination (cbase, TREE_TYPE (cbase), &cbase_aff);
+ if (compare_aff_trees (&ubase_aff, &cbase_aff))
+ return -1;
+ }
+
+ tree_to_aff_combination (ub, TREE_TYPE (ub), &ubase_aff);
+ tree_to_aff_combination (cb, TREE_TYPE (cb), &cbase_aff);
+
+ aff_combination_scale (&cbase_aff, shwi_to_double_int (-1 * ratio));
+ aff_combination_add (&ubase_aff, &cbase_aff);
+ expr = aff_combination_to_tree (&ubase_aff);
+ return get_expr_id (data, expr);
+}
+
+
+
/* Determines the cost of the computation by that USE is expressed
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
register. A set of invariants we depend on is stored in
- DEPENDS_ON. AT is the statement at that the value is computed. */
+ DEPENDS_ON. AT is the statement at that the value is computed.
+ If CAN_AUTOINC is nonnull, use it to record whether autoinc
+ addressing is likely. */
-static unsigned
+static comp_cost
get_computation_cost_at (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on, tree at)
+ bool address_p, bitmap *depends_on, gimple at,
+ bool *can_autoinc,
+ int *inv_expr_id)
{
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;
+ bool var_present, symbol_present, stmt_is_after_inc;
+ comp_cost cost;
+ double_int rat;
+ bool speed = optimize_bb_for_speed_p (gimple_bb (at));
*depends_on = NULL;
/* Only consider real candidates. */
if (!cand->iv)
- return INFTY;
+ return infinite_cost;
cbase = cand->iv->base;
cstep = cand->iv->step;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
/* We do not have a precision to express the values of use. */
- return INFTY;
+ return infinite_cost;
}
- if (address_p)
+ if (address_p
+ || (use->iv->base_object
+ && cand->iv->base_object
+ && POINTER_TYPE_P (TREE_TYPE (use->iv->base_object))
+ && POINTER_TYPE_P (TREE_TYPE (cand->iv->base_object))))
{
/* Do not try to express address of an object with computation based
on address of a different object. This may cause problems in rtl
if (use->iv->base_object
&& cand->iv->base_object
&& !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
- return INFTY;
+ return infinite_cost;
}
- if (!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))
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
}
- if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
- return INFTY;
+ /* CSTEPI is removed from the offset in case statement is after the
+ increment. If the step is not constant, we use zero instead.
+ This is a bit imprecise (there is the extra addition), but
+ redundancy elimination is likely to transform the code so that
+ it uses value of the variable before increment anyway,
+ so it is not that much unrealistic. */
+ if (cst_and_fits_in_hwi (cstep))
+ cstepi = int_cst_value (cstep);
+ else
+ cstepi = 0;
+
+ if (!constant_multiple_of (ustep, cstep, &rat))
+ return infinite_cost;
+
+ if (double_int_fits_in_shwi_p (rat))
+ ratio = double_int_to_shwi (rat);
+ else
+ return infinite_cost;
+
+ STRIP_NOPS (cbase);
+ ctype = TREE_TYPE (cbase);
+
+ stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
-
+
ubase - ratio * cbase + ratio * var
-
+
(also holds in the case ratio == -1, TODO. */
- if (TREE_CODE (cbase) == INTEGER_CST)
+ if (cst_and_fits_in_hwi (cbase))
{
- offset = - ratio * int_cst_value (cbase);
- cost += difference_cost (data,
- ubase, integer_zero_node,
- &symbol_present, &var_present, &offset,
- depends_on);
+ offset = - ratio * int_cst_value (cbase);
+ cost = difference_cost (data,
+ ubase, build_int_cst (utype, 0),
+ &symbol_present, &var_present, &offset,
+ depends_on);
+ cost.cost /= avg_loop_niter (data->current_loop);
}
else if (ratio == 1)
{
- cost += difference_cost (data,
- ubase, cbase,
- &symbol_present, &var_present, &offset,
- depends_on);
+ tree real_cbase = cbase;
+
+ /* Check to see if any adjustment is needed. */
+ if (cstepi == 0 && stmt_is_after_inc)
+ {
+ aff_tree real_cbase_aff;
+ aff_tree cstep_aff;
+
+ tree_to_aff_combination (cbase, TREE_TYPE (real_cbase),
+ &real_cbase_aff);
+ tree_to_aff_combination (cstep, TREE_TYPE (cstep), &cstep_aff);
+
+ aff_combination_add (&real_cbase_aff, &cstep_aff);
+ real_cbase = aff_combination_to_tree (&real_cbase_aff);
+ }
+
+ cost = difference_cost (data,
+ ubase, real_cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
+ cost.cost /= avg_loop_niter (data->current_loop);
+ }
+ else if (address_p
+ && !POINTER_TYPE_P (ctype)
+ && multiplier_allowed_in_address_p
+ (ratio, TYPE_MODE (TREE_TYPE (utype)),
+ TYPE_ADDR_SPACE (TREE_TYPE (utype))))
+ {
+ cbase
+ = fold_build2 (MULT_EXPR, ctype, cbase, build_int_cst (ctype, ratio));
+ cost = difference_cost (data,
+ ubase, cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
+ cost.cost /= avg_loop_niter (data->current_loop);
}
else
{
- cost += force_var_cost (data, cbase, depends_on);
- cost += add_cost (TYPE_MODE (ctype));
- cost += difference_cost (data,
- ubase, integer_zero_node,
- &symbol_present, &var_present, &offset,
- depends_on);
+ cost = force_var_cost (data, cbase, depends_on);
+ cost = add_costs (cost,
+ difference_cost (data,
+ ubase, build_int_cst (utype, 0),
+ &symbol_present, &var_present,
+ &offset, depends_on));
+ cost.cost /= avg_loop_niter (data->current_loop);
+ cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
+ }
+
+ if (inv_expr_id)
+ {
+ *inv_expr_id =
+ get_loop_invariant_expr_id (data, ubase, cbase, ratio, address_p);
+ /* Clear depends on. */
+ if (*inv_expr_id != -1 && depends_on && *depends_on)
+ bitmap_clear (*depends_on);
}
/* If we are after the increment, the value of the candidate is higher by
one iteration. */
- if (stmt_after_increment (data->current_loop, cand, at))
+ if (stmt_is_after_inc)
offset -= ratio * cstepi;
/* Now the computation is in shape symbol + var1 + const + ratio * var2.
- (symbol/var/const parts may be omitted). If we are looking for an address,
- find the cost of addressing this. */
+ (symbol/var1/const parts may be omitted). If we are looking for an
+ address, find the cost of addressing this. */
if (address_p)
- return cost + get_address_cost (symbol_present, var_present, offset, ratio);
+ return add_costs (cost,
+ get_address_cost (symbol_present, var_present,
+ offset, ratio, cstepi,
+ TYPE_MODE (TREE_TYPE (utype)),
+ TYPE_ADDR_SPACE (TREE_TYPE (utype)),
+ speed, stmt_is_after_inc,
+ can_autoinc));
/* Otherwise estimate the costs for computing the expression. */
- aratio = ratio > 0 ? ratio : -ratio;
if (!symbol_present && !var_present && !offset)
{
if (ratio != 1)
- cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
-
+ cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
return cost;
}
- if (aratio != 1)
- cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
+ /* Symbol + offset should be compile-time computable so consider that they
+ are added once to the variable, if present. */
+ if (var_present && (symbol_present || offset))
+ cost.cost += adjust_setup_cost (data,
+ add_cost (TYPE_MODE (ctype), speed));
- n_sums = 1;
- if (var_present
- /* Symbol + offset should be compile-time computable. */
- && (symbol_present || offset))
- n_sums++;
+ /* Having offset does not affect runtime cost in case it is added to
+ symbol, but it increases complexity. */
+ if (offset)
+ cost.complexity++;
- return cost + n_sums * add_cost (TYPE_MODE (ctype));
+ cost.cost += add_cost (TYPE_MODE (ctype), speed);
+
+ aratio = ratio > 0 ? ratio : -ratio;
+ if (aratio != 1)
+ cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
+ return cost;
fallback:
+ if (can_autoinc)
+ *can_autoinc = false;
+
{
/* Just get the expression, expand it and measure the cost. */
tree comp = get_computation_at (data->current_loop, use, cand, at);
if (!comp)
- return INFTY;
+ return infinite_cost;
if (address_p)
- comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
+ comp = build_simple_mem_ref (comp);
- return computation_cost (comp);
+ return new_cost (computation_cost (comp, speed), 0);
}
}
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
register. A set of invariants we depend on is stored in
- DEPENDS_ON. */
+ DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
+ autoinc addressing is likely. */
-static unsigned
+static comp_cost
get_computation_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on)
+ bool address_p, bitmap *depends_on,
+ bool *can_autoinc, int *inv_expr_id)
{
return get_computation_cost_at (data,
- use, cand, address_p, depends_on, use->stmt);
+ use, cand, address_p, depends_on, use->stmt,
+ can_autoinc, inv_expr_id);
}
/* Determines cost of basing replacement of USE on CAND in a generic
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost;
+ comp_cost cost;
+ int inv_expr_id = -1;
/* The simple case first -- if we need to express value of the preserved
original biv, the cost is 0. This also prevents us from counting the
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
- set_use_iv_cost (data, use, cand, 0, NULL);
+ set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE,
+ ERROR_MARK, -1);
return true;
}
-
- cost = get_computation_cost (data, use, cand, false, &depends_on);
- set_use_iv_cost (data, use, cand, cost, depends_on);
-
- return cost != INFTY;
+
+ cost = get_computation_cost (data, use, cand, false, &depends_on,
+ NULL, &inv_expr_id);
+
+ set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE, ERROR_MARK,
+ inv_expr_id);
+
+ return !infinite_cost_p (cost);
+}
+
+/* Determines cost of basing replacement of USE on CAND in an address. */
+
+static bool
+determine_use_iv_cost_address (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand)
+{
+ bitmap depends_on;
+ bool can_autoinc;
+ int inv_expr_id = -1;
+ comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on,
+ &can_autoinc, &inv_expr_id);
+
+ if (cand->ainc_use == use)
+ {
+ if (can_autoinc)
+ cost.cost -= cand->cost_step;
+ /* If we generated the candidate solely for exploiting autoincrement
+ opportunities, and it turns out it can't be used, set the cost to
+ infinity to make sure we ignore it. */
+ else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
+ cost = infinite_cost;
+ }
+ set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE, ERROR_MARK,
+ inv_expr_id);
+
+ return !infinite_cost_p (cost);
+}
+
+/* Computes value of candidate CAND at position AT in iteration NITER, and
+ stores it to VAL. */
+
+static void
+cand_value_at (struct loop *loop, struct iv_cand *cand, gimple at, tree niter,
+ aff_tree *val)
+{
+ aff_tree step, delta, nit;
+ struct iv *iv = cand->iv;
+ tree type = TREE_TYPE (iv->base);
+ tree steptype = type;
+ if (POINTER_TYPE_P (type))
+ steptype = sizetype;
+
+ tree_to_aff_combination (iv->step, steptype, &step);
+ tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
+ aff_combination_convert (&nit, steptype);
+ aff_combination_mult (&nit, &step, &delta);
+ if (stmt_after_increment (loop, cand, at))
+ aff_combination_add (&delta, &step);
+
+ tree_to_aff_combination (iv->base, type, val);
+ aff_combination_add (val, &delta);
+}
+
+/* Returns period of induction variable iv. */
+
+static tree
+iv_period (struct iv *iv)
+{
+ tree step = iv->step, period, type;
+ tree pow2div;
+
+ gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
+
+ type = unsigned_type_for (TREE_TYPE (step));
+ /* Period of the iv is lcm (step, type_range)/step -1,
+ i.e., N*type_range/step - 1. Since type range is power
+ of two, N == (step >> num_of_ending_zeros_binary (step),
+ so the final result is
+
+ (type_range >> num_of_ending_zeros_binary (step)) - 1
+
+ */
+ pow2div = num_ending_zeros (step);
+
+ period = build_low_bits_mask (type,
+ (TYPE_PRECISION (type)
+ - tree_low_cst (pow2div, 1)));
+
+ return period;
+}
+
+/* Returns the comparison operator used when eliminating the iv USE. */
+
+static enum tree_code
+iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
+{
+ struct loop *loop = data->current_loop;
+ basic_block ex_bb;
+ edge exit;
+
+ ex_bb = gimple_bb (use->stmt);
+ exit = EDGE_SUCC (ex_bb, 0);
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ exit = EDGE_SUCC (ex_bb, 1);
+
+ return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
+}
+
+static tree
+strip_wrap_conserving_type_conversions (tree exp)
+{
+ while (tree_ssa_useless_type_conversion (exp)
+ && (nowrap_type_p (TREE_TYPE (exp))
+ == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp, 0)))))
+ exp = TREE_OPERAND (exp, 0);
+ return exp;
+}
+
+/* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
+ check for an exact match. */
+
+static bool
+expr_equal_p (tree e, tree what)
+{
+ gimple stmt;
+ enum tree_code code;
+
+ e = strip_wrap_conserving_type_conversions (e);
+ what = strip_wrap_conserving_type_conversions (what);
+
+ code = TREE_CODE (what);
+ if (TREE_TYPE (e) != TREE_TYPE (what))
+ return false;
+
+ if (operand_equal_p (e, what, 0))
+ return true;
+
+ if (TREE_CODE (e) != SSA_NAME)
+ return false;
+
+ stmt = SSA_NAME_DEF_STMT (e);
+ if (gimple_code (stmt) != GIMPLE_ASSIGN
+ || gimple_assign_rhs_code (stmt) != code)
+ return false;
+
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_BINARY_RHS:
+ if (!expr_equal_p (gimple_assign_rhs2 (stmt), TREE_OPERAND (what, 1)))
+ return false;
+ /* Fallthru. */
+
+ case GIMPLE_UNARY_RHS:
+ case GIMPLE_SINGLE_RHS:
+ return expr_equal_p (gimple_assign_rhs1 (stmt), TREE_OPERAND (what, 0));
+ default:
+ return false;
+ }
+}
+
+/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
+ we only detect the situation that BASE = SOMETHING + OFFSET, where the
+ calculation is performed in non-wrapping type.
+
+ TODO: More generally, we could test for the situation that
+ BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
+ This would require knowing the sign of OFFSET.
+
+ Also, we only look for the first addition in the computation of BASE.
+ More complex analysis would be better, but introducing it just for
+ this optimization seems like an overkill. */
+
+static bool
+difference_cannot_overflow_p (tree base, tree offset)
+{
+ enum tree_code code;
+ tree e1, e2;
+
+ if (!nowrap_type_p (TREE_TYPE (base)))
+ return false;
+
+ base = expand_simple_operations (base);
+
+ if (TREE_CODE (base) == SSA_NAME)
+ {
+ gimple stmt = SSA_NAME_DEF_STMT (base);
+
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
+ return false;
+
+ e1 = gimple_assign_rhs1 (stmt);
+ e2 = gimple_assign_rhs2 (stmt);
+ }
+ else
+ {
+ code = TREE_CODE (base);
+ if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
+ return false;
+ e1 = TREE_OPERAND (base, 0);
+ e2 = TREE_OPERAND (base, 1);
+ }
+
+ /* TODO: deeper inspection may be necessary to prove the equality. */
+ switch (code)
+ {
+ case PLUS_EXPR:
+ return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
+ case POINTER_PLUS_EXPR:
+ return expr_equal_p (e2, offset);
+
+ default:
+ return false;
+ }
}
-/* Determines cost of basing replacement of USE on CAND in an address. */
+/* Tries to replace loop exit by one formulated in terms of a LT_EXPR
+ comparison with CAND. NITER describes the number of iterations of
+ the loops. If successful, the comparison in COMP_P is altered accordingly.
-static bool
-determine_use_iv_cost_address (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
-{
- bitmap depends_on;
- unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
+ We aim to handle the following situation:
- set_use_iv_cost (data, use, cand, cost, depends_on);
+ sometype *base, *p;
+ int a, b, i;
- return cost != INFTY;
-}
+ i = a;
+ p = p_0 = base + a;
-/* Computes value of induction variable IV in iteration NITER. */
+ do
+ {
+ bla (*p);
+ p++;
+ i++;
+ }
+ while (i < b);
-static tree
-iv_value (struct iv *iv, tree niter)
-{
- tree val;
- tree type = TREE_TYPE (iv->base);
+ Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
+ We aim to optimize this to
- niter = fold_convert (type, niter);
- val = fold (build2 (MULT_EXPR, type, iv->step, niter));
+ p = p_0 = base + a;
+ do
+ {
+ bla (*p);
+ p++;
+ }
+ while (p < p_0 - a + b);
- return fold (build2 (PLUS_EXPR, type, iv->base, val));
-}
+ This preserves the correctness, since the pointer arithmetics does not
+ overflow. More precisely:
-/* Computes value of candidate CAND at position AT in iteration NITER. */
+ 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
+ overflow in computing it or the values of p.
+ 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
+ overflow. To prove this, we use the fact that p_0 = base + a. */
-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);
+static bool
+iv_elimination_compare_lt (struct ivopts_data *data,
+ struct iv_cand *cand, enum tree_code *comp_p,
+ struct tree_niter_desc *niter)
+{
+ tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset;
+ struct affine_tree_combination nit, tmpa, tmpb;
+ enum tree_code comp;
+ HOST_WIDE_INT step;
+
+ /* We need to know that the candidate induction variable does not overflow.
+ While more complex analysis may be used to prove this, for now just
+ check that the variable appears in the original program and that it
+ is computed in a type that guarantees no overflows. */
+ cand_type = TREE_TYPE (cand->iv->base);
+ if (cand->pos != IP_ORIGINAL || !nowrap_type_p (cand_type))
+ return false;
- if (stmt_after_increment (loop, cand, at))
- val = fold (build2 (PLUS_EXPR, type, val, cand->iv->step));
+ /* Make sure that the loop iterates till the loop bound is hit, as otherwise
+ the calculation of the BOUND could overflow, making the comparison
+ invalid. */
+ if (!data->loop_single_exit_p)
+ return false;
- return val;
-}
+ /* We need to be able to decide whether candidate is increasing or decreasing
+ in order to choose the right comparison operator. */
+ if (!cst_and_fits_in_hwi (cand->iv->step))
+ return false;
+ step = int_cst_value (cand->iv->step);
-/* Returns period of induction variable iv. */
+ /* Check that the number of iterations matches the expected pattern:
+ a + 1 > b ? 0 : b - a - 1. */
+ mbz = niter->may_be_zero;
+ if (TREE_CODE (mbz) == GT_EXPR)
+ {
+ /* Handle a + 1 > b. */
+ tree op0 = TREE_OPERAND (mbz, 0);
+ if (TREE_CODE (op0) == PLUS_EXPR && integer_onep (TREE_OPERAND (op0, 1)))
+ {
+ a = TREE_OPERAND (op0, 0);
+ b = TREE_OPERAND (mbz, 1);
+ }
+ else
+ return false;
+ }
+ else if (TREE_CODE (mbz) == LT_EXPR)
+ {
+ tree op1 = TREE_OPERAND (mbz, 1);
-static tree
-iv_period (struct iv *iv)
-{
- tree step = iv->step, period, type;
- tree pow2div;
+ /* Handle b < a + 1. */
+ if (TREE_CODE (op1) == PLUS_EXPR && integer_onep (TREE_OPERAND (op1, 1)))
+ {
+ a = TREE_OPERAND (op1, 0);
+ b = TREE_OPERAND (mbz, 0);
+ }
+ else
+ return false;
+ }
+ else
+ return false;
- gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
+ /* Expected number of iterations is B - A - 1. Check that it matches
+ the actual number, i.e., that B - A - NITER = 1. */
+ tree_to_aff_combination (niter->niter, nit_type, &nit);
+ tree_to_aff_combination (fold_convert (nit_type, a), nit_type, &tmpa);
+ tree_to_aff_combination (fold_convert (nit_type, b), nit_type, &tmpb);
+ aff_combination_scale (&nit, double_int_minus_one);
+ aff_combination_scale (&tmpa, double_int_minus_one);
+ aff_combination_add (&tmpb, &tmpa);
+ aff_combination_add (&tmpb, &nit);
+ if (tmpb.n != 0 || !double_int_equal_p (tmpb.offset, double_int_one))
+ return false;
- /* Period of the iv is gcd (step, type range). Since type range is power
- of two, it suffices to determine the maximum power of two that divides
- step. */
- pow2div = num_ending_zeros (step);
- type = unsigned_type_for (TREE_TYPE (step));
+ /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
+ overflow. */
+ offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
+ cand->iv->step,
+ fold_convert (TREE_TYPE (cand->iv->step), a));
+ if (!difference_cannot_overflow_p (cand->iv->base, offset))
+ return false;
- period = build_low_bits_mask (type,
- (TYPE_PRECISION (type)
- - tree_low_cst (pow2div, 1)));
+ /* Determine the new comparison operator. */
+ comp = step < 0 ? GT_EXPR : LT_EXPR;
+ if (*comp_p == NE_EXPR)
+ *comp_p = comp;
+ else if (*comp_p == EQ_EXPR)
+ *comp_p = invert_tree_comparison (comp, false);
+ else
+ gcc_unreachable ();
- return period;
+ return true;
}
/* Check whether it is possible to express the condition in USE by comparison
- of candidate CAND. If so, store the comparison code to COMPARE and the
- value compared with to BOUND. */
+ of candidate CAND. If so, store the value compared with to BOUND, and the
+ comparison operator to COMP. */
static bool
may_eliminate_iv (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand,
- enum tree_code *compare, tree *bound)
+ struct iv_use *use, struct iv_cand *cand, tree *bound,
+ enum tree_code *comp)
{
basic_block ex_bb;
edge exit;
- struct tree_niter_desc *niter;
- tree nit, nit_type;
- tree wider_type, period, per_type;
+ tree period;
struct loop *loop = data->current_loop;
-
- /* 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 (use->stmt != last_stmt (ex_bb)
- || TREE_CODE (use->stmt) != COND_EXPR)
+ aff_tree bnd;
+ struct tree_niter_desc *desc = NULL;
+
+ if (TREE_CODE (cand->iv->step) != INTEGER_CST)
return false;
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
+
+ /* For now works only for exits that dominate the loop latch.
+ TODO: extend to other conditions inside loop body. */
+ ex_bb = gimple_bb (use->stmt);
+ if (use->stmt != last_stmt (ex_bb)
+ || gimple_code (use->stmt) != GIMPLE_COND
+ || !dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
return false;
exit = EDGE_SUCC (ex_bb, 0);
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))
+ desc = niter_for_exit (data, exit);
+ if (!desc)
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. */
+ /* Determine whether we can use the variable to test the exit condition.
+ This is the case iff the period of the induction variable is greater
+ than the number of iterations for which the exit condition is true. */
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;
+ /* If the number of iterations is constant, compare against it directly. */
+ if (TREE_CODE (desc->niter) == INTEGER_CST)
+ {
+ /* See cand_value_at. */
+ if (stmt_after_increment (loop, cand, use->stmt))
+ {
+ if (!tree_int_cst_lt (desc->niter, period))
+ return false;
+ }
+ else
+ {
+ if (tree_int_cst_lt (period, desc->niter))
+ return false;
+ }
+ }
+
+ /* If not, and if this is the only possible exit of the loop, see whether
+ we can get a conservative estimate on the number of iterations of the
+ entire loop and compare against that instead. */
else
- wider_type = nit_type;
+ {
+ double_int period_value, max_niter;
- if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
- fold_convert (wider_type, period),
- fold_convert (wider_type, nit)))))
+ max_niter = desc->max;
+ if (stmt_after_increment (loop, cand, use->stmt))
+ max_niter = double_int_add (max_niter, double_int_one);
+ period_value = tree_to_double_int (period);
+ if (double_int_ucmp (max_niter, period_value) > 0)
+ {
+ /* See if we can take advantage of infered loop bound information. */
+ if (data->loop_single_exit_p)
+ {
+ if (!estimated_loop_iterations (loop, true, &max_niter))
+ return false;
+ /* The loop bound is already adjusted by adding 1. */
+ if (double_int_ucmp (max_niter, period_value) > 0)
+ return false;
+ }
+ else
+ return false;
+ }
+ }
+
+ cand_value_at (loop, cand, use->stmt, desc->niter, &bnd);
+
+ *bound = aff_combination_to_tree (&bnd);
+ *comp = iv_elimination_compare (data, use);
+
+ /* It is unlikely that computing the number of iterations using division
+ would be more profitable than keeping the original induction variable. */
+ if (expression_expensive_p (*bound))
return false;
- if (exit->flags & EDGE_TRUE_VALUE)
- *compare = EQ_EXPR;
- else
- *compare = NE_EXPR;
+ /* Sometimes, it is possible to handle the situation that the number of
+ iterations may be zero unless additional assumtions by using <
+ instead of != in the exit condition.
+
+ TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
+ base the exit condition on it. However, that is often too
+ expensive. */
+ if (!integer_zerop (desc->may_be_zero))
+ return iv_elimination_compare_lt (data, cand, comp, desc);
- *bound = cand_value_at (loop, cand, use->stmt, nit);
return true;
}
+ /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
+ be copied, if is is used in the loop body and DATA->body_includes_call. */
+
+static int
+parm_decl_cost (struct ivopts_data *data, tree bound)
+{
+ tree sbound = bound;
+ STRIP_NOPS (sbound);
+
+ if (TREE_CODE (sbound) == SSA_NAME
+ && TREE_CODE (SSA_NAME_VAR (sbound)) == PARM_DECL
+ && gimple_nop_p (SSA_NAME_DEF_STMT (sbound))
+ && data->body_includes_call)
+ return COSTS_N_INSNS (1);
+
+ return 0;
+}
+
/* 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;
- enum tree_code compare;
+ tree bound = NULL_TREE;
+ struct iv *cmp_iv;
+ bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
+ comp_cost elim_cost, express_cost, cost, bound_cost;
+ bool ok;
+ int elim_inv_expr_id = -1, express_inv_expr_id = -1, inv_expr_id;
+ tree *control_var, *bound_cst;
+ enum tree_code comp = ERROR_MARK;
/* Only consider real candidates. */
if (!cand->iv)
{
- set_use_iv_cost (data, use, cand, INFTY, NULL);
+ set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE,
+ ERROR_MARK, -1);
return false;
}
- if (may_eliminate_iv (data, use, cand, &compare, &bound))
- {
- bitmap depends_on = NULL;
- unsigned cost = force_var_cost (data, bound, &depends_on);
-
- set_use_iv_cost (data, use, cand, cost, depends_on);
- return cost != INFTY;
+ /* Try iv elimination. */
+ if (may_eliminate_iv (data, use, cand, &bound, &comp))
+ {
+ elim_cost = force_var_cost (data, bound, &depends_on_elim);
+ if (elim_cost.cost == 0)
+ elim_cost.cost = parm_decl_cost (data, bound);
+ else if (TREE_CODE (bound) == INTEGER_CST)
+ elim_cost.cost = 0;
+ /* If we replace a loop condition 'i < n' with 'p < base + n',
+ depends_on_elim will have 'base' and 'n' set, which implies
+ that both 'base' and 'n' will be live during the loop. More likely,
+ 'base + n' will be loop invariant, resulting in only one live value
+ during the loop. So in that case we clear depends_on_elim and set
+ elim_inv_expr_id instead. */
+ if (depends_on_elim && bitmap_count_bits (depends_on_elim) > 1)
+ {
+ elim_inv_expr_id = get_expr_id (data, bound);
+ bitmap_clear (depends_on_elim);
+ }
+ /* The bound is a loop invariant, so it will be only computed
+ once. */
+ elim_cost.cost = adjust_setup_cost (data, elim_cost.cost);
+ }
+ else
+ elim_cost = infinite_cost;
+
+ /* Try expressing the original giv. If it is compared with an invariant,
+ note that we cannot get rid of it. */
+ ok = extract_cond_operands (data, use->stmt, &control_var, &bound_cst,
+ NULL, &cmp_iv);
+ gcc_assert (ok);
+
+ /* When the condition is a comparison of the candidate IV against
+ zero, prefer this IV.
+
+ TODO: The constant that we're substracting from the cost should
+ be target-dependent. This information should be added to the
+ target costs for each backend. */
+ if (!infinite_cost_p (elim_cost) /* Do not try to decrease infinite! */
+ && integer_zerop (*bound_cst)
+ && (operand_equal_p (*control_var, cand->var_after, 0)
+ || operand_equal_p (*control_var, cand->var_before, 0)))
+ elim_cost.cost -= 1;
+
+ express_cost = get_computation_cost (data, use, cand, false,
+ &depends_on_express, NULL,
+ &express_inv_expr_id);
+ fd_ivopts_data = data;
+ walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
+
+ /* Count the cost of the original bound as well. */
+ bound_cost = force_var_cost (data, *bound_cst, NULL);
+ if (bound_cost.cost == 0)
+ bound_cost.cost = parm_decl_cost (data, *bound_cst);
+ else if (TREE_CODE (*bound_cst) == INTEGER_CST)
+ bound_cost.cost = 0;
+ express_cost.cost += bound_cost.cost;
+
+ /* Choose the better approach, preferring the eliminated IV. */
+ if (compare_costs (elim_cost, express_cost) <= 0)
+ {
+ cost = elim_cost;
+ depends_on = depends_on_elim;
+ depends_on_elim = NULL;
+ inv_expr_id = elim_inv_expr_id;
}
-
- /* The induction variable elimination failed; just express the original
- giv. If it is compared with an invariant, note that we cannot get
- rid of it. */
- if (TREE_CODE (*use->op_p) == SSA_NAME)
- record_invariant (data, *use->op_p, true);
else
{
- record_invariant (data, TREE_OPERAND (*use->op_p, 0), true);
- record_invariant (data, TREE_OPERAND (*use->op_p, 1), true);
+ cost = express_cost;
+ depends_on = depends_on_express;
+ depends_on_express = NULL;
+ bound = NULL_TREE;
+ comp = ERROR_MARK;
+ inv_expr_id = express_inv_expr_id;
}
- return determine_use_iv_cost_generic (data, use, cand);
+ set_use_iv_cost (data, use, cand, cost, depends_on, bound, comp, inv_expr_id);
+
+ if (depends_on_elim)
+ BITMAP_FREE (depends_on_elim);
+ if (depends_on_express)
+ BITMAP_FREE (depends_on_express);
+
+ return !infinite_cost_p (cost);
}
-/* Checks whether it is possible to replace the final value of USE by
- a direct computation. If so, the formula is stored to *VALUE. */
+/* Determines cost of basing replacement of USE on CAND. Returns false
+ if USE cannot be based on CAND. */
static bool
-may_replace_final_value (struct ivopts_data *data, struct iv_use *use,
- tree *value)
+determine_use_iv_cost (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand)
{
- struct loop *loop = data->current_loop;
- edge exit;
- struct tree_niter_desc *niter;
-
- exit = single_dom_exit (loop);
- if (!exit)
- return false;
-
- gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
- bb_for_stmt (use->stmt)));
+ switch (use->type)
+ {
+ case USE_NONLINEAR_EXPR:
+ return determine_use_iv_cost_generic (data, use, cand);
- niter = niter_for_single_dom_exit (data);
- if (!niter
- || !zero_p (niter->may_be_zero))
- return false;
+ case USE_ADDRESS:
+ return determine_use_iv_cost_address (data, use, cand);
- *value = iv_value (use->iv, niter->niter);
+ case USE_COMPARE:
+ return determine_use_iv_cost_condition (data, use, cand);
- return true;
+ default:
+ gcc_unreachable ();
+ }
}
-/* Determines cost of replacing final value of USE using CAND. */
+/* Return true if get_computation_cost indicates that autoincrement is
+ a possibility for the pair of USE and CAND, false otherwise. */
static bool
-determine_use_iv_cost_outer (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use,
+ struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost;
- edge exit;
- tree value;
- struct loop *loop = data->current_loop;
+ bool can_autoinc;
+ comp_cost cost;
- /* The simple case first -- if we need to express value of the preserved
- original biv, the cost is 0. This also prevents us from counting the
- 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);
- return true;
- }
+ if (use->type != USE_ADDRESS)
+ return false;
- if (!cand->iv)
- {
- if (!may_replace_final_value (data, use, &value))
- {
- set_use_iv_cost (data, use, cand, INFTY, NULL);
- return false;
- }
+ cost = get_computation_cost (data, use, cand, true, &depends_on,
+ &can_autoinc, NULL);
- depends_on = NULL;
- cost = force_var_cost (data, value, &depends_on);
+ BITMAP_FREE (depends_on);
- cost /= AVG_LOOP_NITER (loop);
+ return !infinite_cost_p (cost) && can_autoinc;
+}
- set_use_iv_cost (data, use, cand, cost, depends_on);
- return cost != INFTY;
- }
+/* Examine IP_ORIGINAL candidates to see if they are incremented next to a
+ use that allows autoincrement, and set their AINC_USE if possible. */
- exit = single_dom_exit (loop);
- if (exit)
- {
- /* 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);
- }
- else
+static void
+set_autoinc_for_original_candidates (struct ivopts_data *data)
+{
+ unsigned i, j;
+
+ for (i = 0; i < n_iv_cands (data); i++)
{
- /* Otherwise we just need to compute the iv. */
- cost = get_computation_cost (data, use, cand, false, &depends_on);
+ struct iv_cand *cand = iv_cand (data, i);
+ struct iv_use *closest = NULL;
+ if (cand->pos != IP_ORIGINAL)
+ continue;
+ for (j = 0; j < n_iv_uses (data); j++)
+ {
+ struct iv_use *use = iv_use (data, j);
+ unsigned uid = gimple_uid (use->stmt);
+ if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at)
+ || uid > gimple_uid (cand->incremented_at))
+ continue;
+ if (closest == NULL || uid > gimple_uid (closest->stmt))
+ closest = use;
+ }
+ if (closest == NULL || !autoinc_possible_for_pair (data, closest, cand))
+ continue;
+ cand->ainc_use = closest;
}
-
- set_use_iv_cost (data, use, cand, cost, depends_on);
-
- return cost != INFTY;
}
-/* Determines cost of basing replacement of USE on CAND. Returns false
- if USE cannot be based on CAND. */
+/* Finds the candidates for the induction variables. */
-static bool
-determine_use_iv_cost (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+static void
+find_iv_candidates (struct ivopts_data *data)
{
- switch (use->type)
- {
- case USE_NONLINEAR_EXPR:
- return determine_use_iv_cost_generic (data, use, cand);
+ /* Add commonly used ivs. */
+ add_standard_iv_candidates (data);
- case USE_OUTER:
- return determine_use_iv_cost_outer (data, use, cand);
+ /* Add old induction variables. */
+ add_old_ivs_candidates (data);
- case USE_ADDRESS:
- return determine_use_iv_cost_address (data, use, cand);
+ /* Add induction variables derived from uses. */
+ add_derived_ivs_candidates (data);
- case USE_COMPARE:
- return determine_use_iv_cost_condition (data, use, cand);
+ set_autoinc_for_original_candidates (data);
- default:
- gcc_unreachable ();
- }
+ /* Record the important candidates. */
+ record_important_candidates (data);
}
/* Determines costs of basing the use of the iv on an iv candidate. */
use = iv_use (data, i);
fprintf (dump_file, "Use %d:\n", i);
- fprintf (dump_file, " cand\tcost\tdepends on\n");
+ fprintf (dump_file, " cand\tcost\tcompl.\tdepends on\n");
for (j = 0; j < use->n_map_members; j++)
{
if (!use->cost_map[j].cand
- || use->cost_map[j].cost == INFTY)
+ || infinite_cost_p (use->cost_map[j].cost))
continue;
- fprintf (dump_file, " %d\t%d\t",
+ fprintf (dump_file, " %d\t%d\t%d\t",
use->cost_map[j].cand->id,
- use->cost_map[j].cost);
+ use->cost_map[j].cost.cost,
+ use->cost_map[j].cost.complexity);
if (use->cost_map[j].depends_on)
bitmap_print (dump_file,
use->cost_map[j].depends_on, "","");
+ if (use->cost_map[j].inv_expr_id != -1)
+ fprintf (dump_file, " inv_expr:%d", use->cost_map[j].inv_expr_id);
fprintf (dump_file, "\n");
}
static void
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
- unsigned cost_base, cost_step;
+ comp_cost cost_base;
+ unsigned cost, cost_step;
tree base;
if (!cand->iv)
base = cand->iv->base;
cost_base = force_var_cost (data, base, NULL);
- cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
+ /* It will be exceptional that the iv register happens to be initialized with
+ the proper value at no cost. In general, there will at least be a regcopy
+ or a const set. */
+ if (cost_base.cost == 0)
+ cost_base.cost = COSTS_N_INSNS (1);
+ cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
+
+ cost = cost_step + adjust_setup_cost (data, cost_base.cost);
+
+ /* Prefer the original ivs unless we may gain something by replacing it.
+ The reason is to make debugging simpler; so this is not relevant for
+ artificial ivs created by other optimization passes. */
+ if (cand->pos != IP_ORIGINAL
+ || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
+ cost++;
- cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
-
- /* Prefer the original iv unless we may gain something by replacing it;
- this is not really relevant for artificial ivs created by other
- passes. */
- if (cand->pos == IP_ORIGINAL
- && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
- cand->cost--;
-
/* Prefer not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
if (cand->pos == IP_END
&& empty_block_p (ip_end_pos (data->current_loop)))
- cand->cost++;
+ cost++;
+
+ cand->cost = cost;
+ cand->cost_step = cost_step;
}
/* Determines costs of computation of the candidates. */
if (dump_file && (dump_flags & TDF_DETAILS))
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, data->speed,
+ data->body_includes_call);
}
/* For each size of the induction variable set determine the penalty. */
determine_set_costs (struct ivopts_data *data)
{
unsigned j, n;
- tree phi, op;
+ gimple phi;
+ gimple_stmt_iterator psi;
+ tree op;
struct loop *loop = data->current_loop;
bitmap_iterator bi;
- /* We use the following model (definitely improvable, especially the
- cost function -- TODO):
-
- We estimate the number of registers available (using MD data), name it A.
-
- We estimate the number of registers used by the loop, name it U. This
- number is obtained as the number of loop phi nodes (not counting virtual
- registers and bivs) + the number of variables from outside of the loop.
-
- We set a reserve R (free regs that are used for temporary computations,
- etc.). For now the reserve is a constant 3.
-
- Let I be the number of induction variables.
-
- -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
- make a lot of ivs without a reason).
- -- if A - R < U + I <= A, the cost is I * PRES_COST
- -- if U + I > A, the cost is I * PRES_COST and
- number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
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_spill_cost %d\n", target_spill_cost);
+ fprintf (dump_file, " target_clobbered_regs %d\n", target_clobbered_regs);
+ fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost[data->speed]);
+ fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost[data->speed]);
}
n = 0;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
op = PHI_RESULT (phi);
if (!is_gimple_reg (op))
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);
static bool
cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
{
+ int cmp;
+
if (!a)
return false;
if (!b)
return true;
- if (a->cost < b->cost)
+ cmp = compare_costs (a->cost, b->cost);
+ if (cmp < 0)
return true;
- if (a->cost > b->cost)
+ if (cmp > 0)
return false;
/* In case the costs are the same, prefer the cheaper candidate. */
return false;
}
+
+/* Returns candidate by that USE is expressed in IVS. */
+
+static struct cost_pair *
+iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
+{
+ return ivs->cand_for_use[use->id];
+}
+
/* Computes the cost field of IVS structure. */
static void
iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned cost = 0;
+ comp_cost cost = ivs->cand_use_cost;
+
+ cost.cost += ivs->cand_cost;
- cost += ivs->cand_use_cost;
- cost += ivs->cand_cost;
- cost += ivopts_global_cost_for_size (data, ivs->n_regs);
+ cost.cost += ivopts_global_cost_for_size (data,
+ ivs->n_regs + ivs->num_used_inv_expr);
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;
+ ivs->cand_use_cost = sub_costs (ivs->cand_use_cost, cp->cost);
- deps = cp->depends_on;
+ iv_ca_set_remove_invariants (ivs, cp->depends_on);
- if (deps)
+ if (cp->inv_expr_id != -1)
{
- 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->used_inv_expr[cp->inv_expr_id]--;
+ if (ivs->used_inv_expr[cp->inv_expr_id] == 0)
+ ivs->num_used_inv_expr--;
}
-
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;
+
+ EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
+ {
+ ivs->n_invariant_uses[iid]++;
+ if (ivs->n_invariant_uses[iid] == 1)
+ ivs->n_regs++;
+ }
+}
+
/* Set cost pair for USE in set IVS to CP. */
static void
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 = add_costs (ivs->cand_use_cost, cp->cost);
+ iv_ca_set_add_invariants (ivs, cp->depends_on);
+
+ if (cp->inv_expr_id != -1)
+ {
+ ivs->used_inv_expr[cp->inv_expr_id]++;
+ if (ivs->used_inv_expr[cp->inv_expr_id] == 1)
+ ivs->num_used_inv_expr++;
+ }
iv_ca_recount_cost (data, ivs);
}
}
/* Extend set IVS by expressing USE by some of the candidates in it
- if possible. */
+ if possible. All important candidates will be considered
+ if IMPORTANT_CANDIDATES is true. */
static void
iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_use *use)
+ struct iv_use *use, bool important_candidates)
{
struct cost_pair *best_cp = NULL, *cp;
bitmap_iterator bi;
+ bitmap cands;
unsigned i;
gcc_assert (ivs->upto >= use->id);
ivs->bad_uses++;
}
- EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+ cands = (important_candidates ? data->important_candidates : ivs->cands);
+ EXECUTE_IF_SET_IN_BITMAP (cands, 0, i, bi)
{
- cp = get_use_iv_cost (data, use, iv_cand (data, i));
+ struct iv_cand *cand = iv_cand (data, i);
+
+ cp = get_use_iv_cost (data, use, cand);
if (cheaper_cost_pair (cp, best_cp))
best_cp = cp;
/* Get cost for assignment IVS. */
-static unsigned
+static comp_cost
iv_ca_cost (struct iv_ca *ivs)
{
- return (ivs->bad_uses ? INFTY : ivs->cost);
+ /* This was a conditional expression but it triggered a bug in
+ Sun C 5.5. */
+ if (ivs->bad_uses)
+ return infinite_cost;
+ else
+ return ivs->cost;
}
/* Returns true if all dependences of CP are among invariants in IVS. */
iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
struct cost_pair *new_cp, struct iv_ca_delta *next_change)
{
- struct iv_ca_delta *change = xmalloc (sizeof (struct iv_ca_delta));
+ struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
change->use = use;
change->old_cp = old_cp;
return l1;
}
-/* Returns candidate by that USE is expressed in IVS. */
-
-static struct cost_pair *
-iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
-{
- return ivs->cand_for_use[use->id];
-}
-
/* Reverse the list of changes DELTA, forming the inverse to it. */
static struct iv_ca_delta *
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_use_cost = zero_cost;
nw->cand_cost = 0;
- nw->n_invariant_uses = xcalloc (data->max_inv_id + 1, sizeof (unsigned));
- nw->cost = 0;
+ nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
+ nw->cost = zero_cost;
+ nw->used_inv_expr = XCNEWVEC (unsigned, data->inv_expr_id + 1);
+ nw->num_used_inv_expr = 0;
return nw;
}
free ((*ivs)->n_cand_uses);
BITMAP_FREE ((*ivs)->cands);
free ((*ivs)->n_invariant_uses);
+ free ((*ivs)->used_inv_expr);
free (*ivs);
*ivs = NULL;
}
{
const char *pref = " invariants ";
unsigned i;
+ comp_cost cost = iv_ca_cost (ivs);
+
+ fprintf (file, " cost: %d (complexity %d)\n", cost.cost, cost.complexity);
+ fprintf (file, " cand_cost: %d\n cand_use_cost: %d (complexity %d)\n",
+ ivs->cand_cost, ivs->cand_use_cost.cost, ivs->cand_use_cost.complexity);
+ bitmap_print (file, ivs->cands, " candidates: ","\n");
- fprintf (file, " cost %d\n", iv_ca_cost (ivs));
- bitmap_print (file, ivs->cands, " candidates ","\n");
+ for (i = 0; i < ivs->upto; i++)
+ {
+ struct iv_use *use = iv_use (data, i);
+ struct cost_pair *cp = iv_ca_cand_for_use (ivs, use);
+ if (cp)
+ fprintf (file, " use:%d --> iv_cand:%d, cost=(%d,%d)\n",
+ use->id, cp->cand->id, cp->cost.cost, cp->cost.complexity);
+ else
+ fprintf (file, " use:%d --> ??\n", use->id);
+ }
for (i = 1; i <= data->max_inv_id; i++)
if (ivs->n_invariant_uses[i])
fprintf (file, "%s%d", pref, i);
pref = ", ";
}
- fprintf (file, "\n");
+ fprintf (file, "\n\n");
}
/* Try changing candidate in IVS to CAND for each use. Return cost of the
new set, and store differences in DELTA. Number of induction variables
- in the new set is stored to N_IVS. */
+ in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
+ the function will try to find a solution with mimimal iv candidates. */
-static unsigned
+static comp_cost
iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta,
- unsigned *n_ivs)
+ unsigned *n_ivs, bool min_ncand)
{
- unsigned i, cost;
+ unsigned i;
+ comp_cost cost;
struct iv_use *use;
struct cost_pair *old_cp, *new_cp;
if (!new_cp)
continue;
- if (!iv_ca_has_deps (ivs, new_cp))
- continue;
-
- if (!cheaper_cost_pair (new_cp, old_cp))
+ if (!min_ncand && !iv_ca_has_deps (ivs, new_cp))
continue;
+ if (!min_ncand && !cheaper_cost_pair (new_cp, old_cp))
+ continue;
+
*delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
}
/* Try narrowing set IVS by removing CAND. Return the cost of
the new set and store the differences in DELTA. */
-static unsigned
+static comp_cost
iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta)
{
struct cost_pair *old_cp, *new_cp, *cp;
bitmap_iterator bi;
struct iv_cand *cnd;
- unsigned cost;
+ comp_cost cost;
*delta = NULL;
for (i = 0; i < n_iv_uses (data); i++)
cp = get_use_iv_cost (data, use, cnd);
if (!cp)
continue;
+
if (!iv_ca_has_deps (ivs, cp))
- continue;
-
+ continue;
+
if (!cheaper_cost_pair (cp, new_cp))
continue;
continue;
if (!iv_ca_has_deps (ivs, cp))
continue;
-
+
if (!cheaper_cost_pair (cp, new_cp))
continue;
if (!new_cp)
{
iv_ca_delta_free (delta);
- return INFTY;
+ return infinite_cost;
}
*delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
from to EXCEPT_CAND from it. Return cost of the new set, and store
differences in DELTA. */
-static unsigned
+static comp_cost
iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *except_cand, struct iv_ca_delta **delta)
{
bitmap_iterator bi;
struct iv_ca_delta *act_delta, *best_delta;
- unsigned i, best_cost, acost;
+ unsigned i;
+ comp_cost best_cost, acost;
struct iv_cand *cand;
best_delta = NULL;
acost = iv_ca_narrow (data, ivs, cand, &act_delta);
- if (acost < best_cost)
+ if (compare_costs (acost, best_cost) < 0)
{
best_cost = acost;
iv_ca_delta_free (&best_delta);
}
/* Tries to extend the sets IVS in the best possible way in order
- to express the USE. */
+ to express the USE. If ORIGINALP is true, prefer candidates from
+ the original set of IVs, otherwise favor important candidates not
+ based on any memory object. */
static bool
try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_use *use)
+ struct iv_use *use, bool originalp)
{
- unsigned best_cost, act_cost;
+ comp_cost best_cost, act_cost;
unsigned i;
bitmap_iterator bi;
struct iv_cand *cand;
struct iv_ca_delta *best_delta = NULL, *act_delta;
struct cost_pair *cp;
- iv_ca_add_use (data, ivs, use);
+ iv_ca_add_use (data, ivs, use, false);
best_cost = iv_ca_cost (ivs);
cp = iv_ca_cand_for_use (ivs, use);
+ if (!cp)
+ {
+ ivs->upto--;
+ ivs->bad_uses--;
+ iv_ca_add_use (data, ivs, use, true);
+ best_cost = iv_ca_cost (ivs);
+ cp = iv_ca_cand_for_use (ivs, use);
+ }
if (cp)
{
best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
iv_ca_set_no_cp (data, ivs, use);
}
- /* First try important candidates. Only if it fails, try the specific ones.
- Rationale -- in loops with many variables the best choice often is to use
- just one generic biv. If we added here many ivs specific to the uses,
- the optimization algorithm later would be likely to get stuck in a local
- minimum, thus causing us to create too many ivs. The approach from
- few ivs to more seems more likely to be successful -- starting from few
- ivs, replacing an expensive use by a specific iv should always be a
- win. */
+ /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
+ first try important candidates not based on any memory object. Only if
+ this fails, try the specific ones. Rationale -- in loops with many
+ variables the best choice often is to use just one generic biv. If we
+ added here many ivs specific to the uses, the optimization algorithm later
+ would be likely to get stuck in a local minimum, thus causing us to create
+ too many ivs. The approach from few ivs to more seems more likely to be
+ successful -- starting from few ivs, replacing an expensive use by a
+ specific iv should always be a win. */
EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
{
cand = iv_cand (data, i);
- if (iv_ca_cand_used_p (ivs, cand))
+ if (originalp && cand->pos !=IP_ORIGINAL)
+ continue;
+
+ if (!originalp && cand->iv->base_object != NULL_TREE)
continue;
+ if (iv_ca_cand_used_p (ivs, cand))
+ continue;
+
cp = get_use_iv_cost (data, use, cand);
if (!cp)
continue;
iv_ca_set_cp (data, ivs, use, cp);
- act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
+ act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL,
+ true);
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
- if (act_cost < best_cost)
+ if (compare_costs (act_cost, best_cost) < 0)
{
best_cost = act_cost;
iv_ca_delta_free (&act_delta);
}
- if (best_cost == INFTY)
+ if (infinite_cost_p (best_cost))
{
for (i = 0; i < use->n_map_members; i++)
{
/* Already tried this. */
if (cand->important)
- continue;
-
+ {
+ if (originalp && cand->pos == IP_ORIGINAL)
+ continue;
+ if (!originalp && cand->iv->base_object == NULL_TREE)
+ continue;
+ }
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
act_delta = NULL;
iv_ca_set_cp (data, ivs, use, cp);
- act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
+ act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL, true);
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
cp, act_delta);
- if (act_cost < best_cost)
+ if (compare_costs (act_cost, best_cost) < 0)
{
best_cost = act_cost;
iv_ca_delta_commit (data, ivs, best_delta, true);
iv_ca_delta_free (&best_delta);
- return (best_cost != INFTY);
+ return !infinite_cost_p (best_cost);
}
/* Finds an initial assignment of candidates to uses. */
static struct iv_ca *
-get_initial_solution (struct ivopts_data *data)
+get_initial_solution (struct ivopts_data *data, bool originalp)
{
struct iv_ca *ivs = iv_ca_new (data);
unsigned i;
for (i = 0; i < n_iv_uses (data); i++)
- if (!try_add_cand_for (data, ivs, iv_use (data, i)))
+ if (!try_add_cand_for (data, ivs, iv_use (data, i), originalp))
{
iv_ca_free (&ivs);
return NULL;
static bool
try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
+ unsigned i, n_ivs;
+ comp_cost acost, best_cost = iv_ca_cost (ivs);
struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
struct iv_cand *cand;
for (i = 0; i < n_iv_cands (data); i++)
{
cand = iv_cand (data, i);
-
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
- acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
+ acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs, false);
if (!act_delta)
continue;
act_delta = iv_ca_delta_join (act_delta, tmp_delta);
}
- if (acost < best_cost)
+ if (compare_costs (acost, best_cost) < 0)
{
best_cost = acost;
iv_ca_delta_free (&best_delta);
}
iv_ca_delta_commit (data, ivs, best_delta, true);
- gcc_assert (best_cost == iv_ca_cost (ivs));
+ gcc_assert (compare_costs (best_cost, iv_ca_cost (ivs)) == 0);
iv_ca_delta_free (&best_delta);
return true;
}
solution and remove the unused ivs while this improves the cost. */
static struct iv_ca *
-find_optimal_iv_set (struct ivopts_data *data)
+find_optimal_iv_set_1 (struct ivopts_data *data, bool originalp)
{
- unsigned i;
struct iv_ca *set;
- struct iv_use *use;
/* Get the initial solution. */
- set = get_initial_solution (data);
+ set = get_initial_solution (data, originalp);
if (!set)
{
if (dump_file && (dump_flags & TDF_DETAILS))
}
}
+ return set;
+}
+
+static struct iv_ca *
+find_optimal_iv_set (struct ivopts_data *data)
+{
+ unsigned i;
+ struct iv_ca *set, *origset;
+ struct iv_use *use;
+ comp_cost cost, origcost;
+
+ /* Determine the cost based on a strategy that starts with original IVs,
+ and try again using a strategy that prefers candidates not based
+ on any IVs. */
+ origset = find_optimal_iv_set_1 (data, true);
+ set = find_optimal_iv_set_1 (data, false);
+
+ if (!origset && !set)
+ return NULL;
+
+ origcost = origset ? iv_ca_cost (origset) : infinite_cost;
+ cost = set ? iv_ca_cost (set) : infinite_cost;
+
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
+ {
+ fprintf (dump_file, "Original cost %d (complexity %d)\n\n",
+ origcost.cost, origcost.complexity);
+ fprintf (dump_file, "Final cost %d (complexity %d)\n\n",
+ cost.cost, cost.complexity);
+ }
+
+ /* Choose the one with the best cost. */
+ if (compare_costs (origcost, cost) <= 0)
+ {
+ if (set)
+ iv_ca_free (&set);
+ set = origset;
+ }
+ else if (origset)
+ iv_ca_free (&origset);
for (i = 0; i < n_iv_uses (data); i++)
{
static void
create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
{
- block_stmt_iterator incr_pos;
+ gimple_stmt_iterator incr_pos;
tree base;
bool after = false;
switch (cand->pos)
{
case IP_NORMAL:
- incr_pos = bsi_last (ip_normal_pos (data->current_loop));
+ incr_pos = gsi_last_bb (ip_normal_pos (data->current_loop));
break;
case IP_END:
- incr_pos = bsi_last (ip_end_pos (data->current_loop));
+ incr_pos = gsi_last_bb (ip_end_pos (data->current_loop));
+ after = true;
+ break;
+
+ case IP_AFTER_USE:
after = true;
+ /* fall through */
+ case IP_BEFORE_USE:
+ incr_pos = gsi_for_stmt (cand->incremented_at);
break;
case IP_ORIGINAL:
/* Rewrite the increment so that it uses var_before directly. */
find_interesting_uses_op (data, cand->var_after)->selected = cand;
-
return;
}
-
+
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);
}
cand = iv_cand (data, i);
create_new_iv (data, cand);
}
-}
-/* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
- is true, remove also the ssa name defined by the statement. */
-
-static void
-remove_statement (tree stmt, bool including_defined_name)
-{
- 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);
- }
- else
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- block_stmt_iterator bsi = bsi_for_stmt (stmt);
-
- bsi_remove (&bsi);
+ fprintf (dump_file, "\nSelected IV set: \n");
+ EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
+ {
+ cand = iv_cand (data, i);
+ dump_cand (dump_file, cand);
+ }
+ fprintf (dump_file, "\n");
}
}
struct iv_use *use, struct iv_cand *cand)
{
tree comp;
- tree op, stmts, tgt, ass;
- block_stmt_iterator bsi, pbsi;
+ tree op, tgt;
+ gimple ass;
+ gimple_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)
+ {
+ enum tree_code stmt_code;
+
+ gcc_assert (is_gimple_assign (use->stmt));
+ gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
+
+ /* 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. */
+ stmt_code = gimple_assign_rhs_code (use->stmt);
+ if (stmt_code == PLUS_EXPR
+ || stmt_code == MINUS_EXPR
+ || stmt_code == POINTER_PLUS_EXPR)
+ {
+ if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs2 (use->stmt);
+ else if (gimple_assign_rhs2 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs1 (use->stmt);
+ else
+ op = NULL_TREE;
+ }
+ else
+ op = NULL_TREE;
+
+ if (op && expr_invariant_in_loop_p (data->current_loop, op))
return;
}
- comp = unshare_expr (get_computation (data->current_loop,
- use, cand));
- switch (TREE_CODE (use->stmt))
+ comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
+
+ switch (gimple_code (use->stmt))
{
- case PHI_NODE:
+ case GIMPLE_PHI:
tgt = PHI_RESULT (use->stmt);
/* If we should keep the biv, do not replace it. */
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 = gsi_after_labels (gimple_bb (use->stmt));
break;
- case MODIFY_EXPR:
- tgt = TREE_OPERAND (use->stmt, 0);
- bsi = bsi_for_stmt (use->stmt);
+ case GIMPLE_ASSIGN:
+ tgt = gimple_assign_lhs (use->stmt);
+ bsi = gsi_for_stmt (use->stmt);
break;
default:
gcc_unreachable ();
}
- op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
+ if (!valid_gimple_rhs_p (comp)
+ || (gimple_code (use->stmt) != GIMPLE_PHI
+ /* We can't allow re-allocating the stmt as it might be pointed
+ to still. */
+ && (get_gimple_rhs_num_ops (TREE_CODE (comp))
+ >= gimple_num_ops (gsi_stmt (bsi)))))
+ {
+ comp = force_gimple_operand_gsi (&bsi, comp, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ if (POINTER_TYPE_P (TREE_TYPE (tgt)))
+ {
+ duplicate_ssa_name_ptr_info (comp, SSA_NAME_PTR_INFO (tgt));
+ /* As this isn't a plain copy we have to reset alignment
+ information. */
+ if (SSA_NAME_PTR_INFO (comp))
+ {
+ SSA_NAME_PTR_INFO (comp)->align = 1;
+ SSA_NAME_PTR_INFO (comp)->misalign = 0;
+ }
+ }
+ }
- if (TREE_CODE (use->stmt) == PHI_NODE)
+ if (gimple_code (use->stmt) == GIMPLE_PHI)
{
- 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);
- remove_statement (use->stmt, false);
- SSA_NAME_DEF_STMT (tgt) = ass;
+ ass = gimple_build_assign (tgt, comp);
+ gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
+
+ bsi = gsi_for_stmt (use->stmt);
+ remove_phi_node (&bsi, false);
}
else
{
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
- TREE_OPERAND (use->stmt, 1) = op;
+ gimple_assign_set_rhs_from_tree (&bsi, comp);
+ use->stmt = gsi_stmt (bsi);
}
}
-/* Replaces ssa name in index IDX by its basic variable. Callback for
- for_each_index. */
-
-static bool
-idx_remove_ssa_names (tree base, tree *idx,
- void *data ATTRIBUTE_UNUSED)
-{
- tree *op;
+/* Performs a peephole optimization to reorder the iv update statement with
+ a mem ref to enable instruction combining in later phases. The mem ref uses
+ the iv value before the update, so the reordering transformation requires
+ adjustment of the offset. CAND is the selected IV_CAND.
- if (TREE_CODE (*idx) == SSA_NAME)
- *idx = SSA_NAME_VAR (*idx);
+ Example:
- if (TREE_CODE (base) == ARRAY_REF)
- {
- op = &TREE_OPERAND (base, 2);
- if (*op
- && TREE_CODE (*op) == SSA_NAME)
- *op = SSA_NAME_VAR (*op);
- op = &TREE_OPERAND (base, 3);
- if (*op
- && TREE_CODE (*op) == SSA_NAME)
- *op = SSA_NAME_VAR (*op);
- }
+ t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
+ iv2 = iv1 + 1;
- return true;
-}
+ if (t < val) (1)
+ goto L;
+ goto Head;
-/* Unshares REF and replaces ssa names inside it by their basic variables. */
-static tree
-unshare_and_remove_ssa_names (tree ref)
-{
- ref = unshare_expr (ref);
- for_each_index (&ref, idx_remove_ssa_names, NULL);
+ directly propagating t over to (1) will introduce overlapping live range
+ thus increase register pressure. This peephole transform it into:
- return ref;
-}
-/* Rewrites base of memory access OP with expression WITH in statement
- pointed to by BSI. */
+ iv2 = iv1 + 1;
+ t = MEM_REF (base, iv2, 8, 8);
+ if (t < val)
+ goto L;
+ goto Head;
+*/
static void
-rewrite_address_base (block_stmt_iterator *bsi, tree *op, tree with)
+adjust_iv_update_pos (struct iv_cand *cand, struct iv_use *use)
{
- tree bvar, var, new_name, copy, name;
- tree orig;
+ tree var_after;
+ gimple iv_update, stmt;
+ basic_block bb;
+ gimple_stmt_iterator gsi, gsi_iv;
- var = bvar = get_base_address (*op);
+ if (cand->pos != IP_NORMAL)
+ return;
- if (!var || TREE_CODE (with) != SSA_NAME)
- goto do_rewrite;
+ var_after = cand->var_after;
+ iv_update = SSA_NAME_DEF_STMT (var_after);
- 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;
- var = SSA_NAME_VAR (var);
- }
- 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);
- }
+ bb = gimple_bb (iv_update);
+ gsi = gsi_last_nondebug_bb (bb);
+ stmt = gsi_stmt (gsi);
+
+ /* Only handle conditional statement for now. */
+ if (gimple_code (stmt) != GIMPLE_COND)
+ return;
+
+ gsi_prev_nondebug (&gsi);
+ stmt = gsi_stmt (gsi);
+ if (stmt != iv_update)
+ return;
- TREE_OPERAND (copy, 0) = new_name;
- update_stmt (copy);
- bsi_insert_before (bsi, copy, BSI_SAME_STMT);
- with = new_name;
+ gsi_prev_nondebug (&gsi);
+ if (gsi_end_p (gsi))
+ return;
-do_rewrite:
+ stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return;
- orig = NULL_TREE;
- gcc_assert (TREE_CODE (*op) != ALIGN_INDIRECT_REF);
- gcc_assert (TREE_CODE (*op) != MISALIGNED_INDIRECT_REF);
+ if (stmt != use->stmt)
+ return;
- if (TREE_CODE (*op) == INDIRECT_REF)
- orig = REF_ORIGINAL (*op);
- if (!orig)
- orig = unshare_and_remove_ssa_names (*op);
+ if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
+ return;
- *op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Reordering \n");
+ print_gimple_stmt (dump_file, iv_update, 0, 0);
+ print_gimple_stmt (dump_file, use->stmt, 0, 0);
+ fprintf (dump_file, "\n");
+ }
- /* Record the original reference, for purposes of alias analysis. */
- REF_ORIGINAL (*op) = orig;
+ gsi = gsi_for_stmt (use->stmt);
+ gsi_iv = gsi_for_stmt (iv_update);
+ gsi_move_before (&gsi_iv, &gsi);
- /* Virtual operands in the original statement may have to be renamed
- because of the replacement. */
- mark_new_vars_to_rename (bsi_stmt (*bsi));
+ cand->pos = IP_BEFORE_USE;
+ cand->incremented_at = use->stmt;
}
/* 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));
- block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
- tree stmts;
- tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
-
- if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
-
- rewrite_address_base (&bsi, use->op_p, op);
+ aff_tree aff;
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+ tree base_hint = NULL_TREE;
+ tree ref, iv;
+ bool ok;
+
+ adjust_iv_update_pos (cand, use);
+ ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+ gcc_assert (ok);
+ unshare_aff_combination (&aff);
+
+ /* To avoid undefined overflow problems, all IV candidates use unsigned
+ integer types. The drawback is that this makes it impossible for
+ create_mem_ref to distinguish an IV that is based on a memory object
+ from one that represents simply an offset.
+
+ To work around this problem, we pass a hint to create_mem_ref that
+ indicates which variable (if any) in aff is an IV based on a memory
+ object. Note that we only consider the candidate. If this is not
+ based on an object, the base of the reference is in some subexpression
+ of the use -- but these will use pointer types, so they are recognized
+ by the create_mem_ref heuristics anyway. */
+ if (cand->iv->base_object)
+ base_hint = var_at_stmt (data->current_loop, cand, use->stmt);
+
+ iv = var_at_stmt (data->current_loop, cand, use->stmt);
+ ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff,
+ reference_alias_ptr_type (*use->op_p),
+ iv, base_hint, data->speed);
+ copy_ref_info (ref, *use->op_p);
+ *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;
- block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
+ tree comp, *var_p, op, bound;
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
enum tree_code compare;
-
- if (may_eliminate_iv (data, use, cand, &compare, &bound))
+ struct cost_pair *cp = get_use_iv_cost (data, use, cand);
+ bool ok;
+
+ bound = cp->value;
+ if (bound)
{
tree var = var_at_stmt (data->current_loop, cand, use->stmt);
tree var_type = TREE_TYPE (var);
+ gimple_seq stmts;
- bound = fold_convert (var_type, bound);
- op = force_gimple_operand (unshare_expr (bound), &stmts,
- true, NULL_TREE);
-
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Replacing exit test: ");
+ print_gimple_stmt (dump_file, use->stmt, 0, TDF_SLIM);
+ }
+ compare = cp->comp;
+ bound = unshare_expr (fold_convert (var_type, bound));
+ op = force_gimple_operand (bound, &stmts, true, NULL_TREE);
if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ gsi_insert_seq_on_edge_immediate (
+ loop_preheader_edge (data->current_loop),
+ stmts);
- *use->op_p = build2 (compare, boolean_type_node, var, op);
- update_stmt (use->stmt);
+ gimple_cond_set_lhs (use->stmt, var);
+ gimple_cond_set_code (use->stmt, compare);
+ gimple_cond_set_rhs (use->stmt, op);
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;
+ comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
- 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)
- {
- bool ok = may_replace_final_value (data, use, &value);
- gcc_assert (ok);
- }
- 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);
-
- /* 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;
- }
+ ok = extract_cond_operands (data, use->stmt, &var_p, NULL, NULL, NULL);
+ gcc_assert (ok);
- /* If the variable is going to be preserved anyway, there is nothing to
- do. */
- if (name_info (data, tgt)->preserve_biv)
- return;
-
- /* Otherwise we just need to compute the iv. */
- rewrite_use_nonlinear_expr (data, use, cand);
+ *var_p = force_gimple_operand_gsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
+ true, GSI_SAME_STMT);
}
/* Rewrites USE using candidate CAND. */
static void
-rewrite_use (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand)
+rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
{
switch (use->type)
{
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);
}
{
unsigned j;
bitmap_iterator bi;
+ bitmap toremove = BITMAP_ALLOC (NULL);
+ /* Figure out an order in which to release SSA DEFs so that we don't
+ release something that we'd have to propagate into a debug stmt
+ afterwards. */
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
{
struct version_info *info;
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)
- remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
+ bitmap_set_bit (toremove, SSA_NAME_VERSION (info->iv->ssa_name));
}
+
+ release_defs_bitset (toremove);
+
+ BITMAP_FREE (toremove);
+}
+
+/* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
+ for pointer_map_traverse. */
+
+static bool
+free_tree_niter_desc (const void *key ATTRIBUTE_UNUSED, void **value,
+ void *data ATTRIBUTE_UNUSED)
+{
+ struct tree_niter_desc *const niter = (struct tree_niter_desc *) *value;
+
+ free (niter);
+ return true;
}
/* Frees data allocated by the optimization of a single loop. */
{
unsigned i, j;
bitmap_iterator bi;
+ tree obj;
- htab_empty (data->niters);
+ if (data->niters)
+ {
+ pointer_map_traverse (data->niters, free_tree_niter_desc, NULL);
+ pointer_map_destroy (data->niters);
+ data->niters = NULL;
+ }
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
struct version_info *info;
info = ver_info (data, i);
- if (info->iv)
- free (info->iv);
+ free (info->iv);
info->iv = NULL;
info->has_nonlin_use = false;
info->preserve_biv = false;
free (use->cost_map);
free (use);
}
- VARRAY_POP_ALL (data->iv_uses);
+ VEC_truncate (iv_use_p, data->iv_uses, 0);
for (i = 0; i < n_iv_cands (data); i++)
{
struct iv_cand *cand = iv_cand (data, i);
- if (cand->iv)
- free (cand->iv);
+ free (cand->iv);
+ if (cand->depends_on)
+ BITMAP_FREE (cand->depends_on);
free (cand);
}
- VARRAY_POP_ALL (data->iv_candidates);
+ VEC_truncate (iv_cand_p, data->iv_candidates, 0);
if (data->version_info_size < num_ssa_names)
{
data->version_info_size = 2 * num_ssa_names;
free (data->version_info);
- data->version_info = xcalloc (data->version_info_size,
- sizeof (struct version_info));
+ data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
}
data->max_inv_id = 0;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (decl_rtl_to_reset); i++)
- {
- tree obj = VARRAY_GENERIC_PTR_NOGC (decl_rtl_to_reset, i);
+ FOR_EACH_VEC_ELT (tree, decl_rtl_to_reset, i, obj)
+ SET_DECL_RTL (obj, NULL_RTX);
- SET_DECL_RTL (obj, NULL_RTX);
- }
- VARRAY_POP_ALL (decl_rtl_to_reset);
+ VEC_truncate (tree, decl_rtl_to_reset, 0);
+
+ htab_empty (data->inv_expr_tab);
+ data->inv_expr_id = 0;
}
/* Finalizes data structures used by the iv optimization pass. LOOPS is the
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);
- VARRAY_FREE (decl_rtl_to_reset);
- VARRAY_FREE (data->iv_uses);
- VARRAY_FREE (data->iv_candidates);
+ VEC_free (tree, heap, decl_rtl_to_reset);
+ VEC_free (iv_use_p, heap, data->iv_uses);
+ VEC_free (iv_cand_p, heap, data->iv_candidates);
+ htab_delete (data->inv_expr_tab);
+}
+
+/* Returns true if the loop body BODY includes any function calls. */
+
+static bool
+loop_body_includes_call (basic_block *body, unsigned num_nodes)
+{
+ gimple_stmt_iterator gsi;
+ unsigned i;
+
+ for (i = 0; i < num_nodes; i++)
+ for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ if (is_gimple_call (stmt)
+ && !is_inexpensive_builtin (gimple_call_fndecl (stmt)))
+ return true;
+ }
+ return false;
}
/* Optimizes the LOOP. Returns true if anything changed. */
{
bool changed = false;
struct iv_ca *iv_ca;
- edge exit;
+ edge exit = single_dom_exit (loop);
+ basic_block *body;
+ gcc_assert (!data->niters);
data->current_loop = loop;
+ data->speed = optimize_loop_for_speed_p (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Processing loop %d\n", loop->num);
-
- exit = single_dom_exit (loop);
+
if (exit)
{
fprintf (dump_file, " single exit %d -> %d, exit condition ",
exit->src->index, exit->dest->index);
- print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
+ print_gimple_stmt (dump_file, last_stmt (exit->src), 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
fprintf (dump_file, "\n");
}
+ body = get_loop_body (loop);
+ data->body_includes_call = loop_body_includes_call (body, loop->num_nodes);
+ renumber_gimple_stmt_uids_in_blocks (body, loop->num_nodes);
+ free (body);
+
+ data->loop_single_exit_p = exit != NULL && loop_only_exit_p (loop, exit);
+
/* For each ssa name determines whether it behaves as an induction variable
in some loop. */
if (!find_induction_variables (data))
find_iv_candidates (data);
/* Calculates the costs (item 3, part 1). */
- determine_use_iv_costs (data);
determine_iv_costs (data);
+ determine_use_iv_costs (data);
determine_set_costs (data);
/* Find the optimal set of induction variables (item 3, part 2). */
/* Create the new induction variables (item 4, part 1). */
create_new_ivs (data, iv_ca);
iv_ca_free (&iv_ca);
-
+
/* Rewrite the uses (item 4, part 2). */
rewrite_uses (data);
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));
-
- update_ssa (TODO_update_ssa);
}
- rewrite_into_loop_closed_ssa (NULL);
- tree_ssa_iv_optimize_finalize (loops, &data);
+ tree_ssa_iv_optimize_finalize (&data);
}
OSDN Git Service
