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