1 /* Functions to determine/estimate number of iterations of a loop. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3, or (at your option) any 10 later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "tm_p.h" 27 #include "basic-block.h" 28 #include "output.h" 29 #include "tree-pretty-print.h" 30 #include "gimple-pretty-print.h" 31 #include "intl.h" 32 #include "tree-flow.h" 33 #include "tree-dump.h" 34 #include "cfgloop.h" 35 #include "tree-pass.h" 36 #include "ggc.h" 37 #include "tree-chrec.h" 38 #include "tree-scalar-evolution.h" 39 #include "tree-data-ref.h" 40 #include "params.h" 41 #include "flags.h" 42 #include "diagnostic-core.h" 43 #include "tree-inline.h" 44 #include "gmp.h" 45 46 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) 47 48 /* The maximum number of dominator BBs we search for conditions 49 of loop header copies we use for simplifying a conditional 50 expression. */ 51 #define MAX_DOMINATORS_TO_WALK 8 52 53 /* 54 55 Analysis of number of iterations of an affine exit test. 56 57 */ 58 59 /* Bounds on some value, BELOW <= X <= UP. */ 60 61 typedef struct 62 { 63 mpz_t below, up; 64 } bounds; 65 66 67 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */ 68 69 static void 70 split_to_var_and_offset (tree expr, tree *var, mpz_t offset) 71 { 72 tree type = TREE_TYPE (expr); 73 tree op0, op1; 74 double_int off; 75 bool negate = false; 76 77 *var = expr; 78 mpz_set_ui (offset, 0); 79 80 switch (TREE_CODE (expr)) 81 { 82 case MINUS_EXPR: 83 negate = true; 84 /* Fallthru. */ 85 86 case PLUS_EXPR: 87 case POINTER_PLUS_EXPR: 88 op0 = TREE_OPERAND (expr, 0); 89 op1 = TREE_OPERAND (expr, 1); 90 91 if (TREE_CODE (op1) != INTEGER_CST) 92 break; 93 94 *var = op0; 95 /* Always sign extend the offset. */ 96 off = tree_to_double_int (op1); 97 off = double_int_sext (off, TYPE_PRECISION (type)); 98 mpz_set_double_int (offset, off, false); 99 if (negate) 100 mpz_neg (offset, offset); 101 break; 102 103 case INTEGER_CST: 104 *var = build_int_cst_type (type, 0); 105 off = tree_to_double_int (expr); 106 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type)); 107 break; 108 109 default: 110 break; 111 } 112 } 113 114 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF 115 in TYPE to MIN and MAX. */ 116 117 static void 118 determine_value_range (tree type, tree var, mpz_t off, 119 mpz_t min, mpz_t max) 120 { 121 /* If the expression is a constant, we know its value exactly. */ 122 if (integer_zerop (var)) 123 { 124 mpz_set (min, off); 125 mpz_set (max, off); 126 return; 127 } 128 129 /* If the computation may wrap, we know nothing about the value, except for 130 the range of the type. */ 131 get_type_static_bounds (type, min, max); 132 if (!nowrap_type_p (type)) 133 return; 134 135 /* Since the addition of OFF does not wrap, if OFF is positive, then we may 136 add it to MIN, otherwise to MAX. */ 137 if (mpz_sgn (off) < 0) 138 mpz_add (max, max, off); 139 else 140 mpz_add (min, min, off); 141 } 142 143 /* Stores the bounds on the difference of the values of the expressions 144 (var + X) and (var + Y), computed in TYPE, to BNDS. */ 145 146 static void 147 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y, 148 bounds *bnds) 149 { 150 int rel = mpz_cmp (x, y); 151 bool may_wrap = !nowrap_type_p (type); 152 mpz_t m; 153 154 /* If X == Y, then the expressions are always equal. 155 If X > Y, there are the following possibilities: 156 a) neither of var + X and var + Y overflow or underflow, or both of 157 them do. Then their difference is X - Y. 158 b) var + X overflows, and var + Y does not. Then the values of the 159 expressions are var + X - M and var + Y, where M is the range of 160 the type, and their difference is X - Y - M. 161 c) var + Y underflows and var + X does not. Their difference again 162 is M - X + Y. 163 Therefore, if the arithmetics in type does not overflow, then the 164 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y) 165 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or 166 (X - Y, X - Y + M). */ 167 168 if (rel == 0) 169 { 170 mpz_set_ui (bnds->below, 0); 171 mpz_set_ui (bnds->up, 0); 172 return; 173 } 174 175 mpz_init (m); 176 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true); 177 mpz_add_ui (m, m, 1); 178 mpz_sub (bnds->up, x, y); 179 mpz_set (bnds->below, bnds->up); 180 181 if (may_wrap) 182 { 183 if (rel > 0) 184 mpz_sub (bnds->below, bnds->below, m); 185 else 186 mpz_add (bnds->up, bnds->up, m); 187 } 188 189 mpz_clear (m); 190 } 191 192 /* From condition C0 CMP C1 derives information regarding the 193 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE, 194 and stores it to BNDS. */ 195 196 static void 197 refine_bounds_using_guard (tree type, tree varx, mpz_t offx, 198 tree vary, mpz_t offy, 199 tree c0, enum tree_code cmp, tree c1, 200 bounds *bnds) 201 { 202 tree varc0, varc1, tmp, ctype; 203 mpz_t offc0, offc1, loffx, loffy, bnd; 204 bool lbound = false; 205 bool no_wrap = nowrap_type_p (type); 206 bool x_ok, y_ok; 207 208 switch (cmp) 209 { 210 case LT_EXPR: 211 case LE_EXPR: 212 case GT_EXPR: 213 case GE_EXPR: 214 STRIP_SIGN_NOPS (c0); 215 STRIP_SIGN_NOPS (c1); 216 ctype = TREE_TYPE (c0); 217 if (!useless_type_conversion_p (ctype, type)) 218 return; 219 220 break; 221 222 case EQ_EXPR: 223 /* We could derive quite precise information from EQ_EXPR, however, such 224 a guard is unlikely to appear, so we do not bother with handling 225 it. */ 226 return; 227 228 case NE_EXPR: 229 /* NE_EXPR comparisons do not contain much of useful information, except for 230 special case of comparing with the bounds of the type. */ 231 if (TREE_CODE (c1) != INTEGER_CST 232 || !INTEGRAL_TYPE_P (type)) 233 return; 234 235 /* Ensure that the condition speaks about an expression in the same type 236 as X and Y. */ 237 ctype = TREE_TYPE (c0); 238 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type)) 239 return; 240 c0 = fold_convert (type, c0); 241 c1 = fold_convert (type, c1); 242 243 if (TYPE_MIN_VALUE (type) 244 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0)) 245 { 246 cmp = GT_EXPR; 247 break; 248 } 249 if (TYPE_MAX_VALUE (type) 250 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0)) 251 { 252 cmp = LT_EXPR; 253 break; 254 } 255 256 return; 257 default: 258 return; 259 } 260 261 mpz_init (offc0); 262 mpz_init (offc1); 263 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); 264 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); 265 266 /* We are only interested in comparisons of expressions based on VARX and 267 VARY. TODO -- we might also be able to derive some bounds from 268 expressions containing just one of the variables. */ 269 270 if (operand_equal_p (varx, varc1, 0)) 271 { 272 tmp = varc0; varc0 = varc1; varc1 = tmp; 273 mpz_swap (offc0, offc1); 274 cmp = swap_tree_comparison (cmp); 275 } 276 277 if (!operand_equal_p (varx, varc0, 0) 278 || !operand_equal_p (vary, varc1, 0)) 279 goto end; 280 281 mpz_init_set (loffx, offx); 282 mpz_init_set (loffy, offy); 283 284 if (cmp == GT_EXPR || cmp == GE_EXPR) 285 { 286 tmp = varx; varx = vary; vary = tmp; 287 mpz_swap (offc0, offc1); 288 mpz_swap (loffx, loffy); 289 cmp = swap_tree_comparison (cmp); 290 lbound = true; 291 } 292 293 /* If there is no overflow, the condition implies that 294 295 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0). 296 297 The overflows and underflows may complicate things a bit; each 298 overflow decreases the appropriate offset by M, and underflow 299 increases it by M. The above inequality would not necessarily be 300 true if 301 302 -- VARX + OFFX underflows and VARX + OFFC0 does not, or 303 VARX + OFFC0 overflows, but VARX + OFFX does not. 304 This may only happen if OFFX < OFFC0. 305 -- VARY + OFFY overflows and VARY + OFFC1 does not, or 306 VARY + OFFC1 underflows and VARY + OFFY does not. 307 This may only happen if OFFY > OFFC1. */ 308 309 if (no_wrap) 310 { 311 x_ok = true; 312 y_ok = true; 313 } 314 else 315 { 316 x_ok = (integer_zerop (varx) 317 || mpz_cmp (loffx, offc0) >= 0); 318 y_ok = (integer_zerop (vary) 319 || mpz_cmp (loffy, offc1) <= 0); 320 } 321 322 if (x_ok && y_ok) 323 { 324 mpz_init (bnd); 325 mpz_sub (bnd, loffx, loffy); 326 mpz_add (bnd, bnd, offc1); 327 mpz_sub (bnd, bnd, offc0); 328 329 if (cmp == LT_EXPR) 330 mpz_sub_ui (bnd, bnd, 1); 331 332 if (lbound) 333 { 334 mpz_neg (bnd, bnd); 335 if (mpz_cmp (bnds->below, bnd) < 0) 336 mpz_set (bnds->below, bnd); 337 } 338 else 339 { 340 if (mpz_cmp (bnd, bnds->up) < 0) 341 mpz_set (bnds->up, bnd); 342 } 343 mpz_clear (bnd); 344 } 345 346 mpz_clear (loffx); 347 mpz_clear (loffy); 348 end: 349 mpz_clear (offc0); 350 mpz_clear (offc1); 351 } 352 353 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. 354 The subtraction is considered to be performed in arbitrary precision, 355 without overflows. 356 357 We do not attempt to be too clever regarding the value ranges of X and 358 Y; most of the time, they are just integers or ssa names offsetted by 359 integer. However, we try to use the information contained in the 360 comparisons before the loop (usually created by loop header copying). */ 361 362 static void 363 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) 364 { 365 tree type = TREE_TYPE (x); 366 tree varx, vary; 367 mpz_t offx, offy; 368 mpz_t minx, maxx, miny, maxy; 369 int cnt = 0; 370 edge e; 371 basic_block bb; 372 tree c0, c1; 373 gimple cond; 374 enum tree_code cmp; 375 376 /* Get rid of unnecessary casts, but preserve the value of 377 the expressions. */ 378 STRIP_SIGN_NOPS (x); 379 STRIP_SIGN_NOPS (y); 380 381 mpz_init (bnds->below); 382 mpz_init (bnds->up); 383 mpz_init (offx); 384 mpz_init (offy); 385 split_to_var_and_offset (x, &varx, offx); 386 split_to_var_and_offset (y, &vary, offy); 387 388 if (!integer_zerop (varx) 389 && operand_equal_p (varx, vary, 0)) 390 { 391 /* Special case VARX == VARY -- we just need to compare the 392 offsets. The matters are a bit more complicated in the 393 case addition of offsets may wrap. */ 394 bound_difference_of_offsetted_base (type, offx, offy, bnds); 395 } 396 else 397 { 398 /* Otherwise, use the value ranges to determine the initial 399 estimates on below and up. */ 400 mpz_init (minx); 401 mpz_init (maxx); 402 mpz_init (miny); 403 mpz_init (maxy); 404 determine_value_range (type, varx, offx, minx, maxx); 405 determine_value_range (type, vary, offy, miny, maxy); 406 407 mpz_sub (bnds->below, minx, maxy); 408 mpz_sub (bnds->up, maxx, miny); 409 mpz_clear (minx); 410 mpz_clear (maxx); 411 mpz_clear (miny); 412 mpz_clear (maxy); 413 } 414 415 /* If both X and Y are constants, we cannot get any more precise. */ 416 if (integer_zerop (varx) && integer_zerop (vary)) 417 goto end; 418 419 /* Now walk the dominators of the loop header and use the entry 420 guards to refine the estimates. */ 421 for (bb = loop->header; 422 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; 423 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 424 { 425 if (!single_pred_p (bb)) 426 continue; 427 e = single_pred_edge (bb); 428 429 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 430 continue; 431 432 cond = last_stmt (e->src); 433 c0 = gimple_cond_lhs (cond); 434 cmp = gimple_cond_code (cond); 435 c1 = gimple_cond_rhs (cond); 436 437 if (e->flags & EDGE_FALSE_VALUE) 438 cmp = invert_tree_comparison (cmp, false); 439 440 refine_bounds_using_guard (type, varx, offx, vary, offy, 441 c0, cmp, c1, bnds); 442 ++cnt; 443 } 444 445 end: 446 mpz_clear (offx); 447 mpz_clear (offy); 448 } 449 450 /* Update the bounds in BNDS that restrict the value of X to the bounds 451 that restrict the value of X + DELTA. X can be obtained as a 452 difference of two values in TYPE. */ 453 454 static void 455 bounds_add (bounds *bnds, double_int delta, tree type) 456 { 457 mpz_t mdelta, max; 458 459 mpz_init (mdelta); 460 mpz_set_double_int (mdelta, delta, false); 461 462 mpz_init (max); 463 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); 464 465 mpz_add (bnds->up, bnds->up, mdelta); 466 mpz_add (bnds->below, bnds->below, mdelta); 467 468 if (mpz_cmp (bnds->up, max) > 0) 469 mpz_set (bnds->up, max); 470 471 mpz_neg (max, max); 472 if (mpz_cmp (bnds->below, max) < 0) 473 mpz_set (bnds->below, max); 474 475 mpz_clear (mdelta); 476 mpz_clear (max); 477 } 478 479 /* Update the bounds in BNDS that restrict the value of X to the bounds 480 that restrict the value of -X. */ 481 482 static void 483 bounds_negate (bounds *bnds) 484 { 485 mpz_t tmp; 486 487 mpz_init_set (tmp, bnds->up); 488 mpz_neg (bnds->up, bnds->below); 489 mpz_neg (bnds->below, tmp); 490 mpz_clear (tmp); 491 } 492 493 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ 494 495 static tree 496 inverse (tree x, tree mask) 497 { 498 tree type = TREE_TYPE (x); 499 tree rslt; 500 unsigned ctr = tree_floor_log2 (mask); 501 502 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) 503 { 504 unsigned HOST_WIDE_INT ix; 505 unsigned HOST_WIDE_INT imask; 506 unsigned HOST_WIDE_INT irslt = 1; 507 508 gcc_assert (cst_and_fits_in_hwi (x)); 509 gcc_assert (cst_and_fits_in_hwi (mask)); 510 511 ix = int_cst_value (x); 512 imask = int_cst_value (mask); 513 514 for (; ctr; ctr--) 515 { 516 irslt *= ix; 517 ix *= ix; 518 } 519 irslt &= imask; 520 521 rslt = build_int_cst_type (type, irslt); 522 } 523 else 524 { 525 rslt = build_int_cst (type, 1); 526 for (; ctr; ctr--) 527 { 528 rslt = int_const_binop (MULT_EXPR, rslt, x); 529 x = int_const_binop (MULT_EXPR, x, x); 530 } 531 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask); 532 } 533 534 return rslt; 535 } 536 537 /* Derives the upper bound BND on the number of executions of loop with exit 538 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of 539 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed 540 that the loop ends through this exit, i.e., the induction variable ever 541 reaches the value of C. 542 543 The value C is equal to final - base, where final and base are the final and 544 initial value of the actual induction variable in the analysed loop. BNDS 545 bounds the value of this difference when computed in signed type with 546 unbounded range, while the computation of C is performed in an unsigned 547 type with the range matching the range of the type of the induction variable. 548 In particular, BNDS.up contains an upper bound on C in the following cases: 549 -- if the iv must reach its final value without overflow, i.e., if 550 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or 551 -- if final >= base, which we know to hold when BNDS.below >= 0. */ 552 553 static void 554 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s, 555 bounds *bnds, bool exit_must_be_taken) 556 { 557 double_int max; 558 mpz_t d; 559 bool bnds_u_valid = ((no_overflow && exit_must_be_taken) 560 || mpz_sgn (bnds->below) >= 0); 561 562 if (multiple_of_p (TREE_TYPE (c), c, s)) 563 { 564 /* If C is an exact multiple of S, then its value will be reached before 565 the induction variable overflows (unless the loop is exited in some 566 other way before). Note that the actual induction variable in the 567 loop (which ranges from base to final instead of from 0 to C) may 568 overflow, in which case BNDS.up will not be giving a correct upper 569 bound on C; thus, BNDS_U_VALID had to be computed in advance. */ 570 no_overflow = true; 571 exit_must_be_taken = true; 572 } 573 574 /* If the induction variable can overflow, the number of iterations is at 575 most the period of the control variable (or infinite, but in that case 576 the whole # of iterations analysis will fail). */ 577 if (!no_overflow) 578 { 579 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c)) 580 - tree_low_cst (num_ending_zeros (s), 1)); 581 mpz_set_double_int (bnd, max, true); 582 return; 583 } 584 585 /* Now we know that the induction variable does not overflow, so the loop 586 iterates at most (range of type / S) times. */ 587 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))), 588 true); 589 590 /* If the induction variable is guaranteed to reach the value of C before 591 overflow, ... */ 592 if (exit_must_be_taken) 593 { 594 /* ... then we can strenghten this to C / S, and possibly we can use 595 the upper bound on C given by BNDS. */ 596 if (TREE_CODE (c) == INTEGER_CST) 597 mpz_set_double_int (bnd, tree_to_double_int (c), true); 598 else if (bnds_u_valid) 599 mpz_set (bnd, bnds->up); 600 } 601 602 mpz_init (d); 603 mpz_set_double_int (d, tree_to_double_int (s), true); 604 mpz_fdiv_q (bnd, bnd, d); 605 mpz_clear (d); 606 } 607 608 /* Determines number of iterations of loop whose ending condition 609 is IV <> FINAL. TYPE is the type of the iv. The number of 610 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if 611 we know that the exit must be taken eventually, i.e., that the IV 612 ever reaches the value FINAL (we derived this earlier, and possibly set 613 NITER->assumptions to make sure this is the case). BNDS contains the 614 bounds on the difference FINAL - IV->base. */ 615 616 static bool 617 number_of_iterations_ne (tree type, affine_iv *iv, tree final, 618 struct tree_niter_desc *niter, bool exit_must_be_taken, 619 bounds *bnds) 620 { 621 tree niter_type = unsigned_type_for (type); 622 tree s, c, d, bits, assumption, tmp, bound; 623 mpz_t max; 624 625 niter->control = *iv; 626 niter->bound = final; 627 niter->cmp = NE_EXPR; 628 629 /* Rearrange the terms so that we get inequality S * i <> C, with S 630 positive. Also cast everything to the unsigned type. If IV does 631 not overflow, BNDS bounds the value of C. Also, this is the 632 case if the computation |FINAL - IV->base| does not overflow, i.e., 633 if BNDS->below in the result is nonnegative. */ 634 if (tree_int_cst_sign_bit (iv->step)) 635 { 636 s = fold_convert (niter_type, 637 fold_build1 (NEGATE_EXPR, type, iv->step)); 638 c = fold_build2 (MINUS_EXPR, niter_type, 639 fold_convert (niter_type, iv->base), 640 fold_convert (niter_type, final)); 641 bounds_negate (bnds); 642 } 643 else 644 { 645 s = fold_convert (niter_type, iv->step); 646 c = fold_build2 (MINUS_EXPR, niter_type, 647 fold_convert (niter_type, final), 648 fold_convert (niter_type, iv->base)); 649 } 650 651 mpz_init (max); 652 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds, 653 exit_must_be_taken); 654 niter->max = mpz_get_double_int (niter_type, max, false); 655 mpz_clear (max); 656 657 /* First the trivial cases -- when the step is 1. */ 658 if (integer_onep (s)) 659 { 660 niter->niter = c; 661 return true; 662 } 663 664 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop 665 is infinite. Otherwise, the number of iterations is 666 (inverse(s/d) * (c/d)) mod (size of mode/d). */ 667 bits = num_ending_zeros (s); 668 bound = build_low_bits_mask (niter_type, 669 (TYPE_PRECISION (niter_type) 670 - tree_low_cst (bits, 1))); 671 672 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, 673 build_int_cst (niter_type, 1), bits); 674 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits); 675 676 if (!exit_must_be_taken) 677 { 678 /* If we cannot assume that the exit is taken eventually, record the 679 assumptions for divisibility of c. */ 680 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d); 681 assumption = fold_build2 (EQ_EXPR, boolean_type_node, 682 assumption, build_int_cst (niter_type, 0)); 683 if (!integer_nonzerop (assumption)) 684 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 685 niter->assumptions, assumption); 686 } 687 688 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); 689 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); 690 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); 691 return true; 692 } 693 694 /* Checks whether we can determine the final value of the control variable 695 of the loop with ending condition IV0 < IV1 (computed in TYPE). 696 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value 697 of the step. The assumptions necessary to ensure that the computation 698 of the final value does not overflow are recorded in NITER. If we 699 find the final value, we adjust DELTA and return TRUE. Otherwise 700 we return false. BNDS bounds the value of IV1->base - IV0->base, 701 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is 702 true if we know that the exit must be taken eventually. */ 703 704 static bool 705 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, 706 struct tree_niter_desc *niter, 707 tree *delta, tree step, 708 bool exit_must_be_taken, bounds *bnds) 709 { 710 tree niter_type = TREE_TYPE (step); 711 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); 712 tree tmod; 713 mpz_t mmod; 714 tree assumption = boolean_true_node, bound, noloop; 715 bool ret = false, fv_comp_no_overflow; 716 tree type1 = type; 717 if (POINTER_TYPE_P (type)) 718 type1 = sizetype; 719 720 if (TREE_CODE (mod) != INTEGER_CST) 721 return false; 722 if (integer_nonzerop (mod)) 723 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); 724 tmod = fold_convert (type1, mod); 725 726 mpz_init (mmod); 727 mpz_set_double_int (mmod, tree_to_double_int (mod), true); 728 mpz_neg (mmod, mmod); 729 730 /* If the induction variable does not overflow and the exit is taken, 731 then the computation of the final value does not overflow. This is 732 also obviously the case if the new final value is equal to the 733 current one. Finally, we postulate this for pointer type variables, 734 as the code cannot rely on the object to that the pointer points being 735 placed at the end of the address space (and more pragmatically, 736 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */ 737 if (integer_zerop (mod) || POINTER_TYPE_P (type)) 738 fv_comp_no_overflow = true; 739 else if (!exit_must_be_taken) 740 fv_comp_no_overflow = false; 741 else 742 fv_comp_no_overflow = 743 (iv0->no_overflow && integer_nonzerop (iv0->step)) 744 || (iv1->no_overflow && integer_nonzerop (iv1->step)); 745 746 if (integer_nonzerop (iv0->step)) 747 { 748 /* The final value of the iv is iv1->base + MOD, assuming that this 749 computation does not overflow, and that 750 iv0->base <= iv1->base + MOD. */ 751 if (!fv_comp_no_overflow) 752 { 753 bound = fold_build2 (MINUS_EXPR, type1, 754 TYPE_MAX_VALUE (type1), tmod); 755 assumption = fold_build2 (LE_EXPR, boolean_type_node, 756 iv1->base, bound); 757 if (integer_zerop (assumption)) 758 goto end; 759 } 760 if (mpz_cmp (mmod, bnds->below) < 0) 761 noloop = boolean_false_node; 762 else if (POINTER_TYPE_P (type)) 763 noloop = fold_build2 (GT_EXPR, boolean_type_node, 764 iv0->base, 765 fold_build_pointer_plus (iv1->base, tmod)); 766 else 767 noloop = fold_build2 (GT_EXPR, boolean_type_node, 768 iv0->base, 769 fold_build2 (PLUS_EXPR, type1, 770 iv1->base, tmod)); 771 } 772 else 773 { 774 /* The final value of the iv is iv0->base - MOD, assuming that this 775 computation does not overflow, and that 776 iv0->base - MOD <= iv1->base. */ 777 if (!fv_comp_no_overflow) 778 { 779 bound = fold_build2 (PLUS_EXPR, type1, 780 TYPE_MIN_VALUE (type1), tmod); 781 assumption = fold_build2 (GE_EXPR, boolean_type_node, 782 iv0->base, bound); 783 if (integer_zerop (assumption)) 784 goto end; 785 } 786 if (mpz_cmp (mmod, bnds->below) < 0) 787 noloop = boolean_false_node; 788 else if (POINTER_TYPE_P (type)) 789 noloop = fold_build2 (GT_EXPR, boolean_type_node, 790 fold_build_pointer_plus (iv0->base, 791 fold_build1 (NEGATE_EXPR, 792 type1, tmod)), 793 iv1->base); 794 else 795 noloop = fold_build2 (GT_EXPR, boolean_type_node, 796 fold_build2 (MINUS_EXPR, type1, 797 iv0->base, tmod), 798 iv1->base); 799 } 800 801 if (!integer_nonzerop (assumption)) 802 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 803 niter->assumptions, 804 assumption); 805 if (!integer_zerop (noloop)) 806 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 807 niter->may_be_zero, 808 noloop); 809 bounds_add (bnds, tree_to_double_int (mod), type); 810 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); 811 812 ret = true; 813 end: 814 mpz_clear (mmod); 815 return ret; 816 } 817 818 /* Add assertions to NITER that ensure that the control variable of the loop 819 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 820 are TYPE. Returns false if we can prove that there is an overflow, true 821 otherwise. STEP is the absolute value of the step. */ 822 823 static bool 824 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, 825 struct tree_niter_desc *niter, tree step) 826 { 827 tree bound, d, assumption, diff; 828 tree niter_type = TREE_TYPE (step); 829 830 if (integer_nonzerop (iv0->step)) 831 { 832 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */ 833 if (iv0->no_overflow) 834 return true; 835 836 /* If iv0->base is a constant, we can determine the last value before 837 overflow precisely; otherwise we conservatively assume 838 MAX - STEP + 1. */ 839 840 if (TREE_CODE (iv0->base) == INTEGER_CST) 841 { 842 d = fold_build2 (MINUS_EXPR, niter_type, 843 fold_convert (niter_type, TYPE_MAX_VALUE (type)), 844 fold_convert (niter_type, iv0->base)); 845 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 846 } 847 else 848 diff = fold_build2 (MINUS_EXPR, niter_type, step, 849 build_int_cst (niter_type, 1)); 850 bound = fold_build2 (MINUS_EXPR, type, 851 TYPE_MAX_VALUE (type), fold_convert (type, diff)); 852 assumption = fold_build2 (LE_EXPR, boolean_type_node, 853 iv1->base, bound); 854 } 855 else 856 { 857 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */ 858 if (iv1->no_overflow) 859 return true; 860 861 if (TREE_CODE (iv1->base) == INTEGER_CST) 862 { 863 d = fold_build2 (MINUS_EXPR, niter_type, 864 fold_convert (niter_type, iv1->base), 865 fold_convert (niter_type, TYPE_MIN_VALUE (type))); 866 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 867 } 868 else 869 diff = fold_build2 (MINUS_EXPR, niter_type, step, 870 build_int_cst (niter_type, 1)); 871 bound = fold_build2 (PLUS_EXPR, type, 872 TYPE_MIN_VALUE (type), fold_convert (type, diff)); 873 assumption = fold_build2 (GE_EXPR, boolean_type_node, 874 iv0->base, bound); 875 } 876 877 if (integer_zerop (assumption)) 878 return false; 879 if (!integer_nonzerop (assumption)) 880 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 881 niter->assumptions, assumption); 882 883 iv0->no_overflow = true; 884 iv1->no_overflow = true; 885 return true; 886 } 887 888 /* Add an assumption to NITER that a loop whose ending condition 889 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS 890 bounds the value of IV1->base - IV0->base. */ 891 892 static void 893 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, 894 struct tree_niter_desc *niter, bounds *bnds) 895 { 896 tree assumption = boolean_true_node, bound, diff; 897 tree mbz, mbzl, mbzr, type1; 898 bool rolls_p, no_overflow_p; 899 double_int dstep; 900 mpz_t mstep, max; 901 902 /* We are going to compute the number of iterations as 903 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned 904 variant of TYPE. This formula only works if 905 906 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 907 908 (where MAX is the maximum value of the unsigned variant of TYPE, and 909 the computations in this formula are performed in full precision, 910 i.e., without overflows). 911 912 Usually, for loops with exit condition iv0->base + step * i < iv1->base, 913 we have a condition of the form iv0->base - step < iv1->base before the loop, 914 and for loops iv0->base < iv1->base - step * i the condition 915 iv0->base < iv1->base + step, due to loop header copying, which enable us 916 to prove the lower bound. 917 918 The upper bound is more complicated. Unless the expressions for initial 919 and final value themselves contain enough information, we usually cannot 920 derive it from the context. */ 921 922 /* First check whether the answer does not follow from the bounds we gathered 923 before. */ 924 if (integer_nonzerop (iv0->step)) 925 dstep = tree_to_double_int (iv0->step); 926 else 927 { 928 dstep = double_int_sext (tree_to_double_int (iv1->step), 929 TYPE_PRECISION (type)); 930 dstep = double_int_neg (dstep); 931 } 932 933 mpz_init (mstep); 934 mpz_set_double_int (mstep, dstep, true); 935 mpz_neg (mstep, mstep); 936 mpz_add_ui (mstep, mstep, 1); 937 938 rolls_p = mpz_cmp (mstep, bnds->below) <= 0; 939 940 mpz_init (max); 941 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); 942 mpz_add (max, max, mstep); 943 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0 944 /* For pointers, only values lying inside a single object 945 can be compared or manipulated by pointer arithmetics. 946 Gcc in general does not allow or handle objects larger 947 than half of the address space, hence the upper bound 948 is satisfied for pointers. */ 949 || POINTER_TYPE_P (type)); 950 mpz_clear (mstep); 951 mpz_clear (max); 952 953 if (rolls_p && no_overflow_p) 954 return; 955 956 type1 = type; 957 if (POINTER_TYPE_P (type)) 958 type1 = sizetype; 959 960 /* Now the hard part; we must formulate the assumption(s) as expressions, and 961 we must be careful not to introduce overflow. */ 962 963 if (integer_nonzerop (iv0->step)) 964 { 965 diff = fold_build2 (MINUS_EXPR, type1, 966 iv0->step, build_int_cst (type1, 1)); 967 968 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since 969 0 address never belongs to any object, we can assume this for 970 pointers. */ 971 if (!POINTER_TYPE_P (type)) 972 { 973 bound = fold_build2 (PLUS_EXPR, type1, 974 TYPE_MIN_VALUE (type), diff); 975 assumption = fold_build2 (GE_EXPR, boolean_type_node, 976 iv0->base, bound); 977 } 978 979 /* And then we can compute iv0->base - diff, and compare it with 980 iv1->base. */ 981 mbzl = fold_build2 (MINUS_EXPR, type1, 982 fold_convert (type1, iv0->base), diff); 983 mbzr = fold_convert (type1, iv1->base); 984 } 985 else 986 { 987 diff = fold_build2 (PLUS_EXPR, type1, 988 iv1->step, build_int_cst (type1, 1)); 989 990 if (!POINTER_TYPE_P (type)) 991 { 992 bound = fold_build2 (PLUS_EXPR, type1, 993 TYPE_MAX_VALUE (type), diff); 994 assumption = fold_build2 (LE_EXPR, boolean_type_node, 995 iv1->base, bound); 996 } 997 998 mbzl = fold_convert (type1, iv0->base); 999 mbzr = fold_build2 (MINUS_EXPR, type1, 1000 fold_convert (type1, iv1->base), diff); 1001 } 1002 1003 if (!integer_nonzerop (assumption)) 1004 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1005 niter->assumptions, assumption); 1006 if (!rolls_p) 1007 { 1008 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); 1009 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 1010 niter->may_be_zero, mbz); 1011 } 1012 } 1013 1014 /* Determines number of iterations of loop whose ending condition 1015 is IV0 < IV1. TYPE is the type of the iv. The number of 1016 iterations is stored to NITER. BNDS bounds the difference 1017 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know 1018 that the exit must be taken eventually. */ 1019 1020 static bool 1021 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, 1022 struct tree_niter_desc *niter, 1023 bool exit_must_be_taken, bounds *bnds) 1024 { 1025 tree niter_type = unsigned_type_for (type); 1026 tree delta, step, s; 1027 mpz_t mstep, tmp; 1028 1029 if (integer_nonzerop (iv0->step)) 1030 { 1031 niter->control = *iv0; 1032 niter->cmp = LT_EXPR; 1033 niter->bound = iv1->base; 1034 } 1035 else 1036 { 1037 niter->control = *iv1; 1038 niter->cmp = GT_EXPR; 1039 niter->bound = iv0->base; 1040 } 1041 1042 delta = fold_build2 (MINUS_EXPR, niter_type, 1043 fold_convert (niter_type, iv1->base), 1044 fold_convert (niter_type, iv0->base)); 1045 1046 /* First handle the special case that the step is +-1. */ 1047 if ((integer_onep (iv0->step) && integer_zerop (iv1->step)) 1048 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step))) 1049 { 1050 /* for (i = iv0->base; i < iv1->base; i++) 1051 1052 or 1053 1054 for (i = iv1->base; i > iv0->base; i--). 1055 1056 In both cases # of iterations is iv1->base - iv0->base, assuming that 1057 iv1->base >= iv0->base. 1058 1059 First try to derive a lower bound on the value of 1060 iv1->base - iv0->base, computed in full precision. If the difference 1061 is nonnegative, we are done, otherwise we must record the 1062 condition. */ 1063 1064 if (mpz_sgn (bnds->below) < 0) 1065 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, 1066 iv1->base, iv0->base); 1067 niter->niter = delta; 1068 niter->max = mpz_get_double_int (niter_type, bnds->up, false); 1069 return true; 1070 } 1071 1072 if (integer_nonzerop (iv0->step)) 1073 step = fold_convert (niter_type, iv0->step); 1074 else 1075 step = fold_convert (niter_type, 1076 fold_build1 (NEGATE_EXPR, type, iv1->step)); 1077 1078 /* If we can determine the final value of the control iv exactly, we can 1079 transform the condition to != comparison. In particular, this will be 1080 the case if DELTA is constant. */ 1081 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step, 1082 exit_must_be_taken, bnds)) 1083 { 1084 affine_iv zps; 1085 1086 zps.base = build_int_cst (niter_type, 0); 1087 zps.step = step; 1088 /* number_of_iterations_lt_to_ne will add assumptions that ensure that 1089 zps does not overflow. */ 1090 zps.no_overflow = true; 1091 1092 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds); 1093 } 1094 1095 /* Make sure that the control iv does not overflow. */ 1096 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step)) 1097 return false; 1098 1099 /* We determine the number of iterations as (delta + step - 1) / step. For 1100 this to work, we must know that iv1->base >= iv0->base - step + 1, 1101 otherwise the loop does not roll. */ 1102 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds); 1103 1104 s = fold_build2 (MINUS_EXPR, niter_type, 1105 step, build_int_cst (niter_type, 1)); 1106 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); 1107 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); 1108 1109 mpz_init (mstep); 1110 mpz_init (tmp); 1111 mpz_set_double_int (mstep, tree_to_double_int (step), true); 1112 mpz_add (tmp, bnds->up, mstep); 1113 mpz_sub_ui (tmp, tmp, 1); 1114 mpz_fdiv_q (tmp, tmp, mstep); 1115 niter->max = mpz_get_double_int (niter_type, tmp, false); 1116 mpz_clear (mstep); 1117 mpz_clear (tmp); 1118 1119 return true; 1120 } 1121 1122 /* Determines number of iterations of loop whose ending condition 1123 is IV0 <= IV1. TYPE is the type of the iv. The number of 1124 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if 1125 we know that this condition must eventually become false (we derived this 1126 earlier, and possibly set NITER->assumptions to make sure this 1127 is the case). BNDS bounds the difference IV1->base - IV0->base. */ 1128 1129 static bool 1130 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, 1131 struct tree_niter_desc *niter, bool exit_must_be_taken, 1132 bounds *bnds) 1133 { 1134 tree assumption; 1135 tree type1 = type; 1136 if (POINTER_TYPE_P (type)) 1137 type1 = sizetype; 1138 1139 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff 1140 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest 1141 value of the type. This we must know anyway, since if it is 1142 equal to this value, the loop rolls forever. We do not check 1143 this condition for pointer type ivs, as the code cannot rely on 1144 the object to that the pointer points being placed at the end of 1145 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is 1146 not defined for pointers). */ 1147 1148 if (!exit_must_be_taken && !POINTER_TYPE_P (type)) 1149 { 1150 if (integer_nonzerop (iv0->step)) 1151 assumption = fold_build2 (NE_EXPR, boolean_type_node, 1152 iv1->base, TYPE_MAX_VALUE (type)); 1153 else 1154 assumption = fold_build2 (NE_EXPR, boolean_type_node, 1155 iv0->base, TYPE_MIN_VALUE (type)); 1156 1157 if (integer_zerop (assumption)) 1158 return false; 1159 if (!integer_nonzerop (assumption)) 1160 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 1161 niter->assumptions, assumption); 1162 } 1163 1164 if (integer_nonzerop (iv0->step)) 1165 { 1166 if (POINTER_TYPE_P (type)) 1167 iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1); 1168 else 1169 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base, 1170 build_int_cst (type1, 1)); 1171 } 1172 else if (POINTER_TYPE_P (type)) 1173 iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1); 1174 else 1175 iv0->base = fold_build2 (MINUS_EXPR, type1, 1176 iv0->base, build_int_cst (type1, 1)); 1177 1178 bounds_add (bnds, double_int_one, type1); 1179 1180 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken, 1181 bnds); 1182 } 1183 1184 /* Dumps description of affine induction variable IV to FILE. */ 1185 1186 static void 1187 dump_affine_iv (FILE *file, affine_iv *iv) 1188 { 1189 if (!integer_zerop (iv->step)) 1190 fprintf (file, "["); 1191 1192 print_generic_expr (dump_file, iv->base, TDF_SLIM); 1193 1194 if (!integer_zerop (iv->step)) 1195 { 1196 fprintf (file, ", + , "); 1197 print_generic_expr (dump_file, iv->step, TDF_SLIM); 1198 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : ""); 1199 } 1200 } 1201 1202 /* Determine the number of iterations according to condition (for staying 1203 inside loop) which compares two induction variables using comparison 1204 operator CODE. The induction variable on left side of the comparison 1205 is IV0, the right-hand side is IV1. Both induction variables must have 1206 type TYPE, which must be an integer or pointer type. The steps of the 1207 ivs must be constants (or NULL_TREE, which is interpreted as constant zero). 1208 1209 LOOP is the loop whose number of iterations we are determining. 1210 1211 ONLY_EXIT is true if we are sure this is the only way the loop could be 1212 exited (including possibly non-returning function calls, exceptions, etc.) 1213 -- in this case we can use the information whether the control induction 1214 variables can overflow or not in a more efficient way. 1215 1216 The results (number of iterations and assumptions as described in 1217 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. 1218 Returns false if it fails to determine number of iterations, true if it 1219 was determined (possibly with some assumptions). */ 1220 1221 static bool 1222 number_of_iterations_cond (struct loop *loop, 1223 tree type, affine_iv *iv0, enum tree_code code, 1224 affine_iv *iv1, struct tree_niter_desc *niter, 1225 bool only_exit) 1226 { 1227 bool exit_must_be_taken = false, ret; 1228 bounds bnds; 1229 1230 /* The meaning of these assumptions is this: 1231 if !assumptions 1232 then the rest of information does not have to be valid 1233 if may_be_zero then the loop does not roll, even if 1234 niter != 0. */ 1235 niter->assumptions = boolean_true_node; 1236 niter->may_be_zero = boolean_false_node; 1237 niter->niter = NULL_TREE; 1238 niter->max = double_int_zero; 1239 1240 niter->bound = NULL_TREE; 1241 niter->cmp = ERROR_MARK; 1242 1243 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that 1244 the control variable is on lhs. */ 1245 if (code == GE_EXPR || code == GT_EXPR 1246 || (code == NE_EXPR && integer_zerop (iv0->step))) 1247 { 1248 SWAP (iv0, iv1); 1249 code = swap_tree_comparison (code); 1250 } 1251 1252 if (POINTER_TYPE_P (type)) 1253 { 1254 /* Comparison of pointers is undefined unless both iv0 and iv1 point 1255 to the same object. If they do, the control variable cannot wrap 1256 (as wrap around the bounds of memory will never return a pointer 1257 that would be guaranteed to point to the same object, even if we 1258 avoid undefined behavior by casting to size_t and back). */ 1259 iv0->no_overflow = true; 1260 iv1->no_overflow = true; 1261 } 1262 1263 /* If the control induction variable does not overflow and the only exit 1264 from the loop is the one that we analyze, we know it must be taken 1265 eventually. */ 1266 if (only_exit) 1267 { 1268 if (!integer_zerop (iv0->step) && iv0->no_overflow) 1269 exit_must_be_taken = true; 1270 else if (!integer_zerop (iv1->step) && iv1->no_overflow) 1271 exit_must_be_taken = true; 1272 } 1273 1274 /* We can handle the case when neither of the sides of the comparison is 1275 invariant, provided that the test is NE_EXPR. This rarely occurs in 1276 practice, but it is simple enough to manage. */ 1277 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step)) 1278 { 1279 tree step_type = POINTER_TYPE_P (type) ? sizetype : type; 1280 if (code != NE_EXPR) 1281 return false; 1282 1283 iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type, 1284 iv0->step, iv1->step); 1285 iv0->no_overflow = false; 1286 iv1->step = build_int_cst (step_type, 0); 1287 iv1->no_overflow = true; 1288 } 1289 1290 /* If the result of the comparison is a constant, the loop is weird. More 1291 precise handling would be possible, but the situation is not common enough 1292 to waste time on it. */ 1293 if (integer_zerop (iv0->step) && integer_zerop (iv1->step)) 1294 return false; 1295 1296 /* Ignore loops of while (i-- < 10) type. */ 1297 if (code != NE_EXPR) 1298 { 1299 if (iv0->step && tree_int_cst_sign_bit (iv0->step)) 1300 return false; 1301 1302 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) 1303 return false; 1304 } 1305 1306 /* If the loop exits immediately, there is nothing to do. */ 1307 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) 1308 { 1309 niter->niter = build_int_cst (unsigned_type_for (type), 0); 1310 niter->max = double_int_zero; 1311 return true; 1312 } 1313 1314 /* OK, now we know we have a senseful loop. Handle several cases, depending 1315 on what comparison operator is used. */ 1316 bound_difference (loop, iv1->base, iv0->base, &bnds); 1317 1318 if (dump_file && (dump_flags & TDF_DETAILS)) 1319 { 1320 fprintf (dump_file, 1321 "Analyzing # of iterations of loop %d\n", loop->num); 1322 1323 fprintf (dump_file, " exit condition "); 1324 dump_affine_iv (dump_file, iv0); 1325 fprintf (dump_file, " %s ", 1326 code == NE_EXPR ? "!=" 1327 : code == LT_EXPR ? "<" 1328 : "<="); 1329 dump_affine_iv (dump_file, iv1); 1330 fprintf (dump_file, "\n"); 1331 1332 fprintf (dump_file, " bounds on difference of bases: "); 1333 mpz_out_str (dump_file, 10, bnds.below); 1334 fprintf (dump_file, " ... "); 1335 mpz_out_str (dump_file, 10, bnds.up); 1336 fprintf (dump_file, "\n"); 1337 } 1338 1339 switch (code) 1340 { 1341 case NE_EXPR: 1342 gcc_assert (integer_zerop (iv1->step)); 1343 ret = number_of_iterations_ne (type, iv0, iv1->base, niter, 1344 exit_must_be_taken, &bnds); 1345 break; 1346 1347 case LT_EXPR: 1348 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken, 1349 &bnds); 1350 break; 1351 1352 case LE_EXPR: 1353 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken, 1354 &bnds); 1355 break; 1356 1357 default: 1358 gcc_unreachable (); 1359 } 1360 1361 mpz_clear (bnds.up); 1362 mpz_clear (bnds.below); 1363 1364 if (dump_file && (dump_flags & TDF_DETAILS)) 1365 { 1366 if (ret) 1367 { 1368 fprintf (dump_file, " result:\n"); 1369 if (!integer_nonzerop (niter->assumptions)) 1370 { 1371 fprintf (dump_file, " under assumptions "); 1372 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM); 1373 fprintf (dump_file, "\n"); 1374 } 1375 1376 if (!integer_zerop (niter->may_be_zero)) 1377 { 1378 fprintf (dump_file, " zero if "); 1379 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM); 1380 fprintf (dump_file, "\n"); 1381 } 1382 1383 fprintf (dump_file, " # of iterations "); 1384 print_generic_expr (dump_file, niter->niter, TDF_SLIM); 1385 fprintf (dump_file, ", bounded by "); 1386 dump_double_int (dump_file, niter->max, true); 1387 fprintf (dump_file, "\n"); 1388 } 1389 else 1390 fprintf (dump_file, " failed\n\n"); 1391 } 1392 return ret; 1393 } 1394 1395 /* Substitute NEW for OLD in EXPR and fold the result. */ 1396 1397 static tree 1398 simplify_replace_tree (tree expr, tree old, tree new_tree) 1399 { 1400 unsigned i, n; 1401 tree ret = NULL_TREE, e, se; 1402 1403 if (!expr) 1404 return NULL_TREE; 1405 1406 /* Do not bother to replace constants. */ 1407 if (CONSTANT_CLASS_P (old)) 1408 return expr; 1409 1410 if (expr == old 1411 || operand_equal_p (expr, old, 0)) 1412 return unshare_expr (new_tree); 1413 1414 if (!EXPR_P (expr)) 1415 return expr; 1416 1417 n = TREE_OPERAND_LENGTH (expr); 1418 for (i = 0; i < n; i++) 1419 { 1420 e = TREE_OPERAND (expr, i); 1421 se = simplify_replace_tree (e, old, new_tree); 1422 if (e == se) 1423 continue; 1424 1425 if (!ret) 1426 ret = copy_node (expr); 1427 1428 TREE_OPERAND (ret, i) = se; 1429 } 1430 1431 return (ret ? fold (ret) : expr); 1432 } 1433 1434 /* Expand definitions of ssa names in EXPR as long as they are simple 1435 enough, and return the new expression. */ 1436 1437 tree 1438 expand_simple_operations (tree expr) 1439 { 1440 unsigned i, n; 1441 tree ret = NULL_TREE, e, ee, e1; 1442 enum tree_code code; 1443 gimple stmt; 1444 1445 if (expr == NULL_TREE) 1446 return expr; 1447 1448 if (is_gimple_min_invariant (expr)) 1449 return expr; 1450 1451 code = TREE_CODE (expr); 1452 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) 1453 { 1454 n = TREE_OPERAND_LENGTH (expr); 1455 for (i = 0; i < n; i++) 1456 { 1457 e = TREE_OPERAND (expr, i); 1458 ee = expand_simple_operations (e); 1459 if (e == ee) 1460 continue; 1461 1462 if (!ret) 1463 ret = copy_node (expr); 1464 1465 TREE_OPERAND (ret, i) = ee; 1466 } 1467 1468 if (!ret) 1469 return expr; 1470 1471 fold_defer_overflow_warnings (); 1472 ret = fold (ret); 1473 fold_undefer_and_ignore_overflow_warnings (); 1474 return ret; 1475 } 1476 1477 if (TREE_CODE (expr) != SSA_NAME) 1478 return expr; 1479 1480 stmt = SSA_NAME_DEF_STMT (expr); 1481 if (gimple_code (stmt) == GIMPLE_PHI) 1482 { 1483 basic_block src, dest; 1484 1485 if (gimple_phi_num_args (stmt) != 1) 1486 return expr; 1487 e = PHI_ARG_DEF (stmt, 0); 1488 1489 /* Avoid propagating through loop exit phi nodes, which 1490 could break loop-closed SSA form restrictions. */ 1491 dest = gimple_bb (stmt); 1492 src = single_pred (dest); 1493 if (TREE_CODE (e) == SSA_NAME 1494 && src->loop_father != dest->loop_father) 1495 return expr; 1496 1497 return expand_simple_operations (e); 1498 } 1499 if (gimple_code (stmt) != GIMPLE_ASSIGN) 1500 return expr; 1501 1502 e = gimple_assign_rhs1 (stmt); 1503 code = gimple_assign_rhs_code (stmt); 1504 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 1505 { 1506 if (is_gimple_min_invariant (e)) 1507 return e; 1508 1509 if (code == SSA_NAME) 1510 return expand_simple_operations (e); 1511 1512 return expr; 1513 } 1514 1515 switch (code) 1516 { 1517 CASE_CONVERT: 1518 /* Casts are simple. */ 1519 ee = expand_simple_operations (e); 1520 return fold_build1 (code, TREE_TYPE (expr), ee); 1521 1522 case PLUS_EXPR: 1523 case MINUS_EXPR: 1524 case POINTER_PLUS_EXPR: 1525 /* And increments and decrements by a constant are simple. */ 1526 e1 = gimple_assign_rhs2 (stmt); 1527 if (!is_gimple_min_invariant (e1)) 1528 return expr; 1529 1530 ee = expand_simple_operations (e); 1531 return fold_build2 (code, TREE_TYPE (expr), ee, e1); 1532 1533 default: 1534 return expr; 1535 } 1536 } 1537 1538 /* Tries to simplify EXPR using the condition COND. Returns the simplified 1539 expression (or EXPR unchanged, if no simplification was possible). */ 1540 1541 static tree 1542 tree_simplify_using_condition_1 (tree cond, tree expr) 1543 { 1544 bool changed; 1545 tree e, te, e0, e1, e2, notcond; 1546 enum tree_code code = TREE_CODE (expr); 1547 1548 if (code == INTEGER_CST) 1549 return expr; 1550 1551 if (code == TRUTH_OR_EXPR 1552 || code == TRUTH_AND_EXPR 1553 || code == COND_EXPR) 1554 { 1555 changed = false; 1556 1557 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); 1558 if (TREE_OPERAND (expr, 0) != e0) 1559 changed = true; 1560 1561 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); 1562 if (TREE_OPERAND (expr, 1) != e1) 1563 changed = true; 1564 1565 if (code == COND_EXPR) 1566 { 1567 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); 1568 if (TREE_OPERAND (expr, 2) != e2) 1569 changed = true; 1570 } 1571 else 1572 e2 = NULL_TREE; 1573 1574 if (changed) 1575 { 1576 if (code == COND_EXPR) 1577 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 1578 else 1579 expr = fold_build2 (code, boolean_type_node, e0, e1); 1580 } 1581 1582 return expr; 1583 } 1584 1585 /* In case COND is equality, we may be able to simplify EXPR by copy/constant 1586 propagation, and vice versa. Fold does not handle this, since it is 1587 considered too expensive. */ 1588 if (TREE_CODE (cond) == EQ_EXPR) 1589 { 1590 e0 = TREE_OPERAND (cond, 0); 1591 e1 = TREE_OPERAND (cond, 1); 1592 1593 /* We know that e0 == e1. Check whether we cannot simplify expr 1594 using this fact. */ 1595 e = simplify_replace_tree (expr, e0, e1); 1596 if (integer_zerop (e) || integer_nonzerop (e)) 1597 return e; 1598 1599 e = simplify_replace_tree (expr, e1, e0); 1600 if (integer_zerop (e) || integer_nonzerop (e)) 1601 return e; 1602 } 1603 if (TREE_CODE (expr) == EQ_EXPR) 1604 { 1605 e0 = TREE_OPERAND (expr, 0); 1606 e1 = TREE_OPERAND (expr, 1); 1607 1608 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ 1609 e = simplify_replace_tree (cond, e0, e1); 1610 if (integer_zerop (e)) 1611 return e; 1612 e = simplify_replace_tree (cond, e1, e0); 1613 if (integer_zerop (e)) 1614 return e; 1615 } 1616 if (TREE_CODE (expr) == NE_EXPR) 1617 { 1618 e0 = TREE_OPERAND (expr, 0); 1619 e1 = TREE_OPERAND (expr, 1); 1620 1621 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ 1622 e = simplify_replace_tree (cond, e0, e1); 1623 if (integer_zerop (e)) 1624 return boolean_true_node; 1625 e = simplify_replace_tree (cond, e1, e0); 1626 if (integer_zerop (e)) 1627 return boolean_true_node; 1628 } 1629 1630 te = expand_simple_operations (expr); 1631 1632 /* Check whether COND ==> EXPR. */ 1633 notcond = invert_truthvalue (cond); 1634 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te); 1635 if (e && integer_nonzerop (e)) 1636 return e; 1637 1638 /* Check whether COND ==> not EXPR. */ 1639 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); 1640 if (e && integer_zerop (e)) 1641 return e; 1642 1643 return expr; 1644 } 1645 1646 /* Tries to simplify EXPR using the condition COND. Returns the simplified 1647 expression (or EXPR unchanged, if no simplification was possible). 1648 Wrapper around tree_simplify_using_condition_1 that ensures that chains 1649 of simple operations in definitions of ssa names in COND are expanded, 1650 so that things like casts or incrementing the value of the bound before 1651 the loop do not cause us to fail. */ 1652 1653 static tree 1654 tree_simplify_using_condition (tree cond, tree expr) 1655 { 1656 cond = expand_simple_operations (cond); 1657 1658 return tree_simplify_using_condition_1 (cond, expr); 1659 } 1660 1661 /* Tries to simplify EXPR using the conditions on entry to LOOP. 1662 Returns the simplified expression (or EXPR unchanged, if no 1663 simplification was possible).*/ 1664 1665 static tree 1666 simplify_using_initial_conditions (struct loop *loop, tree expr) 1667 { 1668 edge e; 1669 basic_block bb; 1670 gimple stmt; 1671 tree cond; 1672 int cnt = 0; 1673 1674 if (TREE_CODE (expr) == INTEGER_CST) 1675 return expr; 1676 1677 /* Limit walking the dominators to avoid quadraticness in 1678 the number of BBs times the number of loops in degenerate 1679 cases. */ 1680 for (bb = loop->header; 1681 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; 1682 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 1683 { 1684 if (!single_pred_p (bb)) 1685 continue; 1686 e = single_pred_edge (bb); 1687 1688 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 1689 continue; 1690 1691 stmt = last_stmt (e->src); 1692 cond = fold_build2 (gimple_cond_code (stmt), 1693 boolean_type_node, 1694 gimple_cond_lhs (stmt), 1695 gimple_cond_rhs (stmt)); 1696 if (e->flags & EDGE_FALSE_VALUE) 1697 cond = invert_truthvalue (cond); 1698 expr = tree_simplify_using_condition (cond, expr); 1699 ++cnt; 1700 } 1701 1702 return expr; 1703 } 1704 1705 /* Tries to simplify EXPR using the evolutions of the loop invariants 1706 in the superloops of LOOP. Returns the simplified expression 1707 (or EXPR unchanged, if no simplification was possible). */ 1708 1709 static tree 1710 simplify_using_outer_evolutions (struct loop *loop, tree expr) 1711 { 1712 enum tree_code code = TREE_CODE (expr); 1713 bool changed; 1714 tree e, e0, e1, e2; 1715 1716 if (is_gimple_min_invariant (expr)) 1717 return expr; 1718 1719 if (code == TRUTH_OR_EXPR 1720 || code == TRUTH_AND_EXPR 1721 || code == COND_EXPR) 1722 { 1723 changed = false; 1724 1725 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); 1726 if (TREE_OPERAND (expr, 0) != e0) 1727 changed = true; 1728 1729 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); 1730 if (TREE_OPERAND (expr, 1) != e1) 1731 changed = true; 1732 1733 if (code == COND_EXPR) 1734 { 1735 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); 1736 if (TREE_OPERAND (expr, 2) != e2) 1737 changed = true; 1738 } 1739 else 1740 e2 = NULL_TREE; 1741 1742 if (changed) 1743 { 1744 if (code == COND_EXPR) 1745 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 1746 else 1747 expr = fold_build2 (code, boolean_type_node, e0, e1); 1748 } 1749 1750 return expr; 1751 } 1752 1753 e = instantiate_parameters (loop, expr); 1754 if (is_gimple_min_invariant (e)) 1755 return e; 1756 1757 return expr; 1758 } 1759 1760 /* Returns true if EXIT is the only possible exit from LOOP. */ 1761 1762 bool 1763 loop_only_exit_p (const struct loop *loop, const_edge exit) 1764 { 1765 basic_block *body; 1766 gimple_stmt_iterator bsi; 1767 unsigned i; 1768 gimple call; 1769 1770 if (exit != single_exit (loop)) 1771 return false; 1772 1773 body = get_loop_body (loop); 1774 for (i = 0; i < loop->num_nodes; i++) 1775 { 1776 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi)) 1777 { 1778 call = gsi_stmt (bsi); 1779 if (gimple_code (call) != GIMPLE_CALL) 1780 continue; 1781 1782 if (gimple_has_side_effects (call)) 1783 { 1784 free (body); 1785 return false; 1786 } 1787 } 1788 } 1789 1790 free (body); 1791 return true; 1792 } 1793 1794 /* Stores description of number of iterations of LOOP derived from 1795 EXIT (an exit edge of the LOOP) in NITER. Returns true if some 1796 useful information could be derived (and fields of NITER has 1797 meaning described in comments at struct tree_niter_desc 1798 declaration), false otherwise. If WARN is true and 1799 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use 1800 potentially unsafe assumptions. */ 1801 1802 bool 1803 number_of_iterations_exit (struct loop *loop, edge exit, 1804 struct tree_niter_desc *niter, 1805 bool warn) 1806 { 1807 gimple stmt; 1808 tree type; 1809 tree op0, op1; 1810 enum tree_code code; 1811 affine_iv iv0, iv1; 1812 1813 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) 1814 return false; 1815 1816 niter->assumptions = boolean_false_node; 1817 stmt = last_stmt (exit->src); 1818 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 1819 return false; 1820 1821 /* We want the condition for staying inside loop. */ 1822 code = gimple_cond_code (stmt); 1823 if (exit->flags & EDGE_TRUE_VALUE) 1824 code = invert_tree_comparison (code, false); 1825 1826 switch (code) 1827 { 1828 case GT_EXPR: 1829 case GE_EXPR: 1830 case NE_EXPR: 1831 case LT_EXPR: 1832 case LE_EXPR: 1833 break; 1834 1835 default: 1836 return false; 1837 } 1838 1839 op0 = gimple_cond_lhs (stmt); 1840 op1 = gimple_cond_rhs (stmt); 1841 type = TREE_TYPE (op0); 1842 1843 if (TREE_CODE (type) != INTEGER_TYPE 1844 && !POINTER_TYPE_P (type)) 1845 return false; 1846 1847 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false)) 1848 return false; 1849 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false)) 1850 return false; 1851 1852 /* We don't want to see undefined signed overflow warnings while 1853 computing the number of iterations. */ 1854 fold_defer_overflow_warnings (); 1855 1856 iv0.base = expand_simple_operations (iv0.base); 1857 iv1.base = expand_simple_operations (iv1.base); 1858 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter, 1859 loop_only_exit_p (loop, exit))) 1860 { 1861 fold_undefer_and_ignore_overflow_warnings (); 1862 return false; 1863 } 1864 1865 if (optimize >= 3) 1866 { 1867 niter->assumptions = simplify_using_outer_evolutions (loop, 1868 niter->assumptions); 1869 niter->may_be_zero = simplify_using_outer_evolutions (loop, 1870 niter->may_be_zero); 1871 niter->niter = simplify_using_outer_evolutions (loop, niter->niter); 1872 } 1873 1874 niter->assumptions 1875 = simplify_using_initial_conditions (loop, 1876 niter->assumptions); 1877 niter->may_be_zero 1878 = simplify_using_initial_conditions (loop, 1879 niter->may_be_zero); 1880 1881 fold_undefer_and_ignore_overflow_warnings (); 1882 1883 if (integer_onep (niter->assumptions)) 1884 return true; 1885 1886 /* With -funsafe-loop-optimizations we assume that nothing bad can happen. 1887 But if we can prove that there is overflow or some other source of weird 1888 behavior, ignore the loop even with -funsafe-loop-optimizations. */ 1889 if (integer_zerop (niter->assumptions) || !single_exit (loop)) 1890 return false; 1891 1892 if (flag_unsafe_loop_optimizations) 1893 niter->assumptions = boolean_true_node; 1894 1895 if (warn) 1896 { 1897 const char *wording; 1898 location_t loc = gimple_location (stmt); 1899 1900 /* We can provide a more specific warning if one of the operator is 1901 constant and the other advances by +1 or -1. */ 1902 if (!integer_zerop (iv1.step) 1903 ? (integer_zerop (iv0.step) 1904 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) 1905 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step))) 1906 wording = 1907 flag_unsafe_loop_optimizations 1908 ? N_("assuming that the loop is not infinite") 1909 : N_("cannot optimize possibly infinite loops"); 1910 else 1911 wording = 1912 flag_unsafe_loop_optimizations 1913 ? N_("assuming that the loop counter does not overflow") 1914 : N_("cannot optimize loop, the loop counter may overflow"); 1915 1916 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location, 1917 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); 1918 } 1919 1920 return flag_unsafe_loop_optimizations; 1921 } 1922 1923 /* Try to determine the number of iterations of LOOP. If we succeed, 1924 expression giving number of iterations is returned and *EXIT is 1925 set to the edge from that the information is obtained. Otherwise 1926 chrec_dont_know is returned. */ 1927 1928 tree 1929 find_loop_niter (struct loop *loop, edge *exit) 1930 { 1931 unsigned i; 1932 VEC (edge, heap) *exits = get_loop_exit_edges (loop); 1933 edge ex; 1934 tree niter = NULL_TREE, aniter; 1935 struct tree_niter_desc desc; 1936 1937 *exit = NULL; 1938 FOR_EACH_VEC_ELT (edge, exits, i, ex) 1939 { 1940 if (!just_once_each_iteration_p (loop, ex->src)) 1941 continue; 1942 1943 if (!number_of_iterations_exit (loop, ex, &desc, false)) 1944 continue; 1945 1946 if (integer_nonzerop (desc.may_be_zero)) 1947 { 1948 /* We exit in the first iteration through this exit. 1949 We won't find anything better. */ 1950 niter = build_int_cst (unsigned_type_node, 0); 1951 *exit = ex; 1952 break; 1953 } 1954 1955 if (!integer_zerop (desc.may_be_zero)) 1956 continue; 1957 1958 aniter = desc.niter; 1959 1960 if (!niter) 1961 { 1962 /* Nothing recorded yet. */ 1963 niter = aniter; 1964 *exit = ex; 1965 continue; 1966 } 1967 1968 /* Prefer constants, the lower the better. */ 1969 if (TREE_CODE (aniter) != INTEGER_CST) 1970 continue; 1971 1972 if (TREE_CODE (niter) != INTEGER_CST) 1973 { 1974 niter = aniter; 1975 *exit = ex; 1976 continue; 1977 } 1978 1979 if (tree_int_cst_lt (aniter, niter)) 1980 { 1981 niter = aniter; 1982 *exit = ex; 1983 continue; 1984 } 1985 } 1986 VEC_free (edge, heap, exits); 1987 1988 return niter ? niter : chrec_dont_know; 1989 } 1990 1991 /* Return true if loop is known to have bounded number of iterations. */ 1992 1993 bool 1994 finite_loop_p (struct loop *loop) 1995 { 1996 unsigned i; 1997 VEC (edge, heap) *exits; 1998 edge ex; 1999 struct tree_niter_desc desc; 2000 bool finite = false; 2001 int flags; 2002 2003 if (flag_unsafe_loop_optimizations) 2004 return true; 2005 flags = flags_from_decl_or_type (current_function_decl); 2006 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) 2007 { 2008 if (dump_file && (dump_flags & TDF_DETAILS)) 2009 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n", 2010 loop->num); 2011 return true; 2012 } 2013 2014 exits = get_loop_exit_edges (loop); 2015 FOR_EACH_VEC_ELT (edge, exits, i, ex) 2016 { 2017 if (!just_once_each_iteration_p (loop, ex->src)) 2018 continue; 2019 2020 if (number_of_iterations_exit (loop, ex, &desc, false)) 2021 { 2022 if (dump_file && (dump_flags & TDF_DETAILS)) 2023 { 2024 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num); 2025 print_generic_expr (dump_file, desc.niter, TDF_SLIM); 2026 fprintf (dump_file, " times\n"); 2027 } 2028 finite = true; 2029 break; 2030 } 2031 } 2032 VEC_free (edge, heap, exits); 2033 return finite; 2034 } 2035 2036 /* 2037 2038 Analysis of a number of iterations of a loop by a brute-force evaluation. 2039 2040 */ 2041 2042 /* Bound on the number of iterations we try to evaluate. */ 2043 2044 #define MAX_ITERATIONS_TO_TRACK \ 2045 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) 2046 2047 /* Returns the loop phi node of LOOP such that ssa name X is derived from its 2048 result by a chain of operations such that all but exactly one of their 2049 operands are constants. */ 2050 2051 static gimple 2052 chain_of_csts_start (struct loop *loop, tree x) 2053 { 2054 gimple stmt = SSA_NAME_DEF_STMT (x); 2055 tree use; 2056 basic_block bb = gimple_bb (stmt); 2057 enum tree_code code; 2058 2059 if (!bb 2060 || !flow_bb_inside_loop_p (loop, bb)) 2061 return NULL; 2062 2063 if (gimple_code (stmt) == GIMPLE_PHI) 2064 { 2065 if (bb == loop->header) 2066 return stmt; 2067 2068 return NULL; 2069 } 2070 2071 if (gimple_code (stmt) != GIMPLE_ASSIGN) 2072 return NULL; 2073 2074 code = gimple_assign_rhs_code (stmt); 2075 if (gimple_references_memory_p (stmt) 2076 || TREE_CODE_CLASS (code) == tcc_reference 2077 || (code == ADDR_EXPR 2078 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) 2079 return NULL; 2080 2081 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); 2082 if (use == NULL_TREE) 2083 return NULL; 2084 2085 return chain_of_csts_start (loop, use); 2086 } 2087 2088 /* Determines whether the expression X is derived from a result of a phi node 2089 in header of LOOP such that 2090 2091 * the derivation of X consists only from operations with constants 2092 * the initial value of the phi node is constant 2093 * the value of the phi node in the next iteration can be derived from the 2094 value in the current iteration by a chain of operations with constants. 2095 2096 If such phi node exists, it is returned, otherwise NULL is returned. */ 2097 2098 static gimple 2099 get_base_for (struct loop *loop, tree x) 2100 { 2101 gimple phi; 2102 tree init, next; 2103 2104 if (is_gimple_min_invariant (x)) 2105 return NULL; 2106 2107 phi = chain_of_csts_start (loop, x); 2108 if (!phi) 2109 return NULL; 2110 2111 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 2112 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 2113 2114 if (TREE_CODE (next) != SSA_NAME) 2115 return NULL; 2116 2117 if (!is_gimple_min_invariant (init)) 2118 return NULL; 2119 2120 if (chain_of_csts_start (loop, next) != phi) 2121 return NULL; 2122 2123 return phi; 2124 } 2125 2126 /* Given an expression X, then 2127 2128 * if X is NULL_TREE, we return the constant BASE. 2129 * otherwise X is a SSA name, whose value in the considered loop is derived 2130 by a chain of operations with constant from a result of a phi node in 2131 the header of the loop. Then we return value of X when the value of the 2132 result of this phi node is given by the constant BASE. */ 2133 2134 static tree 2135 get_val_for (tree x, tree base) 2136 { 2137 gimple stmt; 2138 2139 gcc_assert (is_gimple_min_invariant (base)); 2140 2141 if (!x) 2142 return base; 2143 2144 stmt = SSA_NAME_DEF_STMT (x); 2145 if (gimple_code (stmt) == GIMPLE_PHI) 2146 return base; 2147 2148 gcc_assert (is_gimple_assign (stmt)); 2149 2150 /* STMT must be either an assignment of a single SSA name or an 2151 expression involving an SSA name and a constant. Try to fold that 2152 expression using the value for the SSA name. */ 2153 if (gimple_assign_ssa_name_copy_p (stmt)) 2154 return get_val_for (gimple_assign_rhs1 (stmt), base); 2155 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS 2156 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) 2157 { 2158 return fold_build1 (gimple_assign_rhs_code (stmt), 2159 gimple_expr_type (stmt), 2160 get_val_for (gimple_assign_rhs1 (stmt), base)); 2161 } 2162 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS) 2163 { 2164 tree rhs1 = gimple_assign_rhs1 (stmt); 2165 tree rhs2 = gimple_assign_rhs2 (stmt); 2166 if (TREE_CODE (rhs1) == SSA_NAME) 2167 rhs1 = get_val_for (rhs1, base); 2168 else if (TREE_CODE (rhs2) == SSA_NAME) 2169 rhs2 = get_val_for (rhs2, base); 2170 else 2171 gcc_unreachable (); 2172 return fold_build2 (gimple_assign_rhs_code (stmt), 2173 gimple_expr_type (stmt), rhs1, rhs2); 2174 } 2175 else 2176 gcc_unreachable (); 2177 } 2178 2179 2180 /* Tries to count the number of iterations of LOOP till it exits by EXIT 2181 by brute force -- i.e. by determining the value of the operands of the 2182 condition at EXIT in first few iterations of the loop (assuming that 2183 these values are constant) and determining the first one in that the 2184 condition is not satisfied. Returns the constant giving the number 2185 of the iterations of LOOP if successful, chrec_dont_know otherwise. */ 2186 2187 tree 2188 loop_niter_by_eval (struct loop *loop, edge exit) 2189 { 2190 tree acnd; 2191 tree op[2], val[2], next[2], aval[2]; 2192 gimple phi, cond; 2193 unsigned i, j; 2194 enum tree_code cmp; 2195 2196 cond = last_stmt (exit->src); 2197 if (!cond || gimple_code (cond) != GIMPLE_COND) 2198 return chrec_dont_know; 2199 2200 cmp = gimple_cond_code (cond); 2201 if (exit->flags & EDGE_TRUE_VALUE) 2202 cmp = invert_tree_comparison (cmp, false); 2203 2204 switch (cmp) 2205 { 2206 case EQ_EXPR: 2207 case NE_EXPR: 2208 case GT_EXPR: 2209 case GE_EXPR: 2210 case LT_EXPR: 2211 case LE_EXPR: 2212 op[0] = gimple_cond_lhs (cond); 2213 op[1] = gimple_cond_rhs (cond); 2214 break; 2215 2216 default: 2217 return chrec_dont_know; 2218 } 2219 2220 for (j = 0; j < 2; j++) 2221 { 2222 if (is_gimple_min_invariant (op[j])) 2223 { 2224 val[j] = op[j]; 2225 next[j] = NULL_TREE; 2226 op[j] = NULL_TREE; 2227 } 2228 else 2229 { 2230 phi = get_base_for (loop, op[j]); 2231 if (!phi) 2232 return chrec_dont_know; 2233 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 2234 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 2235 } 2236 } 2237 2238 /* Don't issue signed overflow warnings. */ 2239 fold_defer_overflow_warnings (); 2240 2241 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) 2242 { 2243 for (j = 0; j < 2; j++) 2244 aval[j] = get_val_for (op[j], val[j]); 2245 2246 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]); 2247 if (acnd && integer_zerop (acnd)) 2248 { 2249 fold_undefer_and_ignore_overflow_warnings (); 2250 if (dump_file && (dump_flags & TDF_DETAILS)) 2251 fprintf (dump_file, 2252 "Proved that loop %d iterates %d times using brute force.\n", 2253 loop->num, i); 2254 return build_int_cst (unsigned_type_node, i); 2255 } 2256 2257 for (j = 0; j < 2; j++) 2258 { 2259 val[j] = get_val_for (next[j], val[j]); 2260 if (!is_gimple_min_invariant (val[j])) 2261 { 2262 fold_undefer_and_ignore_overflow_warnings (); 2263 return chrec_dont_know; 2264 } 2265 } 2266 } 2267 2268 fold_undefer_and_ignore_overflow_warnings (); 2269 2270 return chrec_dont_know; 2271 } 2272 2273 /* Finds the exit of the LOOP by that the loop exits after a constant 2274 number of iterations and stores the exit edge to *EXIT. The constant 2275 giving the number of iterations of LOOP is returned. The number of 2276 iterations is determined using loop_niter_by_eval (i.e. by brute force 2277 evaluation). If we are unable to find the exit for that loop_niter_by_eval 2278 determines the number of iterations, chrec_dont_know is returned. */ 2279 2280 tree 2281 find_loop_niter_by_eval (struct loop *loop, edge *exit) 2282 { 2283 unsigned i; 2284 VEC (edge, heap) *exits = get_loop_exit_edges (loop); 2285 edge ex; 2286 tree niter = NULL_TREE, aniter; 2287 2288 *exit = NULL; 2289 2290 /* Loops with multiple exits are expensive to handle and less important. */ 2291 if (!flag_expensive_optimizations 2292 && VEC_length (edge, exits) > 1) 2293 { 2294 VEC_free (edge, heap, exits); 2295 return chrec_dont_know; 2296 } 2297 2298 FOR_EACH_VEC_ELT (edge, exits, i, ex) 2299 { 2300 if (!just_once_each_iteration_p (loop, ex->src)) 2301 continue; 2302 2303 aniter = loop_niter_by_eval (loop, ex); 2304 if (chrec_contains_undetermined (aniter)) 2305 continue; 2306 2307 if (niter 2308 && !tree_int_cst_lt (aniter, niter)) 2309 continue; 2310 2311 niter = aniter; 2312 *exit = ex; 2313 } 2314 VEC_free (edge, heap, exits); 2315 2316 return niter ? niter : chrec_dont_know; 2317 } 2318 2319 /* 2320 2321 Analysis of upper bounds on number of iterations of a loop. 2322 2323 */ 2324 2325 static double_int derive_constant_upper_bound_ops (tree, tree, 2326 enum tree_code, tree); 2327 2328 /* Returns a constant upper bound on the value of the right-hand side of 2329 an assignment statement STMT. */ 2330 2331 static double_int 2332 derive_constant_upper_bound_assign (gimple stmt) 2333 { 2334 enum tree_code code = gimple_assign_rhs_code (stmt); 2335 tree op0 = gimple_assign_rhs1 (stmt); 2336 tree op1 = gimple_assign_rhs2 (stmt); 2337 2338 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)), 2339 op0, code, op1); 2340 } 2341 2342 /* Returns a constant upper bound on the value of expression VAL. VAL 2343 is considered to be unsigned. If its type is signed, its value must 2344 be nonnegative. */ 2345 2346 static double_int 2347 derive_constant_upper_bound (tree val) 2348 { 2349 enum tree_code code; 2350 tree op0, op1; 2351 2352 extract_ops_from_tree (val, &code, &op0, &op1); 2353 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1); 2354 } 2355 2356 /* Returns a constant upper bound on the value of expression OP0 CODE OP1, 2357 whose type is TYPE. The expression is considered to be unsigned. If 2358 its type is signed, its value must be nonnegative. */ 2359 2360 static double_int 2361 derive_constant_upper_bound_ops (tree type, tree op0, 2362 enum tree_code code, tree op1) 2363 { 2364 tree subtype, maxt; 2365 double_int bnd, max, mmax, cst; 2366 gimple stmt; 2367 2368 if (INTEGRAL_TYPE_P (type)) 2369 maxt = TYPE_MAX_VALUE (type); 2370 else 2371 maxt = upper_bound_in_type (type, type); 2372 2373 max = tree_to_double_int (maxt); 2374 2375 switch (code) 2376 { 2377 case INTEGER_CST: 2378 return tree_to_double_int (op0); 2379 2380 CASE_CONVERT: 2381 subtype = TREE_TYPE (op0); 2382 if (!TYPE_UNSIGNED (subtype) 2383 /* If TYPE is also signed, the fact that VAL is nonnegative implies 2384 that OP0 is nonnegative. */ 2385 && TYPE_UNSIGNED (type) 2386 && !tree_expr_nonnegative_p (op0)) 2387 { 2388 /* If we cannot prove that the casted expression is nonnegative, 2389 we cannot establish more useful upper bound than the precision 2390 of the type gives us. */ 2391 return max; 2392 } 2393 2394 /* We now know that op0 is an nonnegative value. Try deriving an upper 2395 bound for it. */ 2396 bnd = derive_constant_upper_bound (op0); 2397 2398 /* If the bound does not fit in TYPE, max. value of TYPE could be 2399 attained. */ 2400 if (double_int_ucmp (max, bnd) < 0) 2401 return max; 2402 2403 return bnd; 2404 2405 case PLUS_EXPR: 2406 case POINTER_PLUS_EXPR: 2407 case MINUS_EXPR: 2408 if (TREE_CODE (op1) != INTEGER_CST 2409 || !tree_expr_nonnegative_p (op0)) 2410 return max; 2411 2412 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to 2413 choose the most logical way how to treat this constant regardless 2414 of the signedness of the type. */ 2415 cst = tree_to_double_int (op1); 2416 cst = double_int_sext (cst, TYPE_PRECISION (type)); 2417 if (code != MINUS_EXPR) 2418 cst = double_int_neg (cst); 2419 2420 bnd = derive_constant_upper_bound (op0); 2421 2422 if (double_int_negative_p (cst)) 2423 { 2424 cst = double_int_neg (cst); 2425 /* Avoid CST == 0x80000... */ 2426 if (double_int_negative_p (cst)) 2427 return max;; 2428 2429 /* OP0 + CST. We need to check that 2430 BND <= MAX (type) - CST. */ 2431 2432 mmax = double_int_sub (max, cst); 2433 if (double_int_ucmp (bnd, mmax) > 0) 2434 return max; 2435 2436 return double_int_add (bnd, cst); 2437 } 2438 else 2439 { 2440 /* OP0 - CST, where CST >= 0. 2441 2442 If TYPE is signed, we have already verified that OP0 >= 0, and we 2443 know that the result is nonnegative. This implies that 2444 VAL <= BND - CST. 2445 2446 If TYPE is unsigned, we must additionally know that OP0 >= CST, 2447 otherwise the operation underflows. 2448 */ 2449 2450 /* This should only happen if the type is unsigned; however, for 2451 buggy programs that use overflowing signed arithmetics even with 2452 -fno-wrapv, this condition may also be true for signed values. */ 2453 if (double_int_ucmp (bnd, cst) < 0) 2454 return max; 2455 2456 if (TYPE_UNSIGNED (type)) 2457 { 2458 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0, 2459 double_int_to_tree (type, cst)); 2460 if (!tem || integer_nonzerop (tem)) 2461 return max; 2462 } 2463 2464 bnd = double_int_sub (bnd, cst); 2465 } 2466 2467 return bnd; 2468 2469 case FLOOR_DIV_EXPR: 2470 case EXACT_DIV_EXPR: 2471 if (TREE_CODE (op1) != INTEGER_CST 2472 || tree_int_cst_sign_bit (op1)) 2473 return max; 2474 2475 bnd = derive_constant_upper_bound (op0); 2476 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); 2477 2478 case BIT_AND_EXPR: 2479 if (TREE_CODE (op1) != INTEGER_CST 2480 || tree_int_cst_sign_bit (op1)) 2481 return max; 2482 return tree_to_double_int (op1); 2483 2484 case SSA_NAME: 2485 stmt = SSA_NAME_DEF_STMT (op0); 2486 if (gimple_code (stmt) != GIMPLE_ASSIGN 2487 || gimple_assign_lhs (stmt) != op0) 2488 return max; 2489 return derive_constant_upper_bound_assign (stmt); 2490 2491 default: 2492 return max; 2493 } 2494 } 2495 2496 /* Records that every statement in LOOP is executed I_BOUND times. 2497 REALISTIC is true if I_BOUND is expected to be close to the real number 2498 of iterations. UPPER is true if we are sure the loop iterates at most 2499 I_BOUND times. */ 2500 2501 static void 2502 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, 2503 bool upper) 2504 { 2505 /* Update the bounds only when there is no previous estimation, or when the current 2506 estimation is smaller. */ 2507 if (upper 2508 && (!loop->any_upper_bound 2509 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0)) 2510 { 2511 loop->any_upper_bound = true; 2512 loop->nb_iterations_upper_bound = i_bound; 2513 } 2514 if (realistic 2515 && (!loop->any_estimate 2516 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0)) 2517 { 2518 loop->any_estimate = true; 2519 loop->nb_iterations_estimate = i_bound; 2520 } 2521 } 2522 2523 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT 2524 is true if the loop is exited immediately after STMT, and this exit 2525 is taken at last when the STMT is executed BOUND + 1 times. 2526 REALISTIC is true if BOUND is expected to be close to the real number 2527 of iterations. UPPER is true if we are sure the loop iterates at most 2528 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */ 2529 2530 static void 2531 record_estimate (struct loop *loop, tree bound, double_int i_bound, 2532 gimple at_stmt, bool is_exit, bool realistic, bool upper) 2533 { 2534 double_int delta; 2535 edge exit; 2536 2537 if (dump_file && (dump_flags & TDF_DETAILS)) 2538 { 2539 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : ""); 2540 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM); 2541 fprintf (dump_file, " is %sexecuted at most ", 2542 upper ? "" : "probably "); 2543 print_generic_expr (dump_file, bound, TDF_SLIM); 2544 fprintf (dump_file, " (bounded by "); 2545 dump_double_int (dump_file, i_bound, true); 2546 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num); 2547 } 2548 2549 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the 2550 real number of iterations. */ 2551 if (TREE_CODE (bound) != INTEGER_CST) 2552 realistic = false; 2553 if (!upper && !realistic) 2554 return; 2555 2556 /* If we have a guaranteed upper bound, record it in the appropriate 2557 list. */ 2558 if (upper) 2559 { 2560 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound (); 2561 2562 elt->bound = i_bound; 2563 elt->stmt = at_stmt; 2564 elt->is_exit = is_exit; 2565 elt->next = loop->bounds; 2566 loop->bounds = elt; 2567 } 2568 2569 /* Update the number of iteration estimates according to the bound. 2570 If at_stmt is an exit or dominates the single exit from the loop, 2571 then the loop latch is executed at most BOUND times, otherwise 2572 it can be executed BOUND + 1 times. */ 2573 exit = single_exit (loop); 2574 if (is_exit 2575 || (exit != NULL 2576 && dominated_by_p (CDI_DOMINATORS, 2577 exit->src, gimple_bb (at_stmt)))) 2578 delta = double_int_zero; 2579 else 2580 delta = double_int_one; 2581 i_bound = double_int_add (i_bound, delta); 2582 2583 /* If an overflow occurred, ignore the result. */ 2584 if (double_int_ucmp (i_bound, delta) < 0) 2585 return; 2586 2587 record_niter_bound (loop, i_bound, realistic, upper); 2588 } 2589 2590 /* Record the estimate on number of iterations of LOOP based on the fact that 2591 the induction variable BASE + STEP * i evaluated in STMT does not wrap and 2592 its values belong to the range <LOW, HIGH>. REALISTIC is true if the 2593 estimated number of iterations is expected to be close to the real one. 2594 UPPER is true if we are sure the induction variable does not wrap. */ 2595 2596 static void 2597 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, 2598 tree low, tree high, bool realistic, bool upper) 2599 { 2600 tree niter_bound, extreme, delta; 2601 tree type = TREE_TYPE (base), unsigned_type; 2602 double_int max; 2603 2604 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) 2605 return; 2606 2607 if (dump_file && (dump_flags & TDF_DETAILS)) 2608 { 2609 fprintf (dump_file, "Induction variable ("); 2610 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM); 2611 fprintf (dump_file, ") "); 2612 print_generic_expr (dump_file, base, TDF_SLIM); 2613 fprintf (dump_file, " + "); 2614 print_generic_expr (dump_file, step, TDF_SLIM); 2615 fprintf (dump_file, " * iteration does not wrap in statement "); 2616 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2617 fprintf (dump_file, " in loop %d.\n", loop->num); 2618 } 2619 2620 unsigned_type = unsigned_type_for (type); 2621 base = fold_convert (unsigned_type, base); 2622 step = fold_convert (unsigned_type, step); 2623 2624 if (tree_int_cst_sign_bit (step)) 2625 { 2626 extreme = fold_convert (unsigned_type, low); 2627 if (TREE_CODE (base) != INTEGER_CST) 2628 base = fold_convert (unsigned_type, high); 2629 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); 2630 step = fold_build1 (NEGATE_EXPR, unsigned_type, step); 2631 } 2632 else 2633 { 2634 extreme = fold_convert (unsigned_type, high); 2635 if (TREE_CODE (base) != INTEGER_CST) 2636 base = fold_convert (unsigned_type, low); 2637 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); 2638 } 2639 2640 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value 2641 would get out of the range. */ 2642 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); 2643 max = derive_constant_upper_bound (niter_bound); 2644 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper); 2645 } 2646 2647 /* Returns true if REF is a reference to an array at the end of a dynamically 2648 allocated structure. If this is the case, the array may be allocated larger 2649 than its upper bound implies. */ 2650 2651 bool 2652 array_at_struct_end_p (tree ref) 2653 { 2654 tree base = get_base_address (ref); 2655 tree parent, field; 2656 2657 /* Unless the reference is through a pointer, the size of the array matches 2658 its declaration. */ 2659 if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF)) 2660 return false; 2661 2662 for (;handled_component_p (ref); ref = parent) 2663 { 2664 parent = TREE_OPERAND (ref, 0); 2665 2666 if (TREE_CODE (ref) == COMPONENT_REF) 2667 { 2668 /* All fields of a union are at its end. */ 2669 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE) 2670 continue; 2671 2672 /* Unless the field is at the end of the struct, we are done. */ 2673 field = TREE_OPERAND (ref, 1); 2674 if (DECL_CHAIN (field)) 2675 return false; 2676 } 2677 2678 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR. 2679 In all these cases, we might be accessing the last element, and 2680 although in practice this will probably never happen, it is legal for 2681 the indices of this last element to exceed the bounds of the array. 2682 Therefore, continue checking. */ 2683 } 2684 2685 return true; 2686 } 2687 2688 /* Determine information about number of iterations a LOOP from the index 2689 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is 2690 guaranteed to be executed in every iteration of LOOP. Callback for 2691 for_each_index. */ 2692 2693 struct ilb_data 2694 { 2695 struct loop *loop; 2696 gimple stmt; 2697 bool reliable; 2698 }; 2699 2700 static bool 2701 idx_infer_loop_bounds (tree base, tree *idx, void *dta) 2702 { 2703 struct ilb_data *data = (struct ilb_data *) dta; 2704 tree ev, init, step; 2705 tree low, high, type, next; 2706 bool sign, upper = data->reliable, at_end = false; 2707 struct loop *loop = data->loop; 2708 2709 if (TREE_CODE (base) != ARRAY_REF) 2710 return true; 2711 2712 /* For arrays at the end of the structure, we are not guaranteed that they 2713 do not really extend over their declared size. However, for arrays of 2714 size greater than one, this is unlikely to be intended. */ 2715 if (array_at_struct_end_p (base)) 2716 { 2717 at_end = true; 2718 upper = false; 2719 } 2720 2721 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx)); 2722 init = initial_condition (ev); 2723 step = evolution_part_in_loop_num (ev, loop->num); 2724 2725 if (!init 2726 || !step 2727 || TREE_CODE (step) != INTEGER_CST 2728 || integer_zerop (step) 2729 || tree_contains_chrecs (init, NULL) 2730 || chrec_contains_symbols_defined_in_loop (init, loop->num)) 2731 return true; 2732 2733 low = array_ref_low_bound (base); 2734 high = array_ref_up_bound (base); 2735 2736 /* The case of nonconstant bounds could be handled, but it would be 2737 complicated. */ 2738 if (TREE_CODE (low) != INTEGER_CST 2739 || !high 2740 || TREE_CODE (high) != INTEGER_CST) 2741 return true; 2742 sign = tree_int_cst_sign_bit (step); 2743 type = TREE_TYPE (step); 2744 2745 /* The array of length 1 at the end of a structure most likely extends 2746 beyond its bounds. */ 2747 if (at_end 2748 && operand_equal_p (low, high, 0)) 2749 return true; 2750 2751 /* In case the relevant bound of the array does not fit in type, or 2752 it does, but bound + step (in type) still belongs into the range of the 2753 array, the index may wrap and still stay within the range of the array 2754 (consider e.g. if the array is indexed by the full range of 2755 unsigned char). 2756 2757 To make things simpler, we require both bounds to fit into type, although 2758 there are cases where this would not be strictly necessary. */ 2759 if (!int_fits_type_p (high, type) 2760 || !int_fits_type_p (low, type)) 2761 return true; 2762 low = fold_convert (type, low); 2763 high = fold_convert (type, high); 2764 2765 if (sign) 2766 next = fold_binary (PLUS_EXPR, type, low, step); 2767 else 2768 next = fold_binary (PLUS_EXPR, type, high, step); 2769 2770 if (tree_int_cst_compare (low, next) <= 0 2771 && tree_int_cst_compare (next, high) <= 0) 2772 return true; 2773 2774 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper); 2775 return true; 2776 } 2777 2778 /* Determine information about number of iterations a LOOP from the bounds 2779 of arrays in the data reference REF accessed in STMT. RELIABLE is true if 2780 STMT is guaranteed to be executed in every iteration of LOOP.*/ 2781 2782 static void 2783 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref, 2784 bool reliable) 2785 { 2786 struct ilb_data data; 2787 2788 data.loop = loop; 2789 data.stmt = stmt; 2790 data.reliable = reliable; 2791 for_each_index (&ref, idx_infer_loop_bounds, &data); 2792 } 2793 2794 /* Determine information about number of iterations of a LOOP from the way 2795 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be 2796 executed in every iteration of LOOP. */ 2797 2798 static void 2799 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable) 2800 { 2801 if (is_gimple_assign (stmt)) 2802 { 2803 tree op0 = gimple_assign_lhs (stmt); 2804 tree op1 = gimple_assign_rhs1 (stmt); 2805 2806 /* For each memory access, analyze its access function 2807 and record a bound on the loop iteration domain. */ 2808 if (REFERENCE_CLASS_P (op0)) 2809 infer_loop_bounds_from_ref (loop, stmt, op0, reliable); 2810 2811 if (REFERENCE_CLASS_P (op1)) 2812 infer_loop_bounds_from_ref (loop, stmt, op1, reliable); 2813 } 2814 else if (is_gimple_call (stmt)) 2815 { 2816 tree arg, lhs; 2817 unsigned i, n = gimple_call_num_args (stmt); 2818 2819 lhs = gimple_call_lhs (stmt); 2820 if (lhs && REFERENCE_CLASS_P (lhs)) 2821 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable); 2822 2823 for (i = 0; i < n; i++) 2824 { 2825 arg = gimple_call_arg (stmt, i); 2826 if (REFERENCE_CLASS_P (arg)) 2827 infer_loop_bounds_from_ref (loop, stmt, arg, reliable); 2828 } 2829 } 2830 } 2831 2832 /* Determine information about number of iterations of a LOOP from the fact 2833 that pointer arithmetics in STMT does not overflow. */ 2834 2835 static void 2836 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt) 2837 { 2838 tree def, base, step, scev, type, low, high; 2839 tree var, ptr; 2840 2841 if (!is_gimple_assign (stmt) 2842 || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) 2843 return; 2844 2845 def = gimple_assign_lhs (stmt); 2846 if (TREE_CODE (def) != SSA_NAME) 2847 return; 2848 2849 type = TREE_TYPE (def); 2850 if (!nowrap_type_p (type)) 2851 return; 2852 2853 ptr = gimple_assign_rhs1 (stmt); 2854 if (!expr_invariant_in_loop_p (loop, ptr)) 2855 return; 2856 2857 var = gimple_assign_rhs2 (stmt); 2858 if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) 2859 return; 2860 2861 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); 2862 if (chrec_contains_undetermined (scev)) 2863 return; 2864 2865 base = initial_condition_in_loop_num (scev, loop->num); 2866 step = evolution_part_in_loop_num (scev, loop->num); 2867 2868 if (!base || !step 2869 || TREE_CODE (step) != INTEGER_CST 2870 || tree_contains_chrecs (base, NULL) 2871 || chrec_contains_symbols_defined_in_loop (base, loop->num)) 2872 return; 2873 2874 low = lower_bound_in_type (type, type); 2875 high = upper_bound_in_type (type, type); 2876 2877 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot 2878 produce a NULL pointer. The contrary would mean NULL points to an object, 2879 while NULL is supposed to compare unequal with the address of all objects. 2880 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a 2881 NULL pointer since that would mean wrapping, which we assume here not to 2882 happen. So, we can exclude NULL from the valid range of pointer 2883 arithmetic. */ 2884 if (flag_delete_null_pointer_checks && int_cst_value (low) == 0) 2885 low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type))); 2886 2887 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); 2888 } 2889 2890 /* Determine information about number of iterations of a LOOP from the fact 2891 that signed arithmetics in STMT does not overflow. */ 2892 2893 static void 2894 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt) 2895 { 2896 tree def, base, step, scev, type, low, high; 2897 2898 if (gimple_code (stmt) != GIMPLE_ASSIGN) 2899 return; 2900 2901 def = gimple_assign_lhs (stmt); 2902 2903 if (TREE_CODE (def) != SSA_NAME) 2904 return; 2905 2906 type = TREE_TYPE (def); 2907 if (!INTEGRAL_TYPE_P (type) 2908 || !TYPE_OVERFLOW_UNDEFINED (type)) 2909 return; 2910 2911 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); 2912 if (chrec_contains_undetermined (scev)) 2913 return; 2914 2915 base = initial_condition_in_loop_num (scev, loop->num); 2916 step = evolution_part_in_loop_num (scev, loop->num); 2917 2918 if (!base || !step 2919 || TREE_CODE (step) != INTEGER_CST 2920 || tree_contains_chrecs (base, NULL) 2921 || chrec_contains_symbols_defined_in_loop (base, loop->num)) 2922 return; 2923 2924 low = lower_bound_in_type (type, type); 2925 high = upper_bound_in_type (type, type); 2926 2927 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); 2928 } 2929 2930 /* The following analyzers are extracting informations on the bounds 2931 of LOOP from the following undefined behaviors: 2932 2933 - data references should not access elements over the statically 2934 allocated size, 2935 2936 - signed variables should not overflow when flag_wrapv is not set. 2937 */ 2938 2939 static void 2940 infer_loop_bounds_from_undefined (struct loop *loop) 2941 { 2942 unsigned i; 2943 basic_block *bbs; 2944 gimple_stmt_iterator bsi; 2945 basic_block bb; 2946 bool reliable; 2947 2948 bbs = get_loop_body (loop); 2949 2950 for (i = 0; i < loop->num_nodes; i++) 2951 { 2952 bb = bbs[i]; 2953 2954 /* If BB is not executed in each iteration of the loop, we cannot 2955 use the operations in it to infer reliable upper bound on the 2956 # of iterations of the loop. However, we can use it as a guess. */ 2957 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); 2958 2959 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 2960 { 2961 gimple stmt = gsi_stmt (bsi); 2962 2963 infer_loop_bounds_from_array (loop, stmt, reliable); 2964 2965 if (reliable) 2966 { 2967 infer_loop_bounds_from_signedness (loop, stmt); 2968 infer_loop_bounds_from_pointer_arith (loop, stmt); 2969 } 2970 } 2971 2972 } 2973 2974 free (bbs); 2975 } 2976 2977 /* Converts VAL to double_int. */ 2978 2979 static double_int 2980 gcov_type_to_double_int (gcov_type val) 2981 { 2982 double_int ret; 2983 2984 ret.low = (unsigned HOST_WIDE_INT) val; 2985 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by 2986 the size of type. */ 2987 val >>= HOST_BITS_PER_WIDE_INT - 1; 2988 val >>= 1; 2989 ret.high = (unsigned HOST_WIDE_INT) val; 2990 2991 return ret; 2992 } 2993 2994 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P 2995 is true also use estimates derived from undefined behavior. */ 2996 2997 void 2998 estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p) 2999 { 3000 VEC (edge, heap) *exits; 3001 tree niter, type; 3002 unsigned i; 3003 struct tree_niter_desc niter_desc; 3004 edge ex; 3005 double_int bound; 3006 3007 /* Give up if we already have tried to compute an estimation. */ 3008 if (loop->estimate_state != EST_NOT_COMPUTED) 3009 return; 3010 loop->estimate_state = EST_AVAILABLE; 3011 loop->any_upper_bound = false; 3012 loop->any_estimate = false; 3013 3014 exits = get_loop_exit_edges (loop); 3015 FOR_EACH_VEC_ELT (edge, exits, i, ex) 3016 { 3017 if (!number_of_iterations_exit (loop, ex, &niter_desc, false)) 3018 continue; 3019 3020 niter = niter_desc.niter; 3021 type = TREE_TYPE (niter); 3022 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST) 3023 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, 3024 build_int_cst (type, 0), 3025 niter); 3026 record_estimate (loop, niter, niter_desc.max, 3027 last_stmt (ex->src), 3028 true, true, true); 3029 } 3030 VEC_free (edge, heap, exits); 3031 3032 if (use_undefined_p) 3033 infer_loop_bounds_from_undefined (loop); 3034 3035 /* If we have a measured profile, use it to estimate the number of 3036 iterations. */ 3037 if (loop->header->count != 0) 3038 { 3039 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1; 3040 bound = gcov_type_to_double_int (nit); 3041 record_niter_bound (loop, bound, true, false); 3042 } 3043 3044 /* If an upper bound is smaller than the realistic estimate of the 3045 number of iterations, use the upper bound instead. */ 3046 if (loop->any_upper_bound 3047 && loop->any_estimate 3048 && double_int_ucmp (loop->nb_iterations_upper_bound, 3049 loop->nb_iterations_estimate) < 0) 3050 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; 3051 } 3052 3053 /* Sets NIT to the estimated number of executions of the latch of the 3054 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as 3055 large as the number of iterations. If we have no reliable estimate, 3056 the function returns false, otherwise returns true. */ 3057 3058 bool 3059 estimated_loop_iterations (struct loop *loop, bool conservative, 3060 double_int *nit) 3061 { 3062 estimate_numbers_of_iterations_loop (loop, true); 3063 if (conservative) 3064 { 3065 if (!loop->any_upper_bound) 3066 return false; 3067 3068 *nit = loop->nb_iterations_upper_bound; 3069 } 3070 else 3071 { 3072 if (!loop->any_estimate) 3073 return false; 3074 3075 *nit = loop->nb_iterations_estimate; 3076 } 3077 3078 return true; 3079 } 3080 3081 /* Similar to estimated_loop_iterations, but returns the estimate only 3082 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate 3083 on the number of iterations of LOOP could not be derived, returns -1. */ 3084 3085 HOST_WIDE_INT 3086 estimated_loop_iterations_int (struct loop *loop, bool conservative) 3087 { 3088 double_int nit; 3089 HOST_WIDE_INT hwi_nit; 3090 3091 if (!estimated_loop_iterations (loop, conservative, &nit)) 3092 return -1; 3093 3094 if (!double_int_fits_in_shwi_p (nit)) 3095 return -1; 3096 hwi_nit = double_int_to_shwi (nit); 3097 3098 return hwi_nit < 0 ? -1 : hwi_nit; 3099 } 3100 3101 /* Returns an upper bound on the number of executions of statements 3102 in the LOOP. For statements before the loop exit, this exceeds 3103 the number of execution of the latch by one. */ 3104 3105 HOST_WIDE_INT 3106 max_stmt_executions_int (struct loop *loop, bool conservative) 3107 { 3108 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative); 3109 HOST_WIDE_INT snit; 3110 3111 if (nit == -1) 3112 return -1; 3113 3114 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); 3115 3116 /* If the computation overflows, return -1. */ 3117 return snit < 0 ? -1 : snit; 3118 } 3119 3120 /* Sets NIT to the estimated number of executions of the latch of the 3121 LOOP, plus one. If CONSERVATIVE is true, we must be sure that NIT is at 3122 least as large as the number of iterations. If we have no reliable 3123 estimate, the function returns false, otherwise returns true. */ 3124 3125 bool 3126 max_stmt_executions (struct loop *loop, bool conservative, double_int *nit) 3127 { 3128 double_int nit_minus_one; 3129 3130 if (!estimated_loop_iterations (loop, conservative, nit)) 3131 return false; 3132 3133 nit_minus_one = *nit; 3134 3135 *nit = double_int_add (*nit, double_int_one); 3136 3137 return double_int_ucmp (*nit, nit_minus_one) > 0; 3138 } 3139 3140 /* Records estimates on numbers of iterations of loops. */ 3141 3142 void 3143 estimate_numbers_of_iterations (bool use_undefined_p) 3144 { 3145 loop_iterator li; 3146 struct loop *loop; 3147 3148 /* We don't want to issue signed overflow warnings while getting 3149 loop iteration estimates. */ 3150 fold_defer_overflow_warnings (); 3151 3152 FOR_EACH_LOOP (li, loop, 0) 3153 { 3154 estimate_numbers_of_iterations_loop (loop, use_undefined_p); 3155 } 3156 3157 fold_undefer_and_ignore_overflow_warnings (); 3158 } 3159 3160 /* Returns true if statement S1 dominates statement S2. */ 3161 3162 bool 3163 stmt_dominates_stmt_p (gimple s1, gimple s2) 3164 { 3165 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2); 3166 3167 if (!bb1 3168 || s1 == s2) 3169 return true; 3170 3171 if (bb1 == bb2) 3172 { 3173 gimple_stmt_iterator bsi; 3174 3175 if (gimple_code (s2) == GIMPLE_PHI) 3176 return false; 3177 3178 if (gimple_code (s1) == GIMPLE_PHI) 3179 return true; 3180 3181 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi)) 3182 if (gsi_stmt (bsi) == s1) 3183 return true; 3184 3185 return false; 3186 } 3187 3188 return dominated_by_p (CDI_DOMINATORS, bb2, bb1); 3189 } 3190 3191 /* Returns true when we can prove that the number of executions of 3192 STMT in the loop is at most NITER, according to the bound on 3193 the number of executions of the statement NITER_BOUND->stmt recorded in 3194 NITER_BOUND. If STMT is NULL, we must prove this bound for all 3195 statements in the loop. */ 3196 3197 static bool 3198 n_of_executions_at_most (gimple stmt, 3199 struct nb_iter_bound *niter_bound, 3200 tree niter) 3201 { 3202 double_int bound = niter_bound->bound; 3203 tree nit_type = TREE_TYPE (niter), e; 3204 enum tree_code cmp; 3205 3206 gcc_assert (TYPE_UNSIGNED (nit_type)); 3207 3208 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that 3209 the number of iterations is small. */ 3210 if (!double_int_fits_to_tree_p (nit_type, bound)) 3211 return false; 3212 3213 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 3214 times. This means that: 3215 3216 -- if NITER_BOUND->is_exit is true, then everything before 3217 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 3218 times, and everything after it at most NITER_BOUND->bound times. 3219 3220 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT 3221 is executed, then NITER_BOUND->stmt is executed as well in the same 3222 iteration (we conclude that if both statements belong to the same 3223 basic block, or if STMT is after NITER_BOUND->stmt), then STMT 3224 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is 3225 executed at most NITER_BOUND->bound + 2 times. */ 3226 3227 if (niter_bound->is_exit) 3228 { 3229 if (stmt 3230 && stmt != niter_bound->stmt 3231 && stmt_dominates_stmt_p (niter_bound->stmt, stmt)) 3232 cmp = GE_EXPR; 3233 else 3234 cmp = GT_EXPR; 3235 } 3236 else 3237 { 3238 if (!stmt 3239 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) 3240 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt))) 3241 { 3242 bound = double_int_add (bound, double_int_one); 3243 if (double_int_zero_p (bound) 3244 || !double_int_fits_to_tree_p (nit_type, bound)) 3245 return false; 3246 } 3247 cmp = GT_EXPR; 3248 } 3249 3250 e = fold_binary (cmp, boolean_type_node, 3251 niter, double_int_to_tree (nit_type, bound)); 3252 return e && integer_nonzerop (e); 3253 } 3254 3255 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */ 3256 3257 bool 3258 nowrap_type_p (tree type) 3259 { 3260 if (INTEGRAL_TYPE_P (type) 3261 && TYPE_OVERFLOW_UNDEFINED (type)) 3262 return true; 3263 3264 if (POINTER_TYPE_P (type)) 3265 return true; 3266 3267 return false; 3268 } 3269 3270 /* Return false only when the induction variable BASE + STEP * I is 3271 known to not overflow: i.e. when the number of iterations is small 3272 enough with respect to the step and initial condition in order to 3273 keep the evolution confined in TYPEs bounds. Return true when the 3274 iv is known to overflow or when the property is not computable. 3275 3276 USE_OVERFLOW_SEMANTICS is true if this function should assume that 3277 the rules for overflow of the given language apply (e.g., that signed 3278 arithmetics in C does not overflow). */ 3279 3280 bool 3281 scev_probably_wraps_p (tree base, tree step, 3282 gimple at_stmt, struct loop *loop, 3283 bool use_overflow_semantics) 3284 { 3285 struct nb_iter_bound *bound; 3286 tree delta, step_abs; 3287 tree unsigned_type, valid_niter; 3288 tree type = TREE_TYPE (step); 3289 3290 /* FIXME: We really need something like 3291 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. 3292 3293 We used to test for the following situation that frequently appears 3294 during address arithmetics: 3295 3296 D.1621_13 = (long unsigned intD.4) D.1620_12; 3297 D.1622_14 = D.1621_13 * 8; 3298 D.1623_15 = (doubleD.29 *) D.1622_14; 3299 3300 And derived that the sequence corresponding to D_14 3301 can be proved to not wrap because it is used for computing a 3302 memory access; however, this is not really the case -- for example, 3303 if D_12 = (unsigned char) [254,+,1], then D_14 has values 3304 2032, 2040, 0, 8, ..., but the code is still legal. */ 3305 3306 if (chrec_contains_undetermined (base) 3307 || chrec_contains_undetermined (step)) 3308 return true; 3309 3310 if (integer_zerop (step)) 3311 return false; 3312 3313 /* If we can use the fact that signed and pointer arithmetics does not 3314 wrap, we are done. */ 3315 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base))) 3316 return false; 3317 3318 /* To be able to use estimates on number of iterations of the loop, 3319 we must have an upper bound on the absolute value of the step. */ 3320 if (TREE_CODE (step) != INTEGER_CST) 3321 return true; 3322 3323 /* Don't issue signed overflow warnings. */ 3324 fold_defer_overflow_warnings (); 3325 3326 /* Otherwise, compute the number of iterations before we reach the 3327 bound of the type, and verify that the loop is exited before this 3328 occurs. */ 3329 unsigned_type = unsigned_type_for (type); 3330 base = fold_convert (unsigned_type, base); 3331 3332 if (tree_int_cst_sign_bit (step)) 3333 { 3334 tree extreme = fold_convert (unsigned_type, 3335 lower_bound_in_type (type, type)); 3336 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); 3337 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type, 3338 fold_convert (unsigned_type, step)); 3339 } 3340 else 3341 { 3342 tree extreme = fold_convert (unsigned_type, 3343 upper_bound_in_type (type, type)); 3344 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); 3345 step_abs = fold_convert (unsigned_type, step); 3346 } 3347 3348 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); 3349 3350 estimate_numbers_of_iterations_loop (loop, true); 3351 for (bound = loop->bounds; bound; bound = bound->next) 3352 { 3353 if (n_of_executions_at_most (at_stmt, bound, valid_niter)) 3354 { 3355 fold_undefer_and_ignore_overflow_warnings (); 3356 return false; 3357 } 3358 } 3359 3360 fold_undefer_and_ignore_overflow_warnings (); 3361 3362 /* At this point we still don't have a proof that the iv does not 3363 overflow: give up. */ 3364 return true; 3365 } 3366 3367 /* Frees the information on upper bounds on numbers of iterations of LOOP. */ 3368 3369 void 3370 free_numbers_of_iterations_estimates_loop (struct loop *loop) 3371 { 3372 struct nb_iter_bound *bound, *next; 3373 3374 loop->nb_iterations = NULL; 3375 loop->estimate_state = EST_NOT_COMPUTED; 3376 for (bound = loop->bounds; bound; bound = next) 3377 { 3378 next = bound->next; 3379 ggc_free (bound); 3380 } 3381 3382 loop->bounds = NULL; 3383 } 3384 3385 /* Frees the information on upper bounds on numbers of iterations of loops. */ 3386 3387 void 3388 free_numbers_of_iterations_estimates (void) 3389 { 3390 loop_iterator li; 3391 struct loop *loop; 3392 3393 FOR_EACH_LOOP (li, loop, 0) 3394 { 3395 free_numbers_of_iterations_estimates_loop (loop); 3396 } 3397 } 3398 3399 /* Substitute value VAL for ssa name NAME inside expressions held 3400 at LOOP. */ 3401 3402 void 3403 substitute_in_loop_info (struct loop *loop, tree name, tree val) 3404 { 3405 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); 3406 } 3407