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