comparison gcc/tree-chrec.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Chains of recurrences. 1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 4
6 This file is part of GCC. 5 This file is part of GCC.
7 6
8 GCC is free software; you can redistribute it and/or modify it under 7 GCC is free software; you can redistribute it and/or modify it under
25 */ 24 */
26 25
27 #include "config.h" 26 #include "config.h"
28 #include "system.h" 27 #include "system.h"
29 #include "coretypes.h" 28 #include "coretypes.h"
29 #include "backend.h"
30 #include "tree.h"
31 #include "gimple-expr.h"
30 #include "tree-pretty-print.h" 32 #include "tree-pretty-print.h"
33 #include "fold-const.h"
31 #include "cfgloop.h" 34 #include "cfgloop.h"
32 #include "tree-flow.h" 35 #include "tree-ssa-loop-ivopts.h"
36 #include "tree-ssa-loop-niter.h"
33 #include "tree-chrec.h" 37 #include "tree-chrec.h"
34 #include "tree-pass.h" 38 #include "dumpfile.h"
35 #include "params.h" 39 #include "params.h"
36 #include "tree-scalar-evolution.h" 40 #include "tree-scalar-evolution.h"
37 41
38 /* Extended folder for chrecs. */ 42 /* Extended folder for chrecs. */
39 43
54 tree cst) 58 tree cst)
55 { 59 {
56 gcc_assert (poly); 60 gcc_assert (poly);
57 gcc_assert (cst); 61 gcc_assert (cst);
58 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC); 62 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
59 gcc_assert (!is_not_constant_evolution (cst)); 63 gcc_checking_assert (!is_not_constant_evolution (cst));
60 gcc_assert (type == chrec_type (poly)); 64 gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly)));
61 65
62 switch (code) 66 switch (code)
63 { 67 {
64 case PLUS_EXPR: 68 case PLUS_EXPR:
65 return build_polynomial_chrec 69 return build_polynomial_chrec
93 tree poly1) 97 tree poly1)
94 { 98 {
95 tree left, right; 99 tree left, right;
96 struct loop *loop0 = get_chrec_loop (poly0); 100 struct loop *loop0 = get_chrec_loop (poly0);
97 struct loop *loop1 = get_chrec_loop (poly1); 101 struct loop *loop1 = get_chrec_loop (poly1);
98 tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type; 102 tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
99 103
100 gcc_assert (poly0); 104 gcc_assert (poly0);
101 gcc_assert (poly1); 105 gcc_assert (poly1);
102 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 106 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
103 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 107 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
104 if (POINTER_TYPE_P (chrec_type (poly0))) 108 if (POINTER_TYPE_P (chrec_type (poly0)))
105 gcc_assert (chrec_type (poly1) == sizetype); 109 gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
110 && useless_type_conversion_p (type, chrec_type (poly0)));
106 else 111 else
107 gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 112 gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
108 gcc_assert (type == chrec_type (poly0)); 113 && useless_type_conversion_p (type, chrec_type (poly1)));
109 114
110 /* 115 /*
111 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, 116 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
112 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, 117 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
113 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ 118 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
142 CHREC_RIGHT (poly0)); 147 CHREC_RIGHT (poly0));
143 } 148 }
144 149
145 /* This function should never be called for chrecs of loops that 150 /* This function should never be called for chrecs of loops that
146 do not belong to the same loop nest. */ 151 do not belong to the same loop nest. */
147 gcc_assert (loop0 == loop1); 152 if (loop0 != loop1)
153 {
154 /* It still can happen if we are not in loop-closed SSA form. */
155 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
156 return chrec_dont_know;
157 }
148 158
149 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 159 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
150 { 160 {
151 left = chrec_fold_plus 161 left = chrec_fold_plus
152 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 162 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
184 194
185 gcc_assert (poly0); 195 gcc_assert (poly0);
186 gcc_assert (poly1); 196 gcc_assert (poly1);
187 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 197 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
188 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 198 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
189 gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 199 gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
190 gcc_assert (type == chrec_type (poly0)); 200 && useless_type_conversion_p (type, chrec_type (poly1)));
191 201
192 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, 202 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
193 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, 203 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
194 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 204 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
195 if (flow_loop_nested_p (loop0, loop1)) 205 if (flow_loop_nested_p (loop0, loop1))
204 return build_polynomial_chrec 214 return build_polynomial_chrec
205 (CHREC_VARIABLE (poly0), 215 (CHREC_VARIABLE (poly0),
206 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), 216 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
207 CHREC_RIGHT (poly0)); 217 CHREC_RIGHT (poly0));
208 218
209 gcc_assert (loop0 == loop1); 219 if (loop0 != loop1)
220 {
221 /* It still can happen if we are not in loop-closed SSA form. */
222 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
223 return chrec_dont_know;
224 }
210 225
211 /* poly0 and poly1 are two polynomials in the same variable, 226 /* poly0 and poly1 are two polynomials in the same variable,
212 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 227 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
213 228
214 /* "a*c". */ 229 /* "a*c". */
260 275
261 static tree 276 static tree
262 chrec_fold_plus_1 (enum tree_code code, tree type, 277 chrec_fold_plus_1 (enum tree_code code, tree type,
263 tree op0, tree op1) 278 tree op0, tree op1)
264 { 279 {
265 tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
266
267 if (automatically_generated_chrec_p (op0) 280 if (automatically_generated_chrec_p (op0)
268 || automatically_generated_chrec_p (op1)) 281 || automatically_generated_chrec_p (op1))
269 return chrec_fold_automatically_generated_operands (op0, op1); 282 return chrec_fold_automatically_generated_operands (op0, op1);
270 283
271 switch (TREE_CODE (op0)) 284 switch (TREE_CODE (op0))
272 { 285 {
273 case POLYNOMIAL_CHREC: 286 case POLYNOMIAL_CHREC:
287 gcc_checking_assert
288 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
274 switch (TREE_CODE (op1)) 289 switch (TREE_CODE (op1))
275 { 290 {
276 case POLYNOMIAL_CHREC: 291 case POLYNOMIAL_CHREC:
292 gcc_checking_assert
293 (!chrec_contains_symbols_defined_in_loop (op1,
294 CHREC_VARIABLE (op1)));
277 return chrec_fold_plus_poly_poly (code, type, op0, op1); 295 return chrec_fold_plus_poly_poly (code, type, op0, op1);
278 296
279 CASE_CONVERT: 297 CASE_CONVERT:
280 if (tree_contains_chrecs (op1, NULL)) 298 if (tree_contains_chrecs (op1, NULL))
281 return chrec_dont_know; 299 return chrec_dont_know;
300 /* FALLTHRU */
282 301
283 default: 302 default:
284 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 303 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
285 return build_polynomial_chrec 304 return build_polynomial_chrec
286 (CHREC_VARIABLE (op0), 305 (CHREC_VARIABLE (op0),
294 } 313 }
295 314
296 CASE_CONVERT: 315 CASE_CONVERT:
297 if (tree_contains_chrecs (op0, NULL)) 316 if (tree_contains_chrecs (op0, NULL))
298 return chrec_dont_know; 317 return chrec_dont_know;
318 /* FALLTHRU */
299 319
300 default: 320 default:
301 switch (TREE_CODE (op1)) 321 switch (TREE_CODE (op1))
302 { 322 {
303 case POLYNOMIAL_CHREC: 323 case POLYNOMIAL_CHREC:
324 gcc_checking_assert
325 (!chrec_contains_symbols_defined_in_loop (op1,
326 CHREC_VARIABLE (op1)));
304 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 327 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
305 return build_polynomial_chrec 328 return build_polynomial_chrec
306 (CHREC_VARIABLE (op1), 329 (CHREC_VARIABLE (op1),
307 chrec_fold_plus (type, op0, CHREC_LEFT (op1)), 330 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
308 CHREC_RIGHT (op1)); 331 CHREC_RIGHT (op1));
316 : build_int_cst_type (type, -1))); 339 : build_int_cst_type (type, -1)));
317 340
318 CASE_CONVERT: 341 CASE_CONVERT:
319 if (tree_contains_chrecs (op1, NULL)) 342 if (tree_contains_chrecs (op1, NULL))
320 return chrec_dont_know; 343 return chrec_dont_know;
344 /* FALLTHRU */
321 345
322 default: 346 default:
323 { 347 {
324 int size = 0; 348 int size = 0;
325 if ((tree_contains_chrecs (op0, &size) 349 if ((tree_contains_chrecs (op0, &size)
326 || tree_contains_chrecs (op1, &size)) 350 || tree_contains_chrecs (op1, &size))
327 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 351 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
328 return build2 (code, type, op0, op1); 352 return build2 (code, type, op0, op1);
329 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 353 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
330 return fold_build2 (code, type, 354 {
331 fold_convert (type, op0), 355 if (code == POINTER_PLUS_EXPR)
332 fold_convert (op1_type, op1)); 356 return fold_build_pointer_plus (fold_convert (type, op0),
357 op1);
358 else
359 return fold_build2 (code, type,
360 fold_convert (type, op0),
361 fold_convert (type, op1));
362 }
333 else 363 else
334 return chrec_dont_know; 364 return chrec_dont_know;
335 } 365 }
336 } 366 }
337 } 367 }
391 return chrec_fold_automatically_generated_operands (op0, op1); 421 return chrec_fold_automatically_generated_operands (op0, op1);
392 422
393 switch (TREE_CODE (op0)) 423 switch (TREE_CODE (op0))
394 { 424 {
395 case POLYNOMIAL_CHREC: 425 case POLYNOMIAL_CHREC:
426 gcc_checking_assert
427 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
396 switch (TREE_CODE (op1)) 428 switch (TREE_CODE (op1))
397 { 429 {
398 case POLYNOMIAL_CHREC: 430 case POLYNOMIAL_CHREC:
431 gcc_checking_assert
432 (!chrec_contains_symbols_defined_in_loop (op1,
433 CHREC_VARIABLE (op1)));
399 return chrec_fold_multiply_poly_poly (type, op0, op1); 434 return chrec_fold_multiply_poly_poly (type, op0, op1);
400 435
401 CASE_CONVERT: 436 CASE_CONVERT:
402 if (tree_contains_chrecs (op1, NULL)) 437 if (tree_contains_chrecs (op1, NULL))
403 return chrec_dont_know; 438 return chrec_dont_know;
439 /* FALLTHRU */
404 440
405 default: 441 default:
406 if (integer_onep (op1)) 442 if (integer_onep (op1))
407 return op0; 443 return op0;
408 if (integer_zerop (op1)) 444 if (integer_zerop (op1))
415 } 451 }
416 452
417 CASE_CONVERT: 453 CASE_CONVERT:
418 if (tree_contains_chrecs (op0, NULL)) 454 if (tree_contains_chrecs (op0, NULL))
419 return chrec_dont_know; 455 return chrec_dont_know;
456 /* FALLTHRU */
420 457
421 default: 458 default:
422 if (integer_onep (op0)) 459 if (integer_onep (op0))
423 return op1; 460 return op1;
424 461
426 return build_int_cst (type, 0); 463 return build_int_cst (type, 0);
427 464
428 switch (TREE_CODE (op1)) 465 switch (TREE_CODE (op1))
429 { 466 {
430 case POLYNOMIAL_CHREC: 467 case POLYNOMIAL_CHREC:
468 gcc_checking_assert
469 (!chrec_contains_symbols_defined_in_loop (op1,
470 CHREC_VARIABLE (op1)));
431 return build_polynomial_chrec 471 return build_polynomial_chrec
432 (CHREC_VARIABLE (op1), 472 (CHREC_VARIABLE (op1),
433 chrec_fold_multiply (type, CHREC_LEFT (op1), op0), 473 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
434 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); 474 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
435 475
436 CASE_CONVERT: 476 CASE_CONVERT:
437 if (tree_contains_chrecs (op1, NULL)) 477 if (tree_contains_chrecs (op1, NULL))
438 return chrec_dont_know; 478 return chrec_dont_know;
479 /* FALLTHRU */
439 480
440 default: 481 default:
441 if (integer_onep (op1)) 482 if (integer_onep (op1))
442 return op0; 483 return op0;
443 if (integer_zerop (op1)) 484 if (integer_zerop (op1))
455 calculation overflows, otherwise return C(n,k) with type TYPE. */ 496 calculation overflows, otherwise return C(n,k) with type TYPE. */
456 497
457 static tree 498 static tree
458 tree_fold_binomial (tree type, tree n, unsigned int k) 499 tree_fold_binomial (tree type, tree n, unsigned int k)
459 { 500 {
460 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; 501 bool overflow;
461 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
462 unsigned int i; 502 unsigned int i;
463 tree res;
464 503
465 /* Handle the most frequent cases. */ 504 /* Handle the most frequent cases. */
466 if (k == 0) 505 if (k == 0)
467 return build_int_cst (type, 1); 506 return build_int_cst (type, 1);
468 if (k == 1) 507 if (k == 1)
469 return fold_convert (type, n); 508 return fold_convert (type, n);
470 509
510 widest_int num = wi::to_widest (n);
511
471 /* Check that k <= n. */ 512 /* Check that k <= n. */
472 if (TREE_INT_CST_HIGH (n) == 0 513 if (wi::ltu_p (num, k))
473 && TREE_INT_CST_LOW (n) < k)
474 return NULL_TREE; 514 return NULL_TREE;
475 515
476 /* Numerator = n. */
477 lnum = TREE_INT_CST_LOW (n);
478 hnum = TREE_INT_CST_HIGH (n);
479
480 /* Denominator = 2. */ 516 /* Denominator = 2. */
481 ldenom = 2; 517 widest_int denom = 2;
482 hdenom = 0;
483 518
484 /* Index = Numerator-1. */ 519 /* Index = Numerator-1. */
485 if (lnum == 0) 520 widest_int idx = num - 1;
486 {
487 hidx = hnum - 1;
488 lidx = ~ (unsigned HOST_WIDE_INT) 0;
489 }
490 else
491 {
492 hidx = hnum;
493 lidx = lnum - 1;
494 }
495 521
496 /* Numerator = Numerator*Index = n*(n-1). */ 522 /* Numerator = Numerator*Index = n*(n-1). */
497 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) 523 num = wi::smul (num, idx, &overflow);
524 if (overflow)
498 return NULL_TREE; 525 return NULL_TREE;
499 526
500 for (i = 3; i <= k; i++) 527 for (i = 3; i <= k; i++)
501 { 528 {
502 /* Index--. */ 529 /* Index--. */
503 if (lidx == 0) 530 --idx;
504 {
505 hidx--;
506 lidx = ~ (unsigned HOST_WIDE_INT) 0;
507 }
508 else
509 lidx--;
510 531
511 /* Numerator *= Index. */ 532 /* Numerator *= Index. */
512 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) 533 num = wi::smul (num, idx, &overflow);
534 if (overflow)
513 return NULL_TREE; 535 return NULL_TREE;
514 536
515 /* Denominator *= i. */ 537 /* Denominator *= i. */
516 mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom); 538 denom *= i;
517 } 539 }
518 540
519 /* Result = Numerator / Denominator. */ 541 /* Result = Numerator / Denominator. */
520 div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom, 542 num = wi::udiv_trunc (num, denom);
521 &lres, &hres, &ldum, &hdum); 543 if (! wi::fits_to_tree_p (num, type))
522 544 return NULL_TREE;
523 res = build_int_cst_wide (type, lres, hres); 545 return wide_int_to_tree (type, num);
524 return int_fits_type_p (res, type) ? res : NULL_TREE;
525 } 546 }
526 547
527 /* Helper function. Use the Newton's interpolating formula for 548 /* Helper function. Use the Newton's interpolating formula for
528 evaluating the value of the evolution function. */ 549 evaluating the value of the evolution function.
550 The result may be in an unsigned type of CHREC. */
529 551
530 static tree 552 static tree
531 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) 553 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
532 { 554 {
533 tree arg0, arg1, binomial_n_k; 555 tree arg0, arg1, binomial_n_k;
534 tree type = TREE_TYPE (chrec); 556 tree type = TREE_TYPE (chrec);
535 struct loop *var_loop = get_loop (var); 557 struct loop *var_loop = get_loop (cfun, var);
536 558
537 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 559 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
538 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec))) 560 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
539 chrec = CHREC_LEFT (chrec); 561 chrec = CHREC_LEFT (chrec);
540 562
563 /* The formula associates the expression and thus we have to make
564 sure to not introduce undefined overflow. */
565 tree ctype = type;
566 if (INTEGRAL_TYPE_P (type)
567 && ! TYPE_OVERFLOW_WRAPS (type))
568 ctype = unsigned_type_for (type);
569
541 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 570 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
542 && CHREC_VARIABLE (chrec) == var) 571 && CHREC_VARIABLE (chrec) == var)
543 { 572 {
544 arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1); 573 arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
545 if (arg1 == chrec_dont_know) 574 if (arg1 == chrec_dont_know)
546 return chrec_dont_know; 575 return chrec_dont_know;
547 binomial_n_k = tree_fold_binomial (type, n, k); 576 binomial_n_k = tree_fold_binomial (ctype, n, k);
548 if (!binomial_n_k) 577 if (!binomial_n_k)
549 return chrec_dont_know; 578 return chrec_dont_know;
550 arg0 = fold_build2 (MULT_EXPR, type, 579 tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
551 CHREC_LEFT (chrec), binomial_n_k); 580 arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
552 return chrec_fold_plus (type, arg0, arg1); 581 return chrec_fold_plus (ctype, arg0, arg1);
553 } 582 }
554 583
555 binomial_n_k = tree_fold_binomial (type, n, k); 584 binomial_n_k = tree_fold_binomial (ctype, n, k);
556 if (!binomial_n_k) 585 if (!binomial_n_k)
557 return chrec_dont_know; 586 return chrec_dont_know;
558 587
559 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k); 588 return fold_build2 (MULT_EXPR, ctype,
589 chrec_convert (ctype, chrec, NULL), binomial_n_k);
560 } 590 }
561 591
562 /* Evaluates "CHREC (X)" when the varying variable is VAR. 592 /* Evaluates "CHREC (X)" when the varying variable is VAR.
563 Example: Given the following parameters, 593 Example: Given the following parameters,
564 594
585 to symbolically compute the apply, since the symbols are 615 to symbolically compute the apply, since the symbols are
586 constants with respect to the varying loop. */ 616 constants with respect to the varying loop. */
587 || chrec_contains_symbols_defined_in_loop (chrec, var)) 617 || chrec_contains_symbols_defined_in_loop (chrec, var))
588 return chrec_dont_know; 618 return chrec_dont_know;
589 619
590 if (dump_file && (dump_flags & TDF_DETAILS)) 620 if (dump_file && (dump_flags & TDF_SCEV))
591 fprintf (dump_file, "(chrec_apply \n"); 621 fprintf (dump_file, "(chrec_apply \n");
592 622
593 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) 623 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
594 x = build_real_from_int_cst (type, x); 624 x = build_real_from_int_cst (type, x);
595 625
610 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); 640 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
611 } 641 }
612 else if (TREE_CODE (x) == INTEGER_CST 642 else if (TREE_CODE (x) == INTEGER_CST
613 && tree_int_cst_sgn (x) == 1) 643 && tree_int_cst_sgn (x) == 1)
614 /* testsuite/.../ssa-chrec-38.c. */ 644 /* testsuite/.../ssa-chrec-38.c. */
615 res = chrec_evaluate (var, chrec, x, 0); 645 res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
616 else 646 else
617 res = chrec_dont_know; 647 res = chrec_dont_know;
618 break; 648 break;
619 649
620 CASE_CONVERT: 650 CASE_CONVERT:
626 default: 656 default:
627 res = chrec; 657 res = chrec;
628 break; 658 break;
629 } 659 }
630 660
631 if (dump_file && (dump_flags & TDF_DETAILS)) 661 if (dump_file && (dump_flags & TDF_SCEV))
632 { 662 {
633 fprintf (dump_file, " (varying_loop = %d\n", var); 663 fprintf (dump_file, " (varying_loop = %d\n", var);
634 fprintf (dump_file, ")\n (chrec = "); 664 fprintf (dump_file, ")\n (chrec = ");
635 print_generic_expr (dump_file, chrec, 0); 665 print_generic_expr (dump_file, chrec);
636 fprintf (dump_file, ")\n (x = "); 666 fprintf (dump_file, ")\n (x = ");
637 print_generic_expr (dump_file, x, 0); 667 print_generic_expr (dump_file, x);
638 fprintf (dump_file, ")\n (res = "); 668 fprintf (dump_file, ")\n (res = ");
639 print_generic_expr (dump_file, res, 0); 669 print_generic_expr (dump_file, res);
640 fprintf (dump_file, "))\n"); 670 fprintf (dump_file, "))\n");
641 } 671 }
642 672
643 return res; 673 return res;
644 } 674 }
646 /* For a given CHREC and an induction variable map IV_MAP that maps 676 /* For a given CHREC and an induction variable map IV_MAP that maps
647 (loop->num, expr) for every loop number of the current_loops an 677 (loop->num, expr) for every loop number of the current_loops an
648 expression, calls chrec_apply when the expression is not NULL. */ 678 expression, calls chrec_apply when the expression is not NULL. */
649 679
650 tree 680 tree
651 chrec_apply_map (tree chrec, VEC (tree, heap) *iv_map) 681 chrec_apply_map (tree chrec, vec<tree> iv_map)
652 { 682 {
653 int i; 683 int i;
654 tree expr; 684 tree expr;
655 685
656 FOR_EACH_VEC_ELT (tree, iv_map, i, expr) 686 FOR_EACH_VEC_ELT (iv_map, i, expr)
657 if (expr) 687 if (expr)
658 chrec = chrec_apply (i, chrec, expr); 688 chrec = chrec_apply (i, chrec, expr);
659 689
660 return chrec; 690 return chrec;
661 } 691 }
703 733
704 tree 734 tree
705 hide_evolution_in_other_loops_than_loop (tree chrec, 735 hide_evolution_in_other_loops_than_loop (tree chrec,
706 unsigned loop_num) 736 unsigned loop_num)
707 { 737 {
708 struct loop *loop = get_loop (loop_num), *chloop; 738 struct loop *loop = get_loop (cfun, loop_num), *chloop;
709 if (automatically_generated_chrec_p (chrec)) 739 if (automatically_generated_chrec_p (chrec))
710 return chrec; 740 return chrec;
711 741
712 switch (TREE_CODE (chrec)) 742 switch (TREE_CODE (chrec))
713 { 743 {
723 753
724 else if (flow_loop_nested_p (chloop, loop)) 754 else if (flow_loop_nested_p (chloop, loop))
725 /* There is no evolution in this loop. */ 755 /* There is no evolution in this loop. */
726 return initial_condition (chrec); 756 return initial_condition (chrec);
727 757
758 else if (flow_loop_nested_p (loop, chloop))
759 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
760 loop_num);
761
728 else 762 else
729 { 763 return chrec_dont_know;
730 gcc_assert (flow_loop_nested_p (loop, chloop));
731 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
732 loop_num);
733 }
734 764
735 default: 765 default:
736 return chrec; 766 return chrec;
737 } 767 }
738 } 768 }
744 chrec_component_in_loop_num (tree chrec, 774 chrec_component_in_loop_num (tree chrec,
745 unsigned loop_num, 775 unsigned loop_num,
746 bool right) 776 bool right)
747 { 777 {
748 tree component; 778 tree component;
749 struct loop *loop = get_loop (loop_num), *chloop; 779 struct loop *loop = get_loop (cfun, loop_num), *chloop;
750 780
751 if (automatically_generated_chrec_p (chrec)) 781 if (automatically_generated_chrec_p (chrec))
752 return chrec; 782 return chrec;
753 783
754 switch (TREE_CODE (chrec)) 784 switch (TREE_CODE (chrec))
826 tree 856 tree
827 reset_evolution_in_loop (unsigned loop_num, 857 reset_evolution_in_loop (unsigned loop_num,
828 tree chrec, 858 tree chrec,
829 tree new_evol) 859 tree new_evol)
830 { 860 {
831 struct loop *loop = get_loop (loop_num); 861 struct loop *loop = get_loop (cfun, loop_num);
832 862
833 if (POINTER_TYPE_P (chrec_type (chrec))) 863 if (POINTER_TYPE_P (chrec_type (chrec)))
834 gcc_assert (sizetype == chrec_type (new_evol)); 864 gcc_assert (ptrofftype_p (chrec_type (new_evol)));
835 else 865 else
836 gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); 866 gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
837 867
838 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 868 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
839 && flow_loop_nested_p (loop, get_chrec_loop (chrec))) 869 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
840 { 870 {
841 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), 871 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
842 new_evol); 872 new_evol);
843 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), 873 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
844 new_evol); 874 new_evol);
845 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), 875 return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
846 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
847 left, right);
848 } 876 }
849 877
850 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 878 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
851 && CHREC_VARIABLE (chrec) == loop_num) 879 && CHREC_VARIABLE (chrec) == loop_num)
852 chrec = CHREC_LEFT (chrec); 880 chrec = CHREC_LEFT (chrec);
930 958
931 if (chrec == NULL_TREE) 959 if (chrec == NULL_TREE)
932 return false; 960 return false;
933 961
934 if (TREE_CODE (chrec) == SSA_NAME 962 if (TREE_CODE (chrec) == SSA_NAME
935 || TREE_CODE (chrec) == VAR_DECL 963 || VAR_P (chrec)
936 || TREE_CODE (chrec) == PARM_DECL 964 || TREE_CODE (chrec) == PARM_DECL
937 || TREE_CODE (chrec) == FUNCTION_DECL 965 || TREE_CODE (chrec) == FUNCTION_DECL
938 || TREE_CODE (chrec) == LABEL_DECL 966 || TREE_CODE (chrec) == LABEL_DECL
939 || TREE_CODE (chrec) == RESULT_DECL 967 || TREE_CODE (chrec) == RESULT_DECL
940 || TREE_CODE (chrec) == FIELD_DECL) 968 || TREE_CODE (chrec) == FIELD_DECL)
1000 if (evolution_function_is_constant_p (chrec)) 1028 if (evolution_function_is_constant_p (chrec))
1001 return true; 1029 return true;
1002 1030
1003 if (TREE_CODE (chrec) == SSA_NAME 1031 if (TREE_CODE (chrec) == SSA_NAME
1004 && (loopnum == 0 1032 && (loopnum == 0
1005 || expr_invariant_in_loop_p (get_loop (loopnum), chrec))) 1033 || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1006 return true; 1034 return true;
1007 1035
1008 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 1036 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1009 { 1037 {
1010 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum 1038 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1039 || flow_loop_nested_p (get_loop (cfun, loopnum),
1040 get_chrec_loop (chrec))
1011 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), 1041 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1012 loopnum) 1042 loopnum)
1013 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), 1043 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1014 loopnum)) 1044 loopnum))
1015 return false; 1045 return false;
1020 { 1050 {
1021 case 2: 1051 case 2:
1022 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), 1052 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1023 loopnum)) 1053 loopnum))
1024 return false; 1054 return false;
1055 /* FALLTHRU */
1025 1056
1026 case 1: 1057 case 1:
1027 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), 1058 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1028 loopnum)) 1059 loopnum))
1029 return false; 1060 return false;
1109 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) 1140 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1110 return false; 1141 return false;
1111 break; 1142 break;
1112 1143
1113 default: 1144 default:
1145 if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1146 return false;
1114 break; 1147 break;
1115 } 1148 }
1116 1149
1117 switch (TREE_CODE (CHREC_RIGHT (chrec))) 1150 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1118 { 1151 {
1122 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) 1155 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1123 return false; 1156 return false;
1124 break; 1157 break;
1125 1158
1126 default: 1159 default:
1160 if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1161 return false;
1127 break; 1162 break;
1128 } 1163 }
1129 1164
1130 default: 1165 default:
1131 return true; 1166 return true;
1150 default: 1185 default:
1151 return 0; 1186 return 0;
1152 } 1187 }
1153 } 1188 }
1154 1189
1155 static tree chrec_convert_1 (tree, tree, gimple, bool);
1156
1157 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv 1190 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1158 the scev corresponds to. AT_STMT is the statement at that the scev is 1191 the scev corresponds to. AT_STMT is the statement at that the scev is
1159 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that 1192 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1160 the rules for overflow of the given language apply (e.g., that signed 1193 that the rules for overflow of the given language apply (e.g., that signed
1161 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1194 arithmetics in C does not overflow) -- i.e., to use them to avoid
1162 tests, but also to enforce that the result follows them. Returns true if the 1195 unnecessary tests, but also to enforce that the result follows them.
1163 conversion succeeded, false otherwise. */ 1196 FROM is the source variable converted if it's not NULL. Returns true if
1197 the conversion succeeded, false otherwise. */
1164 1198
1165 bool 1199 bool
1166 convert_affine_scev (struct loop *loop, tree type, 1200 convert_affine_scev (struct loop *loop, tree type,
1167 tree *base, tree *step, gimple at_stmt, 1201 tree *base, tree *step, gimple *at_stmt,
1168 bool use_overflow_semantics) 1202 bool use_overflow_semantics, tree from)
1169 { 1203 {
1170 tree ct = TREE_TYPE (*step); 1204 tree ct = TREE_TYPE (*step);
1171 bool enforce_overflow_semantics; 1205 bool enforce_overflow_semantics;
1172 bool must_check_src_overflow, must_check_rslt_overflow; 1206 bool must_check_src_overflow, must_check_rslt_overflow;
1173 tree new_base, new_step; 1207 tree new_base, new_step;
1222 } 1256 }
1223 else 1257 else
1224 must_check_rslt_overflow = false; 1258 must_check_rslt_overflow = false;
1225 1259
1226 if (must_check_src_overflow 1260 if (must_check_src_overflow
1227 && scev_probably_wraps_p (*base, *step, at_stmt, loop, 1261 && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1228 use_overflow_semantics)) 1262 use_overflow_semantics))
1229 return false; 1263 return false;
1230 1264
1231 new_base = chrec_convert_1 (type, *base, at_stmt, 1265 new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1232 use_overflow_semantics);
1233 /* The step must be sign extended, regardless of the signedness 1266 /* The step must be sign extended, regardless of the signedness
1234 of CT and TYPE. This only needs to be handled specially when 1267 of CT and TYPE. This only needs to be handled specially when
1235 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] 1268 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1236 (with values 100, 99, 98, ...) from becoming signed or unsigned 1269 (with values 100, 99, 98, ...) from becoming signed or unsigned
1237 [100, +, 255] with values 100, 355, ...; the sign-extension is 1270 [100, +, 255] with values 100, 355, ...; the sign-extension is
1238 performed by default when CT is signed. */ 1271 performed by default when CT is signed. */
1239 new_step = *step; 1272 new_step = *step;
1240 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) 1273 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1241 { 1274 {
1242 tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0); 1275 tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1243 new_step = chrec_convert_1 (signed_ct, new_step, at_stmt, 1276 new_step = chrec_convert (signed_ct, new_step, at_stmt,
1244 use_overflow_semantics); 1277 use_overflow_semantics);
1245 } 1278 }
1246 new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics); 1279 new_step = chrec_convert (step_type, new_step, at_stmt,
1280 use_overflow_semantics);
1247 1281
1248 if (automatically_generated_chrec_p (new_base) 1282 if (automatically_generated_chrec_p (new_base)
1249 || automatically_generated_chrec_p (new_step)) 1283 || automatically_generated_chrec_p (new_step))
1250 return false; 1284 return false;
1251 1285
1252 if (must_check_rslt_overflow 1286 if (must_check_rslt_overflow
1253 /* Note that in this case we cannot use the fact that signed variables 1287 /* Note that in this case we cannot use the fact that signed variables
1254 do not overflow, as this is what we are verifying for the new iv. */ 1288 do not overflow, as this is what we are verifying for the new iv. */
1255 && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false)) 1289 && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1290 at_stmt, loop, false))
1256 return false; 1291 return false;
1257 1292
1258 *base = new_base; 1293 *base = new_base;
1259 *step = new_step; 1294 *step = new_step;
1260 return true; 1295 return true;
1263 1298
1264 /* Convert CHREC for the right hand side of a CHREC. 1299 /* Convert CHREC for the right hand side of a CHREC.
1265 The increment for a pointer type is always sizetype. */ 1300 The increment for a pointer type is always sizetype. */
1266 1301
1267 tree 1302 tree
1268 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt) 1303 chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1269 { 1304 {
1270 if (POINTER_TYPE_P (type)) 1305 if (POINTER_TYPE_P (type))
1271 type = sizetype; 1306 type = sizetype;
1272 1307
1273 return chrec_convert (type, chrec, at_stmt); 1308 return chrec_convert (type, chrec, at_stmt);
1278 contains the definition of the analyzed variable, otherwise the 1313 contains the definition of the analyzed variable, otherwise the
1279 conversion is less accurate: the information is used for 1314 conversion is less accurate: the information is used for
1280 determining a more accurate estimation of the number of iterations. 1315 determining a more accurate estimation of the number of iterations.
1281 By default AT_STMT could be safely set to NULL_TREE. 1316 By default AT_STMT could be safely set to NULL_TREE.
1282 1317
1283 The following rule is always true: TREE_TYPE (chrec) ==
1284 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1285 An example of what could happen when adding two chrecs and the type
1286 of the CHREC_RIGHT is different than CHREC_LEFT is:
1287
1288 {(uint) 0, +, (uchar) 10} +
1289 {(uint) 0, +, (uchar) 250}
1290
1291 that would produce a wrong result if CHREC_RIGHT is not (uint):
1292
1293 {(uint) 0, +, (uchar) 4}
1294
1295 instead of
1296
1297 {(uint) 0, +, (uint) 260}
1298 */
1299
1300 tree
1301 chrec_convert (tree type, tree chrec, gimple at_stmt)
1302 {
1303 return chrec_convert_1 (type, chrec, at_stmt, true);
1304 }
1305
1306 /* Convert CHREC to TYPE. When the analyzer knows the context in
1307 which the CHREC is built, it sets AT_STMT to the statement that
1308 contains the definition of the analyzed variable, otherwise the
1309 conversion is less accurate: the information is used for
1310 determining a more accurate estimation of the number of iterations.
1311 By default AT_STMT could be safely set to NULL_TREE.
1312
1313 USE_OVERFLOW_SEMANTICS is true if this function should assume that 1318 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1314 the rules for overflow of the given language apply (e.g., that signed 1319 the rules for overflow of the given language apply (e.g., that signed
1315 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1320 arithmetics in C does not overflow) -- i.e., to use them to avoid
1316 tests, but also to enforce that the result follows them. */ 1321 unnecessary tests, but also to enforce that the result follows them.
1322
1323 FROM is the source variable converted if it's not NULL. */
1317 1324
1318 static tree 1325 static tree
1319 chrec_convert_1 (tree type, tree chrec, gimple at_stmt, 1326 chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1320 bool use_overflow_semantics) 1327 bool use_overflow_semantics, tree from)
1321 { 1328 {
1322 tree ct, res; 1329 tree ct, res;
1323 tree base, step; 1330 tree base, step;
1324 struct loop *loop; 1331 struct loop *loop;
1325 1332
1326 if (automatically_generated_chrec_p (chrec)) 1333 if (automatically_generated_chrec_p (chrec))
1327 return chrec; 1334 return chrec;
1328 1335
1329 ct = chrec_type (chrec); 1336 ct = chrec_type (chrec);
1330 if (ct == type) 1337 if (useless_type_conversion_p (type, ct))
1331 return chrec; 1338 return chrec;
1332 1339
1333 if (!evolution_function_is_affine_p (chrec)) 1340 if (!evolution_function_is_affine_p (chrec))
1334 goto keep_cast; 1341 goto keep_cast;
1335 1342
1336 loop = get_chrec_loop (chrec); 1343 loop = get_chrec_loop (chrec);
1337 base = CHREC_LEFT (chrec); 1344 base = CHREC_LEFT (chrec);
1338 step = CHREC_RIGHT (chrec); 1345 step = CHREC_RIGHT (chrec);
1339 1346
1340 if (convert_affine_scev (loop, type, &base, &step, at_stmt, 1347 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1341 use_overflow_semantics)) 1348 use_overflow_semantics, from))
1342 return build_polynomial_chrec (loop->num, base, step); 1349 return build_polynomial_chrec (loop->num, base, step);
1343 1350
1344 /* If we cannot propagate the cast inside the chrec, just keep the cast. */ 1351 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1345 keep_cast: 1352 keep_cast:
1346 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that 1353 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1354 && TYPE_PRECISION (type) > TYPE_PRECISION (ct) 1361 && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1355 && TYPE_OVERFLOW_UNDEFINED (ct)) 1362 && TYPE_OVERFLOW_UNDEFINED (ct))
1356 res = fold_build2 (TREE_CODE (chrec), type, 1363 res = fold_build2 (TREE_CODE (chrec), type,
1357 fold_convert (type, TREE_OPERAND (chrec, 0)), 1364 fold_convert (type, TREE_OPERAND (chrec, 0)),
1358 fold_convert (type, TREE_OPERAND (chrec, 1))); 1365 fold_convert (type, TREE_OPERAND (chrec, 1)));
1366 /* Similar perform the trick that (signed char)((int)x + 2) can be
1367 narrowed to (signed char)((unsigned char)x + 2). */
1368 else if (use_overflow_semantics
1369 && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1370 && TREE_CODE (ct) == INTEGER_TYPE
1371 && TREE_CODE (type) == INTEGER_TYPE
1372 && TYPE_OVERFLOW_UNDEFINED (type)
1373 && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1374 {
1375 tree utype = unsigned_type_for (type);
1376 res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1377 fold_convert (utype,
1378 CHREC_LEFT (chrec)),
1379 fold_convert (utype,
1380 CHREC_RIGHT (chrec)));
1381 res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1382 }
1359 else 1383 else
1360 res = fold_convert (type, chrec); 1384 res = fold_convert (type, chrec);
1361 1385
1362 /* Don't propagate overflows. */ 1386 /* Don't propagate overflows. */
1363 if (CONSTANT_CLASS_P (res)) 1387 if (CONSTANT_CLASS_P (res))
1375 res = chrec_dont_know; 1399 res = chrec_dont_know;
1376 1400
1377 return res; 1401 return res;
1378 } 1402 }
1379 1403
1404 /* Convert CHREC to TYPE. When the analyzer knows the context in
1405 which the CHREC is built, it sets AT_STMT to the statement that
1406 contains the definition of the analyzed variable, otherwise the
1407 conversion is less accurate: the information is used for
1408 determining a more accurate estimation of the number of iterations.
1409 By default AT_STMT could be safely set to NULL_TREE.
1410
1411 The following rule is always true: TREE_TYPE (chrec) ==
1412 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1413 An example of what could happen when adding two chrecs and the type
1414 of the CHREC_RIGHT is different than CHREC_LEFT is:
1415
1416 {(uint) 0, +, (uchar) 10} +
1417 {(uint) 0, +, (uchar) 250}
1418
1419 that would produce a wrong result if CHREC_RIGHT is not (uint):
1420
1421 {(uint) 0, +, (uchar) 4}
1422
1423 instead of
1424
1425 {(uint) 0, +, (uint) 260}
1426
1427 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1428 the rules for overflow of the given language apply (e.g., that signed
1429 arithmetics in C does not overflow) -- i.e., to use them to avoid
1430 unnecessary tests, but also to enforce that the result follows them.
1431
1432 FROM is the source variable converted if it's not NULL. */
1433
1434 tree
1435 chrec_convert (tree type, tree chrec, gimple *at_stmt,
1436 bool use_overflow_semantics, tree from)
1437 {
1438 return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1439 }
1440
1380 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new 1441 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1381 chrec if something else than what chrec_convert would do happens, NULL_TREE 1442 chrec if something else than what chrec_convert would do happens, NULL_TREE
1382 otherwise. */ 1443 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1444 if the result chrec may overflow. */
1383 1445
1384 tree 1446 tree
1385 chrec_convert_aggressive (tree type, tree chrec) 1447 chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1386 { 1448 {
1387 tree inner_type, left, right, lc, rc, rtype; 1449 tree inner_type, left, right, lc, rc, rtype;
1450
1451 gcc_assert (fold_conversions != NULL);
1388 1452
1389 if (automatically_generated_chrec_p (chrec) 1453 if (automatically_generated_chrec_p (chrec)
1390 || TREE_CODE (chrec) != POLYNOMIAL_CHREC) 1454 || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1391 return NULL_TREE; 1455 return NULL_TREE;
1392 1456
1393 inner_type = TREE_TYPE (chrec); 1457 inner_type = TREE_TYPE (chrec);
1394 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type)) 1458 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1395 return NULL_TREE; 1459 return NULL_TREE;
1396 1460
1461 if (useless_type_conversion_p (type, inner_type))
1462 return NULL_TREE;
1463
1464 if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1465 {
1466 tree base, step;
1467 struct loop *loop;
1468
1469 loop = get_chrec_loop (chrec);
1470 base = CHREC_LEFT (chrec);
1471 step = CHREC_RIGHT (chrec);
1472 if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1473 return build_polynomial_chrec (loop->num, base, step);
1474 }
1397 rtype = POINTER_TYPE_P (type) ? sizetype : type; 1475 rtype = POINTER_TYPE_P (type) ? sizetype : type;
1398 1476
1399 left = CHREC_LEFT (chrec); 1477 left = CHREC_LEFT (chrec);
1400 right = CHREC_RIGHT (chrec); 1478 right = CHREC_RIGHT (chrec);
1401 lc = chrec_convert_aggressive (type, left); 1479 lc = chrec_convert_aggressive (type, left, fold_conversions);
1402 if (!lc) 1480 if (!lc)
1403 lc = chrec_convert (type, left, NULL); 1481 lc = chrec_convert (type, left, NULL);
1404 rc = chrec_convert_aggressive (rtype, right); 1482 rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1405 if (!rc) 1483 if (!rc)
1406 rc = chrec_convert (rtype, right, NULL); 1484 rc = chrec_convert (rtype, right, NULL);
1485
1486 *fold_conversions = true;
1407 1487
1408 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); 1488 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1409 } 1489 }
1410 1490
1411 /* Returns true when CHREC0 == CHREC1. */ 1491 /* Returns true when CHREC0 == CHREC1. */
1419 return false; 1499 return false;
1420 1500
1421 if (chrec0 == chrec1) 1501 if (chrec0 == chrec1)
1422 return true; 1502 return true;
1423 1503
1504 if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1505 return false;
1506
1424 switch (TREE_CODE (chrec0)) 1507 switch (TREE_CODE (chrec0))
1425 { 1508 {
1426 case INTEGER_CST:
1427 return operand_equal_p (chrec0, chrec1, 0);
1428
1429 case POLYNOMIAL_CHREC: 1509 case POLYNOMIAL_CHREC:
1430 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) 1510 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1431 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) 1511 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1432 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); 1512 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1433 1513
1438 return eq_evolutions_p (TREE_OPERAND (chrec0, 0), 1518 return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1439 TREE_OPERAND (chrec1, 0)) 1519 TREE_OPERAND (chrec1, 0))
1440 && eq_evolutions_p (TREE_OPERAND (chrec0, 1), 1520 && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1441 TREE_OPERAND (chrec1, 1)); 1521 TREE_OPERAND (chrec1, 1));
1442 1522
1523 CASE_CONVERT:
1524 return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1525 TREE_OPERAND (chrec1, 0));
1526
1443 default: 1527 default:
1444 return false; 1528 return operand_equal_p (chrec0, chrec1, 0);
1445 } 1529 }
1446 } 1530 }
1447 1531
1448 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), 1532 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1449 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine 1533 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1474 { 1558 {
1475 switch (TREE_CODE_LENGTH (TREE_CODE (*scev))) 1559 switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1476 { 1560 {
1477 case 3: 1561 case 3:
1478 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data); 1562 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1563 /* FALLTHRU */
1479 1564
1480 case 2: 1565 case 2:
1481 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data); 1566 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1567 /* FALLTHRU */
1482 1568
1483 case 1: 1569 case 1:
1484 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data); 1570 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1571 /* FALLTHRU */
1485 1572
1486 default: 1573 default:
1487 cbck (scev, data); 1574 cbck (scev, data);
1488 break; 1575 break;
1489 } 1576 }
1520 Multiplications are restricted to constant scaling: "cst * x". */ 1607 Multiplications are restricted to constant scaling: "cst * x". */
1521 1608
1522 bool 1609 bool
1523 scev_is_linear_expression (tree scev) 1610 scev_is_linear_expression (tree scev)
1524 { 1611 {
1612 if (evolution_function_is_constant_p (scev))
1613 return true;
1614
1525 if (scev == NULL 1615 if (scev == NULL
1526 || !operator_is_linear (scev)) 1616 || !operator_is_linear (scev))
1527 return false; 1617 return false;
1528 1618
1529 if (TREE_CODE (scev) == MULT_EXPR) 1619 if (TREE_CODE (scev) == MULT_EXPR)