/* Scalar evolution detector.
- Copyright (C) 2003-2014 Free Software Foundation, Inc.
+ Copyright (C) 2003-2021 Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
+#include "backend.h"
+#include "target.h"
+#include "rtl.h"
+#include "optabs-query.h"
#include "tree.h"
-#include "expr.h"
-#include "gimple-pretty-print.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
-#include "gimple-ssa.h"
#include "tree-cfg.h"
-#include "tree-phinodes.h"
-#include "stringpool.h"
-#include "tree-ssanames.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-affine.h"
#include "tree-scalar-evolution.h"
#include "dumpfile.h"
-#include "params.h"
#include "tree-ssa-propagate.h"
#include "gimple-fold.h"
-#include "gimplify-me.h"
+#include "tree-into-ssa.h"
+#include "builtins.h"
+#include "case-cfn-macros.h"
-static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
-static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
+static tree analyze_scalar_evolution_1 (class loop *, tree);
+static tree analyze_scalar_evolution_for_address_of (class loop *loop,
tree var);
/* The cached information about an SSA name with version NAME_VERSION,
claiming that below basic block with index INSTANTIATED_BELOW, the
value of the SSA name can be expressed as CHREC. */
-struct GTY(()) scev_info_str {
+struct GTY((for_user)) scev_info_str {
unsigned int name_version;
int instantiated_below;
tree chrec;
static unsigned nb_set_scev = 0;
static unsigned nb_get_scev = 0;
-/* The following trees are unique elements. Thus the comparison of
- another element to these elements should be done on the pointer to
- these trees, and not on their value. */
-
-/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
-tree chrec_not_analyzed_yet;
-
-/* Reserved to the cases where the analyzer has detected an
- undecidable property at compile time. */
-tree chrec_dont_know;
-
-/* When the analyzer has detected that a property will never
- happen, then it qualifies it with chrec_known. */
-tree chrec_known;
+struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
+{
+ static hashval_t hash (scev_info_str *i);
+ static bool equal (const scev_info_str *a, const scev_info_str *b);
+};
-static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
+static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
\f
/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
/* Computes a hash function for database element ELT. */
-static inline hashval_t
-hash_scev_info (const void *elt_)
+hashval_t
+scev_info_hasher::hash (scev_info_str *elt)
{
- const struct scev_info_str *elt = (const struct scev_info_str *) elt_;
return elt->name_version ^ elt->instantiated_below;
}
/* Compares database elements E1 and E2. */
-static inline int
-eq_scev_info (const void *e1, const void *e2)
+bool
+scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
{
- const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
- const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
-
return (elt1->name_version == elt2->name_version
&& elt1->instantiated_below == elt2->instantiated_below);
}
-/* Deletes database element E. */
-
-static void
-del_scev_info (void *e)
-{
- ggc_free (e);
-}
-
-
/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
A first query on VAR returns chrec_not_analyzed_yet. */
{
struct scev_info_str *res;
struct scev_info_str tmp;
- PTR *slot;
tmp.name_version = SSA_NAME_VERSION (var);
tmp.instantiated_below = instantiated_below->index;
- slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
+ scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
if (!*slot)
*slot = new_scev_info_str (instantiated_below, var);
- res = (struct scev_info_str *) *slot;
+ res = *slot;
return &res->chrec;
}
-/* Return true when CHREC contains symbolic names defined in
- LOOP_NB. */
-bool
-chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
-{
- int i, n;
+/* Hashtable helpers for a temporary hash-table used when
+ analyzing a scalar evolution, instantiating a CHREC or
+ resolving mixers. */
- if (chrec == NULL_TREE)
- return false;
+class instantiate_cache_type
+{
+public:
+ htab_t map;
+ vec<scev_info_str> entries;
- if (is_gimple_min_invariant (chrec))
- return false;
+ instantiate_cache_type () : map (NULL), entries (vNULL) {}
+ ~instantiate_cache_type ();
+ tree get (unsigned slot) { return entries[slot].chrec; }
+ void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
+};
- if (TREE_CODE (chrec) == SSA_NAME)
+instantiate_cache_type::~instantiate_cache_type ()
+{
+ if (map != NULL)
{
- gimple def;
- loop_p def_loop, loop;
-
- if (SSA_NAME_IS_DEFAULT_DEF (chrec))
- return false;
-
- def = SSA_NAME_DEF_STMT (chrec);
- def_loop = loop_containing_stmt (def);
- loop = get_loop (cfun, loop_nb);
-
- if (def_loop == NULL)
- return false;
-
- if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
- return true;
-
- return false;
+ htab_delete (map);
+ entries.release ();
}
-
- n = TREE_OPERAND_LENGTH (chrec);
- for (i = 0; i < n; i++)
- if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
- loop_nb))
- return true;
- return false;
}
+/* Cache to avoid infinite recursion when instantiating an SSA name.
+ Live during the outermost analyze_scalar_evolution, instantiate_scev
+ or resolve_mixers call. */
+static instantiate_cache_type *global_cache;
+
+
/* Return true when PHI is a loop-phi-node. */
static bool
-loop_phi_node_p (gimple phi)
+loop_phi_node_p (gimple *phi)
{
/* The implementation of this function is based on the following
property: "all the loop-phi-nodes of a loop are contained in the
*/
tree
-compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
+compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn)
{
bool val = false;
else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
{
- struct loop *inner_loop = get_chrec_loop (evolution_fn);
+ class loop *inner_loop = get_chrec_loop (evolution_fn);
if (inner_loop == loop
|| flow_loop_nested_p (loop, inner_loop))
fprintf (dump_file, " instantiated_below = %d \n",
instantiated_below->index);
fprintf (dump_file, " (scalar = ");
- print_generic_expr (dump_file, scalar, 0);
+ print_generic_expr (dump_file, scalar);
fprintf (dump_file, ")\n (scalar_evolution = ");
- print_generic_expr (dump_file, chrec, 0);
+ print_generic_expr (dump_file, chrec);
fprintf (dump_file, "))\n");
}
if (dump_flags & TDF_STATS)
{
fprintf (dump_file, "(get_scalar_evolution \n");
fprintf (dump_file, " (scalar = ");
- print_generic_expr (dump_file, scalar, 0);
+ print_generic_expr (dump_file, scalar);
fprintf (dump_file, ")\n");
}
if (dump_flags & TDF_STATS)
nb_get_scev++;
}
- switch (TREE_CODE (scalar))
- {
- case SSA_NAME:
- res = *find_var_scev_info (instantiated_below, scalar);
- break;
-
- case REAL_CST:
- case FIXED_CST:
- case INTEGER_CST:
- res = scalar;
- break;
-
- default:
- res = chrec_not_analyzed_yet;
- break;
- }
+ if (VECTOR_TYPE_P (TREE_TYPE (scalar))
+ || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
+ /* For chrec_dont_know we keep the symbolic form. */
+ res = scalar;
+ else
+ switch (TREE_CODE (scalar))
+ {
+ case SSA_NAME:
+ if (SSA_NAME_IS_DEFAULT_DEF (scalar))
+ res = scalar;
+ else
+ res = *find_var_scev_info (instantiated_below, scalar);
+ break;
+
+ case REAL_CST:
+ case FIXED_CST:
+ case INTEGER_CST:
+ res = scalar;
+ break;
+
+ default:
+ res = chrec_not_analyzed_yet;
+ break;
+ }
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (scalar_evolution = ");
- print_generic_expr (dump_file, res, 0);
+ print_generic_expr (dump_file, res);
fprintf (dump_file, "))\n");
}
static tree
add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
- gimple at_stmt)
+ gimple *at_stmt)
{
tree type, left, right;
- struct loop *loop = get_loop (cfun, loop_nb), *chloop;
+ class loop *loop = get_loop (cfun, loop_nb), *chloop;
switch (TREE_CODE (chrec_before))
{
static tree
add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
- tree to_add, gimple at_stmt)
+ tree to_add, gimple *at_stmt)
{
tree type = chrec_type (to_add);
tree res = NULL_TREE;
fprintf (dump_file, "(add_to_evolution \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (chrec_before = ");
- print_generic_expr (dump_file, chrec_before, 0);
+ print_generic_expr (dump_file, chrec_before);
fprintf (dump_file, ")\n (to_add = ");
- print_generic_expr (dump_file, to_add, 0);
+ print_generic_expr (dump_file, to_add);
fprintf (dump_file, ")\n");
}
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (res = ");
- print_generic_expr (dump_file, res, 0);
+ print_generic_expr (dump_file, res);
fprintf (dump_file, "))\n");
}
guards the exit edge. If the expression is too difficult to
analyze, then give up. */
-gimple
-get_loop_exit_condition (const struct loop *loop)
+gcond *
+get_loop_exit_condition (const class loop *loop)
{
- gimple res = NULL;
+ gcond *res = NULL;
edge exit_edge = single_exit (loop);
if (dump_file && (dump_flags & TDF_SCEV))
if (exit_edge)
{
- gimple stmt;
+ gimple *stmt;
stmt = last_stmt (exit_edge->src);
- if (gimple_code (stmt) == GIMPLE_COND)
- res = stmt;
+ if (gcond *cond_stmt = safe_dyn_cast <gcond *> (stmt))
+ res = cond_stmt;
}
if (dump_file && (dump_flags & TDF_SCEV))
{
- print_gimple_stmt (dump_file, res, 0, 0);
+ print_gimple_stmt (dump_file, res, 0);
fprintf (dump_file, ")\n");
}
\f
/* Depth first search algorithm. */
-typedef enum t_bool {
+enum t_bool {
t_false,
t_true,
t_dont_know
-} t_bool;
+};
-static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
+static t_bool follow_ssa_edge_expr (class loop *loop, gimple *, tree, gphi *,
+ tree *, int);
/* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
Return true if the strongly connected component has been found. */
static t_bool
-follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
+follow_ssa_edge_binary (class loop *loop, gimple *at_stmt,
tree type, tree rhs0, enum tree_code code, tree rhs1,
- gimple halting_phi, tree *evolution_of_loop, int limit)
+ gphi *halting_phi, tree *evolution_of_loop,
+ int limit)
{
t_bool res = t_false;
tree evol;
limit++;
evol = *evolution_of_loop;
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
-
- if (res == t_true)
- *evolution_of_loop = add_to_evolution
+ evol = add_to_evolution
(loop->num,
chrec_convert (type, evol, at_stmt),
code, rhs1, at_stmt);
-
+ res = follow_ssa_edge_expr
+ (loop, at_stmt, rhs0, halting_phi, &evol, limit);
+ if (res == t_true)
+ *evolution_of_loop = evol;
else if (res == t_false)
{
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop, limit);
-
- if (res == t_true)
- *evolution_of_loop = add_to_evolution
+ *evolution_of_loop = add_to_evolution
(loop->num,
chrec_convert (type, *evolution_of_loop, at_stmt),
code, rhs0, at_stmt);
-
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
+ res = follow_ssa_edge_expr
+ (loop, at_stmt, rhs1, halting_phi,
+ evolution_of_loop, limit);
}
-
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
}
else
- {
- /* Match an assignment under the form:
- "a = b + ...". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop, limit);
- if (res == t_true)
- *evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type, *evolution_of_loop,
- at_stmt),
- code, rhs1, at_stmt);
-
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
- }
+ gcc_unreachable (); /* Handled in caller. */
}
else if (TREE_CODE (rhs1) == SSA_NAME)
{
/* Match an assignment under the form:
"a = ... + c". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop, limit);
- if (res == t_true)
- *evolution_of_loop = add_to_evolution
+ *evolution_of_loop = add_to_evolution
(loop->num, chrec_convert (type, *evolution_of_loop,
at_stmt),
code, rhs0, at_stmt);
-
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
+ res = follow_ssa_edge_expr
+ (loop, at_stmt, rhs1, halting_phi,
+ evolution_of_loop, limit);
}
else
case MINUS_EXPR:
/* This case is under the form "opnd0 = rhs0 - rhs1". */
if (TREE_CODE (rhs0) == SSA_NAME)
- {
- /* Match an assignment under the form:
- "a = b - ...". */
-
- /* We want only assignments of form "name - name" contribute to
- LIMIT, as the other cases do not necessarily contribute to
- the complexity of the expression. */
- if (TREE_CODE (rhs1) == SSA_NAME)
- limit++;
-
- res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop, limit);
- if (res == t_true)
- *evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
- MINUS_EXPR, rhs1, at_stmt);
-
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
- }
+ gcc_unreachable (); /* Handled in caller. */
else
/* Otherwise, match an assignment under the form:
"a = ... - ...". */
return res;
}
-/* Follow the ssa edge into the expression EXPR.
- Return true if the strongly connected component has been found. */
-
-static t_bool
-follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
- gimple halting_phi, tree *evolution_of_loop, int limit)
-{
- enum tree_code code = TREE_CODE (expr);
- tree type = TREE_TYPE (expr), rhs0, rhs1;
- t_bool res;
-
- /* The EXPR is one of the following cases:
- - an SSA_NAME,
- - an INTEGER_CST,
- - a PLUS_EXPR,
- - a POINTER_PLUS_EXPR,
- - a MINUS_EXPR,
- - an ASSERT_EXPR,
- - other cases are not yet handled. */
-
- switch (code)
- {
- CASE_CONVERT:
- /* This assignment is under the form "a_1 = (cast) rhs. */
- res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
- halting_phi, evolution_of_loop, limit);
- *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
- break;
-
- case INTEGER_CST:
- /* This assignment is under the form "a_1 = 7". */
- res = t_false;
- break;
-
- case SSA_NAME:
- /* This assignment is under the form: "a_1 = b_2". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
- break;
-
- case POINTER_PLUS_EXPR:
- case PLUS_EXPR:
- case MINUS_EXPR:
- /* This case is under the form "rhs0 +- rhs1". */
- rhs0 = TREE_OPERAND (expr, 0);
- rhs1 = TREE_OPERAND (expr, 1);
- type = TREE_TYPE (rhs0);
- STRIP_USELESS_TYPE_CONVERSION (rhs0);
- STRIP_USELESS_TYPE_CONVERSION (rhs1);
- res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
- halting_phi, evolution_of_loop, limit);
- break;
-
- case ADDR_EXPR:
- /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
- if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
- {
- expr = TREE_OPERAND (expr, 0);
- rhs0 = TREE_OPERAND (expr, 0);
- rhs1 = TREE_OPERAND (expr, 1);
- type = TREE_TYPE (rhs0);
- STRIP_USELESS_TYPE_CONVERSION (rhs0);
- STRIP_USELESS_TYPE_CONVERSION (rhs1);
- res = follow_ssa_edge_binary (loop, at_stmt, type,
- rhs0, POINTER_PLUS_EXPR, rhs1,
- halting_phi, evolution_of_loop, limit);
- }
- else
- res = t_false;
- break;
-
- case ASSERT_EXPR:
- /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
- It must be handled as a copy assignment of the form a_1 = a_2. */
- rhs0 = ASSERT_EXPR_VAR (expr);
- if (TREE_CODE (rhs0) == SSA_NAME)
- res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
- halting_phi, evolution_of_loop, limit);
- else
- res = t_false;
- break;
-
- default:
- res = t_false;
- break;
- }
-
- return res;
-}
-
-/* Follow the ssa edge into the right hand side of an assignment STMT.
- Return true if the strongly connected component has been found. */
-
-static t_bool
-follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
- gimple halting_phi, tree *evolution_of_loop, int limit)
-{
- enum tree_code code = gimple_assign_rhs_code (stmt);
- tree type = gimple_expr_type (stmt), rhs1, rhs2;
- t_bool res;
-
- switch (code)
- {
- CASE_CONVERT:
- /* This assignment is under the form "a_1 = (cast) rhs. */
- res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
- halting_phi, evolution_of_loop, limit);
- *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
- break;
-
- case POINTER_PLUS_EXPR:
- case PLUS_EXPR:
- case MINUS_EXPR:
- rhs1 = gimple_assign_rhs1 (stmt);
- rhs2 = gimple_assign_rhs2 (stmt);
- type = TREE_TYPE (rhs1);
- res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
- halting_phi, evolution_of_loop, limit);
- break;
-
- default:
- if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
- res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
- halting_phi, evolution_of_loop, limit);
- else
- res = t_false;
- break;
- }
-
- return res;
-}
-
/* Checks whether the I-th argument of a PHI comes from a backedge. */
static bool
-backedge_phi_arg_p (gimple phi, int i)
+backedge_phi_arg_p (gphi *phi, int i)
{
const_edge e = gimple_phi_arg_edge (phi, i);
static inline t_bool
follow_ssa_edge_in_condition_phi_branch (int i,
- struct loop *loop,
- gimple condition_phi,
- gimple halting_phi,
+ class loop *loop,
+ gphi *condition_phi,
+ gphi *halting_phi,
tree *evolution_of_branch,
tree init_cond, int limit)
{
if (TREE_CODE (branch) == SSA_NAME)
{
*evolution_of_branch = init_cond;
- return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
- evolution_of_branch, limit);
+ return follow_ssa_edge_expr (loop, condition_phi, branch, halting_phi,
+ evolution_of_branch, limit);
}
/* This case occurs when one of the condition branches sets
loop. */
static t_bool
-follow_ssa_edge_in_condition_phi (struct loop *loop,
- gimple condition_phi,
- gimple halting_phi,
+follow_ssa_edge_in_condition_phi (class loop *loop,
+ gphi *condition_phi,
+ gphi *halting_phi,
tree *evolution_of_loop, int limit)
{
int i, n;
considered as a single statement. */
static t_bool
-follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
- gimple loop_phi_node,
- gimple halting_phi,
+follow_ssa_edge_inner_loop_phi (class loop *outer_loop,
+ gphi *loop_phi_node,
+ gphi *halting_phi,
tree *evolution_of_loop, int limit)
{
- struct loop *loop = loop_containing_stmt (loop_phi_node);
+ class loop *loop = loop_containing_stmt (loop_phi_node);
tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
/* Sometimes, the inner loop is too difficult to analyze, and the
evolution_of_loop, limit);
}
-/* Follow an SSA edge from a loop-phi-node to itself, constructing a
- path that is analyzed on the return walk. */
+/* Follow the ssa edge into the expression EXPR.
+ Return true if the strongly connected component has been found. */
static t_bool
-follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
- tree *evolution_of_loop, int limit)
+follow_ssa_edge_expr (class loop *loop, gimple *at_stmt, tree expr,
+ gphi *halting_phi, tree *evolution_of_loop,
+ int limit)
{
- struct loop *def_loop;
+ enum tree_code code;
+ tree type, rhs0, rhs1 = NULL_TREE;
- if (gimple_nop_p (def))
- return t_false;
+ /* The EXPR is one of the following cases:
+ - an SSA_NAME,
+ - an INTEGER_CST,
+ - a PLUS_EXPR,
+ - a POINTER_PLUS_EXPR,
+ - a MINUS_EXPR,
+ - an ASSERT_EXPR,
+ - other cases are not yet handled. */
+
+ /* For SSA_NAME look at the definition statement, handling
+ PHI nodes and otherwise expand appropriately for the expression
+ handling below. */
+tail_recurse:
+ if (TREE_CODE (expr) == SSA_NAME)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (expr);
- /* Give up if the path is longer than the MAX that we allow. */
- if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
- return t_dont_know;
+ if (gimple_nop_p (def))
+ return t_false;
- def_loop = loop_containing_stmt (def);
+ /* Give up if the path is longer than the MAX that we allow. */
+ if (limit > param_scev_max_expr_complexity)
+ {
+ *evolution_of_loop = chrec_dont_know;
+ return t_dont_know;
+ }
- switch (gimple_code (def))
- {
- case GIMPLE_PHI:
- if (!loop_phi_node_p (def))
- /* DEF is a condition-phi-node. Follow the branches, and
- record their evolutions. Finally, merge the collected
- information and set the approximation to the main
- variable. */
- return follow_ssa_edge_in_condition_phi
- (loop, def, halting_phi, evolution_of_loop, limit);
-
- /* When the analyzed phi is the halting_phi, the
- depth-first search is over: we have found a path from
- the halting_phi to itself in the loop. */
- if (def == halting_phi)
- return t_true;
+ if (gphi *phi = dyn_cast <gphi *>(def))
+ {
+ if (!loop_phi_node_p (phi))
+ /* DEF is a condition-phi-node. Follow the branches, and
+ record their evolutions. Finally, merge the collected
+ information and set the approximation to the main
+ variable. */
+ return follow_ssa_edge_in_condition_phi
+ (loop, phi, halting_phi, evolution_of_loop, limit);
+
+ /* When the analyzed phi is the halting_phi, the
+ depth-first search is over: we have found a path from
+ the halting_phi to itself in the loop. */
+ if (phi == halting_phi)
+ return t_true;
+
+ /* Otherwise, the evolution of the HALTING_PHI depends
+ on the evolution of another loop-phi-node, i.e. the
+ evolution function is a higher degree polynomial. */
+ class loop *def_loop = loop_containing_stmt (def);
+ if (def_loop == loop)
+ return t_false;
+
+ /* Inner loop. */
+ if (flow_loop_nested_p (loop, def_loop))
+ return follow_ssa_edge_inner_loop_phi
+ (loop, phi, halting_phi, evolution_of_loop,
+ limit + 1);
+
+ /* Outer loop. */
+ return t_false;
+ }
- /* Otherwise, the evolution of the HALTING_PHI depends
- on the evolution of another loop-phi-node, i.e. the
- evolution function is a higher degree polynomial. */
- if (def_loop == loop)
+ /* At this level of abstraction, the program is just a set
+ of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
+ other def to be handled. */
+ if (!is_gimple_assign (def))
return t_false;
- /* Inner loop. */
- if (flow_loop_nested_p (loop, def_loop))
- return follow_ssa_edge_inner_loop_phi
- (loop, def, halting_phi, evolution_of_loop, limit + 1);
+ code = gimple_assign_rhs_code (def);
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_BINARY_RHS:
+ rhs0 = gimple_assign_rhs1 (def);
+ rhs1 = gimple_assign_rhs2 (def);
+ break;
+ case GIMPLE_UNARY_RHS:
+ case GIMPLE_SINGLE_RHS:
+ rhs0 = gimple_assign_rhs1 (def);
+ break;
+ default:
+ return t_false;
+ }
+ type = TREE_TYPE (gimple_assign_lhs (def));
+ at_stmt = def;
+ }
+ else
+ {
+ code = TREE_CODE (expr);
+ type = TREE_TYPE (expr);
+ switch (code)
+ {
+ CASE_CONVERT:
+ rhs0 = TREE_OPERAND (expr, 0);
+ break;
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ rhs0 = TREE_OPERAND (expr, 0);
+ rhs1 = TREE_OPERAND (expr, 1);
+ break;
+ default:
+ rhs0 = expr;
+ }
+ }
+
+ switch (code)
+ {
+ CASE_CONVERT:
+ {
+ /* This assignment is under the form "a_1 = (cast) rhs. */
+ t_bool res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi,
+ evolution_of_loop, limit);
+ *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
+ return res;
+ }
- /* Outer loop. */
+ case INTEGER_CST:
+ /* This assignment is under the form "a_1 = 7". */
return t_false;
- case GIMPLE_ASSIGN:
- return follow_ssa_edge_in_rhs (loop, def, halting_phi,
- evolution_of_loop, limit);
+ case ADDR_EXPR:
+ {
+ /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
+ if (TREE_CODE (TREE_OPERAND (rhs0, 0)) != MEM_REF)
+ return t_false;
+ tree mem = TREE_OPERAND (rhs0, 0);
+ rhs0 = TREE_OPERAND (mem, 0);
+ rhs1 = TREE_OPERAND (mem, 1);
+ code = POINTER_PLUS_EXPR;
+ }
+ /* Fallthru. */
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ /* This case is under the form "rhs0 +- rhs1". */
+ STRIP_USELESS_TYPE_CONVERSION (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs1);
+ if (TREE_CODE (rhs0) == SSA_NAME
+ && (TREE_CODE (rhs1) != SSA_NAME || code == MINUS_EXPR))
+ {
+ /* Match an assignment under the form:
+ "a = b +- ...".
+ Use tail-recursion for the simple case. */
+ *evolution_of_loop = add_to_evolution
+ (loop->num, chrec_convert (type, *evolution_of_loop,
+ at_stmt),
+ code, rhs1, at_stmt);
+ expr = rhs0;
+ goto tail_recurse;
+ }
+ /* Else search for the SCC in both rhs0 and rhs1. */
+ return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
+ halting_phi, evolution_of_loop, limit);
+
+ case ASSERT_EXPR:
+ /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
+ It must be handled as a copy assignment of the form a_1 = a_2. */
+ expr = ASSERT_EXPR_VAR (rhs0);
+ goto tail_recurse;
default:
- /* At this level of abstraction, the program is just a set
- of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
- other node to be handled. */
return t_false;
}
}
See PR41488. */
static tree
-simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
+simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond)
{
aff_tree aff1, aff2;
tree ev, left, right, type, step_val;
return build_polynomial_chrec (loop->num, init_cond, right);
}
+ /* The affine code only deals with pointer and integer types. */
+ if (!POINTER_TYPE_P (type)
+ && !INTEGRAL_TYPE_P (type))
+ return chrec_dont_know;
+
/* Try harder to check if they are equal. */
tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
static tree
-analyze_evolution_in_loop (gimple loop_phi_node,
+analyze_evolution_in_loop (gphi *loop_phi_node,
tree init_cond)
{
int i, n = gimple_phi_num_args (loop_phi_node);
tree evolution_function = chrec_not_analyzed_yet;
- struct loop *loop = loop_containing_stmt (loop_phi_node);
+ class loop *loop = loop_containing_stmt (loop_phi_node);
basic_block bb;
static bool simplify_peeled_chrec_p = true;
{
fprintf (dump_file, "(analyze_evolution_in_loop \n");
fprintf (dump_file, " (loop_phi_node = ");
- print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
+ print_gimple_stmt (dump_file, loop_phi_node, 0);
fprintf (dump_file, ")\n");
}
for (i = 0; i < n; i++)
{
tree arg = PHI_ARG_DEF (loop_phi_node, i);
- gimple ssa_chain;
tree ev_fn;
t_bool res;
{
bool val = false;
- ssa_chain = SSA_NAME_DEF_STMT (arg);
-
/* Pass in the initial condition to the follow edge function. */
ev_fn = init_cond;
- res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
+ res = follow_ssa_edge_expr (loop, loop_phi_node, arg,
+ loop_phi_node, &ev_fn, 0);
/* If ev_fn has no evolution in the inner loop, and the
init_cond is not equal to ev_fn, then we have an
/* When there are multiple back edges of the loop (which in fact never
happens currently, but nevertheless), merge their evolutions. */
evolution_function = chrec_merge (evolution_function, ev_fn);
+
+ if (evolution_function == chrec_dont_know)
+ break;
}
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (evolution_function = ");
- print_generic_expr (dump_file, evolution_function, 0);
+ print_generic_expr (dump_file, evolution_function);
fprintf (dump_file, "))\n");
}
return evolution_function;
}
+/* Looks to see if VAR is a copy of a constant (via straightforward assignments
+ or degenerate phi's). If so, returns the constant; else, returns VAR. */
+
+static tree
+follow_copies_to_constant (tree var)
+{
+ tree res = var;
+ while (TREE_CODE (res) == SSA_NAME
+ /* We face not updated SSA form in multiple places and this walk
+ may end up in sibling loops so we have to guard it. */
+ && !name_registered_for_update_p (res))
+ {
+ gimple *def = SSA_NAME_DEF_STMT (res);
+ if (gphi *phi = dyn_cast <gphi *> (def))
+ {
+ if (tree rhs = degenerate_phi_result (phi))
+ res = rhs;
+ else
+ break;
+ }
+ else if (gimple_assign_single_p (def))
+ /* Will exit loop if not an SSA_NAME. */
+ res = gimple_assign_rhs1 (def);
+ else
+ break;
+ }
+ if (CONSTANT_CLASS_P (res))
+ return res;
+ return var;
+}
+
/* Given a loop-phi-node, return the initial conditions of the
variable on entry of the loop. When the CCP has propagated
constants into the loop-phi-node, the initial condition is
loop, and leaves this task to the on-demand tree reconstructor. */
static tree
-analyze_initial_condition (gimple loop_phi_node)
+analyze_initial_condition (gphi *loop_phi_node)
{
int i, n;
tree init_cond = chrec_not_analyzed_yet;
- struct loop *loop = loop_containing_stmt (loop_phi_node);
+ class loop *loop = loop_containing_stmt (loop_phi_node);
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(analyze_initial_condition \n");
fprintf (dump_file, " (loop_phi_node = \n");
- print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
+ print_gimple_stmt (dump_file, loop_phi_node, 0);
fprintf (dump_file, ")\n");
}
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_dont_know;
- /* During early loop unrolling we do not have fully constant propagated IL.
- Handle degenerate PHIs here to not miss important unrollings. */
- if (TREE_CODE (init_cond) == SSA_NAME)
- {
- gimple def = SSA_NAME_DEF_STMT (init_cond);
- tree res;
- if (gimple_code (def) == GIMPLE_PHI
- && (res = degenerate_phi_result (def)) != NULL_TREE
- /* Only allow invariants here, otherwise we may break
- loop-closed SSA form. */
- && is_gimple_min_invariant (res))
- init_cond = res;
- }
+ /* We may not have fully constant propagated IL. Handle degenerate PHIs here
+ to not miss important early loop unrollings. */
+ init_cond = follow_copies_to_constant (init_cond);
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (init_cond = ");
- print_generic_expr (dump_file, init_cond, 0);
+ print_generic_expr (dump_file, init_cond);
fprintf (dump_file, "))\n");
}
/* Analyze the scalar evolution for LOOP_PHI_NODE. */
static tree
-interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
+interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
{
tree res;
- struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
+ class loop *phi_loop = loop_containing_stmt (loop_phi_node);
tree init_cond;
- if (phi_loop != loop)
- {
- struct loop *subloop;
- tree evolution_fn = analyze_scalar_evolution
- (phi_loop, PHI_RESULT (loop_phi_node));
-
- /* Dive one level deeper. */
- subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
-
- /* Interpret the subloop. */
- res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
- return res;
- }
+ gcc_assert (phi_loop == loop);
/* Otherwise really interpret the loop phi. */
init_cond = analyze_initial_condition (loop_phi_node);
analyzed. */
static tree
-interpret_condition_phi (struct loop *loop, gimple condition_phi)
+interpret_condition_phi (class loop *loop, gphi *condition_phi)
{
int i, n = gimple_phi_num_args (condition_phi);
tree res = chrec_not_analyzed_yet;
(loop, PHI_ARG_DEF (condition_phi, i));
res = chrec_merge (res, branch_chrec);
+ if (res == chrec_dont_know)
+ break;
}
return res;
analyze the effect of an inner loop: see interpret_loop_phi. */
static tree
-interpret_rhs_expr (struct loop *loop, gimple at_stmt,
+interpret_rhs_expr (class loop *loop, gimple *at_stmt,
tree type, tree rhs1, enum tree_code code, tree rhs2)
{
- tree res, chrec1, chrec2;
- gimple def;
+ tree res, chrec1, chrec2, ctype;
+ gimple *def;
if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
{
if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
|| handled_component_p (TREE_OPERAND (rhs1, 0)))
{
- enum machine_mode mode;
- HOST_WIDE_INT bitsize, bitpos;
- int unsignedp;
+ machine_mode mode;
+ poly_int64 bitsize, bitpos;
+ int unsignedp, reversep;
int volatilep = 0;
tree base, offset;
tree chrec3;
tree unitpos;
base = get_inner_reference (TREE_OPERAND (rhs1, 0),
- &bitsize, &bitpos, &offset,
- &mode, &unsignedp, &volatilep, false);
+ &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &reversep, &volatilep);
if (TREE_CODE (base) == MEM_REF)
{
res = chrec_fold_plus (type, res, chrec2);
}
- if (bitpos != 0)
+ if (maybe_ne (bitpos, 0))
{
- gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
-
- unitpos = size_int (bitpos / BITS_PER_UNIT);
+ unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
chrec3 = analyze_scalar_evolution (loop, unitpos);
chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
chrec3 = instantiate_parameters (loop, chrec3);
case PLUS_EXPR:
chrec1 = analyze_scalar_evolution (loop, rhs1);
chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
- chrec2 = chrec_convert (type, chrec2, at_stmt);
+ ctype = type;
+ /* When the stmt is conditionally executed re-write the CHREC
+ into a form that has well-defined behavior on overflow. */
+ if (at_stmt
+ && INTEGRAL_TYPE_P (type)
+ && ! TYPE_OVERFLOW_WRAPS (type)
+ && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
+ gimple_bb (at_stmt)))
+ ctype = unsigned_type_for (type);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt);
+ chrec2 = chrec_convert (ctype, chrec2, at_stmt);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
- res = chrec_fold_plus (type, chrec1, chrec2);
+ res = chrec_fold_plus (ctype, chrec1, chrec2);
+ if (type != ctype)
+ res = chrec_convert (type, res, at_stmt);
break;
case MINUS_EXPR:
chrec1 = analyze_scalar_evolution (loop, rhs1);
chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
- chrec2 = chrec_convert (type, chrec2, at_stmt);
+ ctype = type;
+ /* When the stmt is conditionally executed re-write the CHREC
+ into a form that has well-defined behavior on overflow. */
+ if (at_stmt
+ && INTEGRAL_TYPE_P (type)
+ && ! TYPE_OVERFLOW_WRAPS (type)
+ && ! dominated_by_p (CDI_DOMINATORS,
+ loop->latch, gimple_bb (at_stmt)))
+ ctype = unsigned_type_for (type);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt);
+ chrec2 = chrec_convert (ctype, chrec2, at_stmt);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
- res = chrec_fold_minus (type, chrec1, chrec2);
+ res = chrec_fold_minus (ctype, chrec1, chrec2);
+ if (type != ctype)
+ res = chrec_convert (type, res, at_stmt);
break;
case NEGATE_EXPR:
chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
+ ctype = type;
+ /* When the stmt is conditionally executed re-write the CHREC
+ into a form that has well-defined behavior on overflow. */
+ if (at_stmt
+ && INTEGRAL_TYPE_P (type)
+ && ! TYPE_OVERFLOW_WRAPS (type)
+ && ! dominated_by_p (CDI_DOMINATORS,
+ loop->latch, gimple_bb (at_stmt)))
+ ctype = unsigned_type_for (type);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt);
/* TYPE may be integer, real or complex, so use fold_convert. */
chrec1 = instantiate_parameters (loop, chrec1);
- res = chrec_fold_multiply (type, chrec1,
- fold_convert (type, integer_minus_one_node));
+ res = chrec_fold_multiply (ctype, chrec1,
+ fold_convert (ctype, integer_minus_one_node));
+ if (type != ctype)
+ res = chrec_convert (type, res, at_stmt);
break;
case BIT_NOT_EXPR:
case MULT_EXPR:
chrec1 = analyze_scalar_evolution (loop, rhs1);
chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
- chrec2 = chrec_convert (type, chrec2, at_stmt);
+ ctype = type;
+ /* When the stmt is conditionally executed re-write the CHREC
+ into a form that has well-defined behavior on overflow. */
+ if (at_stmt
+ && INTEGRAL_TYPE_P (type)
+ && ! TYPE_OVERFLOW_WRAPS (type)
+ && ! dominated_by_p (CDI_DOMINATORS,
+ loop->latch, gimple_bb (at_stmt)))
+ ctype = unsigned_type_for (type);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt);
+ chrec2 = chrec_convert (ctype, chrec2, at_stmt);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
- res = chrec_fold_multiply (type, chrec1, chrec2);
+ res = chrec_fold_multiply (ctype, chrec1, chrec2);
+ if (type != ctype)
+ res = chrec_convert (type, res, at_stmt);
+ break;
+
+ case LSHIFT_EXPR:
+ {
+ /* Handle A<<B as A * (1<<B). */
+ tree uns = unsigned_type_for (type);
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = chrec_convert (uns, chrec1, at_stmt);
+ chrec1 = instantiate_parameters (loop, chrec1);
+ chrec2 = instantiate_parameters (loop, chrec2);
+
+ tree one = build_int_cst (uns, 1);
+ chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
+ res = chrec_fold_multiply (uns, chrec1, chrec2);
+ res = chrec_convert (type, res, at_stmt);
+ }
break;
CASE_CONVERT:
}
else
chrec1 = analyze_scalar_evolution (loop, rhs1);
- res = chrec_convert (type, chrec1, at_stmt);
+ res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
+ break;
+
+ case BIT_AND_EXPR:
+ /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
+ If A is SCEV and its value is in the range of representable set
+ of type unsigned short, the result expression is a (no-overflow)
+ SCEV. */
+ res = chrec_dont_know;
+ if (tree_fits_uhwi_p (rhs2))
+ {
+ int precision;
+ unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
+
+ val ++;
+ /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
+ it's not the maximum value of a smaller type than rhs1. */
+ if (val != 0
+ && (precision = exact_log2 (val)) > 0
+ && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
+ {
+ tree utype = build_nonstandard_integer_type (precision, 1);
+
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
+ {
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec1 = chrec_convert (utype, chrec1, at_stmt);
+ res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
+ }
+ }
+ }
break;
default:
/* Interpret the expression EXPR. */
static tree
-interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
+interpret_expr (class loop *loop, gimple *at_stmt, tree expr)
{
enum tree_code code;
tree type = TREE_TYPE (expr), op0, op1;
return expr;
if (TREE_CODE (expr) == POLYNOMIAL_CHREC
+ || TREE_CODE (expr) == CALL_EXPR
|| get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
return chrec_dont_know;
/* Interpret the rhs of the assignment STMT. */
static tree
-interpret_gimple_assign (struct loop *loop, gimple stmt)
+interpret_gimple_assign (class loop *loop, gimple *stmt)
{
tree type = TREE_TYPE (gimple_assign_lhs (stmt));
enum tree_code code = gimple_assign_rhs_code (stmt);
- instantiate_parameters.
*/
-/* Compute and return the evolution function in WRTO_LOOP, the nearest
- common ancestor of DEF_LOOP and USE_LOOP. */
-
-static tree
-compute_scalar_evolution_in_loop (struct loop *wrto_loop,
- struct loop *def_loop,
- tree ev)
-{
- bool val;
- tree res;
-
- if (def_loop == wrto_loop)
- return ev;
-
- def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
- res = compute_overall_effect_of_inner_loop (def_loop, ev);
-
- if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
- return res;
-
- return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
-}
-
/* Helper recursive function. */
static tree
-analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
+analyze_scalar_evolution_1 (class loop *loop, tree var)
{
- tree type = TREE_TYPE (var);
- gimple def;
+ gimple *def;
basic_block bb;
- struct loop *def_loop;
-
- if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
- return chrec_dont_know;
+ class loop *def_loop;
+ tree res;
if (TREE_CODE (var) != SSA_NAME)
return interpret_expr (loop, NULL, var);
def = SSA_NAME_DEF_STMT (var);
bb = gimple_bb (def);
- def_loop = bb ? bb->loop_father : NULL;
+ def_loop = bb->loop_father;
- if (bb == NULL
- || !flow_bb_inside_loop_p (loop, bb))
+ if (!flow_bb_inside_loop_p (loop, bb))
{
- /* Keep the symbolic form. */
- res = var;
- goto set_and_end;
- }
-
- if (res != chrec_not_analyzed_yet)
- {
- if (loop != bb->loop_father)
- res = compute_scalar_evolution_in_loop
- (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
-
+ /* Keep symbolic form, but look through obvious copies for constants. */
+ res = follow_copies_to_constant (var);
goto set_and_end;
}
if (loop != def_loop)
{
- res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
- res = compute_scalar_evolution_in_loop (loop, def_loop, res);
-
+ res = analyze_scalar_evolution_1 (def_loop, var);
+ class loop *loop_to_skip = superloop_at_depth (def_loop,
+ loop_depth (loop) + 1);
+ res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
+ if (chrec_contains_symbols_defined_in_loop (res, loop->num))
+ res = analyze_scalar_evolution_1 (loop, res);
goto set_and_end;
}
case GIMPLE_PHI:
if (loop_phi_node_p (def))
- res = interpret_loop_phi (loop, def);
+ res = interpret_loop_phi (loop, as_a <gphi *> (def));
else
- res = interpret_condition_phi (loop, def);
+ res = interpret_condition_phi (loop, as_a <gphi *> (def));
break;
default:
*/
tree
-analyze_scalar_evolution (struct loop *loop, tree var)
+analyze_scalar_evolution (class loop *loop, tree var)
{
tree res;
+ /* ??? Fix callers. */
+ if (! loop)
+ return var;
+
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(analyze_scalar_evolution \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (scalar = ");
- print_generic_expr (dump_file, var, 0);
+ print_generic_expr (dump_file, var);
fprintf (dump_file, ")\n");
}
res = get_scalar_evolution (block_before_loop (loop), var);
- res = analyze_scalar_evolution_1 (loop, var, res);
+ if (res == chrec_not_analyzed_yet)
+ {
+ /* We'll recurse into instantiate_scev, avoid tearing down the
+ instantiate cache repeatedly and keep it live from here. */
+ bool destr = false;
+ if (!global_cache)
+ {
+ global_cache = new instantiate_cache_type;
+ destr = true;
+ }
+ res = analyze_scalar_evolution_1 (loop, var);
+ if (destr)
+ {
+ delete global_cache;
+ global_cache = NULL;
+ }
+ }
if (dump_file && (dump_flags & TDF_SCEV))
fprintf (dump_file, ")\n");
/* Analyzes and returns the scalar evolution of VAR address in LOOP. */
static tree
-analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
+analyze_scalar_evolution_for_address_of (class loop *loop, tree var)
{
return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
}
*/
static tree
-analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
+analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop,
tree version, bool *folded_casts)
{
bool val = false;
/* We cannot just do
tmp = analyze_scalar_evolution (use_loop, version);
- ev = resolve_mixers (wrto_loop, tmp);
+ ev = resolve_mixers (wrto_loop, tmp, folded_casts);
as resolve_mixers would query the scalar evolution with respect to
wrto_loop. For example, in the situation described in the function
analyze_scalar_evolution (use_loop, version) = k2
- and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
- is 100, which is a wrong result, since we are interested in the
- value in loop 3.
+ and resolve_mixers (loop1, k2, folded_casts) finds that the value of
+ k2 in loop 1 is 100, which is a wrong result, since we are interested
+ in the value in loop 3.
Instead, we need to proceed from use_loop to wrto_loop loop by loop,
each time checking that there is no evolution in the inner loop. */
while (1)
{
tmp = analyze_scalar_evolution (use_loop, ev);
- ev = resolve_mixers (use_loop, tmp);
-
- if (folded_casts && tmp != ev)
- *folded_casts = true;
+ ev = resolve_mixers (use_loop, tmp, folded_casts);
if (use_loop == wrto_loop)
return ev;
}
-/* Hashtable helpers for a temporary hash-table used when
- instantiating a CHREC or resolving mixers. For this use
- instantiated_below is always the same. */
-
-struct instantiate_cache_type
-{
- htab_t map;
- vec<scev_info_str> entries;
-
- instantiate_cache_type () : map (NULL), entries (vNULL) {}
- ~instantiate_cache_type ();
- tree get (unsigned slot) { return entries[slot].chrec; }
- void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
-};
-
-instantiate_cache_type::~instantiate_cache_type ()
-{
- if (map != NULL)
- {
- htab_delete (map);
- entries.release ();
- }
-}
-
-/* Cache to avoid infinite recursion when instantiating an SSA name.
- Live during the outermost instantiate_scev or resolve_mixers call. */
-static instantiate_cache_type *global_cache;
-
/* Computes a hash function for database element ELT. */
static inline hashval_t
hash_idx_scev_info (const void *elt_)
{
unsigned idx = ((size_t) elt_) - 2;
- return hash_scev_info (&global_cache->entries[idx]);
+ return scev_info_hasher::hash (&global_cache->entries[idx]);
}
/* Compares database elements E1 and E2. */
eq_idx_scev_info (const void *e1, const void *e2)
{
unsigned idx1 = ((size_t) e1) - 2;
- return eq_scev_info (&global_cache->entries[idx1], e2);
+ return scev_info_hasher::equal (&global_cache->entries[idx1],
+ (const scev_info_str *) e2);
}
/* Returns from CACHE the slot number of the cached chrec for NAME. */
static unsigned
get_instantiated_value_entry (instantiate_cache_type &cache,
- tree name, basic_block instantiate_below)
+ tree name, edge instantiate_below)
{
if (!cache.map)
{
scev_info_str e;
e.name_version = SSA_NAME_VERSION (name);
- e.instantiated_below = instantiate_below->index;
+ e.instantiated_below = instantiate_below->dest->index;
void **slot = htab_find_slot_with_hash (cache.map, &e,
- hash_scev_info (&e), INSERT);
+ scev_info_hasher::hash (&e), INSERT);
if (!*slot)
{
e.chrec = chrec_not_analyzed_yet;
static tree
loop_closed_phi_def (tree var)
{
- struct loop *loop;
+ class loop *loop;
edge exit;
- gimple phi;
- gimple_stmt_iterator psi;
+ gphi *phi;
+ gphi_iterator psi;
if (var == NULL_TREE
|| TREE_CODE (var) != SSA_NAME)
for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
{
- phi = gsi_stmt (psi);
+ phi = psi.phi ();
if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
return PHI_RESULT (phi);
}
return NULL_TREE;
}
-static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
- tree, bool, int);
+static tree instantiate_scev_r (edge, class loop *, class loop *,
+ tree, bool *, int);
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
CACHE is the cache of already instantiated values.
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
+ Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
+ conversions that may wrap in signed/pointer type are folded, as long
+ as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
+ then we don't do such fold.
SIZE_EXPR is used for computing the size of the expression to be
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_name (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+instantiate_scev_name (edge instantiate_below,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec,
- bool fold_conversions,
+ bool *fold_conversions,
int size_expr)
{
tree res;
- struct loop *def_loop;
+ class loop *def_loop;
basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
- /* A parameter (or loop invariant and we do not want to include
- evolutions in outer loops), nothing to do. */
+ /* A parameter, nothing to do. */
if (!def_bb
- || loop_depth (def_bb->loop_father) == 0
- || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
+ || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
return chrec;
/* We cache the value of instantiated variable to avoid exponential
def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
+ if (! dominated_by_p (CDI_DOMINATORS,
+ def_loop->header, instantiate_below->dest))
+ {
+ gimple *def = SSA_NAME_DEF_STMT (chrec);
+ if (gassign *ass = dyn_cast <gassign *> (def))
+ {
+ switch (gimple_assign_rhs_class (ass))
+ {
+ case GIMPLE_UNARY_RHS:
+ {
+ tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+ inner_loop, gimple_assign_rhs1 (ass),
+ fold_conversions, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+ res = fold_build1 (gimple_assign_rhs_code (ass),
+ TREE_TYPE (chrec), op0);
+ break;
+ }
+ case GIMPLE_BINARY_RHS:
+ {
+ tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+ inner_loop, gimple_assign_rhs1 (ass),
+ fold_conversions, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+ tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
+ inner_loop, gimple_assign_rhs2 (ass),
+ fold_conversions, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+ res = fold_build2 (gimple_assign_rhs_code (ass),
+ TREE_TYPE (chrec), op0, op1);
+ break;
+ }
+ default:
+ res = chrec_dont_know;
+ }
+ }
+ else
+ res = chrec_dont_know;
+ global_cache->set (si, res);
+ return res;
+ }
+
/* If the analysis yields a parametric chrec, instantiate the
result again. */
res = analyze_scalar_evolution (def_loop, chrec);
inner_loop, res,
fold_conversions, size_expr);
}
- else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
- gimple_bb (SSA_NAME_DEF_STMT (res))))
+ else if (dominated_by_p (CDI_DOMINATORS,
+ gimple_bb (SSA_NAME_DEF_STMT (res)),
+ instantiate_below->dest))
res = chrec_dont_know;
}
CACHE is the cache of already instantiated values.
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
+ Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
+ conversions that may wrap in signed/pointer type are folded, as long
+ as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
+ then we don't do such fold.
SIZE_EXPR is used for computing the size of the expression to be
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_poly (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *,
- tree chrec, bool fold_conversions, int size_expr)
+instantiate_scev_poly (edge instantiate_below,
+ class loop *evolution_loop, class loop *,
+ tree chrec, bool *fold_conversions, int size_expr)
{
tree op1;
tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
CACHE is the cache of already instantiated values.
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
+ Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
+ conversions that may wrap in signed/pointer type are folded, as long
+ as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
+ then we don't do such fold.
SIZE_EXPR is used for computing the size of the expression to be
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_binary (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+instantiate_scev_binary (edge instantiate_below,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec, enum tree_code code,
tree type, tree c0, tree c1,
- bool fold_conversions, int size_expr)
+ bool *fold_conversions, int size_expr)
{
tree op1;
tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
- c1, fold_conversions, size_expr);
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
+ /* While we eventually compute the same op1 if c0 == c1 the process
+ of doing this is expensive so the following short-cut prevents
+ exponential compile-time behavior. */
+ if (c0 != c1)
+ {
+ op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
+ c1, fold_conversions, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+ }
+ else
+ op1 = op0;
if (c0 != op0
|| c1 != op1)
return chrec ? chrec : fold_build2 (code, type, c0, c1);
}
-/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
- and EVOLUTION_LOOP, that were left under a symbolic form.
-
- "CHREC" is an array reference to be instantiated.
-
- CACHE is the cache of already instantiated values.
-
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
-
- SIZE_EXPR is used for computing the size of the expression to be
- instantiated, and to stop if it exceeds some limit. */
-
-static tree
-instantiate_array_ref (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
- tree chrec, bool fold_conversions, int size_expr)
-{
- tree res;
- tree index = TREE_OPERAND (chrec, 1);
- tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, index,
- fold_conversions, size_expr);
-
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
-
- if (chrec && op1 == index)
- return chrec;
-
- res = unshare_expr (chrec);
- TREE_OPERAND (res, 1) = op1;
- return res;
-}
-
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
CACHE is the cache of already instantiated values.
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
+ Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
+ conversions that may wrap in signed/pointer type are folded, as long
+ as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
+ then we don't do such fold.
SIZE_EXPR is used for computing the size of the expression to be
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_convert (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+instantiate_scev_convert (edge instantiate_below,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec, tree type, tree op,
- bool fold_conversions, int size_expr)
+ bool *fold_conversions, int size_expr)
{
tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
inner_loop, op,
if (fold_conversions)
{
- tree tmp = chrec_convert_aggressive (type, op0);
+ tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
if (tmp)
return tmp;
- }
- if (chrec && op0 == op)
- return chrec;
+ /* If we used chrec_convert_aggressive, we can no longer assume that
+ signed chrecs do not overflow, as chrec_convert does, so avoid
+ calling it in that case. */
+ if (*fold_conversions)
+ {
+ if (chrec && op0 == op)
+ return chrec;
- /* If we used chrec_convert_aggressive, we can no longer assume that
- signed chrecs do not overflow, as chrec_convert does, so avoid
- calling it in that case. */
- if (fold_conversions)
- return fold_convert (type, op0);
+ return fold_convert (type, op0);
+ }
+ }
return chrec_convert (type, op0, NULL);
}
CACHE is the cache of already instantiated values.
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
+ Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
+ conversions that may wrap in signed/pointer type are folded, as long
+ as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
+ then we don't do such fold.
SIZE_EXPR is used for computing the size of the expression to be
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_not (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+instantiate_scev_not (edge instantiate_below,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec,
enum tree_code code, tree type, tree op,
- bool fold_conversions, int size_expr)
+ bool *fold_conversions, int size_expr)
{
tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
inner_loop, op,
return chrec ? chrec : fold_build1 (code, type, op0);
}
-/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
- and EVOLUTION_LOOP, that were left under a symbolic form.
-
- CHREC is an expression with 3 operands to be instantiated.
-
- CACHE is the cache of already instantiated values.
-
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
-
- SIZE_EXPR is used for computing the size of the expression to be
- instantiated, and to stop if it exceeds some limit. */
-
-static tree
-instantiate_scev_3 (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
- tree chrec,
- bool fold_conversions, int size_expr)
-{
- tree op1, op2;
- tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, TREE_OPERAND (chrec, 0),
- fold_conversions, size_expr);
- if (op0 == chrec_dont_know)
- return chrec_dont_know;
-
- op1 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, TREE_OPERAND (chrec, 1),
- fold_conversions, size_expr);
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
-
- op2 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, TREE_OPERAND (chrec, 2),
- fold_conversions, size_expr);
- if (op2 == chrec_dont_know)
- return chrec_dont_know;
-
- if (op0 == TREE_OPERAND (chrec, 0)
- && op1 == TREE_OPERAND (chrec, 1)
- && op2 == TREE_OPERAND (chrec, 2))
- return chrec;
-
- return fold_build3 (TREE_CODE (chrec),
- TREE_TYPE (chrec), op0, op1, op2);
-}
-
-/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
- and EVOLUTION_LOOP, that were left under a symbolic form.
-
- CHREC is an expression with 2 operands to be instantiated.
-
- CACHE is the cache of already instantiated values.
-
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
-
- SIZE_EXPR is used for computing the size of the expression to be
- instantiated, and to stop if it exceeds some limit. */
-
-static tree
-instantiate_scev_2 (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
- tree chrec,
- bool fold_conversions, int size_expr)
-{
- tree op1;
- tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, TREE_OPERAND (chrec, 0),
- fold_conversions, size_expr);
- if (op0 == chrec_dont_know)
- return chrec_dont_know;
-
- op1 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, TREE_OPERAND (chrec, 1),
- fold_conversions, size_expr);
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
-
- if (op0 == TREE_OPERAND (chrec, 0)
- && op1 == TREE_OPERAND (chrec, 1))
- return chrec;
-
- return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
-}
-
-/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
- and EVOLUTION_LOOP, that were left under a symbolic form.
-
- CHREC is an expression with 2 operands to be instantiated.
-
- CACHE is the cache of already instantiated values.
-
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
-
- SIZE_EXPR is used for computing the size of the expression to be
- instantiated, and to stop if it exceeds some limit. */
-
-static tree
-instantiate_scev_1 (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
- tree chrec,
- bool fold_conversions, int size_expr)
-{
- tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
- inner_loop, TREE_OPERAND (chrec, 0),
- fold_conversions, size_expr);
-
- if (op0 == chrec_dont_know)
- return chrec_dont_know;
-
- if (op0 == TREE_OPERAND (chrec, 0))
- return chrec;
-
- return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
-}
-
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
CACHE is the cache of already instantiated values.
- FOLD_CONVERSIONS should be set to true when the conversions that
- may wrap in signed/pointer type are folded, as long as the value of
- the chrec is preserved.
+ Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
+ conversions that may wrap in signed/pointer type are folded, as long
+ as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
+ then we don't do such fold.
SIZE_EXPR is used for computing the size of the expression to be
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_r (basic_block instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+instantiate_scev_r (edge instantiate_below,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec,
- bool fold_conversions, int size_expr)
+ bool *fold_conversions, int size_expr)
{
/* Give up if the expression is larger than the MAX that we allow. */
- if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+ if (size_expr++ > param_scev_max_expr_size)
return chrec_dont_know;
if (chrec == NULL_TREE
fold_conversions, size_expr);
case ADDR_EXPR:
+ if (is_gimple_min_invariant (chrec))
+ return chrec;
+ /* Fallthru. */
case SCEV_NOT_KNOWN:
return chrec_dont_know;
case SCEV_KNOWN:
return chrec_known;
- case ARRAY_REF:
- return instantiate_array_ref (instantiate_below, evolution_loop,
- inner_loop, chrec,
- fold_conversions, size_expr);
-
default:
- break;
- }
-
- if (VL_EXP_CLASS_P (chrec))
- return chrec_dont_know;
-
- switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
- {
- case 3:
- return instantiate_scev_3 (instantiate_below, evolution_loop,
- inner_loop, chrec,
- fold_conversions, size_expr);
-
- case 2:
- return instantiate_scev_2 (instantiate_below, evolution_loop,
- inner_loop, chrec,
- fold_conversions, size_expr);
-
- case 1:
- return instantiate_scev_1 (instantiate_below, evolution_loop,
- inner_loop, chrec,
- fold_conversions, size_expr);
-
- case 0:
- return chrec;
-
- default:
- break;
+ if (CONSTANT_CLASS_P (chrec))
+ return chrec;
+ return chrec_dont_know;
}
-
- /* Too complicated to handle. */
- return chrec_dont_know;
}
/* Analyze all the parameters of the chrec that were left under a
a function parameter. */
tree
-instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
+instantiate_scev (edge instantiate_below, class loop *evolution_loop,
tree chrec)
{
tree res;
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(instantiate_scev \n");
- fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
- fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
+ fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
+ instantiate_below->src->index, instantiate_below->dest->index);
+ if (evolution_loop)
+ fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
fprintf (dump_file, " (chrec = ");
- print_generic_expr (dump_file, chrec, 0);
+ print_generic_expr (dump_file, chrec);
fprintf (dump_file, ")\n");
}
}
res = instantiate_scev_r (instantiate_below, evolution_loop,
- NULL, chrec, false, 0);
+ NULL, chrec, NULL, 0);
if (destr)
{
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (res = ");
- print_generic_expr (dump_file, res, 0);
+ print_generic_expr (dump_file, res);
fprintf (dump_file, "))\n");
}
of an expression. */
tree
-resolve_mixers (struct loop *loop, tree chrec)
+resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
{
bool destr = false;
+ bool fold_conversions = false;
if (!global_cache)
{
global_cache = new instantiate_cache_type;
destr = true;
}
- tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
- chrec, true, 0);
+ tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
+ chrec, &fold_conversions, 0);
+
+ if (folded_casts && !*folded_casts)
+ *folded_casts = fold_conversions;
if (destr)
{
the loop body has been executed 6 times. */
tree
-number_of_latch_executions (struct loop *loop)
+number_of_latch_executions (class loop *loop)
{
edge exit;
- struct tree_niter_desc niter_desc;
+ class tree_niter_desc niter_desc;
tree may_be_zero;
tree res;
if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (set_nb_iterations_in_loop = ");
- print_generic_expr (dump_file, res, 0);
+ print_generic_expr (dump_file, res);
fprintf (dump_file, "))\n");
}
stats->nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
- (int) htab_elements (scalar_evolution_info));
+ (int) scalar_evolution_info->elements ());
fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
fprintf (file, "-----------------------------------------\n");
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "(classify_chrec ");
- print_generic_expr (dump_file, chrec, 0);
+ print_generic_expr (dump_file, chrec);
fprintf (dump_file, "\n");
}
fprintf (dump_file, ")\n");
}
-/* Callback for htab_traverse, gathers information on chrecs in the
- hashtable. */
-
-static int
-gather_stats_on_scev_database_1 (void **slot, void *stats)
-{
- struct scev_info_str *entry = (struct scev_info_str *) *slot;
-
- gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
-
- return 1;
-}
-
/* Classify the chrecs of the whole database. */
void
reset_chrecs_counters (&stats);
- htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
- &stats);
+ hash_table<scev_info_hasher>::iterator iter;
+ scev_info_str *elt;
+ FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
+ iter)
+ gather_chrec_stats (elt->chrec, &stats);
dump_chrecs_stats (dump_file, &stats);
}
\f
-
-/* Initializer. */
-
-static void
-initialize_scalar_evolutions_analyzer (void)
-{
- /* The elements below are unique. */
- if (chrec_dont_know == NULL_TREE)
- {
- chrec_not_analyzed_yet = NULL_TREE;
- chrec_dont_know = make_node (SCEV_NOT_KNOWN);
- chrec_known = make_node (SCEV_KNOWN);
- TREE_TYPE (chrec_dont_know) = void_type_node;
- TREE_TYPE (chrec_known) = void_type_node;
- }
-}
-
/* Initialize the analysis of scalar evolutions for LOOPS. */
void
scev_initialize (void)
{
- struct loop *loop;
+ gcc_assert (! scev_initialized_p ());
- scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
- del_scev_info);
+ scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
- initialize_scalar_evolutions_analyzer ();
-
- FOR_EACH_LOOP (loop, 0)
- {
- loop->nb_iterations = NULL_TREE;
- }
+ for (auto loop : loops_list (cfun, 0))
+ loop->nb_iterations = NULL_TREE;
}
/* Return true if SCEV is initialized. */
if (!scalar_evolution_info)
return;
- htab_empty (scalar_evolution_info);
+ scalar_evolution_info->empty ();
}
/* Cleans up the information cached by the scalar evolutions analysis
void
scev_reset (void)
{
- struct loop *loop;
-
scev_reset_htab ();
- FOR_EACH_LOOP (loop, 0)
+ for (auto loop : loops_list (cfun, 0))
+ loop->nb_iterations = NULL_TREE;
+}
+
+/* Return true if the IV calculation in TYPE can overflow based on the knowledge
+ of the upper bound on the number of iterations of LOOP, the BASE and STEP
+ of IV.
+
+ We do not use information whether TYPE can overflow so it is safe to
+ use this test even for derived IVs not computed every iteration or
+ hypotetical IVs to be inserted into code. */
+
+bool
+iv_can_overflow_p (class loop *loop, tree type, tree base, tree step)
+{
+ widest_int nit;
+ wide_int base_min, base_max, step_min, step_max, type_min, type_max;
+ signop sgn = TYPE_SIGN (type);
+ value_range r;
+
+ if (integer_zerop (step))
+ return false;
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (base))
+ || !get_range_query (cfun)->range_of_expr (r, base)
+ || r.kind () != VR_RANGE)
+ return true;
+
+ base_min = r.lower_bound ();
+ base_max = r.upper_bound ();
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (step))
+ || !get_range_query (cfun)->range_of_expr (r, step)
+ || r.kind () != VR_RANGE)
+ return true;
+
+ step_min = r.lower_bound ();
+ step_max = r.upper_bound ();
+
+ if (!get_max_loop_iterations (loop, &nit))
+ return true;
+
+ type_min = wi::min_value (type);
+ type_max = wi::max_value (type);
+
+ /* Just sanity check that we don't see values out of the range of the type.
+ In this case the arithmetics bellow would overflow. */
+ gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
+ && wi::le_p (base_max, type_max, sgn));
+
+ /* Account the possible increment in the last ieration. */
+ wi::overflow_type overflow = wi::OVF_NONE;
+ nit = wi::add (nit, 1, SIGNED, &overflow);
+ if (overflow)
+ return true;
+
+ /* NIT is typeless and can exceed the precision of the type. In this case
+ overflow is always possible, because we know STEP is non-zero. */
+ if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
+ return true;
+ wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
+
+ /* If step can be positive, check that nit*step <= type_max-base.
+ This can be done by unsigned arithmetic and we only need to watch overflow
+ in the multiplication. The right hand side can always be represented in
+ the type. */
+ if (sgn == UNSIGNED || !wi::neg_p (step_max))
+ {
+ wi::overflow_type overflow = wi::OVF_NONE;
+ if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
+ type_max - base_max)
+ || overflow)
+ return true;
+ }
+ /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
+ if (sgn == SIGNED && wi::neg_p (step_min))
{
- loop->nb_iterations = NULL_TREE;
+ wi::overflow_type overflow, overflow2;
+ overflow = overflow2 = wi::OVF_NONE;
+ if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
+ nit2, UNSIGNED, &overflow),
+ base_min - type_min)
+ || overflow || overflow2)
+ return true;
}
+
+ return false;
+}
+
+/* Given EV with form of "(type) {inner_base, inner_step}_loop", this
+ function tries to derive condition under which it can be simplified
+ into "{(type)inner_base, (type)inner_step}_loop". The condition is
+ the maximum number that inner iv can iterate. */
+
+static tree
+derive_simple_iv_with_niters (tree ev, tree *niters)
+{
+ if (!CONVERT_EXPR_P (ev))
+ return ev;
+
+ tree inner_ev = TREE_OPERAND (ev, 0);
+ if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
+ return ev;
+
+ tree init = CHREC_LEFT (inner_ev);
+ tree step = CHREC_RIGHT (inner_ev);
+ if (TREE_CODE (init) != INTEGER_CST
+ || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
+ return ev;
+
+ tree type = TREE_TYPE (ev);
+ tree inner_type = TREE_TYPE (inner_ev);
+ if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
+ return ev;
+
+ /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
+ folded only if inner iv won't overflow. We compute the maximum
+ number the inner iv can iterate before overflowing and return the
+ simplified affine iv. */
+ tree delta;
+ init = fold_convert (type, init);
+ step = fold_convert (type, step);
+ ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
+ if (tree_int_cst_sign_bit (step))
+ {
+ tree bound = lower_bound_in_type (inner_type, inner_type);
+ delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
+ step = fold_build1 (NEGATE_EXPR, type, step);
+ }
+ else
+ {
+ tree bound = upper_bound_in_type (inner_type, inner_type);
+ delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
+ }
+ *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
+ return ev;
}
/* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
not wrap by some other argument. Otherwise, this might introduce undefined
behavior, and
- for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
+ i = iv->base;
+ for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
+
+ must be used instead.
+
+ When IV_NITERS is not NULL, this function also checks case in which OP
+ is a conversion of an inner simple iv of below form:
- must be used instead. */
+ (outer_type){inner_base, inner_step}_loop.
+
+ If type of inner iv has smaller precision than outer_type, it can't be
+ folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
+ the inner iv could overflow/wrap. In this case, we derive a condition
+ under which the inner iv won't overflow/wrap and do the simplification.
+ The derived condition normally is the maximum number the inner iv can
+ iterate, and will be stored in IV_NITERS. This is useful in loop niter
+ analysis, to derive break conditions when a loop must terminate, when is
+ infinite. */
bool
-simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
- affine_iv *iv, bool allow_nonconstant_step)
+simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
+ tree op, affine_iv *iv, tree *iv_niters,
+ bool allow_nonconstant_step)
{
- tree type, ev;
+ enum tree_code code;
+ tree type, ev, base, e;
+ wide_int extreme;
bool folded_casts;
iv->base = NULL_TREE;
return true;
}
- if (TREE_CODE (ev) != POLYNOMIAL_CHREC
- || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
+ /* If we can derive valid scalar evolution with assumptions. */
+ if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
+ ev = derive_simple_iv_with_niters (ev, iv_niters);
+
+ if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
+ return false;
+
+ if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
return false;
iv->step = CHREC_RIGHT (ev);
if (tree_contains_chrecs (iv->base, NULL))
return false;
- iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
+ iv->no_overflow = !folded_casts && nowrap_type_p (type);
+
+ if (!iv->no_overflow
+ && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
+ iv->no_overflow = true;
+
+ /* Try to simplify iv base:
+
+ (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
+ == (signed T)(unsigned T)base + step
+ == base + step
+
+ If we can prove operation (base + step) doesn't overflow or underflow.
+ Specifically, we try to prove below conditions are satisfied:
+
+ base <= UPPER_BOUND (type) - step ;;step > 0
+ base >= LOWER_BOUND (type) - step ;;step < 0
+
+ This is done by proving the reverse conditions are false using loop's
+ initial conditions.
+
+ The is necessary to make loop niter, or iv overflow analysis easier
+ for below example:
+
+ int foo (int *a, signed char s, signed char l)
+ {
+ signed char i;
+ for (i = s; i < l; i++)
+ a[i] = 0;
+ return 0;
+ }
+
+ Note variable I is firstly converted to type unsigned char, incremented,
+ then converted back to type signed char. */
+
+ if (wrto_loop->num != use_loop->num)
+ return true;
+
+ if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
+ return true;
+
+ type = TREE_TYPE (iv->base);
+ e = TREE_OPERAND (iv->base, 0);
+ if (TREE_CODE (e) != PLUS_EXPR
+ || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
+ || !tree_int_cst_equal (iv->step,
+ fold_convert (type, TREE_OPERAND (e, 1))))
+ return true;
+ e = TREE_OPERAND (e, 0);
+ if (!CONVERT_EXPR_P (e))
+ return true;
+ base = TREE_OPERAND (e, 0);
+ if (!useless_type_conversion_p (type, TREE_TYPE (base)))
+ return true;
+
+ if (tree_int_cst_sign_bit (iv->step))
+ {
+ code = LT_EXPR;
+ extreme = wi::min_value (type);
+ }
+ else
+ {
+ code = GT_EXPR;
+ extreme = wi::max_value (type);
+ }
+ wi::overflow_type overflow = wi::OVF_NONE;
+ extreme = wi::sub (extreme, wi::to_wide (iv->step),
+ TYPE_SIGN (type), &overflow);
+ if (overflow)
+ return true;
+ e = fold_build2 (code, boolean_type_node, base,
+ wide_int_to_tree (type, extreme));
+ e = simplify_using_initial_conditions (use_loop, e);
+ if (!integer_zerop (e))
+ return true;
+
+ if (POINTER_TYPE_P (TREE_TYPE (base)))
+ code = POINTER_PLUS_EXPR;
+ else
+ code = PLUS_EXPR;
+ iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
return true;
}
+/* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
+ affine iv unconditionally. */
+
+bool
+simple_iv (class loop *wrto_loop, class loop *use_loop, tree op,
+ affine_iv *iv, bool allow_nonconstant_step)
+{
+ return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
+ NULL, allow_nonconstant_step);
+}
+
/* Finalize the scalar evolution analysis. */
void
{
if (!scalar_evolution_info)
return;
- htab_delete (scalar_evolution_info);
+ scalar_evolution_info->empty ();
scalar_evolution_info = NULL;
+ free_numbers_of_iterations_estimates (cfun);
}
/* Returns true if the expression EXPR is considered to be too expensive
for scev_const_prop. */
-bool
-expression_expensive_p (tree expr)
+static bool
+expression_expensive_p (tree expr, hash_map<tree, uint64_t> &cache,
+ uint64_t &cost)
{
enum tree_code code;
return true;
}
+ bool visited_p;
+ uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
+ if (visited_p)
+ {
+ uint64_t tem = cost + local_cost;
+ if (tem < cost)
+ return true;
+ cost = tem;
+ return false;
+ }
+ local_cost = 1;
+
+ uint64_t op_cost = 0;
+ if (code == CALL_EXPR)
+ {
+ tree arg;
+ call_expr_arg_iterator iter;
+ /* Even though is_inexpensive_builtin might say true, we will get a
+ library call for popcount when backend does not have an instruction
+ to do so. We consider this to be expenseive and generate
+ __builtin_popcount only when backend defines it. */
+ combined_fn cfn = get_call_combined_fn (expr);
+ switch (cfn)
+ {
+ CASE_CFN_POPCOUNT:
+ /* Check if opcode for popcount is available in the mode required. */
+ if (optab_handler (popcount_optab,
+ TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
+ == CODE_FOR_nothing)
+ {
+ machine_mode mode;
+ mode = TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)));
+ scalar_int_mode int_mode;
+
+ /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
+ double-word popcount by emitting two single-word popcount
+ instructions. */
+ if (is_a <scalar_int_mode> (mode, &int_mode)
+ && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
+ && (optab_handler (popcount_optab, word_mode)
+ != CODE_FOR_nothing))
+ break;
+ return true;
+ }
+ default:
+ break;
+ }
+
+ if (!is_inexpensive_builtin (get_callee_fndecl (expr)))
+ return true;
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
+ if (expression_expensive_p (arg, cache, op_cost))
+ return true;
+ *cache.get (expr) += op_cost;
+ cost += op_cost + 1;
+ return false;
+ }
+
+ if (code == COND_EXPR)
+ {
+ if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost)
+ || (EXPR_P (TREE_OPERAND (expr, 1))
+ && EXPR_P (TREE_OPERAND (expr, 2)))
+ /* If either branch has side effects or could trap. */
+ || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
+ || generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
+ || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
+ || generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
+ || expression_expensive_p (TREE_OPERAND (expr, 1),
+ cache, op_cost)
+ || expression_expensive_p (TREE_OPERAND (expr, 2),
+ cache, op_cost))
+ return true;
+ *cache.get (expr) += op_cost;
+ cost += op_cost + 1;
+ return false;
+ }
+
switch (TREE_CODE_CLASS (code))
{
case tcc_binary:
case tcc_comparison:
- if (expression_expensive_p (TREE_OPERAND (expr, 1)))
+ if (expression_expensive_p (TREE_OPERAND (expr, 1), cache, op_cost))
return true;
/* Fallthru. */
case tcc_unary:
- return expression_expensive_p (TREE_OPERAND (expr, 0));
+ if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost))
+ return true;
+ *cache.get (expr) += op_cost;
+ cost += op_cost + 1;
+ return false;
default:
return true;
}
}
-/* Replace ssa names for that scev can prove they are constant by the
- appropriate constants. Also perform final value replacement in loops,
- in case the replacement expressions are cheap.
-
- We only consider SSA names defined by phi nodes; rest is left to the
- ordinary constant propagation pass. */
-
-unsigned int
-scev_const_prop (void)
+bool
+expression_expensive_p (tree expr)
{
- basic_block bb;
- tree name, type, ev;
- gimple phi, ass;
- struct loop *loop, *ex_loop;
- bitmap ssa_names_to_remove = NULL;
- unsigned i;
- gimple_stmt_iterator psi;
-
- if (number_of_loops (cfun) <= 1)
- return 0;
-
- FOR_EACH_BB_FN (bb, cfun)
- {
- loop = bb->loop_father;
-
- for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
- {
- phi = gsi_stmt (psi);
- name = PHI_RESULT (phi);
+ hash_map<tree, uint64_t> cache;
+ uint64_t expanded_size = 0;
+ return (expression_expensive_p (expr, cache, expanded_size)
+ || expanded_size > cache.elements ());
+}
- if (virtual_operand_p (name))
- continue;
+/* Do final value replacement for LOOP, return true if we did anything. */
- type = TREE_TYPE (name);
+bool
+final_value_replacement_loop (class loop *loop)
+{
+ /* If we do not know exact number of iterations of the loop, we cannot
+ replace the final value. */
+ edge exit = single_exit (loop);
+ if (!exit)
+ return false;
- if (!POINTER_TYPE_P (type)
- && !INTEGRAL_TYPE_P (type))
- continue;
+ tree niter = number_of_latch_executions (loop);
+ if (niter == chrec_dont_know)
+ return false;
- ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
- if (!is_gimple_min_invariant (ev)
- || !may_propagate_copy (name, ev))
- continue;
+ /* Ensure that it is possible to insert new statements somewhere. */
+ if (!single_pred_p (exit->dest))
+ split_loop_exit_edge (exit);
- /* Replace the uses of the name. */
- if (name != ev)
- replace_uses_by (name, ev);
+ /* Set stmt insertion pointer. All stmts are inserted before this point. */
+ gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
- if (!ssa_names_to_remove)
- ssa_names_to_remove = BITMAP_ALLOC (NULL);
- bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
- }
- }
+ class loop *ex_loop
+ = superloop_at_depth (loop,
+ loop_depth (exit->dest->loop_father) + 1);
- /* Remove the ssa names that were replaced by constants. We do not
- remove them directly in the previous cycle, since this
- invalidates scev cache. */
- if (ssa_names_to_remove)
+ bool any = false;
+ gphi_iterator psi;
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
{
- bitmap_iterator bi;
-
- EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
+ gphi *phi = psi.phi ();
+ tree rslt = PHI_RESULT (phi);
+ tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ if (virtual_operand_p (def))
{
- gimple_stmt_iterator psi;
- name = ssa_name (i);
- phi = SSA_NAME_DEF_STMT (name);
-
- gcc_assert (gimple_code (phi) == GIMPLE_PHI);
- psi = gsi_for_stmt (phi);
- remove_phi_node (&psi, true);
+ gsi_next (&psi);
+ continue;
}
- BITMAP_FREE (ssa_names_to_remove);
- scev_reset ();
- }
-
- /* Now the regular final value replacement. */
- FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
- {
- edge exit;
- tree def, rslt, niter;
- gimple_stmt_iterator gsi;
-
- /* If we do not know exact number of iterations of the loop, we cannot
- replace the final value. */
- exit = single_exit (loop);
- if (!exit)
- continue;
-
- niter = number_of_latch_executions (loop);
- if (niter == chrec_dont_know)
- continue;
-
- /* Ensure that it is possible to insert new statements somewhere. */
- if (!single_pred_p (exit->dest))
- split_loop_exit_edge (exit);
- gsi = gsi_after_labels (exit->dest);
-
- ex_loop = superloop_at_depth (loop,
- loop_depth (exit->dest->loop_father) + 1);
-
- for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
+ if (!POINTER_TYPE_P (TREE_TYPE (def))
+ && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
{
- phi = gsi_stmt (psi);
- rslt = PHI_RESULT (phi);
- def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
- if (virtual_operand_p (def))
- {
- gsi_next (&psi);
- continue;
- }
-
- if (!POINTER_TYPE_P (TREE_TYPE (def))
- && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
- {
- gsi_next (&psi);
- continue;
- }
-
- bool folded_casts;
- def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
- &folded_casts);
- def = compute_overall_effect_of_inner_loop (ex_loop, def);
- if (!tree_does_not_contain_chrecs (def)
- || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
- /* Moving the computation from the loop may prolong life range
- of some ssa names, which may cause problems if they appear
- on abnormal edges. */
- || contains_abnormal_ssa_name_p (def)
- /* Do not emit expensive expressions. The rationale is that
- when someone writes a code like
-
- while (n > 45) n -= 45;
-
- he probably knows that n is not large, and does not want it
- to be turned into n %= 45. */
- || expression_expensive_p (def))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "not replacing:\n ");
- print_gimple_stmt (dump_file, phi, 0, 0);
- fprintf (dump_file, "\n");
- }
- gsi_next (&psi);
- continue;
- }
-
- /* Eliminate the PHI node and replace it by a computation outside
- the loop. */
- if (dump_file)
- {
- fprintf (dump_file, "\nfinal value replacement:\n ");
- print_gimple_stmt (dump_file, phi, 0, 0);
- fprintf (dump_file, " with\n ");
- }
- def = unshare_expr (def);
- remove_phi_node (&psi, false);
+ gsi_next (&psi);
+ continue;
+ }
- /* If def's type has undefined overflow and there were folded
- casts, rewrite all stmts added for def into arithmetics
- with defined overflow behavior. */
- if (folded_casts && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
+ bool folded_casts;
+ def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
+ &folded_casts);
+ def = compute_overall_effect_of_inner_loop (ex_loop, def);
+ if (!tree_does_not_contain_chrecs (def)
+ || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
+ /* Moving the computation from the loop may prolong life range
+ of some ssa names, which may cause problems if they appear
+ on abnormal edges. */
+ || contains_abnormal_ssa_name_p (def)
+ /* Do not emit expensive expressions. The rationale is that
+ when someone writes a code like
+
+ while (n > 45) n -= 45;
+
+ he probably knows that n is not large, and does not want it
+ to be turned into n %= 45. */
+ || expression_expensive_p (def))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- gimple_seq stmts;
- gimple_stmt_iterator gsi2;
- def = force_gimple_operand (def, &stmts, true, NULL_TREE);
- gsi2 = gsi_start (stmts);
- while (!gsi_end_p (gsi2))
- {
- gimple stmt = gsi_stmt (gsi2);
- gimple_stmt_iterator gsi3 = gsi2;
- gsi_next (&gsi2);
- gsi_remove (&gsi3, false);
- if (is_gimple_assign (stmt)
- && arith_code_with_undefined_signed_overflow
- (gimple_assign_rhs_code (stmt)))
- gsi_insert_seq_before (&gsi,
- rewrite_to_defined_overflow (stmt),
- GSI_SAME_STMT);
- else
- gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
- }
+ fprintf (dump_file, "not replacing:\n ");
+ print_gimple_stmt (dump_file, phi, 0);
+ fprintf (dump_file, "\n");
}
- else
- def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
- true, GSI_SAME_STMT);
+ gsi_next (&psi);
+ continue;
+ }
- ass = gimple_build_assign (rslt, def);
- gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
- if (dump_file)
+ /* Eliminate the PHI node and replace it by a computation outside
+ the loop. */
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nfinal value replacement:\n ");
+ print_gimple_stmt (dump_file, phi, 0);
+ fprintf (dump_file, " with expr: ");
+ print_generic_expr (dump_file, def);
+ }
+ any = true;
+ def = unshare_expr (def);
+ remove_phi_node (&psi, false);
+
+ /* If def's type has undefined overflow and there were folded
+ casts, rewrite all stmts added for def into arithmetics
+ with defined overflow behavior. */
+ if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
+ && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
+ {
+ gimple_seq stmts;
+ gimple_stmt_iterator gsi2;
+ def = force_gimple_operand (def, &stmts, true, NULL_TREE);
+ gsi2 = gsi_start (stmts);
+ while (!gsi_end_p (gsi2))
{
- print_gimple_stmt (dump_file, ass, 0, 0);
- fprintf (dump_file, "\n");
+ gimple *stmt = gsi_stmt (gsi2);
+ gimple_stmt_iterator gsi3 = gsi2;
+ gsi_next (&gsi2);
+ gsi_remove (&gsi3, false);
+ if (is_gimple_assign (stmt)
+ && arith_code_with_undefined_signed_overflow
+ (gimple_assign_rhs_code (stmt)))
+ gsi_insert_seq_before (&gsi,
+ rewrite_to_defined_overflow (stmt),
+ GSI_SAME_STMT);
+ else
+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
}
}
+ else
+ def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
+ true, GSI_SAME_STMT);
+
+ gassign *ass = gimple_build_assign (rslt, def);
+ gimple_set_location (ass,
+ gimple_phi_arg_location (phi, exit->dest_idx));
+ gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
+ if (dump_file)
+ {
+ fprintf (dump_file, "\n final stmt:\n ");
+ print_gimple_stmt (dump_file, ass, 0);
+ fprintf (dump_file, "\n");
+ }
}
- return 0;
+
+ return any;
}
#include "gt-tree-scalar-evolution.h"
projects / thirdparty / gcc.git / blobdiff