/* Scalar evolution detector.
- Copyright (C) 2003-2018 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 "system.h"
#include "coretypes.h"
#include "backend.h"
+#include "target.h"
#include "rtl.h"
+#include "optabs-query.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.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 "tree-into-ssa.h"
+#include "builtins.h"
+#include "case-cfn-macros.h"
-static tree analyze_scalar_evolution_1 (struct loop *, 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,
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);
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
*/
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))
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))
{
analyze, then give up. */
gcond *
-get_loop_exit_condition (const struct loop *loop)
+get_loop_exit_condition (const class loop *loop)
{
gcond *res = NULL;
edge exit_edge = single_exit (loop);
gimple *stmt;
stmt = last_stmt (exit_edge->src);
- if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+ if (gcond *cond_stmt = safe_dyn_cast <gcond *> (stmt))
res = cond_stmt;
}
};
-static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *,
- 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,
gphi *halting_phi, tree *evolution_of_loop,
int limit)
(loop->num,
chrec_convert (type, evol, at_stmt),
code, rhs1, at_stmt);
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
+ 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)
(loop->num,
chrec_convert (type, *evolution_of_loop, at_stmt),
code, rhs0, at_stmt);
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
+ res = follow_ssa_edge_expr
+ (loop, at_stmt, rhs1, halting_phi,
evolution_of_loop, limit);
- if (res == t_true)
- ;
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
}
-
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
}
else
- {
- /* Match an assignment under the form:
- "a = b + ...". */
- *evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type, *evolution_of_loop,
- at_stmt),
- code, rhs1, at_stmt);
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop, limit);
- if (res == t_true)
- ;
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
- }
+ gcc_unreachable (); /* Handled in caller. */
}
else if (TREE_CODE (rhs1) == SSA_NAME)
(loop->num, chrec_convert (type, *evolution_of_loop,
at_stmt),
code, rhs0, at_stmt);
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
+ res = follow_ssa_edge_expr
+ (loop, at_stmt, rhs1, halting_phi,
evolution_of_loop, limit);
- if (res == t_true)
- ;
- else if (res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
}
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++;
-
- *evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
- MINUS_EXPR, rhs1, at_stmt);
- res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop, limit);
- if (res == t_true)
- ;
- 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,
- gphi *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,
- gphi *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
static inline t_bool
follow_ssa_edge_in_condition_phi_branch (int i,
- struct loop *loop,
+ class loop *loop,
gphi *condition_phi,
gphi *halting_phi,
tree *evolution_of_branch,
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,
+follow_ssa_edge_in_condition_phi (class loop *loop,
gphi *condition_phi,
gphi *halting_phi,
tree *evolution_of_loop, int limit)
considered as a single statement. */
static t_bool
-follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
+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, gphi *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. */
- /* 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;
+ /* 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);
- def_loop = loop_containing_stmt (def);
+ if (gimple_nop_p (def))
+ return t_false;
- 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, as_a <gphi *> (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;
+ /* 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;
+ }
+
+ 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, as_a <gphi *> (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;
+ }
+ }
- /* Outer loop. */
+ 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;
+ }
+
+ 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);
{
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;
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
{
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))
{
/* Analyze the scalar evolution for LOOP_PHI_NODE. */
static tree
-interpret_loop_phi (struct loop *loop, gphi *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;
gcc_assert (phi_loop == loop);
analyzed. */
static tree
-interpret_condition_phi (struct loop *loop, gphi *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;
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, ctype;
/* 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);
/* Helper recursive function. */
static tree
-analyze_scalar_evolution_1 (struct loop *loop, tree var)
+analyze_scalar_evolution_1 (class loop *loop, tree var)
{
gimple *def;
basic_block bb;
- struct loop *def_loop;
+ class loop *def_loop;
tree res;
if (TREE_CODE (var) != SSA_NAME)
if (loop != def_loop)
{
res = analyze_scalar_evolution_1 (def_loop, var);
- struct loop *loop_to_skip = superloop_at_depth (def_loop,
+ 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))
*/
tree
-analyze_scalar_evolution (struct loop *loop, tree var)
+analyze_scalar_evolution (class loop *loop, tree var)
{
tree res;
res = get_scalar_evolution (block_before_loop (loop), var);
if (res == chrec_not_analyzed_yet)
- res = analyze_scalar_evolution_1 (loop, var);
+ {
+ /* 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;
}
-/* 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
static tree
loop_closed_phi_def (tree var)
{
- struct loop *loop;
+ class loop *loop;
edge exit;
gphi *phi;
gphi_iterator psi;
return NULL_TREE;
}
-static tree instantiate_scev_r (edge, struct loop *, struct loop *,
+static tree instantiate_scev_r (edge, class loop *, class loop *,
tree, bool *, int);
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
static tree
instantiate_scev_name (edge instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec,
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, nothing to do. */
static tree
instantiate_scev_poly (edge instantiate_below,
- struct loop *evolution_loop, struct loop *,
+ class loop *evolution_loop, class loop *,
tree chrec, bool *fold_conversions, int size_expr)
{
tree op1;
static tree
instantiate_scev_binary (edge instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+ 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)
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)
static tree
instantiate_scev_convert (edge instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec, tree type, tree op,
bool *fold_conversions, int size_expr)
{
static tree
instantiate_scev_not (edge instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec,
enum tree_code code, tree type, tree op,
bool *fold_conversions, int size_expr)
static tree
instantiate_scev_r (edge instantiate_below,
- struct loop *evolution_loop, struct loop *inner_loop,
+ class loop *evolution_loop, class loop *inner_loop,
tree chrec,
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
a function parameter. */
tree
-instantiate_scev (edge instantiate_below, struct loop *evolution_loop,
+instantiate_scev (edge instantiate_below, class loop *evolution_loop,
tree chrec)
{
tree res;
of an expression. */
tree
-resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
+resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
{
bool destr = false;
bool fold_conversions = false;
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;
}
\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 = 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. */
void
scev_reset (void)
{
- struct loop *loop;
-
scev_reset_htab ();
- 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 the IV calculation in TYPE can overflow based on the knowledge
hypotetical IVs to be inserted into code. */
bool
-iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
+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 (TREE_CODE (base) == INTEGER_CST)
- base_min = base_max = wi::to_wide (base);
- else if (TREE_CODE (base) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (base))
- && get_range_info (base, &base_min, &base_max) == VR_RANGE)
- ;
- else
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (base))
+ || !get_range_query (cfun)->range_of_expr (r, base)
+ || r.kind () != VR_RANGE)
return true;
- if (TREE_CODE (step) == INTEGER_CST)
- step_min = step_max = wi::to_wide (step);
- else if (TREE_CODE (step) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (step))
- && get_range_info (step, &step_min, &step_max) == VR_RANGE)
- ;
- else
+ 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;
&& wi::le_p (base_max, type_max, sgn));
/* Account the possible increment in the last ieration. */
- bool overflow = false;
+ wi::overflow_type overflow = wi::OVF_NONE;
nit = wi::add (nit, 1, SIGNED, &overflow);
if (overflow)
return true;
the type. */
if (sgn == UNSIGNED || !wi::neg_p (step_max))
{
- bool overflow = false;
+ wi::overflow_type overflow = wi::OVF_NONE;
if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
type_max - base_max)
|| overflow)
/* If step can be negative, check that nit*(-step) <= base_min-type_min. */
if (sgn == SIGNED && wi::neg_p (step_min))
{
- bool overflow = false, overflow2 = false;
+ 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)
infinite. */
bool
-simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop,
+simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
tree op, affine_iv *iv, tree *iv_niters,
bool allow_nonconstant_step)
{
enum tree_code code;
tree type, ev, base, e;
wide_int extreme;
- bool folded_casts, overflow;
+ bool folded_casts;
iv->base = NULL_TREE;
iv->step = NULL_TREE;
code = GT_EXPR;
extreme = wi::max_value (type);
}
- overflow = false;
+ wi::overflow_type overflow = wi::OVF_NONE;
extreme = wi::sub (extreme, wi::to_wide (iv->step),
TYPE_SIGN (type), &overflow);
if (overflow)
affine iv unconditionally. */
bool
-simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
+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,
/* 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;
}
}
-/* Do final value replacement for LOOP. */
+bool
+expression_expensive_p (tree expr)
+{
+ hash_map<tree, uint64_t> cache;
+ uint64_t expanded_size = 0;
+ return (expression_expensive_p (expr, cache, expanded_size)
+ || expanded_size > cache.elements ());
+}
-void
-final_value_replacement_loop (struct loop *loop)
+/* Do final value replacement for LOOP, return true if we did anything. */
+
+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;
+ return false;
tree niter = number_of_latch_executions (loop);
if (niter == chrec_dont_know)
- return;
+ return false;
/* Ensure that it is possible to insert new statements somewhere. */
if (!single_pred_p (exit->dest))
/* Set stmt insertion pointer. All stmts are inserted before this point. */
gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
- struct loop *ex_loop
+ class loop *ex_loop
= superloop_at_depth (loop,
loop_depth (exit->dest->loop_father) + 1);
+ bool any = false;
gphi_iterator psi;
for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
{
{
fprintf (dump_file, "\nfinal value replacement:\n ");
print_gimple_stmt (dump_file, phi, 0);
- fprintf (dump_file, " with\n ");
+ fprintf (dump_file, " with expr: ");
+ print_generic_expr (dump_file, def);
}
+ any = true;
def = unshare_expr (def);
remove_phi_node (&psi, false);
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");
}
}
-}
-
-/* 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)
-{
- basic_block bb;
- tree name, type, ev;
- gphi *phi;
- struct loop *loop;
- bitmap ssa_names_to_remove = NULL;
- unsigned i;
- gphi_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 = psi.phi ();
- name = PHI_RESULT (phi);
-
- if (virtual_operand_p (name))
- continue;
-
- type = TREE_TYPE (name);
-
- if (!POINTER_TYPE_P (type)
- && !INTEGRAL_TYPE_P (type))
- continue;
-
- ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
- NULL);
- if (!is_gimple_min_invariant (ev)
- || !may_propagate_copy (name, ev))
- continue;
-
- /* Replace the uses of the name. */
- if (name != ev)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Replacing uses of: ");
- print_generic_expr (dump_file, name);
- fprintf (dump_file, " with: ");
- print_generic_expr (dump_file, ev);
- fprintf (dump_file, "\n");
- }
- replace_uses_by (name, ev);
- }
-
- if (!ssa_names_to_remove)
- ssa_names_to_remove = BITMAP_ALLOC (NULL);
- bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
- }
- }
-
- /* 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)
- {
- bitmap_iterator bi;
-
- EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
- {
- gimple_stmt_iterator psi;
- name = ssa_name (i);
- phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
-
- gcc_assert (gimple_code (phi) == GIMPLE_PHI);
- psi = gsi_for_stmt (phi);
- remove_phi_node (&psi, true);
- }
-
- BITMAP_FREE (ssa_names_to_remove);
- scev_reset ();
- }
-
- /* Now the regular final value replacement. */
- FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
- final_value_replacement_loop (loop);
- return 0;
+ return any;
}
#include "gt-tree-scalar-evolution.h"
projects / thirdparty / gcc.git / blobdiff