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