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