/* Chains of recurrences.
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
- Contributed by Sebastian Pop <s.pop@laposte.net>
+ Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
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. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#ifndef GCC_TREE_CHREC_H
#define GCC_TREE_CHREC_H
-/* Accessors for the chains of recurrences. */
-#define CHREC_VAR(NODE) TREE_OPERAND (NODE, 0)
-#define CHREC_LEFT(NODE) TREE_OPERAND (NODE, 1)
-#define CHREC_RIGHT(NODE) TREE_OPERAND (NODE, 2)
-#define CHREC_VARIABLE(NODE) TREE_INT_CST_LOW (CHREC_VAR (NODE))
-
-\f
-
/* The following trees are unique elements. Thus the comparison of another
element to these elements should be done on the pointer to these trees,
and not on their value. */
static inline bool
automatically_generated_chrec_p (tree chrec)
{
- return (chrec == chrec_not_analyzed_yet
- || chrec == chrec_dont_know
+ return (chrec == chrec_dont_know
|| chrec == chrec_known);
}
extern tree chrec_fold_plus (tree, tree, tree);
extern tree chrec_fold_minus (tree, tree, tree);
extern tree chrec_fold_multiply (tree, tree, tree);
-extern tree chrec_convert (tree, tree);
-extern tree count_ev_in_wider_type (tree, tree);
-extern tree chrec_type (tree);
+extern tree chrec_convert (tree, tree, tree);
+extern tree chrec_convert_rhs (tree, tree, tree);
+extern tree chrec_convert_aggressive (tree, tree);
/* Operations. */
extern tree chrec_apply (unsigned, tree, tree);
extern tree chrec_merge (tree, tree);
/* Observers. */
+extern bool eq_evolutions_p (tree, tree);
extern bool is_multivariate_chrec (tree);
extern bool chrec_is_positive (tree, bool *);
extern bool chrec_contains_symbols (tree);
extern bool chrec_contains_symbols_defined_in_loop (tree, unsigned);
extern bool chrec_contains_undetermined (tree);
-extern bool tree_contains_chrecs (tree);
-extern bool evolution_function_is_affine_multivariate_p (tree);
+extern bool tree_contains_chrecs (tree, int *);
+extern bool evolution_function_is_affine_multivariate_p (tree, int);
extern bool evolution_function_is_univariate_p (tree);
extern unsigned nb_vars_in_chrec (tree);
+extern bool evolution_function_is_invariant_p (tree, int);
-\f
+/* Determines whether CHREC is equal to zero. */
+
+static inline bool
+chrec_zerop (tree chrec)
+{
+ if (chrec == NULL_TREE)
+ return false;
+
+ if (TREE_CODE (chrec) == INTEGER_CST)
+ return integer_zerop (chrec);
+
+ return false;
+}
+
+/* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
+ Set the result in RES and return true when the property can be computed. */
+
+static inline bool
+no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
+{
+ tree scev;
+
+ if (chrec == chrec_not_analyzed_yet
+ || chrec == chrec_dont_know
+ || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
+ return false;
+
+ scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
+ *res = !tree_is_chrec (scev);
+ return true;
+}
/* Build a polynomial chain of recurrence. */
tree left,
tree right)
{
+ bool val;
+
if (left == chrec_dont_know
|| right == chrec_dont_know)
return chrec_dont_know;
- return build (POLYNOMIAL_CHREC, TREE_TYPE (left),
- build_int_cst (NULL_TREE, loop_num), left, right);
-}
-
-\f
+ if (no_evolution_in_loop_p (left, loop_num, &val) && !val)
+ return chrec_dont_know;
-/* Observers. */
+ if (POINTER_TYPE_P (TREE_TYPE (left)))
+ gcc_assert (sizetype == TREE_TYPE (right));
+ else
+ gcc_assert (TREE_TYPE (left) == TREE_TYPE (right));
-/* Determines whether CHREC is equal to zero. */
+ if (chrec_zerop (right))
+ return left;
-static inline bool
-chrec_zerop (tree chrec)
-{
- if (chrec == NULL_TREE)
- return false;
-
- if (TREE_CODE (chrec) == INTEGER_CST)
- return integer_zerop (chrec);
-
- return false;
+ return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
+ build_int_cst (NULL_TREE, loop_num), left, right);
}
/* Determines whether the expression CHREC is a constant. */
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (evolution_function_is_constant_p (CHREC_LEFT (chrec))
- && evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
+ if (evolution_function_is_invariant_p (CHREC_LEFT (chrec),
+ CHREC_VARIABLE (chrec))
+ && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
+ CHREC_VARIABLE (chrec)))
return true;
else
return false;
static inline bool
tree_does_not_contain_chrecs (tree expr)
{
- return !tree_contains_chrecs (expr);
+ return !tree_contains_chrecs (expr, NULL);
}
-/* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
- Set the result in RES and return true when the property can be computed. */
+/* Returns the type of the chrec. */
-static inline bool
-no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
+static inline tree
+chrec_type (tree chrec)
{
- tree scev;
-
- if (chrec == chrec_not_analyzed_yet
- || chrec == chrec_dont_know
- || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
- return false;
+ if (automatically_generated_chrec_p (chrec))
+ return NULL_TREE;
- scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
- *res = !tree_is_chrec (scev);
- return true;
+ return TREE_TYPE (chrec);
}
+
#endif /* GCC_TREE_CHREC_H */