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