Line data Source code
1 : /* Chains of recurrences.
2 : Copyright (C) 2003-2026 Free Software Foundation, Inc.
3 : Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #ifndef GCC_TREE_CHREC_H
22 : #define GCC_TREE_CHREC_H
23 :
24 : /* The following trees are unique elements. Thus the comparison of another
25 : element to these elements should be done on the pointer to these trees,
26 : and not on their value.
27 :
28 : extern tree chrec_not_analyzed_yet;
29 : extern tree chrec_dont_know;
30 : extern tree chrec_known;
31 :
32 : chrec_not_analyzed_yet is NULL_TREE and the others are defined
33 : in global_trees[]. */
34 :
35 : /* After having added an automatically generated element, please
36 : include it in the following function. */
37 :
38 : inline bool
39 1573031772 : automatically_generated_chrec_p (const_tree chrec)
40 : {
41 1573031772 : return (chrec == chrec_dont_know
42 1473562940 : || chrec == chrec_known);
43 : }
44 :
45 : /* The tree nodes aka. CHRECs. */
46 :
47 : inline bool
48 504955909 : tree_is_chrec (const_tree expr)
49 : {
50 504955909 : if (TREE_CODE (expr) == POLYNOMIAL_CHREC
51 998116001 : || automatically_generated_chrec_p (expr))
52 0 : return true;
53 : else
54 : return false;
55 : }
56 :
57 :
58 : enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
59 : enum ev_direction scev_direction (const_tree);
60 :
61 : /* Chrec folding functions. */
62 : extern tree chrec_fold_plus (tree, tree, tree);
63 : extern tree chrec_fold_minus (tree, tree, tree);
64 : extern tree chrec_fold_multiply (tree, tree, tree);
65 : extern tree chrec_convert (tree, tree, gimple *, tree * = nullptr,
66 : bool = true, tree = NULL);
67 : extern tree chrec_convert_rhs (tree, tree, gimple * = NULL, tree * = nullptr);
68 : extern tree chrec_convert_aggressive (tree, tree, bool *);
69 :
70 : /* Operations. */
71 : extern tree chrec_apply (unsigned, tree, tree);
72 : extern tree chrec_apply_map (tree, vec<tree> );
73 : extern tree chrec_replace_initial_condition (tree, tree);
74 : extern tree initial_condition (tree);
75 : extern tree initial_condition_in_loop_num (tree, unsigned);
76 : extern tree evolution_part_in_loop_num (tree, unsigned);
77 : extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
78 : extern tree reset_evolution_in_loop (unsigned, tree, tree);
79 : extern tree chrec_merge (tree, tree);
80 : extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
81 : extern bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *,
82 : bool, tree = NULL, tree * = nullptr);
83 :
84 : /* Observers. */
85 : extern bool eq_evolutions_p (const_tree, const_tree);
86 : extern bool is_multivariate_chrec (const_tree);
87 : extern bool chrec_contains_symbols (const_tree, class loop * = NULL);
88 : extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
89 : extern bool chrec_contains_undetermined (const_tree);
90 : extern bool tree_contains_chrecs (const_tree, int *);
91 : extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
92 : extern bool evolution_function_is_univariate_p (const_tree, int = 0);
93 : extern unsigned nb_vars_in_chrec (tree);
94 : extern bool evolution_function_is_invariant_p (tree, int);
95 : extern bool scev_is_linear_expression (tree);
96 : extern bool evolution_function_right_is_integer_cst (const_tree);
97 :
98 : /* Determines whether CHREC is equal to zero. */
99 :
100 : inline bool
101 44225266 : chrec_zerop (const_tree chrec)
102 : {
103 44225266 : if (chrec == NULL_TREE)
104 : return false;
105 :
106 44225266 : if (TREE_CODE (chrec) == INTEGER_CST)
107 37962413 : return integer_zerop (chrec);
108 :
109 : return false;
110 : }
111 :
112 : /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
113 : Set the result in RES and return true when the property can be computed. */
114 :
115 : inline bool
116 55641815 : no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
117 : {
118 55641815 : tree scev;
119 :
120 55641815 : if (chrec == chrec_not_analyzed_yet
121 55641815 : || chrec == chrec_dont_know
122 107912178 : || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
123 : return false;
124 :
125 48335241 : STRIP_NOPS (chrec);
126 48335241 : scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
127 48335241 : *res = !tree_contains_chrecs (scev, NULL);
128 48335241 : return true;
129 : }
130 :
131 : /* Build a polynomial chain of recurrence. */
132 :
133 : inline tree
134 44140819 : build_polynomial_chrec (unsigned loop_num,
135 : tree left,
136 : tree right)
137 : {
138 44140819 : bool val;
139 :
140 44140819 : if (left == chrec_dont_know
141 44140367 : || right == chrec_dont_know)
142 : return chrec_dont_know;
143 :
144 44139764 : if (!no_evolution_in_loop_p (left, loop_num, &val)
145 44139764 : || !val)
146 1774 : return chrec_dont_know;
147 :
148 : /* Types of left and right sides of a chrec should be compatible, but
149 : pointer CHRECs are special in that the evolution is of ptroff type. */
150 44137990 : if (POINTER_TYPE_P (TREE_TYPE (left)))
151 8952885 : gcc_checking_assert (ptrofftype_p (TREE_TYPE (right)));
152 : else
153 : {
154 : /* Pointer types should occur only on the left hand side, i.e. in
155 : the base of the chrec, and not in the step. */
156 35185105 : gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right))
157 : && types_compatible_p (TREE_TYPE (left),
158 : TREE_TYPE (right)));
159 : }
160 :
161 44137990 : if (chrec_zerop (right))
162 : return left;
163 :
164 44137778 : tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right);
165 44137778 : CHREC_VARIABLE (chrec) = loop_num;
166 44137778 : return chrec;
167 : }
168 :
169 : /* Determines whether the expression CHREC is a constant. */
170 :
171 : inline bool
172 56628653 : evolution_function_is_constant_p (const_tree chrec)
173 : {
174 56628653 : if (chrec == NULL_TREE)
175 : return false;
176 :
177 56628653 : return is_gimple_min_invariant (chrec);
178 : }
179 :
180 : /* Determine whether CHREC is an affine evolution function in LOOPNUM. */
181 :
182 : inline bool
183 5139190 : evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
184 : {
185 5139190 : if (chrec == NULL_TREE)
186 : return false;
187 :
188 5139190 : switch (TREE_CODE (chrec))
189 : {
190 5136073 : case POLYNOMIAL_CHREC:
191 5136073 : if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum)
192 10268576 : && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum))
193 : return true;
194 : else
195 3570 : return false;
196 :
197 : default:
198 : return false;
199 : }
200 : }
201 :
202 : /* Determine whether CHREC is an affine evolution function or not. */
203 :
204 : inline bool
205 48683607 : evolution_function_is_affine_p (const_tree chrec)
206 : {
207 48683607 : return chrec
208 48683607 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
209 11235422 : && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
210 11235422 : CHREC_VARIABLE (chrec))
211 59869497 : && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
212 63 : || evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
213 : }
214 :
215 : /* Determines whether EXPR does not contains chrec expressions. */
216 :
217 : inline bool
218 38324347 : tree_does_not_contain_chrecs (const_tree expr)
219 : {
220 38324347 : return !tree_contains_chrecs (expr, NULL);
221 : }
222 :
223 : /* Returns the type of the chrec. */
224 :
225 : inline tree
226 211518121 : chrec_type (const_tree chrec)
227 : {
228 211518121 : if (automatically_generated_chrec_p (chrec))
229 : return NULL_TREE;
230 :
231 211518121 : return TREE_TYPE (chrec);
232 : }
233 :
234 : inline tree
235 0 : chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1)
236 : {
237 0 : switch (code)
238 : {
239 0 : case PLUS_EXPR:
240 0 : return chrec_fold_plus (type, op0, op1);
241 :
242 0 : case MINUS_EXPR:
243 0 : return chrec_fold_minus (type, op0, op1);
244 :
245 0 : case MULT_EXPR:
246 0 : return chrec_fold_multiply (type, op0, op1);
247 :
248 0 : default:
249 0 : gcc_unreachable ();
250 : }
251 :
252 : }
253 :
254 : #endif /* GCC_TREE_CHREC_H */
|