Branch data Line data Source code
1 : : /* Chains of recurrences.
2 : : Copyright (C) 2003-2025 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 : : /* 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"
29 : : #include "backend.h"
30 : : #include "tree.h"
31 : : #include "gimple-expr.h"
32 : : #include "tree-pretty-print.h"
33 : : #include "fold-const.h"
34 : : #include "cfgloop.h"
35 : : #include "tree-ssa-loop-ivopts.h"
36 : : #include "tree-ssa-loop-niter.h"
37 : : #include "tree-chrec.h"
38 : : #include "gimple.h"
39 : : #include "tree-ssa-loop.h"
40 : : #include "dumpfile.h"
41 : : #include "tree-scalar-evolution.h"
42 : :
43 : : /* Extended folder for chrecs. */
44 : :
45 : : /* Fold the addition of two polynomial functions. */
46 : :
47 : : static inline tree
48 : 83390 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : : tree type,
50 : : tree poly0,
51 : : tree poly1)
52 : : {
53 : 83390 : tree left, right;
54 : 83390 : class loop *loop0 = get_chrec_loop (poly0);
55 : 83390 : class loop *loop1 = get_chrec_loop (poly1);
56 : 83390 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
57 : :
58 : 83390 : gcc_assert (poly0);
59 : 83390 : gcc_assert (poly1);
60 : 83390 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
61 : 83390 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
62 : 83390 : if (POINTER_TYPE_P (chrec_type (poly0)))
63 : 82 : gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
64 : : && useless_type_conversion_p (type, chrec_type (poly0)));
65 : : else
66 : 83308 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
67 : : && useless_type_conversion_p (type, chrec_type (poly1)));
68 : :
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. */
73 : 83390 : if (flow_loop_nested_p (loop0, loop1))
74 : : {
75 : 284 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
76 : 236 : return build_polynomial_chrec
77 : 236 : (CHREC_VARIABLE (poly1),
78 : 236 : chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
79 : 472 : CHREC_RIGHT (poly1));
80 : : else
81 : 48 : return build_polynomial_chrec
82 : 96 : (CHREC_VARIABLE (poly1),
83 : 48 : chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
84 : 48 : chrec_fold_multiply (type, CHREC_RIGHT (poly1),
85 : 48 : SCALAR_FLOAT_TYPE_P (type)
86 : 0 : ? build_real (type, dconstm1)
87 : 96 : : build_int_cst_type (type, -1)));
88 : : }
89 : :
90 : 83106 : if (flow_loop_nested_p (loop1, loop0))
91 : : {
92 : 602 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
93 : 562 : return build_polynomial_chrec
94 : 562 : (CHREC_VARIABLE (poly0),
95 : 562 : chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
96 : 1124 : CHREC_RIGHT (poly0));
97 : : else
98 : 40 : return build_polynomial_chrec
99 : 40 : (CHREC_VARIABLE (poly0),
100 : 40 : chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
101 : 80 : CHREC_RIGHT (poly0));
102 : : }
103 : :
104 : : /* This function should never be called for chrecs of loops that
105 : : do not belong to the same loop nest. */
106 : 82504 : if (loop0 != loop1)
107 : : {
108 : : /* It still can happen if we are not in loop-closed SSA form. */
109 : 32 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
110 : 32 : return chrec_dont_know;
111 : : }
112 : :
113 : 82472 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
114 : : {
115 : 28972 : left = chrec_fold_plus
116 : 28972 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 : 28972 : right = chrec_fold_plus
118 : 28972 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : : }
120 : : else
121 : : {
122 : 53500 : left = chrec_fold_minus
123 : 53500 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 : 53500 : right = chrec_fold_minus
125 : 53500 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : : }
127 : :
128 : 82472 : if (chrec_zerop (right))
129 : : return left;
130 : : else
131 : 30013 : return build_polynomial_chrec
132 : 30013 : (CHREC_VARIABLE (poly0), left, right);
133 : : }
134 : :
135 : :
136 : :
137 : : /* Fold the multiplication of two polynomial functions. */
138 : :
139 : : static inline tree
140 : 40371 : chrec_fold_multiply_poly_poly (tree type,
141 : : tree poly0,
142 : : tree poly1)
143 : : {
144 : 40371 : tree t0, t1, t2;
145 : 40371 : int var;
146 : 40371 : class loop *loop0 = get_chrec_loop (poly0);
147 : 40371 : class loop *loop1 = get_chrec_loop (poly1);
148 : :
149 : 40371 : gcc_assert (poly0);
150 : 40371 : gcc_assert (poly1);
151 : 40371 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
152 : 40371 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
153 : 40371 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
154 : : && useless_type_conversion_p (type, chrec_type (poly1)));
155 : :
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. */
159 : 40371 : if (flow_loop_nested_p (loop0, loop1))
160 : : /* poly0 is a constant wrt. poly1. */
161 : 0 : return build_polynomial_chrec
162 : 0 : (CHREC_VARIABLE (poly1),
163 : 0 : chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
164 : 0 : CHREC_RIGHT (poly1));
165 : :
166 : 40371 : if (flow_loop_nested_p (loop1, loop0))
167 : : /* poly1 is a constant wrt. poly0. */
168 : 0 : return build_polynomial_chrec
169 : 0 : (CHREC_VARIABLE (poly0),
170 : 0 : chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
171 : 0 : CHREC_RIGHT (poly0));
172 : :
173 : 40371 : if (loop0 != loop1)
174 : : {
175 : : /* It still can happen if we are not in loop-closed SSA form. */
176 : 0 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
177 : 0 : return chrec_dont_know;
178 : : }
179 : :
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. */
182 : :
183 : : /* "a*c". */
184 : 40371 : t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
185 : :
186 : : /* "a*d + b*c". */
187 : 40371 : t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
188 : 121113 : t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
189 : 40371 : CHREC_RIGHT (poly0),
190 : 40371 : CHREC_LEFT (poly1)));
191 : : /* "b*d". */
192 : 40371 : t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
193 : : /* "a*d + b*c + b*d". */
194 : 40371 : t1 = chrec_fold_plus (type, t1, t2);
195 : : /* "2*b*d". */
196 : 80742 : t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
197 : 33 : ? build_real (type, dconst2)
198 : 40338 : : build_int_cst (type, 2), t2);
199 : :
200 : 40371 : var = CHREC_VARIABLE (poly0);
201 : 40371 : return build_polynomial_chrec (var, t0,
202 : 40371 : build_polynomial_chrec (var, t1, t2));
203 : : }
204 : :
205 : : /* When the operands are automatically_generated_chrec_p, the fold has
206 : : to respect the semantics of the operands. */
207 : :
208 : : static inline tree
209 : 5183305 : chrec_fold_automatically_generated_operands (tree op0,
210 : : tree op1)
211 : : {
212 : 5183305 : if (op0 == chrec_dont_know
213 : 779469 : || op1 == chrec_dont_know)
214 : : return chrec_dont_know;
215 : :
216 : 0 : if (op0 == chrec_known
217 : 0 : || op1 == chrec_known)
218 : : return chrec_known;
219 : :
220 : 0 : if (op0 == chrec_not_analyzed_yet
221 : 0 : || op1 == chrec_not_analyzed_yet)
222 : 0 : return chrec_not_analyzed_yet;
223 : :
224 : : /* The default case produces a safe result. */
225 : : return chrec_dont_know;
226 : : }
227 : :
228 : : /* Fold the addition of two chrecs. */
229 : :
230 : : static tree
231 : 29070206 : chrec_fold_plus_1 (enum tree_code code, tree type,
232 : : tree op0, tree op1)
233 : : {
234 : 58140412 : if (automatically_generated_chrec_p (op0)
235 : 29070206 : || automatically_generated_chrec_p (op1))
236 : 0 : return chrec_fold_automatically_generated_operands (op0, op1);
237 : :
238 : 29070206 : switch (TREE_CODE (op0))
239 : : {
240 : 8884144 : case POLYNOMIAL_CHREC:
241 : 8884144 : gcc_checking_assert
242 : : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
243 : 8884144 : switch (TREE_CODE (op1))
244 : : {
245 : 83390 : case POLYNOMIAL_CHREC:
246 : 83390 : gcc_checking_assert
247 : : (!chrec_contains_symbols_defined_in_loop (op1,
248 : : CHREC_VARIABLE (op1)));
249 : 83390 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
250 : :
251 : 147266 : CASE_CONVERT:
252 : 147266 : if (tree_contains_chrecs (op1, NULL))
253 : : {
254 : : /* We can strip sign-conversions to signed by performing the
255 : : operation in unsigned. */
256 : 658 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
257 : 658 : if (INTEGRAL_TYPE_P (type)
258 : 658 : && INTEGRAL_TYPE_P (optype)
259 : 633 : && tree_nop_conversion_p (type, optype)
260 : 847 : && TYPE_UNSIGNED (optype))
261 : : {
262 : 106 : tree tem = chrec_convert (optype, op0, NULL);
263 : 106 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
264 : 24 : return chrec_convert (type,
265 : : chrec_fold_plus_1 (code, optype,
266 : : tem,
267 : 24 : TREE_OPERAND
268 : : (op1, 0)),
269 : 24 : NULL);
270 : : }
271 : 634 : return chrec_dont_know;
272 : : }
273 : : /* FALLTHRU */
274 : :
275 : 8800096 : default:
276 : 8800096 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
277 : 8101144 : return build_polynomial_chrec
278 : 8101144 : (CHREC_VARIABLE (op0),
279 : 8101144 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
280 : 16202288 : CHREC_RIGHT (op0));
281 : : else
282 : 698952 : return build_polynomial_chrec
283 : 698952 : (CHREC_VARIABLE (op0),
284 : 698952 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
285 : 1397904 : CHREC_RIGHT (op0));
286 : : }
287 : :
288 : 2644752 : CASE_CONVERT:
289 : 2644752 : if (tree_contains_chrecs (op0, NULL))
290 : : {
291 : : /* We can strip sign-conversions to signed by performing the
292 : : operation in unsigned. */
293 : 38776 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
294 : 38776 : if (INTEGRAL_TYPE_P (type)
295 : 37408 : && INTEGRAL_TYPE_P (optype)
296 : 33842 : && tree_nop_conversion_p (type, optype)
297 : 64138 : && TYPE_UNSIGNED (optype))
298 : 50656 : return chrec_convert (type,
299 : : chrec_fold_plus_1 (code, optype,
300 : 25328 : TREE_OPERAND (op0, 0),
301 : : chrec_convert (optype,
302 : : op1, NULL)),
303 : 25328 : NULL);
304 : 13448 : return chrec_dont_know;
305 : : }
306 : : /* FALLTHRU */
307 : :
308 : 20147286 : default:
309 : 20147286 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
310 : 20147286 : switch (TREE_CODE (op1))
311 : : {
312 : 2854619 : case POLYNOMIAL_CHREC:
313 : 2854619 : gcc_checking_assert
314 : : (!chrec_contains_symbols_defined_in_loop (op1,
315 : : CHREC_VARIABLE (op1)));
316 : 2854619 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
317 : 2794086 : return build_polynomial_chrec
318 : 2794086 : (CHREC_VARIABLE (op1),
319 : 2794086 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
320 : 5588172 : CHREC_RIGHT (op1));
321 : : else
322 : 60533 : return build_polynomial_chrec
323 : 121066 : (CHREC_VARIABLE (op1),
324 : 60533 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
325 : 60533 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
326 : 60533 : SCALAR_FLOAT_TYPE_P (type)
327 : 4 : ? build_real (type, dconstm1)
328 : 121062 : : build_int_cst_type (type, -1)));
329 : :
330 : 1976172 : CASE_CONVERT:
331 : 1976172 : if (tree_contains_chrecs (op1, NULL))
332 : : {
333 : : /* We can strip sign-conversions to signed by performing the
334 : : operation in unsigned. */
335 : 62487 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
336 : 62487 : if (INTEGRAL_TYPE_P (type)
337 : 16783 : && INTEGRAL_TYPE_P (optype)
338 : 16783 : && tree_nop_conversion_p (type, optype)
339 : 76215 : && TYPE_UNSIGNED (optype))
340 : 13728 : return chrec_convert (type,
341 : : chrec_fold_plus_1 (code, optype,
342 : : chrec_convert (optype,
343 : : op0,
344 : : NULL),
345 : 13728 : TREE_OPERAND (op1, 0)),
346 : 13728 : NULL);
347 : 48759 : return chrec_dont_know;
348 : : }
349 : : /* FALLTHRU */
350 : :
351 : 17230180 : default:
352 : 17230180 : {
353 : 17230180 : int size = 0;
354 : 17230180 : if ((tree_contains_chrecs (op0, &size)
355 : 17230180 : || tree_contains_chrecs (op1, &size))
356 : 17230180 : && size < param_scev_max_expr_size)
357 : 0 : return build2 (code, type, op0, op1);
358 : 17230180 : else if (size < param_scev_max_expr_size)
359 : : {
360 : 17230094 : if (code == POINTER_PLUS_EXPR)
361 : 3125501 : return fold_build_pointer_plus (fold_convert (type, op0),
362 : : op1);
363 : : else
364 : 14104593 : return fold_build2 (code, type,
365 : : fold_convert (type, op0),
366 : : fold_convert (type, op1));
367 : : }
368 : : else
369 : 86 : return chrec_dont_know;
370 : : }
371 : : }
372 : : }
373 : : }
374 : :
375 : : /* Fold the addition of two chrecs. */
376 : :
377 : : tree
378 : 33843654 : chrec_fold_plus (tree type,
379 : : tree op0,
380 : : tree op1)
381 : : {
382 : 33843654 : enum tree_code code;
383 : 65002564 : if (automatically_generated_chrec_p (op0)
384 : 33843654 : || automatically_generated_chrec_p (op1))
385 : 3230598 : return chrec_fold_automatically_generated_operands (op0, op1);
386 : :
387 : 30613056 : if (integer_zerop (op0))
388 : 3779328 : return chrec_convert (type, op1, NULL);
389 : 26833728 : if (integer_zerop (op1))
390 : 1680457 : return chrec_convert (type, op0, NULL);
391 : :
392 : 25153271 : if (POINTER_TYPE_P (type))
393 : : code = POINTER_PLUS_EXPR;
394 : : else
395 : 19389068 : code = PLUS_EXPR;
396 : :
397 : 25153271 : return chrec_fold_plus_1 (code, type, op0, op1);
398 : : }
399 : :
400 : : /* Fold the subtraction of two chrecs. */
401 : :
402 : : tree
403 : 4833145 : chrec_fold_minus (tree type,
404 : : tree op0,
405 : : tree op1)
406 : : {
407 : 9235575 : if (automatically_generated_chrec_p (op0)
408 : 4833145 : || automatically_generated_chrec_p (op1))
409 : 528231 : return chrec_fold_automatically_generated_operands (op0, op1);
410 : :
411 : 4304914 : if (integer_zerop (op1))
412 : : return op0;
413 : :
414 : 3877855 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
415 : : }
416 : :
417 : : /* Fold the multiplication of two chrecs. */
418 : :
419 : : tree
420 : 19843244 : chrec_fold_multiply (tree type,
421 : : tree op0,
422 : : tree op1)
423 : : {
424 : 19843535 : if (automatically_generated_chrec_p (op0)
425 : 18555158 : || automatically_generated_chrec_p (op1))
426 : 1424476 : return chrec_fold_automatically_generated_operands (op0, op1);
427 : :
428 : 18419059 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
429 : 14718682 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
430 : : std::swap (op0, op1);
431 : :
432 : 18419059 : switch (TREE_CODE (op0))
433 : : {
434 : 3878868 : case POLYNOMIAL_CHREC:
435 : 3878868 : gcc_checking_assert
436 : : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
437 : 3878868 : switch (TREE_CODE (op1))
438 : : {
439 : 40371 : case POLYNOMIAL_CHREC:
440 : 40371 : gcc_checking_assert
441 : : (!chrec_contains_symbols_defined_in_loop (op1,
442 : : CHREC_VARIABLE (op1)));
443 : 40371 : return chrec_fold_multiply_poly_poly (type, op0, op1);
444 : :
445 : 51481 : CASE_CONVERT:
446 : 51481 : if (tree_contains_chrecs (op1, NULL))
447 : : {
448 : : /* We can strip sign-conversions to signed by performing the
449 : : operation in unsigned. */
450 : 185 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
451 : 185 : if (INTEGRAL_TYPE_P (type)
452 : 185 : && INTEGRAL_TYPE_P (optype)
453 : 185 : && tree_nop_conversion_p (type, optype)
454 : 195 : && TYPE_UNSIGNED (optype))
455 : : {
456 : 10 : tree tem = chrec_convert (optype, op0, NULL);
457 : 10 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
458 : 10 : return chrec_convert (type,
459 : : chrec_fold_multiply (optype, tem,
460 : 10 : TREE_OPERAND
461 : : (op1, 0)),
462 : 10 : NULL);
463 : : }
464 : 175 : return chrec_dont_know;
465 : : }
466 : : /* FALLTHRU */
467 : :
468 : 3838312 : default:
469 : 3838312 : if (integer_onep (op1))
470 : : return op0;
471 : 3837861 : if (integer_zerop (op1))
472 : 410 : return build_int_cst (type, 0);
473 : :
474 : : /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
475 : : same sign or CHREC_LEFT is zero then folding the multiply into
476 : : the addition does not have the same behavior on overflow.
477 : : Using unsigned arithmetic in that case causes too many performance
478 : : regressions, but catch the constant case where the multiplication
479 : : of the step overflows. */
480 : 3837451 : if (INTEGRAL_TYPE_P (type)
481 : 3837260 : && TYPE_OVERFLOW_UNDEFINED (type)
482 : 964851 : && !integer_zerop (CHREC_LEFT (op0))
483 : 546319 : && TREE_CODE (op1) == INTEGER_CST
484 : 4225959 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
485 : : {
486 : 302718 : wi::overflow_type ovf = wi::OVF_NONE;
487 : 302718 : wide_int res
488 : 302718 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
489 : 605436 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
490 : 302718 : if (ovf != wi::OVF_NONE)
491 : : {
492 : 16 : tree utype = unsigned_type_for (type);
493 : 16 : tree uop1 = chrec_convert_rhs (utype, op1);
494 : 16 : tree uleft0 = chrec_convert_rhs (utype, CHREC_LEFT (op0));
495 : 16 : tree uright0 = chrec_convert_rhs (utype, CHREC_RIGHT (op0));
496 : 16 : tree left = chrec_fold_multiply (utype, uleft0, uop1);
497 : 16 : tree right = chrec_fold_multiply (utype, uright0, uop1);
498 : 16 : tree tem = build_polynomial_chrec (CHREC_VARIABLE (op0),
499 : : left, right);
500 : 16 : return chrec_convert_rhs (type, tem);
501 : : }
502 : 302718 : }
503 : 3837435 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
504 : 3837435 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
505 : 3837435 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
506 : : }
507 : :
508 : 4414754 : CASE_CONVERT:
509 : 4414754 : if (tree_contains_chrecs (op0, NULL))
510 : : {
511 : : /* We can strip sign-conversions to signed by performing the
512 : : operation in unsigned. */
513 : 47667 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
514 : 47667 : if (INTEGRAL_TYPE_P (type)
515 : 47667 : && INTEGRAL_TYPE_P (optype)
516 : 47667 : && tree_nop_conversion_p (type, optype)
517 : 58029 : && TYPE_UNSIGNED (optype))
518 : 20686 : return chrec_convert (type,
519 : : chrec_fold_multiply (optype,
520 : 10343 : TREE_OPERAND (op0, 0),
521 : : chrec_convert (optype,
522 : : op1,
523 : : NULL)),
524 : 10343 : NULL);
525 : 37324 : return chrec_dont_know;
526 : : }
527 : : /* FALLTHRU */
528 : :
529 : 14492524 : default:
530 : 14492524 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
531 : 14492524 : if (integer_onep (op0))
532 : : return op1;
533 : :
534 : 9901638 : if (integer_zerop (op0))
535 : 2161768 : return build_int_cst (type, 0);
536 : :
537 : 7739870 : switch (TREE_CODE (op1))
538 : : {
539 : 0 : case POLYNOMIAL_CHREC:
540 : 0 : gcc_unreachable ();
541 : :
542 : 724401 : CASE_CONVERT:
543 : 724401 : if (tree_contains_chrecs (op1, NULL))
544 : : return chrec_fold_multiply (type, op1, op0);
545 : : /* FALLTHRU */
546 : :
547 : 7739579 : default:
548 : 7739579 : if (integer_onep (op1))
549 : : return op0;
550 : 7676060 : if (integer_zerop (op1))
551 : 2027 : return build_int_cst (type, 0);
552 : 7674033 : return fold_build2 (MULT_EXPR, type, op0, op1);
553 : : }
554 : : }
555 : : }
556 : :
557 : :
558 : :
559 : : /* Operations. */
560 : :
561 : : /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
562 : : calculation overflows, otherwise return C(n,k) with type TYPE. */
563 : :
564 : : static tree
565 : 9484 : tree_fold_binomial (tree type, tree n, unsigned int k)
566 : : {
567 : 9484 : wi::overflow_type overflow;
568 : 9484 : unsigned int i;
569 : :
570 : : /* Handle the most frequent cases. */
571 : 9484 : if (k == 0)
572 : 3144 : return build_int_cst (type, 1);
573 : 6340 : if (k == 1)
574 : 3144 : return fold_convert (type, n);
575 : :
576 : 3196 : widest_int num = wi::to_widest (n);
577 : :
578 : : /* Check that k <= n. */
579 : 3196 : if (wi::ltu_p (num, k))
580 : : return NULL_TREE;
581 : :
582 : : /* Denominator = 2. */
583 : 3160 : widest_int denom = 2;
584 : :
585 : : /* Index = Numerator-1. */
586 : 3160 : widest_int idx = num - 1;
587 : :
588 : : /* Numerator = Numerator*Index = n*(n-1). */
589 : 3160 : num = wi::smul (num, idx, &overflow);
590 : 3160 : if (overflow)
591 : : return NULL_TREE;
592 : :
593 : 3166 : for (i = 3; i <= k; i++)
594 : : {
595 : : /* Index--. */
596 : 6 : --idx;
597 : :
598 : : /* Numerator *= Index. */
599 : 6 : num = wi::smul (num, idx, &overflow);
600 : 6 : if (overflow)
601 : : return NULL_TREE;
602 : :
603 : : /* Denominator *= i. */
604 : 6 : denom *= i;
605 : : }
606 : :
607 : : /* Result = Numerator / Denominator. */
608 : 3160 : num = wi::udiv_trunc (num, denom);
609 : 3160 : if (! wi::fits_to_tree_p (num, type))
610 : : return NULL_TREE;
611 : 3150 : return wide_int_to_tree (type, num);
612 : 6356 : }
613 : :
614 : : /* Helper function. Use the Newton's interpolating formula for
615 : : evaluating the value of the evolution function.
616 : : The result may be in an unsigned type of CHREC. */
617 : :
618 : : static tree
619 : 9585 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
620 : : {
621 : 9585 : tree arg0, arg1, binomial_n_k;
622 : 9585 : tree type = TREE_TYPE (chrec);
623 : 9585 : class loop *var_loop = get_loop (cfun, var);
624 : :
625 : 9585 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
626 : 9585 : && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
627 : 0 : chrec = CHREC_LEFT (chrec);
628 : :
629 : : /* The formula associates the expression and thus we have to make
630 : : sure to not introduce undefined overflow. */
631 : 9585 : tree ctype = type;
632 : 9585 : if (INTEGRAL_TYPE_P (type)
633 : 9585 : && ! TYPE_OVERFLOW_WRAPS (type))
634 : 9408 : ctype = unsigned_type_for (type);
635 : :
636 : 9585 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
637 : 9585 : && CHREC_VARIABLE (chrec) == var)
638 : : {
639 : 6395 : arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
640 : 6395 : if (arg1 == chrec_dont_know)
641 : : return chrec_dont_know;
642 : 6294 : binomial_n_k = tree_fold_binomial (ctype, n, k);
643 : 6294 : if (!binomial_n_k)
644 : 0 : return chrec_dont_know;
645 : 6294 : tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
646 : 6294 : arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
647 : 6294 : return chrec_fold_plus (ctype, arg0, arg1);
648 : : }
649 : :
650 : 3190 : binomial_n_k = tree_fold_binomial (ctype, n, k);
651 : 3190 : if (!binomial_n_k)
652 : 46 : return chrec_dont_know;
653 : :
654 : 3144 : return fold_build2 (MULT_EXPR, ctype,
655 : : chrec_convert (ctype, chrec, NULL), binomial_n_k);
656 : : }
657 : :
658 : : /* Evaluates "CHREC (X)" when the varying variable is VAR.
659 : : Example: Given the following parameters,
660 : :
661 : : var = 1
662 : : chrec = {3, +, 4}_1
663 : : x = 10
664 : :
665 : : The result is given by the Newton's interpolating formula:
666 : : 3 * \binom{10}{0} + 4 * \binom{10}{1}.
667 : : */
668 : :
669 : : tree
670 : 821082 : chrec_apply (unsigned var,
671 : : tree chrec,
672 : : tree x)
673 : : {
674 : 821082 : tree type = chrec_type (chrec);
675 : 821082 : tree res = chrec_dont_know;
676 : :
677 : 1642164 : if (automatically_generated_chrec_p (chrec)
678 : 919075 : || automatically_generated_chrec_p (x)
679 : :
680 : : /* When the symbols are defined in an outer loop, it is possible
681 : : to symbolically compute the apply, since the symbols are
682 : : constants with respect to the varying loop. */
683 : 821082 : || chrec_contains_symbols_defined_in_loop (chrec, var))
684 : 97993 : return chrec_dont_know;
685 : :
686 : 723089 : if (dump_file && (dump_flags & TDF_SCEV))
687 : 0 : fprintf (dump_file, "(chrec_apply \n");
688 : :
689 : 723089 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
690 : 124 : x = build_real_from_int_cst (type, x);
691 : :
692 : 723089 : switch (TREE_CODE (chrec))
693 : : {
694 : 721816 : case POLYNOMIAL_CHREC:
695 : 721816 : if (evolution_function_is_affine_p (chrec))
696 : : {
697 : 717561 : tree chrecr = CHREC_RIGHT (chrec);
698 : 717561 : tree chrecl = CHREC_LEFT (chrec);
699 : 717561 : if (CHREC_VARIABLE (chrec) != var)
700 : 481 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
701 : : chrec_apply (var, chrecl, x),
702 : : chrec_apply (var, chrecr, x));
703 : :
704 : : /* "{a, +, a}" (x-1) -> "a*x". */
705 : 717080 : else if (operand_equal_p (chrecl, chrecr)
706 : 123742 : && TREE_CODE (x) == PLUS_EXPR
707 : 6093 : && integer_all_onesp (TREE_OPERAND (x, 1))
708 : 5883 : && !POINTER_TYPE_P (type)
709 : 722952 : && TYPE_PRECISION (TREE_TYPE (x))
710 : 5872 : >= TYPE_PRECISION (type))
711 : : {
712 : : /* We know the number of iterations can't be negative. */
713 : 4196 : res = build_int_cst (TREE_TYPE (x), 1);
714 : 4196 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
715 : 4196 : res = chrec_convert_rhs (type, res, NULL);
716 : 4196 : res = chrec_fold_multiply (type, chrecr, res);
717 : : }
718 : : /* "{a, +, b} (x)" -> "a + b*x". */
719 : : else
720 : : {
721 : : /* The overall increment might not fit in a signed type so
722 : : use an unsigned computation to get at the final value
723 : : and avoid undefined signed overflow. */
724 : 712884 : tree utype = TREE_TYPE (chrecr);
725 : 712884 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
726 : 634275 : utype = unsigned_type_for (TREE_TYPE (chrecr));
727 : 712884 : res = chrec_convert_rhs (utype, x, NULL);
728 : 712884 : res = chrec_fold_multiply (utype,
729 : : chrec_convert (utype, chrecr, NULL),
730 : : res);
731 : : /* When the resulting increment fits the original type
732 : : do the increment in it. */
733 : 712884 : if (TREE_CODE (res) == INTEGER_CST
734 : 712884 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
735 : : {
736 : 378615 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
737 : 378615 : res = chrec_fold_plus (type, chrecl, res);
738 : : }
739 : : else
740 : : {
741 : 334269 : res = chrec_fold_plus (utype,
742 : : chrec_convert (utype, chrecl, NULL),
743 : : res);
744 : 334269 : res = chrec_convert (type, res, NULL);
745 : : }
746 : : }
747 : : }
748 : 4255 : else if (TREE_CODE (x) == INTEGER_CST
749 : 4255 : && tree_int_cst_sgn (x) == 1)
750 : : /* testsuite/.../ssa-chrec-38.c. */
751 : 3190 : res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
752 : : else
753 : 1065 : res = chrec_dont_know;
754 : : break;
755 : :
756 : 222 : CASE_CONVERT:
757 : 222 : res = chrec_convert (TREE_TYPE (chrec),
758 : 222 : chrec_apply (var, TREE_OPERAND (chrec, 0), x),
759 : : NULL);
760 : 222 : break;
761 : :
762 : : default:
763 : : res = chrec;
764 : : break;
765 : : }
766 : :
767 : 723089 : if (dump_file && (dump_flags & TDF_SCEV))
768 : : {
769 : 0 : fprintf (dump_file, " (varying_loop = %d", var);
770 : 0 : fprintf (dump_file, ")\n (chrec = ");
771 : 0 : print_generic_expr (dump_file, chrec);
772 : 0 : fprintf (dump_file, ")\n (x = ");
773 : 0 : print_generic_expr (dump_file, x);
774 : 0 : fprintf (dump_file, ")\n (res = ");
775 : 0 : print_generic_expr (dump_file, res);
776 : 0 : fprintf (dump_file, "))\n");
777 : : }
778 : :
779 : : return res;
780 : : }
781 : :
782 : : /* For a given CHREC and an induction variable map IV_MAP that maps
783 : : (loop->num, expr) for every loop number of the current_loops an
784 : : expression, calls chrec_apply when the expression is not NULL. */
785 : :
786 : : tree
787 : 844 : chrec_apply_map (tree chrec, vec<tree> iv_map)
788 : : {
789 : 844 : int i;
790 : 844 : tree expr;
791 : :
792 : 8916 : FOR_EACH_VEC_ELT (iv_map, i, expr)
793 : 8072 : if (expr)
794 : 1482 : chrec = chrec_apply (i, chrec, expr);
795 : :
796 : 844 : return chrec;
797 : : }
798 : :
799 : : /* Replaces the initial condition in CHREC with INIT_COND. */
800 : :
801 : : tree
802 : 1901668 : chrec_replace_initial_condition (tree chrec,
803 : : tree init_cond)
804 : : {
805 : 1901668 : if (automatically_generated_chrec_p (chrec))
806 : : return chrec;
807 : :
808 : 1901668 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
809 : :
810 : 1901668 : switch (TREE_CODE (chrec))
811 : : {
812 : 960515 : case POLYNOMIAL_CHREC:
813 : 960515 : return build_polynomial_chrec
814 : 960515 : (CHREC_VARIABLE (chrec),
815 : 960515 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
816 : 1921030 : CHREC_RIGHT (chrec));
817 : :
818 : : default:
819 : : return init_cond;
820 : : }
821 : : }
822 : :
823 : : /* Returns the initial condition of a given CHREC. */
824 : :
825 : : tree
826 : 10335939 : initial_condition (tree chrec)
827 : : {
828 : 16951794 : if (automatically_generated_chrec_p (chrec))
829 : : return chrec;
830 : :
831 : 15814291 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
832 : 6615855 : return initial_condition (CHREC_LEFT (chrec));
833 : : else
834 : : return chrec;
835 : : }
836 : :
837 : : /* Returns a univariate function that represents the evolution in
838 : : LOOP_NUM. Mask the evolution of any other loop. */
839 : :
840 : : tree
841 : 44198635 : hide_evolution_in_other_loops_than_loop (tree chrec,
842 : : unsigned loop_num)
843 : : {
844 : 44200332 : class loop *loop = get_loop (cfun, loop_num), *chloop;
845 : 44200332 : if (automatically_generated_chrec_p (chrec))
846 : : return chrec;
847 : :
848 : 44200332 : switch (TREE_CODE (chrec))
849 : : {
850 : 2357780 : case POLYNOMIAL_CHREC:
851 : 2357780 : chloop = get_chrec_loop (chrec);
852 : :
853 : 2357780 : if (chloop == loop)
854 : 1937813 : return build_polynomial_chrec
855 : 1937813 : (loop_num,
856 : 1937813 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
857 : : loop_num),
858 : 3875626 : CHREC_RIGHT (chrec));
859 : :
860 : 419967 : else if (flow_loop_nested_p (chloop, loop))
861 : : /* There is no evolution in this loop. */
862 : 418270 : return initial_condition (chrec);
863 : :
864 : 1697 : else if (flow_loop_nested_p (loop, chloop))
865 : 1697 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
866 : 1697 : loop_num);
867 : :
868 : : else
869 : 0 : return chrec_dont_know;
870 : :
871 : : default:
872 : : return chrec;
873 : : }
874 : : }
875 : :
876 : : /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
877 : : true, otherwise returns the initial condition in LOOP_NUM. */
878 : :
879 : : static tree
880 : 38278826 : chrec_component_in_loop_num (tree chrec,
881 : : unsigned loop_num,
882 : : bool right)
883 : : {
884 : 38278826 : tree component;
885 : 38278826 : class loop *loop = get_loop (cfun, loop_num), *chloop;
886 : :
887 : 38278826 : if (automatically_generated_chrec_p (chrec))
888 : : return chrec;
889 : :
890 : 37141323 : switch (TREE_CODE (chrec))
891 : : {
892 : 31818619 : case POLYNOMIAL_CHREC:
893 : 31818619 : chloop = get_chrec_loop (chrec);
894 : :
895 : 31818619 : if (chloop == loop)
896 : : {
897 : 30582158 : if (right)
898 : 16307188 : component = CHREC_RIGHT (chrec);
899 : : else
900 : 14274970 : component = CHREC_LEFT (chrec);
901 : :
902 : 30582158 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
903 : 30582158 : || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
904 : : return component;
905 : :
906 : : else
907 : 0 : return build_polynomial_chrec
908 : 0 : (loop_num,
909 : 0 : chrec_component_in_loop_num (CHREC_LEFT (chrec),
910 : : loop_num,
911 : : right),
912 : 0 : component);
913 : : }
914 : :
915 : 1236461 : else if (flow_loop_nested_p (chloop, loop))
916 : : /* There is no evolution part in this loop. */
917 : : return NULL_TREE;
918 : :
919 : : else
920 : : {
921 : 1236461 : gcc_assert (flow_loop_nested_p (loop, chloop));
922 : 1236461 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
923 : : loop_num,
924 : 1236461 : right);
925 : : }
926 : :
927 : 5322704 : default:
928 : 5322704 : if (right)
929 : : return NULL_TREE;
930 : : else
931 : : return chrec;
932 : : }
933 : : }
934 : :
935 : : /* Returns the evolution part in LOOP_NUM. Example: the call
936 : : evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
937 : : {1, +, 2}_1 */
938 : :
939 : : tree
940 : 21938814 : evolution_part_in_loop_num (tree chrec,
941 : : unsigned loop_num)
942 : : {
943 : 21938814 : return chrec_component_in_loop_num (chrec, loop_num, true);
944 : : }
945 : :
946 : : /* Returns the initial condition in LOOP_NUM. Example: the call
947 : : initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
948 : : {0, +, 1}_1 */
949 : :
950 : : tree
951 : 15103551 : initial_condition_in_loop_num (tree chrec,
952 : : unsigned loop_num)
953 : : {
954 : 15103551 : return chrec_component_in_loop_num (chrec, loop_num, false);
955 : : }
956 : :
957 : : /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
958 : : This function is essentially used for setting the evolution to
959 : : chrec_dont_know, for example after having determined that it is
960 : : impossible to say how many times a loop will execute. */
961 : :
962 : : tree
963 : 0 : reset_evolution_in_loop (unsigned loop_num,
964 : : tree chrec,
965 : : tree new_evol)
966 : : {
967 : 0 : class loop *loop = get_loop (cfun, loop_num);
968 : :
969 : 0 : if (POINTER_TYPE_P (chrec_type (chrec)))
970 : 0 : gcc_assert (ptrofftype_p (chrec_type (new_evol)));
971 : : else
972 : 0 : gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
973 : :
974 : 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
975 : 0 : && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
976 : : {
977 : 0 : tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
978 : : new_evol);
979 : 0 : tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
980 : : new_evol);
981 : 0 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
982 : : }
983 : :
984 : 0 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
985 : 0 : && CHREC_VARIABLE (chrec) == loop_num)
986 : 0 : chrec = CHREC_LEFT (chrec);
987 : :
988 : 0 : return build_polynomial_chrec (loop_num, chrec, new_evol);
989 : : }
990 : :
991 : : /* Merges two evolution functions that were found by following two
992 : : alternate paths of a conditional expression. */
993 : :
994 : : tree
995 : 14932337 : chrec_merge (tree chrec1,
996 : : tree chrec2)
997 : : {
998 : 14932337 : if (chrec1 == chrec_dont_know
999 : 14932337 : || chrec2 == chrec_dont_know)
1000 : : return chrec_dont_know;
1001 : :
1002 : 12616959 : if (chrec1 == chrec_known
1003 : 12616959 : || chrec2 == chrec_known)
1004 : : return chrec_known;
1005 : :
1006 : 12616959 : if (chrec1 == chrec_not_analyzed_yet)
1007 : : return chrec2;
1008 : 2636333 : if (chrec2 == chrec_not_analyzed_yet)
1009 : : return chrec1;
1010 : :
1011 : 2636333 : if (eq_evolutions_p (chrec1, chrec2))
1012 : : return chrec1;
1013 : :
1014 : 2049767 : return chrec_dont_know;
1015 : : }
1016 : :
1017 : :
1018 : :
1019 : : /* Observers. */
1020 : :
1021 : : /* Helper function for is_multivariate_chrec. */
1022 : :
1023 : : static bool
1024 : 0 : is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
1025 : : {
1026 : 0 : if (chrec == NULL_TREE)
1027 : : return false;
1028 : :
1029 : 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1030 : : {
1031 : 0 : if (CHREC_VARIABLE (chrec) != rec_var)
1032 : : return true;
1033 : : else
1034 : 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
1035 : 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
1036 : : }
1037 : : else
1038 : : return false;
1039 : : }
1040 : :
1041 : : /* Determine whether the given chrec is multivariate or not. */
1042 : :
1043 : : bool
1044 : 0 : is_multivariate_chrec (const_tree chrec)
1045 : : {
1046 : 0 : if (chrec == NULL_TREE)
1047 : : return false;
1048 : :
1049 : 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1050 : 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
1051 : 0 : CHREC_VARIABLE (chrec))
1052 : 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
1053 : 0 : CHREC_VARIABLE (chrec)));
1054 : : else
1055 : : return false;
1056 : : }
1057 : :
1058 : : /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
1059 : : NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
1060 : :
1061 : : static bool
1062 : 28347950 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1063 : : class loop *loop)
1064 : : {
1065 : 28347950 : int i, n;
1066 : :
1067 : 28347950 : if (chrec == NULL_TREE)
1068 : : return false;
1069 : :
1070 : 28347950 : if (TREE_CODE (chrec) == SSA_NAME
1071 : : || VAR_P (chrec)
1072 : : || TREE_CODE (chrec) == POLY_INT_CST
1073 : : || TREE_CODE (chrec) == PARM_DECL
1074 : : || TREE_CODE (chrec) == FUNCTION_DECL
1075 : : || TREE_CODE (chrec) == LABEL_DECL
1076 : : || TREE_CODE (chrec) == RESULT_DECL
1077 : : || TREE_CODE (chrec) == FIELD_DECL)
1078 : : return true;
1079 : :
1080 : 23255816 : if (loop != NULL
1081 : 486 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1082 : 23255980 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1083 : : return true;
1084 : :
1085 : 23255816 : if (visited.add (chrec))
1086 : : return false;
1087 : :
1088 : 22686619 : n = TREE_OPERAND_LENGTH (chrec);
1089 : 56174861 : for (i = 0; i < n; i++)
1090 : 14345428 : if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
1091 : : return true;
1092 : : return false;
1093 : : }
1094 : :
1095 : : /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
1096 : : CHREC contains any chrec which is invariant wrto the loop (nest), in other
1097 : : words, chrec defined by outer loops of loop, so from LOOP's point of view,
1098 : : the chrec is considered as a SYMBOL. */
1099 : :
1100 : : bool
1101 : 14002522 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1102 : : {
1103 : 14002522 : hash_set<const_tree> visited;
1104 : 14002522 : return chrec_contains_symbols (chrec, visited, loop);
1105 : 14002522 : }
1106 : :
1107 : : /* Return true when CHREC contains symbolic names defined in
1108 : : LOOP_NB. */
1109 : :
1110 : : static bool
1111 : 312122603 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1112 : : hash_set<const_tree> &visited)
1113 : : {
1114 : 312122603 : int i, n;
1115 : :
1116 : 312122603 : if (chrec == NULL_TREE)
1117 : : return false;
1118 : :
1119 : 312089065 : if (is_gimple_min_invariant (chrec))
1120 : : return false;
1121 : :
1122 : 185391088 : if (TREE_CODE (chrec) == SSA_NAME)
1123 : : {
1124 : 67529087 : gimple *def;
1125 : 67529087 : loop_p def_loop, loop;
1126 : :
1127 : 67529087 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1128 : : return false;
1129 : :
1130 : 63455256 : def = SSA_NAME_DEF_STMT (chrec);
1131 : 63455256 : def_loop = loop_containing_stmt (def);
1132 : 63455256 : loop = get_loop (cfun, loop_nb);
1133 : :
1134 : 63455256 : if (def_loop == NULL)
1135 : : return false;
1136 : :
1137 : 63455256 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1138 : 4332268 : return true;
1139 : :
1140 : : return false;
1141 : : }
1142 : :
1143 : 117862001 : if (visited.add (chrec))
1144 : : return false;
1145 : :
1146 : 117825309 : n = TREE_OPERAND_LENGTH (chrec);
1147 : 431069893 : for (i = 0; i < n; i++)
1148 : 196650523 : if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1149 : : loop_nb, visited))
1150 : : return true;
1151 : : return false;
1152 : : }
1153 : :
1154 : : /* Return true when CHREC contains symbolic names defined in
1155 : : LOOP_NB. */
1156 : :
1157 : : bool
1158 : 115472080 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1159 : : {
1160 : 115472080 : hash_set<const_tree> visited;
1161 : 115472080 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1162 : 115472080 : }
1163 : :
1164 : : /* Determines whether the chrec contains undetermined coefficients. */
1165 : :
1166 : : static bool
1167 : 204400903 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1168 : : {
1169 : 204400903 : int i, n;
1170 : :
1171 : 204400903 : if (chrec == chrec_dont_know)
1172 : : return true;
1173 : :
1174 : 183509184 : if (chrec == NULL_TREE)
1175 : : return false;
1176 : :
1177 : 183223449 : if (visited.add (chrec))
1178 : : return false;
1179 : :
1180 : 171325080 : n = TREE_OPERAND_LENGTH (chrec);
1181 : 453369754 : for (i = 0; i < n; i++)
1182 : 110720389 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1183 : : return true;
1184 : : return false;
1185 : : }
1186 : :
1187 : : bool
1188 : 93680514 : chrec_contains_undetermined (const_tree chrec)
1189 : : {
1190 : 93680514 : hash_set<const_tree> visited;
1191 : 93680514 : return chrec_contains_undetermined (chrec, visited);
1192 : 93680514 : }
1193 : :
1194 : : /* Determines whether the tree EXPR contains chrecs, and increment
1195 : : SIZE if it is not a NULL pointer by an estimation of the depth of
1196 : : the tree. */
1197 : :
1198 : : static bool
1199 : 402226431 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1200 : : {
1201 : 402226431 : int i, n;
1202 : :
1203 : 402226431 : if (expr == NULL_TREE)
1204 : : return false;
1205 : :
1206 : 401627704 : if (size)
1207 : 73287293 : (*size)++;
1208 : :
1209 : 401961014 : if (tree_is_chrec (expr))
1210 : : return true;
1211 : :
1212 : 380734068 : if (visited.add (expr))
1213 : : return false;
1214 : :
1215 : 378512974 : n = TREE_OPERAND_LENGTH (expr);
1216 : 952142847 : for (i = 0; i < n; i++)
1217 : 195378525 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1218 : : return true;
1219 : : return false;
1220 : : }
1221 : :
1222 : : bool
1223 : 206847906 : tree_contains_chrecs (const_tree expr, int *size)
1224 : : {
1225 : 206847906 : hash_set<const_tree> visited;
1226 : 206847906 : return tree_contains_chrecs (expr, size, visited);
1227 : 206847906 : }
1228 : :
1229 : :
1230 : : /* Recursive helper function. */
1231 : :
1232 : : static bool
1233 : 52822414 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1234 : : {
1235 : 105644828 : if (evolution_function_is_constant_p (chrec))
1236 : : return true;
1237 : :
1238 : 10821249 : if (TREE_CODE (chrec) == SSA_NAME
1239 : 10821249 : && (loopnum == 0
1240 : 2156228 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1241 : 2135650 : return true;
1242 : :
1243 : 8685599 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1244 : : {
1245 : 6872814 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1246 : 131005 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1247 : 131005 : get_chrec_loop (chrec))
1248 : 3061 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1249 : : loopnum)
1250 : 6875875 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1251 : : loopnum))
1252 : 6869753 : return false;
1253 : : return true;
1254 : : }
1255 : :
1256 : 1812785 : switch (TREE_OPERAND_LENGTH (chrec))
1257 : : {
1258 : 1050511 : case 2:
1259 : 1050511 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1260 : : loopnum))
1261 : : return false;
1262 : : /* FALLTHRU */
1263 : :
1264 : 1635707 : case 1:
1265 : 1635707 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1266 : : loopnum))
1267 : : return false;
1268 : : return true;
1269 : :
1270 : : default:
1271 : : return false;
1272 : : }
1273 : : }
1274 : :
1275 : : /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1276 : :
1277 : : bool
1278 : 36101562 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1279 : : {
1280 : 36101562 : return evolution_function_is_invariant_rec_p (chrec, loopnum);
1281 : : }
1282 : :
1283 : : /* Determine whether the given tree is an affine multivariate
1284 : : evolution. */
1285 : :
1286 : : bool
1287 : 7946400 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1288 : : {
1289 : 7946400 : if (chrec == NULL_TREE)
1290 : : return false;
1291 : :
1292 : 7946400 : switch (TREE_CODE (chrec))
1293 : : {
1294 : 7014256 : case POLYNOMIAL_CHREC:
1295 : 7014256 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1296 : : {
1297 : 6913655 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1298 : : return true;
1299 : : else
1300 : : {
1301 : 168 : if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1302 : 168 : && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1303 : 168 : != CHREC_VARIABLE (chrec)
1304 : 168 : && evolution_function_is_affine_multivariate_p
1305 : 0 : (CHREC_RIGHT (chrec), loopnum))
1306 : : return true;
1307 : : else
1308 : 168 : return false;
1309 : : }
1310 : : }
1311 : : else
1312 : : {
1313 : 100601 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1314 : 100601 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1315 : 100578 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1316 : 201179 : && evolution_function_is_affine_multivariate_p
1317 : 100578 : (CHREC_LEFT (chrec), loopnum))
1318 : : return true;
1319 : : else
1320 : 23 : return false;
1321 : : }
1322 : :
1323 : : default:
1324 : : return false;
1325 : : }
1326 : : }
1327 : :
1328 : : /* Determine whether the given tree is a function in zero or one
1329 : : variables with respect to loop specified by LOOPNUM. Note only positive
1330 : : LOOPNUM stands for a real loop. */
1331 : :
1332 : : bool
1333 : 1834910 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1334 : : {
1335 : 1834910 : if (chrec == NULL_TREE)
1336 : : return true;
1337 : :
1338 : 1834910 : tree sub_chrec;
1339 : 1834910 : switch (TREE_CODE (chrec))
1340 : : {
1341 : 1834907 : case POLYNOMIAL_CHREC:
1342 : 1834907 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1343 : : {
1344 : 30747 : case POLYNOMIAL_CHREC:
1345 : 30747 : sub_chrec = CHREC_LEFT (chrec);
1346 : 30747 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1347 : 30747 : && (loopnum <= 0
1348 : 4811 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1349 : 18 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1350 : 18 : get_chrec_loop (sub_chrec))))
1351 : 30735 : return false;
1352 : 12 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1353 : : return false;
1354 : : break;
1355 : :
1356 : 1804160 : default:
1357 : 1804160 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1358 : : return false;
1359 : : break;
1360 : : }
1361 : :
1362 : 1804172 : switch (TREE_CODE (CHREC_RIGHT (chrec)))
1363 : : {
1364 : 0 : case POLYNOMIAL_CHREC:
1365 : 0 : sub_chrec = CHREC_RIGHT (chrec);
1366 : 0 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1367 : 0 : && (loopnum <= 0
1368 : 0 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1369 : 0 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1370 : 0 : get_chrec_loop (sub_chrec))))
1371 : 0 : return false;
1372 : 0 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1373 : : return false;
1374 : : break;
1375 : :
1376 : 1804172 : default:
1377 : 1804172 : if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1378 : : return false;
1379 : : break;
1380 : : }
1381 : : return true;
1382 : :
1383 : : default:
1384 : : return true;
1385 : : }
1386 : : }
1387 : :
1388 : : /* Returns the number of variables of CHREC. Example: the call
1389 : : nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1390 : :
1391 : : unsigned
1392 : 1748114 : nb_vars_in_chrec (tree chrec)
1393 : : {
1394 : 3496228 : if (chrec == NULL_TREE)
1395 : : return 0;
1396 : :
1397 : 3496228 : switch (TREE_CODE (chrec))
1398 : : {
1399 : 1748114 : case POLYNOMIAL_CHREC:
1400 : 1748114 : return 1 + nb_vars_in_chrec
1401 : 1748114 : (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1402 : :
1403 : : default:
1404 : : return 0;
1405 : : }
1406 : : }
1407 : :
1408 : : /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1409 : : the scev corresponds to. AT_STMT is the statement at that the scev is
1410 : : evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1411 : : that the rules for overflow of the given language apply (e.g., that signed
1412 : : arithmetics in C does not overflow) -- i.e., to use them to avoid
1413 : : unnecessary tests, but also to enforce that the result follows them.
1414 : : FROM is the source variable converted if it's not NULL. Returns true if
1415 : : the conversion succeeded, false otherwise. */
1416 : :
1417 : : bool
1418 : 6722384 : convert_affine_scev (class loop *loop, tree type,
1419 : : tree *base, tree *step, gimple *at_stmt,
1420 : : bool use_overflow_semantics, tree from)
1421 : : {
1422 : 6722384 : tree ct = TREE_TYPE (*step);
1423 : 6722384 : bool enforce_overflow_semantics;
1424 : 6722384 : bool must_check_src_overflow, must_check_rslt_overflow;
1425 : 6722384 : tree new_base, new_step;
1426 : 6722384 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1427 : :
1428 : : /* In general,
1429 : : (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1430 : : but we must check some assumptions.
1431 : :
1432 : : 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1433 : : of CT is smaller than the precision of TYPE. For example, when we
1434 : : cast unsigned char [254, +, 1] to unsigned, the values on left side
1435 : : are 254, 255, 0, 1, ..., but those on the right side are
1436 : : 254, 255, 256, 257, ...
1437 : : 2) In case that we must also preserve the fact that signed ivs do not
1438 : : overflow, we must additionally check that the new iv does not wrap.
1439 : : For example, unsigned char [125, +, 1] casted to signed char could
1440 : : become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1441 : : which would confuse optimizers that assume that this does not
1442 : : happen. */
1443 : 6722384 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1444 : :
1445 : 15228000 : enforce_overflow_semantics = (use_overflow_semantics
1446 : 6722384 : && nowrap_type_p (type));
1447 : 2137099 : if (enforce_overflow_semantics)
1448 : : {
1449 : : /* We can avoid checking whether the result overflows in the following
1450 : : cases:
1451 : :
1452 : : -- must_check_src_overflow is true, and the range of TYPE is superset
1453 : : of the range of CT -- i.e., in all cases except if CT signed and
1454 : : TYPE unsigned.
1455 : : -- both CT and TYPE have the same precision and signedness, and we
1456 : : verify instead that the source does not overflow (this may be
1457 : : easier than verifying it for the result, as we may use the
1458 : : information about the semantics of overflow in CT). */
1459 : 2137099 : if (must_check_src_overflow)
1460 : : {
1461 : 395102 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1462 : : must_check_rslt_overflow = true;
1463 : : else
1464 : : must_check_rslt_overflow = false;
1465 : : }
1466 : 1741997 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1467 : 1741997 : && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1468 : : {
1469 : : must_check_rslt_overflow = false;
1470 : : must_check_src_overflow = true;
1471 : : }
1472 : : else
1473 : : must_check_rslt_overflow = true;
1474 : : }
1475 : : else
1476 : : must_check_rslt_overflow = false;
1477 : :
1478 : 6368517 : if (must_check_src_overflow
1479 : 6722384 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1480 : : use_overflow_semantics))
1481 : : return false;
1482 : :
1483 : 6018346 : new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1484 : : /* The step must be sign extended, regardless of the signedness
1485 : : of CT and TYPE. This only needs to be handled specially when
1486 : : CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1487 : : (with values 100, 99, 98, ...) from becoming signed or unsigned
1488 : : [100, +, 255] with values 100, 355, ...; the sign-extension is
1489 : : performed by default when CT is signed. */
1490 : 6018346 : new_step = *step;
1491 : 6018346 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1492 : : {
1493 : 103867 : tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1494 : 103867 : new_step = chrec_convert (signed_ct, new_step, at_stmt,
1495 : : use_overflow_semantics);
1496 : : }
1497 : 6018346 : new_step = chrec_convert (step_type, new_step, at_stmt,
1498 : : use_overflow_semantics);
1499 : :
1500 : 12036692 : if (automatically_generated_chrec_p (new_base)
1501 : 1764477 : || automatically_generated_chrec_p (new_step))
1502 : : return false;
1503 : :
1504 : 6018093 : if (must_check_rslt_overflow
1505 : : /* Note that in this case we cannot use the fact that signed variables
1506 : : do not overflow, as this is what we are verifying for the new iv. */
1507 : 6018093 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1508 : : at_stmt, loop, false))
1509 : : return false;
1510 : :
1511 : 4957907 : *base = new_base;
1512 : 4957907 : *step = new_step;
1513 : 4957907 : return true;
1514 : : }
1515 : :
1516 : :
1517 : : /* Convert CHREC for the right hand side of a CHREC.
1518 : : The increment for a pointer type is always sizetype. */
1519 : :
1520 : : tree
1521 : 28841428 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1522 : : {
1523 : 28841428 : if (POINTER_TYPE_P (type))
1524 : 5233203 : type = sizetype;
1525 : :
1526 : 28841428 : return chrec_convert (type, chrec, at_stmt);
1527 : : }
1528 : :
1529 : : /* Convert CHREC to TYPE. When the analyzer knows the context in
1530 : : which the CHREC is built, it sets AT_STMT to the statement that
1531 : : contains the definition of the analyzed variable, otherwise the
1532 : : conversion is less accurate: the information is used for
1533 : : determining a more accurate estimation of the number of iterations.
1534 : : By default AT_STMT could be safely set to NULL_TREE.
1535 : :
1536 : : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1537 : : the rules for overflow of the given language apply (e.g., that signed
1538 : : arithmetics in C does not overflow) -- i.e., to use them to avoid
1539 : : unnecessary tests, but also to enforce that the result follows them.
1540 : :
1541 : : FROM is the source variable converted if it's not NULL. */
1542 : :
1543 : : static tree
1544 : 145649011 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1545 : : bool use_overflow_semantics, tree from)
1546 : : {
1547 : 145649011 : tree ct, res;
1548 : 145649011 : tree base, step;
1549 : 145649011 : class loop *loop;
1550 : :
1551 : 250698952 : if (automatically_generated_chrec_p (chrec))
1552 : : return chrec;
1553 : :
1554 : 144625239 : ct = chrec_type (chrec);
1555 : 144625239 : if (useless_type_conversion_p (type, ct))
1556 : : return chrec;
1557 : :
1558 : 39575298 : if (!evolution_function_is_affine_p (chrec))
1559 : 34109698 : goto keep_cast;
1560 : :
1561 : 5465600 : loop = get_chrec_loop (chrec);
1562 : 5465600 : base = CHREC_LEFT (chrec);
1563 : 5465600 : step = CHREC_RIGHT (chrec);
1564 : :
1565 : 5465600 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1566 : : use_overflow_semantics, from))
1567 : 4165273 : return build_polynomial_chrec (loop->num, base, step);
1568 : :
1569 : : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1570 : 1300327 : keep_cast:
1571 : : /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1572 : : may be more expensive. We do want to perform this optimization here
1573 : : though for canonicalization reasons. */
1574 : 35410025 : if (use_overflow_semantics
1575 : 34836894 : && (TREE_CODE (chrec) == PLUS_EXPR
1576 : 34836894 : || TREE_CODE (chrec) == MINUS_EXPR)
1577 : 3173581 : && TREE_CODE (type) == INTEGER_TYPE
1578 : 3137408 : && TREE_CODE (ct) == INTEGER_TYPE
1579 : 3137328 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1580 : 35560011 : && TYPE_OVERFLOW_UNDEFINED (ct))
1581 : 55512 : res = fold_build2 (TREE_CODE (chrec), type,
1582 : : fold_convert (type, TREE_OPERAND (chrec, 0)),
1583 : : fold_convert (type, TREE_OPERAND (chrec, 1)));
1584 : : /* Similar perform the trick that (signed char)((int)x + 2) can be
1585 : : narrowed to (signed char)((unsigned char)x + 2). */
1586 : 35354513 : else if (use_overflow_semantics
1587 : 34781382 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1588 : 1327643 : && TREE_CODE (ct) == INTEGER_TYPE
1589 : 1317438 : && TREE_CODE (type) == INTEGER_TYPE
1590 : 1192002 : && TYPE_OVERFLOW_UNDEFINED (type)
1591 : 36322725 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1592 : : {
1593 : 27549 : tree utype = unsigned_type_for (type);
1594 : 82647 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1595 : 27549 : fold_convert (utype,
1596 : : CHREC_LEFT (chrec)),
1597 : 27549 : fold_convert (utype,
1598 : : CHREC_RIGHT (chrec)));
1599 : 27549 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1600 : : }
1601 : : else
1602 : 35326964 : res = fold_convert (type, chrec);
1603 : :
1604 : : /* Don't propagate overflows. */
1605 : 35410025 : if (CONSTANT_CLASS_P (res))
1606 : 13414700 : TREE_OVERFLOW (res) = 0;
1607 : :
1608 : : /* But reject constants that don't fit in their type after conversion.
1609 : : This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1610 : : natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1611 : : and can cause problems later when computing niters of loops. Note
1612 : : that we don't do the check before converting because we don't want
1613 : : to reject conversions of negative chrecs to unsigned types. */
1614 : 35410025 : if (TREE_CODE (res) == INTEGER_CST
1615 : 13414700 : && TREE_CODE (type) == INTEGER_TYPE
1616 : 13383074 : && !int_fits_type_p (res, type))
1617 : 360 : res = chrec_dont_know;
1618 : :
1619 : : return res;
1620 : : }
1621 : :
1622 : : /* Convert CHREC to TYPE. When the analyzer knows the context in
1623 : : which the CHREC is built, it sets AT_STMT to the statement that
1624 : : contains the definition of the analyzed variable, otherwise the
1625 : : conversion is less accurate: the information is used for
1626 : : determining a more accurate estimation of the number of iterations.
1627 : : By default AT_STMT could be safely set to NULL_TREE.
1628 : :
1629 : : The following rule is always true: TREE_TYPE (chrec) ==
1630 : : TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1631 : : An example of what could happen when adding two chrecs and the type
1632 : : of the CHREC_RIGHT is different than CHREC_LEFT is:
1633 : :
1634 : : {(uint) 0, +, (uchar) 10} +
1635 : : {(uint) 0, +, (uchar) 250}
1636 : :
1637 : : that would produce a wrong result if CHREC_RIGHT is not (uint):
1638 : :
1639 : : {(uint) 0, +, (uchar) 4}
1640 : :
1641 : : instead of
1642 : :
1643 : : {(uint) 0, +, (uint) 260}
1644 : :
1645 : : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1646 : : the rules for overflow of the given language apply (e.g., that signed
1647 : : arithmetics in C does not overflow) -- i.e., to use them to avoid
1648 : : unnecessary tests, but also to enforce that the result follows them.
1649 : :
1650 : : FROM is the source variable converted if it's not NULL. */
1651 : :
1652 : : tree
1653 : 145621462 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1654 : : bool use_overflow_semantics, tree from)
1655 : : {
1656 : 145621462 : return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1657 : : }
1658 : :
1659 : : /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1660 : : chrec if something else than what chrec_convert would do happens, NULL_TREE
1661 : : otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1662 : : if the result chrec may overflow. */
1663 : :
1664 : : tree
1665 : 7925711 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1666 : : {
1667 : 7925711 : tree inner_type, left, right, lc, rc, rtype;
1668 : :
1669 : 7925711 : gcc_assert (fold_conversions != NULL);
1670 : :
1671 : 15387589 : if (automatically_generated_chrec_p (chrec)
1672 : 7925711 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1673 : : return NULL_TREE;
1674 : :
1675 : 588030 : inner_type = TREE_TYPE (chrec);
1676 : 588030 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1677 : : return NULL_TREE;
1678 : :
1679 : 527879 : if (useless_type_conversion_p (type, inner_type))
1680 : : return NULL_TREE;
1681 : :
1682 : 463833 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1683 : : {
1684 : 463128 : tree base, step;
1685 : 463128 : class loop *loop;
1686 : :
1687 : 463128 : loop = get_chrec_loop (chrec);
1688 : 463128 : base = CHREC_LEFT (chrec);
1689 : 463128 : step = CHREC_RIGHT (chrec);
1690 : 463128 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1691 : 1887 : return build_polynomial_chrec (loop->num, base, step);
1692 : : }
1693 : 461946 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1694 : :
1695 : 461946 : left = CHREC_LEFT (chrec);
1696 : 461946 : right = CHREC_RIGHT (chrec);
1697 : 461946 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1698 : 461946 : if (!lc)
1699 : 461946 : lc = chrec_convert (type, left, NULL);
1700 : 461946 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1701 : 461946 : if (!rc)
1702 : 461308 : rc = chrec_convert (rtype, right, NULL);
1703 : :
1704 : 461946 : *fold_conversions = true;
1705 : :
1706 : 461946 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1707 : : }
1708 : :
1709 : : /* Returns true when CHREC0 == CHREC1. */
1710 : :
1711 : : bool
1712 : 11251293 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1713 : : {
1714 : 11280024 : if (chrec0 == NULL_TREE
1715 : 11280024 : || chrec1 == NULL_TREE
1716 : 11280024 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1717 : : return false;
1718 : :
1719 : 10476206 : if (operand_equal_p (chrec0, chrec1, 0))
1720 : : return true;
1721 : :
1722 : 7177073 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1723 : : return false;
1724 : :
1725 : 7176208 : switch (TREE_CODE (chrec0))
1726 : : {
1727 : 2213193 : case POLYNOMIAL_CHREC:
1728 : 2213193 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1729 : 2212842 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1730 : 2507278 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1731 : :
1732 : 66471 : case PLUS_EXPR:
1733 : 66471 : case MULT_EXPR:
1734 : 66471 : case MINUS_EXPR:
1735 : 66471 : case POINTER_PLUS_EXPR:
1736 : 66471 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1737 : 66471 : TREE_OPERAND (chrec1, 0))
1738 : 118763 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1739 : 52292 : TREE_OPERAND (chrec1, 1));
1740 : :
1741 : 28731 : CASE_CONVERT:
1742 : 28731 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1743 : 57462 : TREE_OPERAND (chrec1, 0));
1744 : :
1745 : : default:
1746 : : return false;
1747 : : }
1748 : : }
1749 : :
1750 : : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1751 : : EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1752 : : which of these cases happens. */
1753 : :
1754 : : enum ev_direction
1755 : 3079862 : scev_direction (const_tree chrec)
1756 : : {
1757 : 3079862 : const_tree step;
1758 : :
1759 : 3079862 : if (!evolution_function_is_affine_p (chrec))
1760 : : return EV_DIR_UNKNOWN;
1761 : :
1762 : 3074816 : step = CHREC_RIGHT (chrec);
1763 : 3074816 : if (TREE_CODE (step) != INTEGER_CST)
1764 : : return EV_DIR_UNKNOWN;
1765 : :
1766 : 2905522 : if (tree_int_cst_sign_bit (step))
1767 : : return EV_DIR_DECREASES;
1768 : : else
1769 : 2699894 : return EV_DIR_GROWS;
1770 : : }
1771 : :
1772 : : /* Iterates over all the components of SCEV, and calls CBCK. */
1773 : :
1774 : : void
1775 : 0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1776 : : {
1777 : 0 : switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1778 : : {
1779 : 0 : case 3:
1780 : 0 : for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1781 : : /* FALLTHRU */
1782 : :
1783 : 0 : case 2:
1784 : 0 : for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1785 : : /* FALLTHRU */
1786 : :
1787 : 0 : case 1:
1788 : 0 : for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1789 : : /* FALLTHRU */
1790 : :
1791 : 0 : default:
1792 : 0 : cbck (scev, data);
1793 : 0 : break;
1794 : : }
1795 : 0 : }
1796 : :
1797 : : /* Returns true when the operation can be part of a linear
1798 : : expression. */
1799 : :
1800 : : static inline bool
1801 : 32783 : operator_is_linear (tree scev)
1802 : : {
1803 : 32783 : switch (TREE_CODE (scev))
1804 : : {
1805 : : case INTEGER_CST:
1806 : : case POLYNOMIAL_CHREC:
1807 : : case PLUS_EXPR:
1808 : : case POINTER_PLUS_EXPR:
1809 : : case MULT_EXPR:
1810 : : case MINUS_EXPR:
1811 : : case NEGATE_EXPR:
1812 : : case SSA_NAME:
1813 : : case NON_LVALUE_EXPR:
1814 : : case BIT_NOT_EXPR:
1815 : : CASE_CONVERT:
1816 : : return true;
1817 : :
1818 : 10 : default:
1819 : 10 : return false;
1820 : : }
1821 : : }
1822 : :
1823 : : /* Return true when SCEV is a linear expression. Linear expressions
1824 : : can contain additions, substractions and multiplications.
1825 : : Multiplications are restricted to constant scaling: "cst * x". */
1826 : :
1827 : : bool
1828 : 74680 : scev_is_linear_expression (tree scev)
1829 : : {
1830 : 153908 : if (evolution_function_is_constant_p (scev))
1831 : : return true;
1832 : :
1833 : 32783 : if (scev == NULL
1834 : 32783 : || !operator_is_linear (scev))
1835 : : return false;
1836 : :
1837 : 32773 : if (TREE_CODE (scev) == MULT_EXPR)
1838 : 465 : return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1839 : 0 : && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1840 : :
1841 : 32308 : if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1842 : 32308 : && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1843 : : return false;
1844 : :
1845 : 32140 : switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1846 : : {
1847 : 0 : case 3:
1848 : 0 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1849 : 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1850 : 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1851 : :
1852 : 23452 : case 2:
1853 : 23452 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1854 : 23452 : && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1855 : :
1856 : 2274 : case 1:
1857 : 2274 : return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1858 : :
1859 : : case 0:
1860 : : return true;
1861 : :
1862 : : default:
1863 : : return false;
1864 : : }
1865 : : }
1866 : :
1867 : : /* Determines whether the expression CHREC contains only interger consts
1868 : : in the right parts. */
1869 : :
1870 : : bool
1871 : 4164 : evolution_function_right_is_integer_cst (const_tree chrec)
1872 : : {
1873 : 4164 : if (chrec == NULL_TREE)
1874 : : return false;
1875 : :
1876 : 4164 : switch (TREE_CODE (chrec))
1877 : : {
1878 : : case INTEGER_CST:
1879 : : return true;
1880 : :
1881 : 4164 : case POLYNOMIAL_CHREC:
1882 : 4164 : return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1883 : 4164 : && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1884 : 441 : || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1885 : :
1886 : 0 : CASE_CONVERT:
1887 : 0 : return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1888 : :
1889 : : default:
1890 : : return false;
1891 : : }
1892 : : }
|
