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