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