#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "diagnostic.h"
#include "varray.h"
#include "tree-chrec.h"
#include "tree-pass.h"
static inline bool
is_not_constant_evolution (tree cst)
{
return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
}
static inline tree
chrec_fold_poly_cst (enum tree_code code,
tree type,
tree poly,
tree cst)
{
gcc_assert (poly);
gcc_assert (cst);
gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
gcc_assert (!is_not_constant_evolution (cst));
switch (code)
{
case PLUS_EXPR:
return build_polynomial_chrec
(CHREC_VARIABLE (poly),
chrec_fold_plus (type, CHREC_LEFT (poly), cst),
CHREC_RIGHT (poly));
case MINUS_EXPR:
return build_polynomial_chrec
(CHREC_VARIABLE (poly),
chrec_fold_minus (type, CHREC_LEFT (poly), cst),
CHREC_RIGHT (poly));
case MULT_EXPR:
return build_polynomial_chrec
(CHREC_VARIABLE (poly),
chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
default:
return chrec_dont_know;
}
}
static inline tree
chrec_fold_plus_poly_poly (enum tree_code code,
tree type,
tree poly0,
tree poly1)
{
tree left, right;
gcc_assert (poly0);
gcc_assert (poly1);
gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
{
if (code == PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (poly1),
chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
CHREC_RIGHT (poly1));
else
return build_polynomial_chrec
(CHREC_VARIABLE (poly1),
chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
chrec_fold_multiply (type, CHREC_RIGHT (poly1),
build_int_cst_type (type, -1)));
}
if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
{
if (code == PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (poly0),
chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
CHREC_RIGHT (poly0));
else
return build_polynomial_chrec
(CHREC_VARIABLE (poly0),
chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
CHREC_RIGHT (poly0));
}
if (code == PLUS_EXPR)
{
left = chrec_fold_plus
(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
right = chrec_fold_plus
(type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
}
else
{
left = chrec_fold_minus
(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
right = chrec_fold_minus
(type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
}
if (chrec_zerop (right))
return left;
else
return build_polynomial_chrec
(CHREC_VARIABLE (poly0), left, right);
}
static inline tree
chrec_fold_multiply_poly_poly (tree type,
tree poly0,
tree poly1)
{
gcc_assert (poly0);
gcc_assert (poly1);
gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
return build_polynomial_chrec
(CHREC_VARIABLE (poly1),
chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
CHREC_RIGHT (poly1));
if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
return build_polynomial_chrec
(CHREC_VARIABLE (poly0),
chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
CHREC_RIGHT (poly0));
return
build_polynomial_chrec
(CHREC_VARIABLE (poly0),
build_polynomial_chrec
(CHREC_VARIABLE (poly0),
chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)),
chrec_fold_plus
(type, chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)),
chrec_fold_plus
(type,
chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_LEFT (poly1)),
chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))))),
chrec_fold_multiply
(type, build_int_cst (NULL_TREE, 2),
chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))));
}
static inline tree
chrec_fold_automatically_generated_operands (tree op0,
tree op1)
{
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know)
return chrec_dont_know;
if (op0 == chrec_known
|| op1 == chrec_known)
return chrec_known;
if (op0 == chrec_not_analyzed_yet
|| op1 == chrec_not_analyzed_yet)
return chrec_not_analyzed_yet;
return chrec_dont_know;
}
static tree
chrec_fold_plus_1 (enum tree_code code,
tree type,
tree op0,
tree op1)
{
if (automatically_generated_chrec_p (op0)
|| automatically_generated_chrec_p (op1))
return chrec_fold_automatically_generated_operands (op0, op1);
switch (TREE_CODE (op0))
{
case POLYNOMIAL_CHREC:
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
return chrec_fold_plus_poly_poly (code, type, op0, op1);
default:
if (code == PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
chrec_fold_plus (type, CHREC_LEFT (op0), op1),
CHREC_RIGHT (op0));
else
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
chrec_fold_minus (type, CHREC_LEFT (op0), op1),
CHREC_RIGHT (op0));
}
default:
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
if (code == PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
CHREC_RIGHT (op1));
else
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
chrec_fold_multiply (type, CHREC_RIGHT (op1),
build_int_cst_type (type, -1)));
default:
if (tree_contains_chrecs (op0)
|| tree_contains_chrecs (op1))
return build (code, type, op0, op1);
else
return fold (build (code, type, op0, op1));
}
}
}
tree
chrec_fold_plus (tree type,
tree op0,
tree op1)
{
if (integer_zerop (op0))
return op1;
if (integer_zerop (op1))
return op0;
return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
}
tree
chrec_fold_minus (tree type,
tree op0,
tree op1)
{
if (integer_zerop (op1))
return op0;
return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
}
tree
chrec_fold_multiply (tree type,
tree op0,
tree op1)
{
if (automatically_generated_chrec_p (op0)
|| automatically_generated_chrec_p (op1))
return chrec_fold_automatically_generated_operands (op0, op1);
switch (TREE_CODE (op0))
{
case POLYNOMIAL_CHREC:
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
return chrec_fold_multiply_poly_poly (type, op0, op1);
default:
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
return build_int_cst_type (type, 0);
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
}
default:
if (integer_onep (op0))
return op1;
if (integer_zerop (op0))
return build_int_cst_type (type, 0);
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
default:
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
return build_int_cst_type (type, 0);
return fold (build (MULT_EXPR, type, op0, op1));
}
}
}
static tree
tree_fold_binomial (tree type, tree n, unsigned int k)
{
unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
unsigned int i;
tree res;
if (k == 0)
return build_int_cst (type, 1);
if (k == 1)
return fold_convert (type, n);
if (TREE_INT_CST_HIGH (n) == 0
&& TREE_INT_CST_LOW (n) < k)
return NULL_TREE;
lnum = TREE_INT_CST_LOW (n);
hnum = TREE_INT_CST_HIGH (n);
ldenom = 2;
hdenom = 0;
if (lnum == 0)
{
hidx = hnum - 1;
lidx = ~ (unsigned HOST_WIDE_INT) 0;
}
else
{
hidx = hnum;
lidx = lnum - 1;
}
if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
return NULL_TREE;
if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
return NULL_TREE;
for (i = 3; i <= k; i++)
{
if (lidx == 0)
{
hidx--;
lidx = ~ (unsigned HOST_WIDE_INT) 0;
}
else
lidx--;
if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
return NULL_TREE;
mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
}
div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
&lres, &hres, &ldum, &hdum);
res = build_int_cst_wide (type, lres, hres);
return int_fits_type_p (res, type) ? res : NULL_TREE;
}
static tree
chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
{
tree arg0, arg1, binomial_n_k;
tree type = TREE_TYPE (chrec);
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (chrec) > var)
chrec = CHREC_LEFT (chrec);
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (chrec) == var)
{
arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
if (arg0 == chrec_dont_know)
return chrec_dont_know;
binomial_n_k = tree_fold_binomial (type, n, k);
if (!binomial_n_k)
return chrec_dont_know;
arg1 = fold (build2 (MULT_EXPR, type,
CHREC_LEFT (chrec), binomial_n_k));
return chrec_fold_plus (type, arg0, arg1);
}
binomial_n_k = tree_fold_binomial (type, n, k);
if (!binomial_n_k)
return chrec_dont_know;
return fold (build2 (MULT_EXPR, type, chrec, binomial_n_k));
}
tree
chrec_apply (unsigned var,
tree chrec,
tree x)
{
tree type = chrec_type (chrec);
tree res = chrec_dont_know;
if (automatically_generated_chrec_p (chrec)
|| automatically_generated_chrec_p (x)
|| chrec_contains_symbols_defined_in_loop (chrec, var)
|| chrec_contains_symbols (x))
return chrec_dont_know;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(chrec_apply \n");
if (evolution_function_is_affine_p (chrec))
{
if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
&& integer_zerop (CHREC_LEFT (chrec)))
res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
else
res = chrec_fold_plus (type, CHREC_LEFT (chrec),
chrec_fold_multiply (type,
CHREC_RIGHT (chrec), x));
}
else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
res = chrec;
else if (TREE_CODE (x) == INTEGER_CST
&& tree_int_cst_sgn (x) == 1)
res = chrec_evaluate (var, chrec, x, 0);
else
res = chrec_dont_know;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (varying_loop = %d\n", var);
fprintf (dump_file, ")\n (chrec = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, ")\n (x = ");
print_generic_expr (dump_file, x, 0);
fprintf (dump_file, ")\n (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
tree
chrec_replace_initial_condition (tree chrec,
tree init_cond)
{
if (automatically_generated_chrec_p (chrec))
return chrec;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
return build_polynomial_chrec
(CHREC_VARIABLE (chrec),
chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
CHREC_RIGHT (chrec));
default:
return init_cond;
}
}
tree
initial_condition (tree chrec)
{
if (automatically_generated_chrec_p (chrec))
return chrec;
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
return initial_condition (CHREC_LEFT (chrec));
else
return chrec;
}
tree
hide_evolution_in_other_loops_than_loop (tree chrec,
unsigned loop_num)
{
if (automatically_generated_chrec_p (chrec))
return chrec;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec) == loop_num)
return build_polynomial_chrec
(loop_num,
hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
loop_num),
CHREC_RIGHT (chrec));
else if (CHREC_VARIABLE (chrec) < loop_num)
return initial_condition (chrec);
else
return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
loop_num);
default:
return chrec;
}
}
static tree
chrec_component_in_loop_num (tree chrec,
unsigned loop_num,
bool right)
{
tree component;
if (automatically_generated_chrec_p (chrec))
return chrec;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec) == loop_num)
{
if (right)
component = CHREC_RIGHT (chrec);
else
component = CHREC_LEFT (chrec);
if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
|| CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
return component;
else
return build_polynomial_chrec
(loop_num,
chrec_component_in_loop_num (CHREC_LEFT (chrec),
loop_num,
right),
component);
}
else if (CHREC_VARIABLE (chrec) < loop_num)
return NULL_TREE;
else
return chrec_component_in_loop_num (CHREC_LEFT (chrec),
loop_num,
right);
default:
if (right)
return NULL_TREE;
else
return chrec;
}
}
tree
evolution_part_in_loop_num (tree chrec,
unsigned loop_num)
{
return chrec_component_in_loop_num (chrec, loop_num, true);
}
tree
initial_condition_in_loop_num (tree chrec,
unsigned loop_num)
{
return chrec_component_in_loop_num (chrec, loop_num, false);
}
tree
reset_evolution_in_loop (unsigned loop_num,
tree chrec,
tree new_evol)
{
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (chrec) > loop_num)
return build
(TREE_CODE (chrec),
build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (chrec) == loop_num)
chrec = CHREC_LEFT (chrec);
return build_polynomial_chrec (loop_num, chrec, new_evol);
}
tree
chrec_merge (tree chrec1,
tree chrec2)
{
if (chrec1 == chrec_dont_know
|| chrec2 == chrec_dont_know)
return chrec_dont_know;
if (chrec1 == chrec_known
|| chrec2 == chrec_known)
return chrec_known;
if (chrec1 == chrec_not_analyzed_yet)
return chrec2;
if (chrec2 == chrec_not_analyzed_yet)
return chrec1;
if (operand_equal_p (chrec1, chrec2, 0))
return chrec1;
return chrec_dont_know;
}
static bool
is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
{
if (chrec == NULL_TREE)
return false;
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
{
if (CHREC_VARIABLE (chrec) != rec_var)
return true;
else
return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
}
else
return false;
}
bool
is_multivariate_chrec (tree chrec)
{
if (chrec == NULL_TREE)
return false;
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
CHREC_VARIABLE (chrec))
|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
CHREC_VARIABLE (chrec)));
else
return false;
}
bool
chrec_contains_symbols (tree chrec)
{
if (chrec == NULL_TREE)
return false;
if (TREE_CODE (chrec) == SSA_NAME
|| 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;
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
return true;
case 2:
if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
return true;
case 1:
if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
return true;
default:
return false;
}
}
bool
chrec_contains_undetermined (tree chrec)
{
if (chrec == chrec_dont_know
|| chrec == chrec_not_analyzed_yet
|| chrec == NULL_TREE)
return true;
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
return true;
case 2:
if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
return true;
case 1:
if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
return true;
default:
return false;
}
}
bool
tree_contains_chrecs (tree expr)
{
if (expr == NULL_TREE)
return false;
if (tree_is_chrec (expr))
return true;
switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
{
case 3:
if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
return true;
case 2:
if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
return true;
case 1:
if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
return true;
default:
return false;
}
}
bool
evolution_function_is_affine_multivariate_p (tree chrec)
{
if (chrec == NULL_TREE)
return false;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
{
if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
return true;
else
{
if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (CHREC_RIGHT (chrec))
!= CHREC_VARIABLE (chrec)
&& evolution_function_is_affine_multivariate_p
(CHREC_RIGHT (chrec)))
return true;
else
return false;
}
}
else
{
if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
&& TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
&& evolution_function_is_affine_multivariate_p
(CHREC_LEFT (chrec)))
return true;
else
return false;
}
default:
return false;
}
}
bool
evolution_function_is_univariate_p (tree chrec)
{
if (chrec == NULL_TREE)
return true;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
switch (TREE_CODE (CHREC_LEFT (chrec)))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
return false;
if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
return false;
break;
default:
break;
}
switch (TREE_CODE (CHREC_RIGHT (chrec)))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
return false;
if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
return false;
break;
default:
break;
}
default:
return true;
}
}
unsigned
nb_vars_in_chrec (tree chrec)
{
if (chrec == NULL_TREE)
return 0;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
return 1 + nb_vars_in_chrec
(initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
default:
return 0;
}
}
tree
chrec_convert (tree type,
tree chrec)
{
tree ct;
if (automatically_generated_chrec_p (chrec))
return chrec;
ct = chrec_type (chrec);
if (ct == type)
return chrec;
if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
return count_ev_in_wider_type (type, chrec);
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
return build_polynomial_chrec (CHREC_VARIABLE (chrec),
chrec_convert (type,
CHREC_LEFT (chrec)),
chrec_convert (type,
CHREC_RIGHT (chrec)));
default:
{
tree res = convert (type, chrec);
TREE_OVERFLOW (res) = 0;
if (CONSTANT_CLASS_P (res))
TREE_CONSTANT_OVERFLOW (res) = 0;
return res;
}
}
}
tree
chrec_type (tree chrec)
{
if (automatically_generated_chrec_p (chrec))
return NULL_TREE;
return TREE_TYPE (chrec);
}