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