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 1512006734 : automatically_generated_chrec_p (const_tree chrec)
40 : {
41 1512006734 : return (chrec == chrec_dont_know
42 1417038551 : || chrec == chrec_known);
43 : }
44 :
45 : /* The tree nodes aka. CHRECs. */
46 :
47 : inline bool
48 482111880 : tree_is_chrec (const_tree expr)
49 : {
50 482111880 : if (TREE_CODE (expr) == POLYNOMIAL_CHREC
51 953625882 : || 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 *, bool = true, tree = NULL);
66 : extern tree chrec_convert_rhs (tree, tree, gimple * = NULL);
67 : extern tree chrec_convert_aggressive (tree, tree, bool *);
68 :
69 : /* Operations. */
70 : extern tree chrec_apply (unsigned, tree, tree);
71 : extern tree chrec_apply_map (tree, vec<tree> );
72 : extern tree chrec_replace_initial_condition (tree, tree);
73 : extern tree initial_condition (tree);
74 : extern tree initial_condition_in_loop_num (tree, unsigned);
75 : extern tree evolution_part_in_loop_num (tree, unsigned);
76 : extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
77 : extern tree reset_evolution_in_loop (unsigned, tree, tree);
78 : extern tree chrec_merge (tree, tree);
79 : extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
80 : extern bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *,
81 : bool, tree = NULL);
82 :
83 : /* Observers. */
84 : extern bool eq_evolutions_p (const_tree, const_tree);
85 : extern bool is_multivariate_chrec (const_tree);
86 : extern bool chrec_contains_symbols (const_tree, class loop * = NULL);
87 : extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
88 : extern bool chrec_contains_undetermined (const_tree);
89 : extern bool tree_contains_chrecs (const_tree, int *);
90 : extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
91 : extern bool evolution_function_is_univariate_p (const_tree, int = 0);
92 : extern unsigned nb_vars_in_chrec (tree);
93 : extern bool evolution_function_is_invariant_p (tree, int);
94 : extern bool scev_is_linear_expression (tree);
95 : extern bool evolution_function_right_is_integer_cst (const_tree);
96 :
97 : /* Determines whether CHREC is equal to zero. */
98 :
99 : inline bool
100 42005737 : chrec_zerop (const_tree chrec)
101 : {
102 42005737 : if (chrec == NULL_TREE)
103 : return false;
104 :
105 42005737 : if (TREE_CODE (chrec) == INTEGER_CST)
106 36174840 : return integer_zerop (chrec);
107 :
108 : return false;
109 : }
110 :
111 : /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
112 : Set the result in RES and return true when the property can be computed. */
113 :
114 : inline bool
115 52736618 : no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
116 : {
117 52736618 : tree scev;
118 :
119 52736618 : if (chrec == chrec_not_analyzed_yet
120 52736618 : || chrec == chrec_dont_know
121 102259910 : || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
122 6844914 : return false;
123 :
124 45891704 : STRIP_NOPS (chrec);
125 45891704 : scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
126 45891704 : *res = !tree_contains_chrecs (scev, NULL);
127 45891704 : return true;
128 : }
129 :
130 : /* Build a polynomial chain of recurrence. */
131 :
132 : inline tree
133 41920439 : build_polynomial_chrec (unsigned loop_num,
134 : tree left,
135 : tree right)
136 : {
137 41920439 : bool val;
138 :
139 41920439 : if (left == chrec_dont_know
140 41920368 : || right == chrec_dont_know)
141 : return chrec_dont_know;
142 :
143 41919779 : if (!no_evolution_in_loop_p (left, loop_num, &val)
144 41919779 : || !val)
145 1537 : return chrec_dont_know;
146 :
147 : /* Types of left and right sides of a chrec should be compatible, but
148 : pointer CHRECs are special in that the evolution is of ptroff type. */
149 41918242 : if (POINTER_TYPE_P (TREE_TYPE (left)))
150 8619297 : gcc_checking_assert (ptrofftype_p (TREE_TYPE (right)));
151 : else
152 : {
153 : /* Pointer types should occur only on the left hand side, i.e. in
154 : the base of the chrec, and not in the step. */
155 33298945 : gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right))
156 : && types_compatible_p (TREE_TYPE (left),
157 : TREE_TYPE (right)));
158 : }
159 :
160 41918242 : if (chrec_zerop (right))
161 : return left;
162 :
163 41918099 : tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right);
164 41918099 : CHREC_VARIABLE (chrec) = loop_num;
165 41918099 : return chrec;
166 : }
167 :
168 : /* Determines whether the expression CHREC is a constant. */
169 :
170 : inline bool
171 55697720 : evolution_function_is_constant_p (const_tree chrec)
172 : {
173 55697720 : if (chrec == NULL_TREE)
174 : return false;
175 :
176 55697720 : return is_gimple_min_invariant (chrec);
177 : }
178 :
179 : /* Determine whether CHREC is an affine evolution function in LOOPNUM. */
180 :
181 : inline bool
182 5134612 : evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
183 : {
184 5134612 : if (chrec == NULL_TREE)
185 : return false;
186 :
187 5134612 : switch (TREE_CODE (chrec))
188 : {
189 5131496 : case POLYNOMIAL_CHREC:
190 5131496 : if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum)
191 10259430 : && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum))
192 : return true;
193 : else
194 3562 : return false;
195 :
196 : default:
197 : return false;
198 : }
199 : }
200 :
201 : /* Determine whether CHREC is an affine evolution function or not. */
202 :
203 : inline bool
204 45646821 : evolution_function_is_affine_p (const_tree chrec)
205 : {
206 45646821 : return chrec
207 45646821 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
208 10954082 : && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
209 10954082 : CHREC_VARIABLE (chrec))
210 56555783 : && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
211 60 : || evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
212 : }
213 :
214 : /* Determines whether EXPR does not contains chrec expressions. */
215 :
216 : inline bool
217 36593104 : tree_does_not_contain_chrecs (const_tree expr)
218 : {
219 36593104 : return !tree_contains_chrecs (expr, NULL);
220 : }
221 :
222 : /* Returns the type of the chrec. */
223 :
224 : inline tree
225 210118261 : chrec_type (const_tree chrec)
226 : {
227 210118261 : if (automatically_generated_chrec_p (chrec))
228 : return NULL_TREE;
229 :
230 210118261 : return TREE_TYPE (chrec);
231 : }
232 :
233 : inline tree
234 0 : chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1)
235 : {
236 0 : switch (code)
237 : {
238 0 : case PLUS_EXPR:
239 0 : return chrec_fold_plus (type, op0, op1);
240 :
241 0 : case MINUS_EXPR:
242 0 : return chrec_fold_minus (type, op0, op1);
243 :
244 0 : case MULT_EXPR:
245 0 : return chrec_fold_multiply (type, op0, op1);
246 :
247 0 : default:
248 0 : gcc_unreachable ();
249 : }
250 :
251 : }
252 :
253 : #endif /* GCC_TREE_CHREC_H */
|
