1169689Skan/* Chains of recurrences. 2169689Skan Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan#ifndef GCC_TREE_CHREC_H 23169689Skan#define GCC_TREE_CHREC_H 24169689Skan 25169689Skan/* Accessors for the chains of recurrences. */ 26169689Skan#define CHREC_VAR(NODE) TREE_OPERAND (NODE, 0) 27169689Skan#define CHREC_LEFT(NODE) TREE_OPERAND (NODE, 1) 28169689Skan#define CHREC_RIGHT(NODE) TREE_OPERAND (NODE, 2) 29169689Skan#define CHREC_VARIABLE(NODE) TREE_INT_CST_LOW (CHREC_VAR (NODE)) 30169689Skan 31169689Skan 32169689Skan 33169689Skan/* The following trees are unique elements. Thus the comparison of another 34169689Skan element to these elements should be done on the pointer to these trees, 35169689Skan and not on their value. */ 36169689Skan 37169689Skanextern tree chrec_not_analyzed_yet; 38169689Skanextern GTY(()) tree chrec_dont_know; 39169689Skanextern GTY(()) tree chrec_known; 40169689Skan 41169689Skan/* After having added an automatically generated element, please 42169689Skan include it in the following function. */ 43169689Skan 44169689Skanstatic inline bool 45169689Skanautomatically_generated_chrec_p (tree chrec) 46169689Skan{ 47169689Skan return (chrec == chrec_not_analyzed_yet 48169689Skan || chrec == chrec_dont_know 49169689Skan || chrec == chrec_known); 50169689Skan} 51169689Skan 52169689Skan/* The tree nodes aka. CHRECs. */ 53169689Skan 54169689Skanstatic inline bool 55169689Skantree_is_chrec (tree expr) 56169689Skan{ 57169689Skan if (TREE_CODE (expr) == POLYNOMIAL_CHREC 58169689Skan || automatically_generated_chrec_p (expr)) 59169689Skan return true; 60169689Skan else 61169689Skan return false; 62169689Skan} 63169689Skan 64169689Skan 65169689Skan 66169689Skan/* Chrec folding functions. */ 67169689Skanextern tree chrec_fold_plus (tree, tree, tree); 68169689Skanextern tree chrec_fold_minus (tree, tree, tree); 69169689Skanextern tree chrec_fold_multiply (tree, tree, tree); 70169689Skanextern tree chrec_convert (tree, tree, tree); 71169689Skanextern tree chrec_convert_aggressive (tree, tree); 72169689Skan 73169689Skan/* Operations. */ 74169689Skanextern tree chrec_apply (unsigned, tree, tree); 75169689Skanextern tree chrec_replace_initial_condition (tree, tree); 76169689Skanextern tree initial_condition (tree); 77169689Skanextern tree initial_condition_in_loop_num (tree, unsigned); 78169689Skanextern tree evolution_part_in_loop_num (tree, unsigned); 79169689Skanextern tree hide_evolution_in_other_loops_than_loop (tree, unsigned); 80169689Skanextern tree reset_evolution_in_loop (unsigned, tree, tree); 81169689Skanextern tree chrec_merge (tree, tree); 82169689Skan 83169689Skan/* Observers. */ 84169689Skanextern bool eq_evolutions_p (tree, tree); 85169689Skanextern bool is_multivariate_chrec (tree); 86169689Skanextern bool chrec_is_positive (tree, bool *); 87169689Skanextern bool chrec_contains_symbols (tree); 88169689Skanextern bool chrec_contains_symbols_defined_in_loop (tree, unsigned); 89169689Skanextern bool chrec_contains_undetermined (tree); 90169689Skanextern bool tree_contains_chrecs (tree, int *); 91169689Skanextern bool evolution_function_is_affine_multivariate_p (tree); 92169689Skanextern bool evolution_function_is_univariate_p (tree); 93169689Skanextern unsigned nb_vars_in_chrec (tree); 94169689Skan 95169689Skan 96169689Skan 97169689Skan/* Build a polynomial chain of recurrence. */ 98169689Skan 99169689Skanstatic inline tree 100169689Skanbuild_polynomial_chrec (unsigned loop_num, 101169689Skan tree left, 102169689Skan tree right) 103169689Skan{ 104169689Skan if (left == chrec_dont_know 105169689Skan || right == chrec_dont_know) 106169689Skan return chrec_dont_know; 107169689Skan 108169689Skan gcc_assert (TREE_TYPE (left) == TREE_TYPE (right)); 109169689Skan 110169689Skan return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), 111169689Skan build_int_cst (NULL_TREE, loop_num), left, right); 112169689Skan} 113169689Skan 114169689Skan 115169689Skan 116169689Skan/* Observers. */ 117169689Skan 118169689Skan/* Determines whether CHREC is equal to zero. */ 119169689Skan 120169689Skanstatic inline bool 121169689Skanchrec_zerop (tree chrec) 122169689Skan{ 123169689Skan if (chrec == NULL_TREE) 124169689Skan return false; 125169689Skan 126169689Skan if (TREE_CODE (chrec) == INTEGER_CST) 127169689Skan return integer_zerop (chrec); 128169689Skan 129169689Skan return false; 130169689Skan} 131169689Skan 132169689Skan/* Determines whether the expression CHREC is a constant. */ 133169689Skan 134169689Skanstatic inline bool 135169689Skanevolution_function_is_constant_p (tree chrec) 136169689Skan{ 137169689Skan if (chrec == NULL_TREE) 138169689Skan return false; 139169689Skan 140169689Skan switch (TREE_CODE (chrec)) 141169689Skan { 142169689Skan case INTEGER_CST: 143169689Skan case REAL_CST: 144169689Skan return true; 145169689Skan 146169689Skan default: 147169689Skan return false; 148169689Skan } 149169689Skan} 150169689Skan 151169689Skanextern bool evolution_function_is_invariant_p (tree, int); 152169689Skan/* Determine whether the given tree is an affine evolution function or not. */ 153169689Skan 154169689Skanstatic inline bool 155169689Skanevolution_function_is_affine_p (tree chrec) 156169689Skan{ 157169689Skan if (chrec == NULL_TREE) 158169689Skan return false; 159169689Skan 160169689Skan switch (TREE_CODE (chrec)) 161169689Skan { 162169689Skan case POLYNOMIAL_CHREC: 163169689Skan if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), 164169689Skan CHREC_VARIABLE (chrec)) 165169689Skan && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), 166169689Skan CHREC_VARIABLE (chrec))) 167169689Skan return true; 168169689Skan else 169169689Skan return false; 170169689Skan 171169689Skan default: 172169689Skan return false; 173169689Skan } 174169689Skan} 175169689Skan 176169689Skan/* Determine whether the given tree is an affine or constant evolution 177169689Skan function. */ 178169689Skan 179169689Skanstatic inline bool 180169689Skanevolution_function_is_affine_or_constant_p (tree chrec) 181169689Skan{ 182169689Skan return evolution_function_is_affine_p (chrec) 183169689Skan || evolution_function_is_constant_p (chrec); 184169689Skan} 185169689Skan 186169689Skan/* Determines whether EXPR does not contains chrec expressions. */ 187169689Skan 188169689Skanstatic inline bool 189169689Skantree_does_not_contain_chrecs (tree expr) 190169689Skan{ 191169689Skan return !tree_contains_chrecs (expr, NULL); 192169689Skan} 193169689Skan 194169689Skan/* Determines whether CHREC is a loop invariant with respect to LOOP_NUM. 195169689Skan Set the result in RES and return true when the property can be computed. */ 196169689Skan 197169689Skanstatic inline bool 198169689Skanno_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res) 199169689Skan{ 200169689Skan tree scev; 201169689Skan 202169689Skan if (chrec == chrec_not_analyzed_yet 203169689Skan || chrec == chrec_dont_know 204169689Skan || chrec_contains_symbols_defined_in_loop (chrec, loop_num)) 205169689Skan return false; 206169689Skan 207169689Skan scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num); 208169689Skan *res = !tree_is_chrec (scev); 209169689Skan return true; 210169689Skan} 211169689Skan 212169689Skan/* Returns the type of the chrec. */ 213169689Skan 214169689Skanstatic inline tree 215169689Skanchrec_type (tree chrec) 216169689Skan{ 217169689Skan if (automatically_generated_chrec_p (chrec)) 218169689Skan return NULL_TREE; 219169689Skan 220169689Skan return TREE_TYPE (chrec); 221169689Skan} 222169689Skan 223169689Skan 224169689Skan#endif /* GCC_TREE_CHREC_H */ 225