1/* Chains of recurrences. 2 Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* This file implements operations on chains of recurrences. Chains 23 of recurrences are used for modeling evolution functions of scalar 24 variables. 25*/ 26 27#include "config.h" 28#include "system.h" 29#include "coretypes.h" 30#include "tm.h" 31#include "ggc.h" 32#include "tree.h" 33#include "real.h" 34#include "diagnostic.h" 35#include "cfgloop.h" 36#include "tree-flow.h" 37#include "tree-chrec.h" 38#include "tree-pass.h" 39#include "params.h" 40#include "tree-scalar-evolution.h" 41 42 43 44/* Extended folder for chrecs. */ 45 46/* Determines whether CST is not a constant evolution. */ 47 48static inline bool 49is_not_constant_evolution (tree cst) 50{ 51 return (TREE_CODE (cst) == POLYNOMIAL_CHREC); 52} 53 54/* Fold CODE for a polynomial function and a constant. */ 55 56static inline tree 57chrec_fold_poly_cst (enum tree_code code, 58 tree type, 59 tree poly, 60 tree cst) 61{ 62 gcc_assert (poly); 63 gcc_assert (cst); 64 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC); 65 gcc_assert (!is_not_constant_evolution (cst)); 66 gcc_assert (type == chrec_type (poly)); 67 68 switch (code) 69 { 70 case PLUS_EXPR: 71 return build_polynomial_chrec 72 (CHREC_VARIABLE (poly), 73 chrec_fold_plus (type, CHREC_LEFT (poly), cst), 74 CHREC_RIGHT (poly)); 75 76 case MINUS_EXPR: 77 return build_polynomial_chrec 78 (CHREC_VARIABLE (poly), 79 chrec_fold_minus (type, CHREC_LEFT (poly), cst), 80 CHREC_RIGHT (poly)); 81 82 case MULT_EXPR: 83 return build_polynomial_chrec 84 (CHREC_VARIABLE (poly), 85 chrec_fold_multiply (type, CHREC_LEFT (poly), cst), 86 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst)); 87 88 default: 89 return chrec_dont_know; 90 } 91} 92 93/* Fold the addition of two polynomial functions. */ 94 95static inline tree 96chrec_fold_plus_poly_poly (enum tree_code code, 97 tree type, 98 tree poly0, 99 tree poly1) 100{ 101 tree left, right; 102 103 gcc_assert (poly0); 104 gcc_assert (poly1); 105 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 106 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 107 gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 108 gcc_assert (type == chrec_type (poly0)); 109 110 /* 111 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, 112 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, 113 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ 114 if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) 115 { 116 if (code == PLUS_EXPR) 117 return build_polynomial_chrec 118 (CHREC_VARIABLE (poly1), 119 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)), 120 CHREC_RIGHT (poly1)); 121 else 122 return build_polynomial_chrec 123 (CHREC_VARIABLE (poly1), 124 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)), 125 chrec_fold_multiply (type, CHREC_RIGHT (poly1), 126 SCALAR_FLOAT_TYPE_P (type) 127 ? build_real (type, dconstm1) 128 : build_int_cst_type (type, -1))); 129 } 130 131 if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1)) 132 { 133 if (code == PLUS_EXPR) 134 return build_polynomial_chrec 135 (CHREC_VARIABLE (poly0), 136 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1), 137 CHREC_RIGHT (poly0)); 138 else 139 return build_polynomial_chrec 140 (CHREC_VARIABLE (poly0), 141 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), 142 CHREC_RIGHT (poly0)); 143 } 144 145 if (code == PLUS_EXPR) 146 { 147 left = chrec_fold_plus 148 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 149 right = chrec_fold_plus 150 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 151 } 152 else 153 { 154 left = chrec_fold_minus 155 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 156 right = chrec_fold_minus 157 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 158 } 159 160 if (chrec_zerop (right)) 161 return left; 162 else 163 return build_polynomial_chrec 164 (CHREC_VARIABLE (poly0), left, right); 165} 166 167 168 169/* Fold the multiplication of two polynomial functions. */ 170 171static inline tree 172chrec_fold_multiply_poly_poly (tree type, 173 tree poly0, 174 tree poly1) 175{ 176 tree t0, t1, t2; 177 int var; 178 179 gcc_assert (poly0); 180 gcc_assert (poly1); 181 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 182 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 183 gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 184 gcc_assert (type == chrec_type (poly0)); 185 186 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, 187 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, 188 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 189 if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) 190 /* poly0 is a constant wrt. poly1. */ 191 return build_polynomial_chrec 192 (CHREC_VARIABLE (poly1), 193 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), 194 CHREC_RIGHT (poly1)); 195 196 if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0)) 197 /* poly1 is a constant wrt. poly0. */ 198 return build_polynomial_chrec 199 (CHREC_VARIABLE (poly0), 200 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), 201 CHREC_RIGHT (poly0)); 202 203 /* poly0 and poly1 are two polynomials in the same variable, 204 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 205 206 /* "a*c". */ 207 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 208 209 /* "a*d + b*c + b*d". */ 210 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); 211 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, 212 CHREC_RIGHT (poly0), 213 CHREC_LEFT (poly1))); 214 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, 215 CHREC_RIGHT (poly0), 216 CHREC_RIGHT (poly1))); 217 /* "2*b*d". */ 218 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 219 t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type) 220 ? build_real (type, dconst2) 221 : build_int_cst (type, 2), t2); 222 223 var = CHREC_VARIABLE (poly0); 224 return build_polynomial_chrec (var, t0, 225 build_polynomial_chrec (var, t1, t2)); 226} 227 228/* When the operands are automatically_generated_chrec_p, the fold has 229 to respect the semantics of the operands. */ 230 231static inline tree 232chrec_fold_automatically_generated_operands (tree op0, 233 tree op1) 234{ 235 if (op0 == chrec_dont_know 236 || op1 == chrec_dont_know) 237 return chrec_dont_know; 238 239 if (op0 == chrec_known 240 || op1 == chrec_known) 241 return chrec_known; 242 243 if (op0 == chrec_not_analyzed_yet 244 || op1 == chrec_not_analyzed_yet) 245 return chrec_not_analyzed_yet; 246 247 /* The default case produces a safe result. */ 248 return chrec_dont_know; 249} 250 251/* Fold the addition of two chrecs. */ 252 253static tree 254chrec_fold_plus_1 (enum tree_code code, tree type, 255 tree op0, tree op1) 256{ 257 if (automatically_generated_chrec_p (op0) 258 || automatically_generated_chrec_p (op1)) 259 return chrec_fold_automatically_generated_operands (op0, op1); 260 261 switch (TREE_CODE (op0)) 262 { 263 case POLYNOMIAL_CHREC: 264 switch (TREE_CODE (op1)) 265 { 266 case POLYNOMIAL_CHREC: 267 return chrec_fold_plus_poly_poly (code, type, op0, op1); 268 269 default: 270 if (code == PLUS_EXPR) 271 return build_polynomial_chrec 272 (CHREC_VARIABLE (op0), 273 chrec_fold_plus (type, CHREC_LEFT (op0), op1), 274 CHREC_RIGHT (op0)); 275 else 276 return build_polynomial_chrec 277 (CHREC_VARIABLE (op0), 278 chrec_fold_minus (type, CHREC_LEFT (op0), op1), 279 CHREC_RIGHT (op0)); 280 } 281 282 default: 283 switch (TREE_CODE (op1)) 284 { 285 case POLYNOMIAL_CHREC: 286 if (code == PLUS_EXPR) 287 return build_polynomial_chrec 288 (CHREC_VARIABLE (op1), 289 chrec_fold_plus (type, op0, CHREC_LEFT (op1)), 290 CHREC_RIGHT (op1)); 291 else 292 return build_polynomial_chrec 293 (CHREC_VARIABLE (op1), 294 chrec_fold_minus (type, op0, CHREC_LEFT (op1)), 295 chrec_fold_multiply (type, CHREC_RIGHT (op1), 296 SCALAR_FLOAT_TYPE_P (type) 297 ? build_real (type, dconstm1) 298 : build_int_cst_type (type, -1))); 299 300 default: 301 { 302 int size = 0; 303 if ((tree_contains_chrecs (op0, &size) 304 || tree_contains_chrecs (op1, &size)) 305 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 306 return build2 (code, type, op0, op1); 307 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 308 return fold_build2 (code, type, 309 fold_convert (type, op0), 310 fold_convert (type, op1)); 311 else 312 return chrec_dont_know; 313 } 314 } 315 } 316} 317 318/* Fold the addition of two chrecs. */ 319 320tree 321chrec_fold_plus (tree type, 322 tree op0, 323 tree op1) 324{ 325 if (automatically_generated_chrec_p (op0) 326 || automatically_generated_chrec_p (op1)) 327 return chrec_fold_automatically_generated_operands (op0, op1); 328 329 if (integer_zerop (op0)) 330 return op1; 331 if (integer_zerop (op1)) 332 return op0; 333 334 return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1); 335} 336 337/* Fold the subtraction of two chrecs. */ 338 339tree 340chrec_fold_minus (tree type, 341 tree op0, 342 tree op1) 343{ 344 if (automatically_generated_chrec_p (op0) 345 || automatically_generated_chrec_p (op1)) 346 return chrec_fold_automatically_generated_operands (op0, op1); 347 348 if (integer_zerop (op1)) 349 return op0; 350 351 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); 352} 353 354/* Fold the multiplication of two chrecs. */ 355 356tree 357chrec_fold_multiply (tree type, 358 tree op0, 359 tree op1) 360{ 361 if (automatically_generated_chrec_p (op0) 362 || automatically_generated_chrec_p (op1)) 363 return chrec_fold_automatically_generated_operands (op0, op1); 364 365 switch (TREE_CODE (op0)) 366 { 367 case POLYNOMIAL_CHREC: 368 switch (TREE_CODE (op1)) 369 { 370 case POLYNOMIAL_CHREC: 371 return chrec_fold_multiply_poly_poly (type, op0, op1); 372 373 default: 374 if (integer_onep (op1)) 375 return op0; 376 if (integer_zerop (op1)) 377 return build_int_cst (type, 0); 378 379 return build_polynomial_chrec 380 (CHREC_VARIABLE (op0), 381 chrec_fold_multiply (type, CHREC_LEFT (op0), op1), 382 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); 383 } 384 385 default: 386 if (integer_onep (op0)) 387 return op1; 388 389 if (integer_zerop (op0)) 390 return build_int_cst (type, 0); 391 392 switch (TREE_CODE (op1)) 393 { 394 case POLYNOMIAL_CHREC: 395 return build_polynomial_chrec 396 (CHREC_VARIABLE (op1), 397 chrec_fold_multiply (type, CHREC_LEFT (op1), op0), 398 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); 399 400 default: 401 if (integer_onep (op1)) 402 return op0; 403 if (integer_zerop (op1)) 404 return build_int_cst (type, 0); 405 return fold_build2 (MULT_EXPR, type, op0, op1); 406 } 407 } 408} 409 410 411 412/* Operations. */ 413 414/* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate 415 calculation overflows, otherwise return C(n,k) with type TYPE. */ 416 417static tree 418tree_fold_binomial (tree type, tree n, unsigned int k) 419{ 420 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; 421 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum; 422 unsigned int i; 423 tree res; 424 425 /* Handle the most frequent cases. */ 426 if (k == 0) 427 return build_int_cst (type, 1); 428 if (k == 1) 429 return fold_convert (type, n); 430 431 /* Check that k <= n. */ 432 if (TREE_INT_CST_HIGH (n) == 0 433 && TREE_INT_CST_LOW (n) < k) 434 return NULL_TREE; 435 436 /* Numerator = n. */ 437 lnum = TREE_INT_CST_LOW (n); 438 hnum = TREE_INT_CST_HIGH (n); 439 440 /* Denominator = 2. */ 441 ldenom = 2; 442 hdenom = 0; 443 444 /* Index = Numerator-1. */ 445 if (lnum == 0) 446 { 447 hidx = hnum - 1; 448 lidx = ~ (unsigned HOST_WIDE_INT) 0; 449 } 450 else 451 { 452 hidx = hnum; 453 lidx = lnum - 1; 454 } 455 456 /* Numerator = Numerator*Index = n*(n-1). */ 457 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) 458 return NULL_TREE; 459 460 for (i = 3; i <= k; i++) 461 { 462 /* Index--. */ 463 if (lidx == 0) 464 { 465 hidx--; 466 lidx = ~ (unsigned HOST_WIDE_INT) 0; 467 } 468 else 469 lidx--; 470 471 /* Numerator *= Index. */ 472 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) 473 return NULL_TREE; 474 475 /* Denominator *= i. */ 476 mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom); 477 } 478 479 /* Result = Numerator / Denominator. */ 480 div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom, 481 &lres, &hres, &ldum, &hdum); 482 483 res = build_int_cst_wide (type, lres, hres); 484 return int_fits_type_p (res, type) ? res : NULL_TREE; 485} 486 487/* Helper function. Use the Newton's interpolating formula for 488 evaluating the value of the evolution function. */ 489 490static tree 491chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) 492{ 493 tree arg0, arg1, binomial_n_k; 494 tree type = TREE_TYPE (chrec); 495 496 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 497 && CHREC_VARIABLE (chrec) > var) 498 chrec = CHREC_LEFT (chrec); 499 500 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 501 && CHREC_VARIABLE (chrec) == var) 502 { 503 arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1); 504 if (arg0 == chrec_dont_know) 505 return chrec_dont_know; 506 binomial_n_k = tree_fold_binomial (type, n, k); 507 if (!binomial_n_k) 508 return chrec_dont_know; 509 arg1 = fold_build2 (MULT_EXPR, type, 510 CHREC_LEFT (chrec), binomial_n_k); 511 return chrec_fold_plus (type, arg0, arg1); 512 } 513 514 binomial_n_k = tree_fold_binomial (type, n, k); 515 if (!binomial_n_k) 516 return chrec_dont_know; 517 518 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k); 519} 520 521/* Evaluates "CHREC (X)" when the varying variable is VAR. 522 Example: Given the following parameters, 523 524 var = 1 525 chrec = {3, +, 4}_1 526 x = 10 527 528 The result is given by the Newton's interpolating formula: 529 3 * \binom{10}{0} + 4 * \binom{10}{1}. 530*/ 531 532tree 533chrec_apply (unsigned var, 534 tree chrec, 535 tree x) 536{ 537 tree type = chrec_type (chrec); 538 tree res = chrec_dont_know; 539 540 if (automatically_generated_chrec_p (chrec) 541 || automatically_generated_chrec_p (x) 542 543 /* When the symbols are defined in an outer loop, it is possible 544 to symbolically compute the apply, since the symbols are 545 constants with respect to the varying loop. */ 546 || chrec_contains_symbols_defined_in_loop (chrec, var)) 547 return chrec_dont_know; 548 549 if (dump_file && (dump_flags & TDF_DETAILS)) 550 fprintf (dump_file, "(chrec_apply \n"); 551 552 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) 553 x = build_real_from_int_cst (type, x); 554 555 if (evolution_function_is_affine_p (chrec)) 556 { 557 /* "{a, +, b} (x)" -> "a + b*x". */ 558 x = chrec_convert (type, x, NULL_TREE); 559 res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x); 560 if (!integer_zerop (CHREC_LEFT (chrec))) 561 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); 562 } 563 564 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 565 res = chrec; 566 567 else if (TREE_CODE (x) == INTEGER_CST 568 && tree_int_cst_sgn (x) == 1) 569 /* testsuite/.../ssa-chrec-38.c. */ 570 res = chrec_evaluate (var, chrec, x, 0); 571 else 572 res = chrec_dont_know; 573 574 if (dump_file && (dump_flags & TDF_DETAILS)) 575 { 576 fprintf (dump_file, " (varying_loop = %d\n", var); 577 fprintf (dump_file, ")\n (chrec = "); 578 print_generic_expr (dump_file, chrec, 0); 579 fprintf (dump_file, ")\n (x = "); 580 print_generic_expr (dump_file, x, 0); 581 fprintf (dump_file, ")\n (res = "); 582 print_generic_expr (dump_file, res, 0); 583 fprintf (dump_file, "))\n"); 584 } 585 586 return res; 587} 588 589/* Replaces the initial condition in CHREC with INIT_COND. */ 590 591tree 592chrec_replace_initial_condition (tree chrec, 593 tree init_cond) 594{ 595 if (automatically_generated_chrec_p (chrec)) 596 return chrec; 597 598 gcc_assert (chrec_type (chrec) == chrec_type (init_cond)); 599 600 switch (TREE_CODE (chrec)) 601 { 602 case POLYNOMIAL_CHREC: 603 return build_polynomial_chrec 604 (CHREC_VARIABLE (chrec), 605 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), 606 CHREC_RIGHT (chrec)); 607 608 default: 609 return init_cond; 610 } 611} 612 613/* Returns the initial condition of a given CHREC. */ 614 615tree 616initial_condition (tree chrec) 617{ 618 if (automatically_generated_chrec_p (chrec)) 619 return chrec; 620 621 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 622 return initial_condition (CHREC_LEFT (chrec)); 623 else 624 return chrec; 625} 626 627/* Returns a univariate function that represents the evolution in 628 LOOP_NUM. Mask the evolution of any other loop. */ 629 630tree 631hide_evolution_in_other_loops_than_loop (tree chrec, 632 unsigned loop_num) 633{ 634 if (automatically_generated_chrec_p (chrec)) 635 return chrec; 636 637 switch (TREE_CODE (chrec)) 638 { 639 case POLYNOMIAL_CHREC: 640 if (CHREC_VARIABLE (chrec) == loop_num) 641 return build_polynomial_chrec 642 (loop_num, 643 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 644 loop_num), 645 CHREC_RIGHT (chrec)); 646 647 else if (CHREC_VARIABLE (chrec) < loop_num) 648 /* There is no evolution in this loop. */ 649 return initial_condition (chrec); 650 651 else 652 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 653 loop_num); 654 655 default: 656 return chrec; 657 } 658} 659 660/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is 661 true, otherwise returns the initial condition in LOOP_NUM. */ 662 663static tree 664chrec_component_in_loop_num (tree chrec, 665 unsigned loop_num, 666 bool right) 667{ 668 tree component; 669 670 if (automatically_generated_chrec_p (chrec)) 671 return chrec; 672 673 switch (TREE_CODE (chrec)) 674 { 675 case POLYNOMIAL_CHREC: 676 if (CHREC_VARIABLE (chrec) == loop_num) 677 { 678 if (right) 679 component = CHREC_RIGHT (chrec); 680 else 681 component = CHREC_LEFT (chrec); 682 683 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC 684 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) 685 return component; 686 687 else 688 return build_polynomial_chrec 689 (loop_num, 690 chrec_component_in_loop_num (CHREC_LEFT (chrec), 691 loop_num, 692 right), 693 component); 694 } 695 696 else if (CHREC_VARIABLE (chrec) < loop_num) 697 /* There is no evolution part in this loop. */ 698 return NULL_TREE; 699 700 else 701 return chrec_component_in_loop_num (CHREC_LEFT (chrec), 702 loop_num, 703 right); 704 705 default: 706 if (right) 707 return NULL_TREE; 708 else 709 return chrec; 710 } 711} 712 713/* Returns the evolution part in LOOP_NUM. Example: the call 714 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns 715 {1, +, 2}_1 */ 716 717tree 718evolution_part_in_loop_num (tree chrec, 719 unsigned loop_num) 720{ 721 return chrec_component_in_loop_num (chrec, loop_num, true); 722} 723 724/* Returns the initial condition in LOOP_NUM. Example: the call 725 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns 726 {0, +, 1}_1 */ 727 728tree 729initial_condition_in_loop_num (tree chrec, 730 unsigned loop_num) 731{ 732 return chrec_component_in_loop_num (chrec, loop_num, false); 733} 734 735/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. 736 This function is essentially used for setting the evolution to 737 chrec_dont_know, for example after having determined that it is 738 impossible to say how many times a loop will execute. */ 739 740tree 741reset_evolution_in_loop (unsigned loop_num, 742 tree chrec, 743 tree new_evol) 744{ 745 gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); 746 747 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 748 && CHREC_VARIABLE (chrec) > loop_num) 749 { 750 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), 751 new_evol); 752 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), 753 new_evol); 754 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), 755 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)), 756 left, right); 757 } 758 759 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 760 && CHREC_VARIABLE (chrec) == loop_num) 761 chrec = CHREC_LEFT (chrec); 762 763 return build_polynomial_chrec (loop_num, chrec, new_evol); 764} 765 766/* Merges two evolution functions that were found by following two 767 alternate paths of a conditional expression. */ 768 769tree 770chrec_merge (tree chrec1, 771 tree chrec2) 772{ 773 if (chrec1 == chrec_dont_know 774 || chrec2 == chrec_dont_know) 775 return chrec_dont_know; 776 777 if (chrec1 == chrec_known 778 || chrec2 == chrec_known) 779 return chrec_known; 780 781 if (chrec1 == chrec_not_analyzed_yet) 782 return chrec2; 783 if (chrec2 == chrec_not_analyzed_yet) 784 return chrec1; 785 786 if (eq_evolutions_p (chrec1, chrec2)) 787 return chrec1; 788 789 return chrec_dont_know; 790} 791 792 793 794/* Observers. */ 795 796/* Helper function for is_multivariate_chrec. */ 797 798static bool 799is_multivariate_chrec_rec (tree chrec, unsigned int rec_var) 800{ 801 if (chrec == NULL_TREE) 802 return false; 803 804 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 805 { 806 if (CHREC_VARIABLE (chrec) != rec_var) 807 return true; 808 else 809 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) 810 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var)); 811 } 812 else 813 return false; 814} 815 816/* Determine whether the given chrec is multivariate or not. */ 817 818bool 819is_multivariate_chrec (tree chrec) 820{ 821 if (chrec == NULL_TREE) 822 return false; 823 824 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 825 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), 826 CHREC_VARIABLE (chrec)) 827 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), 828 CHREC_VARIABLE (chrec))); 829 else 830 return false; 831} 832 833/* Determines whether the chrec contains symbolic names or not. */ 834 835bool 836chrec_contains_symbols (tree chrec) 837{ 838 if (chrec == NULL_TREE) 839 return false; 840 841 if (TREE_CODE (chrec) == SSA_NAME 842 || TREE_CODE (chrec) == VAR_DECL 843 || TREE_CODE (chrec) == PARM_DECL 844 || TREE_CODE (chrec) == FUNCTION_DECL 845 || TREE_CODE (chrec) == LABEL_DECL 846 || TREE_CODE (chrec) == RESULT_DECL 847 || TREE_CODE (chrec) == FIELD_DECL) 848 return true; 849 850 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 851 { 852 case 3: 853 if (chrec_contains_symbols (TREE_OPERAND (chrec, 2))) 854 return true; 855 856 case 2: 857 if (chrec_contains_symbols (TREE_OPERAND (chrec, 1))) 858 return true; 859 860 case 1: 861 if (chrec_contains_symbols (TREE_OPERAND (chrec, 0))) 862 return true; 863 864 default: 865 return false; 866 } 867} 868 869/* Determines whether the chrec contains undetermined coefficients. */ 870 871bool 872chrec_contains_undetermined (tree chrec) 873{ 874 if (chrec == chrec_dont_know 875 || chrec == chrec_not_analyzed_yet 876 || chrec == NULL_TREE) 877 return true; 878 879 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 880 { 881 case 3: 882 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2))) 883 return true; 884 885 case 2: 886 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1))) 887 return true; 888 889 case 1: 890 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0))) 891 return true; 892 893 default: 894 return false; 895 } 896} 897 898/* Determines whether the tree EXPR contains chrecs, and increment 899 SIZE if it is not a NULL pointer by an estimation of the depth of 900 the tree. */ 901 902bool 903tree_contains_chrecs (tree expr, int *size) 904{ 905 if (expr == NULL_TREE) 906 return false; 907 908 if (size) 909 (*size)++; 910 911 if (tree_is_chrec (expr)) 912 return true; 913 914 switch (TREE_CODE_LENGTH (TREE_CODE (expr))) 915 { 916 case 3: 917 if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size)) 918 return true; 919 920 case 2: 921 if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size)) 922 return true; 923 924 case 1: 925 if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size)) 926 return true; 927 928 default: 929 return false; 930 } 931} 932 933/* Recursive helper function. */ 934 935static bool 936evolution_function_is_invariant_rec_p (tree chrec, int loopnum) 937{ 938 if (evolution_function_is_constant_p (chrec)) 939 return true; 940 941 if (TREE_CODE (chrec) == SSA_NAME 942 && expr_invariant_in_loop_p (current_loops->parray[loopnum], 943 chrec)) 944 return true; 945 946 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 947 { 948 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum 949 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), 950 loopnum) 951 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), 952 loopnum)) 953 return false; 954 return true; 955 } 956 957 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 958 { 959 case 2: 960 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), 961 loopnum)) 962 return false; 963 964 case 1: 965 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), 966 loopnum)) 967 return false; 968 return true; 969 970 default: 971 return false; 972 } 973 974 return false; 975} 976 977/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ 978 979bool 980evolution_function_is_invariant_p (tree chrec, int loopnum) 981{ 982 if (evolution_function_is_constant_p (chrec)) 983 return true; 984 985 if (current_loops != NULL) 986 return evolution_function_is_invariant_rec_p (chrec, loopnum); 987 988 return false; 989} 990 991/* Determine whether the given tree is an affine multivariate 992 evolution. */ 993 994bool 995evolution_function_is_affine_multivariate_p (tree chrec) 996{ 997 if (chrec == NULL_TREE) 998 return false; 999 1000 switch (TREE_CODE (chrec)) 1001 { 1002 case POLYNOMIAL_CHREC: 1003 if (evolution_function_is_constant_p (CHREC_LEFT (chrec))) 1004 { 1005 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))) 1006 return true; 1007 else 1008 { 1009 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC 1010 && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 1011 != CHREC_VARIABLE (chrec) 1012 && evolution_function_is_affine_multivariate_p 1013 (CHREC_RIGHT (chrec))) 1014 return true; 1015 else 1016 return false; 1017 } 1018 } 1019 else 1020 { 1021 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)) 1022 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC 1023 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) 1024 && evolution_function_is_affine_multivariate_p 1025 (CHREC_LEFT (chrec))) 1026 return true; 1027 else 1028 return false; 1029 } 1030 1031 default: 1032 return false; 1033 } 1034} 1035 1036/* Determine whether the given tree is a function in zero or one 1037 variables. */ 1038 1039bool 1040evolution_function_is_univariate_p (tree chrec) 1041{ 1042 if (chrec == NULL_TREE) 1043 return true; 1044 1045 switch (TREE_CODE (chrec)) 1046 { 1047 case POLYNOMIAL_CHREC: 1048 switch (TREE_CODE (CHREC_LEFT (chrec))) 1049 { 1050 case POLYNOMIAL_CHREC: 1051 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec))) 1052 return false; 1053 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) 1054 return false; 1055 break; 1056 1057 default: 1058 break; 1059 } 1060 1061 switch (TREE_CODE (CHREC_RIGHT (chrec))) 1062 { 1063 case POLYNOMIAL_CHREC: 1064 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec))) 1065 return false; 1066 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) 1067 return false; 1068 break; 1069 1070 default: 1071 break; 1072 } 1073 1074 default: 1075 return true; 1076 } 1077} 1078 1079/* Returns the number of variables of CHREC. Example: the call 1080 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ 1081 1082unsigned 1083nb_vars_in_chrec (tree chrec) 1084{ 1085 if (chrec == NULL_TREE) 1086 return 0; 1087 1088 switch (TREE_CODE (chrec)) 1089 { 1090 case POLYNOMIAL_CHREC: 1091 return 1 + nb_vars_in_chrec 1092 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); 1093 1094 default: 1095 return 0; 1096 } 1097} 1098 1099/* Returns true if TYPE is a type in that we cannot directly perform 1100 arithmetics, even though it is a scalar type. */ 1101 1102static bool 1103avoid_arithmetics_in_type_p (tree type) 1104{ 1105 /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed 1106 in the subtype, but a base type must be used, and the result then can 1107 be casted to the subtype. */ 1108 if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE) 1109 return true; 1110 1111 return false; 1112} 1113 1114static tree chrec_convert_1 (tree, tree, tree, bool); 1115 1116/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv 1117 the scev corresponds to. AT_STMT is the statement at that the scev is 1118 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that 1119 the rules for overflow of the given language apply (e.g., that signed 1120 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1121 tests, but also to enforce that the result follows them. Returns true if the 1122 conversion succeeded, false otherwise. */ 1123 1124bool 1125convert_affine_scev (struct loop *loop, tree type, 1126 tree *base, tree *step, tree at_stmt, 1127 bool use_overflow_semantics) 1128{ 1129 tree ct = TREE_TYPE (*step); 1130 bool enforce_overflow_semantics; 1131 bool must_check_src_overflow, must_check_rslt_overflow; 1132 tree new_base, new_step; 1133 1134 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */ 1135 if (avoid_arithmetics_in_type_p (type)) 1136 return false; 1137 1138 /* In general, 1139 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i, 1140 but we must check some assumptions. 1141 1142 1) If [BASE, +, STEP] wraps, the equation is not valid when precision 1143 of CT is smaller than the precision of TYPE. For example, when we 1144 cast unsigned char [254, +, 1] to unsigned, the values on left side 1145 are 254, 255, 0, 1, ..., but those on the right side are 1146 254, 255, 256, 257, ... 1147 2) In case that we must also preserve the fact that signed ivs do not 1148 overflow, we must additionally check that the new iv does not wrap. 1149 For example, unsigned char [125, +, 1] casted to signed char could 1150 become a wrapping variable with values 125, 126, 127, -128, -127, ..., 1151 which would confuse optimizers that assume that this does not 1152 happen. */ 1153 must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type); 1154 1155 enforce_overflow_semantics = (use_overflow_semantics 1156 && nowrap_type_p (type)); 1157 if (enforce_overflow_semantics) 1158 { 1159 /* We can avoid checking whether the result overflows in the following 1160 cases: 1161 1162 -- must_check_src_overflow is true, and the range of TYPE is superset 1163 of the range of CT -- i.e., in all cases except if CT signed and 1164 TYPE unsigned. 1165 -- both CT and TYPE have the same precision and signedness, and we 1166 verify instead that the source does not overflow (this may be 1167 easier than verifying it for the result, as we may use the 1168 information about the semantics of overflow in CT). */ 1169 if (must_check_src_overflow) 1170 { 1171 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct)) 1172 must_check_rslt_overflow = true; 1173 else 1174 must_check_rslt_overflow = false; 1175 } 1176 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type) 1177 && TYPE_PRECISION (ct) == TYPE_PRECISION (type)) 1178 { 1179 must_check_rslt_overflow = false; 1180 must_check_src_overflow = true; 1181 } 1182 else 1183 must_check_rslt_overflow = true; 1184 } 1185 else 1186 must_check_rslt_overflow = false; 1187 1188 if (must_check_src_overflow 1189 && scev_probably_wraps_p (*base, *step, at_stmt, loop, 1190 use_overflow_semantics)) 1191 return false; 1192 1193 new_base = chrec_convert_1 (type, *base, at_stmt, 1194 use_overflow_semantics); 1195 /* The step must be sign extended, regardless of the signedness 1196 of CT and TYPE. This only needs to be handled specially when 1197 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] 1198 (with values 100, 99, 98, ...) from becoming signed or unsigned 1199 [100, +, 255] with values 100, 355, ...; the sign-extension is 1200 performed by default when CT is signed. */ 1201 new_step = *step; 1202 if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) 1203 new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt, 1204 use_overflow_semantics); 1205 new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics); 1206 1207 if (automatically_generated_chrec_p (new_base) 1208 || automatically_generated_chrec_p (new_step)) 1209 return false; 1210 1211 if (must_check_rslt_overflow 1212 /* Note that in this case we cannot use the fact that signed variables 1213 do not overflow, as this is what we are verifying for the new iv. */ 1214 && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false)) 1215 return false; 1216 1217 *base = new_base; 1218 *step = new_step; 1219 return true; 1220} 1221 1222 1223/* Convert CHREC to TYPE. When the analyzer knows the context in 1224 which the CHREC is built, it sets AT_STMT to the statement that 1225 contains the definition of the analyzed variable, otherwise the 1226 conversion is less accurate: the information is used for 1227 determining a more accurate estimation of the number of iterations. 1228 By default AT_STMT could be safely set to NULL_TREE. 1229 1230 The following rule is always true: TREE_TYPE (chrec) == 1231 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). 1232 An example of what could happen when adding two chrecs and the type 1233 of the CHREC_RIGHT is different than CHREC_LEFT is: 1234 1235 {(uint) 0, +, (uchar) 10} + 1236 {(uint) 0, +, (uchar) 250} 1237 1238 that would produce a wrong result if CHREC_RIGHT is not (uint): 1239 1240 {(uint) 0, +, (uchar) 4} 1241 1242 instead of 1243 1244 {(uint) 0, +, (uint) 260} 1245*/ 1246 1247tree 1248chrec_convert (tree type, tree chrec, tree at_stmt) 1249{ 1250 return chrec_convert_1 (type, chrec, at_stmt, true); 1251} 1252 1253/* Convert CHREC to TYPE. When the analyzer knows the context in 1254 which the CHREC is built, it sets AT_STMT to the statement that 1255 contains the definition of the analyzed variable, otherwise the 1256 conversion is less accurate: the information is used for 1257 determining a more accurate estimation of the number of iterations. 1258 By default AT_STMT could be safely set to NULL_TREE. 1259 1260 USE_OVERFLOW_SEMANTICS is true if this function should assume that 1261 the rules for overflow of the given language apply (e.g., that signed 1262 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1263 tests, but also to enforce that the result follows them. */ 1264 1265static tree 1266chrec_convert_1 (tree type, tree chrec, tree at_stmt, 1267 bool use_overflow_semantics) 1268{ 1269 tree ct, res; 1270 tree base, step; 1271 struct loop *loop; 1272 1273 if (automatically_generated_chrec_p (chrec)) 1274 return chrec; 1275 1276 ct = chrec_type (chrec); 1277 if (ct == type) 1278 return chrec; 1279 1280 if (!evolution_function_is_affine_p (chrec)) 1281 goto keep_cast; 1282 1283 loop = current_loops->parray[CHREC_VARIABLE (chrec)]; 1284 base = CHREC_LEFT (chrec); 1285 step = CHREC_RIGHT (chrec); 1286 1287 if (convert_affine_scev (loop, type, &base, &step, at_stmt, 1288 use_overflow_semantics)) 1289 return build_polynomial_chrec (loop->num, base, step); 1290 1291 /* If we cannot propagate the cast inside the chrec, just keep the cast. */ 1292keep_cast: 1293 res = fold_convert (type, chrec); 1294 1295 /* Don't propagate overflows. */ 1296 if (CONSTANT_CLASS_P (res)) 1297 { 1298 TREE_CONSTANT_OVERFLOW (res) = 0; 1299 TREE_OVERFLOW (res) = 0; 1300 } 1301 1302 /* But reject constants that don't fit in their type after conversion. 1303 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the 1304 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, 1305 and can cause problems later when computing niters of loops. Note 1306 that we don't do the check before converting because we don't want 1307 to reject conversions of negative chrecs to unsigned types. */ 1308 if (TREE_CODE (res) == INTEGER_CST 1309 && TREE_CODE (type) == INTEGER_TYPE 1310 && !int_fits_type_p (res, type)) 1311 res = chrec_dont_know; 1312 1313 return res; 1314} 1315 1316/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new 1317 chrec if something else than what chrec_convert would do happens, NULL_TREE 1318 otherwise. */ 1319 1320tree 1321chrec_convert_aggressive (tree type, tree chrec) 1322{ 1323 tree inner_type, left, right, lc, rc; 1324 1325 if (automatically_generated_chrec_p (chrec) 1326 || TREE_CODE (chrec) != POLYNOMIAL_CHREC) 1327 return NULL_TREE; 1328 1329 inner_type = TREE_TYPE (chrec); 1330 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type)) 1331 return NULL_TREE; 1332 1333 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */ 1334 if (avoid_arithmetics_in_type_p (type)) 1335 return NULL_TREE; 1336 1337 left = CHREC_LEFT (chrec); 1338 right = CHREC_RIGHT (chrec); 1339 lc = chrec_convert_aggressive (type, left); 1340 if (!lc) 1341 lc = chrec_convert (type, left, NULL_TREE); 1342 rc = chrec_convert_aggressive (type, right); 1343 if (!rc) 1344 rc = chrec_convert (type, right, NULL_TREE); 1345 1346 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); 1347} 1348 1349/* Returns true when CHREC0 == CHREC1. */ 1350 1351bool 1352eq_evolutions_p (tree chrec0, 1353 tree chrec1) 1354{ 1355 if (chrec0 == NULL_TREE 1356 || chrec1 == NULL_TREE 1357 || TREE_CODE (chrec0) != TREE_CODE (chrec1)) 1358 return false; 1359 1360 if (chrec0 == chrec1) 1361 return true; 1362 1363 switch (TREE_CODE (chrec0)) 1364 { 1365 case INTEGER_CST: 1366 return operand_equal_p (chrec0, chrec1, 0); 1367 1368 case POLYNOMIAL_CHREC: 1369 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) 1370 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) 1371 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); 1372 default: 1373 return false; 1374 } 1375} 1376 1377/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), 1378 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine 1379 which of these cases happens. */ 1380 1381enum ev_direction 1382scev_direction (tree chrec) 1383{ 1384 tree step; 1385 1386 if (!evolution_function_is_affine_p (chrec)) 1387 return EV_DIR_UNKNOWN; 1388 1389 step = CHREC_RIGHT (chrec); 1390 if (TREE_CODE (step) != INTEGER_CST) 1391 return EV_DIR_UNKNOWN; 1392 1393 if (tree_int_cst_sign_bit (step)) 1394 return EV_DIR_DECREASES; 1395 else 1396 return EV_DIR_GROWS; 1397} 1398