tree-scalar-evolution.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-fold-const.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "tree-vectorizer.h"
#include "flags.h"
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
static tree resolve_mixers (struct loop *, tree);
struct scev_info_str
{
tree var;
tree chrec;
};
static unsigned nb_set_scev = 0;
static unsigned nb_get_scev = 0;
tree chrec_not_analyzed_yet;
tree chrec_top;
tree chrec_bot;
static struct loops *current_loops;
static bitmap already_instantiated;
static htab_t scalar_evolution_info;
static bool dd_info_available;
static inline struct scev_info_str *
new_scev_info_str (tree var)
{
struct scev_info_str *res;
res = xmalloc (sizeof (struct scev_info_str));
res->var = var;
res->chrec = chrec_not_analyzed_yet;
return res;
}
static hashval_t
hash_scev_info (const void *elt)
{
return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
}
static int
eq_scev_info (const void *e1, const void *e2)
{
const struct scev_info_str *elt1 = e1;
const struct scev_info_str *elt2 = e2;
return elt1->var == elt2->var;
}
static void
del_scev_info (void *e)
{
free (e);
}
static tree *
find_var_scev_info (tree var)
{
struct scev_info_str *res;
struct scev_info_str tmp;
PTR *slot;
tmp.var = var;
slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
if (!*slot)
*slot = new_scev_info_str (var);
res = *slot;
return &res->chrec;
}
tree
count_ev_in_wider_type (tree type, tree chrec)
{
tree base, step;
struct loop *loop;
if (!evolution_function_is_affine_p (chrec))
return fold_convert (type, chrec);
base = CHREC_LEFT (chrec);
step = CHREC_RIGHT (chrec);
loop = loop_from_num (current_loops, CHREC_VARIABLE (chrec));
step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
if (!step)
return fold_convert (type, chrec);
base = chrec_convert (type, base);
return build_polynomial_chrec (CHREC_VARIABLE (chrec),
base, step);
}
bool
chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
{
if (chrec == NULL_TREE)
return false;
if (TREE_INVARIANT (chrec))
return false;
if (TREE_CODE (chrec) == VAR_DECL
|| TREE_CODE (chrec) == PARM_DECL
|| TREE_CODE (chrec) == FUNCTION_DECL
|| TREE_CODE (chrec) == LABEL_DECL
|| TREE_CODE (chrec) == RESULT_DECL
|| TREE_CODE (chrec) == FIELD_DECL)
return true;
if (TREE_CODE (chrec) == SSA_NAME)
{
tree def = SSA_NAME_DEF_STMT (chrec);
struct loop *def_loop = loop_of_stmt (def);
struct loop *loop = loop_from_num (current_loops, loop_nb);
if (def_loop == NULL)
return false;
if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
return true;
return false;
}
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
loop_nb))
return true;
case 2:
if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
loop_nb))
return true;
case 1:
if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
loop_nb))
return true;
default:
return false;
}
}
static bool
loop_phi_node_p (tree phi)
{
return loop_of_stmt (phi)->header == bb_for_stmt (phi);
}
static tree
compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
{
bool val = false;
if (evolution_fn == chrec_top)
return chrec_top;
else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
{
if (CHREC_VARIABLE (evolution_fn) >= loop_num (loop))
{
struct loop *inner_loop =
loop_from_num (current_loops, CHREC_VARIABLE (evolution_fn));
tree nb_iter = number_of_iterations_in_loop (inner_loop);
if (nb_iter == chrec_top)
return chrec_top;
else
{
tree res;
nb_iter = chrec_fold_minus (chrec_type (nb_iter),
nb_iter,
fold_convert (chrec_type (nb_iter),
integer_one_node));
res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
return compute_overall_effect_of_inner_loop (loop, res);
}
}
else
return evolution_fn;
}
else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
return evolution_fn;
else
return chrec_top;
}
bool
chrec_is_positive (tree chrec, bool *value)
{
bool value0, value1;
bool value2;
tree end_value;
tree nb_iter;
switch (TREE_CODE (chrec))
{
case INTERVAL_CHREC:
if (!chrec_is_positive (CHREC_LOW (chrec), &value0)
|| !chrec_is_positive (CHREC_UP (chrec), &value1))
return false;
*value = value0;
return value0 == value1;
case POLYNOMIAL_CHREC:
case EXPONENTIAL_CHREC:
if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
|| !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
return false;
if (value0 == value1)
{
*value = value0;
return true;
}
if (!evolution_function_is_affine_p (chrec))
return false;
nb_iter = number_of_iterations_in_loop
(loop_from_num (current_loops, CHREC_VARIABLE (chrec)));
nb_iter = chrec_fold_minus
(chrec_type (nb_iter), nb_iter,
fold_convert (chrec_type (nb_iter), integer_one_node));
#if 0
if (after_exit)
nb_iter = chrec_fold_minus
(chrec_type (nb_iter), nb_iter,
fold_convert (chrec_type (nb_iter), integer_one_node));
#endif
end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
if (!chrec_is_positive (end_value, &value2))
return false;
*value = value0;
return value0 == value1;
case INTEGER_CST:
*value = (tree_int_cst_sgn (chrec) == 1);
return true;
default:
return false;
}
}
static void
set_scalar_evolution (tree scalar, tree chrec)
{
tree *scalar_info;
if (TREE_CODE (scalar) != SSA_NAME)
return;
scalar_info = find_var_scev_info (scalar);
if (dump_file)
{
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "(set_scalar_evolution \n");
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n (scalar_evolution = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, "))\n");
}
if (dump_flags & TDF_STATS)
nb_set_scev++;
}
*scalar_info = chrec;
}
static tree
get_scalar_evolution (tree scalar)
{
tree res;
if (dump_file)
{
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "(get_scalar_evolution \n");
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n");
}
if (dump_flags & TDF_STATS)
nb_get_scev++;
}
switch (TREE_CODE (scalar))
{
case SSA_NAME:
res = *find_var_scev_info (scalar);
break;
case REAL_CST:
case INTEGER_CST:
res = scalar;
break;
default:
res = chrec_not_analyzed_yet;
break;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (scalar_evolution = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
static tree
add_to_evolution_1 (unsigned loop_nb,
tree chrec_before,
tree to_add)
{
switch (TREE_CODE (chrec_before))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec_before) <= loop_nb)
{
unsigned var;
tree left, right;
tree type = chrec_type (chrec_before);
if (CHREC_VARIABLE (chrec_before) < loop_nb)
{
var = loop_nb;
left = chrec_before;
right = fold_convert (type, integer_zero_node);
}
else
{
var = CHREC_VARIABLE (chrec_before);
left = CHREC_LEFT (chrec_before);
right = CHREC_RIGHT (chrec_before);
}
return build_polynomial_chrec
(var, left, chrec_fold_plus (type, right, to_add));
}
else
return build_polynomial_chrec
(CHREC_VARIABLE (chrec_before),
add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
CHREC_RIGHT (chrec_before));
case EXPONENTIAL_CHREC:
if (CHREC_VARIABLE (chrec_before) == loop_nb)
return build_exponential_chrec (loop_nb, CHREC_LEFT (chrec_before),
chrec_top);
else if (CHREC_VARIABLE (chrec_before) < loop_nb)
return build_polynomial_chrec (loop_nb, chrec_before, to_add);
else
return build_exponential_chrec
(CHREC_VARIABLE (chrec_before),
add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
CHREC_RIGHT (chrec_before));
default:
if (chrec_before == chrec_top)
return chrec_top;
return build_polynomial_chrec (loop_nb, chrec_before, to_add);
}
}
static tree
add_to_evolution (unsigned loop_nb,
tree chrec_before,
enum tree_code code,
tree to_add)
{
tree type = chrec_type (to_add);
tree res = NULL_TREE;
if (to_add == NULL_TREE)
return chrec_before;
if (TREE_CODE (to_add) == POLYNOMIAL_CHREC
|| TREE_CODE (to_add) == EXPONENTIAL_CHREC)
return chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
{
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);
fprintf (dump_file, ")\n (to_add = ");
print_generic_expr (dump_file, to_add, 0);
fprintf (dump_file, ")\n");
}
if (code == MINUS_EXPR)
to_add = chrec_fold_multiply (type, to_add,
fold_convert (type, integer_minus_one_node));
res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
static tree
multiply_evolution_1 (unsigned loop_nb,
tree chrec_before,
tree to_mult)
{
if (chrec_before == chrec_not_analyzed_yet)
return chrec_not_analyzed_yet;
switch (TREE_CODE (chrec_before))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec_before) == loop_nb)
return build_polynomial_chrec (loop_nb, CHREC_LEFT (chrec_before),
chrec_top);
else if (CHREC_VARIABLE (chrec_before) < loop_nb)
return build_exponential_chrec (loop_nb, chrec_before, to_mult);
else
return build_polynomial_chrec
(CHREC_VARIABLE (chrec_before),
multiply_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_mult),
CHREC_RIGHT (chrec_before));
case EXPONENTIAL_CHREC:
if (CHREC_VARIABLE (chrec_before) == loop_nb
&& ((TREE_CODE (CHREC_LEFT (chrec_before)) != POLYNOMIAL_CHREC
&& TREE_CODE (CHREC_LEFT (chrec_before)) != EXPONENTIAL_CHREC)
|| (CHREC_VARIABLE (CHREC_LEFT (chrec_before)) != loop_nb)))
return build_exponential_chrec
(loop_nb,
CHREC_LEFT (chrec_before),
chrec_fold_multiply (chrec_type (to_mult),
CHREC_RIGHT (chrec_before), to_mult));
else if (CHREC_VARIABLE (chrec_before) < loop_nb)
return build_exponential_chrec (loop_nb, chrec_before, to_mult);
else
return build_exponential_chrec
(CHREC_VARIABLE (chrec_before),
multiply_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_mult),
CHREC_RIGHT (chrec_before));
default:
return build_exponential_chrec (loop_nb, chrec_before, to_mult);
}
}
static tree
multiply_evolution (unsigned loop_nb,
tree chrec_before,
tree to_mult)
{
tree res = NULL_TREE;
if (to_mult == chrec_not_analyzed_yet)
return chrec_before;
if (TREE_CODE (to_mult) == POLYNOMIAL_CHREC
|| TREE_CODE (to_mult) == EXPONENTIAL_CHREC)
return chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(multiply_evolution \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (chrec_before = ");
print_generic_expr (dump_file, chrec_before, 0);
fprintf (dump_file, ")\n (to_mult = ");
print_generic_expr (dump_file, to_mult, 0);
fprintf (dump_file, ")\n");
}
res = multiply_evolution_1 (loop_nb, chrec_before, to_mult);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
static tree
first_iteration_non_satisfying_noev_noev (enum tree_code code,
unsigned loop_nb ATTRIBUTE_UNUSED,
tree chrec0,
tree chrec1)
{
bool val = false;
tree init0 = initial_condition (chrec0);
tree init1 = initial_condition (chrec1);
if (TREE_CODE (init0) != INTEGER_CST
|| TREE_CODE (init1) != INTEGER_CST)
return chrec_top;
switch (code)
{
case LE_EXPR:
if (!tree_is_gt (init0, init1, &val))
return chrec_top;
break;
case LT_EXPR:
if (!tree_is_ge (init0, init1, &val))
return chrec_top;
break;
case EQ_EXPR:
if (!tree_is_eq (init0, init1, &val))
return chrec_top;
break;
case NE_EXPR:
if (!tree_is_ne (init0, init1, &val))
return chrec_top;
break;
default:
return chrec_top;
}
if (val)
return integer_zero_node;
else if (evolution_function_is_constant_p (chrec0)
&& evolution_function_is_constant_p (chrec1))
return chrec_bot;
else
return chrec_top;
}
static tree
first_iteration_non_satisfying_noev_ev (enum tree_code code,
unsigned loop_nb,
tree chrec0,
tree chrec1)
{
bool val = false;
tree type1 = chrec_type (chrec1);
tree ev_in_this_loop;
tree init0, init1, step1;
struct tree_niter_desc niter_desc;
ev_in_this_loop = hide_evolution_in_other_loops_than_loop (chrec1, loop_nb);
if (!evolution_function_is_affine_p (ev_in_this_loop))
return chrec_top;
init1 = CHREC_LEFT (ev_in_this_loop);
step1 = CHREC_RIGHT (ev_in_this_loop);
init0 = initial_condition (chrec0);
if (!no_evolution_in_loop_p (init0, loop_nb, &val)
|| val == false
|| !no_evolution_in_loop_p (init1, loop_nb, &val)
|| val == false
|| TREE_CODE (step1) != INTEGER_CST)
return chrec_top;
niter_desc.niter = NULL_TREE;
number_of_iterations_cond (type1, init0, NULL_TREE, code, init1, step1,
&niter_desc);
if (niter_desc.niter != NULL_TREE
&& integer_onep (niter_desc.assumptions)
&& integer_zerop (niter_desc.may_be_zero))
return niter_desc.niter;
return chrec_top;
}
static tree
first_iteration_non_satisfying_ev_noev (enum tree_code code,
unsigned loop_nb,
tree chrec0,
tree chrec1)
{
bool val = false;
tree type0 = chrec_type (chrec0);
tree ev_in_this_loop;
tree init0, init1, step0;
struct tree_niter_desc niter_desc;
ev_in_this_loop = hide_evolution_in_other_loops_than_loop (chrec0, loop_nb);
if (!evolution_function_is_affine_p (ev_in_this_loop))
return chrec_top;
init0 = CHREC_LEFT (ev_in_this_loop);
step0 = CHREC_RIGHT (ev_in_this_loop);
init1 = initial_condition (chrec1);
if (!no_evolution_in_loop_p (init0, loop_nb, &val)
|| val == false
|| !no_evolution_in_loop_p (init1, loop_nb, &val)
|| val == false
|| TREE_CODE (step0) != INTEGER_CST)
return chrec_top;
niter_desc.niter = NULL_TREE;
number_of_iterations_cond (type0, init0, step0, code, init1, NULL_TREE,
&niter_desc);
if (niter_desc.niter != NULL_TREE
&& integer_onep (niter_desc.assumptions)
&& integer_zerop (niter_desc.may_be_zero))
return niter_desc.niter;
return chrec_top;
}
static tree
first_iteration_non_satisfying_ev_ev (enum tree_code code,
unsigned loop_nb,
tree chrec0,
tree chrec1)
{
bool val = false;
tree init0, init1, step0, step1;
tree type0, type1;
struct tree_niter_desc niter_desc;
if (evolution_function_is_multivariate (chrec0)
|| evolution_function_is_multivariate (chrec1))
return chrec_top;
init0 = CHREC_LEFT (chrec0);
step0 = CHREC_RIGHT (chrec0);
init1 = CHREC_LEFT (chrec1);
step1 = CHREC_RIGHT (chrec1);
if (!no_evolution_in_loop_p (init0, loop_nb, &val)
|| val == false
|| !no_evolution_in_loop_p (init1, loop_nb, &val)
|| val == false
|| TREE_CODE (step0) != INTEGER_CST
|| TREE_CODE (step1) != INTEGER_CST)
return chrec_top;
type0 = chrec_type (chrec0);
type1 = chrec_type (chrec1);
if (type0 != type1)
return chrec_top;
niter_desc.niter = NULL_TREE;
number_of_iterations_cond (type0, init0, step0, code, init1, step1,
&niter_desc);
if (niter_desc.niter != NULL_TREE
&& integer_onep (niter_desc.assumptions)
&& integer_zerop (niter_desc.may_be_zero))
return niter_desc.niter;
return chrec_top;
}
static tree
first_iteration_non_satisfying_1 (enum tree_code code,
unsigned loop_nb,
tree chrec0,
tree chrec1)
{
bool val = false;
tree res, other_evs;
if (automatically_generated_chrec_p (chrec0)
|| automatically_generated_chrec_p (chrec1))
return chrec_top;
if (!no_evolution_in_loop_p (chrec0, loop_nb, &val))
return chrec_top;
else if (val)
{
if (!no_evolution_in_loop_p (chrec1, loop_nb, &val))
return chrec_top;
else if (val)
return first_iteration_non_satisfying_noev_noev (code, loop_nb,
chrec0, chrec1);
else
{
res = first_iteration_non_satisfying_noev_ev (code, loop_nb,
chrec0, chrec1);
if (res == chrec_top)
return res;
other_evs = hide_evolution_in_loop (chrec1, loop_nb);
other_evs = chrec_fold_minus (chrec_type (other_evs),
other_evs, chrec0);
other_evs = chrec_replace_initial_condition
(other_evs, fold_convert (chrec_type (other_evs), integer_zero_node));
}
}
else
{
if (!no_evolution_in_loop_p (chrec1, loop_nb, &val))
return chrec_top;
else if (val)
{
res = first_iteration_non_satisfying_ev_noev (code, loop_nb,
chrec0, chrec1);
if (res == chrec_top)
return res;
other_evs = hide_evolution_in_loop (chrec0, loop_nb);
other_evs = chrec_fold_minus (chrec_type (other_evs),
other_evs, chrec1);
other_evs = chrec_replace_initial_condition
(other_evs, fold_convert (chrec_type (other_evs), integer_zero_node));
}
else
return first_iteration_non_satisfying_ev_ev (code, loop_nb,
chrec0, chrec1);
}
res = chrec_fold_minus (chrec_type (res), res, other_evs);
return res;
}
tree
first_iteration_non_satisfying (enum tree_code code,
unsigned loop_nb,
tree chrec0,
tree chrec1)
{
switch (code)
{
case EQ_EXPR:
case NE_EXPR:
case LT_EXPR:
case LE_EXPR:
return first_iteration_non_satisfying_1 (code, loop_nb, chrec0, chrec1);
case GT_EXPR:
return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb,
chrec1, chrec0);
case GE_EXPR:
return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb,
chrec1, chrec0);
default:
return chrec_top;
}
}
static inline tree
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
res = chrec_fold_plus (chrec_type (res), res, integer_one_node);
if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
|| TREE_OVERFLOW (res))
res = chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (set_nb_iterations_in_loop = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
loop->nb_iterations = res;
return res;
}
static bool
analyzable_condition (tree expr)
{
tree condition;
if (TREE_CODE (expr) != COND_EXPR)
return false;
condition = TREE_OPERAND (expr, 0);
switch (TREE_CODE (condition))
{
case SSA_NAME:
if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition)))
return false;
return true;
case LT_EXPR:
case LE_EXPR:
case GT_EXPR:
case GE_EXPR:
case EQ_EXPR:
case NE_EXPR:
{
tree opnd0, opnd1;
opnd0 = TREE_OPERAND (condition, 0);
opnd1 = TREE_OPERAND (condition, 1);
if (TREE_CODE (opnd0) == SSA_NAME
&& TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0)))
return false;
if (TREE_CODE (opnd1) == SSA_NAME
&& TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1)))
return false;
return true;
}
default:
return false;
}
return false;
}
tree
get_loop_exit_condition (struct loop *loop)
{
tree res = NULL_TREE;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(get_loop_exit_condition \n ");
if (loop_exit_edges (loop))
{
edge exit_edge;
tree expr;
exit_edge = loop_exit_edge (loop, 0);
expr = last_stmt (edge_source (exit_edge));
if (analyzable_condition (expr))
res = expr;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, ")\n");
}
return res;
}
static void
get_exit_conditions_rec (struct loop *loop,
varray_type *exit_conditions)
{
if (!loop)
return;
get_exit_conditions_rec (inner_loop (loop), exit_conditions);
get_exit_conditions_rec (next_loop (loop), exit_conditions);
flow_loop_scan (loop, LOOP_EXIT_EDGES);
if (loop_num_exits (loop) == 1)
{
tree loop_condition = get_loop_exit_condition (loop);
if (loop_condition)
VARRAY_PUSH_TREE (*exit_conditions, loop_condition);
}
}
static void
select_loops_exit_conditions (struct loops *loops,
varray_type *exit_conditions)
{
struct loop *function_body = loops->parray[0];
get_exit_conditions_rec (inner_loop (function_body), exit_conditions);
}
static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
static bool
follow_ssa_edge_in_rhs (struct loop *loop,
tree rhs,
tree halting_phi,
tree *evolution_of_loop)
{
bool res = false;
tree rhs0, rhs1;
tree type_rhs = TREE_TYPE (rhs);
switch (TREE_CODE (rhs))
{
case NOP_EXPR:
res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
evolution_of_loop);
*evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
break;
case INTEGER_CST:
res = false;
break;
case SSA_NAME:
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
break;
case PLUS_EXPR:
rhs0 = TREE_OPERAND (rhs, 0);
rhs1 = TREE_OPERAND (rhs, 1);
if (TREE_CODE (rhs0) == SSA_NAME)
{
if (TREE_CODE (rhs1) == SSA_NAME)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num,
chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs1);
else
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num,
chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs0);
}
}
else
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num, chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs1);
}
}
else if (TREE_CODE (rhs1) == SSA_NAME)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num, chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs0);
}
else
res = false;
break;
case MINUS_EXPR:
rhs0 = TREE_OPERAND (rhs, 0);
rhs1 = TREE_OPERAND (rhs, 1);
if (TREE_CODE (rhs0) == SSA_NAME)
{
if (TREE_CODE (rhs1) == SSA_NAME)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num, chrec_convert (type_rhs, *evolution_of_loop),
MINUS_EXPR, rhs1);
else
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
fold_convert (type_rhs,
integer_minus_one_node)),
PLUS_EXPR, rhs0);
}
}
else
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num, chrec_convert (type_rhs, *evolution_of_loop),
MINUS_EXPR, rhs1);
}
}
else if (TREE_CODE (rhs1) == SSA_NAME)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
fold_convert (type_rhs, integer_minus_one_node)),
PLUS_EXPR, rhs0);
}
else
res = false;
break;
case MULT_EXPR:
rhs0 = TREE_OPERAND (rhs, 0);
rhs1 = TREE_OPERAND (rhs, 1);
if (TREE_CODE (rhs0) == SSA_NAME)
{
if (TREE_CODE (rhs1) == SSA_NAME)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
(loop->num, *evolution_of_loop, rhs1);
else
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
(loop->num, *evolution_of_loop, rhs0);
}
}
else
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
(loop->num, *evolution_of_loop, rhs1);
}
}
else if (TREE_CODE (rhs1) == SSA_NAME)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
(loop->num, *evolution_of_loop, rhs0);
}
else
res = false;
break;
default:
res = false;
break;
}
return res;
}
static bool
backedge_phi_arg_p (tree phi, int i)
{
edge e = PHI_ARG_EDGE (phi, i);
if (e->flags & EDGE_IRREDUCIBLE_LOOP)
return true;
return false;
}
static inline bool
follow_ssa_edge_in_condition_phi_branch (int i,
struct loop *loop,
tree condition_phi,
tree halting_phi,
tree *evolution_of_branch,
tree init_cond)
{
tree branch = PHI_ARG_DEF (condition_phi, i);
*evolution_of_branch = chrec_top;
if (backedge_phi_arg_p (condition_phi, i))
return false;
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);
}
return false;
}
static bool
follow_ssa_edge_in_condition_phi (struct loop *loop,
tree condition_phi,
tree halting_phi,
tree *evolution_of_loop)
{
int i;
tree init = *evolution_of_loop;
tree evolution_of_branch;
if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
halting_phi,
&evolution_of_branch,
init))
return false;
*evolution_of_loop = evolution_of_branch;
for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
{
if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
halting_phi,
&evolution_of_branch,
init))
return false;
*evolution_of_loop = chrec_merge (*evolution_of_loop,
evolution_of_branch);
}
return true;
}
static bool
follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
tree loop_phi_node,
tree halting_phi,
tree *evolution_of_loop)
{
struct loop *loop = loop_of_stmt (loop_phi_node);
tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
if (ev == PHI_RESULT (loop_phi_node))
{
bool res = false;
int i;
for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
{
tree arg = PHI_ARG_DEF (loop_phi_node, i);
basic_block bb;
bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
evolution_of_loop);
}
if (res == true)
*evolution_of_loop = chrec_top;
return res;
}
ev = compute_overall_effect_of_inner_loop (loop, ev);
return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
evolution_of_loop);
}
static bool
follow_ssa_edge (struct loop *loop,
tree def,
tree halting_phi,
tree *evolution_of_loop)
{
struct loop *def_loop;
if (TREE_CODE (def) == NOP_EXPR)
return false;
def_loop = loop_of_stmt (def);
switch (TREE_CODE (def))
{
case PHI_NODE:
if (!loop_phi_node_p (def))
return follow_ssa_edge_in_condition_phi
(loop, def, halting_phi, evolution_of_loop);
if (def == halting_phi)
return true;
if (def_loop == loop)
return false;
if (flow_loop_nested_p (loop, def_loop))
return follow_ssa_edge_inner_loop_phi
(loop, def, halting_phi, evolution_of_loop);
return false;
case MODIFY_EXPR:
return follow_ssa_edge_in_rhs (loop,
TREE_OPERAND (def, 1),
halting_phi,
evolution_of_loop);
default:
return false;
}
}
static tree
analyze_evolution_in_loop (tree loop_phi_node,
tree init_cond)
{
int i;
tree evolution_function = chrec_not_analyzed_yet;
struct loop *loop = loop_of_stmt (loop_phi_node);
basic_block bb;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_evolution_in_loop \n");
fprintf (dump_file, " (loop_phi_node = ");
print_generic_expr (dump_file, loop_phi_node, 0);
fprintf (dump_file, ")\n");
}
for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
{
tree arg = PHI_ARG_DEF (loop_phi_node, i);
tree ssa_chain, ev_fn;
bool res;
bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
continue;
if (TREE_CODE (arg) == SSA_NAME)
{
ssa_chain = SSA_NAME_DEF_STMT (arg);
ev_fn = init_cond;
res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
}
else
res = false;
if (!res)
{
ev_fn = build_peeled_chrec (loop->num, init_cond, arg);
ev_fn = simplify_peeled_chrec (ev_fn);
}
evolution_function = chrec_merge (evolution_function, ev_fn);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (evolution_function = ");
print_generic_expr (dump_file, evolution_function, 0);
fprintf (dump_file, "))\n");
}
return evolution_function;
}
static tree
analyze_initial_condition (tree loop_phi_node)
{
int i;
tree init_cond = chrec_not_analyzed_yet;
struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_initial_condition \n");
fprintf (dump_file, " (loop_phi_node = \n");
print_generic_expr (dump_file, loop_phi_node, 0);
fprintf (dump_file, ")\n");
}
for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
{
tree branch = PHI_ARG_DEF (loop_phi_node, i);
basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
if (flow_bb_inside_loop_p (loop, bb))
continue;
if (init_cond == chrec_not_analyzed_yet)
{
init_cond = branch;
continue;
}
if (TREE_CODE (branch) == SSA_NAME)
{
init_cond = chrec_top;
break;
}
init_cond = chrec_merge (init_cond, branch);
}
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (init_cond = ");
print_generic_expr (dump_file, init_cond, 0);
fprintf (dump_file, "))\n");
}
return init_cond;
}
static tree
interpret_loop_phi (struct loop *loop, tree loop_phi_node)
{
tree res;
struct loop *phi_loop = loop_of_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));
subloop = superloop_at_depth (phi_loop, loop->depth + 1);
res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
return res;
}
init_cond = analyze_initial_condition (loop_phi_node);
res = analyze_evolution_in_loop (loop_phi_node, init_cond);
return res;
}
static tree
interpret_condition_phi (struct loop *loop, tree condition_phi)
{
int i;
tree res = chrec_not_analyzed_yet;
for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
{
tree branch_chrec;
if (backedge_phi_arg_p (condition_phi, i))
{
res = chrec_top;
break;
}
branch_chrec = analyze_scalar_evolution
(loop, PHI_ARG_DEF (condition_phi, i));
res = chrec_merge (res, branch_chrec);
}
return res;
}
static tree
interpret_rhs_modify_expr (struct loop *loop,
tree opnd1, tree type)
{
tree res, opnd10, opnd11, chrec10, chrec11;
if (is_gimple_min_invariant (opnd1))
return chrec_convert (type, opnd1);
switch (TREE_CODE (opnd1))
{
case PLUS_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
chrec10 = chrec_convert (type, chrec10);
chrec11 = chrec_convert (type, chrec11);
res = chrec_fold_plus (type, chrec10, chrec11);
break;
case MINUS_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
chrec10 = chrec_convert (type, chrec10);
chrec11 = chrec_convert (type, chrec11);
res = chrec_fold_minus (type, chrec10, chrec11);
break;
case NEGATE_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec10 = chrec_convert (type, chrec10);
res = chrec_fold_minus (type, fold_convert (type, integer_zero_node),
chrec10);
break;
case MULT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
chrec10 = chrec_convert (type, chrec10);
chrec11 = chrec_convert (type, chrec11);
res = chrec_fold_multiply (type, chrec10, chrec11);
break;
case SSA_NAME:
res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
break;
case NOP_EXPR:
case CONVERT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
res = chrec_convert (type, chrec10);
break;
default:
res = chrec_top;
break;
}
return res;
}
static tree
compute_scalar_evolution_in_loop (struct loop *wrto_loop,
struct loop *def_loop,
tree ev)
{
tree res;
if (def_loop == wrto_loop)
return ev;
def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
res = compute_overall_effect_of_inner_loop (def_loop, ev);
return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
}
static tree
analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
{
tree def, type = TREE_TYPE (var);
basic_block bb;
struct loop *def_loop;
if (loop == NULL)
return chrec_top;
if (TREE_CODE (var) != SSA_NAME)
return interpret_rhs_modify_expr (loop, var, type);
def = SSA_NAME_DEF_STMT (var);
bb = bb_for_stmt (def);
def_loop = bb ? bb->loop_father : NULL;
if (bb == NULL
|| !flow_bb_inside_loop_p (loop, bb))
{
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);
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);
goto set_and_end;
}
switch (TREE_CODE (def))
{
case MODIFY_EXPR:
res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
break;
case PHI_NODE:
if (loop_phi_node_p (def))
res = interpret_loop_phi (loop, def);
else
res = interpret_condition_phi (loop, def);
break;
default:
res = chrec_top;
break;
}
set_and_end:
if (res == chrec_top)
res = var;
if (loop == def_loop)
set_scalar_evolution (var, res);
return res;
}
tree
analyze_scalar_evolution (struct loop *loop, tree var)
{
tree res;
if (dump_file && (dump_flags & TDF_DETAILS))
{
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);
fprintf (dump_file, ")\n");
}
res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
if (TREE_CODE (var) == SSA_NAME && res == chrec_top)
res = var;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
tree version)
{
bool val = false;
tree ev = version;
while (1)
{
ev = analyze_scalar_evolution (use_loop, ev);
ev = resolve_mixers (use_loop, ev);
if (use_loop == wrto_loop)
return ev;
if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
|| !val)
return chrec_top;
use_loop = use_loop->outer;
}
}
static tree
instantiate_parameters_1 (struct loop *loop, tree chrec,
bool allow_superloop_chrecs)
{
tree res, op0, op1, op2;
basic_block def_bb;
struct loop *def_loop;
if (chrec == NULL_TREE
|| automatically_generated_chrec_p (chrec))
return chrec;
if (is_gimple_min_invariant (chrec))
return chrec;
switch (TREE_CODE (chrec))
{
case SSA_NAME:
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
if (!def_bb
|| (!allow_superloop_chrecs
&& !flow_bb_inside_loop_p (loop, def_bb)))
return chrec;
if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
{
if (!flow_bb_inside_loop_p (loop, def_bb))
{
return chrec;
}
else
{
return chrec_top;
}
}
def_loop = find_common_loop (loop, def_bb->loop_father);
bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
return res;
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
allow_superloop_chrecs);
return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
case EXPONENTIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
allow_superloop_chrecs);
return build_exponential_chrec (CHREC_VARIABLE (chrec), op0, op1);
case PEELED_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
allow_superloop_chrecs);
return build_peeled_chrec (CHREC_VARIABLE (chrec), op0, op1);
case INTERVAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LOW (chrec),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, CHREC_UP (chrec),
allow_superloop_chrecs);
return build_interval_chrec (op0, op1);
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
case NOP_EXPR:
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
return chrec_convert (TREE_TYPE (chrec), op0);
default:
break;
}
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
allow_superloop_chrecs);
return fold (build (TREE_CODE (chrec),
TREE_TYPE (chrec), op0, op1, op2));
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
case 0:
return chrec;
default:
break;
}
return chrec_top;
}
tree
instantiate_parameters (struct loop *loop,
tree chrec)
{
tree res;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(instantiate_parameters \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (chrec = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, ")\n");
}
res = instantiate_parameters_1 (loop, chrec, true);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
static tree
resolve_mixers (struct loop *loop, tree chrec)
{
return instantiate_parameters_1 (loop, chrec, false);
}
tree
number_of_iterations_in_loop (struct loop *loop)
{
tree res, type;
edge exit;
struct tree_niter_desc niter_desc;
res = loop_nb_iterations (loop);
if (res)
return res;
res = chrec_top;
if (!loop_exit_edges (loop))
goto end;
exit = loop_exit_edge (loop, 0);
if (!number_of_iterations_exit (loop, exit, &niter_desc))
goto end;
type = TREE_TYPE (niter_desc.niter);
if (integer_nonzerop (niter_desc.may_be_zero))
res = fold_convert (type, integer_zero_node);
else if (integer_zerop (niter_desc.may_be_zero))
res = niter_desc.niter;
else
res = chrec_top;
#if 0
enum tree_code code;
tree cond, test, opnd0, opnd1;
tree chrec0, chrec1;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop \n");
cond = get_loop_exit_condition (loop);
if (cond == NULL_TREE)
return set_nb_iterations_in_loop (loop, chrec_top);
test = TREE_OPERAND (cond, 0);
exit = loop_exit_edge (loop, 0);
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return set_nb_iterations_in_loop (loop, chrec_top);
if (exit->flags & EDGE_TRUE_VALUE)
test = invert_truthvalue (test);
code = TREE_CODE (test);
switch (code)
{
case SSA_NAME:
code = NE_EXPR;
chrec0 = analyze_scalar_evolution (loop, test);
chrec1 = integer_zero_node;
if (chrec0 == chrec_top)
chrec0 = test;
goto end;
case LT_EXPR:
case LE_EXPR:
case GT_EXPR:
case GE_EXPR:
case EQ_EXPR:
case NE_EXPR:
opnd0 = TREE_OPERAND (test, 0);
opnd1 = TREE_OPERAND (test, 1);
chrec0 = analyze_scalar_evolution (loop, opnd0);
chrec1 = analyze_scalar_evolution (loop, opnd1);
if (chrec0 == chrec_top)
chrec0 = opnd0;
if (chrec1 == chrec_top)
chrec1 = opnd1;
goto end;
default:
return set_nb_iterations_in_loop (loop, chrec_top);
}
end:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (loop_while_expr_is_true: ");
print_generic_expr (dump_file, test, 0);
fprintf (dump_file, ")\n (chrec0 = ");
print_generic_expr (dump_file, chrec0, 0);
fprintf (dump_file, ")\n (chrec1 = ");
print_generic_expr (dump_file, chrec1, 0);
fprintf (dump_file, ")\n");
}
if (chrec_contains_undetermined (chrec0)
|| chrec_contains_undetermined (chrec1))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " (nb_iterations cannot be determined))\n");
return chrec_top;
}
res = first_iteration_non_satisfying (code, loop->num, chrec0, chrec1);
#endif
end:
return set_nb_iterations_in_loop (loop, res);
}
static void
number_of_iterations_for_all_loops (varray_type exit_conditions)
{
unsigned int i;
unsigned nb_chrec_top_loops = 0;
unsigned nb_static_loops = 0;
for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
{
tree res = number_of_iterations_in_loop
(loop_of_stmt (VARRAY_TREE (exit_conditions, i)));
if (res == chrec_top)
nb_chrec_top_loops++;
else
nb_static_loops++;
}
if (dump_file)
{
fprintf (dump_file, "\n(\n");
fprintf (dump_file, "-----------------------------------------\n");
fprintf (dump_file, "%d\tnb_chrec_top_loops\n", nb_chrec_top_loops);
fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
fprintf (dump_file, "-----------------------------------------\n");
fprintf (dump_file, ")\n\n");
print_loop_ir (dump_file);
}
}
struct chrec_stats
{
unsigned nb_chrecs;
unsigned nb_peeled;
unsigned nb_affine;
unsigned nb_affine_multivar;
unsigned nb_higher_poly;
unsigned nb_expo;
unsigned nb_chrec_top;
unsigned nb_interval_chrec;
unsigned nb_undetermined;
};
static inline void
reset_chrecs_counters (struct chrec_stats *stats)
{
stats->nb_chrecs = 0;
stats->nb_peeled = 0;
stats->nb_affine = 0;
stats->nb_affine_multivar = 0;
stats->nb_higher_poly = 0;
stats->nb_expo = 0;
stats->nb_chrec_top = 0;
stats->nb_interval_chrec = 0;
stats->nb_undetermined = 0;
}
static void
dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
{
fprintf (file, "\n(\n");
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
fprintf (file, "%d\tdegree greater than 2 polynomials\n",
stats->nb_higher_poly);
fprintf (file, "%d\taffine peeled chrecs\n", stats->nb_peeled);
fprintf (file, "%d\texponential chrecs\n", stats->nb_expo);
fprintf (file, "%d\tchrec_top chrecs\n", stats->nb_chrec_top);
fprintf (file, "%d\tinterval chrecs\n", stats->nb_chrec_top);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
fprintf (file, "%d\twith undetermined coefficients\n",
stats->nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
(int) htab_elements (scalar_evolution_info));
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");
fprintf (file, ")\n\n");
}
static void
gather_chrec_stats (tree chrec, struct chrec_stats *stats)
{
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "(classify_chrec ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, "\n");
}
stats->nb_chrecs++;
if (chrec == NULL_TREE)
{
stats->nb_undetermined++;
return;
}
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (evolution_function_is_affine_p (chrec))
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " affine_univariate\n");
stats->nb_affine++;
}
else if (evolution_function_is_affine_multivariate_p (chrec))
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " affine_multivariate\n");
stats->nb_affine_multivar++;
}
else
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " higher_degree_polynomial\n");
stats->nb_higher_poly++;
}
break;
case EXPONENTIAL_CHREC:
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " exponential\n");
stats->nb_expo++;
break;
case INTERVAL_CHREC:
if (chrec == chrec_top)
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " chrec_top\n");
stats->nb_chrec_top++;
}
else
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " interval chrec\n");
stats->nb_interval_chrec++;
}
break;
case PEELED_CHREC:
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " peeled chrec\n");
stats->nb_peeled++;
break;
default:
break;
}
if (chrec_contains_undetermined (chrec))
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " undetermined\n");
stats->nb_undetermined++;
}
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, ")\n");
}
static void
analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
{
unsigned int i;
struct chrec_stats stats;
reset_chrecs_counters (&stats);
for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
{
struct loop *loop;
basic_block bb;
tree phi, chrec;
loop = loop_of_stmt (VARRAY_TREE (exit_conditions, i));
bb = loop_header (loop);
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
if (is_gimple_reg (PHI_RESULT (phi)))
{
chrec = instantiate_parameters
(loop,
analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (dump_file && (dump_flags & TDF_STATS))
gather_chrec_stats (chrec, &stats);
}
}
if (dump_file && (dump_flags & TDF_STATS))
dump_chrecs_stats (dump_file, &stats);
}
static int
gather_stats_on_scev_database_1 (void **slot, void *stats)
{
struct scev_info_str *entry = *slot;
gather_chrec_stats (entry->chrec, stats);
return 1;
}
void
gather_stats_on_scev_database (void)
{
struct chrec_stats stats;
if (!dump_file)
return;
reset_chrecs_counters (&stats);
htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
&stats);
dump_chrecs_stats (dump_file, &stats);
}
static void initialize_scalar_evolutions_analyzer (void);
static void scev_init (void);
static void scev_analysis (void);
static void scev_depend (void);
static void scev_elim_checks (void);
static void scev_vectorize (void);
static void scev_done (void);
static bool gate_scev (void);
static bool gate_scev_analysis (void);
static bool gate_scev_depend (void);
static bool gate_scev_elim_checks (void);
static bool gate_scev_vectorize (void);
static void
initialize_scalar_evolutions_analyzer (void)
{
chrec_not_analyzed_yet = NULL_TREE;
chrec_top = build_interval_chrec
(build_int_2 (2222, 0), build_int_2 (3222, 0));
chrec_bot = build_interval_chrec
(build_int_2 (3333, 0), build_int_2 (4333, 0));
}
void
scev_initialize (struct loops *loops)
{
unsigned i;
current_loops = loops;
scalar_evolution_info = htab_create (100, hash_scev_info,
eq_scev_info, del_scev_info);
already_instantiated = BITMAP_XMALLOC ();
initialize_scalar_evolutions_analyzer ();
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
flow_loop_scan (loops->parray[i], LOOP_EXIT_EDGES);
}
void
scev_reset (void)
{
unsigned i;
struct loop *loop;
htab_empty (scalar_evolution_info);
for (i = 1; i < current_loops->num; i++)
{
loop = current_loops->parray[i];
if (loop)
loop->nb_iterations = NULL_TREE;
}
}
static void
scev_init (void)
{
current_loops = tree_loop_optimizer_init (NULL, flag_tree_loop != 0);
if (!current_loops)
return;
scev_initialize (current_loops);
}
bool
simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
{
basic_block bb = bb_for_stmt (stmt);
tree type, ev;
*base = NULL_TREE;
*step = NULL_TREE;
type = TREE_TYPE (op);
if (TREE_CODE (type) != INTEGER_TYPE
&& TREE_CODE (type) != POINTER_TYPE)
return false;
ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
if (tree_does_not_contain_chrecs (ev)
&& !chrec_contains_symbols_defined_in_loop (ev, loop->num))
{
*base = ev;
return true;
}
if (TREE_CODE (ev) != POLYNOMIAL_CHREC
|| CHREC_VARIABLE (ev) != (unsigned) loop->num)
return false;
*step = CHREC_RIGHT (ev);
if (TREE_CODE (*step) != INTEGER_CST)
return false;
*base = CHREC_LEFT (ev);
if (tree_contains_chrecs (*base)
|| chrec_contains_symbols_defined_in_loop (*base, loop->num))
return false;
return true;
}
static void
scev_analysis (void)
{
varray_type exit_conditions;
VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions");
select_loops_exit_conditions (current_loops, &exit_conditions);
#if 0
dump_file = stderr;
dump_flags = 31;
#endif
if (dump_file && (dump_flags & TDF_STATS))
analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions);
number_of_iterations_for_all_loops (exit_conditions);
VARRAY_CLEAR (exit_conditions);
}
static void
scev_depend (void)
{
analyze_all_data_dependences (current_loops);
dd_info_available = true;
}
static void
scev_elim_checks (void)
{
eliminate_redundant_checks ();
}
static void
scev_linear_transform (void)
{
linear_transform_loops (current_loops);
}
static void
scev_iv_canon (void)
{
canonicalize_induction_variables (current_loops);
}
static void
scev_vectorize (void)
{
bitmap_clear (vars_to_rename);
vectorize_loops (current_loops);
}
void
scev_finalize (void)
{
htab_delete (scalar_evolution_info);
BITMAP_XFREE (already_instantiated);
current_loops = NULL;
chrec_top = NULL;
chrec_bot = NULL;
}
static void
scev_done (void)
{
if (current_loops)
{
loop_optimizer_finalize (current_loops, NULL);
scev_finalize ();
cleanup_tree_cfg ();
}
dd_info_available = false;
}
static bool
gate_scev (void)
{
return (flag_scalar_evolutions != 0
|| flag_tree_vectorize != 0
|| flag_all_data_deps != 0
|| flag_tree_elim_checks != 0
|| flag_tree_loop_linear != 0);
}
static bool
gate_scev_analysis (void)
{
return current_loops && flag_scalar_evolutions != 0;
}
static bool
gate_scev_depend (void)
{
return current_loops && flag_all_data_deps != 0;
}
static bool
gate_scev_elim_checks (void)
{
return current_loops && flag_tree_elim_checks != 0;
}
static bool
gate_scev_linear_transform (void)
{
return current_loops && flag_tree_loop_linear != 0;
}
static bool
gate_scev_iv_canon (void)
{
return (current_loops
&& flag_tree_loop);
}
static bool
gate_scev_vectorize (void)
{
return current_loops && flag_tree_vectorize != 0;
}
static bool
gate_ddg (void)
{
return dd_info_available && flag_ddg && flag_scalar_evolutions != 0;
}
static bool
gate_delete_ddg (void)
{
return flag_ddg && flag_scalar_evolutions != 0;
}
static void
create_dg_graph (void)
{
dg_create_graph (current_loops);
}
struct tree_opt_pass pass_scev =
{
NULL,
gate_scev,
NULL,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func
};
struct tree_opt_pass pass_scev_init =
{
NULL,
NULL,
scev_init,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa,
0,
0,
0,
0
};
struct tree_opt_pass pass_scev_anal =
{
"scev",
gate_scev_analysis,
scev_analysis,
NULL,
NULL,
0,
TV_SCALAR_EVOLUTIONS,
PROP_cfg | PROP_ssa,
0,
0,
0,
0
};
struct tree_opt_pass pass_scev_depend =
{
"ddall",
gate_scev_depend,
scev_depend,
NULL,
NULL,
0,
TV_ALL_DATA_DEPS,
PROP_cfg | PROP_ssa,
PROP_scev,
0,
0,
0
};
struct tree_opt_pass pass_scev_vectorize =
{
"vect",
gate_scev_vectorize,
scev_vectorize,
NULL,
NULL,
0,
TV_TREE_VECTORIZATION,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_rename_vars
};
struct tree_opt_pass pass_scev_linear_transform =
{
"ltrans",
gate_scev_linear_transform,
scev_linear_transform,
NULL,
NULL,
0,
TV_TREE_LINEAR_TRANSFORM,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func
};
struct tree_opt_pass pass_scev_iv_canon =
{
"ivcan",
gate_scev_iv_canon,
scev_iv_canon,
NULL,
NULL,
0,
TV_TREE_LOOP_IVCANON,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func
};
struct tree_opt_pass pass_scev_elim_checks =
{
"elck",
gate_scev_elim_checks,
scev_elim_checks,
NULL,
NULL,
0,
TV_TREE_ELIM_CHECKS,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func
};
struct tree_opt_pass pass_scev_done =
{
NULL,
NULL,
scev_done,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa,
0,
0,
0,
0
};
struct tree_opt_pass pass_ddg =
{
"ddg",
gate_ddg,
create_dg_graph,
NULL,
NULL,
0,
TV_DEP_GRAPH,
PROP_scev,
0,
0,
0,
0
};
struct tree_opt_pass pass_delete_ddg =
{
"delete ddg",
gate_delete_ddg,
dg_delete_graph,
NULL,
NULL,
0,
TV_DEP_GRAPH,
0,
0,
0,
0,
0
};