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