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