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