diff options
Diffstat (limited to 'gcc/tree-chrec.c')
| -rw-r--r-- | gcc/tree-chrec.c | 2000 |
1 files changed, 2000 insertions, 0 deletions
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c new file mode 100644 index 00000000000..d00aabb24f7 --- /dev/null +++ b/gcc/tree-chrec.c @@ -0,0 +1,2000 @@ +/* Chains of recurrences. + Copyright (C) 2003 Free Software Foundation, Inc. + Contributed by Sebastian Pop <s.pop@laposte.net> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* This file implements operations on chains of recurrences. Chains + of recurrences are used for modeling evolution functions of scalar + variables. +*/ + +#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-fold-const.h" +#include "tree-chrec.h" +#include "tree-pass.h" + + +/* Extended folder for chrecs. */ + +/* Determines whether CST is not a constant evolution. */ + +static inline bool +is_not_constant_evolution (tree cst) +{ + return (TREE_CODE (cst) == POLYNOMIAL_CHREC + || TREE_CODE (cst) == EXPONENTIAL_CHREC + || TREE_CODE (cst) == PEELED_CHREC); +} + +/* Fold CODE for a polynomial function and a constant. */ + +static inline tree +chrec_fold_poly_cst (enum tree_code code, + tree type, + tree poly, + tree cst) +{ +#if defined ENABLE_CHECKING + if (poly == NULL_TREE + || cst == NULL_TREE + || TREE_CODE (poly) != POLYNOMIAL_CHREC + || is_not_constant_evolution (cst)) + abort (); +#endif + + 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_top; + } +} + +/* Fold the addition of a peeled chrec and a constant. */ + +static inline tree +chrec_fold_plus_peel_cst (tree type, + tree peel, + tree cst) +{ +#if defined ENABLE_CHECKING + if (peel == NULL_TREE + || cst == NULL_TREE + || TREE_CODE (peel) != PEELED_CHREC + || is_not_constant_evolution (cst)) + abort (); +#endif + + return build_peeled_chrec + (CHREC_VARIABLE (peel), + chrec_fold_plus (type, CHREC_LEFT (peel), cst), + chrec_fold_plus (type, CHREC_RIGHT (peel), cst)); +} + +/* Fold the addition of an exponential function and a constant. */ + +static inline tree +chrec_fold_plus_expo_cst (enum tree_code code, + tree type, + tree expo, + tree cst) +{ +#if defined ENABLE_CHECKING + if (expo == NULL_TREE + || cst == NULL_TREE + || TREE_CODE (expo) != EXPONENTIAL_CHREC + || is_not_constant_evolution (cst)) + abort (); +#endif + + /* For the moment, we don't know how to fold this further. */ + return build (code, type, expo, cst); +} + +/* Fold the addition of an exponential function and a constant. */ + +static inline tree +chrec_fold_plus_cst_expo (enum tree_code code, + tree type, + tree cst, + tree expo) +{ +#if defined ENABLE_CHECKING + if (expo == NULL_TREE + || cst == NULL_TREE + || TREE_CODE (expo) != EXPONENTIAL_CHREC + || is_not_constant_evolution (cst)) + abort (); +#endif + + /* For the moment, we don't know how to fold this further. */ + return build (code, type, cst, expo); +} + +/* Fold the addition of two polynomial functions. */ + +static inline tree +chrec_fold_plus_poly_poly (enum tree_code code, + tree type, + tree poly0, + tree poly1) +{ + tree left, right; + +#if defined ENABLE_CHECKING + if (poly0 == NULL_TREE + || poly1 == NULL_TREE + || TREE_CODE (poly0) != POLYNOMIAL_CHREC + || TREE_CODE (poly1) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* + {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, + {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, + {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ + 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 (integer_type_node, CHREC_RIGHT (poly1), + integer_minus_one_node)); + } + + 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); +} + +/* Fold the addition of a polynomial and a peeled chrec. */ + +static inline tree +chrec_fold_plus_poly_peel (enum tree_code code, + tree type, + tree poly, + tree peel) +{ +#if defined ENABLE_CHECKING + if (peel == NULL_TREE + || poly == NULL_TREE + || TREE_CODE (peel) != PEELED_CHREC + || TREE_CODE (poly) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* + {a, +, b}_1 + (c, d)_2 -> ({a, +, b}_1 + c, {a, +, b}_1 + d)_2, + {a, +, b}_2 + (c, d)_1 -> {a + (c, d)_1, +, b}_2, + {a, +, b}_x + (c, d)_x -> ({a, +, b}_x + c, {a, +, b}_x + d)_x. */ + if (CHREC_VARIABLE (poly) < CHREC_VARIABLE (peel)) + return build_peeled_chrec + (CHREC_VARIABLE (peel), + (code == PLUS_EXPR ? + chrec_fold_plus (type, poly, CHREC_LEFT (peel)) : + chrec_fold_minus (type, poly, CHREC_LEFT (peel))), + (code == PLUS_EXPR ? + chrec_fold_plus (type, poly, CHREC_RIGHT (peel)) : + chrec_fold_minus (type, poly, CHREC_RIGHT (peel)))); + + if (CHREC_VARIABLE (poly) > CHREC_VARIABLE (peel)) + return build_polynomial_chrec + (CHREC_VARIABLE (poly), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_LEFT (poly), peel) : + chrec_fold_minus (type, CHREC_LEFT (poly), peel)), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_RIGHT (poly), peel) : + chrec_fold_minus (type, CHREC_RIGHT (poly), peel))); + + return build_peeled_chrec + (CHREC_VARIABLE (peel), + (code == PLUS_EXPR ? + chrec_fold_plus (type, poly, CHREC_LEFT (peel)) : + chrec_fold_minus (type, poly, CHREC_LEFT (peel))), + (code == PLUS_EXPR ? + chrec_fold_plus (type, poly, CHREC_RIGHT (peel)) : + chrec_fold_minus (type, poly, CHREC_RIGHT (peel)))); +} + +/* Fold the addition of a polynomial and a peeled chrec. */ + +static inline tree +chrec_fold_plus_peel_poly (enum tree_code code, + tree type, + tree peel, + tree poly) +{ +#if defined ENABLE_CHECKING + if (peel == NULL_TREE + || poly == NULL_TREE + || TREE_CODE (peel) != PEELED_CHREC + || TREE_CODE (poly) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* + {a, +, b}_1 + (c, d)_2 -> ({a, +, b}_1 + c, {a, +, b}_1 + d)_2, + {a, +, b}_2 + (c, d)_1 -> {a + (c, d)_1, +, b}_2, + {a, +, b}_x + (c, d)_x -> ({a, +, b}_x + c, {a, +, b}_x + d)_x. */ + if (CHREC_VARIABLE (poly) < CHREC_VARIABLE (peel)) + return build_peeled_chrec + (CHREC_VARIABLE (peel), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_LEFT (peel), poly) : + chrec_fold_minus (type, CHREC_LEFT (peel), poly)), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_RIGHT (peel), poly) : + chrec_fold_minus (type, CHREC_RIGHT (peel), poly))); + + if (CHREC_VARIABLE (poly) > CHREC_VARIABLE (peel)) + return build_polynomial_chrec + (CHREC_VARIABLE (poly), + (code == PLUS_EXPR ? + chrec_fold_plus (type, peel, CHREC_LEFT (poly)) : + chrec_fold_minus (type, peel, CHREC_LEFT (poly))), + (code == PLUS_EXPR ? + chrec_fold_plus (type, peel, CHREC_RIGHT (poly)) : + chrec_fold_minus (type, peel, CHREC_RIGHT (poly)))); + + return build_peeled_chrec + (CHREC_VARIABLE (peel), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_LEFT (peel), poly) : + chrec_fold_minus (type, CHREC_LEFT (peel), poly)), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_RIGHT (peel), poly) : + chrec_fold_minus (type, CHREC_RIGHT (peel), poly))); +} + +/* Fold the addition of a polynomial and an exponential functions. */ + +static inline tree +chrec_fold_plus_poly_expo (enum tree_code code, + tree type, + tree poly, + tree expo) +{ +#if defined ENABLE_CHECKING + if (expo == NULL_TREE + || poly == NULL_TREE + || TREE_CODE (expo) != EXPONENTIAL_CHREC + || TREE_CODE (poly) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* For the moment, we don't know how to fold this further. */ + return build (code, type, poly, expo); +} + +/* Fold the addition of a polynomial and an exponential functions. */ + +static inline tree +chrec_fold_plus_expo_poly (enum tree_code code, + tree type, + tree expo, + tree poly) +{ +#if defined ENABLE_CHECKING + if (expo == NULL_TREE + || poly == NULL_TREE + || TREE_CODE (expo) != EXPONENTIAL_CHREC + || TREE_CODE (poly) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* For the moment, we don't know how to fold this further. */ + return build (code, type, expo, poly); +} + +/* Fold the addition of two peeled chrecs. */ + +static inline tree +chrec_fold_plus_peel_peel (tree type, + tree peel0, + tree peel1) +{ +#if defined ENABLE_CHECKING + if (peel0 == NULL_TREE + || peel1 == NULL_TREE + || TREE_CODE (peel0) != PEELED_CHREC + || TREE_CODE (peel1) != PEELED_CHREC) + abort (); +#endif + + /* + (a, b)_1 + (c, d)_2 -> ((a, b)_1 + c, (a, b)_1 + d)_2, + (a, b)_2 + (c, d)_1 -> (a + (c, d)_1, b + (c, d)_1)_2, + (a, b)_x + (c, d)_x -> (a + c, b + d)_x. */ + if (CHREC_VARIABLE (peel0) < CHREC_VARIABLE (peel1)) + return build_peeled_chrec + (CHREC_VARIABLE (peel1), + chrec_fold_plus (type, peel0, CHREC_LEFT (peel1)), + chrec_fold_plus (type, peel0, CHREC_RIGHT (peel1))); + + if (CHREC_VARIABLE (peel0) > CHREC_VARIABLE (peel1)) + return build_peeled_chrec + (CHREC_VARIABLE (peel0), + chrec_fold_plus (type, CHREC_LEFT (peel0), peel1), + chrec_fold_plus (type, CHREC_RIGHT (peel0), peel1)); + + return build_peeled_chrec + (CHREC_VARIABLE (peel0), + chrec_fold_plus (type, CHREC_LEFT (peel0), CHREC_LEFT (peel1)), + chrec_fold_plus (type, CHREC_RIGHT (peel0), CHREC_RIGHT (peel1))); +} + +/* Fold the addition of two exponential functions. */ + +static inline tree +chrec_fold_plus_expo_expo (enum tree_code code, + tree type, + tree expo0, + tree expo1) +{ +#if defined ENABLE_CHECKING + if (expo0 == NULL_TREE + || expo1 == NULL_TREE + || TREE_CODE (expo0) != EXPONENTIAL_CHREC + || TREE_CODE (expo1) != EXPONENTIAL_CHREC) + abort (); +#endif + + /* For the moment, we don't know how to fold this further. */ + return build (code, type, expo0, expo1); +} + + + +/* Fold the multiplication of a peeled chrec and a constant. */ + +static inline tree +chrec_fold_multiply_peel_cst (tree type, + tree peel, + tree cst) +{ +#if defined ENABLE_CHECKING + if (peel == NULL_TREE + || cst == NULL_TREE + || TREE_CODE (peel) != PEELED_CHREC + || is_not_constant_evolution (cst)) + abort (); +#endif + + return build_peeled_chrec + (CHREC_VARIABLE (peel), + chrec_fold_multiply (type, CHREC_LEFT (peel), cst), + chrec_fold_multiply (type, CHREC_RIGHT (peel), cst)); +} + +/* Fold the multiplication of an interval and a constant. */ + +static inline tree +chrec_fold_multiply_ival_cst (tree type, + tree ival, + tree cst) +{ + tree lowm, upm; + bool pos; + +#if defined ENABLE_CHECKING + if (ival == NULL_TREE + || cst == NULL_TREE + || TREE_CODE (ival) != INTERVAL_CHREC + || is_not_constant_evolution (cst)) + abort (); +#endif + + /* Don't modify abstract values. */ + if (ival == chrec_top) + return chrec_top; + if (ival == chrec_bot) + return chrec_bot; + + if (!chrec_is_positive (cst, &pos)) + return chrec_top; + + lowm = chrec_fold_multiply (type, CHREC_LOW (ival), cst); + upm = chrec_fold_multiply (type, CHREC_UP (ival), cst); + + if (pos) + return build_interval_chrec (lowm, upm); + else + return build_interval_chrec (upm, lowm); +} + +/* Fold the multiplication of two polynomial functions. */ + +static inline tree +chrec_fold_multiply_poly_poly (tree type, + tree poly0, + tree poly1) +{ +#if defined ENABLE_CHECKING + if (poly0 == NULL_TREE + || poly1 == NULL_TREE + || TREE_CODE (poly0) != POLYNOMIAL_CHREC + || TREE_CODE (poly1) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, + {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, + {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ + if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) + /* poly0 is a constant wrt. 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)) + /* poly1 is a constant wrt. poly0. */ + return build_polynomial_chrec + (CHREC_VARIABLE (poly0), + chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), + CHREC_RIGHT (poly0)); + + /* poly0 and poly1 are two polynomials in the same variable, + {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ + return + build_polynomial_chrec + (CHREC_VARIABLE (poly0), + build_polynomial_chrec + (CHREC_VARIABLE (poly0), + + /* "a*c". */ + chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)), + + /* "a*d + b*c + b*d". */ + 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))))), + + /* "2*b*d". */ + chrec_fold_multiply + (type, build_int_2 (2, 0), + chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)))); +} + +/* Fold the addition of a polynomial and a peeled chrec. */ + +static inline tree +chrec_fold_multiply_poly_peel (tree type, + tree poly, + tree peel) +{ +#if defined ENABLE_CHECKING + if (peel == NULL_TREE + || poly == NULL_TREE + || TREE_CODE (peel) != PEELED_CHREC + || TREE_CODE (poly) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* + {a, +, b}_1 * (c, d)_2 -> ({a, +, b}_1 * c, {a, +, b}_1 * d)_2, + {a, +, b}_2 * (c, d)_1 -> {a * (c, d)_1, +, b}_2, + {a, +, b}_x * (c, d)_x -> ({a, +, b}_x * c, {a, +, b}_x * d)_x. */ + if (CHREC_VARIABLE (poly) < CHREC_VARIABLE (peel)) + return build_peeled_chrec + (CHREC_VARIABLE (peel), + chrec_fold_multiply (type, poly, CHREC_LEFT (peel)), + chrec_fold_multiply (type, poly, CHREC_RIGHT (peel))); + + if (CHREC_VARIABLE (poly) > CHREC_VARIABLE (peel)) + return build_polynomial_chrec + (CHREC_VARIABLE (poly), + chrec_fold_multiply (type, CHREC_LEFT (poly), peel), + chrec_fold_multiply (type, CHREC_RIGHT (poly), peel)); + + return build_peeled_chrec + (CHREC_VARIABLE (peel), + chrec_fold_multiply (type, poly, CHREC_LEFT (peel)), + chrec_fold_multiply (type, poly, CHREC_RIGHT (peel))); +} + +/* Fold the multiplication of a polynomial and an exponential + functions. */ + +static inline tree +chrec_fold_multiply_poly_expo (tree type, + tree poly, + tree expo) +{ +#if defined ENABLE_CHECKING + if (expo == NULL_TREE + || poly == NULL_TREE + || TREE_CODE (expo) != EXPONENTIAL_CHREC + || TREE_CODE (poly) != POLYNOMIAL_CHREC) + abort (); +#endif + + /* For the moment, we don't know how to fold this further. */ + return build (MULT_EXPR, type, expo, poly); +} + +/* Fold the addition of two peeled chrecs. */ + +static inline tree +chrec_fold_multiply_peel_peel (tree type, + tree peel0, + tree peel1) +{ +#if defined ENABLE_CHECKING + if (peel0 == NULL_TREE + || peel1 == NULL_TREE + || TREE_CODE (peel0) != PEELED_CHREC + || TREE_CODE (peel1) != PEELED_CHREC) + abort (); +#endif + + /* + (a, b)_1 * (c, d)_2 -> ((a, b)_1 * c, (a, b)_1 * d)_2, + (a, b)_2 * (c, d)_1 -> (a * (c, d)_1, b * (c, d)_1)_2, + (a, b)_x * (c, d)_x -> (a * c, b * d)_x. */ + if (CHREC_VARIABLE (peel0) < CHREC_VARIABLE (peel1)) + return build_peeled_chrec + (CHREC_VARIABLE (peel1), + chrec_fold_multiply (type, peel0, CHREC_LEFT (peel1)), + chrec_fold_multiply (type, peel0, CHREC_RIGHT (peel1))); + + if (CHREC_VARIABLE (peel0) > CHREC_VARIABLE (peel1)) + return build_peeled_chrec + (CHREC_VARIABLE (peel0), + chrec_fold_multiply (type, CHREC_LEFT (peel0), peel1), + chrec_fold_multiply (type, CHREC_RIGHT (peel0), peel1)); + + return build_peeled_chrec + (CHREC_VARIABLE (peel0), + chrec_fold_multiply (type, CHREC_LEFT (peel0), CHREC_LEFT (peel1)), + chrec_fold_multiply (type, CHREC_RIGHT (peel0), CHREC_RIGHT (peel1))); +} + +/* Fold the multiplication of two exponential functions. */ + +static inline tree +chrec_fold_multiply_expo_expo (tree type, + tree expo0, + tree expo1) +{ +#if defined ENABLE_CHECKING + if (expo0 == NULL_TREE + || expo1 == NULL_TREE + || TREE_CODE (expo0) != EXPONENTIAL_CHREC + || TREE_CODE (expo1) != EXPONENTIAL_CHREC) + abort (); +#endif + + if (CHREC_VARIABLE (expo0) < CHREC_VARIABLE (expo1)) + /* expo0 is a constant wrt. expo1. */ + return build_exponential_chrec + (CHREC_VARIABLE (expo1), + chrec_fold_multiply (type, CHREC_LEFT (expo1), expo0), + CHREC_RIGHT (expo1)); + + if (CHREC_VARIABLE (expo1) < CHREC_VARIABLE (expo0)) + /* expo1 is a constant wrt. expo0. */ + return build_exponential_chrec + (CHREC_VARIABLE (expo0), + chrec_fold_multiply (type, CHREC_LEFT (expo0), expo1), + CHREC_RIGHT (expo0)); + + return build_exponential_chrec + (CHREC_VARIABLE (expo0), + chrec_fold_multiply (type, CHREC_LEFT (expo0), CHREC_LEFT (expo1)), + chrec_fold_multiply (type, CHREC_RIGHT (expo0), CHREC_RIGHT (expo1))); +} + +/* Fold the multiplication of two intervals. */ + +static inline tree +chrec_fold_multiply_ival_ival (tree type, + tree ival0, + tree ival1) +{ + tree ac, ad, bc, bd; + +#if defined ENABLE_CHECKING + if (ival0 == NULL_TREE + || ival1 == NULL_TREE + || TREE_CODE (ival0) != INTERVAL_CHREC + || TREE_CODE (ival1) != INTERVAL_CHREC) + abort (); +#endif + + /* Don't modify abstract values. */ + if (automatically_generated_chrec_p (ival0) + || automatically_generated_chrec_p (ival1)) + chrec_fold_automatically_generated_operands (ival0, ival1); + + ac = tree_fold_multiply (type, CHREC_LOW (ival0), CHREC_LOW (ival1)); + ad = tree_fold_multiply (type, CHREC_LOW (ival0), CHREC_UP (ival1)); + bc = tree_fold_multiply (type, CHREC_UP (ival0), CHREC_LOW (ival1)); + bd = tree_fold_multiply (type, CHREC_UP (ival0), CHREC_UP (ival1)); + + /* [a, b] * [c, d] -> [min (ac, ad, bc, bd), max (ac, ad, bc, bd)], + for reference, see Moore's "Interval Arithmetic". */ + return build_interval_chrec + (tree_fold_min + (type, tree_fold_min + (type, tree_fold_min (type, ac, ad), bc), bd), + tree_fold_max + (type, tree_fold_max + (type, tree_fold_max (type, ac, ad), bc), bd)); +} + +/* When the operands are automatically_generated_chrec_p, the fold has + to respect the semantics of the operands. */ + +tree +chrec_fold_automatically_generated_operands (tree op0, + tree op1) +{ + /* TOP op x = TOP, + x op TOP = TOP. */ + if (op0 == chrec_top + || op1 == chrec_top) + return chrec_top; + + /* BOT op TOP = TOP, + TOP op BOT = TOP, + BOT op x = BOT, + x op BOT = BOT. */ + if (op0 == chrec_bot + || op1 == chrec_bot) + return chrec_bot; + + if (op0 == chrec_not_analyzed_yet + || op1 == chrec_not_analyzed_yet) + return chrec_not_analyzed_yet; + + /* The default case produces a safe result. */ + return chrec_top; +} + +/* Fold the addition of two chrecs. */ + +static tree +chrec_fold_plus_1 (enum tree_code code, + tree type, + tree op0, + tree op1) +{ + tree t1, t2; + + 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); + + case EXPONENTIAL_CHREC: + return chrec_fold_plus_poly_expo (code, type, op0, op1); + + case PEELED_CHREC: + return chrec_fold_plus_poly_peel (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)); + } + + case EXPONENTIAL_CHREC: + switch (TREE_CODE (op1)) + { + case POLYNOMIAL_CHREC: + return chrec_fold_plus_expo_poly (code, type, op0, op1); + + case EXPONENTIAL_CHREC: + return chrec_fold_plus_expo_expo (code, type, op0, op1); + + case PEELED_CHREC: + return build (code, type, op0, op1); + + default: + return chrec_fold_plus_expo_cst (code, type, op0, op1); + } + + case PEELED_CHREC: + switch (TREE_CODE (op1)) + { + case POLYNOMIAL_CHREC: + return chrec_fold_plus_peel_poly (code, type, op0, op1); + + case PEELED_CHREC: + return chrec_fold_plus_peel_peel (type, op0, op1); + + case EXPONENTIAL_CHREC: + return build (code, type, op0, op1); + + default: + return build_peeled_chrec + (CHREC_VARIABLE (op0), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_LEFT (op0), op1) : + chrec_fold_minus (type, CHREC_LEFT (op0), op1)), + (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_RIGHT (op0), op1) : + chrec_fold_minus (type, CHREC_RIGHT (op0), op1))); + } + + case INTERVAL_CHREC: + switch (TREE_CODE (op1)) + { + case POLYNOMIAL_CHREC: + return build_polynomial_chrec + (CHREC_VARIABLE (op1), + (code == PLUS_EXPR ? + chrec_fold_plus (type, op0, CHREC_LEFT (op1)) : + chrec_fold_minus (type, op0, CHREC_LEFT (op1))), + CHREC_RIGHT (op1)); + + case EXPONENTIAL_CHREC: + return chrec_fold_plus_cst_expo (code, type, op0, op1); + + case INTERVAL_CHREC: + t1 = (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_LOW (op0), CHREC_LOW (op1)) : + chrec_fold_minus (type, CHREC_LOW (op0), CHREC_LOW (op1))); + t2 = (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_UP (op0), CHREC_UP (op1)) : + chrec_fold_minus (type, CHREC_UP (op0), CHREC_UP (op1))); + + return build_interval_chrec + (tree_fold_min (type, t1, t2), + tree_fold_max (type, t1, t2)); + + default: + t1 = (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_LOW (op0), op1) : + chrec_fold_minus (type, CHREC_LOW (op0), op1)); + t2 = (code == PLUS_EXPR ? + chrec_fold_plus (type, CHREC_UP (op0), op1) : + chrec_fold_minus (type, CHREC_UP (op0), op1)); + + return build_interval_chrec + (tree_fold_min (type, t1, t2), + tree_fold_max (type, t1, t2)); + } + + 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), + convert (type, + integer_minus_one_node))); + + case EXPONENTIAL_CHREC: + return chrec_fold_plus_cst_expo (code, type, op0, op1); + + case PEELED_CHREC: + if (code == PLUS_EXPR) + return build_peeled_chrec + (CHREC_VARIABLE (op1), + chrec_fold_plus (type, op0, CHREC_LEFT (op1)), + chrec_fold_plus (type, op0, CHREC_RIGHT (op1))); + else + return build_peeled_chrec + (CHREC_VARIABLE (op1), + chrec_fold_minus (type, op0, CHREC_LEFT (op1)), + chrec_fold_minus (type, op0, CHREC_RIGHT (op1))); + + case INTERVAL_CHREC: + t1 = (code == PLUS_EXPR ? + chrec_fold_plus (type, op0, CHREC_LOW (op1)) : + chrec_fold_minus (type, op0, CHREC_LOW (op1))); + t2 = (code == PLUS_EXPR ? + chrec_fold_plus (type, op0, CHREC_UP (op1)) : + chrec_fold_minus (type, op0, CHREC_UP (op1))); + + return build_interval_chrec + (tree_fold_min (type, t1, t2), + tree_fold_max (type, t1, t2)); + + default: + if (tree_contains_chrecs (op0) + || tree_contains_chrecs (op1)) + return build (code, type, op0, op1); + else + return fold (build (code, type, op0, op1)); + } + } +} + +/* Fold the addition of two chrecs. */ + +tree +chrec_fold_plus (tree type, + tree op0, + tree op1) +{ + if (integer_zerop (op0) + || (TREE_CODE (op0) == INTERVAL_CHREC + && integer_zerop (CHREC_LOW (op0)) + && integer_zerop (CHREC_UP (op0)))) + return op1; + if (integer_zerop (op1) + || (TREE_CODE (op1) == INTERVAL_CHREC + && integer_zerop (CHREC_LOW (op1)) + && integer_zerop (CHREC_UP (op1)))) + return op0; + + return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1); +} + +/* Fold the substraction of two chrecs. */ + +tree +chrec_fold_minus (tree type, + tree op0, + tree op1) +{ + if (integer_zerop (op1) + || (TREE_CODE (op1) == INTERVAL_CHREC + && integer_zerop (CHREC_LOW (op1)) + && integer_zerop (CHREC_UP (op1)))) + return op0; + + return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); +} + +/* Fold the negation of a two chrec. */ + +tree +chrec_fold_negate (tree type, tree op0) +{ + if (integer_zerop (op0) + || (TREE_CODE (op0) == INTERVAL_CHREC + && integer_zerop (CHREC_LOW (op0)) + && integer_zerop (CHREC_UP (op0)))) + return op0; + + return chrec_fold_plus_1 (MINUS_EXPR, type, + convert (type, integer_zero_node), + op0); +} +/* Fold the multiplication of two chrecs. */ + +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); + + case PEELED_CHREC: + return chrec_fold_multiply_poly_peel (type, op0, op1); + + case EXPONENTIAL_CHREC: + return chrec_fold_multiply_poly_expo (type, op0, op1); + + default: + if (integer_onep (op1)) + return op0; + if (integer_zerop (op1)) + return integer_zero_node; + + return build_polynomial_chrec + (CHREC_VARIABLE (op0), + chrec_fold_multiply (type, CHREC_LEFT (op0), op1), + chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); + } + + case PEELED_CHREC: + switch (TREE_CODE (op1)) + { + case POLYNOMIAL_CHREC: + return chrec_fold_multiply_poly_peel (type, op1, op0); + + case PEELED_CHREC: + return chrec_fold_multiply_peel_peel (type, op0, op1); + + default: + if (integer_onep (op1)) + return op0; + if (integer_zerop (op1)) + return integer_zero_node; + + return build_peeled_chrec + (CHREC_VARIABLE (op0), + chrec_fold_multiply (type, CHREC_LEFT (op0), op1), + chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); + } + + case EXPONENTIAL_CHREC: + switch (TREE_CODE (op1)) + { + case POLYNOMIAL_CHREC: + return chrec_fold_multiply_poly_expo (type, op1, op0); + + case EXPONENTIAL_CHREC: + return chrec_fold_multiply_expo_expo (type, op0, op1); + + default: + if (integer_onep (op1)) + return op0; + if (integer_zerop (op1)) + return integer_zero_node; + + return build_exponential_chrec + (CHREC_VARIABLE (op0), + chrec_fold_multiply (type, CHREC_LEFT (op0), op1), + CHREC_RIGHT (op0)); + } + + case INTERVAL_CHREC: + 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)); + + case PEELED_CHREC: + return build_peeled_chrec + (CHREC_VARIABLE (op1), + chrec_fold_multiply (type, CHREC_LEFT (op1), op0), + chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); + + case EXPONENTIAL_CHREC: + return build_exponential_chrec + (CHREC_VARIABLE (op1), + chrec_fold_multiply (type, CHREC_LEFT (op1), op0), + CHREC_RIGHT (op1)); + + case INTERVAL_CHREC: + return chrec_fold_multiply_ival_ival (type, op0, op1); + + default: + if (integer_onep (op1)) + return op0; + if (integer_zerop (op1)) + return integer_zero_node; + return chrec_fold_multiply_ival_cst (type, op0, op1); + } + + default: + if (integer_onep (op0)) + return op1; + + if (integer_zerop (op0)) + return integer_zero_node; + + 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)); + + case PEELED_CHREC: + return build_peeled_chrec + (CHREC_VARIABLE (op1), + chrec_fold_multiply (type, CHREC_LEFT (op1), op0), + chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); + + case EXPONENTIAL_CHREC: + return build_exponential_chrec + (CHREC_VARIABLE (op1), + chrec_fold_multiply (type, CHREC_LEFT (op1), op0), + CHREC_RIGHT (op1)); + + case INTERVAL_CHREC: + return chrec_fold_multiply_ival_cst (type, op1, op0); + + default: + if (integer_onep (op1)) + return op0; + if (integer_zerop (op1)) + return integer_zero_node; + return tree_fold_multiply (type, op0, op1); + } + } +} + + + +/* Operations. */ + +/* Try to recognize the nature of the peeled chrec and to transform it + into a more specific chrec: polynomial, periodic, ... For example, + this function transforms (6, {9, +, 3}_1)_1 into {6, +, 3}_1. */ + +tree +simplify_peeled_chrec (tree peel) +{ + tree res = peel; + + return res; +} + +/* Helper function. Use the Newton's interpolating formula for + evaluating the value of the evolution function. */ + +static tree +chrec_evaluate (unsigned var, + tree chrec, + tree n, + tree k) +{ + tree binomial_n_k = tree_fold_binomial (n, k); + + if (TREE_CODE (chrec) == EXPONENTIAL_CHREC + && CHREC_VARIABLE (chrec) == var) + return chrec_top; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + { + if (CHREC_VARIABLE (chrec) > var) + return chrec_evaluate (var, CHREC_LEFT (chrec), n, k); + + if (CHREC_VARIABLE (chrec) == var) + return chrec_fold_plus + (chrec_type (chrec), + chrec_fold_multiply (chrec_type (CHREC_LEFT (chrec)), + binomial_n_k, + CHREC_LEFT (chrec)), + chrec_evaluate (var, CHREC_RIGHT (chrec), n, + tree_fold_plus (integer_type_node, + k, integer_one_node))); + + return chrec_fold_multiply (chrec_type (chrec), binomial_n_k, chrec); + } + else + return chrec_fold_multiply (chrec_type (chrec), binomial_n_k, chrec); +} + +/* Evaluates "CHREC (X)" when the varying variable is VAR. + Example: Given the following parameters, + + var = 1 + chrec = {5, +, {3, +, 4}_1}_1 + x = 10 + + The result is given by the Newton's interpolating formula: + 5 * \binom{10}{0} + 3 * \binom{10}{1} + 4 * \binom{10}{2}. +*/ + +tree +chrec_apply (unsigned var, + tree chrec, + tree x) +{ + tree res = chrec_top; + + if (automatically_generated_chrec_p (chrec) + || automatically_generated_chrec_p (x)) + return chrec_top; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(chrec_apply \n"); + + if (evolution_function_is_affine_p (chrec)) + { + /* "{a, +, b} (x)" -> "a + b*x". */ + if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST + && integer_zerop (CHREC_LEFT (chrec))) + res = chrec_fold_multiply + (chrec_type (chrec), CHREC_RIGHT (chrec), x); + + else + res = chrec_fold_plus (chrec_type (chrec), + CHREC_LEFT (chrec), + chrec_fold_multiply + (chrec_type (chrec), CHREC_RIGHT (chrec), x)); + } + + else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC + && TREE_CODE (chrec) != EXPONENTIAL_CHREC) + res = chrec; + + else if (TREE_CODE (x) == INTEGER_CST + && tree_int_cst_sgn (x) == 1) + /* testsuite/.../ssa-chrec-38.c. */ + res = chrec_evaluate (var, chrec, x, integer_zero_node); + + else + res = chrec_top; + + 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; +} + +/* Replaces the initial condition in CHREC with INIT_COND. */ + +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)); + + case EXPONENTIAL_CHREC: + return build_exponential_chrec + (CHREC_VARIABLE (chrec), + chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), + CHREC_RIGHT (chrec)); + + case PEELED_CHREC: + return chrec_top; + + default: + return init_cond; + } +} + +/* Returns the initial condition of a given CHREC. */ + +tree +initial_condition (tree chrec) +{ + if (automatically_generated_chrec_p (chrec)) + return chrec; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC + || TREE_CODE (chrec) == EXPONENTIAL_CHREC) + return initial_condition (CHREC_LEFT (chrec)); + else + return chrec; +} + +/* Returns a multivariate function that has no evolution in LOOP_NUM. + Mask the evolution LOOP_NUM. */ + +tree +hide_evolution_in_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 hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num); + + else + return build_polynomial_chrec + (CHREC_VARIABLE (chrec), + hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num), + CHREC_RIGHT (chrec)); + + case EXPONENTIAL_CHREC: + if (CHREC_VARIABLE (chrec) >= loop_num) + return hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num); + + else + return build_exponential_chrec + (CHREC_VARIABLE (chrec), + hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num), + CHREC_RIGHT (chrec)); + + default: + return chrec; + } +} + +/* Returns a univariate function that represents the evolution in + LOOP_NUM. Mask the evolution of any other loop. */ + +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) + /* There is no evolution in this loop. */ + return initial_condition (chrec); + + else + return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), + loop_num); + + case EXPONENTIAL_CHREC: + if (CHREC_VARIABLE (chrec) == loop_num) + return build_exponential_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) + /* There is no evolution in this loop. */ + return initial_condition (chrec); + + else + return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), + loop_num); + + default: + return chrec; + } +} + +/* Returns the evolution part in LOOP_NUM. Example: the call + get_evolution_in_loop (1, {{0, +, 1}_1, +, 2}_1) returns + {1, +, 2}_1 */ + +tree +evolution_part_in_loop_num (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) + { + if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC + || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) + return CHREC_RIGHT (chrec); + + else + return build_polynomial_chrec + (loop_num, + evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num), + CHREC_RIGHT (chrec)); + } + + else if (CHREC_VARIABLE (chrec) < loop_num) + /* There is no evolution part in this loop. */ + return NULL_TREE; + + else + return evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num); + + case EXPONENTIAL_CHREC: + if (CHREC_VARIABLE (chrec) == loop_num) + { + if (TREE_CODE (CHREC_LEFT (chrec)) != EXPONENTIAL_CHREC + || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) + return CHREC_RIGHT (chrec); + + else + return build_exponential_chrec + (loop_num, + evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num), + CHREC_RIGHT (chrec)); + } + + else if (CHREC_VARIABLE (chrec) < loop_num) + /* There is no evolution part in this loop. */ + return NULL_TREE; + + else + return evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num); + + default: + return NULL_TREE; + } +} + +/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. + This function is essentially used for setting the evolution to + chrec_top, for example after having determined that it is + impossible to say how many times a loop will execute. */ + +tree +reset_evolution_in_loop (unsigned loop_num, + tree chrec, + tree new_evol) +{ + if ((TREE_CODE (chrec) == POLYNOMIAL_CHREC + || TREE_CODE (chrec) == EXPONENTIAL_CHREC) + && CHREC_VARIABLE (chrec) > loop_num) + return build + (TREE_CODE (chrec), + build_int_2 (CHREC_VARIABLE (chrec), 0), + 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 + || TREE_CODE (chrec) == EXPONENTIAL_CHREC) + && CHREC_VARIABLE (chrec) == loop_num) + chrec = CHREC_LEFT (chrec); + + return build_polynomial_chrec (loop_num, chrec, new_evol); +} + + +/* Returns the value of the variable after one execution of the loop + LOOP_NB, supposing that CHREC is the evolution function of the + variable. + + Example: + chrec_eval_next_init_cond (4, {{1, +, 3}_2, +, 10}_4) = 11. */ + +tree +chrec_eval_next_init_cond (unsigned loop_nb, + tree chrec) +{ + tree init_cond; + + init_cond = initial_condition (chrec); + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC + || TREE_CODE (chrec) == EXPONENTIAL_CHREC) + { + if (CHREC_VARIABLE (chrec) < loop_nb) + /* There is no evolution in this dimension. */ + return init_cond; + + while ((TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC + || TREE_CODE (CHREC_LEFT (chrec)) == EXPONENTIAL_CHREC) + && CHREC_VARIABLE (CHREC_LEFT (chrec)) >= loop_nb) + chrec = CHREC_LEFT (chrec); + + if (CHREC_VARIABLE (chrec) != loop_nb) + /* There is no evolution in this dimension. */ + return init_cond; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + /* testsuite/.../ssa-chrec-14.c */ + return chrec_fold_plus (chrec_type (init_cond), init_cond, + initial_condition (CHREC_RIGHT (chrec))); + + else + return chrec_fold_multiply (chrec_type (init_cond), init_cond, + initial_condition (CHREC_RIGHT (chrec))); + } + + else + return init_cond; +} + +/* Determine the type of the result after the merge of types TYPE0 and + TYPE1. */ + +static inline tree +chrec_merge_types (tree type0, + tree type1) +{ + if (type0 == type1) + return type0; + + else + /* FIXME. */ + return NULL_TREE; +} + +/* Merge the information contained in intervals or scalar constants. + merge ([a, b], [c, d]) -> [min (a, c), max (b, d)], + merge ([a, b], c) -> [min (a, c), max (b, c)], + merge (a, [b, c]) -> [min (a, b), max (a, c)], + merge (a, b) -> [min (a, b), max (a, b)]. */ + +static inline tree +chrec_merge_intervals (tree chrec1, + tree chrec2) +{ + tree type1 = chrec_type (chrec1); + tree type2 = chrec_type (chrec2); + tree type = chrec_merge_types (type1, type2); + + if (type == NULL_TREE) + return chrec_top; + + if (TREE_CODE (chrec1) == INTERVAL_CHREC) + { + if (TREE_CODE (chrec2) == INTERVAL_CHREC) + return build_interval_chrec + (tree_fold_min (type, CHREC_LOW (chrec1), CHREC_LOW (chrec2)), + tree_fold_max (type, CHREC_UP (chrec1), CHREC_UP (chrec2))); + else + return build_interval_chrec + (tree_fold_min (type, CHREC_LOW (chrec1), chrec2), + tree_fold_max (type, CHREC_UP (chrec1), chrec2)); + } + else if (TREE_CODE (chrec2) == INTERVAL_CHREC) + return build_interval_chrec + (tree_fold_min (type, CHREC_LOW (chrec2), chrec1), + tree_fold_max (type, CHREC_UP (chrec2), chrec1)); + else + return build_interval_chrec + (tree_fold_min (type, chrec1, chrec2), + tree_fold_max (type, chrec1, chrec2)); +} + +/* Merges two evolution functions that were found by following two + alternate paths of a conditional expression. */ + +tree +chrec_merge (tree chrec1, + tree chrec2) +{ + if (chrec1 == chrec_top + || chrec2 == chrec_top) + return chrec_top; + + if (chrec1 == chrec_bot + || chrec2 == chrec_bot) + return chrec_bot; + + 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; + + switch (TREE_CODE (chrec1)) + { + case INTEGER_CST: + case INTERVAL_CHREC: + switch (TREE_CODE (chrec2)) + { + case INTEGER_CST: + case INTERVAL_CHREC: + return chrec_merge_intervals (chrec1, chrec2); + + case POLYNOMIAL_CHREC: + return build_polynomial_chrec + (CHREC_VARIABLE (chrec2), + chrec_merge (chrec1, CHREC_LEFT (chrec2)), + chrec_merge (integer_zero_node, CHREC_RIGHT (chrec2))); + + case EXPONENTIAL_CHREC: + return build_exponential_chrec + (CHREC_VARIABLE (chrec2), + chrec_merge (chrec1, CHREC_LEFT (chrec2)), + chrec_merge (integer_one_node, CHREC_RIGHT (chrec2))); + + default: + return chrec_top; + } + + case POLYNOMIAL_CHREC: + switch (TREE_CODE (chrec2)) + { + case INTEGER_CST: + case INTERVAL_CHREC: + return build_polynomial_chrec + (CHREC_VARIABLE (chrec1), + chrec_merge (CHREC_LEFT (chrec1), chrec2), + chrec_merge (CHREC_RIGHT (chrec1), integer_zero_node)); + + case POLYNOMIAL_CHREC: + if (CHREC_VARIABLE (chrec1) == CHREC_VARIABLE (chrec2)) + return build_polynomial_chrec + (CHREC_VARIABLE (chrec2), + chrec_merge (CHREC_LEFT (chrec1), CHREC_LEFT (chrec2)), + chrec_merge (CHREC_RIGHT (chrec1), CHREC_RIGHT (chrec2))); + else if (CHREC_VARIABLE (chrec1) < CHREC_VARIABLE (chrec2)) + return build_polynomial_chrec + (CHREC_VARIABLE (chrec2), + chrec_merge (chrec1, CHREC_LEFT (chrec2)), + chrec_merge (integer_zero_node, CHREC_RIGHT (chrec2))); + else + return build_polynomial_chrec + (CHREC_VARIABLE (chrec1), + chrec_merge (CHREC_LEFT (chrec1), chrec2), + chrec_merge (CHREC_RIGHT (chrec1), integer_zero_node)); + + case EXPONENTIAL_CHREC: + return chrec_top; + + default: + return chrec_top; + } + + case EXPONENTIAL_CHREC: + return chrec_top; + + default: + return chrec_top; + } +} + + + +/* Observers. */ + +/* Helper function for is_multivariate_chrec. */ + +static bool +is_multivariate_chrec_rec (tree chrec, unsigned int rec_var) +{ + if (chrec == NULL_TREE) + return false; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC + || TREE_CODE (chrec) == EXPONENTIAL_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; +} + +/* Determine whether the given chrec is multivariate or not. */ + +bool +is_multivariate_chrec (tree chrec) +{ + if (chrec == NULL_TREE) + return false; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC + || TREE_CODE (chrec) == EXPONENTIAL_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; +} + +/* Determine whether the given chrec is a polynomial or not. */ + +bool +is_pure_sum_chrec (tree chrec) +{ + if (chrec == NULL_TREE) + return true; + + if (TREE_CODE (chrec) == EXPONENTIAL_CHREC) + return false; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + return (is_pure_sum_chrec (CHREC_LEFT (chrec)) + && is_pure_sum_chrec (CHREC_RIGHT (chrec))); + + return true; +} + +/* Determines whether CHREC is a loop invariant wrt. LOOP_NUM. */ + +bool +no_evolution_in_loop_p (tree chrec, + unsigned loop_num) +{ + tree scev; + + if (chrec == chrec_not_analyzed_yet) + return true; + if (chrec == chrec_top) + return false; + + scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num); + return (TREE_CODE (scev) != POLYNOMIAL_CHREC + && TREE_CODE (scev) != EXPONENTIAL_CHREC); +} + +/* Determines whether the chrec contains symbolic names or not. */ + +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; + } +} + +/* Determines whether the chrec contains undetermined coefficients. */ + +bool +chrec_contains_undetermined (tree chrec) +{ + if (chrec == chrec_top + || 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; + } +} + +/* Determines whether the chrec contains interval coefficients. */ + +bool +chrec_contains_intervals (tree chrec) +{ + if (chrec == NULL_TREE + || automatically_generated_chrec_p (chrec)) + return false; + + if (TREE_CODE (chrec) == INTERVAL_CHREC) + return true; + + switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) + { + case 3: + if (chrec_contains_intervals (TREE_OPERAND (chrec, 2))) + return true; + + case 2: + if (chrec_contains_intervals (TREE_OPERAND (chrec, 1))) + return true; + + case 1: + if (chrec_contains_intervals (TREE_OPERAND (chrec, 0))) + return true; + + default: + return false; + } +} + +/* Determines whether the tree EXPR contains chrecs. */ + +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; + } +} + +/* Determine whether the given tree is an affine multivariate + evolution. */ + +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 (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)) + && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) + && evolution_function_is_affine_multivariate_p + (CHREC_LEFT (chrec))) + return true; + else + return false; + } + + + case EXPONENTIAL_CHREC: + case INTERVAL_CHREC: + default: + return false; + } +} + +/* Determine whether the given tree is a function in zero or one + variables. */ + +bool +evolution_function_is_univariate_p (tree chrec) +{ + if (chrec == NULL_TREE) + return true; + + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + case EXPONENTIAL_CHREC: + switch (TREE_CODE (CHREC_LEFT (chrec))) + { + case POLYNOMIAL_CHREC: + case EXPONENTIAL_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: + case EXPONENTIAL_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; + } +} + + + +/* Convert the initial condition of chrec to type. */ + +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 convert (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))); + + case EXPONENTIAL_CHREC: + return build_exponential_chrec (CHREC_VARIABLE (chrec), + chrec_convert (type, + CHREC_LEFT (chrec)), + chrec_convert (type, + CHREC_RIGHT (chrec))); + + case PEELED_CHREC: + return build_peeled_chrec + (CHREC_VARIABLE (chrec), + chrec_convert (type, CHREC_LEFT (chrec)), + chrec_convert (type, CHREC_RIGHT (chrec))); + + case INTERVAL_CHREC: + return build_interval_chrec + (chrec_convert (type, CHREC_LOW (chrec)), + chrec_convert (type, CHREC_UP (chrec))); + + default: + return convert (type, chrec); + } +} + +/* Returns the type of the chrec. */ + +tree +chrec_type (tree chrec) +{ + if (automatically_generated_chrec_p (chrec)) + return NULL_TREE; + + return TREE_TYPE (chrec); +} + |