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