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