]>
Commit | Line | Data |
---|---|---|
c8a2ab6d | 1 | /* Chains of recurrences. |
8d9254fc | 2 | Copyright (C) 2003-2020 Free Software Foundation, Inc. |
0ff4040e | 3 | Contributed by Sebastian Pop <pop@cri.ensmp.fr> |
c8a2ab6d SP |
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
c8a2ab6d SP |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
c8a2ab6d SP |
20 | |
21 | /* This file implements operations on chains of recurrences. Chains | |
22 | of recurrences are used for modeling evolution functions of scalar | |
23 | variables. | |
24 | */ | |
25 | ||
26 | #include "config.h" | |
27 | #include "system.h" | |
28 | #include "coretypes.h" | |
c7131fb2 | 29 | #include "backend.h" |
957060b5 | 30 | #include "tree.h" |
2fb9a547 | 31 | #include "gimple-expr.h" |
957060b5 | 32 | #include "tree-pretty-print.h" |
957060b5 AM |
33 | #include "fold-const.h" |
34 | #include "cfgloop.h" | |
e28030cf AM |
35 | #include "tree-ssa-loop-ivopts.h" |
36 | #include "tree-ssa-loop-niter.h" | |
c8a2ab6d | 37 | #include "tree-chrec.h" |
5fd8a9cb RB |
38 | #include "gimple.h" |
39 | #include "tree-ssa-loop.h" | |
7ee2468b | 40 | #include "dumpfile.h" |
18aed06a | 41 | #include "tree-scalar-evolution.h" |
c8a2ab6d | 42 | |
c8a2ab6d SP |
43 | /* Extended folder for chrecs. */ |
44 | ||
c8a2ab6d SP |
45 | /* Fold the addition of two polynomial functions. */ |
46 | ||
b8698a0f L |
47 | static inline tree |
48 | chrec_fold_plus_poly_poly (enum tree_code code, | |
49 | tree type, | |
50 | tree poly0, | |
c8a2ab6d SP |
51 | tree poly1) |
52 | { | |
53 | tree left, right; | |
99b1c316 MS |
54 | class loop *loop0 = get_chrec_loop (poly0); |
55 | class loop *loop1 = get_chrec_loop (poly1); | |
370f4759 | 56 | tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type; |
1e128c5f GB |
57 | |
58 | gcc_assert (poly0); | |
59 | gcc_assert (poly1); | |
60 | gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); | |
61 | gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); | |
5be014d5 | 62 | if (POINTER_TYPE_P (chrec_type (poly0))) |
3da3ff4e RB |
63 | gcc_checking_assert (ptrofftype_p (chrec_type (poly1)) |
64 | && useless_type_conversion_p (type, chrec_type (poly0))); | |
5be014d5 | 65 | else |
3da3ff4e RB |
66 | gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0)) |
67 | && useless_type_conversion_p (type, chrec_type (poly1))); | |
b8698a0f | 68 | |
c8a2ab6d SP |
69 | /* |
70 | {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, | |
71 | {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, | |
72 | {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ | |
677cc14d | 73 | if (flow_loop_nested_p (loop0, loop1)) |
c8a2ab6d | 74 | { |
5be014d5 | 75 | if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) |
b8698a0f L |
76 | return build_polynomial_chrec |
77 | (CHREC_VARIABLE (poly1), | |
c8a2ab6d SP |
78 | chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)), |
79 | CHREC_RIGHT (poly1)); | |
80 | else | |
b8698a0f L |
81 | return build_polynomial_chrec |
82 | (CHREC_VARIABLE (poly1), | |
c8a2ab6d | 83 | chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)), |
b8698a0f | 84 | chrec_fold_multiply (type, CHREC_RIGHT (poly1), |
7e0923cd SP |
85 | SCALAR_FLOAT_TYPE_P (type) |
86 | ? build_real (type, dconstm1) | |
87 | : build_int_cst_type (type, -1))); | |
c8a2ab6d | 88 | } |
b8698a0f | 89 | |
677cc14d | 90 | if (flow_loop_nested_p (loop1, loop0)) |
c8a2ab6d | 91 | { |
5be014d5 | 92 | if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) |
b8698a0f L |
93 | return build_polynomial_chrec |
94 | (CHREC_VARIABLE (poly0), | |
c8a2ab6d SP |
95 | chrec_fold_plus (type, CHREC_LEFT (poly0), poly1), |
96 | CHREC_RIGHT (poly0)); | |
97 | else | |
b8698a0f L |
98 | return build_polynomial_chrec |
99 | (CHREC_VARIABLE (poly0), | |
c8a2ab6d SP |
100 | chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), |
101 | CHREC_RIGHT (poly0)); | |
102 | } | |
b8698a0f | 103 | |
677cc14d ZD |
104 | /* This function should never be called for chrecs of loops that |
105 | do not belong to the same loop nest. */ | |
1b7c8d39 RB |
106 | if (loop0 != loop1) |
107 | { | |
108 | /* It still can happen if we are not in loop-closed SSA form. */ | |
109 | gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA)); | |
110 | return chrec_dont_know; | |
111 | } | |
677cc14d | 112 | |
5be014d5 | 113 | if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) |
c8a2ab6d | 114 | { |
b8698a0f | 115 | left = chrec_fold_plus |
c8a2ab6d | 116 | (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); |
b8698a0f | 117 | right = chrec_fold_plus |
5be014d5 | 118 | (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); |
c8a2ab6d SP |
119 | } |
120 | else | |
121 | { | |
b8698a0f | 122 | left = chrec_fold_minus |
c8a2ab6d | 123 | (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); |
b8698a0f | 124 | right = chrec_fold_minus |
c8a2ab6d SP |
125 | (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); |
126 | } | |
127 | ||
128 | if (chrec_zerop (right)) | |
129 | return left; | |
130 | else | |
b8698a0f L |
131 | return build_polynomial_chrec |
132 | (CHREC_VARIABLE (poly0), left, right); | |
c8a2ab6d SP |
133 | } |
134 | ||
135 | \f | |
136 | ||
137 | /* Fold the multiplication of two polynomial functions. */ | |
138 | ||
b8698a0f L |
139 | static inline tree |
140 | chrec_fold_multiply_poly_poly (tree type, | |
141 | tree poly0, | |
c8a2ab6d SP |
142 | tree poly1) |
143 | { | |
2c5f025d ZD |
144 | tree t0, t1, t2; |
145 | int var; | |
99b1c316 MS |
146 | class loop *loop0 = get_chrec_loop (poly0); |
147 | class loop *loop1 = get_chrec_loop (poly1); | |
2c5f025d | 148 | |
1e128c5f GB |
149 | gcc_assert (poly0); |
150 | gcc_assert (poly1); | |
151 | gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); | |
152 | gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); | |
3da3ff4e RB |
153 | gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0)) |
154 | && useless_type_conversion_p (type, chrec_type (poly1))); | |
b8698a0f | 155 | |
c8a2ab6d SP |
156 | /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, |
157 | {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, | |
158 | {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ | |
677cc14d | 159 | if (flow_loop_nested_p (loop0, loop1)) |
c8a2ab6d | 160 | /* poly0 is a constant wrt. poly1. */ |
b8698a0f L |
161 | return build_polynomial_chrec |
162 | (CHREC_VARIABLE (poly1), | |
c8a2ab6d SP |
163 | chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), |
164 | CHREC_RIGHT (poly1)); | |
b8698a0f | 165 | |
677cc14d | 166 | if (flow_loop_nested_p (loop1, loop0)) |
c8a2ab6d | 167 | /* poly1 is a constant wrt. poly0. */ |
b8698a0f L |
168 | return build_polynomial_chrec |
169 | (CHREC_VARIABLE (poly0), | |
c8a2ab6d SP |
170 | chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), |
171 | CHREC_RIGHT (poly0)); | |
b8698a0f | 172 | |
1b7c8d39 RB |
173 | if (loop0 != loop1) |
174 | { | |
175 | /* It still can happen if we are not in loop-closed SSA form. */ | |
176 | gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA)); | |
177 | return chrec_dont_know; | |
178 | } | |
677cc14d | 179 | |
c8a2ab6d SP |
180 | /* poly0 and poly1 are two polynomials in the same variable, |
181 | {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ | |
b8698a0f | 182 | |
2c5f025d ZD |
183 | /* "a*c". */ |
184 | t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); | |
185 | ||
3cb8677c | 186 | /* "a*d + b*c". */ |
2c5f025d ZD |
187 | t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); |
188 | t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, | |
189 | CHREC_RIGHT (poly0), | |
190 | CHREC_LEFT (poly1))); | |
3cb8677c | 191 | /* "b*d". */ |
2c5f025d | 192 | t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); |
3cb8677c RG |
193 | /* "a*d + b*c + b*d". */ |
194 | t1 = chrec_fold_plus (type, t1, t2); | |
195 | /* "2*b*d". */ | |
7e0923cd SP |
196 | t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type) |
197 | ? build_real (type, dconst2) | |
ff5e9a94 | 198 | : build_int_cst (type, 2), t2); |
2c5f025d ZD |
199 | |
200 | var = CHREC_VARIABLE (poly0); | |
201 | return build_polynomial_chrec (var, t0, | |
202 | build_polynomial_chrec (var, t1, t2)); | |
c8a2ab6d SP |
203 | } |
204 | ||
205 | /* When the operands are automatically_generated_chrec_p, the fold has | |
206 | to respect the semantics of the operands. */ | |
207 | ||
b8698a0f L |
208 | static inline tree |
209 | chrec_fold_automatically_generated_operands (tree op0, | |
c8a2ab6d SP |
210 | tree op1) |
211 | { | |
212 | if (op0 == chrec_dont_know | |
213 | || op1 == chrec_dont_know) | |
214 | return chrec_dont_know; | |
b8698a0f | 215 | |
c8a2ab6d SP |
216 | if (op0 == chrec_known |
217 | || op1 == chrec_known) | |
218 | return chrec_known; | |
b8698a0f | 219 | |
c8a2ab6d SP |
220 | if (op0 == chrec_not_analyzed_yet |
221 | || op1 == chrec_not_analyzed_yet) | |
222 | return chrec_not_analyzed_yet; | |
b8698a0f | 223 | |
8c27b7d4 | 224 | /* The default case produces a safe result. */ |
c8a2ab6d SP |
225 | return chrec_dont_know; |
226 | } | |
227 | ||
228 | /* Fold the addition of two chrecs. */ | |
229 | ||
230 | static tree | |
b8698a0f | 231 | chrec_fold_plus_1 (enum tree_code code, tree type, |
e2157b49 | 232 | tree op0, tree op1) |
c8a2ab6d SP |
233 | { |
234 | if (automatically_generated_chrec_p (op0) | |
235 | || automatically_generated_chrec_p (op1)) | |
236 | return chrec_fold_automatically_generated_operands (op0, op1); | |
b8698a0f | 237 | |
c8a2ab6d SP |
238 | switch (TREE_CODE (op0)) |
239 | { | |
240 | case POLYNOMIAL_CHREC: | |
0547c9b6 RB |
241 | gcc_checking_assert |
242 | (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0))); | |
c8a2ab6d SP |
243 | switch (TREE_CODE (op1)) |
244 | { | |
245 | case POLYNOMIAL_CHREC: | |
0547c9b6 RB |
246 | gcc_checking_assert |
247 | (!chrec_contains_symbols_defined_in_loop (op1, | |
248 | CHREC_VARIABLE (op1))); | |
c8a2ab6d SP |
249 | return chrec_fold_plus_poly_poly (code, type, op0, op1); |
250 | ||
ccc5b640 | 251 | CASE_CONVERT: |
6acfd18c RB |
252 | { |
253 | /* We can strip sign-conversions to signed by performing the | |
254 | operation in unsigned. */ | |
255 | tree optype = TREE_TYPE (TREE_OPERAND (op1, 0)); | |
256 | if (INTEGRAL_TYPE_P (type) | |
257 | && INTEGRAL_TYPE_P (optype) | |
258 | && tree_nop_conversion_p (type, optype) | |
259 | && TYPE_UNSIGNED (optype)) | |
260 | return chrec_convert (type, | |
261 | chrec_fold_plus_1 (code, optype, | |
262 | chrec_convert (optype, | |
263 | op0, NULL), | |
264 | TREE_OPERAND (op1, 0)), | |
265 | NULL); | |
266 | if (tree_contains_chrecs (op1, NULL)) | |
267 | return chrec_dont_know; | |
268 | } | |
191816a3 | 269 | /* FALLTHRU */ |
ccc5b640 | 270 | |
c8a2ab6d | 271 | default: |
5be014d5 | 272 | if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) |
b8698a0f L |
273 | return build_polynomial_chrec |
274 | (CHREC_VARIABLE (op0), | |
c8a2ab6d SP |
275 | chrec_fold_plus (type, CHREC_LEFT (op0), op1), |
276 | CHREC_RIGHT (op0)); | |
277 | else | |
b8698a0f L |
278 | return build_polynomial_chrec |
279 | (CHREC_VARIABLE (op0), | |
c8a2ab6d SP |
280 | chrec_fold_minus (type, CHREC_LEFT (op0), op1), |
281 | CHREC_RIGHT (op0)); | |
282 | } | |
283 | ||
ccc5b640 | 284 | CASE_CONVERT: |
6acfd18c RB |
285 | { |
286 | /* We can strip sign-conversions to signed by performing the | |
287 | operation in unsigned. */ | |
288 | tree optype = TREE_TYPE (TREE_OPERAND (op0, 0)); | |
289 | if (INTEGRAL_TYPE_P (type) | |
290 | && INTEGRAL_TYPE_P (optype) | |
291 | && tree_nop_conversion_p (type, optype) | |
292 | && TYPE_UNSIGNED (optype)) | |
293 | return chrec_convert (type, | |
294 | chrec_fold_plus_1 (code, optype, | |
295 | TREE_OPERAND (op0, 0), | |
296 | chrec_convert (optype, | |
297 | op1, NULL)), | |
298 | NULL); | |
299 | if (tree_contains_chrecs (op0, NULL)) | |
300 | return chrec_dont_know; | |
301 | } | |
191816a3 | 302 | /* FALLTHRU */ |
ccc5b640 | 303 | |
c8a2ab6d SP |
304 | default: |
305 | switch (TREE_CODE (op1)) | |
306 | { | |
307 | case POLYNOMIAL_CHREC: | |
0547c9b6 RB |
308 | gcc_checking_assert |
309 | (!chrec_contains_symbols_defined_in_loop (op1, | |
310 | CHREC_VARIABLE (op1))); | |
5be014d5 | 311 | if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) |
b8698a0f L |
312 | return build_polynomial_chrec |
313 | (CHREC_VARIABLE (op1), | |
c8a2ab6d SP |
314 | chrec_fold_plus (type, op0, CHREC_LEFT (op1)), |
315 | CHREC_RIGHT (op1)); | |
316 | else | |
b8698a0f L |
317 | return build_polynomial_chrec |
318 | (CHREC_VARIABLE (op1), | |
c8a2ab6d | 319 | chrec_fold_minus (type, op0, CHREC_LEFT (op1)), |
b8698a0f | 320 | chrec_fold_multiply (type, CHREC_RIGHT (op1), |
7e0923cd SP |
321 | SCALAR_FLOAT_TYPE_P (type) |
322 | ? build_real (type, dconstm1) | |
323 | : build_int_cst_type (type, -1))); | |
c8a2ab6d | 324 | |
ccc5b640 SP |
325 | CASE_CONVERT: |
326 | if (tree_contains_chrecs (op1, NULL)) | |
327 | return chrec_dont_know; | |
191816a3 | 328 | /* FALLTHRU */ |
ccc5b640 | 329 | |
c8a2ab6d | 330 | default: |
2412d35c | 331 | { |
de0edf87 RB |
332 | int size = 0; |
333 | if ((tree_contains_chrecs (op0, &size) | |
334 | || tree_contains_chrecs (op1, &size)) | |
028d4092 | 335 | && size < param_scev_max_expr_size) |
2412d35c | 336 | return build2 (code, type, op0, op1); |
028d4092 | 337 | else if (size < param_scev_max_expr_size) |
0d82a1c8 RG |
338 | { |
339 | if (code == POINTER_PLUS_EXPR) | |
340 | return fold_build_pointer_plus (fold_convert (type, op0), | |
341 | op1); | |
342 | else | |
343 | return fold_build2 (code, type, | |
344 | fold_convert (type, op0), | |
345 | fold_convert (type, op1)); | |
346 | } | |
de0edf87 RB |
347 | else |
348 | return chrec_dont_know; | |
2412d35c | 349 | } |
c8a2ab6d SP |
350 | } |
351 | } | |
352 | } | |
353 | ||
354 | /* Fold the addition of two chrecs. */ | |
355 | ||
356 | tree | |
b8698a0f | 357 | chrec_fold_plus (tree type, |
c8a2ab6d SP |
358 | tree op0, |
359 | tree op1) | |
360 | { | |
5be014d5 | 361 | enum tree_code code; |
e2157b49 SP |
362 | if (automatically_generated_chrec_p (op0) |
363 | || automatically_generated_chrec_p (op1)) | |
364 | return chrec_fold_automatically_generated_operands (op0, op1); | |
365 | ||
c8a2ab6d | 366 | if (integer_zerop (op0)) |
726a989a | 367 | return chrec_convert (type, op1, NULL); |
c8a2ab6d | 368 | if (integer_zerop (op1)) |
726a989a | 369 | return chrec_convert (type, op0, NULL); |
5be014d5 AP |
370 | |
371 | if (POINTER_TYPE_P (type)) | |
372 | code = POINTER_PLUS_EXPR; | |
373 | else | |
374 | code = PLUS_EXPR; | |
b8698a0f | 375 | |
5be014d5 | 376 | return chrec_fold_plus_1 (code, type, op0, op1); |
c8a2ab6d SP |
377 | } |
378 | ||
379 | /* Fold the subtraction of two chrecs. */ | |
380 | ||
b8698a0f L |
381 | tree |
382 | chrec_fold_minus (tree type, | |
383 | tree op0, | |
c8a2ab6d SP |
384 | tree op1) |
385 | { | |
e2157b49 SP |
386 | if (automatically_generated_chrec_p (op0) |
387 | || automatically_generated_chrec_p (op1)) | |
388 | return chrec_fold_automatically_generated_operands (op0, op1); | |
389 | ||
c8a2ab6d SP |
390 | if (integer_zerop (op1)) |
391 | return op0; | |
b8698a0f | 392 | |
c8a2ab6d SP |
393 | return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); |
394 | } | |
395 | ||
396 | /* Fold the multiplication of two chrecs. */ | |
397 | ||
398 | tree | |
b8698a0f | 399 | chrec_fold_multiply (tree type, |
c8a2ab6d SP |
400 | tree op0, |
401 | tree op1) | |
402 | { | |
403 | if (automatically_generated_chrec_p (op0) | |
404 | || automatically_generated_chrec_p (op1)) | |
405 | return chrec_fold_automatically_generated_operands (op0, op1); | |
b8698a0f | 406 | |
c8a2ab6d SP |
407 | switch (TREE_CODE (op0)) |
408 | { | |
409 | case POLYNOMIAL_CHREC: | |
0547c9b6 RB |
410 | gcc_checking_assert |
411 | (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0))); | |
c8a2ab6d SP |
412 | switch (TREE_CODE (op1)) |
413 | { | |
414 | case POLYNOMIAL_CHREC: | |
0547c9b6 RB |
415 | gcc_checking_assert |
416 | (!chrec_contains_symbols_defined_in_loop (op1, | |
417 | CHREC_VARIABLE (op1))); | |
c8a2ab6d | 418 | return chrec_fold_multiply_poly_poly (type, op0, op1); |
b8698a0f | 419 | |
ccc5b640 SP |
420 | CASE_CONVERT: |
421 | if (tree_contains_chrecs (op1, NULL)) | |
422 | return chrec_dont_know; | |
191816a3 | 423 | /* FALLTHRU */ |
ccc5b640 | 424 | |
c8a2ab6d SP |
425 | default: |
426 | if (integer_onep (op1)) | |
427 | return op0; | |
428 | if (integer_zerop (op1)) | |
ff5e9a94 | 429 | return build_int_cst (type, 0); |
b8698a0f L |
430 | |
431 | return build_polynomial_chrec | |
432 | (CHREC_VARIABLE (op0), | |
c8a2ab6d SP |
433 | chrec_fold_multiply (type, CHREC_LEFT (op0), op1), |
434 | chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); | |
435 | } | |
b8698a0f | 436 | |
ccc5b640 SP |
437 | CASE_CONVERT: |
438 | if (tree_contains_chrecs (op0, NULL)) | |
439 | return chrec_dont_know; | |
191816a3 | 440 | /* FALLTHRU */ |
ccc5b640 | 441 | |
c8a2ab6d SP |
442 | default: |
443 | if (integer_onep (op0)) | |
444 | return op1; | |
b8698a0f | 445 | |
c8a2ab6d | 446 | if (integer_zerop (op0)) |
ff5e9a94 | 447 | return build_int_cst (type, 0); |
b8698a0f | 448 | |
c8a2ab6d SP |
449 | switch (TREE_CODE (op1)) |
450 | { | |
451 | case POLYNOMIAL_CHREC: | |
0547c9b6 RB |
452 | gcc_checking_assert |
453 | (!chrec_contains_symbols_defined_in_loop (op1, | |
454 | CHREC_VARIABLE (op1))); | |
b8698a0f L |
455 | return build_polynomial_chrec |
456 | (CHREC_VARIABLE (op1), | |
c8a2ab6d SP |
457 | chrec_fold_multiply (type, CHREC_LEFT (op1), op0), |
458 | chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); | |
b8698a0f | 459 | |
ccc5b640 SP |
460 | CASE_CONVERT: |
461 | if (tree_contains_chrecs (op1, NULL)) | |
462 | return chrec_dont_know; | |
191816a3 | 463 | /* FALLTHRU */ |
ccc5b640 | 464 | |
c8a2ab6d SP |
465 | default: |
466 | if (integer_onep (op1)) | |
467 | return op0; | |
468 | if (integer_zerop (op1)) | |
ff5e9a94 | 469 | return build_int_cst (type, 0); |
2412d35c | 470 | return fold_build2 (MULT_EXPR, type, op0, op1); |
c8a2ab6d SP |
471 | } |
472 | } | |
473 | } | |
474 | ||
475 | \f | |
476 | ||
477 | /* Operations. */ | |
478 | ||
1a9dddad RS |
479 | /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate |
480 | calculation overflows, otherwise return C(n,k) with type TYPE. */ | |
481 | ||
b8698a0f | 482 | static tree |
1a9dddad | 483 | tree_fold_binomial (tree type, tree n, unsigned int k) |
c8a2ab6d | 484 | { |
4a669ac3 | 485 | wi::overflow_type overflow; |
1a9dddad | 486 | unsigned int i; |
1a9dddad RS |
487 | |
488 | /* Handle the most frequent cases. */ | |
489 | if (k == 0) | |
490 | return build_int_cst (type, 1); | |
491 | if (k == 1) | |
492 | return fold_convert (type, n); | |
493 | ||
2a99de7b RB |
494 | widest_int num = wi::to_widest (n); |
495 | ||
1a9dddad | 496 | /* Check that k <= n. */ |
2a99de7b | 497 | if (wi::ltu_p (num, k)) |
1a9dddad RS |
498 | return NULL_TREE; |
499 | ||
1a9dddad | 500 | /* Denominator = 2. */ |
2a99de7b | 501 | widest_int denom = 2; |
1a9dddad RS |
502 | |
503 | /* Index = Numerator-1. */ | |
2a99de7b | 504 | widest_int idx = num - 1; |
c8a2ab6d | 505 | |
1a9dddad | 506 | /* Numerator = Numerator*Index = n*(n-1). */ |
2a99de7b | 507 | num = wi::smul (num, idx, &overflow); |
9be0ac8c | 508 | if (overflow) |
1a9dddad | 509 | return NULL_TREE; |
c8a2ab6d | 510 | |
1a9dddad RS |
511 | for (i = 3; i <= k; i++) |
512 | { | |
513 | /* Index--. */ | |
9be0ac8c | 514 | --idx; |
1a9dddad RS |
515 | |
516 | /* Numerator *= Index. */ | |
807e902e | 517 | num = wi::smul (num, idx, &overflow); |
9be0ac8c | 518 | if (overflow) |
1a9dddad RS |
519 | return NULL_TREE; |
520 | ||
521 | /* Denominator *= i. */ | |
807e902e | 522 | denom *= i; |
1a9dddad RS |
523 | } |
524 | ||
525 | /* Result = Numerator / Denominator. */ | |
2a99de7b RB |
526 | num = wi::udiv_trunc (num, denom); |
527 | if (! wi::fits_to_tree_p (num, type)) | |
528 | return NULL_TREE; | |
529 | return wide_int_to_tree (type, num); | |
c8a2ab6d SP |
530 | } |
531 | ||
532 | /* Helper function. Use the Newton's interpolating formula for | |
0100ae43 RB |
533 | evaluating the value of the evolution function. |
534 | The result may be in an unsigned type of CHREC. */ | |
c8a2ab6d | 535 | |
b8698a0f | 536 | static tree |
1a9dddad | 537 | chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) |
c8a2ab6d | 538 | { |
1a9dddad RS |
539 | tree arg0, arg1, binomial_n_k; |
540 | tree type = TREE_TYPE (chrec); | |
99b1c316 | 541 | class loop *var_loop = get_loop (cfun, var); |
1a9dddad RS |
542 | |
543 | while (TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
677cc14d | 544 | && flow_loop_nested_p (var_loop, get_chrec_loop (chrec))) |
1a9dddad RS |
545 | chrec = CHREC_LEFT (chrec); |
546 | ||
0100ae43 RB |
547 | /* The formula associates the expression and thus we have to make |
548 | sure to not introduce undefined overflow. */ | |
549 | tree ctype = type; | |
550 | if (INTEGRAL_TYPE_P (type) | |
551 | && ! TYPE_OVERFLOW_WRAPS (type)) | |
552 | ctype = unsigned_type_for (type); | |
553 | ||
1a9dddad RS |
554 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC |
555 | && CHREC_VARIABLE (chrec) == var) | |
c8a2ab6d | 556 | { |
f6ee9fae JJ |
557 | arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1); |
558 | if (arg1 == chrec_dont_know) | |
1a9dddad | 559 | return chrec_dont_know; |
0100ae43 | 560 | binomial_n_k = tree_fold_binomial (ctype, n, k); |
1a9dddad RS |
561 | if (!binomial_n_k) |
562 | return chrec_dont_know; | |
0100ae43 RB |
563 | tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL); |
564 | arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k); | |
565 | return chrec_fold_plus (ctype, arg0, arg1); | |
c8a2ab6d | 566 | } |
1a9dddad | 567 | |
0100ae43 | 568 | binomial_n_k = tree_fold_binomial (ctype, n, k); |
1a9dddad RS |
569 | if (!binomial_n_k) |
570 | return chrec_dont_know; | |
b8698a0f | 571 | |
0100ae43 RB |
572 | return fold_build2 (MULT_EXPR, ctype, |
573 | chrec_convert (ctype, chrec, NULL), binomial_n_k); | |
c8a2ab6d SP |
574 | } |
575 | ||
b8698a0f L |
576 | /* Evaluates "CHREC (X)" when the varying variable is VAR. |
577 | Example: Given the following parameters, | |
578 | ||
c8a2ab6d SP |
579 | var = 1 |
580 | chrec = {3, +, 4}_1 | |
581 | x = 10 | |
b8698a0f L |
582 | |
583 | The result is given by the Newton's interpolating formula: | |
c8a2ab6d SP |
584 | 3 * \binom{10}{0} + 4 * \binom{10}{1}. |
585 | */ | |
586 | ||
b8698a0f | 587 | tree |
c8a2ab6d | 588 | chrec_apply (unsigned var, |
b8698a0f | 589 | tree chrec, |
c8a2ab6d SP |
590 | tree x) |
591 | { | |
592 | tree type = chrec_type (chrec); | |
593 | tree res = chrec_dont_know; | |
594 | ||
595 | if (automatically_generated_chrec_p (chrec) | |
596 | || automatically_generated_chrec_p (x) | |
597 | ||
598 | /* When the symbols are defined in an outer loop, it is possible | |
599 | to symbolically compute the apply, since the symbols are | |
600 | constants with respect to the varying loop. */ | |
a6f778b2 | 601 | || chrec_contains_symbols_defined_in_loop (chrec, var)) |
c8a2ab6d | 602 | return chrec_dont_know; |
b8698a0f | 603 | |
dfedbe40 | 604 | if (dump_file && (dump_flags & TDF_SCEV)) |
c8a2ab6d SP |
605 | fprintf (dump_file, "(chrec_apply \n"); |
606 | ||
3c0c8f9d SP |
607 | if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) |
608 | x = build_real_from_int_cst (type, x); | |
609 | ||
8b059232 | 610 | switch (TREE_CODE (chrec)) |
c8a2ab6d | 611 | { |
8b059232 SP |
612 | case POLYNOMIAL_CHREC: |
613 | if (evolution_function_is_affine_p (chrec)) | |
614 | { | |
615 | if (CHREC_VARIABLE (chrec) != var) | |
616 | return build_polynomial_chrec | |
617 | (CHREC_VARIABLE (chrec), | |
618 | chrec_apply (var, CHREC_LEFT (chrec), x), | |
619 | chrec_apply (var, CHREC_RIGHT (chrec), x)); | |
620 | ||
621 | /* "{a, +, b} (x)" -> "a + b*x". */ | |
622 | x = chrec_convert_rhs (type, x, NULL); | |
623 | res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x); | |
624 | res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); | |
625 | } | |
626 | else if (TREE_CODE (x) == INTEGER_CST | |
627 | && tree_int_cst_sgn (x) == 1) | |
628 | /* testsuite/.../ssa-chrec-38.c. */ | |
0100ae43 | 629 | res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL); |
8b059232 SP |
630 | else |
631 | res = chrec_dont_know; | |
632 | break; | |
b8698a0f | 633 | |
8b059232 SP |
634 | CASE_CONVERT: |
635 | res = chrec_convert (TREE_TYPE (chrec), | |
636 | chrec_apply (var, TREE_OPERAND (chrec, 0), x), | |
637 | NULL); | |
638 | break; | |
b8698a0f | 639 | |
8b059232 SP |
640 | default: |
641 | res = chrec; | |
642 | break; | |
643 | } | |
b8698a0f | 644 | |
dfedbe40 | 645 | if (dump_file && (dump_flags & TDF_SCEV)) |
c8a2ab6d SP |
646 | { |
647 | fprintf (dump_file, " (varying_loop = %d\n", var); | |
648 | fprintf (dump_file, ")\n (chrec = "); | |
ef6cb4c7 | 649 | print_generic_expr (dump_file, chrec); |
c8a2ab6d | 650 | fprintf (dump_file, ")\n (x = "); |
ef6cb4c7 | 651 | print_generic_expr (dump_file, x); |
c8a2ab6d | 652 | fprintf (dump_file, ")\n (res = "); |
ef6cb4c7 | 653 | print_generic_expr (dump_file, res); |
c8a2ab6d SP |
654 | fprintf (dump_file, "))\n"); |
655 | } | |
b8698a0f | 656 | |
c8a2ab6d SP |
657 | return res; |
658 | } | |
659 | ||
2e286fd2 SP |
660 | /* For a given CHREC and an induction variable map IV_MAP that maps |
661 | (loop->num, expr) for every loop number of the current_loops an | |
662 | expression, calls chrec_apply when the expression is not NULL. */ | |
663 | ||
664 | tree | |
9771b263 | 665 | chrec_apply_map (tree chrec, vec<tree> iv_map) |
2e286fd2 SP |
666 | { |
667 | int i; | |
668 | tree expr; | |
669 | ||
9771b263 | 670 | FOR_EACH_VEC_ELT (iv_map, i, expr) |
2e286fd2 SP |
671 | if (expr) |
672 | chrec = chrec_apply (i, chrec, expr); | |
673 | ||
674 | return chrec; | |
675 | } | |
676 | ||
c8a2ab6d SP |
677 | /* Replaces the initial condition in CHREC with INIT_COND. */ |
678 | ||
b8698a0f L |
679 | tree |
680 | chrec_replace_initial_condition (tree chrec, | |
c8a2ab6d SP |
681 | tree init_cond) |
682 | { | |
683 | if (automatically_generated_chrec_p (chrec)) | |
684 | return chrec; | |
e2157b49 SP |
685 | |
686 | gcc_assert (chrec_type (chrec) == chrec_type (init_cond)); | |
687 | ||
c8a2ab6d SP |
688 | switch (TREE_CODE (chrec)) |
689 | { | |
690 | case POLYNOMIAL_CHREC: | |
b8698a0f | 691 | return build_polynomial_chrec |
c8a2ab6d SP |
692 | (CHREC_VARIABLE (chrec), |
693 | chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), | |
694 | CHREC_RIGHT (chrec)); | |
b8698a0f | 695 | |
c8a2ab6d SP |
696 | default: |
697 | return init_cond; | |
698 | } | |
699 | } | |
700 | ||
701 | /* Returns the initial condition of a given CHREC. */ | |
702 | ||
b8698a0f | 703 | tree |
c8a2ab6d SP |
704 | initial_condition (tree chrec) |
705 | { | |
706 | if (automatically_generated_chrec_p (chrec)) | |
707 | return chrec; | |
b8698a0f | 708 | |
c8a2ab6d SP |
709 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) |
710 | return initial_condition (CHREC_LEFT (chrec)); | |
711 | else | |
712 | return chrec; | |
713 | } | |
714 | ||
715 | /* Returns a univariate function that represents the evolution in | |
716 | LOOP_NUM. Mask the evolution of any other loop. */ | |
717 | ||
b8698a0f L |
718 | tree |
719 | hide_evolution_in_other_loops_than_loop (tree chrec, | |
c8a2ab6d SP |
720 | unsigned loop_num) |
721 | { | |
99b1c316 | 722 | class loop *loop = get_loop (cfun, loop_num), *chloop; |
c8a2ab6d SP |
723 | if (automatically_generated_chrec_p (chrec)) |
724 | return chrec; | |
b8698a0f | 725 | |
c8a2ab6d SP |
726 | switch (TREE_CODE (chrec)) |
727 | { | |
728 | case POLYNOMIAL_CHREC: | |
677cc14d ZD |
729 | chloop = get_chrec_loop (chrec); |
730 | ||
731 | if (chloop == loop) | |
b8698a0f L |
732 | return build_polynomial_chrec |
733 | (loop_num, | |
734 | hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), | |
735 | loop_num), | |
c8a2ab6d | 736 | CHREC_RIGHT (chrec)); |
b8698a0f | 737 | |
677cc14d | 738 | else if (flow_loop_nested_p (chloop, loop)) |
c8a2ab6d SP |
739 | /* There is no evolution in this loop. */ |
740 | return initial_condition (chrec); | |
b8698a0f | 741 | |
bc369dbd RB |
742 | else if (flow_loop_nested_p (loop, chloop)) |
743 | return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), | |
744 | loop_num); | |
745 | ||
c8a2ab6d | 746 | else |
bc369dbd | 747 | return chrec_dont_know; |
b8698a0f | 748 | |
c8a2ab6d SP |
749 | default: |
750 | return chrec; | |
751 | } | |
752 | } | |
753 | ||
6775f1f3 IR |
754 | /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is |
755 | true, otherwise returns the initial condition in LOOP_NUM. */ | |
c8a2ab6d | 756 | |
b8698a0f L |
757 | static tree |
758 | chrec_component_in_loop_num (tree chrec, | |
6775f1f3 IR |
759 | unsigned loop_num, |
760 | bool right) | |
c8a2ab6d | 761 | { |
6775f1f3 | 762 | tree component; |
99b1c316 | 763 | class loop *loop = get_loop (cfun, loop_num), *chloop; |
6775f1f3 | 764 | |
c8a2ab6d SP |
765 | if (automatically_generated_chrec_p (chrec)) |
766 | return chrec; | |
b8698a0f | 767 | |
c8a2ab6d SP |
768 | switch (TREE_CODE (chrec)) |
769 | { | |
770 | case POLYNOMIAL_CHREC: | |
677cc14d ZD |
771 | chloop = get_chrec_loop (chrec); |
772 | ||
773 | if (chloop == loop) | |
c8a2ab6d | 774 | { |
6775f1f3 IR |
775 | if (right) |
776 | component = CHREC_RIGHT (chrec); | |
777 | else | |
778 | component = CHREC_LEFT (chrec); | |
779 | ||
c8a2ab6d SP |
780 | if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC |
781 | || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) | |
6775f1f3 | 782 | return component; |
b8698a0f | 783 | |
c8a2ab6d SP |
784 | else |
785 | return build_polynomial_chrec | |
b8698a0f L |
786 | (loop_num, |
787 | chrec_component_in_loop_num (CHREC_LEFT (chrec), | |
788 | loop_num, | |
789 | right), | |
6775f1f3 | 790 | component); |
c8a2ab6d | 791 | } |
b8698a0f | 792 | |
677cc14d | 793 | else if (flow_loop_nested_p (chloop, loop)) |
c8a2ab6d SP |
794 | /* There is no evolution part in this loop. */ |
795 | return NULL_TREE; | |
b8698a0f | 796 | |
c8a2ab6d | 797 | else |
677cc14d ZD |
798 | { |
799 | gcc_assert (flow_loop_nested_p (loop, chloop)); | |
b8698a0f L |
800 | return chrec_component_in_loop_num (CHREC_LEFT (chrec), |
801 | loop_num, | |
677cc14d ZD |
802 | right); |
803 | } | |
b8698a0f | 804 | |
6775f1f3 IR |
805 | default: |
806 | if (right) | |
807 | return NULL_TREE; | |
808 | else | |
809 | return chrec; | |
c8a2ab6d SP |
810 | } |
811 | } | |
812 | ||
6775f1f3 | 813 | /* Returns the evolution part in LOOP_NUM. Example: the call |
b8698a0f | 814 | evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns |
6775f1f3 IR |
815 | {1, +, 2}_1 */ |
816 | ||
b8698a0f L |
817 | tree |
818 | evolution_part_in_loop_num (tree chrec, | |
6775f1f3 IR |
819 | unsigned loop_num) |
820 | { | |
821 | return chrec_component_in_loop_num (chrec, loop_num, true); | |
822 | } | |
823 | ||
824 | /* Returns the initial condition in LOOP_NUM. Example: the call | |
b8698a0f | 825 | initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns |
6775f1f3 IR |
826 | {0, +, 1}_1 */ |
827 | ||
b8698a0f L |
828 | tree |
829 | initial_condition_in_loop_num (tree chrec, | |
6775f1f3 IR |
830 | unsigned loop_num) |
831 | { | |
832 | return chrec_component_in_loop_num (chrec, loop_num, false); | |
833 | } | |
834 | ||
c8a2ab6d SP |
835 | /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. |
836 | This function is essentially used for setting the evolution to | |
837 | chrec_dont_know, for example after having determined that it is | |
838 | impossible to say how many times a loop will execute. */ | |
839 | ||
b8698a0f | 840 | tree |
c8a2ab6d | 841 | reset_evolution_in_loop (unsigned loop_num, |
b8698a0f | 842 | tree chrec, |
c8a2ab6d SP |
843 | tree new_evol) |
844 | { | |
99b1c316 | 845 | class loop *loop = get_loop (cfun, loop_num); |
677cc14d | 846 | |
5be014d5 | 847 | if (POINTER_TYPE_P (chrec_type (chrec))) |
370f4759 | 848 | gcc_assert (ptrofftype_p (chrec_type (new_evol))); |
5be014d5 AP |
849 | else |
850 | gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); | |
e2157b49 | 851 | |
c8a2ab6d | 852 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC |
677cc14d | 853 | && flow_loop_nested_p (loop, get_chrec_loop (chrec))) |
6be74c4f JJ |
854 | { |
855 | tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), | |
856 | new_evol); | |
857 | tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), | |
858 | new_evol); | |
d2ec0277 | 859 | return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right); |
6be74c4f JJ |
860 | } |
861 | ||
c8a2ab6d SP |
862 | while (TREE_CODE (chrec) == POLYNOMIAL_CHREC |
863 | && CHREC_VARIABLE (chrec) == loop_num) | |
864 | chrec = CHREC_LEFT (chrec); | |
b8698a0f | 865 | |
c8a2ab6d SP |
866 | return build_polynomial_chrec (loop_num, chrec, new_evol); |
867 | } | |
868 | ||
869 | /* Merges two evolution functions that were found by following two | |
870 | alternate paths of a conditional expression. */ | |
871 | ||
872 | tree | |
b8698a0f | 873 | chrec_merge (tree chrec1, |
c8a2ab6d SP |
874 | tree chrec2) |
875 | { | |
876 | if (chrec1 == chrec_dont_know | |
877 | || chrec2 == chrec_dont_know) | |
878 | return chrec_dont_know; | |
879 | ||
b8698a0f | 880 | if (chrec1 == chrec_known |
c8a2ab6d SP |
881 | || chrec2 == chrec_known) |
882 | return chrec_known; | |
883 | ||
884 | if (chrec1 == chrec_not_analyzed_yet) | |
885 | return chrec2; | |
886 | if (chrec2 == chrec_not_analyzed_yet) | |
887 | return chrec1; | |
888 | ||
ace23abf | 889 | if (eq_evolutions_p (chrec1, chrec2)) |
c8a2ab6d SP |
890 | return chrec1; |
891 | ||
892 | return chrec_dont_know; | |
893 | } | |
894 | ||
895 | \f | |
896 | ||
897 | /* Observers. */ | |
898 | ||
899 | /* Helper function for is_multivariate_chrec. */ | |
900 | ||
b8698a0f | 901 | static bool |
ed7a4b4b | 902 | is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var) |
c8a2ab6d SP |
903 | { |
904 | if (chrec == NULL_TREE) | |
905 | return false; | |
b8698a0f | 906 | |
c8a2ab6d SP |
907 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) |
908 | { | |
909 | if (CHREC_VARIABLE (chrec) != rec_var) | |
910 | return true; | |
911 | else | |
b8698a0f | 912 | return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) |
c8a2ab6d SP |
913 | || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var)); |
914 | } | |
915 | else | |
916 | return false; | |
917 | } | |
918 | ||
919 | /* Determine whether the given chrec is multivariate or not. */ | |
920 | ||
b8698a0f | 921 | bool |
ed7a4b4b | 922 | is_multivariate_chrec (const_tree chrec) |
c8a2ab6d SP |
923 | { |
924 | if (chrec == NULL_TREE) | |
925 | return false; | |
b8698a0f | 926 | |
c8a2ab6d | 927 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) |
b8698a0f | 928 | return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), |
c8a2ab6d | 929 | CHREC_VARIABLE (chrec)) |
b8698a0f | 930 | || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), |
c8a2ab6d SP |
931 | CHREC_VARIABLE (chrec))); |
932 | else | |
933 | return false; | |
934 | } | |
935 | ||
d6366157 BC |
936 | /* Determines whether the chrec contains symbolic names or not. If LOOP isn't |
937 | NULL, we also consider chrec wrto outer loops of LOOP as symbol. */ | |
c8a2ab6d | 938 | |
577d6588 | 939 | static bool |
d6366157 | 940 | chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited, |
99b1c316 | 941 | class loop *loop) |
c8a2ab6d | 942 | { |
5039610b SL |
943 | int i, n; |
944 | ||
c8a2ab6d SP |
945 | if (chrec == NULL_TREE) |
946 | return false; | |
b8698a0f | 947 | |
c8a2ab6d | 948 | if (TREE_CODE (chrec) == SSA_NAME |
8813a647 | 949 | || VAR_P (chrec) |
8db2698d | 950 | || TREE_CODE (chrec) == POLY_INT_CST |
c8a2ab6d SP |
951 | || TREE_CODE (chrec) == PARM_DECL |
952 | || TREE_CODE (chrec) == FUNCTION_DECL | |
953 | || TREE_CODE (chrec) == LABEL_DECL | |
954 | || TREE_CODE (chrec) == RESULT_DECL | |
955 | || TREE_CODE (chrec) == FIELD_DECL) | |
956 | return true; | |
5039610b | 957 | |
d6366157 BC |
958 | if (loop != NULL |
959 | && TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
960 | && flow_loop_nested_p (get_chrec_loop (chrec), loop)) | |
961 | return true; | |
962 | ||
5fd8a9cb RB |
963 | if (visited.add (chrec)) |
964 | return false; | |
965 | ||
5039610b SL |
966 | n = TREE_OPERAND_LENGTH (chrec); |
967 | for (i = 0; i < n; i++) | |
d6366157 | 968 | if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop)) |
5039610b SL |
969 | return true; |
970 | return false; | |
c8a2ab6d SP |
971 | } |
972 | ||
d6366157 BC |
973 | /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if |
974 | CHREC contains any chrec which is invariant wrto the loop (nest), in other | |
975 | words, chrec defined by outer loops of loop, so from LOOP's point of view, | |
976 | the chrec is considered as a SYMBOL. */ | |
977 | ||
577d6588 | 978 | bool |
99b1c316 | 979 | chrec_contains_symbols (const_tree chrec, class loop* loop) |
577d6588 RB |
980 | { |
981 | hash_set<const_tree> visited; | |
d6366157 | 982 | return chrec_contains_symbols (chrec, visited, loop); |
577d6588 RB |
983 | } |
984 | ||
5fd8a9cb RB |
985 | /* Return true when CHREC contains symbolic names defined in |
986 | LOOP_NB. */ | |
987 | ||
988 | static bool | |
989 | chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb, | |
990 | hash_set<const_tree> &visited) | |
991 | { | |
992 | int i, n; | |
993 | ||
994 | if (chrec == NULL_TREE) | |
995 | return false; | |
996 | ||
997 | if (is_gimple_min_invariant (chrec)) | |
998 | return false; | |
999 | ||
1000 | if (TREE_CODE (chrec) == SSA_NAME) | |
1001 | { | |
1002 | gimple *def; | |
1003 | loop_p def_loop, loop; | |
1004 | ||
1005 | if (SSA_NAME_IS_DEFAULT_DEF (chrec)) | |
1006 | return false; | |
1007 | ||
1008 | def = SSA_NAME_DEF_STMT (chrec); | |
1009 | def_loop = loop_containing_stmt (def); | |
1010 | loop = get_loop (cfun, loop_nb); | |
1011 | ||
1012 | if (def_loop == NULL) | |
1013 | return false; | |
1014 | ||
1015 | if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) | |
1016 | return true; | |
1017 | ||
1018 | return false; | |
1019 | } | |
1020 | ||
1021 | if (visited.add (chrec)) | |
1022 | return false; | |
1023 | ||
1024 | n = TREE_OPERAND_LENGTH (chrec); | |
1025 | for (i = 0; i < n; i++) | |
1026 | if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), | |
1027 | loop_nb, visited)) | |
1028 | return true; | |
1029 | return false; | |
1030 | } | |
1031 | ||
1032 | /* Return true when CHREC contains symbolic names defined in | |
1033 | LOOP_NB. */ | |
1034 | ||
1035 | bool | |
1036 | chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) | |
1037 | { | |
1038 | hash_set<const_tree> visited; | |
1039 | return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited); | |
1040 | } | |
1041 | ||
c8a2ab6d SP |
1042 | /* Determines whether the chrec contains undetermined coefficients. */ |
1043 | ||
577d6588 RB |
1044 | static bool |
1045 | chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited) | |
c8a2ab6d | 1046 | { |
5039610b SL |
1047 | int i, n; |
1048 | ||
e71d7f88 | 1049 | if (chrec == chrec_dont_know) |
c8a2ab6d | 1050 | return true; |
5039610b | 1051 | |
e71d7f88 ZD |
1052 | if (chrec == NULL_TREE) |
1053 | return false; | |
1054 | ||
577d6588 RB |
1055 | if (visited.add (chrec)) |
1056 | return false; | |
1057 | ||
5039610b SL |
1058 | n = TREE_OPERAND_LENGTH (chrec); |
1059 | for (i = 0; i < n; i++) | |
577d6588 | 1060 | if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited)) |
5039610b SL |
1061 | return true; |
1062 | return false; | |
c8a2ab6d SP |
1063 | } |
1064 | ||
577d6588 RB |
1065 | bool |
1066 | chrec_contains_undetermined (const_tree chrec) | |
1067 | { | |
1068 | hash_set<const_tree> visited; | |
1069 | return chrec_contains_undetermined (chrec, visited); | |
1070 | } | |
1071 | ||
2412d35c SP |
1072 | /* Determines whether the tree EXPR contains chrecs, and increment |
1073 | SIZE if it is not a NULL pointer by an estimation of the depth of | |
1074 | the tree. */ | |
c8a2ab6d | 1075 | |
577d6588 RB |
1076 | static bool |
1077 | tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited) | |
c8a2ab6d | 1078 | { |
5039610b SL |
1079 | int i, n; |
1080 | ||
c8a2ab6d SP |
1081 | if (expr == NULL_TREE) |
1082 | return false; | |
2412d35c SP |
1083 | |
1084 | if (size) | |
1085 | (*size)++; | |
b8698a0f | 1086 | |
c8a2ab6d SP |
1087 | if (tree_is_chrec (expr)) |
1088 | return true; | |
2412d35c | 1089 | |
5fd8a9cb RB |
1090 | if (visited.add (expr)) |
1091 | return false; | |
1092 | ||
5039610b SL |
1093 | n = TREE_OPERAND_LENGTH (expr); |
1094 | for (i = 0; i < n; i++) | |
577d6588 | 1095 | if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited)) |
5039610b SL |
1096 | return true; |
1097 | return false; | |
c8a2ab6d SP |
1098 | } |
1099 | ||
577d6588 RB |
1100 | bool |
1101 | tree_contains_chrecs (const_tree expr, int *size) | |
1102 | { | |
1103 | hash_set<const_tree> visited; | |
1104 | return tree_contains_chrecs (expr, size, visited); | |
1105 | } | |
1106 | ||
1107 | ||
1e8552eb SP |
1108 | /* Recursive helper function. */ |
1109 | ||
1110 | static bool | |
1111 | evolution_function_is_invariant_rec_p (tree chrec, int loopnum) | |
1112 | { | |
1113 | if (evolution_function_is_constant_p (chrec)) | |
1114 | return true; | |
1115 | ||
6a732743 SP |
1116 | if (TREE_CODE (chrec) == SSA_NAME |
1117 | && (loopnum == 0 | |
0fc822d0 | 1118 | || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec))) |
1e8552eb SP |
1119 | return true; |
1120 | ||
7ce7896c SP |
1121 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) |
1122 | { | |
1123 | if (CHREC_VARIABLE (chrec) == (unsigned) loopnum | |
0fc822d0 RB |
1124 | || flow_loop_nested_p (get_loop (cfun, loopnum), |
1125 | get_chrec_loop (chrec)) | |
7ce7896c SP |
1126 | || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), |
1127 | loopnum) | |
1128 | || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), | |
1129 | loopnum)) | |
1130 | return false; | |
1131 | return true; | |
1132 | } | |
1e8552eb | 1133 | |
5039610b | 1134 | switch (TREE_OPERAND_LENGTH (chrec)) |
1e8552eb SP |
1135 | { |
1136 | case 2: | |
1137 | if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), | |
1138 | loopnum)) | |
1139 | return false; | |
191816a3 | 1140 | /* FALLTHRU */ |
b8698a0f | 1141 | |
1e8552eb SP |
1142 | case 1: |
1143 | if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), | |
1144 | loopnum)) | |
1145 | return false; | |
1146 | return true; | |
1147 | ||
1148 | default: | |
1149 | return false; | |
1150 | } | |
1151 | ||
1152 | return false; | |
1153 | } | |
1154 | ||
1155 | /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ | |
1156 | ||
1157 | bool | |
1158 | evolution_function_is_invariant_p (tree chrec, int loopnum) | |
1159 | { | |
d51157de | 1160 | return evolution_function_is_invariant_rec_p (chrec, loopnum); |
1e8552eb SP |
1161 | } |
1162 | ||
c8a2ab6d SP |
1163 | /* Determine whether the given tree is an affine multivariate |
1164 | evolution. */ | |
1165 | ||
b8698a0f | 1166 | bool |
ed7a4b4b | 1167 | evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum) |
c8a2ab6d SP |
1168 | { |
1169 | if (chrec == NULL_TREE) | |
1170 | return false; | |
b8698a0f | 1171 | |
c8a2ab6d SP |
1172 | switch (TREE_CODE (chrec)) |
1173 | { | |
1174 | case POLYNOMIAL_CHREC: | |
a50411de | 1175 | if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum)) |
c8a2ab6d | 1176 | { |
a50411de | 1177 | if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)) |
c8a2ab6d SP |
1178 | return true; |
1179 | else | |
1180 | { | |
1181 | if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC | |
b8698a0f | 1182 | && CHREC_VARIABLE (CHREC_RIGHT (chrec)) |
c8a2ab6d | 1183 | != CHREC_VARIABLE (chrec) |
b8698a0f | 1184 | && evolution_function_is_affine_multivariate_p |
a50411de | 1185 | (CHREC_RIGHT (chrec), loopnum)) |
c8a2ab6d SP |
1186 | return true; |
1187 | else | |
1188 | return false; | |
1189 | } | |
1190 | } | |
1191 | else | |
1192 | { | |
a50411de | 1193 | if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum) |
c8a2ab6d SP |
1194 | && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC |
1195 | && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) | |
b8698a0f | 1196 | && evolution_function_is_affine_multivariate_p |
a50411de | 1197 | (CHREC_LEFT (chrec), loopnum)) |
c8a2ab6d SP |
1198 | return true; |
1199 | else | |
1200 | return false; | |
1201 | } | |
b8698a0f | 1202 | |
c8a2ab6d SP |
1203 | default: |
1204 | return false; | |
1205 | } | |
1206 | } | |
1207 | ||
b8698a0f | 1208 | /* Determine whether the given tree is a function in zero or one |
9e14603d BC |
1209 | variables with respect to loop specified by LOOPNUM. Note only positive |
1210 | LOOPNUM stands for a real loop. */ | |
c8a2ab6d SP |
1211 | |
1212 | bool | |
9e14603d | 1213 | evolution_function_is_univariate_p (const_tree chrec, int loopnum) |
c8a2ab6d SP |
1214 | { |
1215 | if (chrec == NULL_TREE) | |
1216 | return true; | |
b8698a0f | 1217 | |
9e14603d | 1218 | tree sub_chrec; |
c8a2ab6d SP |
1219 | switch (TREE_CODE (chrec)) |
1220 | { | |
1221 | case POLYNOMIAL_CHREC: | |
1222 | switch (TREE_CODE (CHREC_LEFT (chrec))) | |
1223 | { | |
1224 | case POLYNOMIAL_CHREC: | |
9e14603d BC |
1225 | sub_chrec = CHREC_LEFT (chrec); |
1226 | if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec) | |
1227 | && (loopnum <= 0 | |
1228 | || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum | |
1229 | || flow_loop_nested_p (get_loop (cfun, loopnum), | |
1230 | get_chrec_loop (sub_chrec)))) | |
c8a2ab6d | 1231 | return false; |
9e14603d | 1232 | if (!evolution_function_is_univariate_p (sub_chrec, loopnum)) |
c8a2ab6d SP |
1233 | return false; |
1234 | break; | |
b8698a0f | 1235 | |
c8a2ab6d | 1236 | default: |
754870ed RG |
1237 | if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL)) |
1238 | return false; | |
c8a2ab6d SP |
1239 | break; |
1240 | } | |
b8698a0f | 1241 | |
c8a2ab6d SP |
1242 | switch (TREE_CODE (CHREC_RIGHT (chrec))) |
1243 | { | |
1244 | case POLYNOMIAL_CHREC: | |
9e14603d BC |
1245 | sub_chrec = CHREC_RIGHT (chrec); |
1246 | if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec) | |
1247 | && (loopnum <= 0 | |
1248 | || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum | |
1249 | || flow_loop_nested_p (get_loop (cfun, loopnum), | |
1250 | get_chrec_loop (sub_chrec)))) | |
c8a2ab6d | 1251 | return false; |
9e14603d | 1252 | if (!evolution_function_is_univariate_p (sub_chrec, loopnum)) |
c8a2ab6d SP |
1253 | return false; |
1254 | break; | |
b8698a0f | 1255 | |
c8a2ab6d | 1256 | default: |
754870ed RG |
1257 | if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL)) |
1258 | return false; | |
b8698a0f | 1259 | break; |
c8a2ab6d | 1260 | } |
65791f42 | 1261 | return true; |
b8698a0f | 1262 | |
c8a2ab6d SP |
1263 | default: |
1264 | return true; | |
1265 | } | |
1266 | } | |
1267 | ||
86df10e3 SP |
1268 | /* Returns the number of variables of CHREC. Example: the call |
1269 | nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ | |
1270 | ||
b8698a0f | 1271 | unsigned |
86df10e3 SP |
1272 | nb_vars_in_chrec (tree chrec) |
1273 | { | |
1274 | if (chrec == NULL_TREE) | |
1275 | return 0; | |
1276 | ||
1277 | switch (TREE_CODE (chrec)) | |
1278 | { | |
1279 | case POLYNOMIAL_CHREC: | |
b8698a0f | 1280 | return 1 + nb_vars_in_chrec |
86df10e3 SP |
1281 | (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); |
1282 | ||
1283 | default: | |
1284 | return 0; | |
1285 | } | |
1286 | } | |
1287 | ||
d7f5de76 ZD |
1288 | /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv |
1289 | the scev corresponds to. AT_STMT is the statement at that the scev is | |
b24d9420 BC |
1290 | evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume |
1291 | that the rules for overflow of the given language apply (e.g., that signed | |
1292 | arithmetics in C does not overflow) -- i.e., to use them to avoid | |
1293 | unnecessary tests, but also to enforce that the result follows them. | |
1294 | FROM is the source variable converted if it's not NULL. Returns true if | |
1295 | the conversion succeeded, false otherwise. */ | |
d7f5de76 ZD |
1296 | |
1297 | bool | |
99b1c316 | 1298 | convert_affine_scev (class loop *loop, tree type, |
355fe088 | 1299 | tree *base, tree *step, gimple *at_stmt, |
b24d9420 | 1300 | bool use_overflow_semantics, tree from) |
d7f5de76 ZD |
1301 | { |
1302 | tree ct = TREE_TYPE (*step); | |
1303 | bool enforce_overflow_semantics; | |
1304 | bool must_check_src_overflow, must_check_rslt_overflow; | |
1305 | tree new_base, new_step; | |
5be014d5 | 1306 | tree step_type = POINTER_TYPE_P (type) ? sizetype : type; |
d7f5de76 ZD |
1307 | |
1308 | /* In general, | |
1309 | (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i, | |
1310 | but we must check some assumptions. | |
b8698a0f | 1311 | |
d7f5de76 ZD |
1312 | 1) If [BASE, +, STEP] wraps, the equation is not valid when precision |
1313 | of CT is smaller than the precision of TYPE. For example, when we | |
1314 | cast unsigned char [254, +, 1] to unsigned, the values on left side | |
1315 | are 254, 255, 0, 1, ..., but those on the right side are | |
1316 | 254, 255, 256, 257, ... | |
1317 | 2) In case that we must also preserve the fact that signed ivs do not | |
1318 | overflow, we must additionally check that the new iv does not wrap. | |
1319 | For example, unsigned char [125, +, 1] casted to signed char could | |
1320 | become a wrapping variable with values 125, 126, 127, -128, -127, ..., | |
1321 | which would confuse optimizers that assume that this does not | |
1322 | happen. */ | |
1323 | must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type); | |
1324 | ||
1325 | enforce_overflow_semantics = (use_overflow_semantics | |
1326 | && nowrap_type_p (type)); | |
1327 | if (enforce_overflow_semantics) | |
1328 | { | |
1329 | /* We can avoid checking whether the result overflows in the following | |
1330 | cases: | |
1331 | ||
1332 | -- must_check_src_overflow is true, and the range of TYPE is superset | |
1333 | of the range of CT -- i.e., in all cases except if CT signed and | |
1334 | TYPE unsigned. | |
20527215 ZD |
1335 | -- both CT and TYPE have the same precision and signedness, and we |
1336 | verify instead that the source does not overflow (this may be | |
1337 | easier than verifying it for the result, as we may use the | |
1338 | information about the semantics of overflow in CT). */ | |
d7f5de76 ZD |
1339 | if (must_check_src_overflow) |
1340 | { | |
1341 | if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct)) | |
1342 | must_check_rslt_overflow = true; | |
1343 | else | |
1344 | must_check_rslt_overflow = false; | |
1345 | } | |
1346 | else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type) | |
1347 | && TYPE_PRECISION (ct) == TYPE_PRECISION (type)) | |
20527215 ZD |
1348 | { |
1349 | must_check_rslt_overflow = false; | |
1350 | must_check_src_overflow = true; | |
1351 | } | |
d7f5de76 ZD |
1352 | else |
1353 | must_check_rslt_overflow = true; | |
1354 | } | |
1355 | else | |
1356 | must_check_rslt_overflow = false; | |
1357 | ||
1358 | if (must_check_src_overflow | |
b24d9420 | 1359 | && scev_probably_wraps_p (from, *base, *step, at_stmt, loop, |
d7f5de76 ZD |
1360 | use_overflow_semantics)) |
1361 | return false; | |
1362 | ||
c70ed622 | 1363 | new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics); |
d7f5de76 ZD |
1364 | /* The step must be sign extended, regardless of the signedness |
1365 | of CT and TYPE. This only needs to be handled specially when | |
1366 | CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] | |
1367 | (with values 100, 99, 98, ...) from becoming signed or unsigned | |
b8698a0f | 1368 | [100, +, 255] with values 100, 355, ...; the sign-extension is |
d7f5de76 ZD |
1369 | performed by default when CT is signed. */ |
1370 | new_step = *step; | |
5be014d5 | 1371 | if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) |
1bbc6693 XDL |
1372 | { |
1373 | tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0); | |
c70ed622 BC |
1374 | new_step = chrec_convert (signed_ct, new_step, at_stmt, |
1375 | use_overflow_semantics); | |
1bbc6693 | 1376 | } |
c70ed622 BC |
1377 | new_step = chrec_convert (step_type, new_step, at_stmt, |
1378 | use_overflow_semantics); | |
d7f5de76 ZD |
1379 | |
1380 | if (automatically_generated_chrec_p (new_base) | |
1381 | || automatically_generated_chrec_p (new_step)) | |
1382 | return false; | |
1383 | ||
1384 | if (must_check_rslt_overflow | |
1385 | /* Note that in this case we cannot use the fact that signed variables | |
1386 | do not overflow, as this is what we are verifying for the new iv. */ | |
b24d9420 BC |
1387 | && scev_probably_wraps_p (NULL_TREE, new_base, new_step, |
1388 | at_stmt, loop, false)) | |
d7f5de76 ZD |
1389 | return false; |
1390 | ||
1391 | *base = new_base; | |
1392 | *step = new_step; | |
1393 | return true; | |
1394 | } | |
c8a2ab6d SP |
1395 | \f |
1396 | ||
072edf07 | 1397 | /* Convert CHREC for the right hand side of a CHREC. |
5be014d5 | 1398 | The increment for a pointer type is always sizetype. */ |
072edf07 | 1399 | |
b8698a0f | 1400 | tree |
355fe088 | 1401 | chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt) |
5be014d5 AP |
1402 | { |
1403 | if (POINTER_TYPE_P (type)) | |
072edf07 SP |
1404 | type = sizetype; |
1405 | ||
5be014d5 AP |
1406 | return chrec_convert (type, chrec, at_stmt); |
1407 | } | |
1408 | ||
d7f5de76 ZD |
1409 | /* Convert CHREC to TYPE. When the analyzer knows the context in |
1410 | which the CHREC is built, it sets AT_STMT to the statement that | |
1411 | contains the definition of the analyzed variable, otherwise the | |
1412 | conversion is less accurate: the information is used for | |
1413 | determining a more accurate estimation of the number of iterations. | |
1414 | By default AT_STMT could be safely set to NULL_TREE. | |
b8698a0f | 1415 | |
d7f5de76 ZD |
1416 | USE_OVERFLOW_SEMANTICS is true if this function should assume that |
1417 | the rules for overflow of the given language apply (e.g., that signed | |
b24d9420 BC |
1418 | arithmetics in C does not overflow) -- i.e., to use them to avoid |
1419 | unnecessary tests, but also to enforce that the result follows them. | |
1420 | ||
1421 | FROM is the source variable converted if it's not NULL. */ | |
d7f5de76 | 1422 | |
b8698a0f | 1423 | static tree |
355fe088 | 1424 | chrec_convert_1 (tree type, tree chrec, gimple *at_stmt, |
b24d9420 | 1425 | bool use_overflow_semantics, tree from) |
c8a2ab6d | 1426 | { |
1e8552eb | 1427 | tree ct, res; |
d7f5de76 | 1428 | tree base, step; |
99b1c316 | 1429 | class loop *loop; |
1e8552eb | 1430 | |
c8a2ab6d SP |
1431 | if (automatically_generated_chrec_p (chrec)) |
1432 | return chrec; | |
b8698a0f | 1433 | |
c8a2ab6d | 1434 | ct = chrec_type (chrec); |
3da3ff4e | 1435 | if (useless_type_conversion_p (type, ct)) |
c8a2ab6d SP |
1436 | return chrec; |
1437 | ||
d7f5de76 ZD |
1438 | if (!evolution_function_is_affine_p (chrec)) |
1439 | goto keep_cast; | |
18aed06a | 1440 | |
42fd6772 | 1441 | loop = get_chrec_loop (chrec); |
d7f5de76 ZD |
1442 | base = CHREC_LEFT (chrec); |
1443 | step = CHREC_RIGHT (chrec); | |
1e8552eb | 1444 | |
d7f5de76 | 1445 | if (convert_affine_scev (loop, type, &base, &step, at_stmt, |
b24d9420 | 1446 | use_overflow_semantics, from)) |
d7f5de76 | 1447 | return build_polynomial_chrec (loop->num, base, step); |
c8a2ab6d | 1448 | |
d7f5de76 ZD |
1449 | /* If we cannot propagate the cast inside the chrec, just keep the cast. */ |
1450 | keep_cast: | |
d73fb533 RG |
1451 | /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that |
1452 | may be more expensive. We do want to perform this optimization here | |
1453 | though for canonicalization reasons. */ | |
1454 | if (use_overflow_semantics | |
1455 | && (TREE_CODE (chrec) == PLUS_EXPR | |
1456 | || TREE_CODE (chrec) == MINUS_EXPR) | |
dc01fed1 JJ |
1457 | && TREE_CODE (type) == INTEGER_TYPE |
1458 | && TREE_CODE (ct) == INTEGER_TYPE | |
d73fb533 RG |
1459 | && TYPE_PRECISION (type) > TYPE_PRECISION (ct) |
1460 | && TYPE_OVERFLOW_UNDEFINED (ct)) | |
1461 | res = fold_build2 (TREE_CODE (chrec), type, | |
1462 | fold_convert (type, TREE_OPERAND (chrec, 0)), | |
1463 | fold_convert (type, TREE_OPERAND (chrec, 1))); | |
195b4c50 RG |
1464 | /* Similar perform the trick that (signed char)((int)x + 2) can be |
1465 | narrowed to (signed char)((unsigned char)x + 2). */ | |
1466 | else if (use_overflow_semantics | |
1467 | && TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
1468 | && TREE_CODE (ct) == INTEGER_TYPE | |
1469 | && TREE_CODE (type) == INTEGER_TYPE | |
1470 | && TYPE_OVERFLOW_UNDEFINED (type) | |
1471 | && TYPE_PRECISION (type) < TYPE_PRECISION (ct)) | |
1472 | { | |
1473 | tree utype = unsigned_type_for (type); | |
1474 | res = build_polynomial_chrec (CHREC_VARIABLE (chrec), | |
1475 | fold_convert (utype, | |
1476 | CHREC_LEFT (chrec)), | |
1477 | fold_convert (utype, | |
1478 | CHREC_RIGHT (chrec))); | |
b24d9420 | 1479 | res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from); |
195b4c50 | 1480 | } |
d73fb533 RG |
1481 | else |
1482 | res = fold_convert (type, chrec); | |
c4cdbeb4 | 1483 | |
1e8552eb SP |
1484 | /* Don't propagate overflows. */ |
1485 | if (CONSTANT_CLASS_P (res)) | |
455f14dd | 1486 | TREE_OVERFLOW (res) = 0; |
1e8552eb SP |
1487 | |
1488 | /* But reject constants that don't fit in their type after conversion. | |
1489 | This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the | |
1490 | natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, | |
1491 | and can cause problems later when computing niters of loops. Note | |
1492 | that we don't do the check before converting because we don't want | |
1493 | to reject conversions of negative chrecs to unsigned types. */ | |
1494 | if (TREE_CODE (res) == INTEGER_CST | |
1495 | && TREE_CODE (type) == INTEGER_TYPE | |
1496 | && !int_fits_type_p (res, type)) | |
1497 | res = chrec_dont_know; | |
1498 | ||
1499 | return res; | |
c8a2ab6d SP |
1500 | } |
1501 | ||
c70ed622 BC |
1502 | /* Convert CHREC to TYPE. When the analyzer knows the context in |
1503 | which the CHREC is built, it sets AT_STMT to the statement that | |
1504 | contains the definition of the analyzed variable, otherwise the | |
1505 | conversion is less accurate: the information is used for | |
1506 | determining a more accurate estimation of the number of iterations. | |
1507 | By default AT_STMT could be safely set to NULL_TREE. | |
1508 | ||
1509 | The following rule is always true: TREE_TYPE (chrec) == | |
1510 | TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). | |
1511 | An example of what could happen when adding two chrecs and the type | |
1512 | of the CHREC_RIGHT is different than CHREC_LEFT is: | |
1513 | ||
1514 | {(uint) 0, +, (uchar) 10} + | |
1515 | {(uint) 0, +, (uchar) 250} | |
1516 | ||
1517 | that would produce a wrong result if CHREC_RIGHT is not (uint): | |
1518 | ||
1519 | {(uint) 0, +, (uchar) 4} | |
1520 | ||
1521 | instead of | |
1522 | ||
1523 | {(uint) 0, +, (uint) 260} | |
1524 | ||
1525 | USE_OVERFLOW_SEMANTICS is true if this function should assume that | |
1526 | the rules for overflow of the given language apply (e.g., that signed | |
b24d9420 BC |
1527 | arithmetics in C does not overflow) -- i.e., to use them to avoid |
1528 | unnecessary tests, but also to enforce that the result follows them. | |
1529 | ||
1530 | FROM is the source variable converted if it's not NULL. */ | |
c70ed622 BC |
1531 | |
1532 | tree | |
355fe088 | 1533 | chrec_convert (tree type, tree chrec, gimple *at_stmt, |
b24d9420 | 1534 | bool use_overflow_semantics, tree from) |
c70ed622 | 1535 | { |
b24d9420 | 1536 | return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from); |
c70ed622 BC |
1537 | } |
1538 | ||
2282a0e6 ZD |
1539 | /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new |
1540 | chrec if something else than what chrec_convert would do happens, NULL_TREE | |
c70ed622 BC |
1541 | otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS |
1542 | if the result chrec may overflow. */ | |
2282a0e6 ZD |
1543 | |
1544 | tree | |
c70ed622 | 1545 | chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions) |
2282a0e6 | 1546 | { |
5be014d5 | 1547 | tree inner_type, left, right, lc, rc, rtype; |
2282a0e6 | 1548 | |
c70ed622 BC |
1549 | gcc_assert (fold_conversions != NULL); |
1550 | ||
2282a0e6 ZD |
1551 | if (automatically_generated_chrec_p (chrec) |
1552 | || TREE_CODE (chrec) != POLYNOMIAL_CHREC) | |
1553 | return NULL_TREE; | |
1554 | ||
1555 | inner_type = TREE_TYPE (chrec); | |
1556 | if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type)) | |
1557 | return NULL_TREE; | |
1558 | ||
c70ed622 BC |
1559 | if (useless_type_conversion_p (type, inner_type)) |
1560 | return NULL_TREE; | |
1561 | ||
1562 | if (!*fold_conversions && evolution_function_is_affine_p (chrec)) | |
1563 | { | |
1564 | tree base, step; | |
99b1c316 | 1565 | class loop *loop; |
c70ed622 BC |
1566 | |
1567 | loop = get_chrec_loop (chrec); | |
1568 | base = CHREC_LEFT (chrec); | |
1569 | step = CHREC_RIGHT (chrec); | |
1570 | if (convert_affine_scev (loop, type, &base, &step, NULL, true)) | |
1571 | return build_polynomial_chrec (loop->num, base, step); | |
1572 | } | |
5be014d5 AP |
1573 | rtype = POINTER_TYPE_P (type) ? sizetype : type; |
1574 | ||
2282a0e6 ZD |
1575 | left = CHREC_LEFT (chrec); |
1576 | right = CHREC_RIGHT (chrec); | |
c70ed622 | 1577 | lc = chrec_convert_aggressive (type, left, fold_conversions); |
2282a0e6 | 1578 | if (!lc) |
726a989a | 1579 | lc = chrec_convert (type, left, NULL); |
c70ed622 | 1580 | rc = chrec_convert_aggressive (rtype, right, fold_conversions); |
2282a0e6 | 1581 | if (!rc) |
726a989a | 1582 | rc = chrec_convert (rtype, right, NULL); |
b8698a0f | 1583 | |
c70ed622 BC |
1584 | *fold_conversions = true; |
1585 | ||
2282a0e6 ZD |
1586 | return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); |
1587 | } | |
1588 | ||
0ff4040e SP |
1589 | /* Returns true when CHREC0 == CHREC1. */ |
1590 | ||
b8698a0f | 1591 | bool |
ed7a4b4b | 1592 | eq_evolutions_p (const_tree chrec0, const_tree chrec1) |
0ff4040e SP |
1593 | { |
1594 | if (chrec0 == NULL_TREE | |
1595 | || chrec1 == NULL_TREE | |
1596 | || TREE_CODE (chrec0) != TREE_CODE (chrec1)) | |
1597 | return false; | |
1598 | ||
1599 | if (chrec0 == chrec1) | |
1600 | return true; | |
1601 | ||
e546907c RB |
1602 | if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1))) |
1603 | return false; | |
1604 | ||
0ff4040e SP |
1605 | switch (TREE_CODE (chrec0)) |
1606 | { | |
0ff4040e SP |
1607 | case POLYNOMIAL_CHREC: |
1608 | return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) | |
1609 | && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) | |
1610 | && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); | |
2bdea539 MM |
1611 | |
1612 | case PLUS_EXPR: | |
1613 | case MULT_EXPR: | |
1614 | case MINUS_EXPR: | |
1615 | case POINTER_PLUS_EXPR: | |
1616 | return eq_evolutions_p (TREE_OPERAND (chrec0, 0), | |
1617 | TREE_OPERAND (chrec1, 0)) | |
1618 | && eq_evolutions_p (TREE_OPERAND (chrec0, 1), | |
1619 | TREE_OPERAND (chrec1, 1)); | |
1620 | ||
e546907c RB |
1621 | CASE_CONVERT: |
1622 | return eq_evolutions_p (TREE_OPERAND (chrec0, 0), | |
1623 | TREE_OPERAND (chrec1, 0)); | |
1624 | ||
0ff4040e | 1625 | default: |
e546907c | 1626 | return operand_equal_p (chrec0, chrec1, 0); |
b8698a0f | 1627 | } |
0ff4040e SP |
1628 | } |
1629 | ||
d7f5de76 ZD |
1630 | /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), |
1631 | EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine | |
1632 | which of these cases happens. */ | |
1633 | ||
1634 | enum ev_direction | |
ed7a4b4b | 1635 | scev_direction (const_tree chrec) |
d7f5de76 | 1636 | { |
ed7a4b4b | 1637 | const_tree step; |
d7f5de76 ZD |
1638 | |
1639 | if (!evolution_function_is_affine_p (chrec)) | |
1640 | return EV_DIR_UNKNOWN; | |
1641 | ||
1642 | step = CHREC_RIGHT (chrec); | |
1643 | if (TREE_CODE (step) != INTEGER_CST) | |
1644 | return EV_DIR_UNKNOWN; | |
1645 | ||
1646 | if (tree_int_cst_sign_bit (step)) | |
1647 | return EV_DIR_DECREASES; | |
1648 | else | |
1649 | return EV_DIR_GROWS; | |
1650 | } | |
f8bf9252 SP |
1651 | |
1652 | /* Iterates over all the components of SCEV, and calls CBCK. */ | |
1653 | ||
1654 | void | |
1655 | for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data) | |
1656 | { | |
1657 | switch (TREE_CODE_LENGTH (TREE_CODE (*scev))) | |
1658 | { | |
1659 | case 3: | |
1660 | for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data); | |
191816a3 | 1661 | /* FALLTHRU */ |
f8bf9252 SP |
1662 | |
1663 | case 2: | |
1664 | for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data); | |
191816a3 | 1665 | /* FALLTHRU */ |
765deab7 | 1666 | |
f8bf9252 SP |
1667 | case 1: |
1668 | for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data); | |
191816a3 | 1669 | /* FALLTHRU */ |
f8bf9252 SP |
1670 | |
1671 | default: | |
1672 | cbck (scev, data); | |
1673 | break; | |
1674 | } | |
1675 | } | |
1676 | ||
6a114766 JS |
1677 | /* Returns true when the operation can be part of a linear |
1678 | expression. */ | |
1679 | ||
1680 | static inline bool | |
1681 | operator_is_linear (tree scev) | |
1682 | { | |
1683 | switch (TREE_CODE (scev)) | |
1684 | { | |
1685 | case INTEGER_CST: | |
1686 | case POLYNOMIAL_CHREC: | |
1687 | case PLUS_EXPR: | |
1688 | case POINTER_PLUS_EXPR: | |
1689 | case MULT_EXPR: | |
1690 | case MINUS_EXPR: | |
1691 | case NEGATE_EXPR: | |
1692 | case SSA_NAME: | |
1693 | case NON_LVALUE_EXPR: | |
765deab7 | 1694 | case BIT_NOT_EXPR: |
6a114766 JS |
1695 | CASE_CONVERT: |
1696 | return true; | |
1697 | ||
1698 | default: | |
1699 | return false; | |
1700 | } | |
1701 | } | |
1702 | ||
1703 | /* Return true when SCEV is a linear expression. Linear expressions | |
1704 | can contain additions, substractions and multiplications. | |
1705 | Multiplications are restricted to constant scaling: "cst * x". */ | |
1706 | ||
1707 | bool | |
1708 | scev_is_linear_expression (tree scev) | |
1709 | { | |
7668b0a6 RB |
1710 | if (evolution_function_is_constant_p (scev)) |
1711 | return true; | |
1712 | ||
6a114766 JS |
1713 | if (scev == NULL |
1714 | || !operator_is_linear (scev)) | |
1715 | return false; | |
1716 | ||
1717 | if (TREE_CODE (scev) == MULT_EXPR) | |
1718 | return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL) | |
1719 | && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL)); | |
1720 | ||
765deab7 SP |
1721 | if (TREE_CODE (scev) == POLYNOMIAL_CHREC |
1722 | && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev))) | |
1723 | return false; | |
1724 | ||
6a114766 JS |
1725 | switch (TREE_CODE_LENGTH (TREE_CODE (scev))) |
1726 | { | |
1727 | case 3: | |
1728 | return scev_is_linear_expression (TREE_OPERAND (scev, 0)) | |
1729 | && scev_is_linear_expression (TREE_OPERAND (scev, 1)) | |
1730 | && scev_is_linear_expression (TREE_OPERAND (scev, 2)); | |
1731 | ||
1732 | case 2: | |
1733 | return scev_is_linear_expression (TREE_OPERAND (scev, 0)) | |
1734 | && scev_is_linear_expression (TREE_OPERAND (scev, 1)); | |
765deab7 | 1735 | |
6a114766 JS |
1736 | case 1: |
1737 | return scev_is_linear_expression (TREE_OPERAND (scev, 0)); | |
1738 | ||
1739 | case 0: | |
1740 | return true; | |
1741 | ||
1742 | default: | |
1743 | return false; | |
1744 | } | |
1745 | } | |
e7c705bb SP |
1746 | |
1747 | /* Determines whether the expression CHREC contains only interger consts | |
1748 | in the right parts. */ | |
1749 | ||
1750 | bool | |
1751 | evolution_function_right_is_integer_cst (const_tree chrec) | |
1752 | { | |
1753 | if (chrec == NULL_TREE) | |
1754 | return false; | |
1755 | ||
1756 | switch (TREE_CODE (chrec)) | |
1757 | { | |
1758 | case INTEGER_CST: | |
1759 | return true; | |
1760 | ||
1761 | case POLYNOMIAL_CHREC: | |
1f380314 SP |
1762 | return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST |
1763 | && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC | |
1764 | || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec))); | |
e7c705bb | 1765 | |
1f380314 SP |
1766 | CASE_CONVERT: |
1767 | return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0)); | |
e7c705bb SP |
1768 | |
1769 | default: | |
1770 | return false; | |
1771 | } | |
1772 | } |