1/* Functions to determine/estimate number of iterations of a loop. 2 Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "tree.h" 26#include "rtl.h" 27#include "tm_p.h" 28#include "hard-reg-set.h" 29#include "basic-block.h" 30#include "output.h" 31#include "diagnostic.h" 32#include "intl.h" 33#include "tree-flow.h" 34#include "tree-dump.h" 35#include "cfgloop.h" 36#include "tree-pass.h" 37#include "ggc.h" 38#include "tree-chrec.h" 39#include "tree-scalar-evolution.h" 40#include "tree-data-ref.h" 41#include "params.h" 42#include "flags.h" 43#include "toplev.h" 44#include "tree-inline.h" 45 46#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) 47 48 49/* 50 51 Analysis of number of iterations of an affine exit test. 52 53*/ 54 55/* Returns true if ARG is either NULL_TREE or constant zero. Unlike 56 integer_zerop, it does not care about overflow flags. */ 57 58bool 59zero_p (tree arg) 60{ 61 if (!arg) 62 return true; 63 64 if (TREE_CODE (arg) != INTEGER_CST) 65 return false; 66 67 return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0); 68} 69 70/* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does 71 not care about overflow flags. */ 72 73static bool 74nonzero_p (tree arg) 75{ 76 if (!arg) 77 return false; 78 79 if (TREE_CODE (arg) != INTEGER_CST) 80 return false; 81 82 return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0); 83} 84 85/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ 86 87static tree 88inverse (tree x, tree mask) 89{ 90 tree type = TREE_TYPE (x); 91 tree rslt; 92 unsigned ctr = tree_floor_log2 (mask); 93 94 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) 95 { 96 unsigned HOST_WIDE_INT ix; 97 unsigned HOST_WIDE_INT imask; 98 unsigned HOST_WIDE_INT irslt = 1; 99 100 gcc_assert (cst_and_fits_in_hwi (x)); 101 gcc_assert (cst_and_fits_in_hwi (mask)); 102 103 ix = int_cst_value (x); 104 imask = int_cst_value (mask); 105 106 for (; ctr; ctr--) 107 { 108 irslt *= ix; 109 ix *= ix; 110 } 111 irslt &= imask; 112 113 rslt = build_int_cst_type (type, irslt); 114 } 115 else 116 { 117 rslt = build_int_cst (type, 1); 118 for (; ctr; ctr--) 119 { 120 rslt = int_const_binop (MULT_EXPR, rslt, x, 0); 121 x = int_const_binop (MULT_EXPR, x, x, 0); 122 } 123 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0); 124 } 125 126 return rslt; 127} 128 129/* Determines number of iterations of loop whose ending condition 130 is IV <> FINAL. TYPE is the type of the iv. The number of 131 iterations is stored to NITER. NEVER_INFINITE is true if 132 we know that the exit must be taken eventually, i.e., that the IV 133 ever reaches the value FINAL (we derived this earlier, and possibly set 134 NITER->assumptions to make sure this is the case). */ 135 136static bool 137number_of_iterations_ne (tree type, affine_iv *iv, tree final, 138 struct tree_niter_desc *niter, bool never_infinite) 139{ 140 tree niter_type = unsigned_type_for (type); 141 tree s, c, d, bits, assumption, tmp, bound; 142 143 niter->control = *iv; 144 niter->bound = final; 145 niter->cmp = NE_EXPR; 146 147 /* Rearrange the terms so that we get inequality s * i <> c, with s 148 positive. Also cast everything to the unsigned type. */ 149 if (tree_int_cst_sign_bit (iv->step)) 150 { 151 s = fold_convert (niter_type, 152 fold_build1 (NEGATE_EXPR, type, iv->step)); 153 c = fold_build2 (MINUS_EXPR, niter_type, 154 fold_convert (niter_type, iv->base), 155 fold_convert (niter_type, final)); 156 } 157 else 158 { 159 s = fold_convert (niter_type, iv->step); 160 c = fold_build2 (MINUS_EXPR, niter_type, 161 fold_convert (niter_type, final), 162 fold_convert (niter_type, iv->base)); 163 } 164 165 /* First the trivial cases -- when the step is 1. */ 166 if (integer_onep (s)) 167 { 168 niter->niter = c; 169 return true; 170 } 171 172 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop 173 is infinite. Otherwise, the number of iterations is 174 (inverse(s/d) * (c/d)) mod (size of mode/d). */ 175 bits = num_ending_zeros (s); 176 bound = build_low_bits_mask (niter_type, 177 (TYPE_PRECISION (niter_type) 178 - tree_low_cst (bits, 1))); 179 180 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, 181 build_int_cst (niter_type, 1), bits); 182 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits); 183 184 if (!never_infinite) 185 { 186 /* If we cannot assume that the loop is not infinite, record the 187 assumptions for divisibility of c. */ 188 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d); 189 assumption = fold_build2 (EQ_EXPR, boolean_type_node, 190 assumption, build_int_cst (niter_type, 0)); 191 if (!nonzero_p (assumption)) 192 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 193 niter->assumptions, assumption); 194 } 195 196 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); 197 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); 198 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); 199 return true; 200} 201 202/* Checks whether we can determine the final value of the control variable 203 of the loop with ending condition IV0 < IV1 (computed in TYPE). 204 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value 205 of the step. The assumptions necessary to ensure that the computation 206 of the final value does not overflow are recorded in NITER. If we 207 find the final value, we adjust DELTA and return TRUE. Otherwise 208 we return false. */ 209 210static bool 211number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, 212 struct tree_niter_desc *niter, 213 tree *delta, tree step) 214{ 215 tree niter_type = TREE_TYPE (step); 216 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); 217 tree tmod; 218 tree assumption = boolean_true_node, bound, noloop; 219 220 if (TREE_CODE (mod) != INTEGER_CST) 221 return false; 222 if (nonzero_p (mod)) 223 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); 224 tmod = fold_convert (type, mod); 225 226 if (nonzero_p (iv0->step)) 227 { 228 /* The final value of the iv is iv1->base + MOD, assuming that this 229 computation does not overflow, and that 230 iv0->base <= iv1->base + MOD. */ 231 if (!iv1->no_overflow && !zero_p (mod)) 232 { 233 bound = fold_build2 (MINUS_EXPR, type, 234 TYPE_MAX_VALUE (type), tmod); 235 assumption = fold_build2 (LE_EXPR, boolean_type_node, 236 iv1->base, bound); 237 if (zero_p (assumption)) 238 return false; 239 } 240 noloop = fold_build2 (GT_EXPR, boolean_type_node, 241 iv0->base, 242 fold_build2 (PLUS_EXPR, type, 243 iv1->base, tmod)); 244 } 245 else 246 { 247 /* The final value of the iv is iv0->base - MOD, assuming that this 248 computation does not overflow, and that 249 iv0->base - MOD <= iv1->base. */ 250 if (!iv0->no_overflow && !zero_p (mod)) 251 { 252 bound = fold_build2 (PLUS_EXPR, type, 253 TYPE_MIN_VALUE (type), tmod); 254 assumption = fold_build2 (GE_EXPR, boolean_type_node, 255 iv0->base, bound); 256 if (zero_p (assumption)) 257 return false; 258 } 259 noloop = fold_build2 (GT_EXPR, boolean_type_node, 260 fold_build2 (MINUS_EXPR, type, 261 iv0->base, tmod), 262 iv1->base); 263 } 264 265 if (!nonzero_p (assumption)) 266 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 267 niter->assumptions, 268 assumption); 269 if (!zero_p (noloop)) 270 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 271 niter->may_be_zero, 272 noloop); 273 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); 274 return true; 275} 276 277/* Add assertions to NITER that ensure that the control variable of the loop 278 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 279 are TYPE. Returns false if we can prove that there is an overflow, true 280 otherwise. STEP is the absolute value of the step. */ 281 282static bool 283assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, 284 struct tree_niter_desc *niter, tree step) 285{ 286 tree bound, d, assumption, diff; 287 tree niter_type = TREE_TYPE (step); 288 289 if (nonzero_p (iv0->step)) 290 { 291 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */ 292 if (iv0->no_overflow) 293 return true; 294 295 /* If iv0->base is a constant, we can determine the last value before 296 overflow precisely; otherwise we conservatively assume 297 MAX - STEP + 1. */ 298 299 if (TREE_CODE (iv0->base) == INTEGER_CST) 300 { 301 d = fold_build2 (MINUS_EXPR, niter_type, 302 fold_convert (niter_type, TYPE_MAX_VALUE (type)), 303 fold_convert (niter_type, iv0->base)); 304 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 305 } 306 else 307 diff = fold_build2 (MINUS_EXPR, niter_type, step, 308 build_int_cst (niter_type, 1)); 309 bound = fold_build2 (MINUS_EXPR, type, 310 TYPE_MAX_VALUE (type), fold_convert (type, diff)); 311 assumption = fold_build2 (LE_EXPR, boolean_type_node, 312 iv1->base, bound); 313 } 314 else 315 { 316 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */ 317 if (iv1->no_overflow) 318 return true; 319 320 if (TREE_CODE (iv1->base) == INTEGER_CST) 321 { 322 d = fold_build2 (MINUS_EXPR, niter_type, 323 fold_convert (niter_type, iv1->base), 324 fold_convert (niter_type, TYPE_MIN_VALUE (type))); 325 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 326 } 327 else 328 diff = fold_build2 (MINUS_EXPR, niter_type, step, 329 build_int_cst (niter_type, 1)); 330 bound = fold_build2 (PLUS_EXPR, type, 331 TYPE_MIN_VALUE (type), fold_convert (type, diff)); 332 assumption = fold_build2 (GE_EXPR, boolean_type_node, 333 iv0->base, bound); 334 } 335 336 if (zero_p (assumption)) 337 return false; 338 if (!nonzero_p (assumption)) 339 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 340 niter->assumptions, assumption); 341 342 iv0->no_overflow = true; 343 iv1->no_overflow = true; 344 return true; 345} 346 347/* Add an assumption to NITER that a loop whose ending condition 348 is IV0 < IV1 rolls. TYPE is the type of the control iv. */ 349 350static void 351assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, 352 struct tree_niter_desc *niter) 353{ 354 tree assumption = boolean_true_node, bound, diff; 355 tree mbz, mbzl, mbzr; 356 357 if (nonzero_p (iv0->step)) 358 { 359 diff = fold_build2 (MINUS_EXPR, type, 360 iv0->step, build_int_cst (type, 1)); 361 362 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since 363 0 address never belongs to any object, we can assume this for 364 pointers. */ 365 if (!POINTER_TYPE_P (type)) 366 { 367 bound = fold_build2 (PLUS_EXPR, type, 368 TYPE_MIN_VALUE (type), diff); 369 assumption = fold_build2 (GE_EXPR, boolean_type_node, 370 iv0->base, bound); 371 } 372 373 /* And then we can compute iv0->base - diff, and compare it with 374 iv1->base. */ 375 mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff); 376 mbzr = iv1->base; 377 } 378 else 379 { 380 diff = fold_build2 (PLUS_EXPR, type, 381 iv1->step, build_int_cst (type, 1)); 382 383 if (!POINTER_TYPE_P (type)) 384 { 385 bound = fold_build2 (PLUS_EXPR, type, 386 TYPE_MAX_VALUE (type), diff); 387 assumption = fold_build2 (LE_EXPR, boolean_type_node, 388 iv1->base, bound); 389 } 390 391 mbzl = iv0->base; 392 mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff); 393 } 394 395 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); 396 397 if (!nonzero_p (assumption)) 398 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 399 niter->assumptions, assumption); 400 if (!zero_p (mbz)) 401 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 402 niter->may_be_zero, mbz); 403} 404 405/* Determines number of iterations of loop whose ending condition 406 is IV0 < IV1. TYPE is the type of the iv. The number of 407 iterations is stored to NITER. */ 408 409static bool 410number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, 411 struct tree_niter_desc *niter, 412 bool never_infinite ATTRIBUTE_UNUSED) 413{ 414 tree niter_type = unsigned_type_for (type); 415 tree delta, step, s; 416 417 if (nonzero_p (iv0->step)) 418 { 419 niter->control = *iv0; 420 niter->cmp = LT_EXPR; 421 niter->bound = iv1->base; 422 } 423 else 424 { 425 niter->control = *iv1; 426 niter->cmp = GT_EXPR; 427 niter->bound = iv0->base; 428 } 429 430 delta = fold_build2 (MINUS_EXPR, niter_type, 431 fold_convert (niter_type, iv1->base), 432 fold_convert (niter_type, iv0->base)); 433 434 /* First handle the special case that the step is +-1. */ 435 if ((iv0->step && integer_onep (iv0->step) 436 && zero_p (iv1->step)) 437 || (iv1->step && integer_all_onesp (iv1->step) 438 && zero_p (iv0->step))) 439 { 440 /* for (i = iv0->base; i < iv1->base; i++) 441 442 or 443 444 for (i = iv1->base; i > iv0->base; i--). 445 446 In both cases # of iterations is iv1->base - iv0->base, assuming that 447 iv1->base >= iv0->base. */ 448 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, 449 iv1->base, iv0->base); 450 niter->niter = delta; 451 return true; 452 } 453 454 if (nonzero_p (iv0->step)) 455 step = fold_convert (niter_type, iv0->step); 456 else 457 step = fold_convert (niter_type, 458 fold_build1 (NEGATE_EXPR, type, iv1->step)); 459 460 /* If we can determine the final value of the control iv exactly, we can 461 transform the condition to != comparison. In particular, this will be 462 the case if DELTA is constant. */ 463 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step)) 464 { 465 affine_iv zps; 466 467 zps.base = build_int_cst (niter_type, 0); 468 zps.step = step; 469 /* number_of_iterations_lt_to_ne will add assumptions that ensure that 470 zps does not overflow. */ 471 zps.no_overflow = true; 472 473 return number_of_iterations_ne (type, &zps, delta, niter, true); 474 } 475 476 /* Make sure that the control iv does not overflow. */ 477 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step)) 478 return false; 479 480 /* We determine the number of iterations as (delta + step - 1) / step. For 481 this to work, we must know that iv1->base >= iv0->base - step + 1, 482 otherwise the loop does not roll. */ 483 assert_loop_rolls_lt (type, iv0, iv1, niter); 484 485 s = fold_build2 (MINUS_EXPR, niter_type, 486 step, build_int_cst (niter_type, 1)); 487 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); 488 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); 489 return true; 490} 491 492/* Determines number of iterations of loop whose ending condition 493 is IV0 <= IV1. TYPE is the type of the iv. The number of 494 iterations is stored to NITER. NEVER_INFINITE is true if 495 we know that this condition must eventually become false (we derived this 496 earlier, and possibly set NITER->assumptions to make sure this 497 is the case). */ 498 499static bool 500number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, 501 struct tree_niter_desc *niter, bool never_infinite) 502{ 503 tree assumption; 504 505 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff 506 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest 507 value of the type. This we must know anyway, since if it is 508 equal to this value, the loop rolls forever. */ 509 510 if (!never_infinite) 511 { 512 if (nonzero_p (iv0->step)) 513 assumption = fold_build2 (NE_EXPR, boolean_type_node, 514 iv1->base, TYPE_MAX_VALUE (type)); 515 else 516 assumption = fold_build2 (NE_EXPR, boolean_type_node, 517 iv0->base, TYPE_MIN_VALUE (type)); 518 519 if (zero_p (assumption)) 520 return false; 521 if (!nonzero_p (assumption)) 522 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 523 niter->assumptions, assumption); 524 } 525 526 if (nonzero_p (iv0->step)) 527 iv1->base = fold_build2 (PLUS_EXPR, type, 528 iv1->base, build_int_cst (type, 1)); 529 else 530 iv0->base = fold_build2 (MINUS_EXPR, type, 531 iv0->base, build_int_cst (type, 1)); 532 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); 533} 534 535/* Determine the number of iterations according to condition (for staying 536 inside loop) which compares two induction variables using comparison 537 operator CODE. The induction variable on left side of the comparison 538 is IV0, the right-hand side is IV1. Both induction variables must have 539 type TYPE, which must be an integer or pointer type. The steps of the 540 ivs must be constants (or NULL_TREE, which is interpreted as constant zero). 541 542 ONLY_EXIT is true if we are sure this is the only way the loop could be 543 exited (including possibly non-returning function calls, exceptions, etc.) 544 -- in this case we can use the information whether the control induction 545 variables can overflow or not in a more efficient way. 546 547 The results (number of iterations and assumptions as described in 548 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. 549 Returns false if it fails to determine number of iterations, true if it 550 was determined (possibly with some assumptions). */ 551 552static bool 553number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, 554 affine_iv *iv1, struct tree_niter_desc *niter, 555 bool only_exit) 556{ 557 bool never_infinite; 558 559 /* The meaning of these assumptions is this: 560 if !assumptions 561 then the rest of information does not have to be valid 562 if may_be_zero then the loop does not roll, even if 563 niter != 0. */ 564 niter->assumptions = boolean_true_node; 565 niter->may_be_zero = boolean_false_node; 566 niter->niter = NULL_TREE; 567 niter->additional_info = boolean_true_node; 568 569 niter->bound = NULL_TREE; 570 niter->cmp = ERROR_MARK; 571 572 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that 573 the control variable is on lhs. */ 574 if (code == GE_EXPR || code == GT_EXPR 575 || (code == NE_EXPR && zero_p (iv0->step))) 576 { 577 SWAP (iv0, iv1); 578 code = swap_tree_comparison (code); 579 } 580 581 if (!only_exit) 582 { 583 /* If this is not the only possible exit from the loop, the information 584 that the induction variables cannot overflow as derived from 585 signedness analysis cannot be relied upon. We use them e.g. in the 586 following way: given loop for (i = 0; i <= n; i++), if i is 587 signed, it cannot overflow, thus this loop is equivalent to 588 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop 589 is exited in some other way before i overflows, this transformation 590 is incorrect (the new loop exits immediately). */ 591 iv0->no_overflow = false; 592 iv1->no_overflow = false; 593 } 594 595 if (POINTER_TYPE_P (type)) 596 { 597 /* Comparison of pointers is undefined unless both iv0 and iv1 point 598 to the same object. If they do, the control variable cannot wrap 599 (as wrap around the bounds of memory will never return a pointer 600 that would be guaranteed to point to the same object, even if we 601 avoid undefined behavior by casting to size_t and back). The 602 restrictions on pointer arithmetics and comparisons of pointers 603 ensure that using the no-overflow assumptions is correct in this 604 case even if ONLY_EXIT is false. */ 605 iv0->no_overflow = true; 606 iv1->no_overflow = true; 607 } 608 609 /* If the control induction variable does not overflow, the loop obviously 610 cannot be infinite. */ 611 if (!zero_p (iv0->step) && iv0->no_overflow) 612 never_infinite = true; 613 else if (!zero_p (iv1->step) && iv1->no_overflow) 614 never_infinite = true; 615 else 616 never_infinite = false; 617 618 /* We can handle the case when neither of the sides of the comparison is 619 invariant, provided that the test is NE_EXPR. This rarely occurs in 620 practice, but it is simple enough to manage. */ 621 if (!zero_p (iv0->step) && !zero_p (iv1->step)) 622 { 623 if (code != NE_EXPR) 624 return false; 625 626 iv0->step = fold_binary_to_constant (MINUS_EXPR, type, 627 iv0->step, iv1->step); 628 iv0->no_overflow = false; 629 iv1->step = NULL_TREE; 630 iv1->no_overflow = true; 631 } 632 633 /* If the result of the comparison is a constant, the loop is weird. More 634 precise handling would be possible, but the situation is not common enough 635 to waste time on it. */ 636 if (zero_p (iv0->step) && zero_p (iv1->step)) 637 return false; 638 639 /* Ignore loops of while (i-- < 10) type. */ 640 if (code != NE_EXPR) 641 { 642 if (iv0->step && tree_int_cst_sign_bit (iv0->step)) 643 return false; 644 645 if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) 646 return false; 647 } 648 649 /* If the loop exits immediately, there is nothing to do. */ 650 if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) 651 { 652 niter->niter = build_int_cst (unsigned_type_for (type), 0); 653 return true; 654 } 655 656 /* OK, now we know we have a senseful loop. Handle several cases, depending 657 on what comparison operator is used. */ 658 switch (code) 659 { 660 case NE_EXPR: 661 gcc_assert (zero_p (iv1->step)); 662 return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite); 663 case LT_EXPR: 664 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); 665 case LE_EXPR: 666 return number_of_iterations_le (type, iv0, iv1, niter, never_infinite); 667 default: 668 gcc_unreachable (); 669 } 670} 671 672/* Substitute NEW for OLD in EXPR and fold the result. */ 673 674static tree 675simplify_replace_tree (tree expr, tree old, tree new) 676{ 677 unsigned i, n; 678 tree ret = NULL_TREE, e, se; 679 680 if (!expr) 681 return NULL_TREE; 682 683 if (expr == old 684 || operand_equal_p (expr, old, 0)) 685 return unshare_expr (new); 686 687 if (!EXPR_P (expr)) 688 return expr; 689 690 n = TREE_CODE_LENGTH (TREE_CODE (expr)); 691 for (i = 0; i < n; i++) 692 { 693 e = TREE_OPERAND (expr, i); 694 se = simplify_replace_tree (e, old, new); 695 if (e == se) 696 continue; 697 698 if (!ret) 699 ret = copy_node (expr); 700 701 TREE_OPERAND (ret, i) = se; 702 } 703 704 return (ret ? fold (ret) : expr); 705} 706 707/* Expand definitions of ssa names in EXPR as long as they are simple 708 enough, and return the new expression. */ 709 710tree 711expand_simple_operations (tree expr) 712{ 713 unsigned i, n; 714 tree ret = NULL_TREE, e, ee, stmt; 715 enum tree_code code; 716 717 if (expr == NULL_TREE) 718 return expr; 719 720 if (is_gimple_min_invariant (expr)) 721 return expr; 722 723 code = TREE_CODE (expr); 724 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) 725 { 726 n = TREE_CODE_LENGTH (code); 727 for (i = 0; i < n; i++) 728 { 729 e = TREE_OPERAND (expr, i); 730 ee = expand_simple_operations (e); 731 if (e == ee) 732 continue; 733 734 if (!ret) 735 ret = copy_node (expr); 736 737 TREE_OPERAND (ret, i) = ee; 738 } 739 740 if (!ret) 741 return expr; 742 743 fold_defer_overflow_warnings (); 744 ret = fold (ret); 745 fold_undefer_and_ignore_overflow_warnings (); 746 return ret; 747 } 748 749 if (TREE_CODE (expr) != SSA_NAME) 750 return expr; 751 752 stmt = SSA_NAME_DEF_STMT (expr); 753 if (TREE_CODE (stmt) != MODIFY_EXPR) 754 return expr; 755 756 e = TREE_OPERAND (stmt, 1); 757 if (/* Casts are simple. */ 758 TREE_CODE (e) != NOP_EXPR 759 && TREE_CODE (e) != CONVERT_EXPR 760 /* Copies are simple. */ 761 && TREE_CODE (e) != SSA_NAME 762 /* Assignments of invariants are simple. */ 763 && !is_gimple_min_invariant (e) 764 /* And increments and decrements by a constant are simple. */ 765 && !((TREE_CODE (e) == PLUS_EXPR 766 || TREE_CODE (e) == MINUS_EXPR) 767 && is_gimple_min_invariant (TREE_OPERAND (e, 1)))) 768 return expr; 769 770 return expand_simple_operations (e); 771} 772 773/* Tries to simplify EXPR using the condition COND. Returns the simplified 774 expression (or EXPR unchanged, if no simplification was possible). */ 775 776static tree 777tree_simplify_using_condition_1 (tree cond, tree expr) 778{ 779 bool changed; 780 tree e, te, e0, e1, e2, notcond; 781 enum tree_code code = TREE_CODE (expr); 782 783 if (code == INTEGER_CST) 784 return expr; 785 786 if (code == TRUTH_OR_EXPR 787 || code == TRUTH_AND_EXPR 788 || code == COND_EXPR) 789 { 790 changed = false; 791 792 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); 793 if (TREE_OPERAND (expr, 0) != e0) 794 changed = true; 795 796 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); 797 if (TREE_OPERAND (expr, 1) != e1) 798 changed = true; 799 800 if (code == COND_EXPR) 801 { 802 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); 803 if (TREE_OPERAND (expr, 2) != e2) 804 changed = true; 805 } 806 else 807 e2 = NULL_TREE; 808 809 if (changed) 810 { 811 if (code == COND_EXPR) 812 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 813 else 814 expr = fold_build2 (code, boolean_type_node, e0, e1); 815 } 816 817 return expr; 818 } 819 820 /* In case COND is equality, we may be able to simplify EXPR by copy/constant 821 propagation, and vice versa. Fold does not handle this, since it is 822 considered too expensive. */ 823 if (TREE_CODE (cond) == EQ_EXPR) 824 { 825 e0 = TREE_OPERAND (cond, 0); 826 e1 = TREE_OPERAND (cond, 1); 827 828 /* We know that e0 == e1. Check whether we cannot simplify expr 829 using this fact. */ 830 e = simplify_replace_tree (expr, e0, e1); 831 if (zero_p (e) || nonzero_p (e)) 832 return e; 833 834 e = simplify_replace_tree (expr, e1, e0); 835 if (zero_p (e) || nonzero_p (e)) 836 return e; 837 } 838 if (TREE_CODE (expr) == EQ_EXPR) 839 { 840 e0 = TREE_OPERAND (expr, 0); 841 e1 = TREE_OPERAND (expr, 1); 842 843 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ 844 e = simplify_replace_tree (cond, e0, e1); 845 if (zero_p (e)) 846 return e; 847 e = simplify_replace_tree (cond, e1, e0); 848 if (zero_p (e)) 849 return e; 850 } 851 if (TREE_CODE (expr) == NE_EXPR) 852 { 853 e0 = TREE_OPERAND (expr, 0); 854 e1 = TREE_OPERAND (expr, 1); 855 856 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ 857 e = simplify_replace_tree (cond, e0, e1); 858 if (zero_p (e)) 859 return boolean_true_node; 860 e = simplify_replace_tree (cond, e1, e0); 861 if (zero_p (e)) 862 return boolean_true_node; 863 } 864 865 te = expand_simple_operations (expr); 866 867 /* Check whether COND ==> EXPR. */ 868 notcond = invert_truthvalue (cond); 869 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te); 870 if (nonzero_p (e)) 871 return e; 872 873 /* Check whether COND ==> not EXPR. */ 874 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); 875 if (e && zero_p (e)) 876 return e; 877 878 return expr; 879} 880 881/* Tries to simplify EXPR using the condition COND. Returns the simplified 882 expression (or EXPR unchanged, if no simplification was possible). 883 Wrapper around tree_simplify_using_condition_1 that ensures that chains 884 of simple operations in definitions of ssa names in COND are expanded, 885 so that things like casts or incrementing the value of the bound before 886 the loop do not cause us to fail. */ 887 888static tree 889tree_simplify_using_condition (tree cond, tree expr) 890{ 891 cond = expand_simple_operations (cond); 892 893 return tree_simplify_using_condition_1 (cond, expr); 894} 895 896/* The maximum number of dominator BBs we search for conditions 897 of loop header copies we use for simplifying a conditional 898 expression. */ 899#define MAX_DOMINATORS_TO_WALK 8 900 901/* Tries to simplify EXPR using the conditions on entry to LOOP. 902 Record the conditions used for simplification to CONDS_USED. 903 Returns the simplified expression (or EXPR unchanged, if no 904 simplification was possible).*/ 905 906static tree 907simplify_using_initial_conditions (struct loop *loop, tree expr, 908 tree *conds_used) 909{ 910 edge e; 911 basic_block bb; 912 tree exp, cond; 913 int cnt = 0; 914 915 if (TREE_CODE (expr) == INTEGER_CST) 916 return expr; 917 918 /* Limit walking the dominators to avoid quadraticness in 919 the number of BBs times the number of loops in degenerate 920 cases. */ 921 for (bb = loop->header; 922 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; 923 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 924 { 925 if (!single_pred_p (bb)) 926 continue; 927 e = single_pred_edge (bb); 928 929 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 930 continue; 931 932 cond = COND_EXPR_COND (last_stmt (e->src)); 933 if (e->flags & EDGE_FALSE_VALUE) 934 cond = invert_truthvalue (cond); 935 exp = tree_simplify_using_condition (cond, expr); 936 937 if (exp != expr) 938 *conds_used = fold_build2 (TRUTH_AND_EXPR, 939 boolean_type_node, 940 *conds_used, 941 cond); 942 943 expr = exp; 944 ++cnt; 945 } 946 947 return expr; 948} 949 950/* Tries to simplify EXPR using the evolutions of the loop invariants 951 in the superloops of LOOP. Returns the simplified expression 952 (or EXPR unchanged, if no simplification was possible). */ 953 954static tree 955simplify_using_outer_evolutions (struct loop *loop, tree expr) 956{ 957 enum tree_code code = TREE_CODE (expr); 958 bool changed; 959 tree e, e0, e1, e2; 960 961 if (is_gimple_min_invariant (expr)) 962 return expr; 963 964 if (code == TRUTH_OR_EXPR 965 || code == TRUTH_AND_EXPR 966 || code == COND_EXPR) 967 { 968 changed = false; 969 970 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); 971 if (TREE_OPERAND (expr, 0) != e0) 972 changed = true; 973 974 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); 975 if (TREE_OPERAND (expr, 1) != e1) 976 changed = true; 977 978 if (code == COND_EXPR) 979 { 980 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); 981 if (TREE_OPERAND (expr, 2) != e2) 982 changed = true; 983 } 984 else 985 e2 = NULL_TREE; 986 987 if (changed) 988 { 989 if (code == COND_EXPR) 990 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 991 else 992 expr = fold_build2 (code, boolean_type_node, e0, e1); 993 } 994 995 return expr; 996 } 997 998 e = instantiate_parameters (loop, expr); 999 if (is_gimple_min_invariant (e)) 1000 return e; 1001 1002 return expr; 1003} 1004 1005/* Returns true if EXIT is the only possible exit from LOOP. */ 1006 1007static bool 1008loop_only_exit_p (struct loop *loop, edge exit) 1009{ 1010 basic_block *body; 1011 block_stmt_iterator bsi; 1012 unsigned i; 1013 tree call; 1014 1015 if (exit != loop->single_exit) 1016 return false; 1017 1018 body = get_loop_body (loop); 1019 for (i = 0; i < loop->num_nodes; i++) 1020 { 1021 for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi)) 1022 { 1023 call = get_call_expr_in (bsi_stmt (bsi)); 1024 if (call && TREE_SIDE_EFFECTS (call)) 1025 { 1026 free (body); 1027 return false; 1028 } 1029 } 1030 } 1031 1032 free (body); 1033 return true; 1034} 1035 1036/* Stores description of number of iterations of LOOP derived from 1037 EXIT (an exit edge of the LOOP) in NITER. Returns true if some 1038 useful information could be derived (and fields of NITER has 1039 meaning described in comments at struct tree_niter_desc 1040 declaration), false otherwise. If WARN is true and 1041 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use 1042 potentially unsafe assumptions. */ 1043 1044bool 1045number_of_iterations_exit (struct loop *loop, edge exit, 1046 struct tree_niter_desc *niter, 1047 bool warn) 1048{ 1049 tree stmt, cond, type; 1050 tree op0, op1; 1051 enum tree_code code; 1052 affine_iv iv0, iv1; 1053 1054 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) 1055 return false; 1056 1057 niter->assumptions = boolean_false_node; 1058 stmt = last_stmt (exit->src); 1059 if (!stmt || TREE_CODE (stmt) != COND_EXPR) 1060 return false; 1061 1062 /* We want the condition for staying inside loop. */ 1063 cond = COND_EXPR_COND (stmt); 1064 if (exit->flags & EDGE_TRUE_VALUE) 1065 cond = invert_truthvalue (cond); 1066 1067 code = TREE_CODE (cond); 1068 switch (code) 1069 { 1070 case GT_EXPR: 1071 case GE_EXPR: 1072 case NE_EXPR: 1073 case LT_EXPR: 1074 case LE_EXPR: 1075 break; 1076 1077 default: 1078 return false; 1079 } 1080 1081 op0 = TREE_OPERAND (cond, 0); 1082 op1 = TREE_OPERAND (cond, 1); 1083 type = TREE_TYPE (op0); 1084 1085 if (TREE_CODE (type) != INTEGER_TYPE 1086 && !POINTER_TYPE_P (type)) 1087 return false; 1088 1089 if (!simple_iv (loop, stmt, op0, &iv0, false)) 1090 return false; 1091 if (!simple_iv (loop, stmt, op1, &iv1, false)) 1092 return false; 1093 1094 /* We don't want to see undefined signed overflow warnings while 1095 computing the nmber of iterations. */ 1096 fold_defer_overflow_warnings (); 1097 1098 iv0.base = expand_simple_operations (iv0.base); 1099 iv1.base = expand_simple_operations (iv1.base); 1100 if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter, 1101 loop_only_exit_p (loop, exit))) 1102 { 1103 fold_undefer_and_ignore_overflow_warnings (); 1104 return false; 1105 } 1106 1107 if (optimize >= 3) 1108 { 1109 niter->assumptions = simplify_using_outer_evolutions (loop, 1110 niter->assumptions); 1111 niter->may_be_zero = simplify_using_outer_evolutions (loop, 1112 niter->may_be_zero); 1113 niter->niter = simplify_using_outer_evolutions (loop, niter->niter); 1114 } 1115 1116 niter->additional_info = boolean_true_node; 1117 niter->assumptions 1118 = simplify_using_initial_conditions (loop, 1119 niter->assumptions, 1120 &niter->additional_info); 1121 niter->may_be_zero 1122 = simplify_using_initial_conditions (loop, 1123 niter->may_be_zero, 1124 &niter->additional_info); 1125 1126 fold_undefer_and_ignore_overflow_warnings (); 1127 1128 if (integer_onep (niter->assumptions)) 1129 return true; 1130 1131 /* With -funsafe-loop-optimizations we assume that nothing bad can happen. 1132 But if we can prove that there is overflow or some other source of weird 1133 behavior, ignore the loop even with -funsafe-loop-optimizations. */ 1134 if (integer_zerop (niter->assumptions)) 1135 return false; 1136 1137 if (flag_unsafe_loop_optimizations) 1138 niter->assumptions = boolean_true_node; 1139 1140 if (warn) 1141 { 1142 const char *wording; 1143 location_t loc = EXPR_LOCATION (stmt); 1144 1145 /* We can provide a more specific warning if one of the operator is 1146 constant and the other advances by +1 or -1. */ 1147 if (!zero_p (iv1.step) 1148 ? (zero_p (iv0.step) 1149 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) 1150 : (iv0.step 1151 && (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))) 1152 wording = 1153 flag_unsafe_loop_optimizations 1154 ? N_("assuming that the loop is not infinite") 1155 : N_("cannot optimize possibly infinite loops"); 1156 else 1157 wording = 1158 flag_unsafe_loop_optimizations 1159 ? N_("assuming that the loop counter does not overflow") 1160 : N_("cannot optimize loop, the loop counter may overflow"); 1161 1162 if (LOCATION_LINE (loc) > 0) 1163 warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording)); 1164 else 1165 warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); 1166 } 1167 1168 return flag_unsafe_loop_optimizations; 1169} 1170 1171/* Try to determine the number of iterations of LOOP. If we succeed, 1172 expression giving number of iterations is returned and *EXIT is 1173 set to the edge from that the information is obtained. Otherwise 1174 chrec_dont_know is returned. */ 1175 1176tree 1177find_loop_niter (struct loop *loop, edge *exit) 1178{ 1179 unsigned n_exits, i; 1180 edge *exits = get_loop_exit_edges (loop, &n_exits); 1181 edge ex; 1182 tree niter = NULL_TREE, aniter; 1183 struct tree_niter_desc desc; 1184 1185 *exit = NULL; 1186 for (i = 0; i < n_exits; i++) 1187 { 1188 ex = exits[i]; 1189 if (!just_once_each_iteration_p (loop, ex->src)) 1190 continue; 1191 1192 if (!number_of_iterations_exit (loop, ex, &desc, false)) 1193 continue; 1194 1195 if (nonzero_p (desc.may_be_zero)) 1196 { 1197 /* We exit in the first iteration through this exit. 1198 We won't find anything better. */ 1199 niter = build_int_cst (unsigned_type_node, 0); 1200 *exit = ex; 1201 break; 1202 } 1203 1204 if (!zero_p (desc.may_be_zero)) 1205 continue; 1206 1207 aniter = desc.niter; 1208 1209 if (!niter) 1210 { 1211 /* Nothing recorded yet. */ 1212 niter = aniter; 1213 *exit = ex; 1214 continue; 1215 } 1216 1217 /* Prefer constants, the lower the better. */ 1218 if (TREE_CODE (aniter) != INTEGER_CST) 1219 continue; 1220 1221 if (TREE_CODE (niter) != INTEGER_CST) 1222 { 1223 niter = aniter; 1224 *exit = ex; 1225 continue; 1226 } 1227 1228 if (tree_int_cst_lt (aniter, niter)) 1229 { 1230 niter = aniter; 1231 *exit = ex; 1232 continue; 1233 } 1234 } 1235 free (exits); 1236 1237 return niter ? niter : chrec_dont_know; 1238} 1239 1240/* 1241 1242 Analysis of a number of iterations of a loop by a brute-force evaluation. 1243 1244*/ 1245 1246/* Bound on the number of iterations we try to evaluate. */ 1247 1248#define MAX_ITERATIONS_TO_TRACK \ 1249 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) 1250 1251/* Returns the loop phi node of LOOP such that ssa name X is derived from its 1252 result by a chain of operations such that all but exactly one of their 1253 operands are constants. */ 1254 1255static tree 1256chain_of_csts_start (struct loop *loop, tree x) 1257{ 1258 tree stmt = SSA_NAME_DEF_STMT (x); 1259 tree use; 1260 basic_block bb = bb_for_stmt (stmt); 1261 1262 if (!bb 1263 || !flow_bb_inside_loop_p (loop, bb)) 1264 return NULL_TREE; 1265 1266 if (TREE_CODE (stmt) == PHI_NODE) 1267 { 1268 if (bb == loop->header) 1269 return stmt; 1270 1271 return NULL_TREE; 1272 } 1273 1274 if (TREE_CODE (stmt) != MODIFY_EXPR) 1275 return NULL_TREE; 1276 1277 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 1278 return NULL_TREE; 1279 if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P) 1280 return NULL_TREE; 1281 1282 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); 1283 if (use == NULL_USE_OPERAND_P) 1284 return NULL_TREE; 1285 1286 return chain_of_csts_start (loop, use); 1287} 1288 1289/* Determines whether the expression X is derived from a result of a phi node 1290 in header of LOOP such that 1291 1292 * the derivation of X consists only from operations with constants 1293 * the initial value of the phi node is constant 1294 * the value of the phi node in the next iteration can be derived from the 1295 value in the current iteration by a chain of operations with constants. 1296 1297 If such phi node exists, it is returned. If X is a constant, X is returned 1298 unchanged. Otherwise NULL_TREE is returned. */ 1299 1300static tree 1301get_base_for (struct loop *loop, tree x) 1302{ 1303 tree phi, init, next; 1304 1305 if (is_gimple_min_invariant (x)) 1306 return x; 1307 1308 phi = chain_of_csts_start (loop, x); 1309 if (!phi) 1310 return NULL_TREE; 1311 1312 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 1313 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 1314 1315 if (TREE_CODE (next) != SSA_NAME) 1316 return NULL_TREE; 1317 1318 if (!is_gimple_min_invariant (init)) 1319 return NULL_TREE; 1320 1321 if (chain_of_csts_start (loop, next) != phi) 1322 return NULL_TREE; 1323 1324 return phi; 1325} 1326 1327/* Given an expression X, then 1328 1329 * if X is NULL_TREE, we return the constant BASE. 1330 * otherwise X is a SSA name, whose value in the considered loop is derived 1331 by a chain of operations with constant from a result of a phi node in 1332 the header of the loop. Then we return value of X when the value of the 1333 result of this phi node is given by the constant BASE. */ 1334 1335static tree 1336get_val_for (tree x, tree base) 1337{ 1338 tree stmt, nx, val; 1339 use_operand_p op; 1340 ssa_op_iter iter; 1341 1342 gcc_assert (is_gimple_min_invariant (base)); 1343 1344 if (!x) 1345 return base; 1346 1347 stmt = SSA_NAME_DEF_STMT (x); 1348 if (TREE_CODE (stmt) == PHI_NODE) 1349 return base; 1350 1351 FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE) 1352 { 1353 nx = USE_FROM_PTR (op); 1354 val = get_val_for (nx, base); 1355 SET_USE (op, val); 1356 val = fold (TREE_OPERAND (stmt, 1)); 1357 SET_USE (op, nx); 1358 /* only iterate loop once. */ 1359 return val; 1360 } 1361 1362 /* Should never reach here. */ 1363 gcc_unreachable(); 1364} 1365 1366/* Tries to count the number of iterations of LOOP till it exits by EXIT 1367 by brute force -- i.e. by determining the value of the operands of the 1368 condition at EXIT in first few iterations of the loop (assuming that 1369 these values are constant) and determining the first one in that the 1370 condition is not satisfied. Returns the constant giving the number 1371 of the iterations of LOOP if successful, chrec_dont_know otherwise. */ 1372 1373tree 1374loop_niter_by_eval (struct loop *loop, edge exit) 1375{ 1376 tree cond, cnd, acnd; 1377 tree op[2], val[2], next[2], aval[2], phi[2]; 1378 unsigned i, j; 1379 enum tree_code cmp; 1380 1381 cond = last_stmt (exit->src); 1382 if (!cond || TREE_CODE (cond) != COND_EXPR) 1383 return chrec_dont_know; 1384 1385 cnd = COND_EXPR_COND (cond); 1386 if (exit->flags & EDGE_TRUE_VALUE) 1387 cnd = invert_truthvalue (cnd); 1388 1389 cmp = TREE_CODE (cnd); 1390 switch (cmp) 1391 { 1392 case EQ_EXPR: 1393 case NE_EXPR: 1394 case GT_EXPR: 1395 case GE_EXPR: 1396 case LT_EXPR: 1397 case LE_EXPR: 1398 for (j = 0; j < 2; j++) 1399 op[j] = TREE_OPERAND (cnd, j); 1400 break; 1401 1402 default: 1403 return chrec_dont_know; 1404 } 1405 1406 for (j = 0; j < 2; j++) 1407 { 1408 phi[j] = get_base_for (loop, op[j]); 1409 if (!phi[j]) 1410 return chrec_dont_know; 1411 } 1412 1413 for (j = 0; j < 2; j++) 1414 { 1415 if (TREE_CODE (phi[j]) == PHI_NODE) 1416 { 1417 val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop)); 1418 next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop)); 1419 } 1420 else 1421 { 1422 val[j] = phi[j]; 1423 next[j] = NULL_TREE; 1424 op[j] = NULL_TREE; 1425 } 1426 } 1427 1428 /* Don't issue signed overflow warnings. */ 1429 fold_defer_overflow_warnings (); 1430 1431 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) 1432 { 1433 for (j = 0; j < 2; j++) 1434 aval[j] = get_val_for (op[j], val[j]); 1435 1436 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]); 1437 if (acnd && zero_p (acnd)) 1438 { 1439 fold_undefer_and_ignore_overflow_warnings (); 1440 if (dump_file && (dump_flags & TDF_DETAILS)) 1441 fprintf (dump_file, 1442 "Proved that loop %d iterates %d times using brute force.\n", 1443 loop->num, i); 1444 return build_int_cst (unsigned_type_node, i); 1445 } 1446 1447 for (j = 0; j < 2; j++) 1448 { 1449 val[j] = get_val_for (next[j], val[j]); 1450 if (!is_gimple_min_invariant (val[j])) 1451 { 1452 fold_undefer_and_ignore_overflow_warnings (); 1453 return chrec_dont_know; 1454 } 1455 } 1456 } 1457 1458 fold_undefer_and_ignore_overflow_warnings (); 1459 1460 return chrec_dont_know; 1461} 1462 1463/* Finds the exit of the LOOP by that the loop exits after a constant 1464 number of iterations and stores the exit edge to *EXIT. The constant 1465 giving the number of iterations of LOOP is returned. The number of 1466 iterations is determined using loop_niter_by_eval (i.e. by brute force 1467 evaluation). If we are unable to find the exit for that loop_niter_by_eval 1468 determines the number of iterations, chrec_dont_know is returned. */ 1469 1470tree 1471find_loop_niter_by_eval (struct loop *loop, edge *exit) 1472{ 1473 unsigned n_exits, i; 1474 edge *exits = get_loop_exit_edges (loop, &n_exits); 1475 edge ex; 1476 tree niter = NULL_TREE, aniter; 1477 1478 *exit = NULL; 1479 for (i = 0; i < n_exits; i++) 1480 { 1481 ex = exits[i]; 1482 if (!just_once_each_iteration_p (loop, ex->src)) 1483 continue; 1484 1485 aniter = loop_niter_by_eval (loop, ex); 1486 if (chrec_contains_undetermined (aniter)) 1487 continue; 1488 1489 if (niter 1490 && !tree_int_cst_lt (aniter, niter)) 1491 continue; 1492 1493 niter = aniter; 1494 *exit = ex; 1495 } 1496 free (exits); 1497 1498 return niter ? niter : chrec_dont_know; 1499} 1500 1501/* 1502 1503 Analysis of upper bounds on number of iterations of a loop. 1504 1505*/ 1506 1507/* Returns true if we can prove that COND ==> VAL >= 0. */ 1508 1509static bool 1510implies_nonnegative_p (tree cond, tree val) 1511{ 1512 tree type = TREE_TYPE (val); 1513 tree compare; 1514 1515 if (tree_expr_nonnegative_p (val)) 1516 return true; 1517 1518 if (nonzero_p (cond)) 1519 return false; 1520 1521 compare = fold_build2 (GE_EXPR, 1522 boolean_type_node, val, build_int_cst (type, 0)); 1523 compare = tree_simplify_using_condition_1 (cond, compare); 1524 1525 return nonzero_p (compare); 1526} 1527 1528/* Returns true if we can prove that COND ==> A >= B. */ 1529 1530static bool 1531implies_ge_p (tree cond, tree a, tree b) 1532{ 1533 tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b); 1534 1535 if (nonzero_p (compare)) 1536 return true; 1537 1538 if (nonzero_p (cond)) 1539 return false; 1540 1541 compare = tree_simplify_using_condition_1 (cond, compare); 1542 1543 return nonzero_p (compare); 1544} 1545 1546/* Returns a constant upper bound on the value of expression VAL. VAL 1547 is considered to be unsigned. If its type is signed, its value must 1548 be nonnegative. 1549 1550 The condition ADDITIONAL must be satisfied (for example, if VAL is 1551 "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that 1552 VAL is at most (unsigned) MAX_INT). */ 1553 1554static double_int 1555derive_constant_upper_bound (tree val, tree additional) 1556{ 1557 tree type = TREE_TYPE (val); 1558 tree op0, op1, subtype, maxt; 1559 double_int bnd, max, mmax, cst; 1560 1561 if (INTEGRAL_TYPE_P (type)) 1562 maxt = TYPE_MAX_VALUE (type); 1563 else 1564 maxt = upper_bound_in_type (type, type); 1565 1566 max = tree_to_double_int (maxt); 1567 1568 switch (TREE_CODE (val)) 1569 { 1570 case INTEGER_CST: 1571 return tree_to_double_int (val); 1572 1573 case NOP_EXPR: 1574 case CONVERT_EXPR: 1575 op0 = TREE_OPERAND (val, 0); 1576 subtype = TREE_TYPE (op0); 1577 if (!TYPE_UNSIGNED (subtype) 1578 /* If TYPE is also signed, the fact that VAL is nonnegative implies 1579 that OP0 is nonnegative. */ 1580 && TYPE_UNSIGNED (type) 1581 && !implies_nonnegative_p (additional, op0)) 1582 { 1583 /* If we cannot prove that the casted expression is nonnegative, 1584 we cannot establish more useful upper bound than the precision 1585 of the type gives us. */ 1586 return max; 1587 } 1588 1589 /* We now know that op0 is an nonnegative value. Try deriving an upper 1590 bound for it. */ 1591 bnd = derive_constant_upper_bound (op0, additional); 1592 1593 /* If the bound does not fit in TYPE, max. value of TYPE could be 1594 attained. */ 1595 if (double_int_ucmp (max, bnd) < 0) 1596 return max; 1597 1598 return bnd; 1599 1600 case PLUS_EXPR: 1601 case MINUS_EXPR: 1602 op0 = TREE_OPERAND (val, 0); 1603 op1 = TREE_OPERAND (val, 1); 1604 1605 if (TREE_CODE (op1) != INTEGER_CST 1606 || !implies_nonnegative_p (additional, op0)) 1607 return max; 1608 1609 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to 1610 choose the most logical way how to treat this constant regardless 1611 of the signedness of the type. */ 1612 cst = tree_to_double_int (op1); 1613 cst = double_int_sext (cst, TYPE_PRECISION (type)); 1614 if (TREE_CODE (val) == PLUS_EXPR) 1615 cst = double_int_neg (cst); 1616 1617 bnd = derive_constant_upper_bound (op0, additional); 1618 1619 if (double_int_negative_p (cst)) 1620 { 1621 cst = double_int_neg (cst); 1622 /* Avoid CST == 0x80000... */ 1623 if (double_int_negative_p (cst)) 1624 return max;; 1625 1626 /* OP0 + CST. We need to check that 1627 BND <= MAX (type) - CST. */ 1628 1629 mmax = double_int_add (max, double_int_neg (cst)); 1630 if (double_int_ucmp (bnd, mmax) > 0) 1631 return max; 1632 1633 return double_int_add (bnd, cst); 1634 } 1635 else 1636 { 1637 /* OP0 - CST, where CST >= 0. 1638 1639 If TYPE is signed, we have already verified that OP0 >= 0, and we 1640 know that the result is nonnegative. This implies that 1641 VAL <= BND - CST. 1642 1643 If TYPE is unsigned, we must additionally know that OP0 >= CST, 1644 otherwise the operation underflows. 1645 */ 1646 1647 /* This should only happen if the type is unsigned; however, for 1648 programs that use overflowing signed arithmetics even with 1649 -fno-wrapv, this condition may also be true for signed values. */ 1650 if (double_int_ucmp (bnd, cst) < 0) 1651 return max; 1652 1653 if (TYPE_UNSIGNED (type) 1654 && !implies_ge_p (additional, 1655 op0, double_int_to_tree (type, cst))) 1656 return max; 1657 1658 bnd = double_int_add (bnd, double_int_neg (cst)); 1659 } 1660 1661 return bnd; 1662 1663 case FLOOR_DIV_EXPR: 1664 case EXACT_DIV_EXPR: 1665 op0 = TREE_OPERAND (val, 0); 1666 op1 = TREE_OPERAND (val, 1); 1667 if (TREE_CODE (op1) != INTEGER_CST 1668 || tree_int_cst_sign_bit (op1)) 1669 return max; 1670 1671 bnd = derive_constant_upper_bound (op0, additional); 1672 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); 1673 1674 default: 1675 return max; 1676 } 1677} 1678 1679/* Records that AT_STMT is executed at most BOUND times in LOOP. The 1680 additional condition ADDITIONAL is recorded with the bound. */ 1681 1682void 1683record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt) 1684{ 1685 struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); 1686 double_int i_bound = derive_constant_upper_bound (bound, additional); 1687 tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)), 1688 i_bound); 1689 1690 if (dump_file && (dump_flags & TDF_DETAILS)) 1691 { 1692 fprintf (dump_file, "Statements after "); 1693 print_generic_expr (dump_file, at_stmt, TDF_SLIM); 1694 fprintf (dump_file, " are executed at most "); 1695 print_generic_expr (dump_file, bound, TDF_SLIM); 1696 fprintf (dump_file, " (bounded by "); 1697 print_generic_expr (dump_file, c_bound, TDF_SLIM); 1698 fprintf (dump_file, ") times in loop %d.\n", loop->num); 1699 } 1700 1701 elt->bound = c_bound; 1702 elt->at_stmt = at_stmt; 1703 elt->next = loop->bounds; 1704 loop->bounds = elt; 1705} 1706 1707/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe 1708 approximation of the number of iterations for LOOP. */ 1709 1710static void 1711compute_estimated_nb_iterations (struct loop *loop) 1712{ 1713 struct nb_iter_bound *bound; 1714 1715 for (bound = loop->bounds; bound; bound = bound->next) 1716 { 1717 if (TREE_CODE (bound->bound) != INTEGER_CST) 1718 continue; 1719 1720 /* Update only when there is no previous estimation, or when the current 1721 estimation is smaller. */ 1722 if (chrec_contains_undetermined (loop->estimated_nb_iterations) 1723 || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)) 1724 loop->estimated_nb_iterations = bound->bound; 1725 } 1726} 1727 1728/* The following analyzers are extracting informations on the bounds 1729 of LOOP from the following undefined behaviors: 1730 1731 - data references should not access elements over the statically 1732 allocated size, 1733 1734 - signed variables should not overflow when flag_wrapv is not set. 1735*/ 1736 1737static void 1738infer_loop_bounds_from_undefined (struct loop *loop) 1739{ 1740 unsigned i; 1741 basic_block bb, *bbs; 1742 block_stmt_iterator bsi; 1743 1744 bbs = get_loop_body (loop); 1745 1746 for (i = 0; i < loop->num_nodes; i++) 1747 { 1748 bb = bbs[i]; 1749 1750 /* If BB is not executed in each iteration of the loop, we cannot 1751 use the operations in it to infer reliable upper bound on the 1752 # of iterations of the loop. */ 1753 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1754 continue; 1755 1756 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1757 { 1758 tree stmt = bsi_stmt (bsi); 1759 1760 switch (TREE_CODE (stmt)) 1761 { 1762 case MODIFY_EXPR: 1763 { 1764 tree op0 = TREE_OPERAND (stmt, 0); 1765 tree op1 = TREE_OPERAND (stmt, 1); 1766 1767 /* For each array access, analyze its access function 1768 and record a bound on the loop iteration domain. */ 1769 if (TREE_CODE (op1) == ARRAY_REF 1770 && !array_ref_contains_indirect_ref (op1)) 1771 estimate_iters_using_array (stmt, op1); 1772 1773 if (TREE_CODE (op0) == ARRAY_REF 1774 && !array_ref_contains_indirect_ref (op0)) 1775 estimate_iters_using_array (stmt, op0); 1776 1777 /* For each signed type variable in LOOP, analyze its 1778 scalar evolution and record a bound of the loop 1779 based on the type's ranges. */ 1780 else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME) 1781 { 1782 tree init, step, diff, estimation; 1783 tree scev = instantiate_parameters 1784 (loop, analyze_scalar_evolution (loop, op0)); 1785 tree type = chrec_type (scev); 1786 1787 if (chrec_contains_undetermined (scev) 1788 || TYPE_OVERFLOW_WRAPS (type)) 1789 break; 1790 1791 init = initial_condition_in_loop_num (scev, loop->num); 1792 step = evolution_part_in_loop_num (scev, loop->num); 1793 1794 if (init == NULL_TREE 1795 || step == NULL_TREE 1796 || TREE_CODE (init) != INTEGER_CST 1797 || TREE_CODE (step) != INTEGER_CST 1798 || TYPE_MIN_VALUE (type) == NULL_TREE 1799 || TYPE_MAX_VALUE (type) == NULL_TREE) 1800 break; 1801 1802 if (integer_nonzerop (step)) 1803 { 1804 tree utype; 1805 1806 if (tree_int_cst_lt (step, integer_zero_node)) 1807 diff = fold_build2 (MINUS_EXPR, type, init, 1808 TYPE_MIN_VALUE (type)); 1809 else 1810 diff = fold_build2 (MINUS_EXPR, type, 1811 TYPE_MAX_VALUE (type), init); 1812 1813 utype = unsigned_type_for (type); 1814 estimation = fold_build2 (CEIL_DIV_EXPR, type, diff, 1815 step); 1816 record_estimate (loop, 1817 fold_convert (utype, estimation), 1818 boolean_true_node, stmt); 1819 } 1820 } 1821 1822 break; 1823 } 1824 1825 case CALL_EXPR: 1826 { 1827 tree args; 1828 1829 for (args = TREE_OPERAND (stmt, 1); args; 1830 args = TREE_CHAIN (args)) 1831 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF 1832 && !array_ref_contains_indirect_ref (TREE_VALUE (args))) 1833 estimate_iters_using_array (stmt, TREE_VALUE (args)); 1834 1835 break; 1836 } 1837 1838 default: 1839 break; 1840 } 1841 } 1842 } 1843 1844 compute_estimated_nb_iterations (loop); 1845 free (bbs); 1846} 1847 1848/* Records estimates on numbers of iterations of LOOP. */ 1849 1850static void 1851estimate_numbers_of_iterations_loop (struct loop *loop) 1852{ 1853 edge *exits; 1854 tree niter, type; 1855 unsigned i, n_exits; 1856 struct tree_niter_desc niter_desc; 1857 1858 /* Give up if we already have tried to compute an estimation. */ 1859 if (loop->estimated_nb_iterations == chrec_dont_know 1860 /* Or when we already have an estimation. */ 1861 || (loop->estimated_nb_iterations != NULL_TREE 1862 && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST)) 1863 return; 1864 else 1865 loop->estimated_nb_iterations = chrec_dont_know; 1866 1867 exits = get_loop_exit_edges (loop, &n_exits); 1868 for (i = 0; i < n_exits; i++) 1869 { 1870 if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false)) 1871 continue; 1872 1873 niter = niter_desc.niter; 1874 type = TREE_TYPE (niter); 1875 if (!zero_p (niter_desc.may_be_zero) 1876 && !nonzero_p (niter_desc.may_be_zero)) 1877 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, 1878 build_int_cst (type, 0), 1879 niter); 1880 record_estimate (loop, niter, 1881 niter_desc.additional_info, 1882 last_stmt (exits[i]->src)); 1883 } 1884 free (exits); 1885 1886 if (chrec_contains_undetermined (loop->estimated_nb_iterations)) 1887 infer_loop_bounds_from_undefined (loop); 1888} 1889 1890/* Records estimates on numbers of iterations of LOOPS. */ 1891 1892void 1893estimate_numbers_of_iterations (struct loops *loops) 1894{ 1895 unsigned i; 1896 struct loop *loop; 1897 1898 /* We don't want to issue signed overflow warnings while getting 1899 loop iteration estimates. */ 1900 fold_defer_overflow_warnings (); 1901 1902 for (i = 1; i < loops->num; i++) 1903 { 1904 loop = loops->parray[i]; 1905 if (loop) 1906 estimate_numbers_of_iterations_loop (loop); 1907 } 1908 1909 fold_undefer_and_ignore_overflow_warnings (); 1910} 1911 1912/* Returns true if statement S1 dominates statement S2. */ 1913 1914static bool 1915stmt_dominates_stmt_p (tree s1, tree s2) 1916{ 1917 basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2); 1918 1919 if (!bb1 1920 || s1 == s2) 1921 return true; 1922 1923 if (bb1 == bb2) 1924 { 1925 block_stmt_iterator bsi; 1926 1927 for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi)) 1928 if (bsi_stmt (bsi) == s1) 1929 return true; 1930 1931 return false; 1932 } 1933 1934 return dominated_by_p (CDI_DOMINATORS, bb2, bb1); 1935} 1936 1937/* Returns true when we can prove that the number of executions of 1938 STMT in the loop is at most NITER, according to the fact 1939 that the statement NITER_BOUND->at_stmt is executed at most 1940 NITER_BOUND->bound times. */ 1941 1942static bool 1943n_of_executions_at_most (tree stmt, 1944 struct nb_iter_bound *niter_bound, 1945 tree niter) 1946{ 1947 tree cond; 1948 tree bound = niter_bound->bound; 1949 tree bound_type = TREE_TYPE (bound); 1950 tree nit_type = TREE_TYPE (niter); 1951 enum tree_code cmp; 1952 1953 gcc_assert (TYPE_UNSIGNED (bound_type) 1954 && TYPE_UNSIGNED (nit_type) 1955 && is_gimple_min_invariant (bound)); 1956 if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type)) 1957 bound = fold_convert (nit_type, bound); 1958 else 1959 niter = fold_convert (bound_type, niter); 1960 1961 /* After the statement niter_bound->at_stmt we know that anything is 1962 executed at most BOUND times. */ 1963 if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt)) 1964 cmp = GE_EXPR; 1965 /* Before the statement niter_bound->at_stmt we know that anything 1966 is executed at most BOUND + 1 times. */ 1967 else 1968 cmp = GT_EXPR; 1969 1970 cond = fold_binary (cmp, boolean_type_node, niter, bound); 1971 return nonzero_p (cond); 1972} 1973 1974/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */ 1975 1976bool 1977nowrap_type_p (tree type) 1978{ 1979 if (INTEGRAL_TYPE_P (type) 1980 && TYPE_OVERFLOW_UNDEFINED (type)) 1981 return true; 1982 1983 if (POINTER_TYPE_P (type)) 1984 return true; 1985 1986 return false; 1987} 1988 1989/* Return false only when the induction variable BASE + STEP * I is 1990 known to not overflow: i.e. when the number of iterations is small 1991 enough with respect to the step and initial condition in order to 1992 keep the evolution confined in TYPEs bounds. Return true when the 1993 iv is known to overflow or when the property is not computable. 1994 1995 USE_OVERFLOW_SEMANTICS is true if this function should assume that 1996 the rules for overflow of the given language apply (e.g., that signed 1997 arithmetics in C does not overflow). */ 1998 1999bool 2000scev_probably_wraps_p (tree base, tree step, 2001 tree at_stmt, struct loop *loop, 2002 bool use_overflow_semantics) 2003{ 2004 struct nb_iter_bound *bound; 2005 tree delta, step_abs; 2006 tree unsigned_type, valid_niter; 2007 tree type = TREE_TYPE (step); 2008 2009 /* FIXME: We really need something like 2010 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. 2011 2012 We used to test for the following situation that frequently appears 2013 during address arithmetics: 2014 2015 D.1621_13 = (long unsigned intD.4) D.1620_12; 2016 D.1622_14 = D.1621_13 * 8; 2017 D.1623_15 = (doubleD.29 *) D.1622_14; 2018 2019 And derived that the sequence corresponding to D_14 2020 can be proved to not wrap because it is used for computing a 2021 memory access; however, this is not really the case -- for example, 2022 if D_12 = (unsigned char) [254,+,1], then D_14 has values 2023 2032, 2040, 0, 8, ..., but the code is still legal. */ 2024 2025 if (chrec_contains_undetermined (base) 2026 || chrec_contains_undetermined (step) 2027 || TREE_CODE (step) != INTEGER_CST) 2028 return true; 2029 2030 if (zero_p (step)) 2031 return false; 2032 2033 /* If we can use the fact that signed and pointer arithmetics does not 2034 wrap, we are done. */ 2035 if (use_overflow_semantics && nowrap_type_p (type)) 2036 return false; 2037 2038 /* Don't issue signed overflow warnings. */ 2039 fold_defer_overflow_warnings (); 2040 2041 /* Otherwise, compute the number of iterations before we reach the 2042 bound of the type, and verify that the loop is exited before this 2043 occurs. */ 2044 unsigned_type = unsigned_type_for (type); 2045 base = fold_convert (unsigned_type, base); 2046 2047 if (tree_int_cst_sign_bit (step)) 2048 { 2049 tree extreme = fold_convert (unsigned_type, 2050 lower_bound_in_type (type, type)); 2051 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); 2052 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type, 2053 fold_convert (unsigned_type, step)); 2054 } 2055 else 2056 { 2057 tree extreme = fold_convert (unsigned_type, 2058 upper_bound_in_type (type, type)); 2059 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); 2060 step_abs = fold_convert (unsigned_type, step); 2061 } 2062 2063 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); 2064 2065 estimate_numbers_of_iterations_loop (loop); 2066 for (bound = loop->bounds; bound; bound = bound->next) 2067 { 2068 if (n_of_executions_at_most (at_stmt, bound, valid_niter)) 2069 { 2070 fold_undefer_and_ignore_overflow_warnings (); 2071 return false; 2072 } 2073 } 2074 2075 fold_undefer_and_ignore_overflow_warnings (); 2076 2077 /* At this point we still don't have a proof that the iv does not 2078 overflow: give up. */ 2079 return true; 2080} 2081 2082/* Frees the information on upper bounds on numbers of iterations of LOOP. */ 2083 2084void 2085free_numbers_of_iterations_estimates_loop (struct loop *loop) 2086{ 2087 struct nb_iter_bound *bound, *next; 2088 2089 loop->nb_iterations = NULL; 2090 loop->estimated_nb_iterations = NULL; 2091 for (bound = loop->bounds; bound; bound = next) 2092 { 2093 next = bound->next; 2094 free (bound); 2095 } 2096 2097 loop->bounds = NULL; 2098} 2099 2100/* Frees the information on upper bounds on numbers of iterations of LOOPS. */ 2101 2102void 2103free_numbers_of_iterations_estimates (struct loops *loops) 2104{ 2105 unsigned i; 2106 struct loop *loop; 2107 2108 for (i = 1; i < loops->num; i++) 2109 { 2110 loop = loops->parray[i]; 2111 if (loop) 2112 free_numbers_of_iterations_estimates_loop (loop); 2113 } 2114} 2115 2116/* Substitute value VAL for ssa name NAME inside expressions held 2117 at LOOP. */ 2118 2119void 2120substitute_in_loop_info (struct loop *loop, tree name, tree val) 2121{ 2122 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); 2123 loop->estimated_nb_iterations 2124 = simplify_replace_tree (loop->estimated_nb_iterations, name, val); 2125} 2126