1/* Chains of recurrences. 2 Copyright (C) 2003-2020 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 return false; 1153} 1154 1155/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ 1156 1157bool 1158evolution_function_is_invariant_p (tree chrec, int loopnum) 1159{ 1160 return evolution_function_is_invariant_rec_p (chrec, loopnum); 1161} 1162 1163/* Determine whether the given tree is an affine multivariate 1164 evolution. */ 1165 1166bool 1167evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum) 1168{ 1169 if (chrec == NULL_TREE) 1170 return false; 1171 1172 switch (TREE_CODE (chrec)) 1173 { 1174 case POLYNOMIAL_CHREC: 1175 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum)) 1176 { 1177 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)) 1178 return true; 1179 else 1180 { 1181 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC 1182 && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 1183 != CHREC_VARIABLE (chrec) 1184 && evolution_function_is_affine_multivariate_p 1185 (CHREC_RIGHT (chrec), loopnum)) 1186 return true; 1187 else 1188 return false; 1189 } 1190 } 1191 else 1192 { 1193 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum) 1194 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC 1195 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) 1196 && evolution_function_is_affine_multivariate_p 1197 (CHREC_LEFT (chrec), loopnum)) 1198 return true; 1199 else 1200 return false; 1201 } 1202 1203 default: 1204 return false; 1205 } 1206} 1207 1208/* Determine whether the given tree is a function in zero or one 1209 variables with respect to loop specified by LOOPNUM. Note only positive 1210 LOOPNUM stands for a real loop. */ 1211 1212bool 1213evolution_function_is_univariate_p (const_tree chrec, int loopnum) 1214{ 1215 if (chrec == NULL_TREE) 1216 return true; 1217 1218 tree sub_chrec; 1219 switch (TREE_CODE (chrec)) 1220 { 1221 case POLYNOMIAL_CHREC: 1222 switch (TREE_CODE (CHREC_LEFT (chrec))) 1223 { 1224 case POLYNOMIAL_CHREC: 1225 sub_chrec = CHREC_LEFT (chrec); 1226 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec) 1227 && (loopnum <= 0 1228 || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum 1229 || flow_loop_nested_p (get_loop (cfun, loopnum), 1230 get_chrec_loop (sub_chrec)))) 1231 return false; 1232 if (!evolution_function_is_univariate_p (sub_chrec, loopnum)) 1233 return false; 1234 break; 1235 1236 default: 1237 if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL)) 1238 return false; 1239 break; 1240 } 1241 1242 switch (TREE_CODE (CHREC_RIGHT (chrec))) 1243 { 1244 case POLYNOMIAL_CHREC: 1245 sub_chrec = CHREC_RIGHT (chrec); 1246 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec) 1247 && (loopnum <= 0 1248 || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum 1249 || flow_loop_nested_p (get_loop (cfun, loopnum), 1250 get_chrec_loop (sub_chrec)))) 1251 return false; 1252 if (!evolution_function_is_univariate_p (sub_chrec, loopnum)) 1253 return false; 1254 break; 1255 1256 default: 1257 if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL)) 1258 return false; 1259 break; 1260 } 1261 return true; 1262 1263 default: 1264 return true; 1265 } 1266} 1267 1268/* Returns the number of variables of CHREC. Example: the call 1269 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ 1270 1271unsigned 1272nb_vars_in_chrec (tree chrec) 1273{ 1274 if (chrec == NULL_TREE) 1275 return 0; 1276 1277 switch (TREE_CODE (chrec)) 1278 { 1279 case POLYNOMIAL_CHREC: 1280 return 1 + nb_vars_in_chrec 1281 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); 1282 1283 default: 1284 return 0; 1285 } 1286} 1287 1288/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv 1289 the scev corresponds to. AT_STMT is the statement at that the scev is 1290 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume 1291 that the rules for overflow of the given language apply (e.g., that signed 1292 arithmetics in C does not overflow) -- i.e., to use them to avoid 1293 unnecessary tests, but also to enforce that the result follows them. 1294 FROM is the source variable converted if it's not NULL. Returns true if 1295 the conversion succeeded, false otherwise. */ 1296 1297bool 1298convert_affine_scev (class loop *loop, tree type, 1299 tree *base, tree *step, gimple *at_stmt, 1300 bool use_overflow_semantics, tree from) 1301{ 1302 tree ct = TREE_TYPE (*step); 1303 bool enforce_overflow_semantics; 1304 bool must_check_src_overflow, must_check_rslt_overflow; 1305 tree new_base, new_step; 1306 tree step_type = POINTER_TYPE_P (type) ? sizetype : type; 1307 1308 /* In general, 1309 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i, 1310 but we must check some assumptions. 1311 1312 1) If [BASE, +, STEP] wraps, the equation is not valid when precision 1313 of CT is smaller than the precision of TYPE. For example, when we 1314 cast unsigned char [254, +, 1] to unsigned, the values on left side 1315 are 254, 255, 0, 1, ..., but those on the right side are 1316 254, 255, 256, 257, ... 1317 2) In case that we must also preserve the fact that signed ivs do not 1318 overflow, we must additionally check that the new iv does not wrap. 1319 For example, unsigned char [125, +, 1] casted to signed char could 1320 become a wrapping variable with values 125, 126, 127, -128, -127, ..., 1321 which would confuse optimizers that assume that this does not 1322 happen. */ 1323 must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type); 1324 1325 enforce_overflow_semantics = (use_overflow_semantics 1326 && nowrap_type_p (type)); 1327 if (enforce_overflow_semantics) 1328 { 1329 /* We can avoid checking whether the result overflows in the following 1330 cases: 1331 1332 -- must_check_src_overflow is true, and the range of TYPE is superset 1333 of the range of CT -- i.e., in all cases except if CT signed and 1334 TYPE unsigned. 1335 -- both CT and TYPE have the same precision and signedness, and we 1336 verify instead that the source does not overflow (this may be 1337 easier than verifying it for the result, as we may use the 1338 information about the semantics of overflow in CT). */ 1339 if (must_check_src_overflow) 1340 { 1341 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct)) 1342 must_check_rslt_overflow = true; 1343 else 1344 must_check_rslt_overflow = false; 1345 } 1346 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type) 1347 && TYPE_PRECISION (ct) == TYPE_PRECISION (type)) 1348 { 1349 must_check_rslt_overflow = false; 1350 must_check_src_overflow = true; 1351 } 1352 else 1353 must_check_rslt_overflow = true; 1354 } 1355 else 1356 must_check_rslt_overflow = false; 1357 1358 if (must_check_src_overflow 1359 && scev_probably_wraps_p (from, *base, *step, at_stmt, loop, 1360 use_overflow_semantics)) 1361 return false; 1362 1363 new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics); 1364 /* The step must be sign extended, regardless of the signedness 1365 of CT and TYPE. This only needs to be handled specially when 1366 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] 1367 (with values 100, 99, 98, ...) from becoming signed or unsigned 1368 [100, +, 255] with values 100, 355, ...; the sign-extension is 1369 performed by default when CT is signed. */ 1370 new_step = *step; 1371 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) 1372 { 1373 tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0); 1374 new_step = chrec_convert (signed_ct, new_step, at_stmt, 1375 use_overflow_semantics); 1376 } 1377 new_step = chrec_convert (step_type, new_step, at_stmt, 1378 use_overflow_semantics); 1379 1380 if (automatically_generated_chrec_p (new_base) 1381 || automatically_generated_chrec_p (new_step)) 1382 return false; 1383 1384 if (must_check_rslt_overflow 1385 /* Note that in this case we cannot use the fact that signed variables 1386 do not overflow, as this is what we are verifying for the new iv. */ 1387 && scev_probably_wraps_p (NULL_TREE, new_base, new_step, 1388 at_stmt, loop, false)) 1389 return false; 1390 1391 *base = new_base; 1392 *step = new_step; 1393 return true; 1394} 1395 1396 1397/* Convert CHREC for the right hand side of a CHREC. 1398 The increment for a pointer type is always sizetype. */ 1399 1400tree 1401chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt) 1402{ 1403 if (POINTER_TYPE_P (type)) 1404 type = sizetype; 1405 1406 return chrec_convert (type, chrec, at_stmt); 1407} 1408 1409/* Convert CHREC to TYPE. When the analyzer knows the context in 1410 which the CHREC is built, it sets AT_STMT to the statement that 1411 contains the definition of the analyzed variable, otherwise the 1412 conversion is less accurate: the information is used for 1413 determining a more accurate estimation of the number of iterations. 1414 By default AT_STMT could be safely set to NULL_TREE. 1415 1416 USE_OVERFLOW_SEMANTICS is true if this function should assume that 1417 the rules for overflow of the given language apply (e.g., that signed 1418 arithmetics in C does not overflow) -- i.e., to use them to avoid 1419 unnecessary tests, but also to enforce that the result follows them. 1420 1421 FROM is the source variable converted if it's not NULL. */ 1422 1423static tree 1424chrec_convert_1 (tree type, tree chrec, gimple *at_stmt, 1425 bool use_overflow_semantics, tree from) 1426{ 1427 tree ct, res; 1428 tree base, step; 1429 class loop *loop; 1430 1431 if (automatically_generated_chrec_p (chrec)) 1432 return chrec; 1433 1434 ct = chrec_type (chrec); 1435 if (useless_type_conversion_p (type, ct)) 1436 return chrec; 1437 1438 if (!evolution_function_is_affine_p (chrec)) 1439 goto keep_cast; 1440 1441 loop = get_chrec_loop (chrec); 1442 base = CHREC_LEFT (chrec); 1443 step = CHREC_RIGHT (chrec); 1444 1445 if (convert_affine_scev (loop, type, &base, &step, at_stmt, 1446 use_overflow_semantics, from)) 1447 return build_polynomial_chrec (loop->num, base, step); 1448 1449 /* If we cannot propagate the cast inside the chrec, just keep the cast. */ 1450keep_cast: 1451 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that 1452 may be more expensive. We do want to perform this optimization here 1453 though for canonicalization reasons. */ 1454 if (use_overflow_semantics 1455 && (TREE_CODE (chrec) == PLUS_EXPR 1456 || TREE_CODE (chrec) == MINUS_EXPR) 1457 && TREE_CODE (type) == INTEGER_TYPE 1458 && TREE_CODE (ct) == INTEGER_TYPE 1459 && TYPE_PRECISION (type) > TYPE_PRECISION (ct) 1460 && TYPE_OVERFLOW_UNDEFINED (ct)) 1461 res = fold_build2 (TREE_CODE (chrec), type, 1462 fold_convert (type, TREE_OPERAND (chrec, 0)), 1463 fold_convert (type, TREE_OPERAND (chrec, 1))); 1464 /* Similar perform the trick that (signed char)((int)x + 2) can be 1465 narrowed to (signed char)((unsigned char)x + 2). */ 1466 else if (use_overflow_semantics 1467 && TREE_CODE (chrec) == POLYNOMIAL_CHREC 1468 && TREE_CODE (ct) == INTEGER_TYPE 1469 && TREE_CODE (type) == INTEGER_TYPE 1470 && TYPE_OVERFLOW_UNDEFINED (type) 1471 && TYPE_PRECISION (type) < TYPE_PRECISION (ct)) 1472 { 1473 tree utype = unsigned_type_for (type); 1474 res = build_polynomial_chrec (CHREC_VARIABLE (chrec), 1475 fold_convert (utype, 1476 CHREC_LEFT (chrec)), 1477 fold_convert (utype, 1478 CHREC_RIGHT (chrec))); 1479 res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from); 1480 } 1481 else 1482 res = fold_convert (type, chrec); 1483 1484 /* Don't propagate overflows. */ 1485 if (CONSTANT_CLASS_P (res)) 1486 TREE_OVERFLOW (res) = 0; 1487 1488 /* But reject constants that don't fit in their type after conversion. 1489 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the 1490 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, 1491 and can cause problems later when computing niters of loops. Note 1492 that we don't do the check before converting because we don't want 1493 to reject conversions of negative chrecs to unsigned types. */ 1494 if (TREE_CODE (res) == INTEGER_CST 1495 && TREE_CODE (type) == INTEGER_TYPE 1496 && !int_fits_type_p (res, type)) 1497 res = chrec_dont_know; 1498 1499 return res; 1500} 1501 1502/* Convert CHREC to TYPE. When the analyzer knows the context in 1503 which the CHREC is built, it sets AT_STMT to the statement that 1504 contains the definition of the analyzed variable, otherwise the 1505 conversion is less accurate: the information is used for 1506 determining a more accurate estimation of the number of iterations. 1507 By default AT_STMT could be safely set to NULL_TREE. 1508 1509 The following rule is always true: TREE_TYPE (chrec) == 1510 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). 1511 An example of what could happen when adding two chrecs and the type 1512 of the CHREC_RIGHT is different than CHREC_LEFT is: 1513 1514 {(uint) 0, +, (uchar) 10} + 1515 {(uint) 0, +, (uchar) 250} 1516 1517 that would produce a wrong result if CHREC_RIGHT is not (uint): 1518 1519 {(uint) 0, +, (uchar) 4} 1520 1521 instead of 1522 1523 {(uint) 0, +, (uint) 260} 1524 1525 USE_OVERFLOW_SEMANTICS is true if this function should assume that 1526 the rules for overflow of the given language apply (e.g., that signed 1527 arithmetics in C does not overflow) -- i.e., to use them to avoid 1528 unnecessary tests, but also to enforce that the result follows them. 1529 1530 FROM is the source variable converted if it's not NULL. */ 1531 1532tree 1533chrec_convert (tree type, tree chrec, gimple *at_stmt, 1534 bool use_overflow_semantics, tree from) 1535{ 1536 return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from); 1537} 1538 1539/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new 1540 chrec if something else than what chrec_convert would do happens, NULL_TREE 1541 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS 1542 if the result chrec may overflow. */ 1543 1544tree 1545chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions) 1546{ 1547 tree inner_type, left, right, lc, rc, rtype; 1548 1549 gcc_assert (fold_conversions != NULL); 1550 1551 if (automatically_generated_chrec_p (chrec) 1552 || TREE_CODE (chrec) != POLYNOMIAL_CHREC) 1553 return NULL_TREE; 1554 1555 inner_type = TREE_TYPE (chrec); 1556 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type)) 1557 return NULL_TREE; 1558 1559 if (useless_type_conversion_p (type, inner_type)) 1560 return NULL_TREE; 1561 1562 if (!*fold_conversions && evolution_function_is_affine_p (chrec)) 1563 { 1564 tree base, step; 1565 class loop *loop; 1566 1567 loop = get_chrec_loop (chrec); 1568 base = CHREC_LEFT (chrec); 1569 step = CHREC_RIGHT (chrec); 1570 if (convert_affine_scev (loop, type, &base, &step, NULL, true)) 1571 return build_polynomial_chrec (loop->num, base, step); 1572 } 1573 rtype = POINTER_TYPE_P (type) ? sizetype : type; 1574 1575 left = CHREC_LEFT (chrec); 1576 right = CHREC_RIGHT (chrec); 1577 lc = chrec_convert_aggressive (type, left, fold_conversions); 1578 if (!lc) 1579 lc = chrec_convert (type, left, NULL); 1580 rc = chrec_convert_aggressive (rtype, right, fold_conversions); 1581 if (!rc) 1582 rc = chrec_convert (rtype, right, NULL); 1583 1584 *fold_conversions = true; 1585 1586 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); 1587} 1588 1589/* Returns true when CHREC0 == CHREC1. */ 1590 1591bool 1592eq_evolutions_p (const_tree chrec0, const_tree chrec1) 1593{ 1594 if (chrec0 == NULL_TREE 1595 || chrec1 == NULL_TREE 1596 || TREE_CODE (chrec0) != TREE_CODE (chrec1)) 1597 return false; 1598 1599 if (chrec0 == chrec1) 1600 return true; 1601 1602 if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1))) 1603 return false; 1604 1605 switch (TREE_CODE (chrec0)) 1606 { 1607 case POLYNOMIAL_CHREC: 1608 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) 1609 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) 1610 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); 1611 1612 case PLUS_EXPR: 1613 case MULT_EXPR: 1614 case MINUS_EXPR: 1615 case POINTER_PLUS_EXPR: 1616 return eq_evolutions_p (TREE_OPERAND (chrec0, 0), 1617 TREE_OPERAND (chrec1, 0)) 1618 && eq_evolutions_p (TREE_OPERAND (chrec0, 1), 1619 TREE_OPERAND (chrec1, 1)); 1620 1621 CASE_CONVERT: 1622 return eq_evolutions_p (TREE_OPERAND (chrec0, 0), 1623 TREE_OPERAND (chrec1, 0)); 1624 1625 default: 1626 return operand_equal_p (chrec0, chrec1, 0); 1627 } 1628} 1629 1630/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), 1631 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine 1632 which of these cases happens. */ 1633 1634enum ev_direction 1635scev_direction (const_tree chrec) 1636{ 1637 const_tree step; 1638 1639 if (!evolution_function_is_affine_p (chrec)) 1640 return EV_DIR_UNKNOWN; 1641 1642 step = CHREC_RIGHT (chrec); 1643 if (TREE_CODE (step) != INTEGER_CST) 1644 return EV_DIR_UNKNOWN; 1645 1646 if (tree_int_cst_sign_bit (step)) 1647 return EV_DIR_DECREASES; 1648 else 1649 return EV_DIR_GROWS; 1650} 1651 1652/* Iterates over all the components of SCEV, and calls CBCK. */ 1653 1654void 1655for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data) 1656{ 1657 switch (TREE_CODE_LENGTH (TREE_CODE (*scev))) 1658 { 1659 case 3: 1660 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data); 1661 /* FALLTHRU */ 1662 1663 case 2: 1664 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data); 1665 /* FALLTHRU */ 1666 1667 case 1: 1668 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data); 1669 /* FALLTHRU */ 1670 1671 default: 1672 cbck (scev, data); 1673 break; 1674 } 1675} 1676 1677/* Returns true when the operation can be part of a linear 1678 expression. */ 1679 1680static inline bool 1681operator_is_linear (tree scev) 1682{ 1683 switch (TREE_CODE (scev)) 1684 { 1685 case INTEGER_CST: 1686 case POLYNOMIAL_CHREC: 1687 case PLUS_EXPR: 1688 case POINTER_PLUS_EXPR: 1689 case MULT_EXPR: 1690 case MINUS_EXPR: 1691 case NEGATE_EXPR: 1692 case SSA_NAME: 1693 case NON_LVALUE_EXPR: 1694 case BIT_NOT_EXPR: 1695 CASE_CONVERT: 1696 return true; 1697 1698 default: 1699 return false; 1700 } 1701} 1702 1703/* Return true when SCEV is a linear expression. Linear expressions 1704 can contain additions, substractions and multiplications. 1705 Multiplications are restricted to constant scaling: "cst * x". */ 1706 1707bool 1708scev_is_linear_expression (tree scev) 1709{ 1710 if (evolution_function_is_constant_p (scev)) 1711 return true; 1712 1713 if (scev == NULL 1714 || !operator_is_linear (scev)) 1715 return false; 1716 1717 if (TREE_CODE (scev) == MULT_EXPR) 1718 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL) 1719 && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL)); 1720 1721 if (TREE_CODE (scev) == POLYNOMIAL_CHREC 1722 && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev))) 1723 return false; 1724 1725 switch (TREE_CODE_LENGTH (TREE_CODE (scev))) 1726 { 1727 case 3: 1728 return scev_is_linear_expression (TREE_OPERAND (scev, 0)) 1729 && scev_is_linear_expression (TREE_OPERAND (scev, 1)) 1730 && scev_is_linear_expression (TREE_OPERAND (scev, 2)); 1731 1732 case 2: 1733 return scev_is_linear_expression (TREE_OPERAND (scev, 0)) 1734 && scev_is_linear_expression (TREE_OPERAND (scev, 1)); 1735 1736 case 1: 1737 return scev_is_linear_expression (TREE_OPERAND (scev, 0)); 1738 1739 case 0: 1740 return true; 1741 1742 default: 1743 return false; 1744 } 1745} 1746 1747/* Determines whether the expression CHREC contains only interger consts 1748 in the right parts. */ 1749 1750bool 1751evolution_function_right_is_integer_cst (const_tree chrec) 1752{ 1753 if (chrec == NULL_TREE) 1754 return false; 1755 1756 switch (TREE_CODE (chrec)) 1757 { 1758 case INTEGER_CST: 1759 return true; 1760 1761 case POLYNOMIAL_CHREC: 1762 return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST 1763 && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC 1764 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec))); 1765 1766 CASE_CONVERT: 1767 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0)); 1768 1769 default: 1770 return false; 1771 } 1772} 1773