Branch data Line data Source code
1 : : /* Chains of recurrences.
2 : : Copyright (C) 2003-2024 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 : 1347255404 : automatically_generated_chrec_p (const_tree chrec)
40 : : {
41 : 1347255404 : return (chrec == chrec_dont_know
42 : 1262781297 : || chrec == chrec_known);
43 : : }
44 : :
45 : : /* The tree nodes aka. CHRECs. */
46 : :
47 : : inline bool
48 : 438797012 : tree_is_chrec (const_tree expr)
49 : : {
50 : 438797012 : if (TREE_CODE (expr) == POLYNOMIAL_CHREC
51 : 868589149 : || 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 : 35269557 : chrec_zerop (const_tree chrec)
101 : : {
102 : 35269557 : if (chrec == NULL_TREE)
103 : : return false;
104 : :
105 : 35269557 : if (TREE_CODE (chrec) == INTEGER_CST)
106 : 29946683 : 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 : 45180887 : no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
116 : : {
117 : 45180887 : tree scev;
118 : :
119 : 45180887 : if (chrec == chrec_not_analyzed_yet
120 : 45180887 : || chrec == chrec_dont_know
121 : 87502905 : || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
122 : 6297657 : return false;
123 : :
124 : 38883230 : STRIP_NOPS (chrec);
125 : 38883230 : scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
126 : 38883230 : *res = !tree_contains_chrecs (scev, NULL);
127 : 38883230 : return true;
128 : : }
129 : :
130 : : /* Build a polynomial chain of recurrence. */
131 : :
132 : : inline tree
133 : 35189683 : build_polynomial_chrec (unsigned loop_num,
134 : : tree left,
135 : : tree right)
136 : : {
137 : 35189683 : bool val;
138 : :
139 : 35189683 : if (left == chrec_dont_know
140 : 35189626 : || right == chrec_dont_know)
141 : : return chrec_dont_know;
142 : :
143 : 35189028 : if (!no_evolution_in_loop_p (left, loop_num, &val)
144 : 35189028 : || !val)
145 : 1393 : 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 : 35187635 : if (POINTER_TYPE_P (TREE_TYPE (left)))
150 : 7037055 : 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 : 28150580 : gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right))
156 : : && types_compatible_p (TREE_TYPE (left),
157 : : TREE_TYPE (right)));
158 : : }
159 : :
160 : 35187635 : if (chrec_zerop (right))
161 : : return left;
162 : :
163 : 35187505 : tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right);
164 : 35187505 : CHREC_VARIABLE (chrec) = loop_num;
165 : 35187505 : return chrec;
166 : : }
167 : :
168 : : /* Determines whether the expression CHREC is a constant. */
169 : :
170 : : inline bool
171 : 62967988 : evolution_function_is_constant_p (const_tree chrec)
172 : : {
173 : 62967988 : if (chrec == NULL_TREE)
174 : : return false;
175 : :
176 : 62967988 : return is_gimple_min_invariant (chrec);
177 : : }
178 : :
179 : : /* Determine whether CHREC is an affine evolution function in LOOPNUM. */
180 : :
181 : : inline bool
182 : 3042493 : evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
183 : : {
184 : 3042493 : if (chrec == NULL_TREE)
185 : : return false;
186 : :
187 : 3042493 : switch (TREE_CODE (chrec))
188 : : {
189 : 3037821 : case POLYNOMIAL_CHREC:
190 : 3037821 : if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum)
191 : 6072085 : && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum))
192 : : return true;
193 : : else
194 : 3557 : 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 : 43646153 : evolution_function_is_affine_p (const_tree chrec)
205 : : {
206 : 43646153 : return chrec
207 : 43646153 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
208 : 10157625 : && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
209 : 10157625 : CHREC_VARIABLE (chrec))
210 : 53746445 : && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
211 : 50 : || evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
212 : : }
213 : :
214 : : /* Determines whether EXPR does not contains chrec expressions. */
215 : :
216 : : inline bool
217 : 30836342 : tree_does_not_contain_chrecs (const_tree expr)
218 : : {
219 : 30836342 : return !tree_contains_chrecs (expr, NULL);
220 : : }
221 : :
222 : : /* Returns the type of the chrec. */
223 : :
224 : : inline tree
225 : 186619432 : chrec_type (const_tree chrec)
226 : : {
227 : 186619432 : if (automatically_generated_chrec_p (chrec))
228 : : return NULL_TREE;
229 : :
230 : 186619432 : 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 */
|
